RSA Cheatsheet

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$:

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$:

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 python3
from Crypto.PublicKey import RSA
​
# Generate RSA key
key = RSA.generate(2048)
with open("key.pem", "wb") as f:
    f.write(key.export_key("PEM"))
​
# Read RSA key
with 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 python3
from Crypto.Util.number import inverse, long_to_bytes
from 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 = 1
for 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 python3
from Crypto.Util.number import inverse, long_to_bytes
from sympy.ntheory.primetest import isprime
from 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 - 1
d = 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 python3
from Crypto.Util.number import inverse, long_to_bytes
from sympy.ntheory.primetest import is_square
from sympy import root
from 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 python3
from Crypto.Util.number import inverse, long_to_bytes
from 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 sage
from 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 python3
from Crypto.Util.number import long_to_bytes, bytes_to_long
from 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[1]:
        m = result[0]
        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:

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

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

Correctness:

Implementation

#!/usr/bin/env python3
from Crypto.Util.number import inverse, long_to_bytes, bytes_to_long
from Crypto.PublicKey import RSA
from sympy import gcdex
from 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 coprime
if gcd != 1:
    print("e1 and e2 must be coprime")
    exit()
​
m = (pow(c1, a, N) * pow(c2, b, N)) % N
flag = 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:

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$:

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 python3
from Crypto.Util.number import inverse, long_to_bytes
from sympy import root
​
#--------Data--------#
​
e = 3
​
n1 = <n1>
n2 = <n2>
n3 = <n3>
​
c1 = <c1>
c2 = <c2>
c3 = <c3>
​
#--------Hastad broadcast attack--------#
​
N = n1 * n2 * n3
N1 = N // n1
N2 = N // n2
N3 = N // n3
​
u1 = inverse(N1, n1)
u2 = inverse(N2, n2)
u3 = inverse(N3, n3)
​
M = (c1*u1*N1 + c2*u2*N2 + c3*u3*N3) % N
m = 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:

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 python3
import owiener
from 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:

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. ​Twenty Years of Attacks on the RSA Cryptosystem​

2. ​An Introduction to Mathematical Cryptography​

3. ​PyCryptodome​

4. Attacking RSA for fun and CTF points

   • ​Part 1​

   • ​Part 2​

   • ​Part 3​

   • ​Part 4​

5. ​Implementation of Boneh and Durfee attack on RSA's low private exponents​