RSA암호화 알고리즘에는 2개의 암호화 키가 사용됩니다. 하나는 모두에게 공개되는 공개키이고 하나는 공개하지 않는 개인만 알고 있는 개인키(비밀 키라고도 함)입니다. 공개키는 평문을 암호화할 때 사용되고 개인키는 암호문을 평문으로 복호화할 때 사용합니다.
RSA알고리즘의 안정성은 아주 큰 합성수는 인수분해하기 어렵다는 인수분해 문제의 어려움에 기반합니다.
오일러 정리
오일러 정리는 \(n\)과 서로소인 양의 정수 \(m\)이 다음 식을 만족한다는 정리입니다.
\( m^{\varphi \left ( n \right )}\equiv 1\left ( \textrm{mod}\,n \right ) \)
여기서 \( \varphi \left ( n \right ) \)는 오일러 파이 함수라고 불리며, \(n\) 이하의 양의 정수 중에서 \(n\)과 서로소인 수의 개수를 의미합니다.
예를 들어 6 이하의 양의 정수 중 6과 서로소인 수는 1,5로 두 개이기 때문에 \( \varphi \left ( 6 \right )=2\)입니다.
공개키 생성
1. 두 소수를 찾는다. \( p = 53, q = 59 \)
2. 두 소수를 곱한다. \( n = p*q = 53 * 59 = 3127\) \(n\)이 첫 번째 공개키 재료
공개키 생성을 위한 재료(\(e\))가 하나 더 필요하고 \(e\)는 아래의 조건을 만족하는 숫자들 중 하나를 정하면 됩니다.
\( \varphi \left ( n \right ) \)와 서로소 관계이어야 한다. \( \textrm{gcd}\,\left ( e,\varphi \left ( n \right ) \right ) = 1 \)
즉, \( e \)값은 \( \varphi \left ( n \right )=\left ( p-1 \right )\left ( q-1 \right )=3016\)와 서로소 관계인 3,5,7,9 중 하나를 선택하면 됩니다.
\( e=3 \)으로 정하겠습니다.
비밀키 생성
비밀키 생성에 필요한 \( d \)는 \( d \equiv e^{-1}\left ( \textrm{mod} \, \varphi \left ( n \right ) \right ) \)을 만족하는 수들 중 하나입니다. \( d=2011 \)로 정하겠습니다.
암호화
공개키 \((n,e)\)로 \(n\)보다 작은 평문 \(m\)을 암호화할 때, 암호문 \(c\)는 다음 식으로 구해집니다.
\( c≡m^{e} \left ( \textrm{mod}\, n \right ) \)
"melon"을 숫자로 변환했을 때 2033으로 가정하고 "melon"을 암호화 하면
\( c≡2033^{3} \left ( \textrm{mod}\, 3127 \right ) \)
암호문은 1983이 됩니다.
복호화
암호문 \(c\)를 개인키 \(d\)로 복호화할 때, 평문 \(m\)은 다음과 같이 구해질 수 있습니다.
\( m≡c^{d} \left ( \textrm{mod}\, n \right ) \)
\( c≡1983^{2011} \left ( \textrm{mod}\, 3127 \right ) \)
당연히 계산 결과는 2033입니다.
참고문헌
geeks for geeks - RSA Algorithm in Cryptography