Let's Failcrypt

Zadanie

Rozwiązanie

Zadanie sprowadza się do tego, że dla danych dwóch dużych liczb - sig i nonce (gdzie sig jest istotne większa od nonce) musimy znaleźć dowolne e i n dla których sig^e ≡ nonce (mod n). Jest to pierwsza, błędna wersja zadania. Błąd polegał na tym, że nie było ograniczenia na e, a dla e = 1 rozwiązanie jest trywialne:

sig ≡ nonce (mod n)
sig - nonce ≡ 0 (mod n)

więc n = sig - nonce.

Skrypt rozwiązujący zadanie (wchodzimy na strone, przeklejamy nonce, dostajemy certyfikat:

from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long

def get_signature_record(domain):
    from dnsknife import resolver
    ans = resolver.query(domain, 'TXT')
    txt = ans.response.answer[0][0].strings[0]
    return bytes_to_long(txt)

domain = "crypto.legit-service.ovh"
nonce = int(input("nonce: "), 16)
sig = get_signature_record(domain)

print(RSA.construct((sig - nonce, 1)).publickey().exportKey().decode())

Flaga: ecsc19{signature_is_not_the_same_as_authentication}