RSA(Rivest, Shamir, Adleman)는 공개키 암호화 방식이며, 큰 숫자의 소인수 분해가 NP-문제로 풀기 어렵다는 것을 기반으로 한다(물론, 양자컴퓨터로는 금방 풀릴 것으로 보인다).
먼저, 수신측에서 다음을 계산한다.
- 서로 다른 두 소수 p, q의 곱인 n을 정한다.
- Euler's totient (n)을 구한다. 여기서는 (p - 1) * (q - 1)과 같다.
- 앞서 구한 Euler(n)의 값과 서로소이면서 더 작은 값 e를 정한다.
- (e * d) % Euler(n) = 1 을 만족하는 d를 구한다.
이후, n과 e를 공개한다.
Encryption
메세지 M과 수신측이 제공하는 n, e를 바탕으로 C = (M^e) % n 를 계산한다.
암호문 C를 전송한다.
Decryption by Third Party
제3자가 C를 가로채 확인한다고 가정하자.
비록 e와 n이 공개되어 있지만, Euler(n)을 추정하기 힘들며, 모듈러 연산은 단방향 함수이기 때문에 M을 추정하기는 더 힘들다.
Decryption
수신받은 암호문 C는 M = (C^d) % n를 계산하여 복호화한다.
Example
p: 3
q: 5
n: 15
e: 7
d: 7
M: 8
Encryption: (8 ^ 7) % 15 = 2
Decryption: (2 ^ 7) % 15 = 8
추가
모듈러 연산의 역원을 구하는 방법과 큰 수에 대한 빠른 모듈러 연산은 다음에 알아보자.
(이 글은 추후 수정될 예정입니다.)