[CryptoHack] Crossed Wires

친구들에게 flag를 암호화해달라고 했다고 한다. 문제 코드를 보자.

from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long, inverse
import math
from gmpy2 import next_prime

FLAG = b"crypto{????????????????????????????????????????????????}"

p = getPrime(1024)
q = getPrime(1024)
N = p*q
phi = (p-1)*(q-1)
e = 0x10001
d = inverse(e, phi)

my_key = (N, d)

friends = 5
friend_keys = [(N, getPrime(17)) for _ in range(friends)]

cipher = bytes_to_long(FLAG)

for key in friend_keys:
    cipher = pow(cipher, key[1], key[0])

print(f"My private key: {my_key}")
print(f"My Friend's public keys: {friend_keys}")
print(f"Encrypted flag: {cipher}")

 

나는 e를 0x10001로 하여 키 N과 d를 얻어냈고, 친구 다섯명에게도 N과 e를 주는데 e를 17bit의 랜덤한 소수로 하였다.

output은 위와 같았다.

이번 문제의 취약점은 d를 알려줬기에 생기게 된다.

위 사이트를 참고하면 알 수 있듯이, d를 알고 있는 상태에서는 N을 인수분해하는 것이 가능해진다.

위의 사이트를 참고해서 인수분해하는 코드를 짜줬다.

def factorize(N, e, d):
    k = d*e - 1
    t = k
    while t % 2 == 0:
        t //= 2

    g = 2
    while True:
        x = pow(g, t, N)
        if x > 1:
            y = gcd(x - 1, N)
            if y > 1:
                return y, N//y
        g = gmpy2.next_prime(g)

 

실제로 잘 수행하는 것을 확인했다.

이렇게 p, q를 얻었으니 phi(N)을 구해서 friends의 e에 대한 d를 구할 수 있다.

그리고 주어진 것과 역순으로 복호화를 진행하면 마지막에 평문을 얻을 수 있다.

전체 코드는 다음과 같다.

from math import gcd
from gmpy2 import *
from Crypto.Util.number import *

def factorize(N, e, d):
    k = d*e - 1
    t = k
    while t % 2 == 0:
        t //= 2

    g = 2
    while True:
        x = pow(g, t, N)
        if x > 1:
            y = gcd(x - 1, N)
            if y > 1:
                return y, N//y
        g = gmpy2.next_prime(g)


N=21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771
d=2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097

friend_e=[106979, 108533, 69557, 97117, 103231]

ct=20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117

e=0x10001
p,q=factorize(N,e,d)
phiN=(p-1) * (q-1)
friend_d=[pow(_e,-1,phiN) for _e in friend_e]

for _d in friend_d[::-1]:
    ct=pow(ct,_d,N)

print(long_to_bytes(ct))

 

성공!

🚩 crypto{3ncrypt_y0ur_s3cr3t_w1th_y0ur_fr1end5_publ1c_k3y}’