**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.read_until(b'> ')

sc.write(str(x).encode()+b"\n")

d = sc.read_until(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}```