DESCRIPTIONMy friend Shamir has used this special encoding technique to protect the preciousFlag Can you help me decode it?
```from sympy import randprimefrom random import randrangedef 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, primek = 3n = 5flag = open('flag.txt', 'rb').read().strip()for i in flag: shares, prime = generate_shares(i, k, n) print(shares,prime,sep=', ')```
![image](https://user-images.githubusercontent.com/76834257/229894872-a3c0d887-e745-4498-9cb7-4171b4688b2b.png)
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 theshares are calculated.
For the solution I tried making the sample flag.txt file which contains all the possiblecharacters which can be in the flag which will give me the output according to the differentprime 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 theascii 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 randprimefrom random import randrangedef 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, primek = 3n = 5flag = 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 theset given in output.txt and it is checking every possible value from the flag.txt andcomparing with every shares generated by the different values of coeffs array. If it matchesit will print the character that gets matched from flag.txt
```Flag: VishwaCTF{l4gr4ng3_f0r_th3_w1n!}```