# RSA tutorial

## Problem

1. Source code

```python
from Crypto.Util.number import getPrime
from Crypto.Util.number import bytes_to_long as b2l

from secret import flag


p = getPrime(256)
q = getPrime(256)
n = p * q
e = 65536

print(p)
print(q)
print(pow(b2l(flag), e, n))
```

2. Output

```
79565304973649738046890929641550086406229645142982116252431882783628570446741
104895446414749804110599905404014579424417002368568255490767700901764221803853
4540356813631057206329938934275504497042552943607683102015080934372428231345551929844529058302190596843384780497234278626232722159254772622184794355722055
```

When I tried to decode it with simple [RSA](https://en.wikipedia.org/wiki/RSA_\(cryptosystem\)) steps, the `e` wasn't invertible for the phi (gcd(e,phi) > 1). In RSA, the public exponent 𝑒  must be chosen such that it is coprime to 𝜑 ( 𝑛 ) (Euler's totient function of 𝑛). This ensures that 𝑒  has a modular inverse, which is necessary for computing the private exponent 𝑑 using the modular inverse:

$$
d≡e ^{−1}\space
mod\spaceφ(n)
$$

```python
from Crypto.Util.number import long_to_bytes
from math import gcd

# Given values
p = 79565304973649738046890929641550086406229645142982116252431882783628570446741
q = 104895446414749804110599905404014579424417002368568255490767700901764221803853
n = p * q
e = 65536
c = 4540356813631057206329938934275504497042552943607683102015080934372428231345551929844529058302190596843384780497234278626232722159254772622184794355722055

# Compute phi(n)
phi = (p - 1) * (q - 1)

# Compute d (modular inverse of e mod phi)
if gcd(e, phi) != 1:
    print("e and phi(n) are not coprime. Cannot compute d directly.")
else:
    d = pow(e, -1, phi)  # Compute modular inverse

    # Decrypt ciphertext
    m = pow(c, d, n)
    
    # Convert to bytes and print flag
    flag = long_to_bytes(m)
    print(flag.decode())
```

**Reduce the Problem**

* Divide e and ϕ(n) by g:
  * e′=e/g
  * ϕ′=ϕ(n)/g
* Compute the modular inverse of e′ modulo ϕ′:
  * d′=e′^(-1)mod  ϕ′
* **Find gg-th Roots Modulo pp and qq:**
  * Use the `nthroot_mod` function to compute:

    mp=nthroot\_mod(c′,g,p) & mq=nthroot\_mod(c′,g,q)
* **Combine Results Using CRT:**
  * Use the Chinese Remainder Theorem (CRT) to combine mp​ and mq:

    m=crt(\[p,q],\[mp,mq])\[0]

> By reducing e and ϕ ( n ), we create new values e ′ , ϕ ′ , and c ′ that allow us to solve the problem despite the non-coprime issue.

## What does `nthroot_mod` do?

$$
m^{e}≡c\space mod \space (p \space OR \space q)
$$

**It Checks if a Solution Exists for flag and Solves.** 

* Once **m\_p**​ (solution modulo p) and **m\_q**(solution modulo q) are found, the Chinese Remainder Theorem (CRT) combines them to get **m**.

## Chinese Remainder Theorem

**Combining m\_p and m\_q into one solution m.**

**Example**

<figure><img src="https://1160714615-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FSQLD7d7YuSCaHXDmYUeJ%2Fuploads%2FDeW1U4V3i5HtFt21K5sa%2FScreenshot%202025-02-22%20at%2017.43.18.png?alt=media&#x26;token=9c4e9541-0455-4255-8da9-337acf0dda3f" alt="" width="375"><figcaption><p>CRT</p></figcaption></figure>

#### Example

Let’s say:

* p=7, q=11, n=77.
* e=16, c=23.

1. Compute ϕ(n)=(7−1)(11−1)=60.
2. Compute g=gcd⁡(16,60)=4.
3. Reduce e′=16/4=4, ϕ′=60/4=15
4. Compute d′=4^{-1}mod  15=4(since 4⋅4=16≡1mod  15).
5. Compute c′=23^{4}mod  77.
6. Compute mp=nthroot\_mod(c′,4,7) and mq=nthroot\_mod(c′,4,11).
7. Combine mp​ and mq​ using CRT to get m mod  77.
8. Convert m to bytes to recover the flag.

```python
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
from math import gcd
from sympy.ntheory.residue_ntheory import nthroot_mod
from sympy.ntheory.modular import crt

# Given values
p = 79565304973649738046890929641550086406229645142982116252431882783628570446741
q = 104895446414749804110599905404014579424417002368568255490767700901764221803853
n = p * q
e = 65536
c = 4540356813631057206329938934275504497042552943607683102015080934372428231345551929844529058302190596843384780497234278626232722159254772622184794355722055

# Compute phi(n)
phi = (p - 1) * (q - 1)

# Compute gcd(e, phi(n))
g = gcd(e, phi)

# Reduce the problem
e_prime = e // g
phi_prime = phi // g
d_prime = pow(e_prime, -1, phi_prime)

# Compute c' = c^d_prime mod n
c_prime = pow(c, d_prime, n)

# Compute g-th root modulo p and q
m_p = nthroot_mod(c_prime, g, p)
m_q = nthroot_mod(c_prime, g, q)

# Combine using CRT
m = crt([p, q], [m_p, m_q])[0]

flag = long_to_bytes(m)
print(flag.decode())
```

Flag: `mazala{m0dul4r_Square_r00t}`