Security of RSA – Secgroup Ca' Foscari

We now discuss the main results about security of RSA cipher.

Computing Φ(n)

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 $\Phi(n)$ . 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 $\frac{1}{2}$ . (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 $2^{16}+1 = 65537$ ) 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 $(3,n_1)$ , $(3,n_2)$ , $(3,n_3)$ giving the three ciphertexts $c_1,c_2,c_3$ such that $c_i = m^3 \mod n_i$ . Notice that moduli $n_1,n_2,n_3$ 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 $x < n_1n_2n_3$ such that $x \mod n_i = c_i$ , with an efficient way to compute it. Notice now that $m < n_i$ which implies $m^3 < n_1n_2n_3$ . By definition of $c_i$ we also have $m^3 \mod n_i = c_i$ . Thus the unique $x$ given by the Chinese Reminder Theorem must be equal to $m^3$ . It is now enough to compute $\sqrt[3]{x}$ to get $m$ .
In general, $b$ encryptions of the same message $m$ under different keys are enough to recover $m$ . Picking $b = 65537$ 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 $m^3 \mod n$ . Now it might be the case that $m^3 \leq n$ meaning that $m^3 \mod n = m^3$ . To decrypt is then enough to compute $\sqrt[3]{x}$ . Padding prevents this attack by making the size of $m$ close to the size of the modulus $n$ .

Partial information

It could be possible that an attacker is able to partially recover the plaintext. Let $y = E_{PK}(x)$ . Some examples of partial information follow:

$\begin{array}{rcl}\mathit{parity(y)}& = &\left\{\begin{array}{ll} 0 & \mbox{~~~if } x \mbox{ is even}\\1& \mbox{~~~otherwise}\end{array}\right.\\\\\mathit{half(y)}& = &\left\{\begin{array}{ll} 0 & \mbox{~~~if } 0 \leq x < n/2\\1& \mbox{~~~otherwise}\end{array}\right.\end{array}$

Function $\mathit{parity}(y)$ returns the parity of the plaintext, while $\mathit{half}(y)$ 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 $E_{PK}(x_1)E_{PK}(x_2) \mod n = E_{PK}(x_1x_2 \mod n)$ .

Proof. It is enough to apply the definition of encryption:

$\begin{array}{ll}E_{PK}(x_1)E_{PK}(x_2) \mod n & = x_1^bx_2^b \mod n \\&= (x_1x_2)^b \mod n =\\& (x_1x_2 \mod n)^b \mod n \\&= E_{PK}(x_1x_2 \mod n)\end{array}$

We can now prove that $\mathit{half}(y) = \mathit{parity}( E_{PK}(2) \ y \mod n)$ . Notice that $\mathit{parity}(E_{PK}(2) \ y \mod n) = \mathit{parity}(E_{PK}(2x \mod n))$ . Consider now the case $\mathit{half}(y) = 0$ . By definition we have $0\leq x<n/2$ which implies $0 \leq 2x < n$ , thus $2x \mod n = 2x$ which is certainly even, i.e., $\mathit{parity}(E_{PK}(2) \ y\mod n) = 0$ . If, instead, $\mathit{half}(y) = 1$ then $n/2<x<n$ which implies $n < 2x < 2n$ thus $2x \mod n = 2x - n$ which is certainly odd since $2x$ is even and $n$ is odd (it cannot be a multiple of 2). As a consequence $\mathit{parity}(y \times E_{PK}(2) \mod n) = 1$ .

In a similar way we can prove that $\mathit{parity}(y) = \mathit{half}( E_{PK}(2^{-1}) \ y \mod n)$ . We leave this proof as an exercise to the interested reader.

The following holds:

Theorem. Given an algorithm that computes $\mathit{half}(y)$ or $\mathit{parity}(y)$ it is possible to compute the whole plaintext $x$ .

Proof. Since $\mathit{half}(y)$ can be defined in terms of $\mathit{parity}(y)$ (see above), it is sufficient to prove that having $\mathit{half}(y)$ we can compute $x$ . It is enough to do a binary search, each time multiplying by $E_{PK}(2)$ 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 $\mathit{half}(y \ E_{PK}(2))$ . It is 0 when $2x \mod n \leq n/2$ which happens when $0 \leq x < n/4$ or $n/2 \leq x < 3n/4$ since we respectively obtain $0 \leq 2x < n/2$ and $n \leq x < 3n/2$ , the latter implying $0 \leq x \mod n < n/2$ . 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 $\lceil\log_2(n)\rceil$ .

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 $\tilde{y}$ by asking for decryptions of different ciphertexts ${y_1} \ldots {y_n}$ . The attack proceeds as follows: we pick a random $r$ such that $1 < r < n$ and is invertible modulo $n$ . The inverse can be computed using the extended Euclidean Algorithm (if it fails we pick another random $r$ ). We ask for decryption of $y_1 = \tilde{y} E_{PK}(r) \mod n$ . We obtain $x_1 = \tilde{x} r \mod n$ where $\tilde{x}$ is the decryption of $\tilde{y}$ . It is now sufficient to multiply this number by $r^{-1} \mod n$ to get $\tilde{x}$ .

References

[1] A. J. Menezes, P. C. van Oorschot, S. A. Vanstone, Handbook of Applied Cryptography, CRC Press.