# RSA Cheatsheet

Forty Years of Attacks on the RSA Cryptosystem

## Textbook RSA Scheme

### Key Generation (Alice)

Generate two large random primes $p$ and $q$. Compute the modulus $N = pq$. Compute $\phi(N) = (p-1)(q-1)$. Choose a public exponent $e$ s.t. $gcd(e, \phi(N)) = 1$ (usually we use $e = 65537$). Publish the modulus $N = pq$ and the public exponent $e$ as the public key $K = (N, e)$.

### Encryption (Bob)

Choose a plaintext $m$ to be sent. Use the public key $K = (N, e)$ to encrypt $m$:

$c \equiv m^e \mod N$

In Python, this step is computed by c = pow(m, e, N). Send the ciphertext $c$ to Alice.

### Decryption (Alice)

Compute the private component $d = inverse(e, \phi(N))$ and decrypt $c$:

$m \equiv c^d \mod N$

In Python, this step is computed by m = pow(c, d, N).

## PyCryptodome RSA Module

PyCryptodome provides a module for RSA generation and RSA key I/O:

#!/usr/bin/env python3from Crypto.PublicKey import RSA​# Generate RSA keykey = RSA.generate(2048)with open("key.pem", "wb") as f:    f.write(key.export_key("PEM"))​# Read RSA keywith open("key.pem", "r") as f:    key = RSA.import_key(f.read())

## Prime Factors

### Case 1: FactorDB

Always try factoring the modulus N using factordb-python.

Implementation:

#!/usr/bin/env python3from Crypto.Util.number import inverse, long_to_bytesfrom factordb.factordb import FactorDB​#--------Data--------#​N = <N>e = <e>c = <c>​#--------FactorDB--------#​f = FactorDB(N)f.connect()factors = f.get_factor_list()​#--------RSA decryption--------#​phi = 1for factor in factors:    phi *= factor - 1​d = inverse(e, phi)m = pow(c, d, N)flag = long_to_bytes(m).decode()​print(flag)

### Case 2: Modulus Itself is a Prime

• If the modulus $N$ is a prime, then we can directly compute $\phi = N - 1$.

• How to verify whether $N$ is a prime or not? Use sympy.ntheory.primetest.isprime.

Implementation:

#!/usr/bin/env python3from Crypto.Util.number import inverse, long_to_bytesfrom sympy.ntheory.primetest import isprimefrom sys import exit​#--------Data--------#​N = <N>e = <e>c = <c>​#--------Primality test--------#​if isprime(N):    print("N is a prime.")else:    print("N is not a prime.")    exit()​#--------RSA decryption--------#​phi = N - 1d = inverse(e, phi)m = pow(c, d, N)flag = long_to_bytes(m).decode()​print(flag)

### Case 3: Repeated Prime Factor

• If the modulus is a perfect square of some prime $p$, i.e. $N = p^2$, then we can simply compute $p = \sqrt{N}$.

• If $p$ is found, then we have $\phi = p \cdot (p - 1)$.

• How to verify whether $N$ is a perfect square or not? Use sympy.ntheory.primetest.is_square.

Implementation:

#!/usr/bin/env python3from Crypto.Util.number import inverse, long_to_bytesfrom sympy.ntheory.primetest import is_squarefrom sympy import rootfrom sys import exit​#--------Data--------#​N = <N>e = <e>c = <c>​#--------Perfect square test--------#​if is_square(N):    print("N is the square of some prime p.")else:    print("N is not a square.")    exit()​#--------RSA decryption--------#​p = int(root(N, 2))print(f"{p = }")phi = p * (p - 1)d = inverse(e, phi)m = pow(c, d, N)flag = long_to_bytes(m).decode()​print(flag)

### Case 4: Twin Primes

"Twin primes" means $N = p \cdot q$ and $q = p + 2$. The value of $p$and $q$can be easily computed using quadratic formula. The detailed derivation can be found here:

Implementation:

#!/usr/bin/env python3from Crypto.Util.number import inverse, long_to_bytesfrom math import sqrt​#--------Data--------#​N = <N>e = <e>c = <c>​#--------Twin primes--------#​p = abs(int(sqrt(N + 1)) - 1)q = abs(int(-sqrt(N + 1)) - 1)​phi = (p - 1) * (q - 1)d = inverse(e, phi)m = pow(c, d, N)flag = long_to_bytes(m).decode()​print(flag)

### Case 5: Multi-prime

If the modulus $N$is the product of multiple primes, it is possible to factor it in a short amount of time. This factorization can be done with the ecm.factor() function from Sage.

Implementation:

#!/usr/bin/env sagefrom Crypto.Util.number import inverse, long_to_bytes​#--------Data--------#​N = <N>e = <e>c = <c>​#--------Multi-prime--------#​primes = ecm.factor(N)​phi = prod(p - 1 for p in primes)d = inverse(e,phi)m = pow(c, d, N)flag = long_to_bytes(m).decode()​print(flag)

## Low Public Exponent

If $e$ is small, it is possible to get the flag by brute-forcing. Suppose we have $e = 3$. In this case, we can try to compute $c + k * N$ (where $k$ is an natural number) until we find a perfect cube. If a perfect cube is found, simply take cubic root on it and we would get the flag.

### Implementation

#!/usr/bin/env python3from Crypto.Util.number import long_to_bytes, bytes_to_longfrom sympy import integer_nthroot​#--------Data--------#​N = <N>e = <e>c = <c>​#--------Cubic root--------#​while True:    # Example: integer_nthroot(16, 2) => (4, True)    # Note that the True or False here is boolean value    result = integer_nthroot(c, 3)    if result:        m = result        break    c += N​flag = long_to_bytes(m).decode()​print(flag)

## Common Modulus

Common Modulus Attack is used when the same plaintext $m$ is encrypted twice with the same modulus $N$ but distinct public exponent $e_1$ and $e_2$. In other words:

$c_1 \equiv m^{e_1} \mod N \\ c_2 \equiv m^{e_2} \mod N$

If $e_1$ and $e_2$ are coprime, then Bezout's Identity tells us that $\exists \ a,b \in \mathbb{Z}$ s.t.

$a \cdot e_1 + b \cdot e_2 = 1$

Here $a$ and $b$ can be solved using extended Euclidean Algorithm. Once we know $a$ and $b$, we could compute

$m \equiv {c_1}^a + {c_2}^b \mod N$

Correctness:

${c_1}^a + {c_2}^b \equiv (m^{e_1})^a \cdot (m^{e_2})^b \equiv m^{e_1 \cdot a + e_2 \cdot b} \equiv m^1 \equiv m \mod N$

### Implementation

#!/usr/bin/env python3from Crypto.Util.number import inverse, long_to_bytes, bytes_to_longfrom Crypto.PublicKey import RSAfrom sympy import gcdexfrom sys import exit​#--------Data--------#​N = <N>e1 = <e1>e2 = <e2>c1 = <c1>c2 = <c2>​#--------Common modulus--------#​a, b, gcd = gcdex(e1, e2)a = int(a)b = int(b)​# Test if e1 and e2 are coprimeif gcd != 1:    print("e1 and e2 must be coprime")    exit()​m = (pow(c1, a, N) * pow(c2, b, N)) % Nflag = long_to_bytes(m)​print(flag)

## Hastad Broadcast Attack

Hastad Broadcast Attack is used when the same plaintext $m$ is encrypted multiple ($\geq 3$) times with the same public exponents $e$ but distinct modulus $N_i$. In other words:

$c_1 \equiv m^{e} \mod N_1 \\ c_2 \equiv m^{e} \mod N_2 \\ ... \\ c_n \equiv m^{e} \mod N_n$

Chinese Remainder Theorem tells us the solution to the following equation exists:

Denote this solution as $M$. Chinese Remainder Theorem also provides a method for computing $M$:

$M \equiv \sum_{i=1}^{e} c_i \cdot u_i \cdot N_i \mod N$

where $N = \prod_{i=1}^{n} N_i$. Note that the plaintext $m < N_i$, hence $m^e < \prod_{i=1}^{n} N_i = N$. As a result, taking $e$-th root of $M$ gives us the plaintext $m$. No need to worry about modulo $N$ since $m^e$ is not large enough.

### Implementation

#!/usr/bin/env python3from Crypto.Util.number import inverse, long_to_bytesfrom sympy import root​#--------Data--------#​e = 3​n1 = <n1>n2 = <n2>n3 = <n3>​c1 = <c1>c2 = <c2>c3 = <c3>​#--------Hastad broadcast attack--------#​N = n1 * n2 * n3N1 = N // n1N2 = N // n2N3 = N // n3​u1 = inverse(N1, n1)u2 = inverse(N2, n2)u3 = inverse(N3, n3)​M = (c1*u1*N1 + c2*u2*N2 + c3*u3*N3) % Nm = root(M, e)​print(long_to_bytes(m).decode())

## Low Private Exponent

### Case 1: Wiener Attack

Wiener Attack works when the private exponent $d$ is small. How small? If the private component $d$ satisfies:

$d < \frac{1}{3}n^{\frac{1}{4}}$

then we can use Wiener's Attack to get the flag.

The idea behind Wiener's Attack is continued fraction. In the context of CTF, we don't need to worry about the underlying theory since this attack is already implemented in the package oWiener. Install it with pip3 install owiener. Read more about this implementation here:

### Implementation

#!/usr/bin/env python3import owienerfrom Crypto.Util.number import long_to_bytes​#--------Data--------#​N = <N>e = <e>c = <c>​#--------Wiener's attack--------#​d = owiener.attack(e, N)​if d:    m = pow(c, d, N)    flag = long_to_bytes(m).decode()    print(flag)else:    print("Wiener's Attack failed.")

### Case 2: Boneh-Durfee Attack

Boneh-Durfee Attack also works when the private component $d$ is small, but it relaxes the restriction to another level compared to Wiener's Attack. If the private component $d$ satisfies:

$d < N^{0.292}$

then we can use Boneh-Durfee Attack to get the flag.

This attack is implemented in Sage. The code can be found here:

## Reference

1. Attacking RSA for fun and CTF points