Large e and Small d (Weiner)

June 13 2017

# # # #

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}


Recommended Reading

I Love Emilia

# # # #

Car 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

# # #

c = 2911901299590689319468053634625275622654003904978205739380623481723661641396883678700531176998074009090944130064383792213854734101182591054606781359574544120823690362905523398270489939706547990345246231530733316646360394579721797156381054207414615333776383945252214100458075195770993971636731892198913293107313263096802400950280001995889600269261084002962194522369348371580184194201319826916320073496756736378234176527727677896098180012125139057850531341929674855173384488699967535868594673470466436155672157436157446615623094626238560694456848398206751930925254978950059694877328019092454478343535457958785859310484

...