공개키 암호 (암호 시스템, 응용, 종류, 조건, 분석, RSA)

목차

1. 공개키 암호

1-1 공개키 암호 시스템

1-2 공개키 암호 시스템의 응용

1-3 공개키 암호 시스템의 종류

1-4 공개키 암호를 위한 요구 사항

1-5 공개키 암호 분석

1-6 RSA

 

 

1. 공개키 암호

1-1 공개키 암호 시스템

공개키 알고리즘은 두 개의 서로 다른 키쌍을 사용한다.

 

공개키: 모든 사람이 접근 가능한 키 (공개)

개인키: 각 사용자 자신만이 소유한 키 (비밀)

공개키 암호 통신을 설명할 때 누구의 키인지 주어 설명은 매우 중요하다.

 

● 특징

- 암호 알고리즘과 암호키를 알아도 복호키 계산은 불가능하다.

- 두 개의 키중 하나는 암호화에, 다른 하나는 복호화에 사용한다.

- 대칭키에 비해 속도가 상대적으로 느리다.

 

● 공개키 암호를 이용한 통신 순서 (A -> B 통신)

1. 공개키와 개인키를 생성한다.

2. 공개키는 공개하고 개인키는 개인이 소유한다.

3. A는 B의 공개키로 메시지를 암호화한다.

4. B는 자신의 개인키로 메시지를 복호화한다.

   (B의 개인키를 모르는 제 3자는 메시지 복호화가 불가능하다.)

 

ex)

조건

: 암호알고리즘 : mod 7에서 곱셈

: 공개키 : 3,  개인키 : 5 

: 원문 : 4

 

위와 같은 조건의 경우 암호화와 복호화는 다음과 같다.

- 암호화 4 * (3 mod 7) = 5 (암호문)

- 복호화 5 * (5 mod 7) = 4 (원문)

- mod 7에서 3, 5는 서로 역원 관계이다. (mod에서는 정수 내에 곱셈에 대한 역원이 존재한다.)

 

1-2 공개키 암호 시스템의 응용

● 공개키 암호의 기밀성

A -> B 통신인 경우, A가 B의 공개키로 암호화한 암호문은 B의 개인키로만 복호화가 가능하므로 공격자가 암호문과 B의 공개키를 획득하더라도 원문을 추출할 수 없다.

 

● 공개키를 이용한 인증

A -> B 통신인 경우, A가 A의 개인키로 암호화한 암호문은 A의 공개키로만 복호화가 가능하므로 공격자가 암호문(서명문)과 A의 공개키를 획득하더라도 원문은 추출할 수 있으나 위조는 불가능하다. (부인 방지 = 근원지 증명 = 전자서명)

 

● 공개키를 이용한 기밀 통신과 서명

A -> B 통신인 경우, A의 서명문을 B의 공개키로 암호화하여 서명문조차 기밀통신이 가능하다.

그러나 이는 암호화 / 복호화 연산의 증가로 속도가 느려 사용하지 않는다.

 

1-3 공개키 암호 시스템의 종류

● 공개키 암호 시스템의 사용

- 암호화 / 복호화 (수신자의 공개키로 메시지를 암호화한다.)

- 디지털 서명 (송신자의 개인키로 메시지에 서명을 한다.)

- 키 교환 (세션키를 교환하기 위해 사용한다.)

 

알고리즘: RSA (소인수분해), Diffie-Hellman(이산대수)

 

1-4 공개키 암호를 위한 요구 사항

● 공개키 알고리즘의 조건 (Diffie-Hellman)

용어 정의는 다음과 같다.

A = 송신자

B = 수신자

K = 키

U = 공개키

R = 개인키

E() = 암호화 알고리즘

D() = 복호화 알고리즘

 

- 키쌍(공개키 KU, 개인키 KR)의 생성이 쉽다.

- 다음 식과 같은 암호문의 생성이 쉽다.

       C = EKUb(M)

- 다음 식과 같은 암호문의 복호화가 쉽다.

       M = DKRb(C) = DKRb[EKUb(M)]

- 공개키 KUb로부터 개인키 KRb를 결정하는 것은 어렵다.

- 공개키 KUb와 암호문C로부터 메시지 M의 복구가 어렵다.

- 암호와 복호 기능이 다음과 같이 적용 가능하다.

       M = EKUb[DKRb(M)]

 

1-5 공개키 암호 분석

● 공격 유형

- 전사적 공격

키의 크기를 크게 함으로써 방지한다. (상대적으로 속도가 느려진다.)

 

- 공개키로부터 개인키를 계산하는 공격

수학적으로 계산이 불가능함을 증명하지 못했다.

 

- 가능한 메시지 공격 : 모든 가능한 메시지를 공개키로 암호화하여 암호문과 비교한다.

메시지에 임의의 비트를 추가함으로써 방지한다.

 

1-6 RSA

● RSA의 개발

RSA는 1977년에 개발되어 1978년에 공포되었다. (Rivest, Shamir, Adleman)

 

● 알고리즘

평문을 블록으로 나누어 암호화한다.

암호화 식: C = M^e mod n

복호화 식: M = C^d mod n

 

공개키 : KU = {e, n}

개인키 : KR = {d, n}