# 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{align}
c &\equiv m \cdot \left(m + b\right) &&\pmod{n} \\
c &\equiv m^2 + bm &&\pmod{n}
\end{align}

However, the exponent 2 not allowed in RSA, since $\text{gcd}\left(e, \phi\left(n\right)\right) = 1$ does not hold (they're both even).

So this is more like the [Rabin cryptosystem](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Coppersmith%27s_attack#Generalizations).

## Solution

> Note: There's a [write-up](https://duksctf.github.io/2017/04/22/PCTF2017-Multicast.html) for Multicast from PlaidCTF 2017, which has a similar solution.

So we have two equations:

\begin{align}
c_1 &\equiv m^2 + b_1m &&\pmod{n_1} \\
c_2 &\equiv m^2 + b_2m &&\pmod{n_2}
\end{align}

We want to make another equation modulo $n_1 \cdot n_2$, where $m$ is a root. First:

\begin{align}
\left(m^2 + b_1m\right) - c_1 \equiv 0 &&\pmod{n_1} \\
\left(m^2 + b_2m\right) - c_2 \equiv 0 &&\pmod{n_2}
\end{align}

So we want to find $t_1$ and $t_2$ so that this equation holds:

\begin{align}
t_1 \left(\left(m^2 + b_1m\right) - c_1\right) + t_2 \left(\left(m^2 + b_2m\right) - c_2\right) \equiv 0 &&\pmod{n_1 n_2}
\end{align}

We can choose $t_1$ and $t_2$ like so and compute them with the Chinese Remainder Theorem:

\begin{equation*}
\begin{aligned}[c]
t_1 &\equiv 1 &&\pmod{n_1} \\
t_1 &\equiv 0 &&\pmod{n_2}
\end{aligned}
\hskip4em
\begin{aligned}[c]
t_2 &\equiv 0 &&\pmod{n_1} \\
t_2 &\equiv 1 &&\pmod{n_2}
\end{aligned}
\end{equation*}

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{align}
\left(m^2 + b_1m\right) - c_1 = k_1 n_1 \\
\left(m^2 + b_2m\right) - c_2 = k_2 n_2 \\
\end{align}

Also we have these equations for some integers $k_3$ and $k_4$:

\begin{align}
t_1 = k_3 n_2 \\
t_2 = k_4 n_1 \\
\end{align}

Substituting into the larger equation, we get

\begin{align}
t_1 k_1 n_1 + t_2 k_2 n_2 &\equiv 0 &&\pmod{n_1 n_2} \\
k_3 n_2 k_1 n_1 + k_4 n_1 k_2 n_2 &\equiv 0 &&\pmod{n_1 n_2} \\
n_1 n_2 \left(k_3 k_1 + k_4 k_2 \right) &\equiv 0 &&\pmod{n_1 n_2} \\
0 &\equiv 0 &&\pmod{n_1 n_2}
\end{align}

So long story short, we've confirmed that $f\left(m\right) \equiv 0 \pmod{n_1 n_2}$ where:

\begin{align}
f\left(m\right) &\equiv t_1 \left(\left(m^2 + b_1m\right) - c_1\right) + t_2 \left(\left(m^2 + b_2m\right) - c_2\right) &&\pmod{n_1 n_2}
\end{align}

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](https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/README.md#stereotyped-messages), 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'