Skip to content

Instantly share code, notes, and snippets.

@ITAYC0HEN ITAYC0HEN/twin-primes.py
Last active Feb 3, 2017

Embed
What would you like to do?
[TWCTF-2016: Crypto] Twin Primes
from sympy import *
from Crypto.Util.number import *
import Crypto.PublicKey.RSA as RSA
import os
# n from key1
n1 = 19402643768027967294480695361037227649637514561280461352708420192197328993512710852087871986349184383442031544945263966477446685587168025154775060178782897097993949800845903218890975275725416699258462920097986424936088541112790958875211336188249107280753661467619511079649070248659536282267267928669265252935184448638997877593781930103866416949585686541509642494048554242004100863315220430074997145531929128200885758274037875349539018669336263469803277281048657198114844413236754680549874472753528866434686048799833381542018876362229842605213500869709361657000044182573308825550237999139442040422107931857506897810951
# n from key2
n2 = 19402643768027967294480695361037227649637514561280461352708420192197328993512710852087871986349184383442031544945263966477446685587168025154775060178782897097993949800845903218890975275725416699258462920097986424936088541112790958875211336188249107280753661467619511079649070248659536282267267928669265252935757418867172314593546678104100129027339256068940987412816779744339994971665109555680401467324487397541852486805770300895063315083965445098467966738905392320963293379345531703349669197397492241574949069875012089172754014231783160960425531160246267389657034543342990940680603153790486530477470655757947009682859
# e from key1 && key2
e=long(65537)
# a,b and c of the quadratic equation
a = 2
b = n1-n2+4
c = 2*n1
x = Symbol('x')
# solve the equation and put the solutions in x1_2, one of the solutions will be p, and the other will be q
x1_2 = solve(a*x**2+b*x+c)
p = x1_2[0]
q = x1_2[1]
# create d1 and d2 form p and q
d1 = inverse(e, (p-1)*(q-1))
d2 = inverse(e, (p+1)*(q+1))
# constructs the paramter to key1 and key2
key1=RSA.construct((n1,e,d1))
key2=RSA.construct((n2,e,d2))
# decrypt the flag
encrypted_flag = open('/Megabeets/encrypted',"r").read()
long_to_bytes(key1.decrypt(key2.decrypt(encrypted_flag)))
# result: "TWCTF{3102628d7059fa267365f8c37a0e56cf7e0797ef}"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.