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

선형 피드백 시프트 레지스터(Linear Feedback Shift Register, LFSR)는 비트를 한 칸씩 옮기는 시프트 레지스터에서, 정해진 위치(탭)의 비트들을 XOR한 값을 다시 새 입력 비트로 넣는 회로이자 알고리즘입니다. 다음 상태가 이전 비트들의 XOR, 즉 GF(2) 위의 선형 함수로만 정해지기 때문에 ‘선형’이라는 이름이 붙었습니다. 구조가 단순해 하드웨어와 소프트웨어 모두에서 빠르게 의사 난수 비트열을 만들 수 있습니다.

어떻게 작동합니까?

• n비트 레지스터에 0이 아닌 초기 상태(시드)를 넣습니다.
• 클록마다 탭 위치의 비트들을 XOR해 피드백 비트를 계산합니다.
• 레지스터 전체를 한 칸 밀고, 빠져나가는 비트를 출력으로 내보내며, 빈자리에 피드백 비트를 넣습니다.
• 같은 과정을 반복하면 출력 비트열이 만들어집니다.

어느 위치를 탭으로 쓸지는 피드백 다항식(연결 다항식)으로 표현합니다. 예를 들어 4비트 LFSR에서 다항식 x⁴ + x³ + 1을 쓰면, 새 비트 = (4번째 비트) XOR (3번째 비트)가 됩니다.

주기와 최대 길이 수열

n비트 LFSR이 가질 수 있는 상태는 2ⁿ개이지만, 모든 비트가 0인 상태에서는 XOR 결과도 계속 0이므로 빠져나올 수 없습니다. 따라서 출력은 최대 2ⁿ − 1 길이에서 반복됩니다. 피드백 다항식이 원시 다항식일 때 이 최대 주기를 얻으며, 이런 출력을 최대 길이 수열(m-sequence)이라고 합니다. 위의 x⁴ + x³ + 1은 원시 다항식이어서 0이 아닌 15개 상태를 모두 거친 뒤 처음으로 돌아옵니다.

간단한 예

4개의 전구가 한 줄로 놓여 있고 켜짐은 1, 꺼짐은 0이라고 생각해 보세요. 매 단계마다 전구 줄 전체를 한 칸 옆으로 밀고, 빈자리의 새 전구는 “맨 끝 두 전구 중 정확히 하나만 켜져 있으면 켜고, 둘 다 같으면 끈다”는 규칙(XOR)으로 정합니다. 이 규칙을 따르면 무작위처럼 보이지만 규칙과 시작 상태를 아는 사람은 정확히 예측할 수 있는 패턴이 만들어집니다. 섞는 방식이 정해진 카드 한 벌처럼, 방식을 알면 순서를 알아낼 수 있습니다.

장점과 한계

• 단순함과 속도: 시프트와 XOR만 쓰므로 최소한의 하드웨어로 구현되고 고속 동작에 적합합니다.
• 통계적 성질: 최대 길이 수열은 0과 1의 개수가 거의 같고 자기 상관이 낮아, 통신 부호와 시험 패턴에 쓰기 좋습니다.
• 예측 가능성: 출력이 선형이므로, n비트 LFSR이라면 연속된 출력 약 2n비트만으로 벌레캄프-매시(Berlekamp–Massey) 알고리즘을 써서 피드백 다항식과 내부 상태를 복원할 수 있습니다. 그래서 단독으로는 안전한 암호가 되지 못합니다.
• 순환 동작: 일정 주기가 지나면 같은 출력이 반복됩니다. 더 긴 수열이 필요하면 레지스터를 늘려야 하므로 회로가 그만큼 커집니다.

실제 사용

• 오류 검출: 디지털 네트워크와 저장 장치의 CRC(Cyclic Redundancy Check) 계산은 LFSR과 같은 원리로 동작합니다.
• 회로 테스트: 전자 회로가 올바르게 작동하는지 확인하는 시험 패턴을 만듭니다.
• 통신: 확산 스펙트럼 통신에서 신호를 넓게 퍼뜨려 간섭을 줄이는 확산 부호와, 데이터 비트열을 고르게 섞는 스크램블링에 쓰입니다.
• GPS 기술: GPS 위성 신호의 확산 부호(Gold 부호)는 두 LFSR의 출력을 조합해 만듭니다.
• 컴퓨터 시뮬레이션: 무작위처럼 보이는 비트열을 빠르게 만들어 시뮬레이션의 무작위 요소로 씁니다.
• 스트림 암호: 여러 LFSR을 비선형적으로 결합하거나 불규칙하게 구동하는 방식으로 스트림 암호의 구성 요소로 쓰여 왔습니다. 선형성을 깨는 장치가 없으면 위의 이유로 쉽게 해독됩니다.