[Cryptography 1.] RSA system

DoHoon Kim·2022년 4월 17일
0

Cryptography

목록 보기
2/6

이번 포스트에서는 public key system들 중, RSA system에 대해서 간략하게 설명하겠습니다.

RSA system이란 무엇인가

RSA system은 '매우 큰 수를 소인수 분해하기 어렵다'는 가정에서 출발합니다. RSA system을 build하는 방법은 다음과 같습니다.

1) 매우 큰 소수 p,qp, q 를 준비합니다.
2) 소수 p, q를 곱해 N을 만듭니다. N=pqN = p * q
3) N의 Euler totient function의 값, ϕ(N)=(p1)(q1)\phi(N) = (p-1) * (q-1) 과 서로소인 수 ee를 준비합니다.
4) de1(modϕ(N))d \equiv e^{-1} \pmod {\phi(N)}dd 값을 구합니다.

위와 과정을 거친 후, 다음과 같이 RSA system을 정의하겠습니다.

Public key는 (e,N)(e, N) 으로, private key는 dd 로 정의합니다.

암호화할 메시지 MM 이 있다고 하고, 이를 암호화하기 전 특정 규칙에 따라 일련의 수로 변환했다고 가정하겠습니다. 암호화는 다음과 같은 과정으로 이루어집니다. 암호화는 메시지를 전달할 대상의 public key를 이용합니다.

암호화된 메시지는 CMe(modN)C \equiv M^{e} \pmod {N} 으로 정의합니다.

복호화는 메시지를 전달받은 쪽의 private key를 통해 이루어집니다.

복호화는 MCd(modN)M \equiv C^{d} \pmod {N} 을 통해 이루어집니다.

RSA system의 정당성

위에서 소개한 복호화 방법으로 어떻게 원문을 얻어낼 수 있는 걸까요? 간단한 수학적 증명으로 보일 수 있습니다.

(e,  ϕ(N))=1d    e    1  (modϕ(N))C    Me  (modN)(e, \;\phi(N)) = 1 \\ d \;* \;e \;\equiv \;1 \;\pmod {\phi(N)} \\ C \;\equiv \;M^{e} \;\pmod {N}

위와 같은 암호화 과정을 거친 후 나온 메시지 CC에 대하여, CdM(modN)C^{d} \equiv M \pmod{N} 임을 증명하겠습니다.

Cd    (Me)dMed  (ed1(modϕ(N)))Mϕ(N)k+1M(Mϕ(N)k)(modN)C^{d} \;\equiv \;(M^{e})^{d} \\ \equiv M^{ed} \;(\because e*d \equiv 1 \pmod {\phi(N)}) \\ \equiv M^{\phi(N) \,* \,k \,+ \,1} \\ \equiv M(M^{\phi(N) \,* \,k}) \pmod {N} \\

위에서 두 가지 케이스를 생각할 수 있겠습니다.

if  (M,N)  =  1,  by  Eulers  theorem,Mϕ(N)1(modN).M(Mϕ(N)k)M  1k(modN)M(modN)CdM(modN)if \;(M, N) \;= \;1, \;by \;Euler's \;theorem, \\ M^{\phi(N)} \equiv 1 \pmod{N}. \\ \\ M(M^{\phi(N) \,* \,k}) \equiv M \;* 1^{k} \pmod{N} \\ \equiv M \pmod {N} \\ \therefore C^{d} \equiv M \pmod {N}

두 번째 케이스는 MMNN이 서로소가 아닌 경우입니다.

if  (M,N)  =  p,ϕ(N)=(p    1)  (q    1)  by  the  property  of  Euler  totient  function,M(Mϕ(N)k)M(M(p1)(q1))kM1k(p1)M(modq)M(Mϕ(N)k)0(modp)(p,q)=1CdM(Mϕ(N)k)M(modN)  (N=pq)if \;(M, N) \;= \;p, \\ \phi(N) = (p \;- \;1) \;* (q \;- \;1) \;by \;the \;property \;of \;Euler \;totient \;function, \\ \\ M(M^{\phi(N) \,* \,k}) \equiv M(M^{(p-1)(q-1)})^{k} \\ \equiv M * 1^{k(p-1)} \\ \equiv M \pmod {q} \\ \\ M(M^{\phi(N) \,* \,k}) \equiv 0 \pmod {p} \\ \because (p, q) = 1 \\ \therefore C^{d} \equiv M(M^{\phi(N) \,* \,k}) \equiv M \pmod {N} \;(N = p * q)

RSA system에서 제시하는 복호화 방법으로 원문 MM 을 얻어낼 수 있음을 보였습니다.

RSA system의 안정성은 앞에서 설명했듯이, 큰 수를 소인수 분해하기 어렵다는 가정에서 출발합니다. 위에서 NN 이 어떤 소인수로 분해될지 알기 어렵다는 사실이, 어떻게 이 암호 체계의 안정성을 보장할 수 있을까요?

N=pqN = p*q 일 때, p,qp, q의 값을 빠르게 찾아낼 수 있다고 가정해 보겠습니다. p,qp, q 의 값을 통해 빠르게 Euler totient function의 값을 얻어낼 수 있고, modulo  ϕ(n)modulo \;\phi(n) 에 대한 public key( ee ) 의 inverse(private key)를 계산할 수 있을 것입니다.

profile
Researcher & Developer

0개의 댓글