배낭암호

전 글에서 공개키 암호에 대해 간략히 알아보았는데 첫 번째로 여러 공개키 암호체계 중 배낭암호 체계에 대해서 알아보자.
배낭암호는 공개키 암호로 제일 먼저 제안되었기 때문이다. 이 외에도 표준 공개키 암호인 RSA 도 있는데 다음 글에서 알아보도록 하겠다.

배낭암호는 머클과 헬먼에 의해 제안되었다.
머클-헬먼 배낭암호체계는 NP-complete로 알려진 문제를 기반으로 하고 있다.

NP-complete
계산 복잡도 이론에서 NP-complete는 가장 어려운 문제이다. 현재 NP-complete 문제를 위해 알려진 알고리즘은 모두 문제의 크기에서 지수적인 시간을 요구한다.

배낭 문제를 수식으로 표현해보자.
n개의 배낭에 담을 수 있는 무게가 각각 다음과 같이 주어졌다고 하자.
W(0), W(1), ... , W(n-1)

요구되는 전체 무게 S를 충족하기 위해 배낭을 어떻게 조합해야 할까??
a(i) = ∈ {0,1}
a(0),a(1), ... , a(n-1) 을 찾는 문제가 바로 배낭문제이다.
S = a(0)W(0) +  a(1)W(1) + ... + a(n-1)W(n-1)

위 수식으로 보면 뭔가 복잡해 보인다. 괜히 쉬운 말을 어렵게 표현하는게 젤 싫으므로 예제로 바로 봐보자.

주어진 배낭 무게
85, 13, 9, 7, 47, 27, 99, 86
이 때 요구되는 전체 무게 S = 172

172 = 85 + 13 + 47 + 27
이므로 답은 존재한다.
a = (a(0), a(1), a(2), a(3), a(4), a(5), a(6), a(7)) = (11001100) 

이렇게 일반적인 배낭 문제는 NP-complete 로 알려져 있지만, 문제를 푸는 데 걸리는 시간이 배낭의 갯수에 선형적으로 비례하는 특수한 경우도 있다.

위에서 본 배낭은 일반 배낭 문제 이다.

수퍼증가 배낭 문제 에 대해 알아보자.
수퍼증가 배낭 문제는 배낭의 무게가 작은 수에서 큰 수로 정리되고,
각 무게는 그 앞의 무게를 전부 합한 무게보다 더 크다는 점을 제외하고는 일반 배낭 문제와 동일하다.

수퍼증가 배낭 문제 예이다.
3, 6, 11, 25, 46, 95, 200, 411

문제를 해결하는 방법은 일반 배낭 문제와 동일하다.
S = 309 라면
S에서 a(7)에서부터 빼는데 뺀 결과가 음수면 빼지 않고 a(6)과 비교하게끔 .. 하는 방식이다.

309 - 411 < 0  ==> a(7) = 0
309 - 200 > 0 ==> a(6) = 1
109 - 95 > 0 ==> a(5) = 1
14 - 46 < 0 ==> a(4) = 0
14 - 25 < 0 ==> a(3) = 0
14 - 11 > 0 ==> a(2) = 1
3 - 6 < 0 ==> a(1) = 0
3 - 3  == 0 ==> a(0) = 1

a = (a(0), a(1), a(2), a(3), a(4), a(5), a(6), a(7)) = (10100110)

배낭암호를 구현하기 위한 절차
1. 수퍼증가 배낭을 생성한다.
2. 수퍼증가 배낭을 일반 배낭으로 변환한다.
3. 여기서 공개키는 일반 배낭이 된다.
4. 여기서 개인키는 변환 값이 있는 수퍼증가 배낭이다. 

이제 예제 문제를 해보자. 

1. 다음과 같이 수퍼증가 배낭을 선택한다.
      (2, 3, 7, 14, 30, 57, 120, 251)

2. 수퍼증가 배낭을 일반 배낭으로 변환하기 위해 승수 m과 계수 n을 선정하는데 
m,n은 서로 소이고 n은 수퍼증가 배낭의 모든 요소의 합보다 큰 수가 되도록 선정한다. 

m = 41
n = 491

2 * m = 2 * 41 = 82 mod 491
3 * m = 3 * 41 = 123 mod 491
7 * m = 7 * 41 = 287 mod 491
14 * m = 14 * 41 = 83 mod 491
30 * m = 30 * 41 = 248 mod 491
57 * m = 57 * 41 = 373 mod 491
120 * m = 120 * 41 = 10 mod 491
251 * m  = 251 * 41 = 471 mod 491

일반 배낭 : (82, 123, 287, 83, 248, 373, 10, 471)  -> 공개키

변환 값 m의 역 mod 값과 수퍼증가 배낭이 함께 개인키가 된다.
m^-1 mod n = 41^-1 mod 491 = 12

A가 B에게 보낼 메시지 M = 150
150을 2진수로 변경 :  10010110 (2)

일반 배낭(공개키)과 비교해 1로 표시된 부분 값을 전부 더함
82 + 83 + 373 + 10 = 548 = C

B는 수퍼증가배낭과 m^-1을 사용해 복호화

C * m^-1 mod n = 548 * 12 mod 491 = 193

193을 수퍼증가배낭을 사용해 값 뽑아냄
193 - 251 < 0 ==> a(7) = 0
193 - 120 > 0 ==> a(6) = 1
73 - 57 > 0 ==> a(5) = 1
16 - 30 < 0 ==> a(4) = 0
16 - 14 > 0 == > a(3) = 1
2 - 7 < 0 ==> a(2) = 0 
2 - 3 < 0 ==> a(1) = 0 
2 - 2 == 0 ==> a(0) = 1

M = (10010110)  복호화 성공

개인키가 없는 공격자 입장에서 암호문을 복호화하기 위해 공개키 요소의 부분집합의 합이 암호문 C값과 일치하도록 하는 요소를 찾아내야한다. 즉, 공개키인 (82, 123, 287, 83, 248, 373, 10, 471)를 가지고 548을 풀어야한다.

배낭암호체계의 트랩도어는 mod 연산을 사용해 수퍼증가배낭을 일반 배낭으로 변환할 때 발생한다.

하지만 이 암호체계는 보안성이 없다. "격자 줄이기" 로 알려진 기법을 사용하면 높은 확율로 평문을 찾을 수 있다.