# Risk Security Analyst Alice Vs Eve Writeup (21 solves / 488 points)
> La Casa De Tuple (L.C.D.T) is a Company in Spain which provides their own End-to-end encryption services and Alice got a job there.

> It was her first day and her boss told her to manage the secrets and encrypt the user data with their new End-to-end encryption system.

> You are Eve and you're hired to break into the system. Alice was so overconfident that she gave you everyone's keys. Can you break their

> new encryption system and read the chats?

> :arrow_down: [File](https://github.com/r3yc0n1c/CTF-Writeups/raw/main/2021/darkCON-2021/Crypto/Risk%20Security%20Analyst%20Alice%20Vs%20Eve/dist/dist.zip)

## Solution

As we have the private key of Alice and all the users share the same public modulus, we can easily estimate the **phi** as follows,

```
e * d = 1 mod phi(n)
=> (e*d - 1) is a multiple of phi(n)
=> (e*d - 1) = k*phi(n)
=> k = (e*d - 1)/phi(n) = (e*d - 1)/n [ phi(n) = n (approx.) ]

Now, we increase k until phi(n)=(e*d - 1)/k becomes an integer
```

Python code to achive this:
```py
def predict_phi(n, e, d):
k = ((e*d) - 1)//n
while 1:
phi = ((e*d) - 1)//k
if phi*k == ((e*d) - 1):
return phi
k += 1
```

After that we can calaulate everyone's private key,
```
private key of User_i = inverse_mod(e_i, phi(n))
```

And then simple RSA decryption of the encrypted chats will give us the flag.

### [Solve Script](sol/solve.py)
```py
from Crypto.Util.number import *
from collections import namedtuple

Publickey = namedtuple("Publickey", ['n','e'])

# End To End RSA Decryption
def E2ERD(pubkey, phi):
enc_chats = open('encrypted_chats.txt').read().strip().split('\n\n')
pubs = open('all_publickeys.txt').read().strip().split('\n\n')

for i, chat in enumerate(enc_chats):
user, msg = chat.split(': ')
e, n = eval(pubs[i].split(': ')[1])
c = bytes_to_long(eval(msg))
d = inverse(e, phi)
m = long_to_bytes(pow(c,d,n)).decode()
print(f"{user}: {m}")

def predict_phi(n, e, d):
k = ((e*d) - 1)//n
while 1:
phi = ((e*d) - 1)//k
if phi*k == ((e*d) - 1):
return phi
k += 1

def main():
n= 134871459832923860099882590902411996710996766501756653086495354300954191050110475349218593219906710987168729946490859346117437393705213066464123381634516073655104369957424501917959364716066521838138728063315157921217685558557422845878448233922585713677077217815414960315913375048754314176130997193108410703707
e= 65537
d= 19546349779408743507159083393977587389734764914989772052665408473846268620686776856842366882870347146743497520969378855752070133900119225861364479282918556646891456167647366904804199245738822376442388779257291859758735359459148377679538927373263135165396852614400167982261412234666697210259242937381901648593
pubkey = Publickey(n, e)

pphi = predict_phi(n,e,d)
E2ERD(pubkey, pphi)

if __name__ == '__main__':
main()
```

## Flag
> darkCON{4m_I_n0t_supp0sed_t0_g1v3_d???}

### # Source Code - [[src folder]](src/)

Original writeup (https://github.com/r3yc0n1c/CTF-Writeups/tree/main/2021/darkCON-2021/Crypto/Risk%20Security%20Analyst%20Alice%20Vs%20Eve#risk-security-analyst-alice-vs-eve-writeup-21-solves--488-points).