Sage Math notes for CTF Crypto
Posted on 07 Nov 2021
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 (
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
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 -
- Functions are multivariate polynomials.
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).
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
n1*n2*n3... such that
m = ri mod ni for all
m = crt([r1, r2, r3], [n1, n2, n3])
Lagrange Interpolation #
Lagrange interpolation finds a polynomial f such that given
m pairs of
f(xi) = yi. Degree of f is at max
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.
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
Coppersmith short-pad attack #