Category: crypto
Points: 256 (12 solves)
Author: theoldmoon0602k
Komachi is going to invite Moe and Lulu to the party. But… she is shy and she
encrypted the invitations. Nanado's secret mission is to decrypt these tickets
so Komachi won't get lonely.
Attachments: party_ticket.gz
from Crypto.Util.number import getPrime, isPrime
from hashlib import sha512
import random
def getSafePrime(bits):
while True:
p = getPrime(bits - 1)
q = 2 * p + 1
if isPrime(q):
return q
def make_inivitation():
with open("flag.txt", "rb") as f:
flag = f.read().strip()
m = int.from_bytes(flag + sha512(flag).digest(), "big")
p = getSafePrime(512)
q = getSafePrime(512)
n = p * q
assert m < n
b = random.randint(2, n - 1)
c = m * (m + b) % n
return c, n, b
# print("Dear Moe:")
print(make_inivitation())
# print("Dear Lulu:")
print(make_inivitation())
At first it kind of looks likes RSA with random linear padding from
However, the exponent 2 not allowed in RSA, since
So this is more like the Rabin cryptosystem, which is similar to RSA but uses exponent 2. It relies on the fact that square roots modulo
We're given 2 encryptions of the same message, but with random linear pads. Since the exponent is 2, this looks like the set up for Håstad's broadcast attack.
Note: There's a write-up for Multicast from PlaidCTF 2017, which has a similar solution.
So we have two equations:
We want to make another equation modulo
So we want to find
We can choose
Why did we choose these values? From the equations above, we know these equations also hold for some integers
Also we have these equations for some integers
Substituting into the larger equation, we get
So long story short, we've confirmed that
We'll use Coppersmith's method to find
I used this implementation, since it prints out the bounds nicely.
Unfortunately the default value of epsilon
is too large, so I slowly decreased it (which in turn increased the upper bound) until it found a solution. In the end, epsilon = 0.09
worked for me.
Script:
import Crypto.Util.number as cun
c1, n1, b1 = (
39795129165179782072948669478321161038899681479625871173358302171683237835893840832234290438594216818679179705997157281783088604033668784734122669285858548434085304860234391595875496651283661871404229929931914526131264445207417648044425803563540967051469010787678249371332908670932659894542284165107881074924,
68660909070969737297724508988762852362244900989155650221801858809739761710736551570690881564899840391495223451995828852734931447471673160591368686788574452119089378643644806717315577499800198973149266893774763827678504269587808830214845193664196824803341291352363645741122863749136102317353277712778211746921,
67178092889486032966910239547294187275937064814538687370261392801988475286892301409412576388719256715674626198440678559254835210118951299316974691924547702661863023685159440234566417895869627139518545768653628797985530216197348765809818845561978683799881440977147882485209500531050870266487696442421879139684,
)
c2, n2, b2 = (
36129665029719417090875571200754697953719279663088594567085283528953872388969769307850818115587391335775050603174937738300553500364215284033587524409615295754037689856216651222399084259820740358670434163638881570227399889906282981752001884272665493024728725562843386437393437830876306729318240313971929190505,
126991469439266064182253640334143646787359600249751079940543800712902350262198976007776974846490305764455811952233960442940522062124810837879374503257253974693717431704743426838043079713490230725414862073192582640938262060331106418061373056529919988728695827648357260941906124164026078519494251443409651992021,
126361241889724771204194948532709880824648737216913346245821320121024754608436799993819209968301950594061546010811840952941646399799787914278677074393432618677546231281655894048478786406241444001324129430720968342426822797458373897535424257744221083876893507563751916046235091732419653547738101160488559383290,
)
t1 = crt([1, 0], [n1, n2])
t2 = crt([0, 1], [n1, n2])
N = n1 * n2
P.<x> = PolynomialRing(Zmod(N), implementation='NTL')
pol = t1 * ((x ** 2 + b1 * x) - c1) + t2 * ((x ** 2 + b2 * x) - c2)
pol = pol.monic()
dd = pol.degree()
beta = 1 # b = N
epsilon = beta / 7 # <= beta / 7
epsilon = 0.09
mm = ceil(beta ** 2 / (dd * epsilon)) # optimized value
tt = floor(dd * mm * ((1 / beta) - 1)) # optimized value
XX = ceil(N ** ((beta ** 2 / dd) - epsilon)) # optimized v
load("coppersmith.sage")
roots = coppersmith_howgrave_univariate(pol, N, beta, mm, tt, XX)
for root in roots:
print(cun.long_to_bytes(root))
Output:
# Optimized t?
we want X^(n-1) < N^(beta*m) so that each vector is helpful
* X^(n-1) = 7.79082197650672e2777
* N^(beta*m) = 439445059494645293974636248793771991612541520285469077227739949579313689273197674697489684632206763326037542213556893543143761312074466866572105819405388745445279760175125421207247597277525481155522822905158568657617831266521788036590899373231493647108845702263079913997398639112858489402545862791811181070924404660377151854851459421821094378085538499937393085398901323455995066984649004147563773718028430794111321563155693221161220524966386095938502252156515930115157038244404236047165496610353024552147896538408259821505748295383306771672945899740538968788569106393242390926655639181134948525359919107351189379810593185726648925100894447961057876722494718983347079052969991232402679750441032482516301684405136829857206658704498026235817131205180753624885119207984983197192900532872166632175302615457076785625968173286607001542536359451210889147364860766066582376779163528286481018926621403897726979761681917004985584019011698383874487090140028994397962380389491012010240927204195797294399746886397558283716462803327095891044817028024182436088243068753273412685586700090254337035037988985084179818075693498209957133488475936082130736270033272499434204259695894171483742261883151275951484199811306332281858044280454548669544261989901092110167969142204333239345948256839585485431618336659910281568841570158770274008775587890080405988019515486767228936448724897906159683726964700416165051033465643375878705551924515964087791799038050703361961028896546602929654354105828340351612984411216164898589459683105031505177817370556707352796676995355015544901668265610979072484842193446032556262948915135653914116505786939600147584234376834462153063813771931933415223391162526523789327799428963781597106431416729647263216502391375226051212864206156425704052460124292519807705257791014112355672456727852447521695387381787728229360874249021407638197913652375872670264130392550822364014413273180265524321704818309472530639047940196499540986073291187136699920248840440365961299988125237466567081094292298137490915151546158985321306094799288559869966770110468206587283455216185673055838127422454011932260304846746013224797009689665973869017061722117355904077851830223659583877565299998560974979762515527904821155404624605292014979306883872459392206626028082140398190242169893956558598965228270990299093456121244013580157668278290446857568495806411395251851468250111937636724790410796465245464065456103516404932287186247659903786958458620217737012556962564233829370832552504151631127244025149939668734391284829513670210171712705938912238080437243026398086785795511215364496107439942165597399248039195588394171815975561425444366086716947508298426933732832607805546617935814726165530223217658910582129800040747836779740241913583690225019765455074346048480315670985307294885772322638608517189248624610071456477218062332388538595885194833798525567248197328419783423233564909229579750003311106877894920187421321497603487530105113856523624462966831941641197452551335411014682243595763138767702145654188065680261106850150623297673262117224966044913024564204314466327391017846975928675515234830067798679190000194726036493349034364788524656085918969370125109074549381484840663354530696626809035680050275851683200400525037853085054990736815729895182377736061484811462012757256063528118601456860014000403983590296913866346246324750387690205266639614464443446025379433636098638481180817323047163105420901888790093879944548248573804774522970891589816004105373785492178562833128254372089047345074281786829548699731720820299420686633347973035284608574053400064137321871716195023669126245425331095078117561607386203922818893468428674057716619676408100684885227930457385776381675166678323332731518848635660471778668949308648918041
* X^(n-1) < N^(beta*m)
-> GOOD
# X bound respected?
we want X <= N^(((2*beta*m)/(n-1)) - ((delta*m*(m+1))/(n*(n-1)))) / 2 = M
* X = 3432404637396682977538831169694005101900586181759588132994992486982299354502215910425673628772685990014927767586667929872969674609512133440118731716214363155009121087359432541981609900951276141768803425417082407881194123058607200631647237329223371718656
* M = 4.69804661339436e279
* X <= M
-> GOOD
# Solutions possible?
we can find a solution if 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)
* 2^((n - 1)/4) * det(L)^(1/n) = 3.67551729270059e3545
* N^(beta*m) / sqrt(n) = 1.26856861696642e3695
* 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)
-> SOLUTION WILL BE FOUND
# Note that no solutions will be found _for sure_ if you don't respect:
* |root| < X
* b >= modulus^beta
00 X 0 0 0 0 0 0 0 0 0 0 0 ~
01 0 X 0 0 0 0 0 0 0 0 0 0 ~
02 X X X 0 0 0 0 0 0 0 0 0
03 0 X X X 0 0 0 0 0 0 0 0 ~
04 X X X X X 0 0 0 0 0 0 0
05 0 X X X X X 0 0 0 0 0 0 ~
06 X X X X X X X 0 0 0 0 0
07 0 X X X X X X X 0 0 0 0
08 X X X X X X X X X 0 0 0
09 0 X X X X X X X X X 0 0
10 X X X X X X X X X X X 0
11 0 X X X X X X X X X X X
potential roots: [(8288019666414250297759292171687475421492232818737821326621996108402380171721836673645567042633149756411614430575568279199859305892583735709780527038824655329947112470481701438783511180691576641391543556967743369328894120863038015520008430190710859664128765078745, 1)]
b'CakeCTF{710_i5_5m4r73r_7h4n_R4bin_4nd_H4574d}\xa1f{\x0c\x19\xd6\xfb\x15\xff\xc1\xf7\x1fB_\xac4WEA\xce\x8c\x02\x88$O\xb9\xf8\xcd\xa5\xacd;\xf2\xb7\xf3L\x05\xdf \x12`\x1b\x88\x91\nr\xb5\x0b\xb6J=\xa7\xc9\xfb\xfe\x93Z\xe5{i\x95H,\xd9'