RSA puzzling
RSA encryption is an asymmetric algorithm that uses very large integers as both keys and messages, and the 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\)
sing the Extended Euclidean algorithm, compute the invert \(d\) of \(e \mod 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\).
We must 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 thinks that the cipher text has been generated by using some permutation and uses all possible permutations of plain text to decipher the cipher text by ‘cycling’ the permutations; 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 is able to know \(p\) and \(q\) using \(n\), then it is possible to figure out the value of the private key.
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\). Marvin can try picking a random \(r ∈ Z_n^∗\) and sets \(m' = r^e m \mod n\) and then asks 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 m\), Alice can now compute \(s = s'/r \mod n\) and obtains Bob’s signature \(s\) on the original \(m\).
Low private exponent
If an attacker somehow guessed decryption key \(d\), putting not only the ciphertext generated by encryption and the plaintext with corresponding encryption key in danger, also future messages are at risk.
Wiener’s attack
Small value for \(e\) can lead to potential attacks known as attacks on the encryption key, such as Wiener’s attack on RSA with low private exponents.
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}\)). We know that when picking the public exponent \(e\) to be a small number and calculating its inverse \(d ≡ e^{−1} \mod ϕ(n)\).
Suppose we have 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 we’ve found \(d\) (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 on low private component \(d\) with a further relaxed condition. If \(d\) satisfies \(d < n^{0.292}\), then it is possible to use the Boneh-Durfee attack to retrive \(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 \(f \mod n\) that are less than \(x = n^{1/d}\). The algorithm’s running time decreases as \(x\) 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 (sending messages whose difference is less than N1/e can compromise RSA)
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 proscribed 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 out of 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 ε 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)^{ei} \mod n_i\), for \(i = 1,...,k\). Hastad showed that if enough parties are involved, Eve can recover the plaintext \(m\) from all the ciphertexts. In more generality, Hastad proved that a system of univariate equations modulo relatively prime composites, such as applying any fixed polynomial \(g_1(m) = 0 \mod n_i\), could be solved if sufficiently many equations are provided. 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 ε 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^k = 1\).
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 randomized padding suggested by Hastad is used improperly then RSA encryption is not secure.
Partial key exposure attack
This attack is possible when the public key is small. If an attacker exposed a fraction of the bits of \(d\), s/he can, on the assumption that the modulus is small, reconstruct the rest of \(d\). Boneh, Durfe, 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.