Bad RSA Keygen (150 pts)

Question:

High-speed RSA Keygen! See this file.

Note: Plaintext has the format The flag is ...............flag......

Write-Up:

The RSA keygen is vulnerable due to the fact that the entropy of its 624 most significant bits is very low. In fact, these bits have only 12 bits of entropy! This is because the value in is publicly known, and only is secret. Using an attack due to Coppersmith, we can factor given at least half of its bits.

So, the attack proceeds as follows:

  1. Exhaustively generate all possible 's.
  2. For each , construct , and break the loop if Coppersmith's attack succeeds in factoring .
  3. Using the factorization of , decrypt the message and find the flag.

The following Sage code shows how to implement the above attack:

#!/usr/bin/env sage

N = 0xA4E20DDB854955794E7ABF4AE40051C0FC30488C82AB93B7DD046C1CC094A54334C97E84B523BD3F79331EBEAF5249200D729A483D5B8D944D58DF18D2CA9401B1A1A6CDA8A3AC5C234A501794B76886C426FAC35AD9615ADAB5C94B58C03CCFFA891CE0156CBC14255F019617E40DE9124FBBE70D64CD823DCA870FF76B649320927628250D47DB8DFA9BBCE9964CB3FE3D1B69845BD6FA2E6938DDA1F109E5F4E4170C845B976BBD5121107642FC00606208F9BC83322532739BCFEAF706FB2AF985EBD9769C7FBD50ECBF55566BD44FB241F9FD2DE25069AA8C744F0558514F1E9C8E4297A4D4B25D9F2B7494B466C2E6E2834BA68C5C824215018368B4FB

pi = 0xCDE6FD1CF108066CC548DF9070E102C2C651B885F24F503AAFFE276FEB573110C1E4592A35890D7678AAEEE9F44800FC43F999D5D06B89FCB22E5335A9287BC6D75A3E91E53906D413163D5

kp = 0xFF000

e = 2**16 + 1

c = 0x64A3F710E3CB9B114FD112B45AC4845292D0B1FEE1468147E80FABA3CD56B1206F5C59E5D400A7F20C9BCD5B42C7197A0D07FBBA48BFBDA550C5CAFB562BEC1B1CB301D131E13233F2BD1C80EEB48956FF0BC8DB6AE2CD727FB1DAC62822331B15A6044F825D01D81036DA3CC8A3575165E813051036715CDF5F7865676DC2513AAD08C5113DFFDC4E6B13E6FFCA2FAD1AA6986D3ED9F1896C109F641074DA7DBFE62CCAD3CACE4B80332475FE3C9EC4869FCA31EE2860D45959F8583C2AEC7A00FC2FD63DBF6CBEB1C604D60CF780FE028ED0AD65DC74BC5335F96EE7CEDEA292F76B427E5F402BCC609B39302CD4A51F405C6ACF8B8A7569AAD9A9318F060B

R.<x> = PolynomialRing(Zmod(N), implementation='NTL')

for i in range(0, 2**12):
    pbar = (kp + i) * pi * 2**400

    f = x - pbar
    SR = f.small_roots(X=2^500, beta=0.4)

    if len(SR) > 0:
        break

p = int(pbar - SR[0])
q = N // p

d = inverse_mod(e, (p-1)*(q-1))

m = c.powermod(d, N)

import binascii
print binascii.unhexlify(hex(m))

The output is:

The flag is ................................................ e7531f1bb9c95c19e823065d3e6a86b6 .........

Source Code

Bad_RSA_Coppersmith.sage.