[알고리즘] 공개 키 암호화 시스템 - RSA(Rivest-Shamir-Adleman) 암호화 알고리즘

암호화 알고리즘

공개 키 암호화 시스템

공개 키 암호화 시스템의 순서도 (출처 : wikimedia)

RSA(Rivest-Shamir-Adleman) 알고리즘

• 1. 서로 다른 두 개의 큰 소수 p, q 선택 (100자리)
  • p*q → r
• 2. 하나의 큰 숫자 e 선택 (공개 암호화 키)
  • p-1, q-1과 각각 서로소이어야 함
  • p, q보다 큰 어떤 소수이어햐 함
• 3. 비밀 해독키 d 계산
  • (e*d) % {(p-1)*(q-1)} == 1을 만족하는 d 찾기
  • 표기법 : d*e = 1 modulo (p-1)*(q-1)
    • mod 연산에 대한 표기법 참고
• 4. 정수 r과 e는 공개하고, d는 비밀로 유지
• 5. 평문 P로부터 암호문 C = P^e modulo r 계산
• 6. 암호문 C로부터 평문 P = C^d modulo r 계산

>>> p = 3
>>> q = 5
>>> r = p*q
>>> r
15
>>> (p-1)*(q-1)
8
>>>
>>> # let e be 11 (prime greater than both p, q)
>>> e = 11
>>>
>>> # find d
>>> # d*e = 1 modulo (p-1)*(q-1)
>>> # d*11 = 1 modulo 8
>>> # so, d = 3
>>> d = 3
>>>
>>> ## Encryption ###
>>> # let P = 13 (Plain text)
>>> P = 13
>>> # C = P^e modulo r
>>> # C = P**e % r
>>> # C = 13*11 % 15
>>> C = P**e % r
>>> C
7
>>>
>>> ### Decryption ###
>>> # P = C^d modulo r
>>> # P = C**d % r
>>> # P = 7**3 % 15
>>> P = C**d % r
>>> P
13

발송인 S가 수신인 R에게 메시지 P 전송

발송인 S :

수신인 R :

S가 메시지 P를 전송하였다는 것을 확인할 수 있음!