Cryptography relies on the premise that keys used in encryption are computationally infeasible to guess. A "strong" key is one that provides a high level of entropy (unpredictability) and sufficient length to make brute-force attacks impractical. For example, a 128-bit key has 2^128 possible combinations, which would take centuries to brute-force using modern hardware.
Characteristics of Strong Keys:
- Length: Longer keys significantly increase the computational effort required to brute-force them.
- Entropy: Keys must be truly random, not derived from predictable inputs like timestamps or user data.
- Uniqueness: Keys must be unique across different encryptions or systems to prevent correlation attacks.
When these principles are violated, keys become vulnerable to brute-force or mathematical attacks.
Math of RSA
RSA encryption, named after its inventors Rivest, Shamir, and Adleman, is based on the difficulty of factoring large numbers.
A public key consists of:
- n=p×q: The product of two large prime numbers, (p) and (q).
- e: A small public exponent (commonly (e = 65537)).
The private key is derived from:
- ϕ(n)=(p−1)×(q−1), where ϕ is Euler's totient function.
- (d): The modular inverse of 𝑒 e modulo 𝜙 ( 𝑛 ) ϕ(n), satisfying 𝑒 × 𝑑 ≡ 1 ( mod 𝜙 ( 𝑛 ) ) e×d≡1 (mod ϕ(n)).
The security of RSA depends on the difficulty of factoring (n) into its prime components (p) and (q). However, if (p) or (q) is poorly generated or shared across keys, this foundational assumption breaks down.
How Factorisation Time Increases Exponentially
To demonstrate how factoring time grows with larger primes, we will test factorisation for different values of (n = p * q) using Python.
import time
from sympy.ntheory import factorint
# Small n (product of two small primes)
n_small = 253 # 11 × 23
start = time.time()
factorint(n_small)
print(f"Time to factor {n_small}: {time.time() - start:.6f} seconds")
# Medium n
n_medium = 988027 # 941 × 1051
start = time.time()
factorint(n_medium)
print(f"Time to factor {n_medium}: {time.time() - start:.6f} seconds")
# Large n
n_large = 2147483647 # A large prime
start = time.time()
factorint(n_large)
print(f"Time to factor {n_large}: {time.time() - start:.6f} seconds")
The above script will have an output of:
Time to factor 253: 0.000019 seconds
Time to factor 988027: 0.000041 seconds
Time to factor 2147483647: 0.000094 seconds
As prime numbers grow larger, factorisation time increases exponentially, making brute-force factorisation infeasible for properly generated RSA keys.
What is "P's and Q's"?
The paper "P's and Q's" by Ross Anderson and Serge Vaudenay explores how poor randomness in RSA key generation can lead to severe vulnerabilities. It outlines key weaknesses that attackers can exploit:
Predictable Primes:
If (p) or (q) are generated using a weak random number generator (e.g., seeded with system time), an attacker can recreate the key generation process and derive the primes.
Shared Primes Across Keys:
When multiple RSA keys share a common prime (p), the attacker can use the greatest common divisor (GCD) method to factor n1=p×q1 and n2=p×q2, breaking both keys.
Small Differences Between Primes:
If (p) and (q) are too close in value, efficient algorithms such as Fermat's factorisation method can quickly factor (n).
Mathematical Exploits Using GCD:
The GCD of two public keys that share a prime can be computed in polynomial time:
GCD(n1,n2)=p
These vulnerabilities highlight the critical importance of randomness and diversity in prime generation for RSA security.
Exercise
Note: Remember to include all values and required imports. The factoring step is not required in the script.
Using the c, n, and e, which are crucial components of the RSA encryption process. The RSA algorithm also utilises two large prime numbers, p and q. Can you uncover the hidden text behind it? Follow along to build a script that will uncover the hidden text.
Public Key: n = 43941819371451617899582143885098799360907134939870946637129466519309346255747
Exponent: e = 65537
Ciphertext: c = 9002431156311360251224219512084136121048022631163334079215596223698721862766
Your task is to recover the plaintext by factoring n and deriving the private key. The challenge assumes n is a product of two weakly generated primes p and q.
Factoring
Since (n) is the product of two large primes ((p) and (q)), factorisation is the first step. Modern factoring tools, like MSIEVE or YAFU, can be used for this purpose. However, for educational purposes, you can use Python and a library like sympy.
Use the following Python code to factor (n) into (p) and (q):
Note: This computation takes a lot of processing power, so if you are using the AttackBox, we strongly recommend that you skip this step and follow along.
from sympy import factorint
from Crypto.Util.number import inverse, long_to_bytes
# Given values
n = 43941819371451617899582143885098799360907134939870946637129466519309346255747
# Factor n
factors = factorint(n)
p, q = factors.keys()
print("Prime factors:")
print("p =", p)
print("q =", q)
Expected Output:
The script will compute:
p = 205237461XXXXXXXXXXXXX
q = 21410233XXXXXXXXXXXXXX
Alternatively, you can use FactorDB and search for the prime numbers of the (n). For example:
Compute phi
Using the two primes, calculate phi(n), where:
phi_n = (p - 1) * (q - 1)
print("Phi(n) =", phi_n)
Finding the Private Key
The private key exponent (d) is the modular inverse of (e) modulo (ϕ(n)):
Use Python to calculate (d):
from sympy import factorint
from Crypto.Util.number import inverse, long_to_bytes
e = 65537
d = inverse(e, phi_n)
print("Private key (d):", d)
Decrypting the Ciphertext
Now that you have (d), decrypt the given ciphertext (c):
Use Python to compute the plaintext:
c = 9002431156311360251224219512084136121048022631163334079215596223698721862766
plaintext = pow(c, d, n)
flag = long_to_bytes(plaintext)
print(flag.decode())
print("Decrypted Plaintext:", flag)
Key Takeaways from Broadcast RSA
- Avoid small public exponents like
e = 3; instead, use larger values like e = 65537.
- Ensure encrypted messages are padded with random data (e.g., PKCS#1 or OAEP) to prevent mathematical attacks.
- Use different plaintexts for different recipients to avoid the conditions that make CRT attacks possible.