This time, in the team Whatever, we solved some Crypto problems, and since they were quite interesting, I decided to briefly document the solutions.

Crypto#

ezdlp#

from Crypto.Util.number import *
from math import prod
from secret import flag

def keygen(pbits,kbits,k):
    p = getPrime(pbits)
    x = [getPrime(kbits + 1) for i in range(k)]
    y = prod(x)
    while 1:
        r = getPrime(pbits - kbits * k)
        q = 2 * y * r + 1
        if isPrime(q):
            return p*q, (p, q, r, x)

def encrypt(key, message):
    return pow(0x10001, message, key)

key = keygen(512, 24, 20)
flag = bytes_to_long(flag)
messages = [getPrime(flag.bit_length()) for i in range(47)] + [flag]
enc = [encrypt(key[0], message) for message in messages]

print(messages[:-1])
print(enc)

In this problem, $n=pq$ is used, where $q-1$ is a smooth number. Then, some $m_i$ are randomly generated and you are given the values of $y_i \equiv 65537^{m_i} \pmod{n}$, but you are not given the value of $n$.

First, we need to recover $n$. This part was actually quite simple for me because I recently created a challenge for ImaginaryCTF called No modulus, which uses the exact same concept of using LLL + gcd to obtain $n$ XDD.

After obtaining $n$, the next step is to factorize $n$. At first glance, it seems that $q-1$ is $2^{25}$ smooth, but in reality, because $512-24 \times 20 = 32$, there is an additional 32-bit factor. This extra factor prevented my original Pollard p-1 script from working, requiring me to find all 32-bit primes, which would take about ten hours with my Python script... (My method here is similar to the Two-stage variant mentioned on wiki, with $B_1=2^{25}, B_2=2^{32}$).

After some research, I found out about a magical command line tool called gmp-ecm that implements p-1, p+1, ecm, and supports many custom settings. After some study, I was able to generate this command:

echo 131158523227880830085100826212925738665356578827561846263073537503153187073136528966506785633847097997799377037969243883439723340886038624250936927221630287086602285835045356221763554989140952262353930420392663280482277832613695689454662506372252641564106136178637816827646124189347219273164844809807934422046441 | ecm -pm1 33554432 4294967296

Magically, it output the prime factor in about 15 seconds, so after that, solving the DLP in $\mathbf{F}_q$ gives the flag.

from Crypto.Util.number import *
import ast

with open('output.txt') as f:
    msgs = ast.literal_eval(f.readline())
    enc = ast.literal_eval(f.readline())

M = matrix(ZZ, msgs).T.augment(matrix.identity(len(msgs)))
M[:,0] *= 2^1024
M = M.LLL()
print(M[0])
print(M[1])
aa = product([ZZ(x)^y for x,y in zip(enc, M[0][1:])])
bb = product([ZZ(x)^y for x,y in zip(enc, M[1][1:])])
n = gcd(aa.numer() - aa.denom(), bb.numer() - bb.denom())
print(n)

# echo 131158523227880830085100826212925738665356578827561846263073537503153187073136528966506785633847097997799377037969243883439723340886038624250936927221630287086602285835045356221763554989140952262353930420392663280482277832613695689454662506372252641564106136178637816827646124189347219273164844809807934422046441 | ecm -pm1 33554432 4294967296

n = 131158523227880830085100826212925738665356578827561846263073537503153187073136528966506785633847097997799377037969243883439723340886038624250936927221630287086602285835045356221763554989140952262353930420392663280482277832613695689454662506372252641564106136178637816827646124189347219273164844809807934422046441
q = 12980311456459934558628309999285260982188754011593109633858685687007370476504059552729490523256867881534711749584157463076269599380216374688443704196597025947
p = n // q

m = GF(q)(enc[-1]).log(0x10001)
flag = long_to_bytes(int(m))
print(flag)

brand_new_checkin#

from Crypto.Util.number import *
from random import getrandbits
from secret import flag

def keygen():
    p = getPrime(512)
    q = getPrime(512)

    n = p * q
    phi = (p-1)*(q-1)

    while True:
        a = getrandbits(1024)
        b = phi + 1 - a

        s = getrandbits(1024)
        t = -s*a * inverse(b, phi) % phi

        if GCD(b, phi) == 1:
            break
    return (s, t, n), (a, b, n)


def enc(m, k):
    s, t, n = k
    r = getrandbits(1024)

    return m * pow(r, s, n) % n, m * pow(r, t, n) % n


pubkey, privkey = keygen()

flag = pow(bytes_to_long(flag), 0x10001, pubkey[2])

c = []
for m in long_to_bytes(flag):
    c1, c2 = enc(m, pubkey)
    c.append((c1, c2))

print(pubkey)
print(c)

This problem is based on CakeCTF 2022 - brand_new_crypto. The main differences are that it first encrypts the flag with standard RSA before byte-by-byte encryption, and it uses Python's random getrandbits for randomness, fixed at 1024 bits.

The initial part can be solved using the original challenge's method. The main difficulty lies in solving the RSA part. Due to the changes in randomness, it is clear that we need to reverse-engineer MT19937 to obtain $a$.

First, let's assume we have $a$ and see what we can do. From keygen, we can list two equations:

Rewriting the first equation, we get:

The only unknown here is $b$, so naturally, we want to eliminate $b$. Multiplying the first equation by $t$ and subtracting the second equation gives:

Thus, $at-as-t$ is a multiple of $\varphi(n)$. Knowing $\varphi(n)$ allows us to compute a usable private key $d$, so having $a$ solves the problem.

Next, we need to recover the random values. From enc, we know that when $m$ is known, we can obtain $r^s$ and $r^t$. Since $\gcd(s,t)=1$, we can use the common modulus attack to get $r$. Each $r$ is 1024 bits, and the problem provides a large number of samples, so using an MT19937 cracking tool should work.

... Initially, I thought so, but in practice, after obtaining $r$, I encountered many difficulties. It turns out that $r<n$ is not always true, and the common modulus attack actually gives $r \mod{n}$. Experiments showed that $r \mod{n}$ could be $r, r-n, r-2n$.

Since cracking MT19937 requires 624 32-bit outputs, and $1024 \div 32 = 32$, at least 20 $r$ values are needed ($20 \times 32 > 624$). However, each $r$ has three possibilities, resulting in $3^{20}$ brute force attempts, which is too large for a CTF.

I wrote a function (solve script's try_xx) to attempt to restore MT19937 and generate some outputs, comparing them with the actual $r \mod{n}$ to see how many bits match. Experiments showed that some xx (guessed inputs) had higher accuracy, so it might be possible to use better brute force methods to reduce the search space from $3^{20}$.

I used a method similar to a Genetic Algorithm. For details, see the code. This method effectively cracked MT19937, so I reversed it and brute-forced $a$, then used the previous method to compute the private key and get the flag.

from Crypto.Util.number import *
import ast
from sage.all import xgcd, gcd, matrix, ZZ
import gmpy2


def pow(a, b, c):
    return int(gmpy2.powmod(a, b, c))


with open("output.txt") as f:
    s, t, n = ast.literal_eval(f.readline())
    c = ast.literal_eval(f.readline())


def inverse(x, y):
    return pow(x, -1, y)

# decrypt
flagct = []
for (c1, c2) in c:
    for m in range(1, 256):
        if c1 == c2 == 0:
            flagct.append(0)
            break
        rs = c1 * inverse(m, n) % n
        rt = c2 * inverse(m, n) % n
        if pow(rs, t, n) == pow(rt, s, n):
            flagct.append(m)
            break
    else:
        raise ValueError("???")
    print(bytes(flagct))

# flagct = list(
#     b'\x08EZg\xbf\xa0\xeb\x9d\x81\x01\xa8\x96m\x97\x08I(\xed\xb5iQE\xdb\xf5\x8c\xbdcr!\xe6\xc9\xac\x0c\x16K\xa0\x0fr\xecM\x04\xe6\x87\x0f}9\x94\xcfa\x16\x87\x8f4\xcd\xcb\xa4\x0eq\xc3Q\x16\x928&\xe2\x18C\xafN\x87\xcc\x18\xc2D\x9d\x06\xbd"\xe7\xe8\xb7\x12\xb0\xb8CC\x9aM\xff\x12\x00\x05,\xeeopYC)mI\xb7\x81\xb6\x13\x0e\x8a\xc0\xd7\xd3\xd2\xa9\xe5vg.\xa4\xf3\xaa\x10f\x9c\xa4nS=O\xe9'
# )

# recover r
g, x, y = xgcd(s, t)
assert g == 1
assert x * s + y * t == 1
rrr = []
for m, (c1, c2) in zip(flagct, c):
    try:
        im = inverse(m, n)
        rs = im * c1 % n
        rt = im * c2 % n
        r = pow(rs, x, n) * pow(rt, y, n) % n
        rrr.append(r)
    except:
        break
print(len(rrr))

import sys

sys.path.append("./MT19937-Symbolic-Execution-and-Solver/source")
from MT19937 import MT19937, MT19937_symbolic
from XorSolver import XorSolver
import random

from functools import lru_cache


@lru_cache(maxsize=None)
def split1024(r):
    x = []
    for _ in range(1024 // 32):
        x.append(r & 0xFFFFFFFF)
        r >>= 32
    return x


def clone(rng):
    return MT19937(state=rng.state[:])


def grb1024(rng):
    ss = 0
    for i in range(1024 // 32):
        ss |= rng() << (i * 32)
    return ss



def randgen(n, prob=0.3, prob2=0.05):
    ar = []
    for _ in range(n):
        r = random.random()
        if r < prob2:
            ar.append(2)
        elif r < prob:
            ar.append(1)
        else:
            ar.append(0)
    return ar


def compare(x, y):
    cnt = 0
    for a, b in zip(f"{x:01024b}", f"{y:01024b}"):
        cnt += a == b
    return cnt


def try_xx(xx, n_cmp, return_rng=False):
    # xx: a list of 0, 1, 2
    rtmp = [r + x * n for r, x in zip(rr, xx)]
    data = []
    for r in rtmp:
        data += split1024(r)
    try:
        rng_clone = MT19937(state_from_data=(data, 32))
        # print("gj", xx)
        cr = clone(rng_clone)
        tot = 0
        for j in range(n_cmp):
            lhs = grb1024(cr) % n
            rhs = rrr[baseidx + j]
            cond = lhs == rhs
            cp = compare(lhs, rhs)
            tot += cp
            # print(j, cond, cp)
        # print(tot)
        if return_rng:
            return rng_clone
        return tot
    except Exception as ex:
        # import traceback
        # traceback.print_exc()
        pass


def mutate(xx):
    xx = list(xx)
    v = random.randint(0, 2)
    xx[random.randrange(len(xx))] = v
    return xx


baseidx = 0  # choose a starting index to start searching
rr = rrr[baseidx : baseidx + 20]
xx = [0] * 20
tot = 0
n_cmp = 40
# a shitty searching algorithm inspired by genetic algorithm
# try_xx is some sort of a fitness function
while tot < n_cmp * 1024:
    mut = [mutate(xx) for _ in range(10)] + [randgen(len(xx)) for _ in range(10)]
    res = [(ret, mx) for mx in mut if (ret := try_xx(mx, n_cmp)) is not None]
    res.sort(key=lambda x: x[0], reverse=True)
    # for r, mx in res:
    #     print(r, mx)
    if len(res) >= 1:
        tot, mx = res[0]
        print(tot, mx)
        xx = mx

rng_clone = try_xx(xx, n_cmp, return_rng=True)

# do some santiy check
cr = clone(rng_clone)
print(grb1024(cr) % n, rrr[baseidx])
cr = clone(rng_clone)
print([cr() for _ in range(1024 // 32)], split1024(rrr[baseidx] + xx[0] * n))

rng = clone(rng_clone)
rng.reverse_states(512 * (1024 // 32))
for i in range(512):
    ss = grb1024(rng)
    if s == ss:
        print("good")
        print(hex(s))
        print(hex(ss))
        a = prv
        print(hex(a))
        phik = s * a - t * a + t
        d = inverse(0x10001, phik)
        cc = bytes_to_long(bytes(flagct))
        m = pow(cc, d, n)
        print(long_to_bytes(m))
    prv = ss
# n1ctf{5255840f-9140-4479-950f-a3c03fe7f4cd}

babyecc#

from Crypto.Util.number import *
from secret import flag

m = Integer(int.from_bytes(flag, 'big'))

for _ in range(7):
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    while 1:
        try:
            a = randint(0,n)
            b = randint(0,n)
            Ep = EllipticCurve(GF(p), [a,b])
            Gp = Ep.lift_x(m) * 2
            Eq = EllipticCurve(GF(q), [a,b])
            Gq = Eq.lift_x(m) * 2
            y = crt([int(Gp[1]),int(Gq[1])],[p,q])
            break
        except Exception as err:
            pass
    print(n, a, b, y)

This problem randomly generates $n=pq$ and $a,b$ to get an elliptic curve $E: y^2 \equiv x^3+ax+b \pmod{n}$, then takes a point $P=(m,?)$ and gives you the y-coordinate of $2P$. The $m$ is fixed as the flag, and this process is repeated seven times, so there are seven sets of $n,a,b,y$.

The method is simple. For each set, set the coordinates of $P$ as unknowns. Using the elliptic curve definition, we get the first equation. Using the doubling formula and the given $y$, we get another equation. Using the resultant to eliminate the unknown y-coordinate of $P$, we get a 12th-degree polynomial $f_i(x)$ with $m$ as the root.

With seven sets, we get seven $f_i(x)$ and $n_i$. Using CRT, we get another $f(x)$ with $m$ as the root modulo $N$ ($N=\prod_{i=1}^{7} n_i$). Using Coppersmith, we get the flag.

For the CRT part, refer to CakeCTF 2021 - Party Ticket. This problem is similar to that one, and can be seen as an extension of the Hastad broadcast attack.

from Crypto.Util.number import *

with open("output.txt") as f:
    ar = []
    for line in f:
        n, a, b, y = map(ZZ, line.strip().split(" "))
        ar.append((n, a, b, y))


def double(x, y, a, b):
    s = (3 * x ^ 2 + a) / (2 * y)
    xr = s ^ 2 - 2 * x
    yr = y + s * (xr - x)
    return xr, yr


P.<mx, my> = QQ[]
eqs = []
for n, a, b, y in ar:
    eq1 = my ^ 2 - (mx ^ 3 + a * mx + b)
    _, yy = double(mx, my, a, b)
    eq2 = (yy - y).numerator()
    f = eq1.sylvester_matrix(eq2, my).det().univariate_polynomial()
    eqs.append(f)

ns = [n for n, a, b, y in ar]
Ti = [crt([1 if nn == n else 0 for nn in ns], ns) for n in ns]

N = product(ns)
ff = sum([f * ti for f, ti in zip(eqs, Ti)])
ff = ff.change_ring(Zmod(N)).monic()
set_verbose(1)
rs = ff.small_roots(epsilon=0.03)
print(rs)
m = int(rs[0])
print(long_to_bytes(m))
# n1ctf{7140f171-5fb5-484d-92f4-9f7ba02c33d0}