Tags: wiener rsa
Rating:
# MPRSA (crypto)
## ENG
[PL](#pl-version)
In the task we get [RSA public key components](public.txt), [encrypted flag](data.enc) and [source code](mprsa.py) used for encryption.
The code contains a classic multiprime RSA implementation, with an interesting key generation code:
```python
def key_gen(self, bits, prime_numbers=4):
delta = randint(5, 15)
bit_prime = int(bits // prime_numbers)
P = [next_prime(number.getPrime(bit_prime) + 1)]
for i in range(1, prime_numbers):
P.append(next_prime(P[i - 1] * delta))
n = self.__compute_module(P)
phi = self.__compute_phi(P)
for d_next in count(int(pow(P[0] // 2, 0.5)), -1):
g, e, __ = gcdext(d_next, phi)
if (1 < e < n) and (g == 1) and (gcd(phi, e) == 1):
d = d_next
break
self.public_key = (e, n)
self.secret_key = (d, n)
```
The initiall issue we noticed with this code, is that modulus `n` is composed of strongly non-random primes, since `.next_prime` is deterministic and `delta` multiplier is very small.
We've seen some writeups for this task which attacked this vector.
Nevertheless, we have a bit of experience already with attacks on RSA and we've noticed one other interesting fact here:
```python
for d_next in count(int(pow(P[0] // 2, 0.5)), -1):
```
Private key exponents starts from `sqrt(p1/2)` and we know that p1 is the smallest of the primes in `n` and they are of similar size, therefore `p1` is smaller than `n^(1/4)`.
And we know that if `d < 1/3 n^(1/4)` then we can use Wiener's attack to recover the private exponent.
It's clear that we are lucky and we can recover the key with a bit of sage:
```python
e = 2968282037100353640375137899109790499983904510372252123726372200136866453960017151334469454219618530252326391316368089337062513360207381202191915473462935477137523455963250056561696664667826520897145326882242932509636924316993816382503962649302107865422204292490659961123103322081852240437978613121365781016988448211321349469941008479597808471102164820173139919110860676464533506147455712945961147297193425603466185665772219928497258618754492859488589873906043003885893571962433509510568617898956135134801893952671289895841202079907023382879176353447845431980339763701845065932967492613174149948295178658632744337984598033199716909609691917091599333032421515584590767434316739374277008976624091929263313294017958203501962609986428734553144207841375915976037349385525685765751825435583700725710652618107250634373424713513298201017768173878869803169781015337283490319756398578109078482368725206020186761161884650413182297877151106135232838271785994275915310662858329477083914589917431343036266926436535406078268574331773960697696088892795445640924833807153106889785640164637689271399503064510417142492169690916011945805675154490404590528925067599406358567902459063109040410209462273031696409389388590120586013927889551821936657759836121166591
n = 7514486184413883943206134802309178399244378977612173666918494750761691891054947551148635071227769468578429057411933207521812645312852372491525360936618326543031520002708891330196401800722400435500157085990690437665009726219084442021182850506847121543952655588437818213790488615953323918596261471907835421407596459273791581399309405067626383928217548743866594178747621345881632069955681378662964970779524097614470204109881600043967504127490912520547758072473768719527077924134830122844355992675524808082077564650441063165395654489609498673176326527753016138066814814395200582603579511246113422000711435941608107654792503944786693356696589418688102700165482722623897706829970814110646089600275631212777003792683291735426294012686607809533096193939103941428766195023630255837719510277444701463006437791991196936648896229397094403915485049521731674097516242423233615004601202795680477677383876821794953563585797462940468885019612996080647173400509657498552114237186425176692867162493697752241051962151120715653607272964311445754089586884116532125369172407750688737448422035240971409748803419916890500367552066268915926436633178471526464741419410486387714614840372951024874043659727111073041432865136565615528171567027369016567760790667844170057
c_fracs = continued_fraction(e/n).convergents()
test_message = 42
test_message_encrypted = pow(test_message,e,n)
d = 0
for i in xrange(len(c_fracs)):
if pow(test_message_encrypted,c_fracs[i].denom(),n) == test_message:
d = c_fracs[i].denom()
break
print(d)
```
And with `d` we can simply decode the flag:
```python
from crypto_commons.generic import long_to_bytes
def main():
n = 7514486184413883943206134802309178399244378977612173666918494750761691891054947551148635071227769468578429057411933207521812645312852372491525360936618326543031520002708891330196401800722400435500157085990690437665009726219084442021182850506847121543952655588437818213790488615953323918596261471907835421407596459273791581399309405067626383928217548743866594178747621345881632069955681378662964970779524097614470204109881600043967504127490912520547758072473768719527077924134830122844355992675524808082077564650441063165395654489609498673176326527753016138066814814395200582603579511246113422000711435941608107654792503944786693356696589418688102700165482722623897706829970814110646089600275631212777003792683291735426294012686607809533096193939103941428766195023630255837719510277444701463006437791991196936648896229397094403915485049521731674097516242423233615004601202795680477677383876821794953563585797462940468885019612996080647173400509657498552114237186425176692867162493697752241051962151120715653607272964311445754089586884116532125369172407750688737448422035240971409748803419916890500367552066268915926436633178471526464741419410486387714614840372951024874043659727111073041432865136565615528171567027369016567760790667844170057
d = 9427062506559859200764441560060897853452091503537282553799991491531587159716894888858396729480853980609608783434755632459538177527336880678476984732352511
ct = 4990981759460304744105598767593686181405870005282225829795794541021226151966053079510943795109726609634828370167775307839662644021918767556530119412853816585221569546843939870445288438295880322602517246037112564416212745954141726471664361647045729235670622890953655065235230427298013906810014221648290750692583336186843003229107021202513937560627163229698907224982160099413064560450430189221548918249561722797270239205285019947483419790983776163671611001827036804081081707549809205146146016914228431689911951835061650007130105435596899572248580145216361550470379538250892374083206633208114199207657470199269462010122511529769658733474277302308656490658251694852119519651331026206905848184310474442594518003923697214854504891077728222935182875777284193900483103844390422979429620136337089544700764854729601666550485708645758202313582038929079609869996469534041940940326632417337431671554125949585769777514656385405640728690453834779703498214246941789126527089991023766694976273980553865664242840580534044580685023115108182135139502041838131616984809782973256326815445038141870218251128685050551152554710812132312358766591390023888015234480632150114384947814031965110524912964541892010650475016456100706107619225121444952046171313017830946278
print(long_to_bytes(pow(ct, d, n)))
main()
```
And we get:
```
Mr.D (12:10):
Okey, see you later ;)
Mr.D (19:30):
So can you help me?
Anonymous (19:31):
Yeah, we will have 10,000 falsified voters. Transfer 100000$ to my bank account: ctfzone{3177809746931830}
```
## PL version
W zadaniu dostajemy [klucz publiczny RSA](public.txt), [zaszyfrowaną flagę](data.enc) oraz [kod szyfrowania](mprsa.py) wykorzystany do szyfrowania danych.
Kod zawira klasyczną implementacje RSA opartego o wiele liczb pierwszych, z dość ciekawą logiką generacji klucza:
```python
def key_gen(self, bits, prime_numbers=4):
delta = randint(5, 15)
bit_prime = int(bits // prime_numbers)
P = [next_prime(number.getPrime(bit_prime) + 1)]
for i in range(1, prime_numbers):
P.append(next_prime(P[i - 1] * delta))
n = self.__compute_module(P)
phi = self.__compute_phi(P)
for d_next in count(int(pow(P[0] // 2, 0.5)), -1):
g, e, __ = gcdext(d_next, phi)
if (1 < e < n) and (g == 1) and (gcd(phi, e) == 1):
d = d_next
break
self.public_key = (e, n)
self.secret_key = (d, n)
```
Pierwszą podatnością, którą zauważyliśmy w tym kodzie był sposób wyliczania modulusa `n`, który składa się z mocno nie-losowych liczb pierwszych, bo `.next_prime` jest deterministyczne a `delta` jest dość niewielka.
Widzieliśmy writeupy które atakowały zadanie zgodnie z tym wektorem.
Niemniej mamy już trochę doświadczenia z atakami na RSA i zauważyliśmy inną ciekawostkę w kodzie:
```python
for d_next in count(int(pow(P[0] // 2, 0.5)), -1):
```
Prywatny wykładnik szyfrujący zaczyna się od `sqrt(p1/2)` a wiemy że p1 jest najmniejszym czynnikiem pierwszym w `n` i że czynniki są zbliżonego rozmiaru, więc `p1` musi być mniejsze od `n^(1/4)`.
Wiemy też że jeśli `d < 1/3 n^(1/4)` to możemy użyć ataku Wienera aby odzyskać prywatny wykładnik szyfrujący.
Jak widać mamy szczęście i możemy użyc prostego skryptu sage:
```python
e = 2968282037100353640375137899109790499983904510372252123726372200136866453960017151334469454219618530252326391316368089337062513360207381202191915473462935477137523455963250056561696664667826520897145326882242932509636924316993816382503962649302107865422204292490659961123103322081852240437978613121365781016988448211321349469941008479597808471102164820173139919110860676464533506147455712945961147297193425603466185665772219928497258618754492859488589873906043003885893571962433509510568617898956135134801893952671289895841202079907023382879176353447845431980339763701845065932967492613174149948295178658632744337984598033199716909609691917091599333032421515584590767434316739374277008976624091929263313294017958203501962609986428734553144207841375915976037349385525685765751825435583700725710652618107250634373424713513298201017768173878869803169781015337283490319756398578109078482368725206020186761161884650413182297877151106135232838271785994275915310662858329477083914589917431343036266926436535406078268574331773960697696088892795445640924833807153106889785640164637689271399503064510417142492169690916011945805675154490404590528925067599406358567902459063109040410209462273031696409389388590120586013927889551821936657759836121166591
n = 7514486184413883943206134802309178399244378977612173666918494750761691891054947551148635071227769468578429057411933207521812645312852372491525360936618326543031520002708891330196401800722400435500157085990690437665009726219084442021182850506847121543952655588437818213790488615953323918596261471907835421407596459273791581399309405067626383928217548743866594178747621345881632069955681378662964970779524097614470204109881600043967504127490912520547758072473768719527077924134830122844355992675524808082077564650441063165395654489609498673176326527753016138066814814395200582603579511246113422000711435941608107654792503944786693356696589418688102700165482722623897706829970814110646089600275631212777003792683291735426294012686607809533096193939103941428766195023630255837719510277444701463006437791991196936648896229397094403915485049521731674097516242423233615004601202795680477677383876821794953563585797462940468885019612996080647173400509657498552114237186425176692867162493697752241051962151120715653607272964311445754089586884116532125369172407750688737448422035240971409748803419916890500367552066268915926436633178471526464741419410486387714614840372951024874043659727111073041432865136565615528171567027369016567760790667844170057
c_fracs = continued_fraction(e/n).convergents()
test_message = 42
test_message_encrypted = pow(test_message,e,n)
d = 0
for i in xrange(len(c_fracs)):
if pow(test_message_encrypted,c_fracs[i].denom(),n) == test_message:
d = c_fracs[i].denom()
break
print(d)
```
I teraz mając już `d` możemy odszyfrować dane:
```python
from crypto_commons.generic import long_to_bytes
def main():
n = 7514486184413883943206134802309178399244378977612173666918494750761691891054947551148635071227769468578429057411933207521812645312852372491525360936618326543031520002708891330196401800722400435500157085990690437665009726219084442021182850506847121543952655588437818213790488615953323918596261471907835421407596459273791581399309405067626383928217548743866594178747621345881632069955681378662964970779524097614470204109881600043967504127490912520547758072473768719527077924134830122844355992675524808082077564650441063165395654489609498673176326527753016138066814814395200582603579511246113422000711435941608107654792503944786693356696589418688102700165482722623897706829970814110646089600275631212777003792683291735426294012686607809533096193939103941428766195023630255837719510277444701463006437791991196936648896229397094403915485049521731674097516242423233615004601202795680477677383876821794953563585797462940468885019612996080647173400509657498552114237186425176692867162493697752241051962151120715653607272964311445754089586884116532125369172407750688737448422035240971409748803419916890500367552066268915926436633178471526464741419410486387714614840372951024874043659727111073041432865136565615528171567027369016567760790667844170057
d = 9427062506559859200764441560060897853452091503537282553799991491531587159716894888858396729480853980609608783434755632459538177527336880678476984732352511
ct = 4990981759460304744105598767593686181405870005282225829795794541021226151966053079510943795109726609634828370167775307839662644021918767556530119412853816585221569546843939870445288438295880322602517246037112564416212745954141726471664361647045729235670622890953655065235230427298013906810014221648290750692583336186843003229107021202513937560627163229698907224982160099413064560450430189221548918249561722797270239205285019947483419790983776163671611001827036804081081707549809205146146016914228431689911951835061650007130105435596899572248580145216361550470379538250892374083206633208114199207657470199269462010122511529769658733474277302308656490658251694852119519651331026206905848184310474442594518003923697214854504891077728222935182875777284193900483103844390422979429620136337089544700764854729601666550485708645758202313582038929079609869996469534041940940326632417337431671554125949585769777514656385405640728690453834779703498214246941789126527089991023766694976273980553865664242840580534044580685023115108182135139502041838131616984809782973256326815445038141870218251128685050551152554710812132312358766591390023888015234480632150114384947814031965110524912964541892010650475016456100706107619225121444952046171313017830946278
print(long_to_bytes(pow(ct, d, n)))
main()
```
I dostajemy:
```
Mr.D (12:10):
Okey, see you later ;)
Mr.D (19:30):
So can you help me?
Anonymous (19:31):
Yeah, we will have 10,000 falsified voters. Transfer 100000$ to my bank account: ctfzone{3177809746931830}
```
