# 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 $\pi$ in $\bar{p} = kp \cdot \pi \cdot 2^{400}$ is publicly known, and only $kp$ is secret. Using an attack due to Coppersmith, we can factor $N$ given at least half of its bits.

So, the attack proceeds as follows:

1. Exhaustively generate all possible $kp$'s.
2. For each $kp$, construct $\bar{p}$, and break the loop if Coppersmith's attack succeeds in factoring $N$.
3. Using the factorization of $N$, decrypt the message and find the flag.

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

#!/usr/bin/env sage

pi = 0xCDE6FD1CF108066CC548DF9070E102C2C651B885F24F503AAFFE276FEB573110C1E4592A35890D7678AAEEE9F44800FC43F999D5D06B89FCB22E5335A9287BC6D75A3E91E53906D413163D5

kp = 0xFF000

e = 2**16 + 1

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 .........