# 피드백 이월 시프트 레지스터 (Feedback with Carry Shift Register, FCSR)

피드백 이월 시프트 레지스터(Feedback with Carry Shift Register, FCSR)는 선형 피드백 시프트 레지스터(LFSR)와 비슷하지만, 피드백 계산에서 생기는 올림수(캐리)를 별도의 메모리에 저장해 다음 계산에 반영하는 수열 생성기입니다. 1990년대 클래퍼(Klapper)와 고레스키(Goresky)가 체계화했으며, LFSR이 GF(2) 위의 다항식 연산으로 설명되듯 FCSR은 2-adic 정수(2진 정수)의 산술로 설명됩니다.

## 캐리의 의미

큰 수를 손으로 더할 때 오른쪽 자리부터 더하고, 합이 넘치면 올림수를 다음 자리로 넘깁니다. LFSR은 비트들을 XOR로만 더해 올림수를 버리지만, FCSR은 비트들을 정수로 더하고 그 올림수를 기억해 다음 단계에 더합니다.

## 동작 방식

길이 r의 레지스터에 비트 an−1, …, an−r가 있고, 정수 메모리 m과 연결 계수 q1, …, qr(0 또는 1)이 있다고 합시다. 매 단계마다 다음을 계산합니다.

1. σ = q1an−1 + q2an−2 + … + qran−r + m (보통의 정수 덧셈)
2. 새 비트 an = σ mod 2를 레지스터에 밀어 넣습니다.
3. 새 메모리 값 m = ⌊σ / 2⌋로 올림수를 저장합니다.

연결 계수로 정해지는 “연결 정수” q = −1 + q1·2 + q2·2^2 + … + qr·2^r가 LFSR의 연결 다항식과 같은 역할을 합니다. FCSR의 출력 수열은 유리수 −p/q의 2-adic 전개와 같으며, 주기는 q를 법으로 한 2의 위수에 따라 정해집니다.

## 성질

- **l-수열:** q가 소수이고 2가 q의 원시근이면 주기가 최대인 q − 1이 됩니다. 이런 수열을 l-수열이라고 하며, LFSR의 m-수열에 대응합니다.
- **2-adic 복잡도:** 어떤 수열을 만들 수 있는 가장 작은 FCSR의 크기를 2-adic 복잡도라고 합니다. 선형 복잡도와 함께 수열의 예측 가능성을 평가하는 척도로 쓰이며, 이를 계산하는 유리 근사 알고리즘이 있습니다.
- **비선형성:** 캐리 때문에 GF(2) 위에서 보면 비선형이므로, 선형 복잡도 공격만으로는 분석하기 어렵습니다. 그러나 2-adic 산술로 보면 다시 “선형”적인 구조를 가지므로, 그 자체로 안전한 것은 아닙니다.

하드웨어로는 LFSR과 마찬가지로 시프트 레지스터와 덧셈기만으로 만들 수 있어, 구현 비용이 크지 않습니다.

## 암호에서의 사용과 한계

FCSR은 스트림 암호의 구성 요소로 제안되었습니다. 대표적인 예가 아르노(Arnault)와 베르제(Berger)의 F-FCSR 계열로, F-FCSR-H는 유럽 eSTREAM 프로젝트의 하드웨어 부문 최종 포트폴리오에 선정되었습니다. 그러나 2008년 헬(Hell)과 요한손(Johansson)이 FCSR의 캐리 동작의 편향을 이용해 짧은 키 스트림으로 내부 상태를 복구하는 공격을 발표했고, F-FCSR-H는 포트폴리오에서 제외되었습니다. 이후 설계자들은 구조를 바꾼 새 FCSR 표현을 제안했습니다.

정리하면 FCSR은 캐리를 기억하는 시프트 레지스터로, 2-adic 산술 덕분에 수학적 분석이 가능한 수열 생성기이지만, 실제 암호에 쓰려면 알려진 공격을 고려한 신중한 설계가 필요합니다.

---
출처: https://achivx.kr/glossary/feedback-with-carry-shift-register-fcsr-%ED%94%BC%EB%93%9C%EB%B0%B1-%EC%9D%B4%EC%9B%94-%EC%8B%9C%ED%94%84%ED%8A%B8-%EB%A0%88%EC%A7%80%EC%8A%A4%ED%84%B0/ · ACHIVX 용어 사전 · 수정일 2026-10-20