공개키암호 - 배낭암호

공개키 암호

공개키는 대칭키보다 굉장히 특별하게 수학적이기 때문에 종류가 대칭키만큼 다양하지는 않다.

​

이러한 유닠-크한 암호인 공개키는 "트랩도어 단방향 함수"를 기본으로 하고 있다.

​

함수 이름도 유닠-크한데, 간단하게 말하면 한쪽으로의 계산은 쉽지만 반대 방향은 계산이 어렵다는 뜻이다.

​

물을 쏟기는 쉽지만 쏟은 걸 다시 담기는 매우 어려운 것처럼.

​

즉, N = pq(p,q는 소수)일 때, p와 q를 알면 N의 값을 구하기는 굉장히 쉽지만 N값만 가지고 p와 q를 찾는 것은 굉장히 어렵다.

​

대칭키에서는 평문은 P(Plaintext), 암호문은 C(Ciphertext)로 표기하였으나 공개키에서는 평문을 M(Message)라고 한다.

​

공개키를 사용할 때에는 개인키(private key)와 공개키(public key)가 한 쌍을 이루어야 한다.

​

<개인키로 암호화 - 공개키로 복호화>를 할 수도 있고,

​

<공개키로 암호화 - 개인키로 복호화>를 할 수도 있다. 이 방식을 보통 서명(Sign)이라 한다.

​

배낭암호

배낭암호는 배낭 알고리즘(knapsack algorithm)에서의 배낭과 의미가 동일하다.

​

배낭의 제한 무게에 물건들의 무게의 합이 딱 맞아떨어지게 넣는 방식이다.

​

말보다 예시로 이해하는 게 더 쉽다.

​

배낭에 들어가는 물건의 무게가 아래의 표와 같을 때

배낭의 제한 무게가 172라고 하면 우리는 a0부터 a7까지 물건의 무게의 합이 정확히 172일 때를 찾아야 한다.

​

가장 큰 수부터 넣어 계산을 해보면 172 = 85 + 13 + 47 + 27 이 나온다.

​

즉, a0,a1,a4,a5 자리가 포함된다.

​

이 때 배낭을 (a0,a1,a2, ..., a7) = (1,1,0,0,1,1,0,0) = (11001100) 와 같이 이진수로 표현을 한다.

​

배낭암호에서는 이러한 나열을 '일반배낭'이라 부르며, 일반 배낭이 '공개키'가 된다.

​

암호화, 복호화를 할 때 필요한 또 다른 개념 중에 '수퍼증가 배낭'이 있다.

​

간단하다. 무게가 an + an+1 < an+2 를 만족하는 물건들의 집합이다.

​

ex) 1, 3, 5(>4) , 10(>8), 30(>15), ...

​

이제 실제로 구현하는 절차를 설명한다.

​

수퍼증가 배낭을 일반 배낭으로 변환할 때 공개키와 암호키가 만들어진다.

​

변환할 때는 두 가지 요소가 필요하다.

​

1. 수퍼배낭의 물건에 곱할 수 m

2. mod 연산의 피연산자가 될 n. 여기서 n은 수퍼증가 배낭의 모든 물건의 무게 합 보다 커야 한다.

​

m, n과 수퍼증가 배낭이 개인키가 된다.

​

공개키는 위 문단에도 언급했듯이 일반 배낭이다.

​

실제 예시를 들어본다. 아래와 같은 수퍼 배낭이 존재한다.

m과 n을 각각 41, 491로 정한다.

​

2m = 2*41 = 82mod491

3m = 3*41 = 123mod491

7m = 7*41 = 287mod491

14m = 14*41 = 83mod491

30m = 30*41 = 248mod491

57m = 57*41 = 373mod491

120m = 120*41 = 10mod491

251m = 251*41 = 471mod491

​

개인키 : 수퍼배낭(2,3,7,14,30,57,120,251), 41(m), 491(n)

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

​

앨리스가 밥에게 평문 M인 150을 보내려고 할 때 배낭 암호를 적용시켜보자.

​

먼저, 150을 이진수인 10010110 으로 바꾼다.

​

이 값을 공개키(82,123,287,83,248,373,10,471)의 자리수에 대응시켜 1에 해당하는 물건값만 더한다.

​

그러면 82, 83, 373, 10이 선택되며, 82 + 83 + 373 + 10 = 548이 되며, 548이 암호문 C가 된다.

​

밥은 개인키인 수퍼배낭(2,3,7,14,30,57,120,251)과 m, n을 이용하여 복호화를 진행한다.

​

먼저, C인 548을 C*m^-1 mod n 을 통해 개인키로 변환시킨다.

​

계산하면 548*41^-1 mod491 = 548*12 mod491 = 193 이 된다.

* 41x = 1mod491, x=12 => 41^-1mod491 = 12

​

193은 수퍼배낭의 물건 무게들의 합이다. 계산해보면 193 = 120 + 57 + 14 + 2 가 된다.

​

선택된 무게에 해당되는 물건을 1, 아닌 물건을 0으로 변환해 이진법으로 나타내면 10010110이 된다.

​

이 값을 십진법으로 변환하면 원래의 평문 M인 150이 나오게 된다.