교류 발전기

Alternating step generator

암호학에서 교류 스텝 발생기(ASG)는 3개의 선형 피드백 시프트 레지스터에 기초하여 스트림 암호에 사용되는 암호 유사수 생성기다. 제3 LFSR의 출력에 따라 2개의 LFSR이 번갈아 가며 스텝(클록)되는 조합이다.

이 디자인은 1987년에 출판되었고 1989년에 C. G. Günter에 의해 특허를 받았다.[1][2]

개요

선형 피드백 시프트 레지스터(LFSR)는 통계적으로 말하면 우수한 유사성 생성기로, 분포가 양호하고 구현이 단순하다. 단, 산출량을 쉽게 예측할 수 있기 때문에 그대로 사용할 수 없다.

ASG는 3개의 선형 피드백 시프트 레지스터로 구성되며, 편의상 LFSR0, LFSR1 및 LFSR2라고 부른다. 예를 들어 LFSR2가 0을 출력하면 LFSR0이 클럭되고, 1을 출력하면 LFSR1이 클럭킹된다. 출력은 LFSR0과 LFSR1이 생산한 마지막 비트의 독점 OR이다. 세 개의 LFSR의 초기 상태가 관건이다.

관례적으로 LFSR은 각 LFSR이 최대 길이 시퀀스를 생성하도록 0이 아닌 상태로 사전 설정된 뚜렷하지만 가까운 수준의 원시 다항식을 사용한다. 이러한 가정 하에서 ASG의 출력은 장기간, 높은 선형 복잡성, 그리고 짧은 반복성의 분포까지 명백하게 가지고 있다.

C의 예 코드: 

/* 16비트 장난감 ASG(실제로 사용하기에는 너무 작음), 반품 0 또는 1. */ 서명이 없는 ASG16토이(공허하게 하다) {   정태의 서명이 없는 /* 최소 16비트의 서명되지 않은 유형 */     lfsr2  = 0x8102, /* 초기 상태, 16비트, 0 */이어서는 안 된다.     lfsr1  = 0x4210, /* 초기 상태, 15비트, 0 */이어서는 안 된다.     lfsr0  = 0x2492; /* 초기 상태, 14비트, 0 */이어서는 안 된다.    /* LFSR2 사용 x^16 + x^14 + x^13 + x^11 + 1 */   lfsr2 = (-(lfsr2&1))&0x8016 ^ lfsr2>>1;    만일 (lfsr2&1)     /* LFSR1은 x^15 + x^14 + 1 */ 사용     lfsr1 = (-(lfsr1&1))&0x4001 ^ lfsr1>>1;   다른     /* LFSR0은 x^14 + x^13 + x^3 + x^2 + 1 */ 사용     lfsr0 = (-(lfsr0&1))&0x2C01 ^ lfsr0>>1;    돌아오다 (lfsr0 ^ lfsr1)&1; }

ASG는 하드웨어에서 구현이 매우 간단하다. 특히 축소되는 발전기와 자체수축 발전기와는 달리 각 클럭마다 출력 비트가 생성돼 타이밍 공격에 대한 일관된 성능과 저항을 보장한다.

보안

Shahram Khazaei, 사이먼 피셔, 빌리 Meier[3]. O(L2.2 2L/3){O(L^{2}.2^{2L/3})\displaystyle}그리고 O(22L/3){\displaystyle O(2^{2L/3})점근 복잡도와 함께는 공대지 사격의 암호 해독 시간 복잡성과 출력의 양이 공격을 감행하기 위해 필요한 예를 들사이의 다양한 트레이드 오프를 허용하는 준다.} 비트, 여기서 은 세 개의 LFSR 중 가장 짧은 크기입니다.

참조

  1. ^ Günther, C. G. (1988). "Alternating Step Generators Controlled by De Bruijn Sequences". Advances in Cryptology — EUROCRYPT' 87. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 304: 5–14. doi:10.1007/3-540-39118-5_2. ISBN 978-3-540-39118-0 – via SpringerLink.
  2. ^ Gunther, Christoph-Georg (1989-03-28). "US4817145A - Generator for generating binary ciphering sequences". Google Patents.
  3. ^ Khazaei, Shahram; Fischer, Simon; Meier, Willi (2007). "Reduced Complexity Attacks on the Alternating Step Generator". Selected Areas in Cryptography. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 4876: 1–16. doi:10.1007/978-3-540-77360-3_1. ISBN 978-3-540-77360-3 – via SpringerLink.
  • 슈나이어, 브루스 Applyed Cryptography (p383-384), Second Edition, John Wiley & Sons, 1996. ISBN 0-471-11709-9