> For the complete documentation index, see [llms.txt](https://sayonara.gitbook.io/writeups/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://sayonara.gitbook.io/writeups/ctf/nitectf2023/crypto/babyrsa.md).
# babyRSA
### Challenge Files :
{% file src="/files/TTUoYUh3jFL5v20gu4t6" %}
{% file src="/files/AYPuadvuGLxJQpKN9Xzs" %}
### RSA ATTACK :
same public exponent `(e=37` is used on the same message M during encryption, then CRT `(Chinese Remainder Theorem)` can be used to obtain M^e using each combination.
### Python Script :
i took the script from MxRy and modified it to work for me you can get the original script from here
```python
import math
import functools
import gmpy2
# Get the Flag
def ReverseX(x, e) :
m = gmpy2.iroot(x, e)[0]
size = int(math.log(m, 10) + 1)
print("Flag : \n"+"".join([chr((m >> j) & 0xff) for j in reversed(range(0, size << 3, 8))]))
return 1
# Step-by-step CRT implementation (cf. demo precedente)
def CrtComputation(C_i, N_i) :
mu = list()
nu = list()
e = list()
(x_i, N) = (0, 1)
"""
Calcul mu_i = PI_(j=1,j!=i)^k(n_j)
"""
N = functools.reduce(lambda a, b: a*b, N_i)
for n_i in N_i :
mu.append(N//n_i)
"""
Calcul nu_i inverse modulo n_i des mu_i
useful link :
https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm
"""
for mu_i, n_i in zip(mu, N_i) :
nu.append(gmpy2.invert(mu_i, n_i))
"""
Calcul e_i = nu_i * mu_i
"""
for mu_i, nu_i in zip(mu, nu) :
e.append(mu_i*nu_i)
"""
Calcul et retour de x
"""
for e_i, a_i in zip(e, C_i) :
x_i += e_i*a_i
x = x_i % N
return x
def HastadAttack(C, N, e):
x = CrtComputation(C, N)
return ReverseX(x, e)
def main():
e = 37
C = [... 37 element ] # put here the c array from the output.txt file
N = [... 37 element ] # put here the n array from the output.txt file
HastadAttack(C, N, e)
if __name__ == "__main__":
main()
```
running the script we get the flag
### Flag :
```
nite{y0u_C@n_N3v3r_Gu3s5!!!}
```
