# 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}```