> For the complete documentation index, see [llms.txt](https://zwique.gitbook.io/zwique_notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zwique.gitbook.io/zwique_notes/writeups/random-ctf-writeup/local/rsa-tutorial.md).
# 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**
CRT
#### 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}`
---
# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.
## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://zwique.gitbook.io/zwique_notes/writeups/random-ctf-writeup/local/rsa-tutorial.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.