알기 쉬운 비대칭 암호 키쌍 (암호키, 복호키) 생성 과정 해설

이 글의 목적은 간단한 암호화 함수를 이용하여 감사 모듈을 개발할 필요가 있을 때, 도움이 되었으면 하는 바램에서 올립니다.

우선 암호화 이론에 대한 적을 위해 대칭키 시스템에서 사용하는 알고리듬을 소개하고 이어서 비대칭 알고리듬을 설명하도록 한다.

아래 소개하는 알고리듬은 Merkle-Hellman knapsack cryptosystems 이라 불리는 것으로 암호화 키의 생성에는 super-increasing vector 를 사용한다. 이 수퍼-증가 벡터는 키를 구성하는 숫자의 배열이 다음의 조건을 만족하도록 요구한다.

super-increasing vector, K = (k1, k2, k3, … , kn-1, kn), ki > k1 + k2 + ×××× + ki-₁ =  Ski, 1 £ i £ n

예를 들면,

암호화키 K = (151, 187, 426, 1091, 2412) 를 구했을 때, k5 (= 2412) 는 k1 부터 k4 의 전체 합친 값 (151 + 187 + 426 + 1091 = 1855 ) 보다 커야 한다는 것을 말한다. k4는 k1 부터 k3 의 합보다 크고…

이 암호키를 이용하여 아래 예시의 평문을 암호문으로 바꾸어 보면,

평문       X = (11001)

암호문    Y  =  K•X  =  kiXi  =  151 * 1 + 187 * 1 + 426 * 0 + 1091 * 0 + 2412 * 1 = 2750

따라서, 전송문으로는 2750 으로 전송하게 된다.

수신측에서는 똑같은 암호키를 이용하여 복호화 과정을 거치게 되는데, 이 과정은 아래와 같다.

X의 restore(복호) 방법

(1)    if Yn < kn, Xn = 0, Yn-1 = Yn

(2)    if Yn ³ kn, Xn = 1, Yn-1 = Yn – kn

        X = (X1,X2, ××××,Xn)

Y5 (2750)  ≥  k5 (2412) 이므로, 위 조건식 (2)를 적용하여 X5 = 1, Y4 = Y5 – k5 = 338

Y4 (338)   <  k4 (1091) 이므로, 위 조건식 (1)을 적용하면 X4 = 0, Y3 = Y4

Y3 (338)   <  k3 (426) 이므로, 위 조건식 (1)을 적용하면 X3 = 0,

Y2 (338)   ≥  k2 (187) 이므로, 위 조건식 (1)을 적용하면 X2 = 1,

Y1 (151)   ≥  k1 (151) 이므로, 위 조건식 (2)을 적용하면 X1 = 1,

결과적으로 해독문  X = (X1 X2 X3 X4 X5) = (11001) 을 구할 수 있다.

한편, 비대칭 암호화 키의 쌍을 구하는 방식은, 대칭키에서 사용한 수퍼-증가 벡터(super-increasing vector)에 추가하여, 소수 (1과 자신 이외의 수로는 나누어 떨어지지지 않는 수) 의 이용이 핵심이다. 수퍼-증가 벡터 방식을 이용하는 경우에는 공개키는 trapdoor knapsack vector라 하고, 비밀키는 simple knapsack vector라고 구분하여 부르고 있다.

그런데, 위의 대칭키 방식의 설명에서 사용한 벡터 방식을 동일하게 사용하여 설명하는 것이 좋을 듯 하지만, 글로 설명하기에 복잡하여 비대칭키 원리를 이해하는데 부족하지 않은 간단한 사례를 들어 설명하기로 한다.

결과적으로 아래의 서로 다른 키쌍이 있을 수 있는데, 이들이 생성되는 과정을 살명하는 것으로 원리를 설명하도록 한다.

공개키 = (n, e) = (33, 3)

비밀키 = (d, p, q) = (7, 3, 11)

공개키의 n, 비밀키의 p와 q 의 관계는 n = p * q (위의 키 구성에서 보면 33 = 3 * 11) 이고, p 와 q는 소수이다. (가능하면 클수록 좋다)

z = (p-1)(q-1) = 20을 구하고, z과 서로소(최대공약수가 1인경우 이들의 관계를 서로 소라고 함)의 관계인 수 (= d)를 구한다. 여기서는 7 인데, 이것은 20과 7이 서로소 관계이다.

마지막으로 e 만 구하면 모든 키의 구성값을 구하는 것이다. e 는 d 와 곱한 값을 z 로 나누었을 때, 나머지가 1인 수로 결정한다.

이제부터 적용 사례를 설명하기로 한다.

원문 P = (8, 1, 16, 16, 25) 가 있을 때, 암호문 C 는 P**e (mod 33) = (17,1,4,4,16) 가 된다.

여기에서 33은 n 이다.

세부 과정을 살펴보면, 아래 방식으로 산출된다.

17 = 8 * 8 * 8 (mod 33) = 512 를 33 으로 나눈 나머지

1 = 1 * 1 * 1 (mod 33) = 1을 33으로 나눈 나머지

4 = 16 * 16 * 16 (mod 33) = 4096을 33으로 나눈 나머지

4 = 16 * 16 * 16 (mod 33) = 4096을 33으로 나눈 나머지

16 = 25 * 25 * 25 (mod 33) = 15625 를 33으로 나눈 나머지

다시, 역으로 비밀키를 갖고 복호화하는 과정을 살펴보면, 복호문 P = C**d (mod  33) = (8, 1, 16, 16, 25) 과정을 밟는다. 여기에서 33은 p * q 이고, 수신한 암호문을 각각 d 승씩을 한 결과 ( = C**d)  는 (410338673, 1, 16384, 16384, 268435456) 이다. 각 요소를 33으로 나눈 후 나머지를 취하면 원래의 평서문 P = (8, 1, 16, 16, 25)가 얻어진다.

신인철

아이티거버넌스인터내셔널© IT Governance International