[암호학, 정보보호, 현대암호] RSA 암호화 방법

1. RSA 암호화 개요

RSA 암호화는 공개키 암호화 알고리즘의 대표적인 방법으로 1977년 리차드 석(Richard Rivest), 아디 샤미르(Adi Shamir), 레오나드 아델만(Leonard Adleman)에 의해 개발되었다. 이 알고리즘은 두 개의 키를 사용하는 비대칭 암호화 방식으로, 하나는 공개키(public key)로 공개되며 누구나 알 수 있지만, 다른 하나는 개인키(private key)로 소유자만이 알고 있어야 한다. RSA는 크게 세 가지 과정으로 이루어진다. 먼저, 두 개의 큰 소수 p와 q를 선택한다. 이 두 소수는 300자리 이상인 큰 숫자로 선택되어야 하며, 이를 곱하면 n=p×q로 나타낸다. 이 n은 공개키와 개인키 모두에 사용되는 모듈로 작용한다. 둘째, 오일러 피 함수 φ(n)를 계산하는데, 이는 (p-1)·(q-1)로 정의된다. 셋째, 공개키 e를 선택하는데, 이는 1보다 크고 φ(n)보다 작으며, φ(n)과 서로소 관계를 가져야 한다. 이후, 개인키 d는 e와 φ(n)에 대해 연립방정식을 만족하는 값으로 구한다. 즉, e×d ≡ 1 (mod φ(n))를 만족하는 d를 찾는다. 이때, e와 d는 서로 역원 관계에 있으며, 이를 통해 송신자가 메시지를 암호화하면 수신자는 개인키로 복호화할 수…