공개 키 암호(Public-Key Cryptography)와 RSA

공개키 암호

대칭키 암호의 문제점

대칭 암호로는 고대의 암호인 스키테일, 시저, 단일치환, 비제네르부터 근대의 에니그마, 현대 암호인 DES, AES, SEED, ARIA 등 대부분의 암호가 대칭 암호이다.

대칭키 암호에도 다음과 같은 3가지의 문제점이 존재한다.

1. 키를 서로 알고 있어야 하므로 송신자가 암호화 할 때 사용한 키를 수신자가 모르고 있다면 암호를 해독할 수 없다.
2. 그리고 여러명과 암호 통신을 한다면 서로 다른 키를 모두 보관해야한다는 문제가 있다. 예를 들어 수신자가 100명이라고 하면 송신자는 100개의 키를 보관해야 한다.
3. 모르는 사람과의 신뢰성 있는 통신이 어렵다. 수신자가 모르는 사람일 경우 누가 수신자를 사칭해도 누가 진짜 수신자일지 알 수 없기 때문에 키를 송신하기 어렵다.

키 배송 문제

인터넷으로 철수를 알게 된 영희는 철수와 안전한 통신을 위해 암호화하고 싶다면 사전에 키를 나누어 가져야 한다. 이 방법에는 3가지 방법이 있는데, 첫 번째로 사전에 키를 공유 하는 방법이 있다.
두 번째는 키 배포 센터를 두는 것이다. 세 번째로는 Diffie-Hellman 키 교환 방식을 사용한다.
각각의 특징을 살펴 보면 다음과 같다.

1. 키 사전 공유
   • 안전한 방법으로 키를 사전에 건네주는 것
   • 키 배송 문제를 해결하기 위한 가장 간단한 방법
   • 한계점으로는 인원이 많아지면 통신을 위한 키의 수가 방대해져 관리가 힘들고, 키를 공유하기 위한 안전한 방법이 필요하다.

2. 키 배포 센터에 의한 키 배송
   1. 송신자가 키 배포 센터에 키를 요청한다.
   2. 키 배포 센터에서 세션키(K)를 생성한다.
   3. KA(영희의 키), KB(철수의 키)를 DB에서 추출한다.
   4. 영희의 키로 암호화 한 세션키를 영희에게 전달한다.
   5. 철수의 키로 암호화 한 세션키를 철수에게 전달한다.
   6. 영희는 암호화 한 세션키를 자신의 키로 복호화하여 복구한다.
   7. 영희는 세션키로 메시지를 암호화를 수행하여 철수에게 전송한다.
   8. 철수는 암호화 된 세션키를 자신의 키로 복호화하여 복구한다.
   9. 영희에게 받은 암호 메시지를 세션키를 이용해 복호화한다.
      키 배포 센터를 이용하면 사전 키 공유의 한계를 보완할 수 있지만, 키 배포 센터 DB의 보안이 매우 중요하다.

3. Diffie-Hellman 키 교환
   • Diffie와 hellman이 제안한 방법
   • 송수신자는 도청자가 읽어도 괜찮은 특정 정보를 서로 교환한다.
   • 교환한 정보를 가지고 동일한 키를 각각 만들어낸다.
   • 도청자는 같은 키를 만들 수 없다.

공개 키 암호(public-key cryptography)

공개키 암호는 비대칭 암호로, 암호화 키와 복호화 키가 서로 다른 암호이다.
암호화 키와 복호화 키가 다르기 때문에 암호화 키로 암호를 복호화 할 수는 없다. 또한 키 쌍은 서로를 유추할 수 없다.

키쌍(key pair)

• 공개키 암호에서는 공개 키와 개인 키가 반드시 쌍으로 존재한다.
• 키 쌍을 이루고 있는 2개의 키는 서로 수학적으로 밀접한 관계가 있다.(공개키와 개인키를 별도로 만들어 낼 수 없다.)
• 공개 키로 암호화한 암호문은 그 공개 키와 쌍이 되는 개인 키가 아니면 복호화할 수 없다.

암호화 키

• 암호화를 위해 송신자가 사용하는 키로 공개 키(public key)

복호화 키

• 복호화를 위해 수신자가 사용하는 키로 수신자가 비밀로 간직하는 개인키(private key)

공개 키를 사용한 통신 과정

1. 철수는 자신이 사용할 공개키와 개인키 한 쌍의 키를 만든다.
2. 철수는 자신의 공개키B를 영희에게 보낸다.
3. 영희는 철수의 공개키로 메시지를 암호화 한다.
4. 영희는 암호문을 철수에게 보낸다.
5. 철수는 암호문을 자신의 개인키로 복호화 한다.

공개 키 암호의 역사

1976년 휘트필드 디피와 마틴 헬만이 공개 키 암호의 아이디어를 발표하여 공개 키가 어떠한 특성을 가져야 하는지를 제시했다. 그리고 1977년 랠프 메르클레와 마틴 헬만이 배낭(napsack) 암호를 발표하여 공개 키 암호의 구체적인 알고리즘을 발표했지만 보안 상의 문제점이 있어 사용되지는 않는다.

1978년, 공개 키 암호 알고리즘 RSA가 발표되었는데 RSA는 Ron Rivest, Adi Shamir, Leonard Adleman의 이름에서 따온 명칭이다.

공개키 암호의 장점

공개키 암호는 대칭 암호체계의 문제점을 보완할 수 있다.

1. 키를 나누어 가져야 한다. -> 공개키 암호는 암호화 키를 공개하고 복호화 키는 수신자만 가지고 있다.
2. 많은 키를 보관해야 한다 -> 개인 키 하나만 보관하면 되므로 많은 키를 보관할 필요가 없다.
3. 모르는 사람과의 신뢰성 있는 통신이 어렵다. -> 믿을 수 있는 기관에 공개키를 등록하고 송신자가 그 기관에서 수신자의 공개키를 가져와 암호화 하여 보내면 된다.

RSA

공개키 암호 알고리즘의 하나로 공개키 암호와 디지털 서명에 사용 가능하다.
1983년 RSA사는 미국에서 RSA 알고리즘에 대한 특허를 취득하였으나 현재는 특허 기간이 종료되었다.

RSA의 암호화

RSA의 암호화는 평문, 키, 암호문 모두 숫자로 이루어진다.
암호문은 평문을 나타내는 수를 E(공개키) 제곱해서 mod N(공개키)을 취한 것이다.

RSA의 복호화

암호문을 나타내는 수를 D제곱해서 mod N을 취하면 평문이 된다.
이 때 D는 개인 키이고 N은 암호화에서 사용한 N과 같은 값이다.
D는 E와 깊은 수학적 연관이 있다.

 

공개 키 암호의 약점

공개 키 암호의 약점으로는 통신 과정에서 찾을 수 있다.
철수가 영희한테 자신의 공개키를 보내는 과정에서 공격자 바둑이는 통신을 도청하고 있다가 철수가 공개키를 보낼 때 메일을 가로채 철수의 공개키를 보관하고, 영희에게 자신의 공개키를 보낸다. 그럼 영희는 바둑이의 공개키로 암호화한 암호문을 철수에게 보낸다. 그 때 바둑이는 그 메일을 가로채서 자신의 개인 키로 복호화하여 평문을 얻고, 보관해놨던 철수의 공개키로 다시 평문을 암호화하여 철수에게 위조 메일을 보내면 영희와 철수 모르게 평문을 얻을 수 있다는 문제점이 있다.

이 것을 중간자 공격 이라고 한다.

다른 공개 키 암호

RSA가 현재 가장 많이 보급되어 있는 공개 키 암호 알고리즘이지만, 그 외에도 공개 키 암호는 EIGamal 방식, Rabin 방식, 타원 곡선 암호 등의 많은 종류가 있다.