[RSA - 3] RSA 암호화
RSA
3단계 중 마지막으로 RSA 암호화에 대해 간단하게 알아보자
RSA를 이해하기 위해 알아야 할 필수 지식들을 이전 두 단계를 통해 알아봤다
RSA 암호화는 공개 키 암호화 방식 중 하나이다.
1. 공개 키 암호화
- 키(key)란?
“암호화”의 목적은 해시함수와 다르게 “복호화”이다.
힘들게 암호화를 해서 수신자에게 보냈는데 송신자가가 보낸 암호문을 해독하지 못하면 어떻겠는가. 암호화라는건 아무 쓸모가 없어진다.
그래서 송신자와 수신자(앞으로는 관례적으로 Alice와 Bob 이라고 하겠다)는 암호문을 복호화 할 수 있는 키(key)가 있어야 한다.
(예를들어 과거 스파르타에서 사용한 원통에 리본을 감아 만드는 스키테일(Scytale) 암호에서 key는 원통의 굵기가 될 것이다.)
- 키(key)의 전달
이렇게 키는 암호를 복호화하기 위해 꼭 필요하다. 그렇다면 Alice와 Bob은 사용할 키를 약속하기 위해 메세지를 송수신 해야한다.
하지만 도청자 Eve 또한 그 메세지를 알아낼 수 있을 것이다.
그렇기 때문에 공개 키 암호화가 등장하기 전 Alice와 Bob은 Eve가 키를 알아내지 못하길 기도하며 암호문을 송수신 해야 했다.
이를 해결하기 위해 엘리스와 밥이 사전에 비밀키를 공유하지 않고도 안전하게 통신을 할 수 있게 공개된 공개키와 공개되지 않은 개인키를 사용하는 방식을 공개키 암호기술이라고 한다.
RSA가 무엇인지 간단하게 알아보기 위해선 공개 키 암호화에 대한 정보는 이정도로 충분 할 것 같다.
2. RSA의 key
다시 RSA로 돌아와서 RSA는 공개키 암호화 방식이다. 즉 공개키와 개인키를 암호화와 복호화에 사용한다는 것이다.
RSA암호화에서 각 키를 어떻게 결정하는지 알아보자.
- RSA 공개키
\[n = p * q\] \[\phi(n) = (p-1) * (q-1)\]이라 하자. $p$와 $q$는 서로소이다. (여기서 $\phi$는 “파이”라고 읽는다.)
그리고 $1 < e < \phi(n)$ 이면서 $\phi(n)$과 서로소인 $e$를 정한다.
RSA의 공개키는 n 과 e 이다.
- RSA 개인키
\[e*d \bmod\,\phi(n) = 1\]개인키를 만드는 과정에서 이전에 설명했던 모듈러 연산과 역원을 사용한다. 공개키 $e$와 곱하고 $\phi(n)$과 모듈러 연산하여 1이 되는 $d$가 개인키에 사용된다.
RSA의 개인키는 n 과 d 이다.
3. RSA의 암호화 복호화
암호문을 $C$ 평문을 $P$ 라고 하겠다.
\[C = P^e\mod\,n\] \[P = C^d\mod\,n\]공개키 $n$과 $e$ 로 암호화하고,
개인키 $n$과 $d$ 로 복호화한다.
4. RSA 예시
간단한 예시를 가지고 RSA 암호화와 복호화를 해보자.
비밀키 $d$는 \(23d + 72t = 1\) 배주 항등식을 확장 유클리드 알고리즘을 사용해서 해를 구하면 $d = -25$ 임을 알 수 있다. 하지만 $d$는 양수이어야 한다.
1
2
3
4
5
e*d mod n = (e mod n)*(d mod n)
d mod n = (d+n) mod n
→ 모듈러 연산의 합동성질
$d+n$을 하면 $ \mod\,n$ 값이 변하지 않기 때문에 $d+n$을 하여 비밀키 $d$를 구했다.
\[d = -25 + 72 = 47\]암호화할 평문은 “hi” 의 각 알파벳의 순서 8 과 9를 붙인 $89$ 로 하자
1
2
3
4
# Encryption
# C = 89^23 mod 91
>>> pow(89, 23, 91)
45
평문 89 는 45로 암호화되었다.
이제 복호화 해보자.
1
2
3
4
# Decryption
# P = 45^5 mod 91
>>> pow(45, 47, 91)
89
복호화가 잘 되는 모습이다.
5. RSA 보안성
공개키는 말 그대로 모두에게 공개되는 키다.
$e$와 $n$을 공개하면 $p$와 $q$도 구할 수 있고 결국엔 암호문을 복호화 할 수 있는거 아닌가? 라고 생각할 수 있지만 현실적으로 힘들다. 바로 $n$이 엄청나게 큰 수이기 때문이다.
예시에서는 $n = 91$로 매우 작게 설정하여 $7$과 $13$으로 아주 쉽게 소인수분해가 가능했지만
현실에서는 엄청난 자릿수의 $n$을 사용하기 때문에 소인수분해가 사실상 어렵다고 볼 수 있다.
또한 모듈러의 합동성질로 인해 $\phi(n)$값을 알아내어도 $d$값을 특정짓는 것도 오랜 시간이 걸릴 것이다.
큰 수 소인수분해의 어려움을 이용하기 때문에 공개 키 암호화가 “아직까지는” 안전한 암호화 방식이라고 볼 수 있다.