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$:

$$\begin{array}{rlrl}c& \equiv m\cdot (m+b)& & (\mathrm{mod}n)\\ c& \equiv m^2+bm& & (\mathrm{mod}n)\end{array}$$

However, the exponent 2 not allowed in RSA, since

$\text{gcd}(e,\varphi \left(n\right))=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:

$$\begin{array}{rlrl}{c}_1& \equiv m^2+b_{1}m& & (\mathrm{mod}{n}_1)\\ c_2& \equiv m^2+b_{2}m& & (\mathrm{mod}{n}_2)\end{array}$$

We want to make another equation modulo

$n_1\cdot n_2$, where

$m$ is a root. First:

$$\begin{array}{rlr}(m^2+b_{1}m)-c_1\equiv 0& & (\mathrm{mod}{n}_1)\\ (m^2+b_{2}m)-c_2\equiv 0& & (\mathrm{mod}{n}_2)\end{array}$$

So we want to find

$t_1$ and

$t_2$ so that this equation holds:

$$\begin{array}{rlr}{t}_1((m^2+b_{1}m)-c_1)+t_2((m^2+b_{2}m)-c_2)\equiv 0& & (\mathrm{mod}{n}_1{n}_2)\end{array}$$

We can choose

$t_1$ and

$t_2$ like so and compute them with the Chinese Remainder Theorem:

$$\begin{array}{rlrl}{t}_1& \equiv 1& & (\mathrm{mod}{n}_1)\\ t_1& \equiv 0& & (\mathrm{mod}{n}_2)\end{array}\begin{array}{rlrl}{t}_2& \equiv 0& & (\mathrm{mod}{n}_1)\\ t_2& \equiv 1& & (\mathrm{mod}{n}_2)\end{array}$$

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

$k_1$ and

$k_2$.

$$\begin{array}{r}(m^2+b_{1}m)-c_1=k_1{n}_1\\ (m^2+b_{2}m)-c_2=k_2{n}_2\end{array}$$

Also we have these equations for some integers

$k_3$ and

$k_4$:

$$\begin{array}{r}{t}_1=k_3{n}_2\\ t_2=k_4{n}_1\end{array}$$

Substituting into the larger equation, we get

$$\begin{array}{rlrl}{t}_1{k}_1{n}_1+t_2{k}_2{n}_2& \equiv 0& & (\mathrm{mod}{n}_1{n}_2)\\ k_3{n}_2{k}_1{n}_1+k_4{n}_1{k}_2{n}_2& \equiv 0& & (\mathrm{mod}{n}_1{n}_2)\\ n_1{n}_2(k_3{k}_1+k_4{k}_2)& \equiv 0& & (\mathrm{mod}{n}_1{n}_2)\\ 0& \equiv 0& & (\mathrm{mod}{n}_1{n}_2)\end{array}$$

So long story short, we've confirmed that

$f\left(m\right)\equiv 0(\mathrm{mod}{n}_1{n}_2)$ where:

$$\begin{array}{rlrl}f\left(m\right)& \equiv t_1((m^2+b_{1}m)-c_1)+t_2((m^2+b_{2}m)-c_2)& & (\mathrm{mod}{n}_1{n}_2)\end{array}$$

We'll use Coppersmith's method to find

$m$. Notice that

• $n_1{n}_2$ is 2048 bits.
• $m$ is less than 1024 bits
• Since
  $m<N^{1/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'