1. 디피-헬만 키 교환 알고리즘
이산 로그 기반 공개키 분배 메커니즘이며, 암호화 메커니즘이 아니다.
y = g^x mod p일때 g와 x와 p를 안다면 y는 구하기 쉽지만, g와 y와 p를 알땐 x를 구하기는 어렵다는 방식에 착안
두 명의 사용자가 메시지 암호화에 사용될 비밀키를 안전하게 교환하는 것을 목표로 함.
두 사람 A, B가 암호화되지 않은 통신망을 통해서 공통의 비밀키를 공유할 수 있도록 동일한 키를 가지게 해주는 알고리즘이다.
취약점
- B가 아닌 사람이 B인척하면서 키를 교환할 수 있다. 즉, B를 검증할 방법이 부족하다.
- 대칭키를 취득한 제 3자가 B의 행세를 할 수도 있다.
- 재전송 공격에 취약하여 암호화된 정보를 스니핑해 재전송할 수 있다.
- 정보의 무결성이 보장되지 않는다.
따라서, 디피헬만 알고리즘은 단독으로 사용하지 않고 인증, 무결성, 부인방지와 같은 B를 검증할 수 있는 추가적인 방법들을 활용하여 안전성을 확보한다.
2. RSA 알고리즘
- 공개키 암호 알고리즘 중의 하나이며, 사실상 세계적 표준이다.
- 인수분해 문제 해결의 높은 난이도를 이용한 가장 대표적인 공개키 암호 알고리즘으로 암호화뿐만 아니라 전자서명의 용도로 사용된다.
- 공개키와 개인키로 구성된다.
- 공개키는 암호화할 때 사용하고, 개인키는 복호화할 때 사용한다.
원리
1) 개인키와 공개키 만들기
- 공개키는 n, e라는 두 정수로 이루어져 있고 개인키는 n, d라는 두 정수로 이루어져 있다.
n 구하기
- 임의의 두 소수 p와 q를 정하고 n = p * q를 해주면 n을 구할 수 있다.
e 구하기
- Φ(n) = (p - 1) * (q - 1)식을 이용하여 Φ(n)을 구한다.
- e는 1 < e < Φ(n)로써 1과 Φ(n) 사이에 있고 Φ(n)와 서로소인 e를 정해주면 된다.
- e는 공개키에 이용된다.
d 구하기
- (e * d) mod Φ(n) = 1
- e*d를 Φ(n)으로 나누었을 때 나머지가 1인 d를 구하면 된다. 이때 d는 개인키에 사용될 숫자이다.
2) 암호화하기
원래 정보를 M, 암호화된 정보를 C라고 했을 때,
C = M^e mod n 식을 이용하여 M을 C로 암호화한다.
3) 복호화하기
페르마의 소정리에 의해 M = C^e mod n 식을 이용하여 복호화한다.
이때 n과 d값을 알아야 하는데 이 값을 아는 사람은 개인키를 가진 사람 뿐이다.
