RSA 알고리즘은 로너드 라이베스트(Ron Rivest), 아디 샤미르(Adi Shamir), 레너드 애들먼(Leonard Adleman) 세 사람이 개발한 공개키 기반 서명 알고리즘입니다. RSA는 디지털 서명 검증뿐만 아니라 일반 데이터의 암호화와 복호화를 통해 정보를 안전하게 주고받을 수 있도록 지원합니다.
RSA 알고리즘의 기본 원리
RSA 알고리즘은 큰 수의 소인수분해가 지니는 수학적 복잡성에 기반합니다. 즉, 매우 큰 숫자를 소인수분해하는 효율적인 방법이 아직 없다는 사실에 의존합니다. 그렇기 때문에 RSA 키를 임의로 추론하려면 막대한 시간과 연산 자원이 소요됩니다.
RSA는 공개키(public key)와 개인키(private key), 서로 다른 두 개의 키를 사용하는 비대칭 암호화 알고리즘입니다. 공개키는 누구에게나 공개되며, 개인키는 소유자만 비밀리에 보관합니다. 공개키는 두 개의 숫자로 구성되는데, 그중 하나는 두 개의 큰 소수를 곱한 값입니다.
RSA 암호화에서 메시지는 숨길 필요가 없는 공개키로 암호화됩니다. 이는 RSA 알고리즘의 수학적 특성 덕분인데, 공개키로 암호화된 메시지는 오직 짝이 되는 개인키로만 복호화할 수 있습니다. 따라서 이러한 메시지를 읽기 위해서는 공개키와 개인키로 이루어진 키 쌍이 반드시 필요합니다.
RSA 알고리즘의 단계
1. 키 생성(Key Generation)
- P와 Q와 같은 두 개의 큰 소수를 선택합니다. 소수는 제3자가 쉽게 알아내지 못하도록 충분히 커야 합니다.
- N = P × Q를 계산합니다.
- (P−1)과 (Q−1)의 인수가 되지 않도록 공개키(암호화 키) E를 선택합니다.
- 다음 식이 성립하도록 개인키(복호화 키) D를 선택합니다.
(D × E) mod (P − 1) × (Q − 1) = 1
2. 암호화 및 복호화 과정
- 암호화 시, 평문(PT)으로부터 암호문(CT)을 다음과 같이 계산합니다.
CT = PTE mod N - 계산된 암호문(CT)을 수신자에게 전송합니다.
- 복호화 시, 암호문(CT)으로부터 평문(PT)을 다음과 같이 계산합니다.
PT = CTD mod N
3. 암호화/복호화 함수
키 생성이 완료되면, 해당 키들을 사용해 암호문과 평문을 계산하는 함수에 매개변수를 전달할 수 있습니다.
- 평문이 m일 때, 암호문 = me mod n
- 암호문이 c일 때, 평문 = cd mod n
RSA 알고리즘 적용 예시
p = 17, q = 13이라고 가정해 보겠습니다. e 값은 조건 1 < e < (p−1)(q−1)을 만족하는 5로 선택할 수 있습니다.
- N = p × q = 91
- D = e−1 mod (p−1)(q−1) = 29
- 공개키 쌍 = (91, 5)
- 개인키 쌍 = (91, 29)
평문(m)의 값이 10이라면, me mod n 공식을 사용해 암호문 82를 얻을 수 있습니다. 이 암호문(c)을 다시 원래 데이터로 복호화할 때는 cd mod n 공식을 적용하며, 그 결과 원래의 평문인 10이 도출됩니다.
이처럼 RSA 알고리즘은 큰 소수의 곱을 기반으로 키를 생성하고, 공개키로 암호화한 데이터를 오직 개인키로만 해독할 수 있는 구조를 통해 안전한 정보 교환을 가능하게 합니다.