Tags: crypto sage interpolation lagrange

Rating: 4.7

# Crypto - Substitution
> Source


#!/usr/bin/python

from functools import reduce

with open("flag", "r") as f:
key = [ord(x) for x in f.read().strip()]

def substitute(value):
return (reduce(lambda x, y: x*value+y, key))%691

print("Enter a number and it will be returned with our super secret synthetic substitution technique")
while True:
try:
value = input("> ")
if value == 'quit':
quit()
value = int(value)
enc = substitute(value)
print(">> ", end="")
print(enc)
except ValueError:
print("Invalid input. ")

Given an oracle that permits to get the output of substitute function, our job to get the flag from those outputs.

####Substotute(value)
By analyzing this function, I noticed that it simply calculates: S(x) = ord(flag[0]) + ord(flag[1]) * x^1 + ord(flag[2]) * x^2 + ... + ord(flag[n-1]) * x^n-1 mod 691 where n is length of the flag and x is the input value. (Using substitution technique)
Obviously this is a polynomial which its coefficients are the chars of flag. We have to get those coeffs and reconstruct the polynomial. A very known way is using [Lagrange Interpolation](https://coast.nd.edu/jjwteach/www/www/30125/pdfnotes/lecture3_6v13.pdf) in finite field.
So after gathering 691 points.

from telnetlib import Telnet #using this library bcuz pwntools didn't work on the google colab
host,port = "crypto.2021.chall.actf.co", 21601

def substitute(x):
sc.write(str(x).encode()+b"\n")
return int(d.decode().lstrip('>>'))

points = []
sc = Telnet(host,port)
for i in range(691):
points.append((i,substitute(i)))
print(points)
sc.close()


[(0, 125), (1, 492), (2, 670), (3, 39), ... , (688, 130), (689, 487), (690, 18)]

Using [SageMathCell](https://sagecell.sagemath.org/) we can reconstruct the polynomial in no time (fortunately SageMath handles Lagrange Interpolation in finite fields).


F = GF(691)
points = ...
R = F['x']
print(R.lagrange_polynomial(points))


97*x^39 + 99*x^38 + 116*x^37 + 102*x^36 + 123*x^35 + .. + 99*x^4 + 102*x^3 + 54*x^2 + 57*x + 125

We can notice that the coeffs are in ASCII range. Gather them and we get the flag:
actf{polynomials_20a829322766642530cf69}