c = 49938873005546615435687311504872509785022284769848698526216639826561007249140360312632267256915204926681345807364733487154803200306964789424438457669341375204871001335059277860364152540205309441986059468568646721718475252818788849738581432943901958543446753508706429359356503196241596325655490713282416769960
n = 142269281344535869088742736116943280058390173908199123033731860167637256284058438570026290267171503564593144579038791106258246936460019066646984380347557856973633574180883795126232851811359705463053986537018379016661776217821802817244947657640746566344862496416333791072979037570103637215724467194819497299907
e = 141211410131186565836904979237284528246734880966191156417995210689827710794052151990500502219902268625710499228242391963419318931769810679560221659007691633465075476338925509588659989483348207094645823751037728970137889820529978911004235927900663723568956034787737608209610740379437975880462460234131696007491
Find the flag.
Solution
The RSA parameter e
can be chosen at will, however there are some values of
e
for which the resulting d
will become very small. In the above example,
for instance, the e
is comparable to the size of n
.
For a choice of parameters as this, the RSA has been broken, and in particular,
this attack for a large e
which results in a computably small d
is called
as Weiner's attack.
This procedure works out by trying the Euler totient function via a continued fraction approximation of e / N.
How this works exactly, I don't really know.
The implementation part, however is as follows.
Copied shamelessly from 15 ways to break RSA security - Renaud Lifchitz
for f in continued_fraction(e/n).convergents():
k, d = f.numerator(), f.denominator()
if k:
psi2 = int((e * d - 1) / k)
a, b, c = 1, -(n - psi2 + 1), n
delta = b * b - 4 * a * c
if is_square(delta):
p, q = (-b - sqrt(delta)) / 2 * a, (-b + sqrt(delta)) / 2 * a
print(p, q)
This gives us p
and q
.
On breaking RSA as usual, gives us a small d
= 4669523849932130508876392554713407521319117239637943224980015676156491
It also gives us the flag.
print(bytes.fromhex(hex(pow(c, d, n))[2:]))
b'flag{overlarge_numbers_might_reveal_large_flaws}'
Flag
flag{overlarge_numbers_might_reveal_large_flaws}
I Love Emilia
#Emilia #ctf #misc #webCar Brand is a nice person. He wants to declare his love to his girl. Unfortunately, another trash girl also likes him. In order to announce to the trash girl about his feelings, he decides to put his confession into irrefutable words, and send it...
...Recommended Reading
Royal Primes
#ctf #misc #rsac = 2911901299590689319468053634625275622654003904978205739380623481723661641396883678700531176998074009090944130064383792213854734101182591054606781359574544120823690362905523398270489939706547990345246231530733316646360394579721797156381054207414615333776383945252214100458075195770993971636731892198913293107313263096802400950280001995889600269261084002962194522369348371580184194201319826916320073496756736378234176527727677896098180012125139057850531341929674855173384488699967535868594673470466436155672157436157446615623094626238560694456848398206751930925254978950059694877328019092454478343535457958785859310484
...