Notebook

2nd Crypto CTF 2020 - GenGol¶

This is again an RSA-like challenge, where few weaknesses are interestingly mixed together.

In [ ]:

from Crypto.Util.number import *
import random

def genkey(k=512, nbit=1024):
    assert 2*k <= nbit
    while True:
        p = random.randint(1, 2**(nbit - k)) * 2**k + 1
        if not isPrime(p): continue
        q = getPrime(nbit)
        n = p * q
        while True:
            y = random.randint(1, n)
            jp, jq = pow(y, (p-1)//2, p), pow(y, (q-1)//2, q)
            if (jp + jq == p + q - 2):
                d = random.randint(int(exp(0.272 * log(n))), int(exp(0.292 * log(n)))) | 1
                e = inverse(d, (p - 1)*(n/p - 1))
                if e * d % ((p - 1)*(n/p - 1)) == 1:
                    return (n, y, k, e), (p, d)

def encrypt(msg, pkey):
    n, y, k, _ = pkey
    m = bytes_to_long(msg)
    assert m <= 2**k - 1
    x = random.randint(1, n)
    c = pow(y, m, n) * pow(x, 4**k, n) % n
    return c

In [2]:

n, y, k, e = pkey = (19545764749038418707423482688339375172570014947642431940684456209199133662612924782350873526870144698958332746564347962129710266450724719417969337820667041471024794991519152124184751777703438755127996141556369377531644132238147658246849302588050812207568092111336823914414716415415043221612879571114226453349014538716642991132002013001057172880188860648420935958930680331305269004539955338202912788402527881753117747941781017257550506692901575263952247810144252350279803242123415203612038326448039955185283198645290497751691434792586616961955028752759257565821926239920507512570745243565662182775774062057791614340059L, 6713416021011621860292095135170808229197691401808786379005956958972631575685722516254902506420897257390134389751222750071612382145080088914855339805564824600399571590429098132306344208575084295212754746022537647167518867331249618141656172215473281056990729825123342876791069716652238530101906241012957925858050801973297467776915931059263433002394778083519034230621723649147245051859246240595459023971754395781480309164911053126130864589542140823684068414351622554117077387498819889441373973156596663742549798997739739818594080622027379880314278201881341695601412534917197345991836322646172268609850323157309277449839L, 512, 6430470634703752752410865118713512102273240450186720678582719773307245425439795018835094838171454393910107856337743886319396544382771488797495287565431789565914797925117124451292370339814770378298130765557283040202149138450222342144790542310174532627018946820721116849808896185555115650699502252019810137138661202289232657347537636031798052620838832324602613187586907293646530610877952048890046729989059412110648213600146045233277015646822494474807562255270052325042929699002216633761536108800580880403467146230213318196826190179231978188794163889939327438074942415151273248971589462645532957964702863891474130785207L)
enc = 3454085346574987225897831843027819308224167386932731290492223099682362777177850503131523581825210489935713468476347858275690317267310391889881249451570639374942758474027300505459731033746919130301261750148953120742881314068224134546119933825907008577335596198633834951391140360579708607628376848859139717083973348586284471677027943816798571794184743064521079266501342213050814388151710070528752227349444352969848344075816569840832978948650595425435333679490829143988877536836692298581315990015291505643844132256649193564238372544816803818259019432171003583987935610027762164808999385479216326262990988010754441786843

First weakness: the prime $p$ has the form $p=2^{512}h+1$ for some random 512-bit number $h$ . Immediately we can recall that knowing half of the bits of a prime leads to factorization via the Coppersmith attack. However, the attack complexity grows rather fast as the number of known bits approaches the half. And in this challenge, we have exactly half, so it's rather tough.

Second weakness: the private exponent $d$ is small, which again would lead to factorization via the Boneh-Durfee attack, as long we have $d \le n^{0.292}$ . Unfortunately, similarly to the first weakness, we have $d$ very close to the bound. Applying this attack would be difficult again.

Can we combine the two weaknesses? Let's see! The following equation links together the exponents and the primes:

$ed = 1 + k\phi(n) = 1 + k(n-p-q+1),$ with another unknown

$k \le d$ .

Note that from the least significant half of $p$ we can always derive the least significant half of $q$ :

$q \equiv n/p \equiv n/1 \pmod{2^{512}}.$ Funnily, it matches the 512 least significant bits of

$n$ !

It is typical to reduce the main equation modulo $e$ when it's large (as in the Boneh-Durfee attack). Let also

$q=2^{512}q_1 + q_0,~~ c=n-q_0,~~ s=h+q_1.$ Then

$1 + ck - 2^{512}ks \equiv 0 \pmod{e}.$

Now that we've got rid of $d$ ... Let's go back to $\mathbb{Z}$ ! Let's multiply the congruence by a magic constant such that all overflows go away. (By the way, this simplified Coppersmith-like technique was actually described by Håstad in 1988).

Does such a constant exist? There is a simple rule of thumb: sum up the unknown bits in each monomial, it should be less than size of the modulus. We know that $k \le d < N^{0.292} \approx 2^{600}$ , and $k(h+q_1) \le 2^{513 + 600}$ , totaling in 1713 bits, while $e$ is close to $n$ , that is 2048 bits. All is well!

We build the lattice spanned by the rows of the following matrix:

$M = \begin{pmatrix} 1 & c & -2^{512} \\ 0 & e & 0 \\ 0 & 0 & e \end{pmatrix},$ and we scale the coordinates (columns of

$M$ ) according to the maximum values of respective unknowns:

$1$ for the monomial

$1$ ,

$2^{600}$ for the monomial

$ck=k(n-q_0)$ and

$2^{600+513}$ for the monomial

$ks=k(h+q_1)$ .

In [3]:

q0 = n % 2**512
c = n - q0

m = matrix(ZZ, 3, 3)
m.set_row(0, [1, n-q0, -2**512])
m[1,1] = m[2,2] = e

# scale
ws = [1, 2**600, 2**(600+513)]
for i, w in enumerate(ws):
    m.set_column(i, m.column(i) * w)

# reduce
m = m.LLL()

# unscale
for i, w in enumerate(ws):
    m.set_column(i, [a // w for a in m.column(i)])

v1, v2, v3 = m[0]
print("logs", *["%.2f" % math.log(abs(int(v)), 2) for v in m[0]])

logs 1873.48 1275.86 765.42

We now have an equation

$v_1 + v_2k + v_3ks = 0$ with known

$v_1,v_2,v_3$ . Let's reduce it modulo

$v_3$ to get rid of

$s$ and recover

$k$ .

In [4]:

mod = abs(v3) # can be negative, no problem
k = (-v1 * inverse_mod(v2, mod)) % mod
assert 0 <= k <= 2**600
print("k", k)

k 216044433968486211309048459396103283041730279225632068616903982472942572502334736404159307637404900676003426000595797121702299425713710848996850411476714168260771030918399955451677

Now we can recover $d$ by inverting $e$ modulo $k$ , except that $k$ is a bit smaller than $d$ so we would need to add a small multiple of $k$ .

In [5]:

for i in range(100):
    d = inverse_mod(e, k) + i*k
    if pow(2, e * d, n) == 2:
        break
else:
    raise
print("d", d)

d 656678790957846493325522295512552964642389087863533147035026289582702006575160547700839896514211327495319861876561572664042587635691012861464469207125743152896724283300906291591687

Finally, we can factorize $n$ using knowledge of $e,d$ .

In [6]:

for i in range(100):
    p = gcd(n, int(pow(2, (e * d - 1)//2**i, n)) - 1)
    if 1 < p < n:
        break
else:
    raise
q = n // p
print("p", p)
print("q", q)

p 172526663954288094402684831904894709672893572566091967600912295188703612481353322028634215632716054996456966521811183881911243075756946478351847294224868653426239553732224998655197250350521485873159799384081746532388926378144538953342220772420070151311687280144185404913564138987585944163712571082540021959643
q 113291269309056938092068497035577523945787720114947464982138940595000056469162234376505618425566254410753094291703374184880373819234307147701908263467938592313201528637552669061051638788295404349743246277302794476046653862387813290948923123537614303866508465481425893261054183642634492637353626231145771302913

Now, I lied to you: this is not an RSA challenge, because the flag is not encrypted by $e$ -exponentiation! Instead, it turns out to be a generalized Goldwasser-Micali cryptosystem. Anyway, the message is easy to recover by doing discrete log in the subgroup of order $2^{512}$ .

In [7]:

msg = 0
if (p-1) % 2**512 != 0:
    p, q = q, p
h = (p-1) >> 512
target = pow(enc, h, p)
gen = pow(y, h, p)
for i in range(512):
    targeti = pow(target, 2**(511-i), p)
    geni = pow(gen, 2**(511-i), p)
    if pow(geni, msg, p) != targeti:
        msg += 1 << i       
print(long_to_bytes(msg).decode())

CCTF{9en3r4liZed_adDi7iv3lY_h0mOmorphiC_Goldwa5ser_Mic4Li}