RSA

대표적인 공개키 알고리즘

큰 소수의 소인수 분해가 어려운 부분을 이용

 

공개키는 n, e

개인키는 n, d로 정의한다

n은 임의의 두 소수 p, q를 이용해 만듬

n = p * q

ϕ(n) = (p-1)(q-1)

ϕ는 오일러 파이함수

오일러 파이 함수는

ϕ(n)이라고 했을 때

1~n중에 n과 서로소인 수의 개수를 반환한다

서로소란 두 수의 공약수가 1이외에 존재하지 않는 수을 의미

4와 12는

4 -> {1, 2, 4}

12 -> {1, 2, 3, 4, 6, 12}

1이외에 2, 4 공약수가 존재함으로 서로소가 아님

3과 8

3 -> {1, 3}

8 -> {1, 2, 4, 8}

1 이외에는 공약수가 존재하지 않음으로 3과 8은 서로소

오일러파이 함수 예시

ex) ϕ(6)

1~6중에 6과 서로소인 자연수의 개수

6 -> {1, 2, 3, 6}

1~6까지 중 1이외에 6의 약수와 겹치 않는, 즉 서로소는 1, 5 이 둘만 존재

ϕ(6) = 2

 

오일러 파이 함수의 대표적인 항등식

ϕ(mn) = ϕ(m) * ϕ(n)

p가 소수 라면

ϕ(p) = p-1

 

이 두 가지 성질 때문에

두 소수 p, q로 만들어진 n의

ϕ(n) = (p-1)(q-1)이 성립

 

공개키에 쓰일 e는

1<e<ϕ(n) 중에 서로소인 수를 사용

ex) p=7, q=2

n = 7*2 = 14

ϕ(14) = (7-1)(2-1) = 6

1<e<6 에 포함되는 소수는 2, 3, 5가있음

 

개인키에 쓰일 d는

d=e^-1 mod ϕ(n)

/*(e*d) mod ϕ(n) =1을 만족하는 d중 하나*/

ex) 이전에 쓰인 p, q, n을 그대로 사용하고

e로 쓸 수 있는 2, 3, 5중 5를 사용한다면

(5*d) mod 6 =1을 만족하는 d로 11을 사용

 

이제 공개키 개인키에 쓰일 n, e, d를 모두 구했음

공개키 (n, e) = (14, 5)

개인키 (n, d) = (14, 11)

평문을 M, 암호문을 C라고한다면

암호화를 할 때

C = M^e mod n

으로 암호화를 하고

복호화를 할 때는 

페르마의 소정리로인해

/*p가 소수이고 a가 p와 서로소인 정수일 때

a^(p-1)≡1(mod p)*/

C = M^e mod n이 성립한다면

M = C^d mod n 역시 성립한다는 것을 이용하여

복호화를 진행한다

M을 3이라고 한다면

C = 3^5 mod 14 = 5

M = 5^11 mod 14 = 3

 

여기선 예시로 작은 소수를 사용하였지만 실제로는

매우 큰 소수를 사용 함으로서

n와 e의 값을 알더라도 d를 구하기 쉽지않다