가장 대표적인 공개키 암호인 RSA는, 최초 개발자인 Rivest, Shamir, Adleman의 첫글자에서 따온 것이다. RSA는 75자리 이상의 큰 소수인 p, q를 이용하며, 이 체계의 안전성은 이 두 수의 곱인 n = pq가 얼마나 소인수분해하기가 어렵냐에 의해서 결정된다.
암호를 받을 사람은, 다음의 단계를 준비한다.
1. 큰 소수 p, q를 선택하여 n = pq를 계산한다.
2. e * d ≡ 1 (mod Φ(n))인 e와 d를 선택한다. 여기서 e가 gcd(e, n) = 1인지 아닌지는 유클리드 알고리즘으로 신속하게 판단할 수 있다. 그리고 d를 결정하는 문제 또한 유클리드 알고리즘으로 계산할 수 있다.
3. (n, e)를 공개한다. 이것이 공개키가 된다.
4. p, q, d를 절대 비밀로 유지한다. p와 q는 폐기하는 것이 좋으며, d는 개인키가 된다.
암호를 보낼 사람은 다음의 과정을 거친다.
1. 메세지 m를 숫자의 형태로 바꾼다.
2. 받는 사람의 공개키(n, e)를 가져온다.
3. c ≡ m^e (mod n)을 계산하여 Encryption 한다.
암호를 받은 사람은, 다음의 과정을 거친다.
1. 개인키 d를 사용하여, c^d ≡ m (mod n)을 계산하여 Decryption 한다.
Decryption 결과가 원래의 메세지 m과 동일하다는 것을 어떻게 보장할 수 있을까? 이것은, m^(e * d) ≡ m(mod n)을 증명하는 문제인데, 증명은 다음과 같다.
e * d ≡ 1 (mod Φ(pq))이므로, e * d = 1 + kΦ(pq),
m^(1 + kΦ(n)) ≡ m * (m^Φ(p)Φ(q))^k ≡ m * 1^k(q - 1) ≡ m (mod p),
여기서 m과 p가 서로소가 아니라면 p는 m을 나눌 수 있으며, m ≡ 0 (mod p)이며, e^(e * d) ≡ 0 (mod p)이다. 그러므로 어느 경우나 m은 동일하다.
그리고 q에 대해서도 마찬가지로,
m^(1 + kΦ(n)) ≡ m * (m^Φ(p)Φ(q))^k ≡ m * 1^k(p - 1) ≡ m (mod q), 위와 동일하다.
또, m^(e * d) ≡ m (mod n)이다.
∴ m^(e * d) ≡ m (mod p), p ｜m^(e * d) - m,
m^(e * d) ≡ m (mod q), q｜ m^(e * d) - m,
따라서 p, q는 m^(e * d) - m의 약수이다. 또, p, q는 서로소이므로 pq ｜ m^(e * d) - m,
∴ m^(e * d) ≡ m (mod n = pq)
이 과정에서 중요한 것은, n, e만으로는 개인키 d를 알기가 쉽지 않다는 것이다. p와 q를 알고 있다면, 개인키 d를 쉽게 알 수 있다. n을 알고 있고, Φ(n)을 알고 있다고 하자. 그렇다면, p, q를 알아내는 것은 간단한 2차 방정식을 세워보면 쉽게 알 수 있다.
n = pq,
p + q = pq - (p - 1)(q - 1) + 1 = n - Φ(n) + 1
따라서, X^2 - (n - Φ(n) + 1)X + pq = (X - p)(X - q), 구하고자하는 p, q는 근의 공식을 써서 구할 수 있을텐데, 문제는 n은 알려져 있어도 Φ(n)을 계산하는게 쉽지 않다는데 있다. 물론, n이 작다면 일일이 소인수분해를 해서 답을 구할 수 있겠지만, RSA에서 사용되는 n은 엄청난 크기의 수이다. 여기서 p, q를 모르는 상태에서 n을 소인수분해하면서 p, q를 찾는 것은, 엄청난 시간을 소모한다. RSA의 안전성은 이 Φ(n)의 값을 구하는 것이 쉽지 않다는데 달려있다.
Reference
최병문, 이영환(2007), 암호의 세계, 경문사
암호를 받을 사람은, 다음의 단계를 준비한다.
1. 큰 소수 p, q를 선택하여 n = pq를 계산한다.
2. e * d ≡ 1 (mod Φ(n))인 e와 d를 선택한다. 여기서 e가 gcd(e, n) = 1인지 아닌지는 유클리드 알고리즘으로 신속하게 판단할 수 있다. 그리고 d를 결정하는 문제 또한 유클리드 알고리즘으로 계산할 수 있다.
3. (n, e)를 공개한다. 이것이 공개키가 된다.
4. p, q, d를 절대 비밀로 유지한다. p와 q는 폐기하는 것이 좋으며, d는 개인키가 된다.
암호를 보낼 사람은 다음의 과정을 거친다.
1. 메세지 m를 숫자의 형태로 바꾼다.
2. 받는 사람의 공개키(n, e)를 가져온다.
3. c ≡ m^e (mod n)을 계산하여 Encryption 한다.
암호를 받은 사람은, 다음의 과정을 거친다.
1. 개인키 d를 사용하여, c^d ≡ m (mod n)을 계산하여 Decryption 한다.
Decryption 결과가 원래의 메세지 m과 동일하다는 것을 어떻게 보장할 수 있을까? 이것은, m^(e * d) ≡ m(mod n)을 증명하는 문제인데, 증명은 다음과 같다.
e * d ≡ 1 (mod Φ(pq))이므로, e * d = 1 + kΦ(pq),
m^(1 + kΦ(n)) ≡ m * (m^Φ(p)Φ(q))^k ≡ m * 1^k(q - 1) ≡ m (mod p),
여기서 m과 p가 서로소가 아니라면 p는 m을 나눌 수 있으며, m ≡ 0 (mod p)이며, e^(e * d) ≡ 0 (mod p)이다. 그러므로 어느 경우나 m은 동일하다.
그리고 q에 대해서도 마찬가지로,
m^(1 + kΦ(n)) ≡ m * (m^Φ(p)Φ(q))^k ≡ m * 1^k(p - 1) ≡ m (mod q), 위와 동일하다.
또, m^(e * d) ≡ m (mod n)이다.
∴ m^(e * d) ≡ m (mod p), p ｜m^(e * d) - m,
m^(e * d) ≡ m (mod q), q｜ m^(e * d) - m,
따라서 p, q는 m^(e * d) - m의 약수이다. 또, p, q는 서로소이므로 pq ｜ m^(e * d) - m,
∴ m^(e * d) ≡ m (mod n = pq)
이 과정에서 중요한 것은, n, e만으로는 개인키 d를 알기가 쉽지 않다는 것이다. p와 q를 알고 있다면, 개인키 d를 쉽게 알 수 있다. n을 알고 있고, Φ(n)을 알고 있다고 하자. 그렇다면, p, q를 알아내는 것은 간단한 2차 방정식을 세워보면 쉽게 알 수 있다.
n = pq,
p + q = pq - (p - 1)(q - 1) + 1 = n - Φ(n) + 1
따라서, X^2 - (n - Φ(n) + 1)X + pq = (X - p)(X - q), 구하고자하는 p, q는 근의 공식을 써서 구할 수 있을텐데, 문제는 n은 알려져 있어도 Φ(n)을 계산하는게 쉽지 않다는데 있다. 물론, n이 작다면 일일이 소인수분해를 해서 답을 구할 수 있겠지만, RSA에서 사용되는 n은 엄청난 크기의 수이다. 여기서 p, q를 모르는 상태에서 n을 소인수분해하면서 p, q를 찾는 것은, 엄청난 시간을 소모한다. RSA의 안전성은 이 Φ(n)의 값을 구하는 것이 쉽지 않다는데 달려있다.
Reference
최병문, 이영환(2007), 암호의 세계, 경문사