Tags: wiener rsa
Rating:
# Baby hands (crypto 300)
###ENG
[PL](#pl-version)
We get some [data](intercepted.txt) 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](intercepted.txt) 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}`
