[Crypto] RSA 복호화 증명 ( 재정리 必 )

RSA 키 형성

- 두 소수 p,q를 골라서 n=pq로 놓는다.

- e를 gcd(phi(n),e) = 1이 되도록 뽑는다. phi는 오일러 totient 함수

- d= $e^-1$ mod phi(n)을 계산한다. modular inverse는 e의 선택에 의해 언제나 존재하고, 확장된 유클리드 호제법을 이용해 빠른 시간안에 계산 가능

 

p, q = 무작위로 큰 두 소수

n = pq

phi = (p-1)*(q-1) >> n이하의 n과 서로소인 수들의 개수

e = 주로 65537 , 다른 값이 되더라도 1<e<phi이고 phi와 서로소인 수로 선택

d = mod phi에 대한 e의 곱셈 역원을 구한다. de = 1+k(phi)

 

암호문 c를 복호화 하는 함수는 다음과 같다 ( D=복호화 )

D(c) = $c^d$ mod n 실제로 평문을 암호화했다가 복호화하면 복구 가능하다는 것을 보일 수 있다.

D(E(m)) = E$(m)^d$ mod n

              = $m^{ed}$ mod n
              = $m^{kphi(n)+1}$ mod n

gcd(m,n)=1 일 경우

gcd의 원리 ( gcd = 두 수 사이에 존재하는 최대 공약수를 찾는 유클리드 알고리즘 )
- 임의의 두 자연수 a,b가 주어졌을때 a>b라고 가정
- a를 b로 나눈 나머지를 n이라고 하면 ( a % b = n )
- n이 0일때, b가 최대 공약수(GCD)
- n이 0이 아니라면 a에 b값을 다시 넣고 n을 b에 대입 후 step2부터 반복

오일러의 toitient 정리에 의해 $m^{phi(n)}$=1 mod n 이므로 D(E(m))= m mod n이다.

오일러의 토션트 함수는 모듈러 곱셈 역원이 존재하는 수의 개수를 구하는 함수 ϕ 기호를 사용한다.
임의의 양의 정수 n에 대해 ϕ(n)은 n 이하의 양의 정수 중 n 과 서로소인 것의 개수와 같다.
오일러 피(파이) 함수라고도 한다.

gcd(m,n) !=1 일 경우 n=pq이므로 gcd(m,n)은 p또는 q이다.

일반성을 위해 gcd(m,n) = p로 놓는다.

일단 $m^{ed}$ mod p = 0이고, m mod p = 0이므로  m=D(E(m)) mod p 이다.

(m,q) =1이므로 페르마의 소정리에 의해 $m^{q-1}$ = 1 mod q 이다.

페르마의 소정리
a가 정수이고 p가 소수이고 a가 임의의 소수 p의 약수가 아닐때
$a^p$=a(mod p )이며 a가 0이 아닐때
$a^{p-1}$ = 1 (mod p) 이다.

따라서 D(E(m)) = $m^{kphi(pq)+1}$ = $m^{k(p-1)(q-1)+1}$ = $(m^{q-1})^{k(p-1)}$m = m mod q 이다.

따라서 나머지 정리에 의해 D(E(m)) = m mod n 이다.