RSA Cheatsheet

Forty Years of Attacks on the RSA Cryptosystem

Textbook RSA Scheme

Key Generation (Alice)

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

Encryption (Bob)

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

cmemodNc \equiv m^e \mod N

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

Decryption (Alice)

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

mcdmodNm \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 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 NN is a prime, then we can directly compute ϕ=N1\phi = N - 1.

  • How to verify whether NN 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 pp, i.e. N=p2N = p^2, then we can simply compute p=Np = \sqrt{N}.

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

  • How to verify whether NN 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=pqN = p \cdot q and q=p+2 q = p + 2. The value of ppand qqcan 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 NNis 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 ee is small, it is possible to get the flag by brute-forcing. Suppose we have e=3e = 3. In this case, we can try to compute c+kNc + k * N (where kk 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 mm is encrypted twice with the same modulus NN but distinct public exponent e1e_1 and e2e_2. In other words:

c1me1modNc2me2modNc_1 \equiv m^{e_1} \mod N \\ c_2 \equiv m^{e_2} \mod N

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

ae1+be2=1a \cdot e_1 + b \cdot e_2 = 1

Here aa and bb can be solved using extended Euclidean Algorithm. Once we know aa and bb, we could compute

mc1a+c2bmodNm \equiv {c_1}^a + {c_2}^b \mod N

Correctness:

c1a+c2b(me1)a(me2)bme1a+e2bm1mmodN{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 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 mm is encrypted multiple (3\geq 3) times with the same public exponents ee but distinct modulus NiN_i. In other words:

c1memodN1c2memodN2...cnmemodNnc_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 MM. Chinese Remainder Theorem also provides a method for computing MM:

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

where N=i=1nNiN = \prod_{i=1}^{n} N_i. Note that the plaintext m<Nim < N_i, hence me<i=1nNi=Nm^e < \prod_{i=1}^{n} N_i = N. As a result, taking ee-th root of MM gives us the plaintext mm. No need to worry about modulo NN since mem^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 dd is small. How small? If the private component dd satisfies:

d<13n14d < \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 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 dd is small, but it relaxes the restriction to another level compared to Wiener's Attack. If the private component dd satisfies:

d<N0.292d < 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