RSA란?
고전 암호와는 달리, RSA, ECC 등은 ‘어려운 문제’에 기반하여 암호화를 진행합니다. 이러한 ‘어려운 문제’는 컴퓨터를 이용하여도 정답(혹은 해)를 구하기 어려운 문제를 말하며, 소인수분해 문제, 이산 로그 문제 등이 대표적인 예시입니다. RSA는 그 중 소인수분해가 어려운 문제라는 점을 활용하는 암호화방식입니다. GNFS 등 빠른 소인수분해 알고리즘이 등장하였으나, 비트수에 대한 다항 시간 알고리즘은 알려져 있지 않아 큰 수를 소인수분해하는 것은 여전히 어려운 문제입니다.
RSA는 1978년 로널드 라이베스트(Ron Rivest), 아디 샤미르(Adi Shamir), 레너드 애들먼(Leonard Adleman)의 연구에 의해 체계화되어, 이 세 연구자의 이름 앞글자를 따 RSA라는 이름이 붙었습니다.
암호화뿐만 아니라 전자서명이 가능한 최초의 알고리즘으로 알려졌다고 합니다.
양자 컴퓨터가 실용화된 후에는 쇼어 알고리즘을 이용하여 RSA를 무력화할 수 있을 것으로 알려졌으나, 아직 그러한 시기에 도달하지 않아 많이 사용되고 있습니다.
RSA의 원리와 구현
다음은 RSA의 동작을 파이썬 코드로 나타낸 것입니다.
from Crypto.Util.number import bytes_to_long, getPrime
bits=1024
def RSA_encrypt(M):
p=getPrime(bits)
q=getPrime(bits)
N=p*q
e=0x10001
C=pow(M,e,N)
return N,e,C
M=bytes_to_long(input("Input Plain Text >> ").encode())
RSA=RSA_encrypt(M)
print(f"""N : {str(RSA[0])}...
e : {str(RSA[1])}
Cipher Text : {hex(RSA[2])}""")
아래는 실행 결과이며, N와 암호문은 길이가 길어 앞부분만 출력하고 생략하였습니다.
Input Plain Text >> Hello World!
N : 1815770945...
e : 65537
Cipher Text : 0x10c4942a...
위 코드의 동작과 결과를 한 번 살펴 봅시다.
우선 RSA의 암호화에서는 특정 비트의 두 소수 p, q를 생성합니다. 약수가 적을 수록 큰 수의 소인수분해는 어렵기 때문에, N=p×q로 정의되는 N을 RSA 암호화에서 활용하게 됩니다.
N과 e의 순서쌍인 (N,e)를 공개키라고 부르는데, 이것은 N와 e가 외부 사용자에게 공개되어도 RSA 암호를 쉽게 깰 수 없으므로 공개되어있기 때문입니다.
e를 공개 지수(public exponent)라고 부르며 RSA 암호화는 간단하게 평문인 숫자 M에 대해 Me mod N으로 정의됩니다.
하지만 복호화에는 비밀 지수(private exponent)라고 불리는 d라는 수가 필요합니다. (N과 d의 순서쌍인 (N,d)는 비밀키라고 부릅니다.)
e와 d는 ed mod ϕ(N)=1을 만족하는 수로, 암호문 C에 대해 Cd mod N을 계산하면 M과 같아지게 됩니다.
이 사실은 오일러의 정리에 기반합니다. 오일러의 정리는 서로소인 a, n 에 대해 다음이 성립함을 의미합니다.
aϕ(n)modn=1
이 때 a=M, n=N인 상황을 생각해본다면 Cd mod N= Med mod N= Mk×ϕ(N)+1 mod N=M이므로 정상적인 복호화가 가능함을 알 수 있습니다.
End Card
본 글에서는 다음과 같은 사실을 다뤘습니다.
- RSA는 소인수분해의 어려움에 기반한다
- 공개키, 비밀키는 각각 (N,e)와 (N,d)로 정의된다.
- RSA 암호화는 평문을 e제곱함으로써 구현된다.
- RSA 복호화는 평문을 d제곱함으로써 구현된다.
- 이러한 암호화/복호화가 가능한 것은 오일러의 정리에 기반한다.
다음 글에서는 RSA의 인자가 특정 조건을 만족할 때 사용할 수 있는 공격법에 대해 다룰 예정입니다.