자가수축발전기
Self-shrinking generator자가수축 발전기는 수축 발전기 개념을 기반으로 하는 유사 발전기이다. 선형피드백 시프트 레지스터(LFSR)에 기초한 자가수축 발전기의 변형은 암호화에 사용하기 위해 연구된다.[who?]
알고리즘.
두 번째 피드백 시프트 레지스터를 사용하여 첫 번째의 출력을 제어하는 수축 발전기와는 달리, 자기축소 발전기는 단일 레지스터의 교차 출력 비트를 사용하여 최종 출력을 제어한다. 이러한 종류의 발전기를 클럭화하는 절차는 다음과 같다.
- LFSR을 두 번 클럭하여 비트 쌍을 LFSR 출력으로 얻으십시오.
- 쌍이 10이면 0이다.
- 쌍이 11이면 1개 출력
- 그렇지 않으면 아무것도 출력하지 않는다.
- 1단계로 돌아가십시오.
예
이 예에서는 연결 다항식 x8 + x4 + x3 + 1과2 초기 레지스터 채우기 1 0 1 0 1 0을 사용한다.
아래 표에는 LFSR의 각 반복에 대해 최종 제너레이터 출력뿐만 아니라 자체 축소 전의 중간 출력 목록이 나와 있다. 연결 다항식으로 정의된 탭 위치는 파란색 헤딩으로 표시된다. zeroth 반복의 상태는 초기 입력을 나타낸다.
| 반복 # | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 중간 출력 | 제너레이터 출력 |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 해당 없음 | 해당 없음 |
| 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 해당 없음 |
| 2 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | |
| 3 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
| 4 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 |
4회 반복이 끝나면 중간 비트의 순서는 0110이다.
첫 번째 비트 쌍인 01은 10이나 11과 일치하지 않기 때문에 폐기된다. 두 번째 비트 쌍인 10은 알고리즘의 두 번째 스텝과 일치하므로 0이 출력된다.
위에서 설명한 것처럼 LFSR을 계속 클럭화하고 출력을 축소하여 더 많은 비트를 생성한다.
암호해석
Meier와 Steffelbach는 그들의 논문에서 길이 L의 연결 다항식을 가진 LFSR 기반의 자체 수축 발전기가 출력 시퀀스 주기가L/2 최소 2이고 선형 복잡성이 최소L/2-1 2라는 것을 증명한다.[1]
게다가, 그들은 모든 자가 수축 발전기가 수축 발전기로 표현될 수 있다는 것을 보여준다. 역도 또한 사실이다. 수축 발전기는 자체 수축 발전기로 구현될 수 있지만, 그 결과 발전기는 최대 길이가 아닐 수 있다.
저자들에 의해 제시된 공격은 알려진 연결 다항식이라고 가정할 때0.7L 약 2단계가 필요하다.
Mihaljevich가 발견한 보다 진보된8 공격은 4.9 x 10비트의 출력 시퀀스를 이용하여 약 2단계에57 걸쳐 레지스터 100비트를 깨뜨릴 수 있다.[2]
또 다른 공격
참조
- ^ "자수축 발전기", Cryptology-Eurocrypt 1994(LNCS 950), 205-214, 1995.
- ^ 1995년 12월 영국 서커스터 "자수축 발전기 보안 검사"
- ^ Zenner, Erik; Krause, Matthias; Lucks, Stefan. "Improved Cryptanalysis of the Self-Shrinking Generator". Information Security and Privacy 13th Australasian Conference ACISP 2008: 30. Retrieved 12 April 2016.
