Let's Failcrypt 2

Zadanie

Zadanie takie samo, jak Let's Failcrypt, ale tym razem mamy ograniczenie e > 65537.

Rozwiązanie

Zrobimy coś podobnego jak w części 1, ale najpierw trzeba coś zauważyć. Z tw. Eulera, dla względnie pierwszych a i n mamy: (phi - Funkcja Eulera)

a^phi(n) ≡ 1 mod(n)
⇓
a^{phi(n) + 1} ≡ a (mod n) Z poprzedniego zadania wiemy, że sig ≡ nonce (mod sig - nonce). Po podstawieniu tego do pierwszego równania dla a = sig i n = sig - nonce mamy: sig^{phi(sig- nonce) + 1} ≡ sig ≡ nonce (mod sig - nonce)

Pozostaje wylosować takie nonce, żeby sig oraz sig - nonce były względnie pierwsze, ale okazuje się, że zwykle tak jest. Ostatnim problemem jest policzenie phi(sig - nonce), ale także tutaj raz na kilkanaście prób otrzymujemy liczbę z którą Sage sobie radzi. Kod rozwiązania (nie chciało mi się implementować timeoutów, więc trzeba odpalić kilka razy aż trafi na liczbę którą da radę sfaktoryzować, czasami też wywali się na tworzeniu certyfikatów, co można poprawić wywalając checka w bilbiotece od RSA. Ale po odpowiedniej liczbie prób tak czy inaczej zadziała):

#!/bin/python2
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long
from sage.all import euler_phi
import requests
import re

pattern = re.compile('Take this nonce: (.+) and sign with your RSA key.')

def __gcd(x, y):
   while(y):
       x, y = y, x % y
   return x


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)



def verify_signature(pubkey, signature, nonce):
    pubkey = RSA.importKey(pubkey)
    e, n = pubkey.e, pubkey.n

    # Don't allow weak keys
    if e < 65537:
        return False
    return pow(signature, e, n) == nonce


def verify(pubkey, domain, nonce):
    return verify_signature(pubkey, get_signature_record(domain), nonce)

def get_nonce_session():
	r = requests.get('https://failcrypt2.ecsc19.hack.cert.pl/')
	nonce = int(re.search(pattern, r.text).group(1) , 16)
	session = r.cookies['session']
	return [nonce, session]

domain = "crypto.legit-service.ovh"
sig = 69652904871897821472183980483739811079341753893561761327070812091923231785899489652896157669669507587458401009228978259408204706276670753919975140850280030223767922199087641241921416001554872048271328614288968166632445276064459059733006891002904038810054234972139730618071021672122606450686569981612121078067


while True:
	s = get_nonce_session()
	nonce = s[0]
	print("Nonce: {}".format(nonce))
	gcd = __gcd(sig, sig - nonce)
	print("GCD: {}".format(gcd))
	if(gcd > 1):
		continue
	print("Calculating phi of {}".format(sig- nonce))
	phi = euler_phi(sig - nonce)
	print("Result: e {} n {}".format(phi + 1, sig - nonce))
	print("Cookie: {}".format(s[1]))
	if(pow(sig, phi + 1, sig - nonce) == nonce):
		print("Result verifired")
	else:
		print("Result wrong O_o")
		continue
	cert = RSA.construct((sig - nonce, phi + 1)).publickey().exportKey().decode()
	print(cert)



print("Solution: {}".format(x))

print("Cert: ")
print(cert)

Następnie wystarczy przekleić ciasteczko oraz certyfikat na stronę i otrzymujemy flagę: ecsc19{crypto-challenges-are-hard-without-unintended-solutions}