# BkPctf 2015 - Bowdoin Writeup

03 March 2015 by nwert

We were provided with two files: found_rain.pdf and flag.encrypted. The contents of the PDF were a picture of a RSA private key, only that some parts were blanked out. After having mf OCR it and extract the parameters - a complete $$N$$ and a partial $$p$$ and $$q$$ - we did some reading one how to recover parameters from partial RSA private keys. In particular  we found to be helpful. It described a method to recover $$p$$ and $$q$$ from given $$N$$ and partial $$p$$:

Coppersmith: Given $$N=pq$$ with $$p > q$$ and an approximation $$p'$$ of $$p$$ with $$|p-p'| \leq N^\frac{1}{4}$$. Then we can find the factorization of $$N$$ in time polynomial in $$\log N$$.

Factorization is done by finding a small root  of the polynomial $$f(x) = x - p'$$ in $$\mathbb{Z}/N\mathbb{Z}$$ giving us a correction $$\Delta$$ from which we can recover $$p$$ using $$p = p' - \Delta$$ and find $$q = N/p$$.

Luckily for us Sage has all the primitives we need to solve this problem already implemented. The code to find the correction to $$p$$ is then given by

N = 0x00EED3C56E80324AFC7AB136015B7D35E573B0694D883D06F2BD1C9A85059A01AED598E0721820F0B0EAFF099C4EA5D2F59263E9B75C7782001000D5E967C35D1C29AFF6E2AC7C5A5D1BB5B49C404993C2C49EB8B10F3B6EE549B0E930E41A5A27FDF2BB8F0B60139C2A95B64737461E65FE551AFA66200C459A29D8EF45116791

F.<x> = PolynomialRing(Zmod(N), implementation='NTL')
f = x - p
p = p - f.small_roots(X=2^180, beta=0.4) # Be generous.


yielding

p = 0xF114805F133F011E29D59D931FAD8AAF8069CE3C2A8A5DE9A3F947DE0A511291ED170C4B5B09B020D703D055F540425EC4E77831BF6B9A596464C23D1D35A499
q = 0xFD9B93C36EBC2756F974A3B617B686AC9A1990F38E3951E23DCA5635CFB97347FB1890993DE3EBC11A53EFF0780929EC25D3CC00A2CEA3A17140D75731DD3DB9


which enables us to decrypt the flag: bkp{dont-f-these-dux}.

## References

1. Don Coppersmith. Finding Small Solutions to Small Degree Polynomials. http://cr.yp.to/bib/2001/coppersmith.pdf
2. Alexander May. New RSA Vulnerabilities Using Lattice Reduction Methods. http://www.cs.uni-paderborn.de/uploads/tx_sibibtex/bp.pdf