Try   HackMD

CakeCTF 2021: Party Ticket

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

Overview

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

b:

cm(m+b)(modn)cm2+bm(modn)

However, the exponent 2 not allowed in RSA, since

gcd(e,ϕ(n))=1 does not hold (they're both even).

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

n are hard to compute.

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.

Solution

Note: There's a write-up for Multicast from PlaidCTF 2017, which has a similar solution.

So we have two equations:

c1m2+b1m(modn1)c2m2+b2m(modn2)

We want to make another equation modulo

n1n2, where
m
is a root. First:

(m2+b1m)c10(modn1)(m2+b2m)c20(modn2)

So we want to find

t1 and
t2
so that this equation holds:

t1((m2+b1m)c1)+t2((m2+b2m)c2)0(modn1n2)

We can choose

t1 and
t2
like so and compute them with the Chinese Remainder Theorem:

t11(modn1)t10(modn2)t20(modn1)t21(modn2)

Why did we choose these values? From the equations above, we know these equations also hold for some integers

k1 and
k2
.

(m2+b1m)c1=k1n1(m2+b2m)c2=k2n2

Also we have these equations for some integers

k3 and
k4
:

t1=k3n2t2=k4n1

Substituting into the larger equation, we get

t1k1n1+t2k2n20(modn1n2)k3n2k1n1+k4n1k2n20(modn1n2)n1n2(k3k1+k4k2)0(modn1n2)00(modn1n2)

So long story short, we've confirmed that

f(m)0(modn1n2) where:

f(m)t1((m2+b1m)c1)+t2((m2+b2m)c2)(modn1n2)

We'll use Coppersmith's method to find

m. Notice that

  • n1n2
    is 2048 bits.
  • m
    is less than 1024 bits
  • Since
    m<N1/2
    , Coppersmith's method should work

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'