# babyRSA

<div align="left"><figure><img src="https://1410593648-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FYI2noEqPw69jd0hR7Prp%2Fuploads%2FHTrbJeaEthazZqVyUzqQ%2FPasted%20image%2020231217155426.png?alt=media&#x26;token=0be28f40-31e3-4297-9eaa-2ce939282667" alt=""><figcaption></figcaption></figure></div>

### Challenge Files :&#x20;

{% file src="<https://1410593648-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FYI2noEqPw69jd0hR7Prp%2Fuploads%2FqpMgYlsjjAsikUMYWMQK%2Fencrypt.py?alt=media&token=9fbf70e2-8b1c-4026-8363-e8d7a0806b84>" %}

{% file src="<https://1410593648-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FYI2noEqPw69jd0hR7Prp%2Fuploads%2FO34vcZkBtUAgseCZBLQ2%2Foutput.txt?alt=media&token=45aac81a-1a70-448d-9adb-6c7ebc0ab881>" %}

### <mark style="color:red;">RSA ATTACK :</mark>&#x20;

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.

### <mark style="color:red;">Python Script :</mark>&#x20;

i took the script from MxRy and modified it to work for me you can get the original script from here <https://github.com/MxRy/rsa-attacks/blob/master/hastad-attack.py>

```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

<div align="left"><figure><img src="https://1410593648-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FYI2noEqPw69jd0hR7Prp%2Fuploads%2F6kokZT4gNocC9PG1DEHo%2FPasted%20image%2020231217155353.png?alt=media&#x26;token=d8aaf3fb-157f-4cbc-b7b5-41a09c308c7f" alt=""><figcaption></figcaption></figure></div>

### <mark style="color:red;">Flag :</mark>&#x20;

```
nite{y0u_C@n_N3v3r_Gu3s5!!!}
```
