[Dreamhack] safeprime

풀이

from Crypto.Util.number import getPrime, isPrime, bytes_to_long
from flag import FLAG

def getSafePrime(n):
    while True:
        p1 = getPrime(n)
        p1 = 122925338396977892377812264658939951801210314312238212067059595148447406166769716855936119104014353481162826500622396956338370238037713303129667973570418205129792800094492802512333202767609745542480301632710243676880179931490273979269048908687034938065216226244568368994455058377505090061149006930577060428653
        p2 = 2*p1 + 1
        if isPrime(p2):
            return p1, p2

while True:
    p1, p2 = getSafePrime(1024)
    q1 = getPrime(1024)
    q2 = getPrime(1024)
    e = 0x10001
    if (p1 - 1) * (q1 - 1) % e == 0:
        continue
    if (p2 - 1) * (q2 - 1) % e == 0:
        continue
    N1 = p1 * q1
    N2 = p2 * q2
    break

FLAG1 = bytes_to_long(FLAG[ : len(FLAG)//2])
FLAG2 = bytes_to_long(FLAG[len(FLAG)//2 : ])

# RSA encryption 1
FLAG1_enc = pow(FLAG1, e, N1)
print(f"{N1 = }")
print(f"{e = }")
print(f"{FLAG1_enc = }")

#RSA encryption 2
FLAG2_enc = pow(FLAG2, e, N2)
print(f"{N2 = }")
print(f"{e = }")
print(f"{FLAG2_enc = }")

주어진 문제코드를 살펴보면 특이하게 p1과  p2 = 2*p1+1이라는 것이 주어져있다. (p1이 주어진게 맞는건가..?) 그 외에는 RSA의 방식으로 flag를 암호화를 하고 있는 것을 볼 수 있다. 

그러면 그냥 p1과 p2를 구해서 복호화를 진행해주면 된다. 제공된 output.txt의 정보를 불러와 복호화하는 코드를 작성하였다. 

exec(open('./safeprime/output.txt', 'r').read()) # N1, N2, e, FLAG1_enc, FLAG2_enc 불러옴

p1 = 122925338396977892377812264658939951801210314312238212067059595148447406166769716855936119104014353481162826500622396956338370238037713303129667973570418205129792800094492802512333202767609745542480301632710243676880179931490273979269048908687034938065216226244568368994455058377505090061149006930577060428653

from Crypto.Util.number import *

p2 = 2*p1+1
q2 = N2 // p2

q1 = N1 // p1

if p2*q2 == N2 and p1*q1 == N1 :
    print("Correct") #p1,p2,q1,q2가 제대로 구해졌는지 확인

phi1 = (p1-1)*(q1-1)
d1 = inverse(e, phi1) # 개인키 획득

phi2 = (p2-1)*(q2-1)
d2 = inverse(e, phi2) # 개인키 획득

FLAG1 = long_to_bytes(pow(FLAG1_enc, d1, N1)) #복호화 후 byte 변환
FLAG2 = long_to_bytes(pow(FLAG2_enc, d2, N2))
print(FLAG1+FLAG2)

 

해당 코드를 실행해보면 아래와 같이 flag를 얻을 수 있다.