공개키 암호
Public Key Encryption
공개키 암호의 정의
공개키는 공개하고, 개인키(비밀키)는 비밀로 하여 사용하는 방식. 비대칭키 방식이라고도 한다. 이때 생성되는 공개키와 개인키는 수학적인 관련성을 갖는다.
공개키 암호는 메시지를 암호화 시에도 사용하고, 전자서명과 같은 인증서에도 사용이 될 수 있다.
공개키 암호의 장점/ 단점
장점
- 공개키는 사용자가 n명일 때 2n개의 키만 필요로 한다. 대칭키가 n명일 때 n(n-1)/2인 것을 비교하면, 큰 차이가 있다.
- 키 관리가 쉽다. 키가 공개 되어도 상관없다.
- 메시지 암호화 이외에도 전자서명에도 사용 가능하다.
단점
- 대칭키에 비해서 크기가 상대적으로 커서 암호화/복호화 시간이 많이 걸린다.
메시지 암호화의 공개키
송신자와 수신자가 있을 때,
송신자(메시지를 보내는 사람)는 수신자의 공개키로 자신이 보낼 메시지를 암호화한다.
그 메시지를 전달받은 수신자는 자신의 개인키(수신자의 개인키)로 메시지를 복호화하여서 메시지를 확인할 수 있다.
전자서명의 공개키
우선, 공개키는 메시지에 대해서 기밀성을 제공해 주지 못하지만, 무결성, 인증, 부인방지를 제공해준다.
송신자와 수신자가 있을 때, 송신자는 자신의 메시지를 자신의 개인키로 서명을 한다. 수신자는 그 메시지를 송신자의 공개키를 이용하여서 검증한다. 이 메시지는 송신자뿐만이 아니라 그 이외의 사람들도 공개키로 검증할 수 있다.
키 교환에서 공개키
양측의 세션키(대칭키)를 교환하기 위해 사용된다.
메시지 암호화/복호화와 같이 수신자의 공개키로 암호화하고 수신자는 자신의 개인키로 복호화한다.
공개키 암호화 비교
| 알고리즘 | 암호화/복호화 | 전자서명 | 키교환 | 방식 |
| RSA | o | o | o | 소인수 분해의 어려움. |
| Rabin | o | o | o | 소인수 분해의 어려움. 합성수 모듈어에 대해 제곱근을 찾기가 어렵다. |
| ElGamal | o | o | o | 이산대수의 어려움. 암호문의 길이가 두배가 된다. |
| ECC | o | o | o | 이산대수의 여려움. 타원 곡선을 이용한 암호. |
| DSS | x | o | x | 이산대수의 여려움. |
| Diffie-Hellman | x | x | o | 이산대수의 여려움 |
| 배낭 암호 | o | x | x | 배상문제의 어려움. |
RSA
- RSA는 Rin Rivest, Adi Shamir, Len Adleman에 의해서 인수분해의 어려움을 바탕으로 만들어진 공개키 암호 알고리즘이다.
- RSA는 공개키 암호화, 전자서명에서 사용이 가능하다.
- 키 생성 순서
1. N을 구한다.
큰 소수 p, q를 곱하여 N을 구한다. N=pxq (N은 공개돼도 되지만, p와 q는 공개되면 안 된다.)
2. 𝜙(n)을 구한다.
𝜙(n)은 (p-1)과 (q-1)의 곱이다. 𝜙(n)= (p-1) x (q-1)
3. E를 구한다.
E의 범위 : 1 < E < 𝜙(n)
E는 𝜙(n)와 최대공약수는 1이어야 한다. gcd(E, 𝜙(n))=1
이때 생성된 E와 N은 공개키가 된다.
4. D를 구한다.
D의 범위 : 1 < D < 𝜙(n)
E와 D는 역수의 관계에 있어야 한다. E X D mod 𝜙(n) = 1
이때 생성된 E와 D가 개인키가 된다.
- 암호화
공개키는 { E, N }이고 M이 평문 메시지일 때, 암호문 C를 만들내는 식은 다음과 같다.
C=M^E mod N
- 복호화
개인키가 { D, N }이고 C가 암호문일 때 평문 M으로 복호화 과정은 다음과 같다.
M=C^D mod N
- 예시
p, q로 각각 7, 11로 설정하면
1. N=7x11=77
2. 𝜙(n)=6x10=60
3. gcd(E, 60)=1 (1 < E < 𝜙(n))을 만족하는 E는 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59이 있다. 그중에서 13을 고르자
4. E X D mod 𝜙(n) = 1 (1 < D < 𝜙(n))을 만족하는 D를 구하자
13 x D mod 60 = 1
D는 37이다.
M이 5일 때, 암호화하면 5^13 mod77=26
복호화하면, 26^37 mod 77=5이다.
[참조]
히로시 유키, 알기쉬운 정보보호개론: 흥미로운 암호 기술의 세계, 인피니티북스
