[Cryptohack] RSA (Ron was Wrong, Whit is Right)

Ron was Wrong, Whit is Right

문제 및 설명

여기 RSA 공개 키 묶음이 있습니다. 인터넷에 접속한 사람들로부터 그들이 보낸 메시지와 함께 수집되었습니다. excerpt.py 에서 볼 수 있듯이, 모든 사람이 PKCS#1 OAEP를 사용하여 자신의 메시지를 암호화했습니다. 암호 해독이 가능해서는 안 되지만, 일부 키에 문제가 있는 것은 아닐까요?

풀이

from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA


msg = "???"

with open('21.pem') as f:
    key = RSA.importKey(f.read())

cipher = PKCS1_OAEP.new(key)
ciphertext = cipher.encrypt(msg)

with open('21.ciphertext', 'w') as f:
    f.write(ciphertext.hex())

문제에서 제공한 키와 암호문

먼저 21번째의 키를 읽고 이를 공개키표준으로 암호화시켜 21번째의 암호문을 내놓는걸 보여준다.

링크

문제에서 제공한 글에선 RSA에 대한 취약점을 말해준다.

그건 키들마다 공통된 약수가 존재하는데, 

예를 들어 A의 키값이 269107 = 439 x 613,

B의 키값은 440747 = 719 x 613을 가지고 있다고 할때,

이 두키의 최대 공약수는 613이고, 다른 키들 중 이를 나누어 다른 인수를 구할 수 있다.

 

그럼 이번문제는

두 키가 하나의 인수에 대해 가지고 있으면,

p와 q를 알 수 있는 50개의 키값 중 같은 최대 공약수 1이 아닌 수가 있는지 확인 후,  

다른 RSA문제 처럼 오일러의 피함수로 개인 인수를 계산하여 메시지를 복호화 할 수 있\다.

 

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from math import gcd

n=[]
c=[]
e=[]

for i in range(1, 51):
    key = RSA.importKey(open(f"keys_and_messages\{i}.pem", 'r').read())
    cipher = open(f"keys_and_messages\{i}.ciphertext", 'r').read()
    n.append(key.n)
    c.append(cipher)
    e.append(key.e)

N = 0
for i in range(len(n)):
    for j in range(i,len(n)):
        gcd_between = gcd(n[i], n[j])
        if gcd_between != 1 and n[i]!=n[j]:
            print(i)
            print(j)
            N =gcd_between
            p_find = i

21번째(문제에서 사용한 코드 번호)와 34번째가 같은 인수가 나온 걸 볼 수 있다.

그래서 21번째 N의 값에 플래그값이 있으므로,

p는 최대공약수 값, q는 최대공약수를 나눈 값으로 잡고, 

오일러의 피함수의 공식인 (p-1)*(q-1)값을 만들고,

비밀 인수 d를 만들고

공개키 암호화로 키를 만든 후 이를 복호화 시켰다.

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Util.number import *
from math import gcd

n=[]
c=[]
e=[]

for i in range(1, 51):
    key = RSA.importKey(open(f"keys_and_messages\{i}.pem", 'r').read())
    cipher = open(f"keys_and_messages\{i}.ciphertext", 'r').read()
    n.append(key.n)
    c.append(cipher)
    e.append(key.e)

N = 0
for i in range(len(n)):
    for j in range(i,len(n)):
        gcd_between = gcd(n[i], n[j])
        if gcd_between != 1 and n[i]!=n[j]:
            #print(i+1)
            #print(j+1)
            N =gcd_between
            p_find = i

ciphertext=bytes.fromhex(c[p_find])
e=e[p_find]
p=N
q=n[p_find]//N
euler=(p-1)*(q-1)
d=inverse(e, euler)

key= RSA.construct((n[p_find], e, d))
cipher = PKCS1_OAEP.new(key)
plaintext = cipher.decrypt(ciphertext)
print(plaintext)

crypto{3ucl1d_w0uld_b3_pr0ud} If you haven't already, check out https://eprint.iacr.org/2012/064.pdf로 나왔고, 

플래그 값은 crypto{3ucl1d_w0uld_b3_pr0ud}이다.

플래그 값으로 나온 사이트를 한번 참고 하는것도 좋을 것 같다.