[암호학] RSA

HyeonMin Kim·2023년 12월 2일
Cryptography
post-thumbnail

RSA라는 알고리즘은 비대칭키를 이용한 알고리즘 중 하나입니다

Mathematical Difficulty에서 Factorization problem을 이용한 알고리즘입니다

Factorization problem이란

소수 A와 B가 주어졌을 때 A*B는 쉽게 구할 수 있지만 두 소수 A,B로 곱해진 값 C를 주고 A와 B를 찾으라 하면 찾기 거의 불가능하다 라는 것입니다

RSA

Public

  • encryption key(random string): e
  • Modulus N

Private

  • Larger Prime : p, q
  • ed=1modϕ(n)ed = 1mod\phi (n) 을 만족하는 d
  • ϕ(n)=(p−1)(q−1)\phi(n) = (p-1)(q-1)

다음과 같이 공개된 값과 공개되면 안되는 값이 정의 되어있습니다

mesage M, ciphertext C라고 한다면

Encryption : C=MemodNC=M^emodN
Decryption : M=CdmodNM=C^dmodN
입니다

Me=CCd=M(Me)d=Med=MCdmodN=MedmodN=MM^e = C\\ C^d = M\\ (M^e)^d = M^{ed} = M\\ C^dmodN = M^{ed}modN = M

위의 식을 증명해야합니다. 위의 식을 증명하기 위해서는 오일러 정리와 페르마 정리가 필요합니다
오일러 정리

  • x와 n이 서로소이면 𝑥ϕ(𝑛)≡1𝑚𝑜𝑑𝑛𝑥^{\phi(𝑛)}≡1𝑚𝑜𝑑𝑛
    페르마 정리
  • p가 소수라면 ap−1≡1modpa^{p-1}≡1modp

증명

CdmodN=MedmodN=MCdmodN=Medmoded=1modϕ(n)ϕ(n)=(p−1)(q−1)ed=1mod(p−1)(q−1)ed=k(p−1)(q−1)+1ed−1=k(p−1)(q−1)=kϕ(n)Med=Med+1−1=M⋅Med−1=M⋅Mk(p−1)(q−1)=M⋅Mkϕ(n)=M(Mϕ(n))kmodNC^dmodN = M^{ed}modN =M\\ C^dmodN = M^{ed}mod\\ ed=1mod\phi(n)\\ \phi(n)=(p-1)(q-1)\\ ed=1mod(p-1)(q-1)\\ ed=k(p-1)(q-1)+1\\ ed-1=k(p-1)(q-1)=k\phi(n)\\ M^{ed} = M^{ed+1-1} = M\cdot M^{ed-1}\\ =M\cdot M^{k(p-1)(q-1)} = M\cdot M^{k\phi(n)} = M(M^{\phi(n)})^kmodN\\

if M & N 서로소라면 𝑥ϕ(𝑛)≡1𝑚𝑜𝑑𝑛𝑥^{\phi(𝑛)}≡1𝑚𝑜𝑑𝑛

  • M⋅(1)kmodN=MM\cdot (1)^kmodN = M

서로소가 아니라면

  • (M(p−1)(q−1))k=(M(p−1))(q−1)k(M(q−1))(p−1)kmodq=1modq(M(p−1)(q−1))k=1modpq(M^{(p-1)(q-1)})^k=(M^{(p-1)})^{(q-1)k}\\ (M^{(q-1)})^{(p-1)k}modq=1modq\\ (M^{(p-1)(q-1)})^k=1modpq

다음과 같이 증명할 수 있습니다

RSA는 ϕN\phi N값이 유출된다면 공격당할 수 있습니다
그러나 Mathmetically difficult로 인해 알 수 없습니다

그리고 N이 p와 q로 소인수분해가 될 수 있는 경우 d는 e를 사용하여 쉽게 찾을 수 있습니다.

Icon made by Freepik from www.flaticon.com

profile
HyeonMin Kim
이전 포스트

[백준] #1874

다음 포스트

[암호학] ElGamal

0개의 댓글