[이산수학] RSA 암호화 및 복호화 알고리즘

 

✔ PKI(Public Key Infrastructure): 비대칭키 암호 시스템

평문(데이터)를 공개키로 암호화하면 개인키로 복호화가 되고 반대로 개인키로 암호화하면 공개키로 복호화가 가능한 것이 핵심이다.

 

• 공개키 : 외부에 공개 가능한 키
• 개인키 : 외부에 공개 불가능한 키

 

이 두 키를 가지고 있으면서 소유자를 증명하는 것이 PKI 인증서이다.

통신주체는 PKI 인증서를 모두 갖고 있어야한다.

기본적인 비대칭키 암호화 알고리즘은 다음과 같이 수행된다.

1. 철수와 영희는 서로 공개키를 교환한다.
2. 철수는 영희의-공개키로 데이터를 암호화하여 영희에게 보낸다.
3. 영희는 자신의 개인키로 데이터를 복호화 한다.
4. 영희는 철수에게서 받은 철수-공개키로 암호화하여 철수에게 보낸다.
5. 철수는 자신의 개인키로 데이터를 복호화 한다.

 

✔ RSA(Ribest Shamir Adelman)

• 완전한 공개키기반구조(PKI)를 제공하며 PKI의 기본이 되는 공개키와 개인키를 만드는 키 생성 알고리즘이다.
• 소인수분해의 어려움에 기반하며 공개되는 공개키를 가지고 개인키를 유추하기 어렵다.
• 두 소수(p, q)가 클 수록 유추하는 것이 어렵다.

 

암호화 순서

공개키(n, e)는 다음과 같이 생성한다.

1. 서로 다른 두 소수(p, q)를 선택한다.
2. p와 q를 곱해 n을 구한다. (n = p * q)
3. e는 (p-1)(q-1)과 서로소인 값이다. 
4. 공개키가 만들어졌다면 메시지를 암호화하기 위해, 평문 m을 정수의 수열로 바꾸어야 한다.
5. 평문의 알파벳을 두 자리 숫자로 바꾼다. (A = 00, B = 01 등)
6. 암호화는 각 블록 m을 암호문 블록 c로 변환하며 진행한다. c = mᵉ mod n
7. 이때 암호문 c는 이진법을 이용한 나머지 거듭제곱 알고리즘을 이용하면 편하다.
8. 암호화 된 블록은 암호문의 수신자에게 보내지게 된다.

 

복호화 순서

해독키 d는 다음과 같이 생성한다.

1. (d*e)/n 일 때, 나머지가 1인 정수 d를 구한다.
2. d는 (p-1)(q-1)의 역이므로 de = 1(mod(p-1)(q-1) 이다.
3. 따라서 de = 1 + k(p-1)(q-1)인 정수 k가 존재하게 된다. 
4. 페르마의 작은 정리에 의해 mᴾ⁻¹ = 1(mod p)이고 m𝚚⁻¹ = 1(mod q)이다. m = cᵈ mod n
5. 복호화 시 m이 나온다면 성립한다.

사실 여기서 유클리드 호제법과 베수의 방정식을 사용해 d를 구해내야한다.

 

유클리드 호제법

공개키 e를 구하기 위해서 오일러함수 n과 서로소여야하는 것을 증명한다. 

 

베수의 방정식

유클리드 호제법에 사용된 식을 이용해 역으로 계산한 값을 숫자에 대치시켜가며 ax + by = 1 이 되는 x, y 값을 찾아야한다. 식을 만족시키는 값이 분명 존재한다는 것이 베수의 방정식이다.