RSA 알고리즘

ball·2024년 7월 29일

배경 지식

RSA 알고리즘을 이해하기 위해서는 다음과 같은 배경지식이 필요합니다.

a, n이 서로소이면, 다음 식이 성립된다:

a^{\phi(n)} \equiv 1 \ (mod \ \ n)

오일러 정리에 대한 증명은 간단합니다.
정수 n에 대해 n과 서로소이고, n 이하의 자연수로 이루어진 이루어진 집합을 기약잉여계라 합니다. 그리고 기약잉여계의 크기는 $\phi(n)$ 입니다.

따라서 n에 대한 기약잉여계 M은 다음과 같이 표현할 수 있습니다.

M = \{p_1, p_2, ..., p_{\phi(n)}\}

M의 각 원소에 a를 곱하게 되면 다음과 같습니다.

aM = \{ap_1, ap_2, ..., ap_{\phi(n)} \}

이때 a와 n은 서로소이므로 M과 aM은 $mod \ n$ 에 대해 동일한 집합이여야 합니다. 따라서 집합내 모든 원소들의 곱또한 $mod \ n$ 에 대해 동일해야 합니다.

p_1p_2...p_{\phi(n)} \equiv (ap_1)(ap_2)...(ap_{\phi(n)}) \equiv a^{\phi(n)}p_1p_2...p_{\phi(n)} \ (mod \ n)

입니다. 식을 정리하면 다음과 같이 됩니다.

a^{\phi(n)} \equiv 1 \ (mod \ \ n)

따라서 오일러 등식이 성립하는 것을 확인할 수 있습니다.

유클리드 호제법은 주어진 2개의 정수에 대해 최대공약수를 구하는 알고리즘입니다. 그리고 확장된 유클리드 호제법은 다음 식에서 x와 y를 구하는 알고리즘입니다.

x*a + y*b = gcd(a, b)

확장된 유클리드 호제법에 대한 설명은 다음 영상을 보면 이해할 수 있습니다.
https://www.youtube.com/watch?v=PmwLXveLtqc

비대칭 암호화 알고리즘으로 2개의 키를 가지고 암호화/복호화하는 기법입니다. 두 개의 키를 public key, private key라 부릅니다.

public key로 암호화한 데이터는 private key로 복호화할 수 있습니다.
반대로 private key로 암호화한 데이터는 public key로 복호화 할 수 있습니다.

비대칭 암호화 기법은 SSL, Digital Signature 등에 활용되고 있습니다.

RSA 알고리즘은 소인수분해를 활용합니다.

서로 다른 소수 p, q를 준비합니다.
$\phi(pq) = (p-1)(q-1)$ 입니다.
$p-1$ 과 $q-1$ 과 서로소인 정수 $e$ 를 준비합니다. e는 주로 소수 3, 17, 65537을 사용합니다.
$de \equiv 1 \ (mod \ pq)$ 인 d 를 구합니다.(확장된 유클리드 호제법을 사용합니다) $d * e + l * pq = gcd(e, pq) = 1$
public key는 (pq, e)이고, private key는 (pq, d)입니다.
암호화와 복호화는 다음과 같이 이루어집니다(오일러 정리): $(plain)^e \equiv encrypt \ (mod \ pq)$ $(encrypt)^d \equiv plain \ (mod \ pq)$

KAIST CS Major