The Problem

The premise for the challenge was straightforward. Given two RSA public keys, a ciphertext, and the code that generated the keys and ciphertext, decrypt the ciphertext. The provided code was as follows:

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)

The keyfiles were as follows:

19402643768027967294480695361037227649637514561280461352708420192197328993512710852087871986349184383442031544945263966477446685587168025154775060178782897097993949800845903218890975275725416699258462920097986424936088541112790958875211336188249107280753661467619511079649070248659536282267267928669265252935184448638997877593781930103866416949585686541509642494048554242004100863315220430074997145531929128200885758274037875349539018669336263469803277281048657198114844413236754680549874472753528866434686048799833381542018876362229842605213500869709361657000044182573308825550237999139442040422107931857506897810951
65537

19402643768027967294480695361037227649637514561280461352708420192197328993512710852087871986349184383442031544945263966477446685587168025154775060178782897097993949800845903218890975275725416699258462920097986424936088541112790958875211336188249107280753661467619511079649070248659536282267267928669265252935757418867172314593546678104100129027339256068940987412816779744339994971665109555680401467324487397541852486805770300895063315083965445098467966738905392320963293379345531703349669197397492241574949069875012089172754014231783160960425531160246267389657034543342990940680603153790486530477470655757947009682859
65537

And finally, the ciphertext:

7991219189591014572196623817385737879027208108469800802629706564258508626010674513875496029177290575819650366802730803283761137036255380767766538866086463895539973594615882321974738140931689333873106124459849322556754579010062541988138211176574621668101228531769828358289973150393343109948611583609219420213530834364837438730411379305046156670015024547263019932288989808228091601206948741304222197779808592738075111024678982273856922586615415238555211148847427589678238745186253649783665607928382002868111278077054871294837923189536714235044041993541158402943372188779797996711792610439969105993917373651847337638929

The Solution

It seemed pretty obvious that the twin prime key generation (which is atypical for RSA key generation) was contributing to some sort of flaw. Because each modulus was derived from the same p and q, I suspected I could come up with an expression would help discover some component of the private key. My first attempt was focused on factoring a modulus to reveal either p or q. During this attempt, I had two particularly interesting equations that I consistently came back to:

n1 = p*q
n2 = (p+2)*(q+2)
=>
((n2-n1)/2)-2 = p+q

Focusing on factorization of n1 or n2 was leading me nowhere so I had to come up with an alternative plan. After some thinking it occurred to me that I did not need to know q or p to recover the private key but I could solve for the moduli used in the private exponent generation. Sure enough, some algebraic magic led me to the following equations:

(p-1)*(q-1) = pq - p - q + 1
            = n1 - (((n2-n1)/2)-2) + 1
            = d1n

(p+1)*(q+1) = pq+p+q+1
            = n1 + (((n2-n1)/2)-2) + 1
            = d2n

The left-hand side of both equations are used to derive the private decryption exponent. Using the equations from earlier, I could solve for these values using the known moduli n1 and n2. I have called these secret moduli d1n and d2n. Using these values in sage allowed me to decrypt the ciphertext and reveal the plaintext (and the random padding).

sage: n1 = 19402643768027967294480695361037227649637514561280461352708420192197328993512710852087871986349184383442031544945263966477446685587168025154775060178782897097993949800845903218890975275725416699258462920097986424936088541112790958875211336188249107280753661467619511079649070248659536282267267928669265252935184448638997877593781930103866416949585686541509642494048554242004100863315220430074997145531929128200885758274037875349539018669336263469803277281048657198114844413236754680549874472753528866434686048799833381542018876362229842605213500869709361657000044182573308825550237999139442040422107931857506897810951
sage: n2 = 19402643768027967294480695361037227649637514561280461352708420192197328993512710852087871986349184383442031544945263966477446685587168025154775060178782897097993949800845903218890975275725416699258462920097986424936088541112790958875211336188249107280753661467619511079649070248659536282267267928669265252935757418867172314593546678104100129027339256068940987412816779744339994971665109555680401467324487397541852486805770300895063315083965445098467966738905392320963293379345531703349669197397492241574949069875012089172754014231783160960425531160246267389657034543342990940680603153790486530477470655757947009682859
sage: e = 65537
sage: d1n = 7661345734913525758679393847031774068347950040691758531598768599931069162368157398573782005016161763198084934008171581312897528565920535803519676019752869540898842378294555495345540048907065220309298616755354878991960255533771830168801119335329819769158540236188072504373996977200840439942511244916661522734475021744932450921341115901747579798393654885114551422204959288643941411308605198487456697932486237279395656684673791662142482167572468147432393801726793341444983178254410054248182059962274408267954626259217708309966622421039008205130331195768525225216264782926181682101976962718778956394356939989025571723473
sage: d2n = 14682025569434715566289067921091264378913035722157264436936630821847962821708078742950421098723297556245437361748714933938836627121150444839946973227126683139046888910440667598932530416005841966364430674786751648464691745592040057258334690087243079913135108099275017066114663346987560054781243436815328782574360659576773365968491083954479736241265710621003918689757432008260802299833258500187540839592714103061124823000731244002031821226892734877380010783508256585975273581410048875828510381083429503855942633972587519902398776190078069432741587778121973508718875201608565680508108964829798569419197562575534356015937
sage: pt1 = Mod(ct1,n2)^d2n
sage: pt1
373239553115651827369899427657360875834152089860180257161642938987416643279267796017763035136285792087924995986378489367185662378937141758836872403737173549717715557150143694357419301981698777842368254230548612496956689640236300513429314367185641895908387283782093980735699566557226166228162186948786794187770887804007641846622887840125971336743542918133130483166950694027240609779212376907420023775526598867122524264065496089993260728922693481442936815735645015670821959440660673801457483695677241321385338513678687427587288462960873117726647186048326364254058577838850975109848822071400003734396085552080839412313
sage: pt2 = Mod(pt1,n1)^d1n
sage: pt2
59226173822840328968888158305624130428096624421825871746890760843535360515281731870020108027391321911226022532779216854436448650823645149055438077156974443110847829297739484809471304661775014651007761960402982748370662627695542285368162140203799886082916142874916556159547556173134812082052469735677421164129
sage: hex(int(pt2))
40830dcd4aae2c53b21745244b0a9ee8fc17349e08686a40e82dc1bed948272819131b62e715e0fce9908efaebacc261eab0c5c7446db65a0e874cca941661L'
sage: "40830dcd4aae2c53b21745244b0a9ee8fc17349e08686a40e82dc1bed948272819131b62e715e0fce9908efaebacc261eab0c5c7446db65a0e874cca941661".decode('hex')
"TWCTF{3102628d7059fa267365f8c37a0e56cf7e0797ef}\n\x00\xa0\xdf\xdd\xeb*\xc0\xfd\x93\tL\xe4\x080\xdc\xd4\xaa\xe2\x7f\xd2<\x805\xecS\xb2\x17E$K\n\x9e\xe8\xfc\x174\x9e\x08hj@\xe8-\xc1\xbe\xd9H'(\x19\x13\x1b$\xe7\x15\xe0\xfc\xe9\x90\x8e\xfa\xeb\xac\xc2a\xea\xb0\xc5\xc7Dm\xb6Z\x0e\x87L\xca\x94\x16a"

The last line in the sage REPL is the ciphertext (and random padding). Another flag captured: TWCTF{3102628d7059fa267365f8c37a0e56cf7e0797ef}.

Tokyo Westerns / MMA CTF: Twin Primes Write-up

The Problem

The Solution