LFSR (Linear-Feedback Shift Register)
CTF 문제들을 둘러보다 Crypto 분야에서 이 개념을 사용하는 문제가 있어서 여기에 개념만 간략히 정리해보려고 한다. 디지털 회로에서, 현재 상태에 대한 선형 연산(linear function)으로 다음 상태를 만드는 레지스터다. 해당 연산에는 다양한 종류들이 있겠지만, 일반적으로 쓰이는 건 XOR이라고 한다. LFSR의 초기값은 시드(seed)라고 부르며 다음 상태를 생성하는 연산에 관여하는 비트는 tap이라고 한다. 또 가장 오른쪽에 있는 비트를 output bit라고 한다. 기본적인 내용은 다음과 같다. LFSR의 초기값을 다음과 같은 8bit 정수로 놓는다. 현재의 상태는 0x59라고 말할 수 있다. LFSR의 tap이 8번째, 6번째, 5번째 비트라고 가정해보자. 현재 상태의 output b..
