# SecureLinearFunctionEvaluation
## Challenge
> In this challenge we provide a sytem that calculates a * x + c in F_2^128 , where a and b are server supplied and x is client supplied. > To get the flag you have to find a and b. Server runs at: >> ```nc crypto2.ctf.nullcon.net 5000```>> file: [lfe.py](lfe.py)
### Solution
Let us analyze the server code. Two 128bit numbers *a*, *b* are generated. Then we get 128 ```cs``` random values that constrain our input *(g, y0, y1)*:
```math(y0 * y1) % p == cs```
Ok, so what happens to out input? For every set, the program gets random 2 numbers r0, r1 (mod p). Calculate and return to us *(c0, c1)*:```mathm0 = b[i]m1 = (a[i] + b[i]) % 2c0 = (    pow(g, r0, p),     int(sha256(long_to_bytes(pow(y0, r0, p))).hexdigest(), 16) ^ m0    )c1 = (    pow(g, r1, p),     int(sha256(long_to_bytes(pow(y1, r1, p))).hexdigest(), 16) ^ m1    )```
So *m0* is just a bit from the *b* value. *m1* on the other hand is simply *xor* of *a* and *b*, then: ```a[i] = m1 ^ m0```.
To get b[i] I should know last bit of ```int(sha256(long_to_bytes(pow(y0, r0, p))).hexdigest(), 16)```. And I will know this if ```g == y0```, I will get ```pow(g, r0, p)``` from the server answer and sha256 it, convert to hex and compare with second item in the c0 pair to get *m0*. Ok, we have *b*. What with *a*? The trick with ```g == y0```, cannot be used second time, because of the assert: ```(y0 * y1) % p == cs```. How to know in advance the result of ```pow(y1, r1, p)```? Use ```y1 = 1```, it will always gice you *1*. So, what about assertion? If ```y1 == 1```, then *y0* should be *cs*, and *g* also *cs*.
```python...inp = " ".join([f'({c},{c},{1})' for c in cs])conn.sendline(inp)...```
When we get the result from the server we can do the math: 
```python...b = []a = []one_hash = int(sha256(long_to_bytes(1)).hexdigest(), 16)for i in range(len(data)):    c0, c1 = data[i]    g_powered, y0_hash = c0    g_hash = int(sha256(long_to_bytes(g_powered)).hexdigest(), 16)    bi = g_hash ^ y0_hash    b.append( bi )    _, y1_hash = c1    a.append( one_hash ^ y1_hash ^ bi )
print(a)print(b)```