What is RSA? #
RSA is an asymmetric cryptographic algorithm: it uses two keys with distinct roles. The public key can be shared to encrypt a message or verify a signature, while the private key remains secret to decrypt or sign. This article starts by creating that key pair, follows a message through RSA, and then shows how incorrect configurations or uses make the system vulnerable.
Its security relies in part on the difficulty of factoring a very large integer. With properly chosen parameters, deriving the private key from the public key is considered infeasible in practice.
RSA Formulas #
Let us begin by building the keys. The same numbers will then be used for encryption, decryption, and signatures.
Key Generation #
- Choose distinct prime numbers \(p\) and \(q\).
- Compute the modulus \(n\) with \(n = p*q\).
- Compute \(\varphi(n) = (p-1)(q-1)\).
- Choose an integer \(e\) coprime to \(\varphi(n)\), with \(1 < e < \varphi(n)\): this is the encryption exponent.
- Compute \(d\) with \(d = e^{-1} \pmod {\varphi(n)} \) and \(d < \varphi(n)\): this is the decryption exponent.
The condition on \(e\) ensures that its inverse modulo \(\varphi(n)\) exists. This yields the public key \((n, e)\) and the private key \((n, d)\). In a real implementation, the private key generally retains \(p\) and \(q\) as well, but \((n, d)\) is enough to understand the formulas below.
Encryption #
Once the public key has been created, it can transform a message into ciphertext. If \(M \in \mathbb{N}\) and \(M < n\) represents that message, the result is:
\[C = M^e \pmod n\]
Decryption #
The recipient then goes from \(C\) back to the plaintext using the private key. With \(d = e^{-1} \pmod {\varphi(n)}\), they compute:
\[M = C^d \pmod n\]
Generating a Signature #
The same key pair can also prove a message’s origin and integrity. In this simplified model, let \(h = hash(M)\), represented as an integer smaller than \(n\), then apply the private exponent \(d\):
\[S = h^d \pmod n\]
Verifying a Signature #
The verifier then uses the public key and applies \(e\) to \(S\):
\[h’ = S^e \pmod n\]
They then check that \(h’ = h\). In practice, encryption and signing use secure padding schemes: the formulas above describe “textbook” RSA so that its mechanism is easier to understand.
Some Simple Attacks #
These mathematical relationships assume that RSA’s parameters and use are correct. The following examples show, for each weakness, what can be observed, the condition that makes it exploitable, and its effect.
Factorizable \(n\) #
Observation: the public key exposes the modulus \(n\). Condition: if this modulus is small enough or built from factors that are too easy to find, it can be factored; the site factordb can help check known examples. Effect: recovering \(p\) and \(q\) makes it possible to recompute \(\varphi(n)\), then \(d\), and thus obtain \(Privkey(n, d)\).
Common Factor Attack #
Observation: two public keys provide the moduli \(n_1\) and \(n_2\). Condition: if they share a prime factor \(p\), they are not coprime. Their GCD then reveals that factor:
- \(p = gcd(n_1, n_2)\)
- \(q_1 = \frac{n_1}{p}\)
- \(q_2 = \frac{n_2}{p}\)
Effect: this recovers \(q_1\) and \(q_2\), after which \(d_1\) is computed from \(e_1\) and \(d_2\) from \(e_2\). Both private keys are compromised.
Example Python script:
from math import gcd
def common_factor_attack(n1, n2, c1, c2, e1, e2):
p = gcd(n1, n2)
q1 = n1 // p
q2 = n2 // p
phi1 = (p - 1) * (q1 - 1)
d1 = pow(e1, -1, phi1)
m1 = pow(c1, d1, n1)
phi2 = (p - 1) * (q2 - 1)
d2 = pow(e2, -1, phi2)
m2 = pow(c2, d2, n2)
return (m1, m2)Low Exponent Attack #
Observation: the public exponent \(e\) is small. Condition: with textbook RSA and no padding, if the message is small enough that \(M^e < n\), reduction modulo \(n\) does not change \(M^e\), so \(C = M^e\) over the integers. Effect: \(M\) can be recovered directly by taking the integer root:
\[M = \sqrt[e]{C}\]
Decryption Oracle #
Observation: textbook RSA has a multiplicative homomorphism. Let \(E(m) = m^e \pmod n\):
\[E(x * y) \equiv E(x) * E(y) \pmod n\]
Condition: suppose an oracle returns the plaintext of a chosen textbook-RSA ciphertext but refuses the target ciphertext \(C\). Choose \(x \in \mathbb{Z}_n^\) such that \(Cx^e \not\equiv C \pmod n\), then submit that different ciphertext:
\[C’ = C * x^e \pmod n\]
Effect: the oracle returns \(M’ = M*x \pmod n\). Because \(x\) is invertible, the message can be recovered with:
\[M = M’ * x^{-1} \pmod n\]
This attack therefore targets a protocol that returns the textbook-RSA plaintext, or leaks equivalent information that is exploitable under chosen ciphertext; it does not indiscriminately apply to every mechanism described as a decryption oracle.
Conclusion #
RSA ties key generation, two inverse operations, and a signature mechanism to a few arithmetic principles. Those same principles explain its weaknesses: security depends on good parameters, suitable padding, and the absence of exploitable leakage under chosen ciphertext.
