[Stream Cipher] A5/1

[Stream Cipher] A5/1

 

A5/1이란?

- Stream cipher 방식을 사용하는 것으로, 쉬프트 레지스터를 기반으로 한다.

- GSM 핸드폰 시스템에서 사용된다.

- bit단위로 키 스트림이 생성된다.

 

 

A5/1은 3개의 선형 피드백 쉬프트 레지스터(LFSR)로 구성된다.

- X: 19 bits (

, 

, 

, …, 

)

 

- Y: 22 bits (

, 

, 

, …, 

)

 

- Z: 23 bits (

, 

, 

, …, 

)

 

 

Key K:

 

- 총 64비트이다.

 

- 처음에 X, Y, Z레지스터를 채운다.

 

- 각 값은 단일 비트이고, Key는 레지스터의 초기값 채울 때 사용한다.

 

A5/1 Algorithm.

 

m = maj(

, 

, 

)    // X, Y, Z중에서 가장 많은 수를 고른다.

 

Ex) maj(0, 1, 0) = 0 and maj(1, 1, 0) = 1

 

if 

 == m then  

t = 

XOR 

XOR

XOR

for(i=18; i>0;i--) 

=

;

= t;

if 

 == m then

t = 

XOR

for(i=21; i>0;i--) 

=

;

= t;

if 

 == m then

t = 

XOR 

XOR

XOR

for(i=22; i>0;i--) 

=

;

= t;

 

Key stream bit 값: 

 XOR 

 XOR 

 

위에 한것을 암호화 해야하는 비트 수 만큼 반복하여 Key stream을 얻은 후, Key stream과 Plaintext를 XOR 연산하여 Ciphertext를 만들어낸다.

 

 

Ex)

 

위 예시를 보면,

m = maj(

, 

, 

)  = maj(1, 0, 1) = 1

 

X와 Z는 실행되고, Y는  

 ≠ m 이므로 실행되지 않는다.

여기서 Key stream은  0 XOR 1 XOR 0 = 1 이 될 것이다.