RSA 암호 원리 이해하기

https://www.youtube.com/watch?v=JIy0nhT6Kfw

 

 

RSA

금융거래에서 본인을 증명하는 디지털 신분증의 용도로 활용

 

 

공개 키 <N, e>

개인 키 <N, d> 

 

예시)

암호화  N= 33 e= 3

전달할 내용 : 9

$9^{3}$ 을 33으로 나눈 나머지 = 3

 

복호화  N= 33 d= 7

$3^{7}$ 를 33으로 나눈 나머지 = 9

 

---

암호에 필요한 키 N, e, d 생성하는 법

1. 두 개의 소수 p, q를 정한다.

최대한 큰 수 일수록 좋지만, 연산을 위해 작은수를 선택.

 

p = 3, q = 11

 

2. 두 소수의 곱을 N으로 한다. 

 

N = pq= 33

 

3. N의 오일러 피함수값을 계산한다.

 

$\phi $ : N이하의 자연수 중에서 N과 서로소인 수의 갯수

N=pq (p,q는 소수)

$\phi $(N) = (p-1)(q-1)

 

$\phi $(33) = 20

 

4. 다음을 만족하는 수를 e로 한다.

$\phi $(N) 보다 작고, $\phi $(N) 과 서로소인 자연수

 

e = 3

 

5. 다음을 만족하는 수를 d로 한다.

ed를 $\phi $(N)으로 나누었을 때, 나머지가 1이 된다.

 

 

$\therefore$ 공개키<33,3> 비밀키 <33,7>

 

---

RSA 암호 - 기본 수학원리 살펴보기

 

1. 나머지 연산

 

 a $ \equiv $ b (mod N) 이면, a-b= kn이다.

 

2. 오일러함수

 

N = pq(p,q는 소수)이면, $\phi $ (N) = (p-1)(q-1) 이다.

 

 

3. 오일러정리

 

a와 n이 서로소인 자연수일 때, $a^{ \phi $ (n) }  \equiv $ 1 (mod n)

 

4. 페르마의 소정리

오일러정리의 특수한경우. n이 소수인경우의 정리.

 

$a^{p-1} \equiv $ 1 (mod p)

 

 

 

두 개의 소수 p, q 

1) N = pq

2) ed $\equiv$ 1 (mod $\phi$(N))

 

- e를 정할 때 필요한 조건

1<e< $\phi$(N), $\phi$(N)과 서로소인 e를 선택.

- e를 정하면, d는 반드시 존재하는지

ed = k$\phi$(N) + 1인 d 찾기

 

=> 공개키 <N, e>

=> 개인키 <N, d>

=> 보안을 위해 두 소수 p,q는 폐기

 

 

C, D가 서로소일 때,

a $\equiv$ b (mod C)

a $\equiv$ b (mod D)

=> a $\equiv$ b (mod CD)