As well as the main CTF at BSides Canberra, there was also a gacha CTF, where you got given random easier challenges. Solving these gave you points separate to the main CTF, which you could exchange for merch. I loved this and went hard into getting as much merch as possible.

Pictured: all the really cool merch I got

I wasn’t planning on doing a write-up for any of these challenges, but I was trying to explain the last RSA challenge - rsa67 - and I fumbled at explaining it beyond “just put it in a lattice then LLL to get flag”. This is my attempt at explaining it more than that :)

challenge

# This is the final boss of the series. You are given the integer part of p^(6/7).
#
# Hint: How many of the top bits of p can you recover? Can you recover the rest?
#
# SageMath is recommended for this challenge.

from Crypto.Util.number import bytes_to_long, getPrime
from gmpy2 import iroot

FLAG = b"skbdg{??????????????????????????????????}"
m = bytes_to_long(FLAG)

p = getPrime(256)
q = getPrime(256)
n = p * q
e = 65537
c = pow(m, e, n)

p67 = int(iroot(p**6, 7)[0])

print(f"{n = }")
print(f"{e = }")
print(f"{c = }")
print(f"{p67 = }")

"""
n = 7202182629848166191658914566003001457751483795584620856835111901303304263504952211013993399973448245877364741537562098590809153440623638773383687363022263
e = 65537
c = 5714427688003899389515016198250334401813386721154379130442076106903838595793778491204674265545257524637861031214521891174085517417865058936030312125923140
p67 = 892597420992830084952632837032489689740253740224086714221869385416
"""

solution + Coppersmith’s attack

rsa67 uses Coppersmith’s attack to find the rest of the value for p. When you’re using Coppersmith’s, you’re taking a polynomial, and then finding small solutions for the polynomial mod n.

Having a polynomial sounds weird, however if you think about this in the form of the equation p = x + approx_p then that’s going to have a solution for x where that equation = 0 mod n :)

Coppersmith’s method/attack basically:

• Takes this polynomial,
• Finds a bunch of other polynomials that have the same small root/s (i.e. being 0 mod n), and
• Reduces the polynomials down to try to find one that is easier to find a small root of.

This is done using lattices, since they’re a good and efficient way to do this sort of linear algebra on integers.

When making the equations of this, some things you may encounter are:

• We need to take into consideration that we know less than half of the prime, so the other prime - q - is about sqrt(n). if you’re using a library like SageMath (which you should, Coppersmith’s is big to implement >.<) this is going to be related to the value beta, which is the lower bound on what the unknown value of x is. We set as 0.5, (as you want q to be greater than n^beta).
• This matters because we also have the value X (common notation but also a bit confusing because our variable is x…) which is basically the maximum value that the root can be. I think this is usually ceil(n**((beta**2/d) - (1/8)), where d is the degree of the polynomial - which in our case is just 1, so this value is n^(1/8).

When I was solving this I did a bit of a test to figure out what my approx. number was and how many bytes I knew of the prime:

from Crypto.Util.number import getPrime
from gmpy2 import iroot

def test():
    p = getPrime(256)
    p67_1 = int(iroot(iroot(p**6, 7)[0] ** 7, 6)[0])
    p67 = bin(p67_1)
    p = bin(p)
    print(p, len(p), p67, len(p67))
    for i in range(max(len(p), len(p67))):
        if p[i] != p67[i]:
            return i
    return max(len(p), len(p67))

for _ in range(10):
    print(test())

This was my code to test how many bytes we had - it ended up being pretty consistently ~220 which was most of the prime!!

The math of this is interesting and confusing but it’s basically “turn this into a lattice and then lattice reduce it”.

You end up with a matrix (or the matrix representation of a lattice) where the values in a row are coefficients for x, and all the rows will have x as a root - which means when you reduce it, you get an equation with smaller coefficients, and it’s easier to solve for a small value of x.

This was my code and solution :)) after I cleaned it up to not suck to look at

from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot
from sage.all import *

n = 7202182629848166191658914566003001457751483795584620856835111901303304263504952211013993399973448245877364741537562098590809153440623638773383687363022263
e = 65537
c = 5714427688003899389515016198250334401813386721154379130442076106903838595793778491204674265545257524637861031214521891174085517417865058936030312125923140
p67 = 892597420992830084952632837032489689740253740224086714221869385416

p67_1 = int(iroot(p67 ** 7, 6)[0])

z = Zmod(n)
P = PolynomialRing(z, names=('x',))
(x,) = P._first_ngens(1)

f = x + p67_1
roots = f.small_roots(beta = 0.5) # this is sages implementation of coppersmiths!
diff = int(roots[0])

p = (p67_1 + diff)
q = n // p

d = pow(e, -1, (p - 1) * (q - 1))
print(long_to_bytes(pow(c, d, n)))

If you’re interested in learning more about how this attack works, I can recommend A Gentle Tutorial for Lattice-Based Cryptanalysis, which is also written by one of the members of skateboarding dog :)