공개키 암호화 알고리즘 예

키 생성 알고리즘

1. 서로 다른 아주 큰 소수 p, q를 선택한다.
2. p와 q를 곱해서 N값을 생성한다.
3. 오일러 파이 함수 값과 오일러 정리를 활용한다.

오일러 파이함수

Φ(N)=(p-1) * (q-1)

결국 p 값에 대한 오일러 함수는  1 부터  솟수인 p와 서로 소 관계인 정수의 갯수를 세는 함수이다. q에 대한 정수의 갯수도 마찬가지. p*q (N)와 서로 소 관계인 정수의 갯수

—>N 과 서로 소인 정수의 갯수는 Φ(p) * Φ(q)가 된다.

오일러 정리

다음의 문자는 위에서 나오는 문자와 관계없는 새로운 값이다. 단지 같은 문자만 사용한다.

a^(p-1) ≡ 1 mod p (단 a 와 p 는 서로소)

a^Φ(n) ≈ 1 mod n

---

4 Φ(N)과 서로소인 e 를 선택한다.

5.  e * d ≡ 1 mod( Φ(N)) 를 만족하는 d 를 구한다.

6  공개키 (N, e) , 개인키(N, d)

7. 암호화(공개키 이용)

C=M^e(mod Φ(N ))

8. 복호화(개인키 이용)

M=C^d( mod Φ(N) )

 

————————————————————————————–

p=11, q=3 라고 할 때

N=33

Φ(33)=10 * 2 = 20

20과 서로소인 임의의 e 를 3이라 하면

( 3* d) mod(20))=1

(3 * d) = 20*Q(x) +1

d= 7

——————————————–

6. 개인키  : N , d (33, 7)

공개키 : N, e (33, 3)

7 . 암호화

평문 M을 암호화. M=3

C=M^e(mod 20) =7

3^3(mod 20) =7

7을 복호화

M=C^7(mod 20)

7^7(mod 20)= 3