The Problem
Given a public key, an encrypted flag and a Python script that encrypted the flag decrypt the flag. First, the script used to create the challenge files.
#!/usr/bin/python
import gmpy
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5
flag = open('flag', 'r').read() * 30
def ext_rsa_encrypt(p, q, e, msg):
m = bytes_to_long(msg) # unused lol
while True:
n = p * q
try:
phi = (p - 1)*(q - 1)
d = gmpy.invert(e, phi)
pubkey = RSA.construct((long(n), long(e)))
key = PKCS1_v1_5.new(pubkey)
enc = key.encrypt(msg).encode('base64')
return enc
except:
p = gmpy.next_prime(p**2 + q**2)
q = gmpy.next_prime(2*p*q)
e = gmpy.next_prime(e**2)
p = getPrime(128)
q = getPrime(128)
n = p*q
e = getPrime(64)
pubkey = RSA.construct((long(n), long(e)))
f = open('pubkey.pem', 'w')
f.write(pubkey.exportKey())
g = open('flag.enc', 'w')
g.write(ext_rsa_encrypt(p, q, e, flag))
The encrypted flag:
mBvIRwW8Q7hkNINbXmTGxscnVjfZ9nVG2AaOYHeTRYsRezHMkpFW15q3NqENPLJGyLlDALb5Cycd
TV9ok/NXoUnnXx3MQLQnBVax2pmZ3bkUBbaRIWyVB2UHcZKpH8UFPT2uFnDSnhOG8PBJ9RCCs2ew
UoJ1wBxV8W7qBmMe6TmoEn6g0/sOte5o7lp5oJMCbWObhjNpxHtrREryTdulDgRVlWbvbpV/m4V1
V7U1a2FQuAQpEMcIMAgWXllzsfGCOPI1iHh7IodWkNjc1sIMOzeqf05L0f393h14GR1/JqPAZJTs
QjM/aB4QkZuH7rPHqyaM5mNsZ1+KPRZsLfYRcTBaiM/mBg/aNWWZg9kvzovP+Zs5EPkJepAYTmLs
l4t5mjkMdJ64nvXJiOcNwHVfClQjyVwJcdeguu1CAsU81CZnYo+Yixh129gCQuMkgQN3t9Pb+zz8
Edl2HlpOwcfT99C/EcQVfNmsHn96Y3LPUkFVPUquhNaMDmsYVbRyxeoa2Rktwr4Ia4Rhi1HQb7jz
Ehql8R4H9HS/wrPueqc5nL2odfC7ctThes6sA447oBCnkb95NVQLRiJlhYJvan2Vy/wySJJArrX4
PiY5Qh+dMrZnHP9XMFs5CFu6PIH9Iy5pwi9SQenUZJ3ajm8fDc6Vtpi+dRNEh78hlZ8iZu0p403i
UE8PEwp6qYf2StIjq/JU+LAEqhR9cn6parxDhZt3ftfq0SIbGSPZ42832Yyhr6GKwYBguHJIvXHi
bo3zIgxPiTLwxseaY9N4KrPWyNpL9Uq14qQt7cNLWfhv/e3vlIReZjWgqBYZYS90FjJt04VPWmUU
i4O8RCgCqPfd1Oc3OS9UB7NnvcN4SQQ5CowA3AJxrd/8vjTBgV0CS5ZxV48yapB9iHOvR7PGJVY4
79q7eQDqf3lSOeQ7DH0Y/wA+HJMw1HGP1BfWD0Fu7PsWxHmBEPkusIc8gxg+y7N1/d2YaWcpe0N0
cXUd1Jm02W+5b1vOfpwbOcGh4eZTS2SN4Iu/uDKWwThD0C9po35qZTC67QUeYU+7u9EafVD+ETQz
9DHo8kP9jYKnjpsP3mPlv7nj1sHEMA52tfNclxagj8haf101V3lH453UBhzQjFOlo7XGFD/fH+HU
Xhszsj6oPttU99qBoun0HSQtK+JhEIjTTj/kO8/rT+jqfSiSf24Ermvxf6ooqYG/HKXShWEkYHBp
yA9cAu5/k1EgKKrkj1SlOcGPfNYiaCvCwok5IZR6cMjYy5H9UXn+naedLSk1r6iG5lY52zXCBm9i
akgyEobAUxUPhENrrM2x/pBNUL5Kpi/z5IrjHiVotCqbofkZK3YX0PjOpaQVwtoklaA5uHvGk5mT
UIVlXPJKice9G6sPu16Ugi0xfaRm2iDAMK5feq527mCI5+pkA8ATjJinh+UxfN50YYN7zzgBBOVh
Kj2MH0mnsHXeYipRM5lFDmTGNCSF/NVu2yo3cayxWFmnWU6kU+TWGgFKN4xdFm/dzb3oO23rhEkP
QKHMdkDweGFzqxXcv7qJICGG/xXKDkcCdVWaRWsNXLHh21Z3cjf0hWsx8bjufB352uDCYGm+oYtM
PdN2SZTdPy937IbVjO9v56+1zpt5zvNc2xyj/jOfr5DVklh/c9h3Cvnx45gukabAsFbhXy8lUU84
uyQmO12MhPK4jSvXQglEsJVqk3UYGiYSkPeWPplMWYzLXurJM0OBsfB9gfFt30C2fdQvgh4b2TWe
O8PZnsf4oaQT9v16A5Z1bniVbb5UVqsn234g3BPOSUGVaEvglANBt07+vNTa6fQ+QhrR/j19csU0
xxgplIzswzf8gue6CWBsaqUV7Sqq7mpPEYOucJ0RMqZCyaA4ACTqpZn8hedIiQWBa02519QyYbwE
AKSwS2/zXINK7wlC/acryghivN3ciKK8Aio7XXuYZ+92NC1sCFsFutySJMcRx09qbQDxu4r/22Wc
4VsH9S/lM0SvIfP0mBQt1Kk2qNJoTX+6Vsa2OFHgwNOubwZga+WBF7gP4zCxI2JQvgoHXdxjikeX
czlDYlQ5KBcK4E3QZKIj7yVH5R1g5noMoEwsj7AYKKJ2pbx9yadMEev9O+7JHg/GIsA+56WcZRC6
UqtFWqBOJVr7WEIk5HI0yyB5oZHKmAf3iWG8r94J84TTKxnbpqSV/t5GT6JZJegaIx2CuwYhTXCM
a3lBtQfDMfdZ/ZvrlnK/+hhE420/x1Z8qHDRfc+ZTbCDOh+RIwlZ32aXvRfEdzTU5YdRBdfAeuXz
GbfDDRmwOLNFX2vC80MXFBpAFYDhHtYsuEx3IWY0mwaftMjgCLjnoMA2D6culnbJ3O3cwsqksqgV
9Axv5GdqqPMANj1FsJo5A97wuOjA7pRG2kMwEIijfx/cPZnIha/rTX3iYuI441qx9bi+l6rw0HvF
qlM+r18eoTOGdN4egNiho5YeMaVzm+bgkVBRYMtxl150ntfdBx7wgFL/8AnPmNH3PA1hhwHaW/0v
LWRXc0M/uB3MD0TG61mlWIDOCJYAn4BasWjYgluMT0Gl31kfM0TiENuY547ZRvAikXWDjbt2wNAA
Dvn/4QIOv/vAI7k4o1m98R94+IQUvTkdOxs5J+R7m6hW7F1FWXKnJcRFV9VyN7VtnFBGfdJihFu1
y4lIBQb5cmZXgaDWsQdrQr2JaAj481Qon227LvpkKWiMz60y5Mv2JCpFZHhtEnQUIsFzX92bGpSC
BXpj6EueRnTnUL695Dq1I6VfjCYnrxMYeuvUCFFJGrX1087TSrFk60yWvYpndx5kUA0/2jCbLFzq
aNfYEE7CT9si10BQqOaeWQ6OJGTg0kGwmykXN/pBZmzxG/EkgK94l66o+W9aScXV5XZfQfz7Tfw0
AknUqW4U
And finally the public key:
-----BEGIN PUBLIC KEY-----
MEIwDQYJKoZIhvcNAQEBBQADMQAwLgIhANjiTBK3uZ7+CpvASmo99YoqlEJptJK3
N23xKQI/IGG5AgkArCrD4MoPVgc=
-----END PUBLIC KEY-----
The Solution
The size of the public key stuck out like a sore thumb. Decoding the public key and dropping it into sage returned the factors pretty quickly.
>>> import gmpy
>>> from Crypto.PublicKey import RSA
>>> from Crypto.Util.number import *
>>> from Crypto.Cipher import PKCS1_v1_5
>>> pbf = open('pubkey.pem', 'r')
>>> pbb = pbf.read()
>>> pbb
'-----BEGIN PUBLIC KEY-----\nMEIwDQYJKoZIhvcNAQEBBQADMQAwLgIhANjiTBK3uZ7+CpvASmo99YoqlEJptJK3\nN23xKQI/IGG5AgkArCrD4MoPVgc=\n-----END PUBLIC KEY-----'
>>> key = RSA.importKey(pbb)
>>> key.n
98099407767975360290660227117126057014537157468191654426411230468489043009977L
>>> key.e
12405943493775545863L
>>>
sage: factor(98099407767975360290660227117126057014537157468191654426411230468489043009977)
311155972145869391293781528370734636009 * 315274063651866931016337573625089033553
Easy right? I went ahead and dropped those factors into a python script and tried to decrypt the flag.
import gmpy
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5
ct = open('flag.enc', 'r')
ctb = ct.read().decode('base64')
p = 311155972145869391293781528370734636009L
q = 315274063651866931016337573625089033553L
n = 98099407767975360290660227117126057014537157468191654426411230468489043009977L
e = 12405943493775545863L
phi = (p-1)*(q-1)
d = gmpy.invert(e,phi)
privkey = RSA.construct((long(n), long(e), long(d), long(p), long(q)))
key = PKCS1_v1_5.new(privkey)
pt = key.decrypt(ctb, "")
print(pt)
Well that won't work because the numeric representation of the ciphertext was
much larger than the modulus. If you follow the python script, you may notice
that the public key written to pubkey.pem is not necessarily the public key
used to encrypt the flag. This is where that weird exception handling code
within the while loop comes into play. After a multiple unsuccessful attempts
(most took too long) the following script eventually gave the first parameters
that were large enough to decrypt the ciphertext.
import gmpy
import sys
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5
flag = open('flag.enc', 'r').read().decode('base64')
ctl = bytes_to_long(flag)
ctlbl = ctl.bit_length()
n = 98099407767975360290660227117126057014537157468191654426411230468489043009977L
e = 12405943493775545863L
p = 311155972145869391293781528370734636009L
q = 315274063651866931016337573625089033553L
while True:
try:
n = p * q
phi = (p-1)*(q-1)
d = gmpy.invert(e, phi)
privkey = RSA.construct((long(n), long(e), long(d), long(p), long(q)))
key = PKCS1_v1_5.new(privkey)
enc = key.decrypt(flag,"")
break
except (ValueError):
print("generating new primes")
p = gmpy.next_prime(p**2 + q**2)
q = gmpy.next_prime(2*p*q)
e = gmpy.next_prime(e**2)
print("e: %d" % e)
print("ebl: %d" % long(e).bit_length())
print("p: %d" % p)
print("pbl: %d" % long(p).bit_length())
print("q: %d" % q)
print("qbl: %d" % long(q).bit_length())
Which gave the parameters:
generating new primes
generating new primes
generating new primes
generating new primes
e: 314830485826658361073450198889881173831713829800385177067682042516610760629294248571248879807488467719664409033735870971057216922576277617591226061893813303020048259898614377557163965487832080431261531763558621183390365333213048774925814019384118187583019105600969353278032498550517473111344678179223171583
ebl: 1015
p: 11813506340065782086301289156296758091306130081220477832021785318407303257593997482766810282251569890070998581138779965561147400718174879921117290624867532940623866873813501508916893904956261644070940363992103452886192903943625997809233877900542185586382507229126919927260575222662344488979668641134861408556677348688568581676557071994293536426874788621167439863881037707559309395645751149427986178124407813777538808729076763648746417811311576215559979426092362962793641493030423859511361794920837524009172269829118910732495510397088785131879120323139759579629597219070654067629572808029782726784623266505282653541446929443261801077750852010506044199013103106355978777399087440528578163053523904105895489332098859172602809798204496225836679509974057030269730427913921627594441404835281908088924389399027195130701149673974222059066776511004444628393046452849913417478171640973124014461366016851281872241272302373654727509226131377848945075915177828954799976116957303106297317876449297424520465011318253175308641610887087067659287195233462246881134059990127259584550136777186474622549292306925359236625034204828810556071352958990296393939712560254842325646682609504054542355200697037835342345394888448085065394317234407614654982389945692656907598323233416180767297796105342412136424450485332346458781108717459396704987941855537147058896880149283468333964095318786385413817035144709558532525945940211962424442893159263617875117618004839288526450401083675390588354659539689859643259796901282804476728068558852910444380193780201789736460380886424119953228304570611009427796432088325452694350610170845749311395773830561691059058603849132986837165525905619051854899954419655597248378782411058472716406121413461991589799153141396934909410148151737662513742991188214758585851452287429064872587154568136516988341136879157414903123436508145593835462194847334859696828413245198936348364858240226051244765640937582602980340974904168500458441553253843458024555871623458752390514031114659971423622314448250162801557907786739626922709148126534770583688973667362683814288450710656004109195398581824731990026609
pbl: 6950
q: 2568018947396906867730484054559176373055678684809062883307996109582522191792904521639205961896458929696494209190832115825348642505303978307861089229858015847226013511992313544673413799955741632284487401900830204742329517432164928566952429611873952485705878557408845731306400006570189198816445184158610878825774485990884002762440249987715560706467593968273717098161655315429936346412939640462961387853160672262886153664799117903261687477444168621507168813004209629790579348749166562426219879914994864828419151343836949730192073951779827132278482200206542119392711424967838590612004623220294832154158660323153295508501674009465975869086038575636786677766417405345015215196199478836107674263972634214142457749191949750391756302271486514967910828236875990049266586225919073091424990228061585485235650512051996110118071940016166260010307240252785548993724930467033985031663692494915748873269780165600667628836005411039528766658031223459512427594643758598081115348508663540267356902641833854965018683497801043068327822943715135848514342985077876701164549248480942949686519320560742070317959963207939161898057169801712769444755745016119821194956470242570775300894005823821150111573385654078632454725214170566527326111000897225336646495220660699788080340696564361148210515177625096239599105302595726558278270245894579646799307874905679240179641048660604830771826971248560392929505881587123673245876552261401229261552351390394220197109211745313149341656871350480690450186360416847337943534539184794149222829415876254778443338997945371645672223139561805344980080516900354124695218052157095079247115165153824348545270832915360956086113182978494133000324309595641667945589371249190729377755739755113702494564623013755346032112420801000607645398740938734923935389478506821395435556912648075640453837062986466448086501768974109850455376997539373245093447066964877848568985839257253998129910845583876493096537079587746179038495658394834307628266084126908800295412691091054505027023284851469848704972176650685606066983403603197857780592131039938683300057782610100876015465367936511774574985343247536020037590734882228879603653981675423695879242520556635056877538914944780734853289853742644991136082383366587307210613080529100167152853181846730554224293600784049867138595602763879265875541346376475782776451239537343265192761233268565460233911019132186322948387353044082450622534426065240123594467744275647329983287662939115142474354901842298509545298063265434284594060938870332165709160137400924381370992836104680409236481377741365626156597158719332046400793906736441256559025457513611317267210217864156350329330948775395384682961509767624219072120831658435938466337525767526115603057013802720263137949671253502369353538174297233848087518284710274378117714187878458938466874644835774384848441820747781857475272435651693982314376470207234588842822898943206441044233151260260224826744287368317723326321354450825928683911684933645539323105707812237168060162384638599574898166033536543607270157600750803595769475725100945982346277514055242368447953161514538396255299641488430096537564859976459495081285771310185618437190615572421911192312857595860426594028707
qbl: 10426
If you throw those parameters into the first script, the flag will decrypt and we'll get the flag (30 times):
ASIS{F4ct0R__N_by_it3rat!ng!}