RSA 알고리즘 [유클리드, 오일러]

RSA 암호방식을 공부하다 보면 Diffie Hellman이라는 내용을 접하게 될 것이다.

이를 정리해 보도록 한다. --> 이를 이용해 공개키 방식을 도입

Diffie Hellman 방식은 소인수 분해의 문제를 기반으로 만들어진 방식이다.

그러면 소인수 분해의 문제란 무엇일까?

그리고 소인수 분해의 문제를 공부하다 보면 나오는 오일러의 정리에 대해서

알아보고자 한다.

기본적인 수학 지식으로 유클리드 정리, 나머지 정리 등을 알아야 한다.

[정수론에서 배운다.]

소인수 분해의 문제

N의 소인수 분해 N = p[소수] × q[소수]라는 관계식을 공격자는 알고 있고 N은 공개 

N으로부터 p와 q를 구할 수는 없는 것일까?  

p와 q는 소수이기 때문에 N으로부터 p와 q를 구핚다는 것은 자연수 N을 소인수분해

하는 것  

즉, 소수 p와 q가 있으면 N을 구할 수 있지만, N만 가지고는 소수 p,q를 가지는 것은

현실적으로 어렵다는 것이다. --> 소인수 분해의 문제

유클리드 호제법 

주어진 두 개의 정수 a, b 에 대하여 a, b의 최대 공약수를 찾는 방법

확장된 유클리드 호제법     [확장된 개념]

gcd(a, b) = d  --> a와 b의 최대 공약수가 d

a*X + b*Y = d를 만족하는 정수 X,Y를 찾는 방법

오일러 정리

필요한 기호 : Φ(n) : 1부터 n까지의 자연수 중, n과 서로 소인 것의 개수. 

EX) Φ(7) = 1,2,3,4,5,6 = 6

gcd(a,n) =1 --> a,n과 서로소인 정수 이면 a^Φ(n) ≡ 1 (mod n) 이 성립

ex) a = 3 , n = 7

3^6 ≡ 1 (mod 7)

--> ( 3^2  (mod 7)) * ( 3^2  (mod 7)) * ( 3^2  (mod 7))

--> ( 9 mod 7 ) * ( 9 mod 7 ) * ( 9 mod 7 )

--> 2 * 2 * 2 mod7 = 8 mod 7 = 1 

RSA 키 생성 과정

1 .랜덤한 두개의 큰소수 p, q 를 고릅니다. 

2.  n = p*q 와 Φ(n) = (p-1)(q-1) 를 계산 합니다.

3.  랜덤한 정수 e 를 선택 합니다. 1 < e < Φ(n), gcd(e, Φ(n))=1

4.  확장된 유클리드 알고리즘을 사용해서 정수 d를 계산 합니다. 

1 < d < Φ(n), ed ≡ 1 (mod Φ(n))

5, public Key 는 (n, e)가 되고, private Key 는 d가 된다.

RSA 키 생성 과정에서의 수학적 원리?

4번 과정을 자세히 보도록 한다.

3번 단계에서 e를 선택 할 때 Φ(n)과 서로소인 수를 선택

등장

확장된 유클리드 호제법     [확장된 개념]

gcd(a, b) = d  --> a와 b의 최대 공약수가 d

a*X + b*Y = d를 만족하는 정수 X,Y를 찾는 방법

확장된 유클리드 호제법을 떠올려 보자

e와  Φ(n)이 서로소이다 그러면 유클리드 호제법에서

a는 e가 되고 b는 Φ(n)가 될 것이다.

e * d[비밀키] + k * Φ(n) = 1을 만족 한다.

여기에  mod Φ(n)을 하면?

e * d = 1 mod Φ(n) 이 나오게 된다.

그러면 e는 정해져 있고 d를 구할 수 있다.

그러면 안전성은 어떻게 될 까?

공개키는 e와 n이라고 했다.

e * d = 1 mod Φ(n)인데....

Φ(n)을 구하기도 어렵다.. 소인수 분해도 해야한다.

그리고 mod 연산이기 때문에 여러개의 값이 나올 수있어서 

현실적으로 어렵다.