배낭 암호 (Knapsack cryptosystem)

배낭 암호

• 배낭의 무게가 N일때 a0~ak까지 물건의 무게의 합이 정확히 N일때를 찾아야함
• 오늘날의 표준 기준으로 보면 안전하지 않지만, 오늘날 사용하는 공개키 암호 시스템을 만드는 토대가 되었다.

정의

a=[a1,a2, ,,, ,ak], x=[x1,x2, ,,, ,xk], xi=0 또는 1

s=knapsackSum(a,x)=x1a1+x2a2+ ,,, + xkak이다.

주어진 a와 x로부터 s를 계산하는것은 아주 쉽다. 하지만 s와 a가 주어졌을때 x를 구하는 것은 어렵다.

초증가 순서짝

→ ai ≥ a1+ a2+… +ai-1 인 경우를 말한다.

즉, a1을 제외한 각 원소가 그 이전의 모든 원소의 합보다 크거나 같을 때를 말한다.

 

 

초증가 k-순서짝에 대한 knapsackSum과 inv_KnapsackSum

예제

a = [17, 25, 46, 94, 201, 400] 이고 s = 272라고 가정하자 knapsackSum과 inv_knapsackSum을 이용하여 순서짝x구하기

i	ai	s	s >= ai	xi	s <- s- ai * xi
6	400	272	false	x6=0	272
5	201	272	true	x5=1	71
4	94	71	false	x4=0	71
3	46	71	true	x3=1	25
2	25	25	true	x2=1	0
1	17	0	false	x1=0	0

이러한 경우에 x = [0, 1, 1, 0, 1, 0]이다. 즉, 25,36,201이 배낭속에 들어있다는것을 나타낸다.

 

배낭 암호를 이용한 비밀 통신

키 생성

1. 초증가 k-순서짝 b=[b1, b2, ... , bk]를 만든다.
2. 모듈로 n>b1+b2+ ... +bk 을 만족하는 n을 선정한다.
3. n과 서로소이면서 1≤r≤n-1 인 임의의 정수 r을 선택한다.
4. ti=r * bi mod n 을 만족하는 순서짝 t=[t1, t2, ... ,tk] 를 생성한다.
5. 치환을 통해 새로운 순서짝 a=[a1, a2, ... , ak] (a = permute(k)) 을 구한다.
6. k-순서짝 a는 공개키로 n, r, k-순서짝b 는 개인키로 사용한다.

암호화

Alice가 Bob에게 메시지를 보낸다고 가정

1. Alice 메시지를 순서짝 x=[x1,x2, ... , xk] 로 변환시킨다. 여기에서 xi=0 or 1이며, 순서짝 x가 평문이다.
2. Alice는 knapsacksum 알고리즘을 사용해서 s를 계산. 만들어지 암호문 sㄴ를 Bob에게 보냄

복호화

Bob은 암호문 s를 수신하는 가정

1. Bob은 보관 중인 개인키 즉, n,r 을 이용하여 암호문 s로부터 s'=s x r-1 mod n 을 계산한다.
2. 보관 중인 개인키 즉, 순서짝 b=[b1,b2, ..., bk]를 이용하여 Bob은 x'- inv_knapsackSum(s',b) 을 계산하여 x'을 구한다.
3. x' 을 치환하면 x가 평문이다.

예제

1. 키생성

1. Bob은 초증가 순서 짝 b = [7,11, 19, 39, 79, 157, 313]을 만든다
2. Bob은 모듈로 n=900, r = 37을 선택한다. 치환표로 [4 2 5 3 1 7 6]을 택한다.
3. Bob은 순서 짝 t = [259, 407 703, 543, 223, 409, 781]를 계산한다.
4. Bob은 순서 짝 a = permute(t) = [543, 407, 223, 703, 781, 409]를 계산한다.
5. Bob은 a를 공개한다. 그리고 n, r, b는 비밀로 한다.

2. Alice가 단 하나의 문자 “g”만을 Bob에게 보낸다고 가정을 해보자.

1. Alice는 7-비트 아스키코드를 이용해 “g”를 (1100111)2로 부호화한다. 그런 다음 순서짝 x=[1,1,0,0,1,1,1]인 평문을 생성한다.
2. Alice는 s = knapsackSum(a,x) = 2165인 Bob에게 보낼 암호문 생성한다.

3. Bob은 암호문 s=2165를 복호화할 수 있다.

1. Bob은 s’ = s * r^-1mod n = 2165 * 37^-1mod900 = 527을 계산한다.
2. Bob은 x’ = inv-knapsackSum(s’, b) = [1,1,0,1,0,1,1]을 계산한다.
3. x = permute(x’)=[1,1,0,0,1,1,1]를 계산하여 (1100111)2 를 얻어 “g를 얻는다.