[암호론]10. 스트림 암호, LFSR(Linear Feedback Shift Register) 선형 피드백 시프트 레지스터

지금까지 설명한 암호들은 모두  평문을 하나 이상의 문자나 비트로 된 블록으로 나누어 블록마다 독립적으로 암호화한 블록 암호(block cipher)였습니다.

이번에 소개 할 암호는 이와 대조를 이루는 스트림 암호(stream cipher)입니다.

스트림 암호는 bit 또는 byte의 작은 단위를 암호화 하는데,

다음 암호화가 이전 암호화에 영향을 받는다는 특징이 있습니다.

스트림 암호는 암호화 속도가 빠르고 에러 전달 가능성이 낮다는 장점이 있고,

혼돈을 일으키는 연산이 암호화가 진행되는 동안 누적 될 수 있으므로 간단하고 빠른 연산으로 상당한 혼돈을 이뤄낼 수 있습니다.

 

앞에서 알펴본 것처럼 반복키 암호는 반복을 이용해서 해독 할 수 있고 

연속키 암호는 빈도분석을 이용해서 해독 할 수 있었습니다.

그렇지만 키가 오직 한 번만 사용된다면 빈도 분석이나 알려진 평문공격을 견딜 수 있게됩니다.

이렇게 키를 오직 한 번만 사용하는 암호체계를 일회성 패드(one-time pad)라고 합니다.

섀넌은 평문의 길이만큼 키도 길고 모든 키는 사용될 수 있는 확률이 같다면 

일회성 패드는 완벽한 안정성을 지닌 암호라고 했습니다.

하지만 일회성 패드 기법은 굉장히 많은 난수키 재료가 필요하고

송신자와 수신자가 이를 교환하는 방법을 찾아야하므로 현실적으로 사용이 어려웠습니다.

 

이를 극복하기 위한 암호 방식으로 자동키 암호(autokey cipher)가 고안되었습니다.

이는 평문이나 암호문, 키텍스트의 일부분을 사용해 새로운 키텍스트를 생성하는 암호입니다.

여러 가지의 자동키 암호 중에서 하나 이상의 이전 블록을 통해서 새로운 키 블록을 생성함으로써 암호의 안정성을 높일 수 있습니다.

가장 처음 사용할 기본키인 초기화 벡터(initialization vector)와 이와같은 점화식을 통해 n번째 자리에 오는 키 숫자를 생성할 수 있습니다.

i 와 j 는 생성되는 숫자가 키스트림에서 얼마나 뒤로 갈지 결정하고 m은 모듈로를 정하게 됩니다.

 

이와같은 점화식을 사용해 키스트림을 생성하는 물리적 장치 또는 가상 장치를 선형 피드백 시프트 레지스터(Linear Feedback Shift Register)라고 합니다.

'선형'은 식의 유형을 가르키고, '피드백'은 이전 값을 사용해 새로운 값을 생성하기 때문에 붙여졌습니다.

'시프트 레지스터'는 장치를 만들 때 사용된 전기 회로 유형을 가르킵니다.

LFSR에서 가장 흔히 사용되는 모듈러는 2입니다. 

모듈러가 2이면 모든수를 0과1로 나타낼 수 있고 이를 컴퓨터의 bit라고 생각 할 수 있습니다.

 

이 LFSR을 보면 11,13,14,16번째 bit의 XOR결과가 새로운 feedback으로 입력되고 

전에 16번째 bit가 출력이 됩니다.

평문과 같은 길이의 키스트림이 완성되면 평문과 XOR연산을 해 암호문을 완성시킵니다.

 

예를 한번 살펴봅시다.

"send $."라는 평문을 초기화 벡터 '1111' 과 c1 = c3 = 1, c2 = c4 = 0인 LFSR을 가지고 암호화 해봅시다.

우리가 설계한 LFSR은 bit를 출력하므로 평문도 ASCII 표의 숫자를 bit로 나타낸 후 암호화 합니다.

평문	s	e	n	d		$	.
ASCII	1010011	1100101	1101110	1100100	0100000	0100100	0101110
키스트림	1111001	1110011	1100111	1001111	0011110	0111100	1111001
암호문비트열	0101010	0010110	0001001	0101011	0111110	0011000	1010111
십진수	42	22	9	43	62	24	87

 

선형 피드백 시프트 레지스터는 선형성 때문에 알려진 평문 공격에 취약합니다.

안정성을 개선할 수 있는 방법으로는 비선형 피드백 함수를 사용하거나,

두 개이상의 셀 값을 선택해 이를 결합하거나

LFSR 안에서 비트가 이동하는 시간을 제어하는 클록을 변경하는 방법 등이있습니다.

 

오늘도 긴글 읽어주셔서 감사합니다.