We now discuss the main results about security of RSA cipher.
As already discussed, security of RSA is based on the secrecy of Φ(n)=(p-1)(q-1). It is however trivial to see that computing Φ(n) is at least as difficult as factoring n. Given an algorithm that computes Φ(n) it is enough to solve the system of equations:
n = pq
Φ(n) = (p-1)(q-1)
to compute p and q.
Computing the private exponent
It could be possible, in principle, to compute the private exponent without necessarily computing . It can be proved that this would allow to factor n:
Theorem. Given an algorithm that computes exponent a we can write a probabilistic “Las Vegas” algorithm that factorises n with probability at least . (See [1, page 287] for more detail).
As for Monte Carlo algorithms, we can iterate a Las Vegas algorithm as needed. This proves that if an exponent is leaked then n is compromised, thus breaking a private key is as difficult as factoring. Notice also that once we leak a private key the modulus is no more secure. This implies that n should never be reused for different key pairs: any time we generate a key pair we need to generate a new modulus n.
Small encryption exponents
We have already observed that implementations of RSA use small encryption exponents (typically ) to improve the performance of encryption function. We discuss some attacks that are possible if we choose an excessively small exponent such as 3.
Attack 1: same message encrypted under different moduli
Suppose the same message m is sent encrypted under at least three different public keys , , giving the three ciphertexts such that . Notice that moduli are very likely to be coprime as they will not share their prime factors. The Chinese Reminder Theorem [1, page 68] applies and proves that there exists a unique such that , with an efficient way to compute it. Notice now that which implies . By definition of we also have . Thus the unique given by the Chinese Reminder Theorem must be equal to . It is now enough to compute to get .
In general, encryptions of the same message under different keys are enough to recover . Picking makes this attack quite unlikely. Moreover the attack can be prevented by a randomized padding scheme such as PKCS1 which transforms message m into a k-bits long message EM = 0x00 || 0x02 || PS || 0x00 || m, where PS is a sequence of random bytes different from 0. In this way any time we encrypt m we in fact encrypt a different plaintext. Notice that PKCS1 enables padding-oracle attacks and is superseded by the more secure Optimal Asymmetric Encryption Padding (OAEP).
Attack 2: small messages
Padding is also needed because of the following trivial attack on small messages encrypted under small exponents. Consider a small m encrypted with exponent 3. We have . Now it might be the case that meaning that . To decrypt is then enough to compute . Padding prevents this attack by making the size of close to the size of the modulus .
It could be possible that an attacker is able to partially recover the plaintext. Let . Some examples of partial information follow:
Function returns the parity of the plaintext, while tells if the plaintext is less then half of the modulus. First we show that the latter can be defined based on the former. This result exploits the following fundamental property of RSA:
Theorem (RSA multiplicative property). RSA cipher is such that .
Proof. It is enough to apply the definition of encryption:
We can now prove that . Notice that . Consider now the case . By definition we have which implies , thus which is certainly even, i.e., . If, instead, then which implies thus which is certainly odd since is even and is odd (it cannot be a multiple of 2). As a consequence .
In a similar way we can prove that . We leave this proof as an exercise to the interested reader.
The following holds:
Theorem. Given an algorithm that computes or it is possible to compute the whole plaintext .
Proof. Since can be defined in terms of (see above), it is sufficient to prove that having we can compute . It is enough to do a binary search, each time multiplying by the ciphertext, and getting the left/right interval depending on the value of half. It is obvious that this works for the first step (definition of half exactly tells us whether x belongs to the first half or the second half of the interval). Then, think of . It is 0 when which happens when or since we respectively obtain and , the latter implying . This reasoning can be applied, similarly, to next steps until a single solution survives. Since each time the interval in split in two, the number of steps is .
The following is a working python code. Notice that half and enc function must be provided.
import math from decimal import * def partial(y,n): k = int(math.ceil(math.log(n,2))) # n. of iterations enctwo = enc(2) # the encryption of 2 getcontext().prec = k # allows for 'precise enough' floats l=Decimal(0) u=Decimal(n) for _ in range(k): h = (l+u)/2 if (half(y,n) == 0): u = h # we get the left interval else: l = h # we get the right interval y=(y*enctwo) % n # multiply y by the encryption of 2 print int(u)
Chosen ciphertext attack
We conclude this section about security of RSA by illustrating a simple attack under the very powerful attacker that can choose ciphertexts to decrypt. The challenge is to decrypt a ciphertext by asking for decryptions of different ciphertexts . The attack proceeds as follows: we pick a random such that and is invertible modulo . The inverse can be computed using the extended Euclidean Algorithm (if it fails we pick another random ). We ask for decryption of . We obtain where is the decryption of . It is now sufficient to multiply this number by to get .
 A. J. Menezes, P. C. van Oorschot, S. A. Vanstone, Handbook of Applied Cryptography, CRC Press.