Let’s first try to build a scheme directly using the Fermat’s Little Theorem.
Given a prime number
p and a message
m < p, we choose two numbers
d such that
e·d = 1 (mod p-1).
c = m^e (mod p)
m = c^d (mod p)
c^d = m^(e·d) ≡ m^(e·d mod p-1) = m (mod p) ∎
Assuming that the couple
n is the public key.
e·d = 1 (mod p-1) then
1 = e·d + (p-1)·y
With the Euclidean’s algorithm we can easily find the “secret”
The weakness can be addressed by replacing the modulo
p with a composite
n. To apply the attack we now require to use the Euler’s theorem and
thus to find
φ(n) by factoring
n. When the prime factors of
n are big
enough this is believed to be a hard problem.
We choose two big primes
q, and we set the modulo
n = p·q. The keys
should satisfy the following property:
e·d = 1 (mod φ(n))
In other words,
(e, φ(n)) = 1.
c = m^e (mod n)
m = c^d (mod n)
(m,n) = 1 then thesis immediately follows from Euler’s theorem:
c^d = m^(e·d) ≡ m^(e·d mod φ(n)) = m (mod n)
(m,n) ≠ 1 then we should have
(m,p) ≠ 1 or
(m,q) ≠ 1 but not both
m = p·q·k = 0 (mod n).
m = q·x and
(m,p) = 1, then
m^[(p-1)·(q-1)·z] ≡ 1 (mod p) → m^[(p-1)·(q-1)·z] = 1 + p⋅k
For the key choice criteria:
e·d = 1 (mod φ(n)) → e·d = 1 + φ(n)·z = 1 + (p-1)·(q-1)·z
m^(e·d) = m^[1 + (p-1)·(q-1)·z] = m·m^[(p-1)·(q-1)·z] = m·(1 + p·k) = m + m·p·k = m + (q·x)·(p·k) = m + (q·p)(x·k) = m + n·w ≡ m (mod n)
In practice generating a message not in
Zn* is very unlikely, but as been
shown, the cipher works anyway.
The probability of having a message with
(m,n) = 1 is
The Euler’s totient is:
φ(n) = n·(1-1/p)·(1-1/q)
q are big the more
1/q are close to
φ(n) ≈ n
This is also good for security.
If a number
m is not coprime with
n = p·q and
m = p·k or
q·k (but not both) with
k less than the other prime, then
(m,n) = p or
(m,n) = q.
In case of a known plaintext attack scenario, to factor
n, an attacker just
has to use the Euclid’s algorithm.
The security of the RSA cipher mostly relies on the hardness of integer factorization.
While there are no known efficient algorithms for factoring large integers, the security of the cipher is not guaranteed. Advances in computer hardware, mathematics, and cryptography could potentially render the RSA cipher vulnerable to attacks in the future.
If an attacker can factor the modulus, then he can easily compute the decryption exponent and decrypt any message encrypted with the public key.
The possible attack types can be classified by the end goal and sorted by complexity (most complex first):
- Determine the factors of
- Determine the totient
- Determine the secret key
- Determine the plaintext
The complexity difference between the attacks is just polynomial. Thus, for example, if we have an algorithm to solve problem 1, then we can easily solve all the other problems as well.
Since today the factorization problem is considered hard, an attacker may be inclined trying to directly solve problem 4.
Can be proven that the first three problems are equivalent.
1 solves 2
If we know
φ(n) = (p-1)·(q-1)
2 solves 1
φ(n) we can easily find
φ(n) = (p-1)·(q-1) = p·q - p - q + 1 = n - p - q + 1 (note: q = n/p) = n - p - n/p + 1 → φ(n)·p = p·n - p^2 - n + p → p^2 + p(φ(n) - n - 1) + n = 0
Solving for p we find two roots who correspond to
2 solves 3
First he computes
φ(n) = (p-1)·(q-1). Then, given that
e·d = 1 (mod φ(n))
and public exponent
e is known, is just a matter of applying the Extended
Euclidean Algorithm to compute the inverse
3 solves 1 (probabilistic)
d we use a probabilistic algorithm that gives
q and thus
x ∈ Zn.
x = gcd(x, n) > 1then we found a non-trivial factor of
n, we return
(p=x, q=n/x). This event has probability
e·d - 1 = s·2^rwith
e·dis odd, see lemma below)
Compute the sequence:
x0 = x^s mod n = x^(s·2^0) mod n
x1 = x0^2 mod n = x^(s·2^1) mod n
xr = x_(r-1)^2 mod n = x^(s·2^r) mod n = x^(ed - 1) mod n
For the encryption/decryption property of RSA:
x^(ed - 1) = x^ed · x^(-1) = x⋅x^(-1) ≡ 1 (mod n)
Thus starting from a
x0 ≠ 1there should be at some point a
xi = ±1, and for all
xj = 1. With probability
1/2we find that
xi = 1. If instead
xi = -1, then we repeat the procedure with another
xi ≠ ±1such that
xi^2 ≡ 1 (mod n)and thus
ncan’t be prime (ref. to Miller-Rabin primality testing).
xi^2 - 1 = (xi-1)·(xi+1) ≡ 0 (mod n) → n | (xi-1)·(xi+1)
The factors of
ncan’t all be in the first factor, because otherwise
n | (xi-1)and thus
xi ≡ 1 (mod n).
This means that some factors are in
(xi-1)and some others in
gcd(n, xi-1)should return some non-trivial factor of
e·d is odd.
Proof. Given that
φ(n) = (p-1)·(q-1) = (2·x)·(2·y) = 2·z and that
(e,φ(n)) = 1
e should be odd, same for
e·d is odd.
3 solves 4
If we have
d then we can then easily find
m using the decryption procedure.
4 doesn’t solve 3 (conjecture)
Can we find
d if we know an algorithm to find
m without knowing the key?
This is known as the RSAP (RSA Problem) and in practice here we’re asking if RSA is resistant to a chosen ciphertext attack.
There is a conjecture that postulates that this problem is as hard as the factorization problem. If not, RSA would be broken.
Side Channel Attacks
These attacks are using techniques which targets physical aspects of the cipher.
Some attack vectors:
- power consumption
- injected faults
Probably, the most popular one is the timing attack (Kocher-96).
When using a naive implementation, the execution time of the algorithm already says something about the secret exponent. For example, using the fast exponentiation algorithm where a 1 bit in the exponent corresponds to a multiplication.
The assumption is that the attacker is able to choose the ciphertext to decrypt. That is, a chosen ciphertext attack is possible.
Exponent bits are disclosed one after the other.
This type of attacks are very concrete and effective, more than analytical attacks that today are assumed to be infeasible.
- Constant time: all executions paths perform as the worst case.
- Random delays: insert random delays independent of the exponent.
When attacking a remote system, the attacker requires having a local copy of the remote system. Where he can try different keys.
Decryption is not directly applied to the ciphertext.
- Choose a random blinding factor:
r ∈ Zn*;
- Blind the ciphertext:
c' = r^e · c = (r·m)^e
- Decrypt the blinded ciphertext:
m' = c'^d = (r·m)^ed = r·m
- Remove the blinding:
m = r^-1·r·m
Because we are decrypting a value not known to the attacker, he can’t replicate the operation in its local device copy.
Blinding the message introduces a performance degradation of approximately 10%.
Another approach is to blind the exponent.
- Choose a random blinding factor:
r ∈ Zn*
- Blind the exponent:
d' = d + r·φ(p)
- Decrypt using the blinded exponent:
m = c^d' = c^d (mod p)
The described RSA cipher is known as textbook RSA.
Textbook RSA has some critical flaws:
If an encrypted message is multiplied by a factor
k^e then the corresponding
decrypted message will result multiplied by the factor
c = m^e → c' = k^e·c = (k·m)^e → m' = c'^d = k·m
This property allows to an attacker to manipulate an encrypted message to produce predictable results on the cleartext.
By definition in a public key cipher the attacker has always access to the encryption key.
If the attacker knows the whole set of possible plaintexts then he can then construct a dictionary of all the possible ciphertexts using the public key.
When the attacker intercepts a ciphertext he can then easily determiner what is the corresponding plaintext using a dictionary lookup.
One common solution to the above issues is to introduce some random factor as padding to the original message. The recipient should be able to remove the randoms factor after decryption.
Popular padding schemes:
- PKCS#1 v1.5: Specified in PKCS#1 v1.5 standard and probably the most popular.
- OAEP (Optimal Asymmetric Encryption Padding): Specified in PKCS#1 v2.0.
- PSS (Probabilistic Signature Scheme): similar to OAEP for digital signatures.
Vulnerabilities that emerge in particular use cases of textbook RSA.
Common Modulus Failure
Encrypt the same message
m using the two different encryption keys but with
the same modulus
c1 = m^e1 mod n c2 = m^e2 mod n
Let’s assume that with high probability
(e1,e2) = 1. An attacker can thus use
the EEA to compute
y such that
e1·x + e2·y = 1.
Finally, he can recover the plaintext:
c1' = c1^x = m^(e1·x) c2' = c2^y = m^(e2·y) c1'·c2' = m^(e1·x) · m^(e2·y) = m^(e1·x + e2·y) ≡ m (mod n)
Note that if
y < 0, set
y = -a, with
a > 0. Then
c2^y = (c2^-1)^aand
thus we also require that
(c2,n) = 1.
Low Exponent Failure
The public exponent is small and there are three keys that differs only for the modulus
(3, n1), (3, n2), (3, n3) c1 = m^3 mod n1 c2 = m^3 mod n2 c3 = m^3 mod n3
(ni, nj) = 1. If not we already found a factor for the modulus, and
thus we can trivially recover the message
The attacker writes a system of equations:
x ≡ c1 (mod n1) x ≡ c2 (mod n2) x ≡ c3 (mod n3)
Using the CRT we construct the unique solution
x ∈ Zn, with
n = n1·n2·n3.
The solution to this system is
x = m^3.
m < n1,
m < n2,
m < n3, thus
m^3 < n1·n2·n3 = n →
m^3 ∈ Zn.
x^-3: the ordinary cubic root of
x with no modulus involved.