21.09.05 RSA 알고리즘

RSA 암복호화 알고리즘에는 public key, private key를 사용하는데

key라고 해서 복잡한 무언가가 아니라 상수 두 개 만들고 각각을 key라고 한다. 

그 두 상수를 생성하는 원리는 다음과 같다. 

 

✔key 생성 원리

1. p와 q는 서로 다른 소수이다. 
2. p와 q를 곱한 값인 N을 찾는다. 
3. 오일러 피 함수에 N을 대입한 값 φ(N)을 찾는다. (p-1)(q-1)으로 계산할 수 있다!
4. φ(N) 보다는 작고 φ(N)와 서로소인 정수 e를 찾는다. 
5. 확장된 유클리드 호제법을 이용하여 
d x e를 φ(N)로 나누었을 때 나머지가 1인 임의의 정수 d를 구한다. 

 

✔public key와 private key

위를 통해 N, e, d 값을 구할 수 있는데 

public key는 <N, e>이고 private key는 <N, d> 이다. 

이때, p, q로 e, d값을 계산할 수 있기 때문에 p와 q의 보안은 매우 중요하다.

따라서 N, e, d값을 알고난 후에는 p, q 값을 지워버리는 것이 안전하다. 

 

RSA 알고리즘은 주어진 public key만으로 private key를 알아내기 위한

소인수분해 계산 과정이 난해하다는 점에서 보안성을 유지할 수 있다. 

 

✔예제

1. p = 61, q = 53일 때, 
2. N = 61 x 53 = 3233
3. φ(3233) = (61 - 1)(53 - 1) = 3120
4. 임의의 수 e를 1 < e < 3120 의 범위에서 φ(N)과 서로소 관계인 정수 17로 선택한다. 
5. 17 x 2753 = 46801 이므로 3120으로 나눴을 때 나머지는 1인 d는 2753이다. 이 값은 하나만 나오는 것인지 궁금

 

검산했을 때,

public key는 3233, 17이며 평문 m은 m^17(mod 3233)로 암호화할 수 있고 

private key는 3233, 2753이며 암호문 c는 c^2753(mod 3233)로 복호화할 수 있다. 

 

평문을 정수로 설정했을 때,

평문 m이 65라면 65^17(mod 3233)인 값인 2790으로 암호화되고 

2790인 암호문 c는 2790^2753(mod 3233)인 65로 복호화된다. 

 

실제로는 p, q의 값이 커서 위와 같은 암복호화 과정보다 연산 과정이 훨씬 복잡하다.

따라서 암호화 라이브러리인 OpenSSL 등을 사용한다. 

 

*참고링크 : https://ko.wikipedia.org/wiki/RSA_%EC%95%94%ED%98%B8