[RSA] 소개 & 키 생성 알고리즘

RSA는 공개키 암호 알고리즘 중 하나이다.

1978년 로널드 라이베스트(Ron Rivest), 아디 샤미르(Adi Shamir), 레너드 애들먼(Leonard Adleman)이 공동 개발하였으며, 이들의 이름 앞글자를 따서 RSA가 되었다.

 

RSA의 안정성은 큰 수에 대한 소인수 분해의 어려움을 기반으로 한다.

 

일반적으로 공개키 암호는 공개키와 개인키가 한 쌍을 이루며, 공개키로 암호화한 메시지를 개인키로 해독하여 열어볼 수 있기 때문에 암호화 키와 복호화 키가 다르다는 점에서 비대칭키 알고리즘의 특징을 가진다.

 

RSA에서 사용되는 용어들

표기	설명
p, q	매우 큰 두 소수 (p≠q)
N	p x q
gcd(a, b)	a, b의 최대 공약수
φ(N)	(p - 1) x (q - 1)
a mod n	a ÷ n의 나머지 (a % n)
a ≡ r mod n	(a % n) = (r % n). a와 r은 합동이다.
e	N과 함께 사용되는 공개키
d	N과 함께 사용되는 비밀키(개인키)
M	평문. 공개키로 암호화 된다.
C	암호문. 개인키로 복호화 된다.
KU	공개키. KU = {e, n}으로 표기
KR	개인키. KR = {d, n}으로 표기

 

키 생성 알고리즘

1. 서로 다른 큰 소수 p, q를 선택한다. (p ≠ q)
2. N = p x q를 계산한다.
3. φ(N) = (p - 1) x (q - 1)을 계산한다.
4. φ(N) 보다 작고, φ(n)와 서로소인 자연수 e를 선택한다. (gcd(e, φ(N))=1, 1 < e < φ(N)인 e 선택)
5. d x e를 φ(N)로 나누었을 때 나머지가 1인 정수 d를 구한다. ( de ≡ 1 mod φ(N) ) , 유클리드 호제법 이용
6. KU = {e, N}, KR = {d, N}이 된다.

암/복호화

암호화

 

복호화

 

즉, KU를 가지고 있으면 M을 암호화하여 C로 만들 수 있고, KR을 가지고 있으면 C를 복호화하여 M을 추출해 낼 수 있다.