## LINDA### Challenge> Dan Boneh loves to improve cryptosystems, you should be loving breaking them?`nc 07.cr.yp.toc.tf 31010`- [linda.txz](https://cr.yp.toc.tf/tasks/linda_a26f6987ed6c630297c2df0847ef258ad3810ca2.txz)
```python#!/usr/bin/env python3
from Crypto.Util.number import *from math import gcdfrom flag import flag
def keygen(p):    while True:        u = getRandomRange(1, p)        if pow(u, (p-1) // 2, p) != 1:            break    x = getRandomRange(1, p)    w = pow(u, x, p)    while True:        r = getRandomRange(1, p-1)        if gcd(r, p-1) == 1:            y = x * inverse(r, p-1) % (p-1)            v = pow(u, r, p)            return u, v, w def encrypt(m, pubkey):    p, u, v, w = pubkey    assert m < p    r, s = [getRandomRange(1, p) for _ in '01']    ca = pow(u, r, p)    cb = pow(v, s, p)    cc = m * pow(w, r + s, p) % p    enc = (ca, cb, cc)    return enc
def die(*args):    pr(*args)    quit()
def pr(*args):    s = " ".join(map(str, args))    sys.stdout.write(s + "\n")    sys.stdout.flush()
def sc():    return sys.stdin.readline().strip()
def main():    border = "+"    pr(border*72)    pr(border, "  .:::::: LINDA Cryptosystem has high grade security level ::::::.  ", border)    pr(border, "  Can you break this cryptosystem and find the flag?                ", border)    pr(border*72)
    pr('| please wait, preparing the LINDA is time consuming...')    from secret import p    u, v, w = keygen(p)    msg = bytes_to_long(flag)    pubkey = p, u, v, w    enc = encrypt(msg, pubkey)    while True:        pr("| Options: \n|\t[E]xpose the parameters \n|\t[T]est the encryption \n|\t[S]how the encrypted flag \n|\t[Q]uit")        ans = sc().lower()        if ans == 'e':            pr(f'| p = {p}')            pr(f'| u = {u}')            pr(f'| v = {v}')            pr(f'| w = {w}')        elif ans == 's':            print(f'enc = {enc}')        elif ans == 't':            pr('| send your message to encrypt: ')            m = sc()            m = bytes_to_long(m.encode('utf-8'))            pr(f'| encrypt(m) = {encrypt(m, pubkey)}')        elif ans == 'q':            die("Quitting ...")        else:            die("Bye ...")
if __name__ == '__main__':    main()```
### SolutionBy interacting with the challenge, we can get public key parameters by sending `e`, get encrypted flag with `s`,  encrypt our own messages with `t` and quit with `q`. Only the first two options will be relevant to the solution.
Encryption here works like this: $p, u, v, w$ are public key parameters, message $m$ is encrypted as follows:
$$ca \equiv u^r \mod p \\ cb \equiv v^s \mod p$ \\cc \equiv mw^{r + s} \mod p$$
where $r, s$ are uniformly random numbers from $[1;p]$.
We can notice that despite $p$ being new on each connection, $p - 1$ is always smooth. Example:
```pythonp = 31236959722193405152010489304408176327538432524312583937104819646529142201202386217645408893898924349364771709996106640982219903602836751314429782819699p - 1 = 2 * 3 * 11 * 41 * 137 * 223 * 7529 * 14827 * 15121 * 40559 * 62011 * 429083 * 916169 * 3810461 * 4316867 * 20962993 * 31469027 * 81724477 * 132735437 * 268901797 * 449598857 * 2101394579 * 2379719473 * 5859408629 * 11862763021 * 45767566217```
This is the key for solving this challenge, because after getting public key paramters and encrypted flag we can factor $p - 1$ by using trial division and [ECM](https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization), then use [Pohlig-Hellman algorithm](https://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm) to compute $r, s$ as discrete logarithms of $ca, cb$ with bases $u, v$ respectively even without trying to find weaknesses in the keygen process. Then we can compute $m \equiv ccw^{-(r + s)} \mod p$ and get the flag.
```python#!/usr/bin/env sagefrom minipwn import remote # mini-pwntools library to connect to serverfrom Crypto.Util.number import long_to_bytes
rem = remote("07.cr.yp.toc.tf", 31010)for _ in range(10):    rem.recvline()rem.sendline('e')p = int(rem.recvline()[6:])u = int(rem.recvline()[6:])v = int(rem.recvline()[6:])w = int(rem.recvline()[6:])for _ in range(5):    rem.recvline()rem.sendline('s')ca, cb, cc = map(int, rem.recvline()[7:-2].split(b', '))r = discrete_log(Mod(ca, p), Mod(u, p)) # sage has built-in discrete logarithm function, which uses Pohlig-Hellmans = discrete_log(Mod(cb, p), Mod(v, p)) # algorithm and automatically determines and factors group order, which divides p - 1m = cc * power_mod(w, -(r + s), p) % pprint(long_to_bytes(m).decode())```
##### Flag`CCTF{1mPr0v3D_CrYp7O_5yST3m_8Y_Boneh_Boyen_Shacham!}`