https://github.com/sh1k4ku/ctf-challenge/tree/main/0CTF2024


dbot


Level 0:

Setup:

from Crypto.Util.number import *
flag = b'flag{test}'
ROUND = 80
primes = [getPrime(512) for _ in range(3)]

N = prod(primes)
phi = prod([(pp - 1) for pp in primes])
d = inverse(0x10001, phi)
m = bytes_to_long(os.urandom(N.bit_length() // 8 - 2))
c = pow(m, 0x10001, N)


#idx = int(input("Choose one prime you prefer: "))
idx = 0 # doesn't matter...
assert idx in list(range(len(primes))), "No such prime"
mod = primes.pop(idx)
print(f"Here is your prime: {mod}")
print(f"{c = }")
print(f"{N = }")

a = [getrandbits(496) for _ in range(ROUND)]
b = getrandbits(248)
c = [getrandbits(496) for _ in range(ROUND)]
e = b
ph1 = [prod([(primes[0] + a[i]), (primes[1] + b)]) for i in range(ROUND)]
ph2 = [prod([(-primes[0] + c[i]), (primes[1] + e)]) for i in range(ROUND)]

for i in range(ROUND):
    x0 = randrange(0, N)
    x1 = randrange(0, N)
    print(f"{x0 = }")
    print(f"{x1 = }")
    v = int(input("Give me v: "))
    m0 = (pow(v - x0, d, mod) + ph1[i]) % mod
    m1 = (pow(v - x1, d, mod) + ph2[i]) % mod
    print(f"{m0 = }")
    print(f"{m1 = }")


m_ = int(input("Give me m: "))
if m_ == m:
    print("Good job!")
else:
    print("Try again!")


We have some N = p*q*r, we’re given one of the factors, and goal is to factor N so we can solve m.

First we need to choose some useful v.

A neat trick exists, v=(x0+x1)/2 (% mod)

    v = (x0+x1) * pow(2, -1, mod) #int(input("Give me v: "))
    m0 = (pow(v - x0, d, mod) + ph1[i]) % mod
    m1 = (pow(v - x1, d, mod) + ph2[i]) % mod
    assert m0 == (pow((x0+x1)*pow(2, -1, mod) - x0, d, mod) + ph1[i]) % mod
    assert m1 == (pow((x0+x1)*pow(2, -1, mod) - x1, d, mod) + ph2[i]) % mod
    assert m0 == (pow((-x0+x1)*pow(2, -1, mod), d, mod) + ph1[i]) % mod
    assert m1 == (pow((-x1+x0)*pow(2, -1, mod), d, mod) + ph2[i]) % mod
    assert (m0+m1) % mod == (ph1[i] + ph2[i]) % mod


But in fact, no tricks are needed haha, because we can simply calculate d % phi(mod) instead of % phi(N).

Maybe the author didn’t consider this.

    v = 69420 # anything arbitrary
    m0 = (pow(v - x0, d, mod) + ph1[i]) % mod
    m1 = (pow(v - x1, d, mod) + ph2[i]) % mod

    d2 = pow(0x10001, -1, mod - 1)
    assert ph1[i] % mod == (m0 - pow(v-x0, d2, mod)) % mod
    assert ph2[i] % mod == (m1 - pow(v-x1, d2, mod)) % mod


Next, if you add each ph1i + ph2i, you can factor out q+b, and p disappears

p, q = primes[0], primes[1]
for ai, ci, ph1i, ph2i in zip(a, c, ph1, ph2):
    assert ph1i + ph2i == (p + ai)*(q + b) + (-p + ci)*(q + b)
    # factor out q+b
    assert ph1i + ph2i == (ai + ci)*(q + b)


Then you can cancel q+b by dividing consecutive terms.

You get a system of 79 equations and 80 small unknowns, solveable with LLL.

p, q = primes[0], primes[1]
r = mod
for i in range(79):
    assert ph1[i] + ph2[i] == (a[i] + c[i])*(q + b)
    assert ph1[i+1] + ph2[i+1] == (a[i+1] + c[i+1])*(q + b)
    # divide and cross multiply
    assert (ph1[i+1] + ph2[i+1]) * (a[i] + c[i]) == (ph1[i] + ph2[i]) * (a[i+1] + c[i+1])

load('https://gist.githubusercontent.com/Connor-McCartney/952583ecac836f843f50b785c7cb283d/raw/5718ebd8c9b4f9a549746094877a97e7796752eb/solvelinmod.py')
aa = [var(f'a{i}') for i in range(80)]
bounds = {ai: 2**496 for ai in aa}
eqs = []
for i in range(79):
    lhs = (ph1[i+1] + ph2[i+1]) * (aa[i] + c[i])
    rhs = (ph1[i] + ph2[i]) * (aa[i+1] + c[i+1])
    eqs.append((lhs==rhs, r))
print('solving...')
sol = solve_linear_mod(eqs, bounds)
recovered_a = list(sol.values())
assert a == recovered_a


With all ai now recovered, you can solve q+b mod r easily:

assert ph1[0] + ph2[0] == (a[0] + c[0])*(q + b)
z = ((ph1[0] + ph2[0]) * pow(recovered_a[0] + c[0], -1, r)) % r
assert z == (q+b) % r


Now we can use coppersmith to recover q. There are 2 cases to consider, when q>r and when q<r


load('https://raw.githubusercontent.com/Connor-McCartney/coppersmith/refs/heads/main/coppersmith.sage')
PR.<bb> = PolynomialRing(Zmod(N//r))
print(q<r)
if q<r:
    assert z == q+b
    f = z-bb
else:
    assert z == q+b-r
    f = z+r-bb
for m in range(1, 20):
    roots = univariate(f, X=2**248, beta=0.4, m=m)
    print(m, roots)


m=17 seems good.


Level 1:

Setup:

from Crypto.Util.number import *

primes = [getPrime(512) for _ in range(4)]
ROUND = 80

N = prod(primes)
phi = prod([(pp - 1) for pp in primes])
d = inverse(0x10001, phi)
m = bytes_to_long(os.urandom(N.bit_length() // 8 - 2))

c = pow(m, 0x10001, N)

#idx = int(input("Choose one prime you prefer: "))
idx = 0 # doesn't matter...
assert idx in list(range(len(primes))), "No such prime"
mod = primes.pop(idx)
#print(f"Here is your prime: {mod}")
#print(f"{c = }")
#print(f"{N = }")

a = [getrandbits(160) for _ in range(ROUND)]
b = a
c = [ai + 1 for ai in a]
e = c
ph1 = [prod([(primes[0] + a[i]), (primes[1] + b[i])]) for i in range(ROUND)]
ph2 = [prod([(primes[0] - c[i]), (primes[1] + e[i])]) for i in range(ROUND)]


We now have 4 primes not 3, I’ll call them p, q, r, s with s being the given mod.

p, q = primes[0], primes[1]
for i in range(79):
    assert ph1[i] == (p + a[i]) * (q + a[i])
    assert ph2[i] == (p - c[i]) * (q + c[i])
    # since every c is just a+1,
    assert ph2[i] == (p - a[i] - 1) * (q + a[i] + 1)


    assert ph1[i+1] == (p + a[i+1]) * (q + a[i+1])
    assert ph2[i+1] == (p - a[i+1] - 1) * (q + a[i+1] + 1)

    # subtract and factor
    assert ph1[i+1] - ph1[i] == (a[i+1] - a[i]) * (a[i]+a[i+1]+p+q)
    assert ph2[i+1] - ph2[i] == (a[i] - a[i+1]) * (a[i]+a[i+1]+(q-p)+2)


If you use the inintended trick of calculating d % mod, you have (79*2) equations and only 82 unknowns so it can be solved trivially without LLL haha.

For example, yeeting into groebner spits out p:

s = mod

print(f'{p = }')
nms = [f'a{i} ' for i in range(80)] + ['p', 'q']
PR = PolynomialRing(Zmod(s), 82, names=nms)
p, q = PR.gens()[-2:]
a = PR.gens()[:80]
eqs = []
for i in range(79):
    eqs.append(ph1[i+1] - ph1[i] - (a[i+1] - a[i]) * (a[i]+a[i+1]+p+q))
    eqs.append(ph2[i+1] - ph2[i] - (a[i] - a[i+1]) * (a[i]+a[i+1]+(q-p)+2))
for p, _ in Ideal(eqs).groebner_basis()[0].univariate_polynomial().roots():
    p = int(p)
    if not is_prime(p):
        p += s
    if is_prime(p):
        break
print(f'{p = }')




Signin


The first time LLL has betrayed me…

It seems the stronger BKZ is needed (A generalisation of LLL, LLL ~= BKZ(block_size=2)).

A small discusison:

ConnorM (me):
is there any heuristic to choose BKZ block size? or just trial and error

grhkm:
Vibes

tl2cents:
maybe the root  hermite factor δ. The shortest LLL/BKZ-reduced vector satisfies ||b1|| < δ^n det(L)^(1/n). LLL has a practical roote hermite factor of 1.021 and for BKZ-20, it is 1.013.

grhkm:
this should be a sage feature :P

tl2cents:
according to this paper, it seems like an algorithmic thing. https://www.iacr.org/archive/eurocrypt2008/49650031/49650031.pdf


Solve:

The error terms e are generated by this suspicious ternary function:

import random
import numpy as np
from string import ascii_lowercase

def ternary_sample(n, ternaryL, SecureRandom):
    return [ternaryL[int(_)] for __ in range(n // 5) for _ in np.base_repr(ord(SecureRandom.choice(ascii_lowercase)), 3)]

m = 220
e_L = [0, 101, 731]
R_e = random.SystemRandom()
e = np.array(ternary_sample(m, e_L, R_e))
print(e.tolist())


If you look at this, another observation you can make it the base 3 representation of all the ascii chars all begin with 1:

while True:
    print([np.base_repr(ord(random.choice(ascii_lowercase)), 3)])


So, every 5th element of e will be ternaryL[1] which is 101.

Another observation:

q = next_prime(1337)
assert 2*731 % q == 101
print([int(i) * pow(731, -1, q) % q for i in e])
print([int(i) * pow(731, -1, q) % q for i in e][::5])

Now e becomes even smaller, all either 0 1 or 2 and every 5th being 2. If you count every 5th, we have 44 known ei.

We can also subtract 1 from our equations to center ei at either -1, 0 or 1.


for Ai, bi, ei in zip(A, b, e):
    assert bi == (sum([aa*ss for aa, ss in zip(Ai, s)]) + ei) % q
    z = pow(731, -1, q)
    assert (- sum([aa*z*ss for aa, ss in zip(Ai, s)]) + bi*z - 1) % q == (ei*z-1) % q
    assert (ei*z-1) % q in [-1%q, 0, 1]


Test (block_size as low as 6 can also work!):

n = 137 - 44
m = 220 - 44 # samples
q = next_prime(1337)

s = random_vector(GF(q), n)
A = random_matrix(GF(q), m, n)
e = [randint(0, 2) for _ in range(m)]
print(f'{e = }')
e = vector(GF(q), e)
b = A * s + e

M = (
    A.change_ring(ZZ)
    .augment(vector([i-1 for i in b]))
    .augment(diagonal_matrix([q]*m))
    .T
)
M = M.BKZ(block_size=12)
for row in M:
    if row != 0:
        break
for row in [row, -row]:
    recovered = [i+1 for i in row]
    print(f'e {recovered = }')