Aspiring Cryptology Researcher


dblp icon

Sage Math notes for CTF Crypto

Me and my friends at SDSLabs participated in BSides Ahmedabad 2021 CTF, and the outcome of the CTF was not something I liked, I found the crypto side a bit weak. The two problems I couldn’t solve (ecc-rsa and there-were-eleven) were not that hard, but my lack of Sagemath experience was a bit of reason why I couldn’t do it.

So here it is, my notes on Sage math.

Choose correct field #

For RSA and any modular math, use Zmod(p).

F = Zmod(p)

Polynomial Fields #

We want to make a field of polynomials where the arithmetic is happening over the F field and has variables x, y, z

PR.<x, y, z> = PolynomialRing(F)


PR = PolynomialRing(F, 3, 'x,y,z')
x, y, z = PR.gens()

Solving multivariate polynomials over Zmod(p) #

One might be tempted to use solve_mod function to solve a system of equations over a modulo. But if you have a special case when -

  1. Functions are multivariate polynomials.
  2. p is huge

In this case, solve_mod sometimes fails with Overflow Error. Instead, use Groebner Basis of the polynomials.

f1 = x*y + x^2 - 88
f2 = y^2 - z^2 + 51
f3 = z^2 - z + x*y - 102
I = (f1, f2, f3)*P

(This is a random example and doesn’t print anything good, but when equations are well formed the basis literally spits out the solution).

What is Groebner Basis? #


Chinese remainder theorem #

CRT is a useful function that given moduli n1, n2, n3... and respective remainders r1, r2, r3..., it finds a number m modulo n1*n2*n3... such that m = ri mod ni for all i.

m = crt([r1, r2, r3], [n1, n2, n3])

Lagrange Interpolation #

Lagrange interpolation finds a polynomial f such that given m pairs of (xi, yi), f(xi) = yi. Degree of f is at max m-1

shares = [(1, 1651293975450381579706844999808202297670211173037061827272908790114230592434748044848097133563469251678879059156225205298834971071359017469397331605782920), (2, 49656064002974834481096383104316375265711545391722811288216446968986145936494966876404160910407919885451814058823146922107458035910700220495010462147112), (3, 1481214561214496310917942246038921499126047497749957535731608952096552856013930232284898279007009260107597472601959627310496773682697020898442717240484400), (4, 1950790377868548708758723604473108315857898618124646291056275632619091046294238343215502355242288776617394025418770078552886012721353626716473759644786481)]

shares = [(F(x), F(y)) for x,y in shares ]
reconstructed_polynomial = PR.lagrange_polynomial(shares)

Always remember to convert the number to the correct field element!

Polynomial GCD #

When two polynomials are known to have a common root, the best way to get that root is by calculating the polynomial gcd. Passing two polynomial objects in gcd could work but is not fast. Use half-GCD algorithm.

(Source: https://github.com/death-of-rats/CTF/tree/master/Dice2021/plagiarism)

def hgcd(a0,a1):
    if a1.degree() <= (a0.degree()//2):
        return np.array([[1,0],[0,1]])
    m = a0.degree()//2
    X = a0.variables()[0]
    b0 = a0 // X**m
    b1 = a1 // X**m
    R = hgcd(b0,b1)
    [d,e] = (R.dot(np.array([a0,a1]).transpose())).transpose()
    ff = d % e
    m = m // 2
    g0 = e // X**m
    g1 = ff // X**m
    S = hgcd(g0,g1)
    q = d // e
    return S.dot(np.array([[0,1],[1,-q]])).dot(R)

def gcd(a0,a1):
    while True:
        print(a0.degree(), end=", ", flush=True)
        if a0 % a1 == 0:
            return a1
        if a0.degree() == a1.degree():
            a1 = a0%a1
        R = hgcd(a0,a1)
        [b0,b1] = R.dot(np.array([a0,a1]).transpose()).transpose()
        if b0%b1==0:
            return b1
        c = b0 % b1
        a0 = b1
        a1 = c

Lattices #


Coppersmith short-pad attack #