This is the main function. It basically asks for a key that should not exceed 30 bytes, and then runs several getNum calls on a certain string "27644437104591489104652716127".
getNum(s, i, j) simply seems to take the argument string s and cut it starting from the i-th byte and keeping j bytes. It then converts it into a integer.
Let's put everything together ; the big number is divided into 5 parts: 27644437, 10459, 1489, 1046527, 16127, and for each of these, the program calculates our input, which has to be a number less than 30 digits, modulus the part. It then tests if it is equal to a certain hardcoded value. Here are the conditions that need to be reunited:
s = 213 mod 27644437
s = 229 mod 10459
s = 25 mod 1489
s = 83 mod 1046527
s = 135 mod 16127
So it happens that all these moduli are co-prime, so we can use the Chinese Remainder Theorem to compute s. You can check the full script to see how it is computed.
We find that the lowest solution for s is 3087629750608333480917556.
Once we entered the key, we are asked for a password, and there is a call to func2(password, s, "27644437104591489104652716127").
So basically what this does is, we concat s with 27644437104591489104652716127 and then we append "80" (the 12344 decimal). We obtain a string v3 = "30876297506083334809175562764443710459148910465271612780".
Then some loops will compare each character of our password to a certain value in "matrix". Looking it up on IDA, matrix is a 10000-byte chunk of ascii characters, from which I dumped the contents in matrix.txt.
The only thing that is left for us to do is to calculate all the indexes that will be read in the matrix to figure out the password. Here's the final keygen:
from functools import reduceimport binasciidefchinese_remainder(n,a): s =0 prod =reduce(lambdaa, b: a*b, n)for n_i, a_i inzip(n, a): p = prod // n_i s += a_i *mul_inv(p, n_i)* preturn s % proddefmul_inv(a,b): b0 = b x0, x1 =0,1if b ==1:return1while a >1: q = a // b a, b = b, a % b x0, x1 = x1 - q * x0, x0if x1 <0: x1 += b0return x1a = [213,229,25,83,135]n = [27644437,10459,1489,1046527,16127]N =27644437104591489104652716127s =chinese_remainder(n, a)matrix =open('matrix.txt', 'r').read()matrix = matrix.replace(' ', '').replace('\r', '').replace('\n', '')matrix = binascii.unhexlify(matrix)v12 =str(s)+str(N)+"80"v12 =list(map(int, list(v12)))v8 =0v10 =len(v12)//2password =b""while v8 <len(v12)//2: q_ =100*(10*v12[v8]+v12[v8+1])+10*v12[v10]+v12[v10+1] password +=bytes([matrix[q_]]) v8 +=2 v10 +=2v9 =0v11 =len(v12)//2while v9 <len(v12)//2: v4 =10* v12[v9]+ v12[v9 +1] v5 =10* v12[v11]+ v12[v11 +1] password +=bytes([matrix[100*(v4**2%97)+v5**2%97]]) v9 +=2 v11 +=2print(s, password)
╭─face0xff@aniesu-chan ~/ctf/pragyan/vault
╰─$ ./vault
Enter the key: 3087629750608333480917556
Enter password: R3v3rS1Ng_#s_h311_L0t_Of_Fun
Your Skills are really great. Flag is:
pctf{R3v3rS1Ng_#s_h311_L0t_Of_Fun}
Enjoy!
Note: actually, there are more than 100000 correct (key, password) couples. Indeed, the solutions to the modular system of equations are all congruent modulo the product of the five integers. I lost a lot of time because I was looking for a 30-digit key instead of simply choosing the lowest solution, which yields a "readable" "flag-looking" password flag.
