뭐, 다들 아시겠지만,
암호가 뭔가요?
네, 맞습니다. 암호는 누군가에게 정보를 보낼 때 보내는 사람과 받는 사람만 해독할 수 있게 바꾸어 보내서 제 3자가 보게 되더라도 해독할 수 없게 만드는 장치입니다. 예시를 들자면, 몰래 책상서랍에 넣어둔 고백편지가 친구에게 들키더라도 전교생 앞에서 낭독될 일이 없게 해주는 장치이죠.
한 때 암호는 전시상황에 ‘지원군을 요청한다!’ 같은 글귀를 안전하게 전달하는 데에나 사용되었지만, 인터넷이 상용화된 지금은 암호를 일상적으로 사용하고 있습니다. 이번 기사에서는 오래 전 개발되었지만 현재까지 쓰일 정도로 강력한, RSA암호에 대해서 소개하려고 합니다!
암호화와 복호화
밥에게 한 눈에 반한 앨리스(Alice)는 밥(Bob)에게 연애편지를 보내기로 결심했습니다. 절친 클레어(Claire)에게 들키지 않기 위해서 앨리스는 연애편지를 암호문으로 바꿉니다. 이 과정을 ‘암호화’ 라고 합니다. 그리고 암호화하기 전의 연애편지를 ‘평문’ 이라고 합니다. 이제 연애편지를 들켜도 클레어가 알아볼 수 없겠군요!
앨리스의 연애편지를 받은 밥은 앨리스의 암호문을 원상태로 되돌려 놓아야 합니다. 이 과정을 ‘복호화’ 라고 합니다. 이렇게 한 커플이 탄생하는 군요…
Key?
로마의 장군 카이사르는 친구들에게 비밀 편지를 보낼 때 알파벳을 3자리씩 평행이동 시켜서 다른 사람이 보지 못하게 했습니다. 바로 이렇게요.
여기서 ‘3’이라는 숫자가 카이사르 암호의 ‘Key’입니다.
카이사르가 만든 암호문은 그가 암호화를 한 방법과, 그 키를 알아야만 복호화를 할 수 있습니다. 현대에 와서는 암호를 만드는 방법이 대부분 알려져 있어서 키를 숨기는 것이 중요해 졌습니다.
하지만, 카이사르 암호를 사용한다면 키를 숨기는 것도 큰 의미가 없습니다. 카이사르 암호의 키는 몇 가지가 가능할까요? 여러분도 한 번 세보세요.
키가 27이면 어떻게 될까요? 알파벳이 총 26가지가 있으므로 이것의 암호문은 평문과 똑같아 지겠군요! 따라서 카이사르 암호의 키는 26가지 밖에 되지 않습니다. 시간이 오래 걸리긴 하겠지만, 1부터 26까지 26가지의 키를 시도하면 쉽게 찾을 수 있을 것입니다. 카이사르 암호는 그의 암호화 방법이 잘 알려져 있지 않던 중세 시절에나 쓸모가 있었던 것입니다.
대칭키 암호와 비대칭키 암호
여러분들이 읽은 앨리스와 밥의 러브 스토리에는 한 가지 이상한 점이 있습니다. 밥은 어떻게 앨리스가 사용한 암호의 키를 알고 편지를 복호화 할 수 있었을까요? 앨리스가 키를 알려주기 전까지는 밥이 앨리스의 키를 알 리가 없잖아요. 따라서 앨리스는 편지를 보내기 전에 밥에게 자신의 키를 알려주어야 합니다. 이것을 ‘키 교환’이라고 합니다.
그러나 앨리스와 밥 사이의 키 교환은 현실적으로 불가능합니다. 앨리스는 밥에게 키를 알려주면서 사실상 고백을 하는 꼴이 되기 때문이죠. 그럼 대체 연애편지가 무슨 의미가 있단 말입니까!
고민하는 앨리스를 위해서 미국의 디피(Whitfield Diffie)와 헬만(Martin Hellman)은 암호화 키와 복호화 키를 다르게 하는 ‘비대칭키 암호’라는 것을 생각해냅니다.
앞서 살펴본 카이사르 암호는 암호화를 할 때 사용하는 키 값과 복호화를 할 때 사용하는 키 값이 3으로 같았습니다. 이와 같이 암호화 키와 복호화 키가 같은 암호를 ‘대칭키 암호’라고 합니다. 반대로 비대칭키 암호는 암호화 키와 복호화 키가 다른 암호이죠.
조금만 더 생각해봅시다. 어떻게 암호화 키와 복호화 키가 다르면 키 교환 없이 통신이 가능한 걸까요? 디피와 헬만은 암호화 키는 공개하고, 복호화 키는 공개하지 않는다는 아이디어를 생각해냈습니다. 이 때 공개되는 암호화 키는 ‘공개키’, 비밀로 유지되는 복호화 키는 ‘개인키’라고 부르기도 합니다.
앨리스가 밥에게 연애편지를 보낼 때 밥의 공개키로 편지를 암호화해서 밥의 책상 서랍에 숨겨둡니다. 중간에 클레어가 편지를 발견하더라도 클레어에게는 복호화 키가 없으므로 앨리스의 연애편지를 알아볼 수 없겠죠. 편지를 본 밥은 자신의 개인키로 연애편지를 복호화해서 앨리스의 사랑 고백을 들을 수 있을 것입니다. 그리고 밥은 앨리스에게 달려가 이렇게 말할 겁니다.
“사실 나도 너를 좋아했었어.”
비대칭키 암호의 문제점
완벽해 보이는 비대칭키 암호에도 문제가 몇 가지 있습니다. 먼저, 어떻게 하면 연애편지를 앨리스가 썼다는 것을 증명할 수 있을까요? 누군가 거짓 정보를 흘린 것을 수도 있잖아요. 이 때 사용하는 것이 ‘공개키 서명’입니다. 앨리스가 편지를 다시 앨리스의 개인키로 암호화해 편지 마지막에 쓰면 밥은 앨리스의 서명을 앨리스의 공개키로 암호화해 편지를 보낸 사람이 앨리스라는 것을 확신할 수 있게 됩니다.
두 번째로, 암호화 키와 복호화 키가 다른 암호를 어떻게 만들 수 있을까요? 상당히 근본적인 질문이죠. 게다가 공개키를 통해 비밀키를 알아낼 수 없게 만들어야 하므로 이 문제는 더더욱 어려워집니다. 이 문제에 대해 MIT의 리베스트(Ronald Rivest), 샤미르(Adi Shamir), 애들먼(Leonard Adleman)은 간단한 수학에서 답을 얻었습니다.
RSA의 등장
이 세 사람들은 디피와 헬만이 발표한 내용을 보고 비대칭키 암호를 만들기 위해 노력하고 있었습니다. 1977년 리베스트는 수학 교과서에서 비대칭키 알고리즘에 대한 아이디어를 생각해냅니다. 큰 두 소수를 곱한 값을 알아내는 것은 쉽게 할 수 있지만, 역으로 소수의 곱을 보고 그 수를 소인수분해하는 것은 매우 어렵습니다. 리베스트는 두 소수를 개인키로 하고, 두 소수의 곱을 공개키로 한다면 공개키를 알더라도 개인키를 알 수 없다는 사실을 이용해 RSA 알고리즘을 만들어 냅니다.
밥이 자신의 공개키와 개인키를 생성하는 방법을 알아봅시다.
(주의: 아래 내용을 읽기 전 항등식, 유클리드 호제법, 오일러 정리를 모르는 독자분들은 미리 찾아보시길 바랍니다.)
자, 이렇게 암호화 키와 복호화 키가 모두 만들어졌습니다. 마침 앨리스가 연애편지를 다 썼다고 합니다! 앨리스가 어떻게 편지를 암호화 하는지 같이 지켜보도록 하죠.
암호화 과정을 살펴보면 암호화 과정에 n, e만 사용되었다는 것을 알 수 있습니다. 정말 신기하군요.
사실 여기까지만 본다면 대체 왜 이렇게 복잡한 과정을 통해 암호화를 하는지 이해가 안 될 수 있습니다. 저도 그랬습니다. 하지만 밥이 앨리스의 편지를 복호화하는 것을 지켜보다 보면 생각이 달라질걸요?
마지막에 오일러 정리를 이용하기 위해서 이렇게 복잡한 과정을 거쳤던 것이군요!
클레어가 중간에 편지를 보았다고 생각해봅시다. 그래도 클레어는 앨리스의 편지를 복호화할 수 없습니다. n을 알아도 p, q를 구할 수 없기 때문에 pi(n)을 구할 수 없고, 따라서 복호화에 필수적인 d를 구할 수 없게 되기 때문이죠. p, q와 d가 이렇게 연결되어 있었군요!
후, 드디어 앨리스의 사랑이 밥에게 전달되었군요. 원래 사랑은 어려운 법입니다.
직접 해보자!
백문이 불여일견! 함께 776이라는 숫자를 RSA 알고리즘을 이용해 암호화, 복호화 해봅시다.
키 설정부터 시작합시다.
맞아요. 호제법을 이용해서 역원을 구하기 위해서 e가 pi(n)에 서로소인 자연수로 설정되었던 것입니다.
따라서 공개키는 n = 2173, e = 623, 개인키는 p = 41, q = 53, d = 207입니다.
암호화는 이 과정보다 훨씬 쉽습니다. 776은 길이가 짧기 때문에 나누지 않고 그대로 암호화 하겠습니다.
간단하죠?
복호화를 해봅시다.
좀 허무하게 끝난 것 같아 아쉽군요.
지금까지 RSA 알고리즘을 이용해서 연애편지를 몰래 보내는 방법에 대해서 알아보았습니다. 아직 공개키 서명을 하는 방법에 대해서는 자세히 다루지는 않았습니다. 이 기사를 읽고 RSA 알고리즘에 대해 관심이 생기셨다면 직접 해보는 것은 어떨까요? 저는 실패했긴 하지만, 파이썬 등을 이용해 RSA 알고리즘을 직접 구현해 보는 것도 좋은 경험이 될 것이라고 생각합니다.
RSA 암호의 미래
급변하는 시대 흐름에 비해 만들어진 지 30년도 더 지난 현재 RSA암호가 아직까지 쓰인다는 것은 정말 놀라운 일입니다. 그만큼 소수가 묘한 대상이긴 한가 봅니다. 사실 큰 수의 소인수분해는 불가능한 일은 아닙니다. 대신 어마어마한 시간이 걸리기 때문에 몇 년 동안 소인수분해를 해서 성공했다고 하더라도 그 문서를 해독하는 것이 의미가 없어진 뒤일 것입니다.
그러나 현재 연구되고 있는 양자컴퓨터가 생겨난다면 피터 쇼어가 제안한 쇼어 알고리즘을 이용해 비교적 짧은 시간안에 큰 수의 소인수분해를 할 수 있어 RSA암호를 뚫을 수 있다고 합니다. 하지만 그 때쯤 되면 RSA가 아닌 다른 암호를 주로 사용하게 되겠지요. 암호를 만드는 사람과 그것을 뚫으려는 사람의 전쟁은 인류 멸망 직전까지 계속될 것입니다.
박찬│Mathematics & Computer Science│지식더하기
참고자료
[1] 네이버 지식백과 - 수학백과 - RSA 암호
https://terms.naver.com/entry.naver?docId=3338503&cid=47324&categoryId=47324
[2] 네이버 지식백과 - 정보보안 개론 - RSA 알고리즘 https://terms.naver.com/entry.naver?docId=3431999&cid=58437&categoryId=58437&expCategoryId=58437
[3] 장삼용, 화이트 해커를 위한 암호와 해킹(제 2판)
첨부 이미지 출처
[1] https://www.pinterest.co.kr/pin/787144841111471212/
[2] 위키피디아 - 카이사르 암호
[3] 네이버 블로그 - 대칭키 암호화, 비대칭키 암호화 https://blog.naver.com/sky00141/220390287199
[4] https://semiye.com/1541
[5] https://www.linux.co.kr/security/certcc/secu_certcc_13.htm
[6] 국립기상과학원. 한국 기후변화 평가보고서 2020 – 기후변화 과학적 근거.
[7] 네이버 지식백과 - RSA 알고리즘
[8] 주간조선. 세상 바꿀 양자컴퓨터, 구글이 진짜 개발했을까? 2019.10.18
http://m.weekly.chosun.com/client/news/viw.asp?ctcd=C08&nNewsNumb=002578100019
