Knapsack Cryptography는 배낭문제(Knapsack Problem)에서 비롯된 공개키 암호화 방법이다. Knapsack Problem에서 Superincreasing Sequence의 경우 다항 시간 내에 해를 구할 수 있지만, General Sequence인 경우 NP-문제가 된다.
수신자(private key를 갖는 쪽)는 다음을 미리 계산하고, H를 공개한다.
- S = [1, 3, 7, 13, 26, 65, 119, 267]
- n = 523 (bigger than sum of S)
- w = 467 (coprime with 523)
- wi = 28 (467 * 28 % 523 = 1)
- H = [467, 355, 131, 318, 113, 21, 135, 215] (S * w % n)
여기서 S는 Superincreasing Sequence이다.
Encryption
발신자가 보낼 메시지를 M = 01001011이라고 하자. 발신자는 M의 각 비트를 H의 각 요소와 곱함으로써 암호문을 얻는다.
M * H
= 0 * 467 + 1 * 355 + 0 * 131 + 0 * 318 + 1 * 113 + 0 * 21 + 1 * 135 + 1 * 215
= 818
Decryption by Third Party
제3자가 암호문 818을 가로채 해독을 시도한다고 가정하자.
H는 공개되어 있기 때문에 합이 818이 되는 H의 요소를 알아내면 복호화에 성공하는 것이다. 하지만, 이는 General Sequence에 대한 Knapsack Problem이다. 비록 지금은 H와 암호문의 크기가 비교적 작기 때문에 충분한 시간 내에 풀 수 있지만, H와 암호문의 크기가 커질수록 난이도는 급상승한다.
Decryption
제3자와 마찬가지로, H만으로 M을 알아내는 것은 매우 힘들다. 하지만, General Sequence인 H는 Superincreasing Sequence인 S로부터 계산된 것이다. 따라서 H로 계산된 암호문을 S에 대한 숫자로 바꾼다면 복호화가 가능해진다.
암호문 818은 M * H이고, H = (S * w) % n이다. 다음과 같이 T를 구한다.
T = (wi * 818) % n
= (wi * M * H) % n
= (M * wi * H) % n
= (M * wi * ((S * w) % n)) % n
= (M * (wi * S * w % n)) % n
= (M * S * 1) % n
= (M * S) % n
= M * S
식을 통해 알 수 있듯이, T는 M과 S의 곱과 같다. 즉, 합이 T가 되는 S의 요소를 구하는 것은 Superincreasing Sequence를 이용하는 Knapsack Problem이므로 쉽게 풀 수 있다. 이 예제에서 T는 (28 * 818) % 523 = 415이다. 합이 415가 되는 S의 요소는 3, 26, 119, 267이므로 M = 01001011임을 알 수 있다.
+ 개인적인 생각
S를 선정할 때, 첫번째 수가 1인 것은 좋지 않다는 생각이 들었다. S의 첫번째 수가 1이라면, H의 첫번째 수는 w가 된다. 비록 w를 알아낸다고 해도 곧바로 암호문을 해독할 수 있는 것은 아니지만, 비밀 키 중 하나가 드러나는 것은 좋을 것이 없기 때문이다.
