RSA puzzling¶
RSA encryption is an asymmetric algorithm that uses very large integers as both keys and messages, and modular exponentiation as the primary mathematical operator for encryption and decryption. The algorithm is simple to understand and relatively easy to implement:
Key generation
Key distribution
Encryption
Decryption
Message encryption is done with a Public Key, and message decryption is done with a Private Key, parameters (\(p\), \(q\), \(d\)) generated together with the Public Key. The private key is known only to the user, and the public key can be made known to anyone who wishes to send an encrypted message to the person with the corresponding private key.
Key generation¶
Pick two primes \(p\) and \(q\)
Using \(p\) and \(q\), calculate modulus \(n = p × q\) and its Euler’s totient \(ϕ(n) = (p−1) × (q−1)\)
Choose the public exponent \(e\) with \(gcd(e,ϕ(n)) = 1\)
Using the Extended Euclidean algorithm, compute the inverse \(d\) of \(e\) modulo \(ϕ(n)\): \(d ≡ e^{−1} \mod (ϕ(n))\), which is the private exponent.
Public key: \(n, e\)
Private key: \(n, d\)
Choose a message \(m\) to convert into integers
Encrypt this plaintext \(m\) and receive a ciphertext \(c ≡ m^e \mod n\)
Decrypt a ciphertext \(c\) with \(m ≡ c^d \mod n\)
Trapdoor function¶
All public-key systems are based on the concept of trapdoor functions, simple to compute in one direction and computationally hard to reverse without knowledge of some special information called the trapdoor. In RSA, the trapdoor function is based on the hardness of factoring integers. Except in certain cases, there exists no efficient algorithm for factoring huge integers.
The RSA trapdoor permutation is the core algorithm behind RSA-based encryption and signatures. Given a modulus \(n\) and number \(e\), the public exponent, the RSA trapdoor permutation transforms a number \(x\) from the set \(Z_n^*\) into a number \(y = x^e \mod n\).
When using the RSA trapdoor permutation to encrypt, the modulus \(n\) and the exponent \(e\) make up the RSA public key.
In order to get \(x\) back from \(y\), \(d\) is used:
Because \(d\) is the trapdoor that allows decryption, it is part of the private key in the RSA key pair, and, unlike the public key, should always be kept secret. It is also called the secret exponent.
\(d\) is not just any number; it is the number such that \(e\) multiplied by \(d\) is equivalent to 1, and therefore such that \(x^{ed} \mod n = x\) for any \(x\).
It is necessary to have \(ed = 1 \mod φ(n)\) in order to get \(x^{ed} = x^1 = x\) and to decrypt the message correctly. It is necessary to compute modulo \(φ(n)\) and not modulo \(n\) because exponents behave like the indexes of elements of \(Z_n^*\) rather than as the elements themselves. Because \(Z_n^*\) has \(φ(n)\) elements, the index must be less than \(φ(n)\).
Finding \(φ(n)\) for an RSA modulus n is equivalent to breaking RSA, because the secret exponent \(d\) can easily be derived from \(φ(n)\) and \(e\), by computing \(e\)’s inverse. Therefore, \(p\) and \(q\) must also be kept secret, since knowing \(p\) or \(q\) gives \(φ(n)\) by computing \((p-1)(q-1) = φ(n)\).
Elementary attacks¶
These include short message attacks in which an attacker knows some blocks of plaintext and tries to decode cipher text with the help of that; cycling attacks, in which the attacker re-encrypts the ciphertext with the public key repeatedly until the original ciphertext reappears, the value one step before it being the plaintext, which works because RSA is a permutation but costs far too much at real key sizes; attacks in which an attacker uses the Extended Euclidean Algorithm to retrieve the plaintext based on ciphertext; and sometimes it happens that the plain text is the same as the cipher text after encryption.
And if an attacker can recover \(p\) and \(q\) from \(n\), the private key can be worked out.
Common modulus¶
To avoid generating a different modulus \(n\) for each user, one may wish to fix \(n\). The same \(n\) is used by all users. A trusted central authority could provide user \(i\) with a unique pair \(e_i, d_i\) from which user \(i\) forms a public key \((n, e_i)\) and a secret key \((n, d_i)\).
The resulting system is insecure. User Bob can use his own exponents \(e_b, d_b\) to factor the modulus \(n\). Once \(n\) is factored Bob can recover Alice’s private key \(d_a\) from her public key \(e_a\).
Blinding¶
Let \((n, d)\) be Bob’s private key and \((n, e)\) his public key. Suppose Alice wants Bob’s signature on a message \(m ∈ Z_n^*\). Bob refuses to sign \(m\). Alice can pick a random \(r ∈ Z_n^*\), set \(m' = r^e m \mod n\), and then ask Bob to sign the random message \(m'\). Bob may be willing to provide his signature \(s'\) on the innocent-looking \(m'\).
Because \(s' = (m')^d \mod n\), Alice can now compute \(s = s'/r \mod n\) and obtains Bob’s signature \(s\) on the original \(m\).
Low private exponent¶
An attacker who recovers the decryption key \(d\) endangers not only the ciphertext already sent, but every future message encrypted under the same key.
Wiener’s attack¶
Wiener’s attack is an attack on RSA that uses continued fractions to find the private exponent \(d\) when it is small (less than \(\frac{1}{3} \sqrt[4]{n}\)).
Given the public key \((n,e)\), this attack will determine \(d\):
Convert the fraction \(\frac{e}{n}\) into a continued fraction \([a_0;a_1,a_2,…,a_{k−2},a_{k−1},a_k]\).
Iterate over each convergent in the continued fraction:
Check if the convergent is \(\frac{k}{d}\) by:
Setting the numerator to be \(k\) and denominator to be \(d\)
Check if \(d\) is odd, if not, move on to the next convergent
Check if \(ed ≡ 1 \mod(k)\), if not, move on to the next convergent
Set \(ϕ(n) = \frac{ed−1}{k}\) and find the roots of the polynomial \(x^2 − (n−ϕ(n)+1)x + n\)
If the roots of the polynomial are integers, then \(d\) has been found (If not, move on to the next convergent).
If all convergents have been tried, and none of them work, then the given RSA parameters are not vulnerable to Wiener’s attack.
Boneh-Durfee attack¶
The Boneh-Durfee attack is an extension of Wiener’s attack. That is, it also attacks the low private exponent \(d\) with a further relaxed condition. If \(d\) satisfies \(d < n^{0.292}\), then it is possible to use the Boneh-Durfee attack to retrieve \(d\).
Low public exponent¶
Coppersmith¶
The most powerful attacks on low public exponent RSA are based on the Coppersmith theorem. The theorem provides an algorithm for efficiently finding all roots of a monic polynomial \(f\) of degree \(d\) modulo \(n\) that are smaller than about \(n^{1/d}\). The algorithm’s running time decreases as that bound gets smaller. The strength of this theorem is its ability to find small roots of polynomials modulo a composite \(n\).
Application of Coppersmith’s Theorem:
Attack stereotyped messages in RSA (a message whose unknown portion is smaller than about \(n^{1/e}\) can be recovered)
Security proof of RSA-OAEP (constructive security proof).
Affine Padding
Polynomially related RSA messages (sending the same message to multiple recipients)
Factoring \(n = pq\) if the high bits of \(p\) are known.
An algorithm that can get the private key for RSA in deterministic polynomial time can be used to factor \(n\) in deterministic polynomial time.
Finding integers with a large smooth factor in a prescribed interval.
Finding roots of modular multivariate polynomials.
Håstad’s broadcast attack¶
Suppose Bob wishes to send an encrypted message \(m\) to a number of parties \(p_1, p_2, ... p_k\). Each party has its own RSA key \((n_i, e_i)\). Assume \(m\) is less than all the \(n_i\)’s. To send \(m\), Bob encrypts it using each of the public keys and sends the \(i\)th ciphertext to \(p_i\). An attacker Eve can eavesdrop on the connection and collect the \(k\) transmitted ciphertexts.
Suppose that for each of the participants \(p_1, ... ,p_k\), Bob has a fixed public polynomial \(f_i \in Z_{n_i}[x]\). To broadcast a message \(m\), Bob sends the encryption of \(f_i(m)\) to party \(p_i\). By eavesdropping, Eve learns \(C_i = f_i(m)^{e_i} \mod n_i\), for \(i = 1,...,k\). Håstad showed that if enough parties are involved, Eve can recover the plaintext \(m\) from all the ciphertexts. More generally, Håstad proved that a system of univariate equations modulo relatively prime composites, of the form \(g_i(m) = 0 \mod n_i\), could be solved given sufficiently many equations. This attack suggests that randomised padding should be used in RSA encryption.
Let \(n_1, ... ,n_k\) be pairwise relatively prime integers and set \(n_{min} = \min_i (n_i)\). Let \(g_i \in Z_{n_i}[x]\) be \(k\) polynomials of maximum degree \(d\). Suppose there exists a unique \(m < n_{min}\) satisfying \(g_i(m) = 0 \mod n_i\) for all \(i = 1, ... ,k\).
Under the assumption that \(k > d\), one can efficiently find \(m\) given \((n_i, g_i)_{i=1}^k\).
Franklin-Reiter related message attack¶
Franklin and Reiter found an attack (pdf) when Bob sends Alice related encrypted messages using the same modulus. Let \((n, e)\) be Alice’s public key. Suppose \(m_1, m_2\) are two distinct messages such that \(m_1 = f(m_2) \mod n\) for some publicly known polynomial \(f\). If Bob encrypts the messages and transmits the resulting ciphers \(c_1\) and \(c_2\), an attacker can easily recover \(m_1\) and \(m_2\).
Coppersmith’s short pad attack¶
Generally, the Franklin-Reiter attack is considered to be an artificial attack because why should Bob send Alice the encryption of related messages? Coppersmith strengthened the attack and proved an important result on padding. Coppersmith showed that if randomised padding suggested by Håstad is used improperly then RSA encryption is not secure.
Partial key exposure attack¶
This attack is possible when the public exponent is small. If an attacker exposes a fraction of the bits of \(d\), they can, on the assumption that the public exponent is small, reconstruct the rest of \(d\). Boneh, Durfee, and Frankel (pdf) gave proof that \(d\) can be reconstructed as long as \(e < √n\).
Implementation attacks¶
Instead of attacking the underlying structure of RSA function, these attacks target the implementation of RSA.
Timing attacks¶
Consider a smartcard that stores a private RSA key. An attacker may not be able to see its content and expose the key, but Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems (pdf) explains that carefully measuring the amount of time required to perform private key operations, can help an attacker find or discover the private decryption exponent \(d\). Repeated squaring algorithm can be used for this attack.
Random faults¶
To speed up the computation of \(m^d \mod n\), implementations of RSA decryption and signatures frequently use the Chinese Remainder Theorem. Instead of working modulo \(n\), the signer Bob first computes the signatures modulo \(p\) and \(q\) and then combines the result using the Chinese Remainder Theorem.