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 [2] 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 [1] 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
p = 0x00F114805F133F011E29D59D931FAD8AAF8069CE3C2A8A5DE9A3F947DE0A511291ED170C4B5B09B020D70000000000000000000000000000000000000000000000

F.<x> = PolynomialRing(Zmod(N), implementation='NTL')
f = x - p
p = p - f.small_roots(X=2^180, beta=0.4)[0] # 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

Comments