LFSR

💻 선형 피드백 시프트 레지스터 (LFSR, Linear Feedback Shift Register)

LFSR (Linear Feedback Shift Register, 선형 피드백 시프트 레지스터)는 시프트 레지스터와 선형 피드백 함수로 구성된 디지털 회로입니다. 이는 빠르고 효율적인 의사 난수 비트 생성기 (PRBG, Pseudo-Random Bit Generator)를 구현하는 데 사용됩니다.

1. ⚙️ 구성 요소와 작동 원리

LFSR은 이름 그대로 두 가지 주요 구성 요소로 이루어져 있습니다.

A. 시프트 레지스터 (Shift Register)

• 기능: $n$개의 플립플롭(Flip-flop)으로 구성되어 $n$비트의 상태(State)를 저장합니다.
• 작동: 클럭 펄스(Clock Pulse)가 들어올 때마다 현재 저장된 모든 비트가 오른쪽(혹은 왼쪽)으로 한 칸씩 이동합니다. 가장 오른쪽 비트가 출력(Output)으로 나갑니다.

B. 선형 피드백 함수 (Linear Feedback Function)

• 기능: 레지스터 내의 특정 위치에 있는 비트들(탭, Taps)을 선택하여 배타적 논리합 (XOR, Exclusive-OR) 연산을 수행하고, 그 결과를 레지스터의 가장 왼쪽 칸으로 되먹임(Feedback)합니다.
• 선형성: 피드백 함수가 오직 XOR 연산만으로 구성되어 있기 때문에 선형(Linear)입니다.

2. 🔢 LFSR의 출력과 주기

LFSR은 결정론적(Deterministic) 장치입니다. 즉, 초기 상태(Initial State)가 결정되면 이후의 모든 출력 비트열이 정해집니다.

• 주기 (Period): LFSR이 생성하는 비트열은 주기성을 가집니다. 레지스터의 상태는 언젠가 반드시 초기 상태로 되돌아오고, 그 순간부터 수열이 반복됩니다.
• 최대 주기: $n$비트 LFSR의 가능한 상태는 $2^n$개입니다 (모든 비트가 0인 상태 제외). 따라서 최대 주기는 $2^n - 1$이며, 이러한 최대 주기를 달성하는 LFSR을 최대 주기 LFSR (Maximal Length LFSR)이라고 부릅니다. 이 최대 주기는 피드백 탭의 위치를 결정하는 원시 다항식 (Primitive Polynomial)에 의해 결정됩니다.

3. 🛡️ 암호학적 의미 및 한계

LFSR은 구현이 간단하고 매우 빠르다는 장점 때문에 암호화에 널리 사용되지만, 단일 LFSR 자체는 안전하지 않습니다.

• 취약성 (선형성): LFSR이 생성하는 키스트림은 선형 함수(XOR)로 구성되므로, 생성된 출력 비트열의 일부(최대 $2n$ 비트)만 알고 있어도 선형 대수학적 방법을 통해 LFSR의 내부 상태와 피드백 탭 위치(즉, 키)를 효율적으로 분석할 수 있습니다. 이는 선형 복잡도(Linear Complexity)가 낮다는 것을 의미합니다.
• 활용: 이 때문에 현대의 안전한 스트림 암호에서는 LFSR을 단독으로 사용하지 않고, 여러 개의 LFSR을 비선형 결합 함수(Nonlinear Combination Function)나 비정규 클럭(Non-regular Clocking)과 조합하여 비선형성(Nonlinearity)을 높이고 예측 불가능하게 만듭니다.

예시: GSM 암호인 A5/1이나 블루투스 암호 등 초기의 스트림 암호들은 여러 개의 LFSR을 복잡하게 조합하여 사용했습니다.

LFSR은 간단하면서도 빠른 키스트림 생성의 기반이 되지만, 그 자체의 선형성 때문에 보안 강화를 위한 추가적인 비선형 메커니즘이 필수적입니다.