Baby hands (crypto 300)

###ENG PL

We get some data with many triplets denoted as (d,c,n). Our first idea was to check if maybe a pair of moduli share the same prime, but we found nothing. It was a bit confusing because there are not that many attacks which require many payloads.

And we were right - this one didn't. It needed only one payload, and each one gave the flag.

If we look at those payloads we can see that d is very very large, which actually suggest that the corresponding exponent e might be rather small. There is an efficient attack agains large public exponent - Wiener attack, and it is exactly what we were supposed to do.

So we simply run:

# sage

n = 162375468556255342840184380017752307049575955143811124651668179546999144455415632265862602514386409412258772643790637233144774447636694664087397175482938958661142022166864007317692608104513835959387316735889741416403005613839667775733147723497537341613995375357897642024075069112712472560335406551536669543677
e = 64193765095472280945778947695026260940793161700792092928929371930940586875921621250436677664062645637750266086941620369817913432656342447118119648040487568561166129534408858429501807430550886328164336961068507005046531729954378900389289038547121166749974617776234380115780563231906876010653549490718147637109
c = 161368580245997137625438248139098888389801359838792140099794084052829279383422322670122662786704858201672541232233171127388341066584896672407182421832728901923771676356720611937864219195771372253188974650818854505110963737925290199983571032857746780899310446337006151661497839040062867489758146326490061720009

c_fracs = continued_fraction(e / n).convergents()
test_message = 42
test_message_encryted = pow(test_message, e, n)
for i in xrange(len(c_fracs)):
    if pow(test_message_encryted, c_fracs[i].denom(), n) == test_message:
        d = c_fracs[i].denom()
        break
flag = pow(c, d, n)
print(flag)

And got flag{G3t_1t?_1t_h4s_4_sm4ll_d}

###PL version

Dostajemy dane z wieloma trójkami oznaczonymi jako (d,c,n). Pierwszy pomysł to sprawdzenie czy nie ma pary modulusów dzielących ten sam czynnik pierwszy, ale nic z tego. Było to trochę mylące, bo niewiele jest ataków które wymagają wielu wiadomości i kluczy.

I mieliśmy rację - ten atak wcale ich nie wymagał. Wymagał tylko jednej trójki i każda trójka dawała flagę.

Jeśli popatrzymy dokładnie na dane zauważymy że d jest bardzo bardzo duże, co sugeruje, że odpowiadający mu wykładnik e może być dość mały. Istnieje efektywny atak dla dużego wykładnika publicznego - atak Wienera i było to dokładnie to czego użyliśmy:

Uruchomiliśmy:

# sage

n = 162375468556255342840184380017752307049575955143811124651668179546999144455415632265862602514386409412258772643790637233144774447636694664087397175482938958661142022166864007317692608104513835959387316735889741416403005613839667775733147723497537341613995375357897642024075069112712472560335406551536669543677
e = 64193765095472280945778947695026260940793161700792092928929371930940586875921621250436677664062645637750266086941620369817913432656342447118119648040487568561166129534408858429501807430550886328164336961068507005046531729954378900389289038547121166749974617776234380115780563231906876010653549490718147637109
c = 161368580245997137625438248139098888389801359838792140099794084052829279383422322670122662786704858201672541232233171127388341066584896672407182421832728901923771676356720611937864219195771372253188974650818854505110963737925290199983571032857746780899310446337006151661497839040062867489758146326490061720009

c_fracs = continued_fraction(e / n).convergents()
test_message = 42
test_message_encryted = pow(test_message, e, n)
for i in xrange(len(c_fracs)):
    if pow(test_message_encryted, c_fracs[i].denom(), n) == test_message:
        d = c_fracs[i].denom()
        break
flag = pow(c, d, n)
print(flag)

I dostaliśmy flag{G3t_1t?_1t_h4s_4_sm4ll_d}