# de1ctf-2019

BabyRSA – Crypto

We are given the script used to encrypt the flag . On taking a look we see that the parameters used to encrypt the flag are not given but the parameters used are encrypted with vulnerable textbook RSA.

Let’s start from the end of the code :

We see that we can get the flag if we know either of the set { e1,p,q1,c1} or { e2,p,q2,c2} .c2,c1,q2 are given.

Let’s look at the beginning :

We see we do not know e1,e2, p and q1 . Let’s see what all we can recover from the rest of the code.

We can recover p by applying Chinese remainder theorem on the above n and c .

We see since ee2=3 we can recover e2 . I used this script .

Subtracting tmp we get get e2.

Now we see we have {c2,e2,p,q2} – All that is needed to solve the second equation.

```c2=pow(flag,e2,p*q2)
phi2=(p-1)*(q2-1)
GCD(e2,phi2) = 70
GCD(e2,p-1)=70
GCD(e2,q2-1) = 2
```

We see that the GCD is not 1 . We can reduce it to 2 by doing cc2 = c2%q2 . Now q2 is the modulus . Since q2 is prime new phi =q2-1.

```cc2 = pow(m,e2,q2)
cc2 ^ (1/2) = pow(m,e2/2,q2)
GCD(e2/2,q2) = 1
Thus, d= inverse(e2/2,q2)
M = pow(m^(e2/2) , d, q2)
= m^((e2*d)/2) % q2
= m^2 % q2
Therefore we can say ,
m = M^(1/2)
```

Converting long_to_bytes we get the flag :