Kanav

Aspiring Cryptology Researcher

@kanav99

# 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)


or

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
print(I.groebner_basis())


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

TODO

## 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()
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
#print(a0.degree())
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


TODO

TODO