Tokyo Westerns CTF 2016 | Twin Primes (Crypto50)

solver.py

from Crypto.Util.number import *
import Crypto.PublicKey.RSA as RSA
import os


n1 = 19402643768027967294480695361037227649637514561280461352708420192197328993512710852087871986349184383442031544945263966477446685587168025154775060178782897097993949800845903218890975275725416699258462920097986424936088541112790958875211336188249107280753661467619511079649070248659536282267267928669265252935184448638997877593781930103866416949585686541509642494048554242004100863315220430074997145531929128200885758274037875349539018669336263469803277281048657198114844413236754680549874472753528866434686048799833381542018876362229842605213500869709361657000044182573308825550237999139442040422107931857506897810951
n2 = 19402643768027967294480695361037227649637514561280461352708420192197328993512710852087871986349184383442031544945263966477446685587168025154775060178782897097993949800845903218890975275725416699258462920097986424936088541112790958875211336188249107280753661467619511079649070248659536282267267928669265252935757418867172314593546678104100129027339256068940987412816779744339994971665109555680401467324487397541852486805770300895063315083965445098467966738905392320963293379345531703349669197397492241574949069875012089172754014231783160960425531160246267389657034543342990940680603153790486530477470655757947009682859
e = long(65537)

# n1 = p*q
# n2 = p*q + 2*(p+q) + 4

# 2*(p+q) = n2 - p*q - 4
# p+q = (n2 - n1 -4) / 2 (=a)

# (p-1)*(q-1) = p*q - (p+q) + 1 = n1 - a + 1
# (p+1)*(q+1) = p*q + (p+q) + 1 = n1 + a + 1

a = (n2 - n1 - 4) / 2
phi1 = n1 - a + 1
phi2 = n1 + a + 1

d1 = inverse(e, phi1)
d2 = inverse(e, phi2)

key1 = RSA.construct((n1, e, d1))
key2 = RSA.construct((n2, e, d2))

c = 7991219189591014572196623817385737879027208108469800802629706564258508626010674513875496029177290575819650366802730803283761137036255380767766538866086463895539973594615882321974738140931689333873106124459849322556754579010062541988138211176574621668101228531769828358289973150393343109948611583609219420213530834364837438730411379305046156670015024547263019932288989808228091601206948741304222197779808592738075111024678982273856922586615415238555211148847427589678238745186253649783665607928382002868111278077054871294837923189536714235044041993541158402943372188779797996711792610439969105993917373651847337638929

c = key2.decrypt(c)
c = key1.decrypt(c)
m = long_to_bytes(c)

print m

# flag: TWCTF{3102628d7059fa267365f8c37a0e56cf7e0797ef}

双子素数のペアを２つ使って鍵を２つ作り、２重にRSA暗号化している。公開鍵としてp_qと(p+2)_(q+2)の値が分かっているので式変形エンヤコラして秘密鍵を求め復号する。