Rating:
DESCRIPTION
My friend Shamir has used this special encoding technique to protect the precious
Flag Can you help me decode it?
```
from sympy import randprime
from random import randrange
def generate_shares(secret, k, n):
prime = randprime(secret, 2*secret)
coeffs = [secret] + [randrange(1, prime) for _ in range(k-1)]
shares = []
for i in range(1, n+1):
x = i
y = sum(c * x**j for j, c in enumerate(coeffs)) % prime
shares.append((x, y))
return shares, prime
k = 3
n = 5
flag = open('flag.txt', 'rb').read().strip()
for i in flag:
shares, prime = generate_shares(i, k, n)
print(shares,prime,sep=', ')
```
We have given this Python program and this output file.
So, as we can see there is the array of shares and given the prime number by which the
shares are calculated.
For the solution I tried making the sample flag.txt file which contains all the possible
characters which can be in the flag which will give me the output according to the different
prime numbers and coeff array.
Flag.txt file consist of
“abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890a!@#$%^&*()_+-
=[]{}:<>?,./|”
By seeing this code we can see that the coeff array in the generate shares function has the
ascii of the character, and two random numbers between the range of 1 to prime.
The code which I made to try to brute force is :
```
from sympy import randprime
from random import randrange
def generate_shares(secret, k, n):
prime = 107
for k1 in range(prime):
for k2 in range(prime):
coeffs = [secret, k1, k2]
shares = []
for i in range(1, n+1):
x = i
y = sum(c * x**j for j, c in enumerate(coeffs)) % prime
shares.append((x, y))
yield shares, prime
k = 3
n = 5
flag = open('flag.txt', 'rb').read().strip()
for i in flag:
for shares, prime in generate_shares(i, k, n):
if(shares[0]==(1, 76) and shares[1]==(2, 31)) and shares[2]==(3,
58) :
print(chr(i), shares, prime, sep=", ")
```
In this code we are taking the values of three shares and the prime number according to the
set given in output.txt and it is checking every possible value from the flag.txt and
comparing with every shares generated by the different values of coeffs array. If it matches
it will print the character that gets matched from flag.txt
```Flag: VishwaCTF{l4gr4ng3_f0r_th3_w1n!}```
