[Crypto] Twin Prime - 50pts

Twin Primes

Crypto Warmup

Problem

Decrypt it.
twin-primes.7z

Flag

	#	Your Score	Score	Your Ratings	Teams
	1	50	50		183

# encrypt.py
from Crypto.Util.number import *
import Crypto.PublicKey.RSA as RSA
import os

N = 1024

def getTwinPrime(N):
    while True:
        p = getPrime(N)
        if isPrime(p+2):
            return p

def genkey(N = 1024):
    p = getTwinPrime(N)
    q = getTwinPrime(N)
    n1 = p*q
    n2 = (p+2)*(q+2)
    e = long(65537)
    d1 = inverse(e, (p-1)*(q-1))
    d2 = inverse(e, (p+1)*(q+1))
    key1 = RSA.construct((n1, e, d1))
    key2 = RSA.construct((n2, e, d2))
    if n1 < n2:
        return (key1, key2)
    else:
        return (key2, key1)

rsa1, rsa2 = genkey(N)

with open("flag", "r") as f:
    flag = f.read()
padded_flag = flag + "\0" + os.urandom(N/8 - 1 - len(flag))

c = bytes_to_long(padded_flag)
c = rsa1.encrypt(c, 0)[0]
c = rsa2.encrypt(c, 0)[0]

with open("key1", "w") as f:
    f.write("%d\n" % rsa1.n)
    f.write("%d\n" % rsa1.e)
with open("key2", "w") as f:
    f.write("%d\n" % rsa2.n)
    f.write("%d\n" % rsa2.e)

with open("encrypted", "w") as f:
    f.write("%d\n" % c)

n1 = p*q

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

2( p+q ) = n2 - p*q - 4

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

(p-1)*(q-1) in d1.

= p*q - ( p+q ) + 1

(p+1)*(q+1) in d1.

= p*q + ( p+q ) + 1

# twin_prime.py
from Crypto.Util.number import *
import Crypto.PublicKey.RSA as RSA
import os

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

p_q = (n2-n1-4)/2
phi_n1 = n1-p_q+1
phi_n2 = n1+p_q+1

d1 = inverse(e, phi_n1)
d2 = inverse(e, phi_n2)

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

c = 7991219189591014572196623817385737879027208108469800802629706564258508626010674513875496029177290575819650366802730803283761137036255380767766538866086463895539973594615882321974738140931689333873106124459849322556754579010062541988138211176574621668101228531769828358289973150393343109948611583609219420213530834364837438730411379305046156670015024547263019932288989808228091601206948741304222197779808592738075111024678982273856922586615415238555211148847427589678238745186253649783665607928382002868111278077054871294837923189536714235044041993541158402943372188779797996711792610439969105993917373651847337638929


c = key2.decrypt(c)
c = key1.decrypt(c)
c = long_to_bytes(c)
print c
'''
shpik@shpik:/ctf/MMA/crypt$ python twin_primes.py 
TWCTF{3102628d7059fa267365f8c37a0e56cf7e0797ef}
 ࠝ髀	0ݔм5듲E$K
麗hj@殁¾؈'(喠ﻫ¬a걅Ƅm¶ZLʔa

'''