BCTF CTF 2015: warmup

解けず。Low Private-Exponent Attackかなというのは分かったが、道具を上手く使えず。具体的には関数に$e, n$を逆にして渡して動かず、解けないと判断してwriteupを見た。

solution

$e$が大きいのでLow Private-Exponent Attackぽい。 Boneh-DurfeeやWienerの攻撃ができる。

実装は以下を借りて試したが、前者は浮動小数点の精度の問題で動かず。後者では上手くいったが、sys.setrecursionlimitが必要であった。

• https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/boneh_durfee.sage
• https://github.com/pablocelayes/rsa-wiener-attack

#!/usr/bin/env python3
import gmpy2
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

c = 0x1e04304936215de8e21965cfca9c245b1a8f38339875d36779c0f123c475bc24d5eef50e7d9ff5830e80c62e8083ec55f27456c80b0ab26546b9aeb8af30e82b650690a2ed7ea407dcd094ab9c9d3d25a93b2140dcebae1814610302896e67f3ae37d108cd029fae6362ea7ac1168974c1a747ec9173799e1107e7a56d783660418ebdf6898d7037cea25867093216c2c702ef3eef71f694a6063f5f0f1179c8a2afe9898ae8dec5bb393cdffa3a52a297cd96d1ea602309ecf47cd009829b44ed3100cf6194510c53c25ca7435f60ce5f4f614cdd2c63756093b848a70aade002d6bc8f316c9e5503f32d39a56193d1d92b697b48f5aa43417631846824b5e86

with open('warmup.pub') as fh:
    key = RSA.importKey(fh.read())
assert key.n = 109966163992903243770643456296093759130737510333736483352345488643432614201030629970207047930115652268531222079508230987041869779760776072105738457123387124961036111210544028669181361694095594938869077306417325203381820822917059651429857093388618818437282624857927551285811542685269229705594166370426152128895901914709902037365652575730201897361139518816164746228733410283595236405985958414491372301878718635708605256444921222945267625853091126691358833453283744166617463257821375566155675868452032401961727814314481343467702299949407935602389342183536222842556906657001984320973035314726867840698884052182976760066141
assert key.e = 30749686305802061816334591167284030734478031427751495527922388099381921172620569310945418007467306454160014597828390709770861577479329793948103408489494025272834473555854835044153374978554414416305012267643957838998648651100705446875979573675767605387333733876537528353237076626094553367977134079292593746416875606876735717905892280664538346000950343671655257046364067221469807138232820446015769882472160551840052921930357988334306659120253114790638496480092361951536576427295789429197483597859657977832368912534761100269065509351345050758943674651053419982561094432258103614830448382949765459939698951824447818497599

# https://github.com/pablocelayes/rsa-wiener-attack
d = 4221909016509078129201801236879446760697885220928506696150646938237440992746683409881141451831939190609743447676525325543963362353923989076199470515758399

key = RSA.construct((key.n, key.e, d))
print(bytes.fromhex(hex(key.decrypt(c))[2:]).decode())