공개키알고리즘

공개키알고리즘 Part.1

카피캣 2007. 12. 20. 15:11

대칭키 알고리즘과는 달리 서로 다른 두 개의 열쇠를 사용하는 새로운 자물쇠가 있다고 가정해 보겠습니다. 이 자물쇠는 두 개의 열쇠 중 하나로 잠그면, 반드시 잠근 것과는 다른 열쇠로만 열 수 있습니다. 즉 첫 번째 열쇠로 잠근 것은 두 번째 열쇠로만 열 수 있고, 두 번째 열쇠로 잠근 것은 첫 번째 열쇠로만 열 수 있습니다.

어떤 사람이 자신의 집 현관에 이 자물쇠가 설치된 편지함과 첫 번째 열쇠를 함께 놓아두고 두 번째 열쇠는 편지함 주인인 자신이 가진다고 가정해보겠습니다. 누구라도 편지함 주인에게 비밀편지를 보내려고 하면 편지함에 편지를 넣고 첫 번째 열쇠로 잠그기만 하면 됩니다. 첫 번째 열쇠로 잠갔기 때문에 두 번째 열쇠를 가진 편지함 주인 이외에 어떤 사람도 편지함을 열지 못합니다. 따라서 누구라도 편지함 주인에게 비밀편지를 보낼 수 있는 것입니다. 이와는 반대로 편지함 주인이 편지를 써서 편지함에 넣고 두 번째 열쇠로 잠근다면 외부인 중 누구라도 첫 번째 열쇠로 열어볼 수 있고 편지함 주인이 편지를 쓴 것이라는 확신을 가질 수 있을 것입니다. 첫 번째 열쇠로 열린다는 것은 두 번째 열쇠로 잠갔다는 것을 의미하며, 이 열쇠는 주인만이 가지고 있기 때문입니다.

공개키 알고리즘은 이와 같은 특성을 가지는 두 개의 키가 존재하는 암호 알고리즘입니다. 첫 번째 열쇠와 같이 외부인 누구에게나 공개되어 있는 것을 공개키라고 하고, 두 번째 열쇠와 같이 외부에는 알리지 않고 자신만 보관하고 있어야 하는 것을 개인키라고 합니다. 대칭키 알고리즘과는 달리 비밀을 공유하려는 사람들 간에 공유하게 되는 동일한 키가 없으며, 외부에 공개되는 키가 존재하는 특징 때문에 보통 공개키 알고리즘이라고 합니다.

공개키 암호 방식

공개키 알고리즘은 문서를 공개키로 암호화하느냐, 개인키로 암호화하느냐에 따라서 활용되는 분야가 확연히 차이가 납니다. 공개키로 암호화한 경우에는 개인키 소유자만이 복호화할 수 있기 때문에 암호로서 효용성을 가집니다. 반면에 개인키로 암호화하는 경우에는 누구나 복호화할 수 있기 때문에 암호로서의 활용은 불가능합니다. 대신 개인키 소유자만이 문서를 암호화할 수 있기 때문에 암호문 작성자를 알리기 위한 용도로 사용되며, 이를 암호화라는 말 대신 전자서명이라고 합니다. 우리나라 공인인증체계의 근간을 이루는 전자서명법은 공개키 알고리즘의 두 용도 중에서 전자서명만 규정하고 있으며, 문서 암호화에 대해서는 규정하지 않고 있습니다. 따라서 전자서명법에서는 개인키를 전자서명생성정보라고 정의하고 공개키를 전자서명검증정보라고 정의하고 있습니다.

공개키 알고리즘은 대칭키 알고리즘과는 달리 공개키와 개인키가 상호작용을 하여 암호화와 복호화를 수행하는 만큼 둘 사이에 상당히 복잡한 수학적 관계가 있으리라는 것은 쉽게 눈치챌 수 있을 것입니다. 공개키 알고리즘이 실제 어떤 수학적인 원리를 이용하는지 살펴보도록 하겠습니다.

공개키 알고리즘 중에서 가장 잘 알려져 있는 RSA 알고리즘은 서로 다른 두 소수의 곱의 형태로 표시되는 큰 수를 원래의 두 소수로 소인수분해하는 것이 어렵다는 문제에 기반하여 설계되었습니다. 서로 다른 두 소수 p 와 q 를 선택하여 두 소수를 곱한 것을 n , 두 소수보다 1씩 작은 것을 곱한 수를 Ф(n) 이라 하고 이를 식으로 표현하면 n = p∙q,  Ф(n) = (p-1)(q-1) 이 됩니다. 다음으로 1 보다 크고 Ф(n) 보다 작은 정수 중에서 Ф(n) 과 서로소가 되는 e 를 선택합니다. 마지막으로 e 와 d 를 곱하여 Ф(n) 으로 나눈 나머지가 1 이 되는 d 를 구합니다. 이를 만족하는 n 과 e 를 공개키라 하고, d 를 개인키라고 합니다.

그렇다면 두 소수 p 와 q 를 모를 경우, 공개키 n 과 e 로부터 개인키 d 를 얼마나 빨리 구해낼 수 있을까요? n 이 두 소수 p 와 q 의 곱으로 구성되어 있다는 것을 알고 있으므로, n 을 소인수분해하여 p 와 q 를 구할 수만 있다면 d 를 계산할 수 있을 것입니다. 하지만 소수 p , q 가 충분히 크다면 두 소수의 곱으로부터 원래의 두 소수를 찾는 것은 매우 어려운 일이라고 합니다. 300자리 이상의 정수를 소인수분해하는 것은 2027년 이후에나 가능하다는 연구결과가 있습니다. 또한 소인수분해를 하지 않고 공개키 n 과 e 로부터 개인키 d 를 구하는 방법은 아직 알려진 바가 없습니다.

방금 구한 공개키와 개인키로 전자서명과 전자서명검증을 어떻게 수행하는지 살펴보도록 하겠습니다. 전자서명할 문서를 m 이라고 하고 전자서명을 수행한 결과값을 c 라고 하면 다음과 같은 식으로 전자서명 과정과 전자서명검증 과정을 표현할 수 있습니다.

   전자서명과정      :  c = md mod n

   전자서명검증과정 :  m = ce mod n

증명

e 와 d 를 곱하여 Ф(n) 으로 나눈 나머지가 1이 되므로 다음 식이 성립합니다.
    e ∙ d  =  k Ф(n) + 1        ……(1)
오일러의 totient 함수에 의하면 다음 식이 성립합니다.
    mФ(n)  mod n  =  1        ……(2)

ce  mod n ≡ (md)e  mod n
               ≡ med  mod n                 ← 계산식(1)을 대입하면
               ≡ mkФ(n)+1 mod n
               ≡ (mФ(n))k∙m  mod n       ← 계산식(2)를 대입하면
               ≡ 1k∙m  mod n
               ≡ m

현재까지 알려진 전자서명을 위한 공개키 알고리즘은 방금 설명한 소인수분해의 어려움에 기반을 둔 RSA 알고리즘 외에도 유한체의 이산대수 문제의 어려움에 기반을 둔 DSA 알고리즘과 KCDSA 알고리즘, 타원곡선 상의 이산대수 문제의 어려움에 기반을 둔 ECDSA 알고리즘 등이 있습니다. 이 중에서 KCDSA 알고리즘은 국산 알고리즘입니다.

우리나라 공인인증체계에서는 RSA 알고리즘을 주로 사용하며, 제한적인 환경에서 ECDSA와 KCDSA를 사용할 수 있습니다.

개별 공개키 알고리즘 부연설명

  1. RSA는 1977년 R. Rivest, A. Shamir, L. Adleman 3명의 수학자에 의해 개발된 알고리즘으로 RSA는 이들의 머릿글자를 따서 지어졌으며, RSA Security사가 소유권을 가지고 있습니다.
  2. DSA(Digital Signature Algorithm)는 미국 국립표준기술연구소(NIST)에서 개발되었으며, 2000년 1월 미국 전자서명 표준(FIPS 186-2)으로 승인되었습니다.
  3. KCDSA(Korean Certificate-based Digital Signature Algorithm)는 한국통신정보보호학회의 주관 하에 국내 암호학자들이 주축이 되어 1996년 11월에 개발되었으며, 1998년 10월에 국내 표준(TTA.KO-12.0001)으로 제정되었습니다.
  4. ECDSA(Elliptic Curve Digital Signature Algorithm)는 DSA 전자서명을 타원곡선을 이용한 전자서명 알고리즘으로 변형한 것으로 2000년 1월 미국 전자서명 표준(FIPS 186-2)으로 승인되었습니다.