선형 피드백 시프트 레지스터

Linear Feedback Shift Register; LFSR

레지스터의 몇 개 비트를 XOR한 값을 입력으로 되먹이면서 한 칸씩 밀어내어 비트열을 만드는 회로

• 하드웨어로 간단히 구현되어 스트림 암호의 키 스트림 생성, 스크램블러, CRC 계산, 의사 난수 생성에 쓴다.
• 되먹임에 사용하는 비트 위치를 탭(tap)이라 하고, 탭 위치를 다항식으로 나타낸 것을 특성 다항식(feedback polynomial)이라 한다. 다항식의 차수가 레지스터의 비트 수다.

주기

• n비트 LFSR의 상태는 2ⁿ가지지만 전부 0인 상태는 그 상태에 머물러 빠져나오지 못하므로 수열에 쓰이지 않는다.
• 특성 다항식이 원시 다항식(primitive polynomial)이면 나머지 모든 상태를 한 번씩 거치므로 주기가 최대가 된다.

최대 주기 = 2ⁿ − 1

• 이렇게 최대 주기를 갖는 수열을 M-수열(maximum length sequence)이라 한다.
• 기약 다항식(irreducible)이라도 원시 다항식이 아니면 주기는 2ⁿ − 1의 약수가 된다.
  • 8차라면 2⁸ − 1 = 255 = 3 × 5 × 17 이므로 주기는 3, 5, 15, 17, 51, 85, 255 중 하나다.
  • 7차라면 2⁷ − 1 = 127이 소수이므로 기약이면 곧 주기가 127이다.

암호에서의 한계

• 되먹임이 선형이라 연속된 2n비트만 알면 버레캠프-매시(Berlekamp-Massey) 알고리즘으로 특성 다항식과 이후 수열 전체를 복원할 수 있다.
• 그래서 실제 스트림 암호는 LFSR 여러 개를 비선형으로 조합하거나(A5/1, E0) 비선형 필터를 덧붙여 쓴다.

같이 보기

• 스트림 암호
• 선형 합동 생성기
• 의사 난수 생성기