DiceCTF 2022 | baby-rsa

#diceCTF2022

from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes

def getAnnoyingPrime(nbits, e):
    while True:
        p = getPrime(nbits)
        if (p-1) % e**2 == 0:
            return p

nbits = 128
e = 17

p = getAnnoyingPrime(nbits, e)
q = getAnnoyingPrime(nbits, e)

flag = b"dice{???????????????????????}"

N = p * q
cipher = pow(bytes_to_long(flag), e, N)

print(f"N = {N}")
print(f"e = {e}")
print(f"cipher = {cipher}")

non-coprime exponent RSA の問題

は与えられていないが小さいのでcado-nfsで素因数分解する。まじか……

あとはnth-rootとかsage の素因数分解アルゴリズムにヒントを与える + nth_root とかで解く

N = 57996511214023134147551927572747727074259762800050285360155793732008227782157
e = 17
cipher = 19441066986971115501070184268860318480501957407683654861466353590162062492971

p = 337117592532677714973555912658569668821
q = 172036442175296373253148927105725488217
assert N == p*q

pari("addprimes({})".format(p))
ms = Zmod(N)(cipher).nth_root(e, all=True)

for m in ms:
    print(int(m).to_bytes(100, "big"))