Security/암호학(Cryptography)

[CryptoHack] RSA Starter 4

그믐​ 2023. 6. 2. 20:50
반응형

 

설명

개인 키 d는 해당 공개 키로 생성된 암호문을 해독하는데 사용된다. (메시지를 "서명"하는데도 사용되지만 이는 나중에 설명할 것이다.)

 

개인 키는 암호화 기능을 빠르게 반전시킬 수 있는 "트랩도어"이다. RSA 가 잘 구현되어 있고 개인 키가 없을 때, 암호문을 해독하는 갖아 빠른 방법은 모듈러를 분해하는 것이다.

 

두 개의 소수가 주어진다. :

p = 857504083339712752489993810777

q = 1029224947942998075080348647219

 

그리고 지수:

e = 65537

 

개인 키 d는 무엇인가?

 

풀이

RSA에서 $d$는 $\phi(N)$에 대한 $e$의 역원이다.

$\therefore d = e^{-1} \bmod \phi(N)$ 이에 대해서는 RSA 원리를 찾아보면 많이 나온다 

 

이전에 페르마의 소정리(FLT)를 공부할 때 오일러 정리에 대해서도 본 적이 있다.

오일러 정리는 다음과 같다.

 

정수 $a$ 및 양의 정수 $N$이 주어져있고 $a, N$이 서로소이면,

$a^{\phi(N)} \equiv 1 \pmod N$ 이 성립한다.

 

공개키로 암호화된 상태는 평문 $m$에 대한 암호문 $c$는 $c = m^e \bmod N$이다. 이를 복호화하기 위해 d제곱한다.

$m^{de}$ $d = e^{-1}$이므로 $de \equiv 1 \bmod \phi N$이다.

오일러 정리에 의해 $m^{ de} = m^{\phi(N) + 1} = m^{\phi(N)} * m^1 \equiv m \bmod N$ 이 성립한다.

 

뭐 암튼..

 

d 를 구해보자.

 

p = 857504083339712752489993810777
q = 1029224947942998075080348647219

e = 65537
phi = (p-1) * (q-1)

def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        gcd, x, y = extended_gcd(b % a, a)
        return gcd, y - (b // a) * x, x
print(extended_gcd(e, phi)[1])

# print(pow(e, -1, phi))​

 

역원을 구하기 위해 extended GCD를 써도 되고.  pow 함수를 써도 된다.

 

p = 857504083339712752489993810777
q = 1029224947942998075080348647219
e = 65537
phi = (p-1) * (q-1)

print(xgcd(e, phi)[1])

최근 sage 사용법도 익히는 겸 sage로도 풀어보았다.

sage에서 extended gcd 를 사용하려면 xgcd를 사용한다.

반응형