RSA: Asymmetric Cryptographic Systems

RSA and other cryptographic algorithms make use of trapdoor functions. Public key cryptography differs from shared key cryptographic systems, in that unlike a shared key, we have two different keys, one of which is shared publicly, and the other which is retained privately.

In a shared system, both parties have to agree on and use the same key. These systems may also be categorised as symmetric cryptosystems, and include those discussed earlier, including DES, 3DES, Twofish, and now very commonly AES.

Problems

Shared key systems, whilst extremely efficient in their encryption and decryption schemes have two major flaws. Compromised keys mean that any interceptor can decrypt the ciphertext that they have acquired. This is typically combatted with a rekeying interval, which happens after a set time or set number of blocks, and is laid out in the standards.

The second major problem with a symmetric system is that the keys must be distributed to the other party securely, either in pieces through separate channels (e.g., new debit card and PIN sent separately), or by encapsulating the key in something such as an asymmetric system.

The concept of public and private keys makes the idea much more approachable to the layperson. Each person has a public key from another user, which they can then use as part of an encryption algorithm. Once encrypted, the data had gone through the one-way function, and cannot then be decrypted with just the public key. This differs to AES, or other shared systems, as these are reversible with the same key.

From here, the data can be submitted in a clear channel to the recipient. If the recipient has the correct private key, then a decryption of the ciphertext can be done to yield a plaintext output.

Trapdoor Functions

Trapdoor functions are a pair of functions \(f,f^{-1}\) such that given \(x\), the evaluation of \(y = f(x)\) is trivial, but given only \(f,y\), the evaluation of \(f^{-1}(y)\) to yield \(x\) is computationally difficult. Given \(f^{-1},y\), then the evaluation of \(f^{-1}(y)\) is trivial.

In common terms, \(x\) is the plaintext, \(y\) is the ciphertext, \(f\) is the public key, and \(f^{-1}\) is the private key.

Formally a trapdoor function \(X \to Y\) is a triple of efficient algorithms \((G, G, F^{-1})\), with \(G\) a key generation algorithm outputting a keypair \((pk,sk)\), an encryption function \((pk, \cdot)\) which is a function \(X \to Y\), and a decryption function \(F^{-1}(sk, \cdot)\) which maps \(Y \to X\), and inverts \(F(pk, \cdot)\).

\[ \forall(pk,sk) \in G, \forall x \in X: F^{-1}(sk, F(pk, x)) = x \]

A secure TDF will be secure if \(F\) is a one way function, such that \(F\) can be evaluated but not inverted without the secret key. When evaluating the security, we assume that the adversary is able to acquire the encrypted message \(C\), the public key of the recipient \(pk\), and the trapdoor function.

They can then try and decrypt the message by finding the inverse of the function \(F\) and applying it to the ciphertext. This function would take the form:

\[ A(C,F,pk) \to p' \]

And in the same way that we defined what a secure symmetric function is, we say that the triple \((G, F, F^{-1})\) is a secure TDF if for all efficient \(A\):

\[ \text{Adv}[A,F] = Pr[p=p'] \]

Improper Use

Trapdoor functions can never be used properly by applying them to a plaintext. If we do this, then for the same input, we yield the same output. Many attacks exist on this, so we need to do something better.

We're now going to go back to some modular arithmetic from the last lecture.

Quick Recall of Number Theory

Let \(N=pq\), where \(p,q\) are prime. \(\mathbb{Z}_N = \{0,1,2,\dots,N-1\}, (\mathbb{Z}_N)^*\) is the set of invertible elements in \(\mathbb{Z}_N\).

If a number \(x \in \mathbb{Z}_N\) is invertible, then \(\gcd(x,N) = 1\). The number of elements in \((\mathbb{Z}_N)\) is \(\phi(N) = (p-1)(q-1) = N - p - q + 1\).

The Euler Totient function \(\phi\) is defines differently dependant on whether \(N = p\) where \(p\) is prime, in which case it is \(\phi(N) = N-1\). For composite primes, \(N = pq\), where \(p,q\) are prime, then it is defined as \((p-1)(q-1)\).

Euler's Theorem is also a generalisation of Fermat's Theorem:

\[ \forall x \in (\mathbb{Z}_N)^*: x^{\phi(N)} \mod N = 1 \]

The RSA Algorithm

Key Generation

The basic algorithm is:

Choose random primes \(p,q\)
Set \(N=pq\)
Choose integers \(e,d | ed = 1 (\mod \phi(N))\)
Output \(pk = (N,e), sk = (p,q,d)\)

The encryption algorithm for the function is:

\[ F(pk, x) : \mathbb{Z}_N \to \mathbb{Z}_N: RSA(x,e) = x^e = y \]

Taking the private key and integer \(e\), giving \(x^e\) in the output. This is possible to do using just the public key of the recipient and the plaintext. The recipient at the other end can then perform the decryption algorithm:

\[ F(sk, y) : \mathbb{Z}_N \to \mathbb{Z}_N : RSA(y,d) = y^d = x \]

Using Modular arithmetic properties, we can prove that \(y^d = x | x,y \in ( \mathbb{Z}_N)^*\). The proof of this algorithm is given in the original RSA paper.

Example

For key generation, we select \(p=17,q=11\). We can then compute \(N = pq = 17 \times 11 = 187\). As \(N\) is a composite prime, we can use the Euler Totient function to compute \(\phi(N) = (p-1)(q-1) = 16 \times 10 = 160\).

We then need to choose some integer \(e\) such that \(\gcd(e,160)=1\). In this instance, we can choose \(e=7\). We can then determine \(d\) such that \(de = 1 \mod 160\). We can choose \(d = 23\) as \(23 \times 7 = 161 = 1\) in \(\mathbb{Z}_{160}\).

We can publish \((187, 7)\) and keep \((17,11,23)\) secret. To encrypt a message \(M = 90\), we take \(90^7 \mod 187 = 95\). Given this, we can then decrypt, with \(M=95^{23}\mod 187 = 90\).

Example 2

Construct an RSA encryption scheme with primes \(p=5,q=11\). \(N = pq = 55\). \(\phi(55) = (p-1)(q-1) = 4 \times 10 = 40\). Select \(e : \gcd(e,40) = 1\). Let's choose \(e=3\). Then we get \(de = 1 \mod 40\). If we choose \(d=27\), then \(27 \times 3 \mod 40 = 81 = 1\) in \(\mathbb{Z}_40\).

Therefore, we have \((N,e) = (55,3)\) and \((p,q,d) = (5,11,27)\).

TODO add more from exercises at end of lecture.

Security

To invert the one way function of RSA without \(d\), the attacker needs to compute:

\[ y = (x^e) (\mod N) \quad x = \sqrt[e]{y} \mod N \]

If the adversary could factorize \(N\), then they would know \(p,q\), which would give them \(\phi(n)\). \(e\) is public knowledge, so they could then find \(d\) and compute \(x = y^d\).

RSA is secure because it depends on the fact that it is very difficult to factorize large integers.

Brute Force

It is possible to find \(p\) and \(q\) by first finding \(\sqrt{n}\). Once this has been done, we then know that \(p \le \sqrt{n}\) or \(q \le \sqrt{n}\). We can then divide \(n\) by each of the primes \(p,q\) until a factor is found.

The number of primes \(\le \sqrt{n} \approx \frac{2\sqrt{n}}{\ln(n)}\), so as \(n\) gets large, this becomes very inefficient.

Fermat Numbers

Fermat numbers are integers of the following form:

\[ F_i = 2^{(2^i)} + 1, i \ge 1 \]

\(F_1=5, F_2 = 17, F_3 = 257, F_4 = 65537\). In 1732, Euler found \(F_5\), in 1880, Landry and LeLasser found \(F_6\), in 1970, Morrison and Brillhart found \(F_7\), in 1980 Brent and Pollart found \(F_8\). As of 2018, we have factorized up to \(F_{11}\).

Most Efficient Algorithm

Currently, the most efficient algorithm to factorize is the number field sieve, which has runtime \(e^{O(\sqrt[3]{N})}\). The current record for this is RSA-768, with 232 digits, taking two years and 100s of machines. For a 1024-bit integer, this is currently infeasible.

Choice of Primes

When choosing primes \(p\) and \(q\), we need to take some precautions to make it infeasible for an algorithm that works better for specific sets of primes, e.g., the Fermat factorization.

Fermat's factorisation method is based on the representation of an odd integer as the difference of two squares:

\[ N = i^2 - j^2 = (i-j)(i+j) \]

If \(N\) can be factored as \(N=pq\), then this can be written as

\[ N = \left(\frac{p+q}{2}\right)^2 - \left(\frac{p-q}{2}\right)^2 \]

Therefore, if we pick \(p,q\) close together, the second term \(\frac{p-q}{2} \approx 0\) and therefore \(\sqrt{N} \approx \frac{p+q}{2}\). This is because the second term in the equation would almost cancel out.

The way to compute this factorisation would be to choose integers \(i\) slightly larger than \(\sqrt{n}\). We could then test whether \(i^2 - N\) is a perfect square \(j^2\) for some integer \(j\). If we can find \(i\), then \(N = i^2 - j^2 = (i-j)(i+j)\).

To factorize \(N=11413\), we take \(\sqrt{N} = 106.83\). Take \(107 > \sqrt{N}\). We then try \(i = 107\), such that \(i^2 - N = 11449 - 11413 = 36 = 6^2\), which would give us \(N = 107^2 - 6^2 - (107 - 6) (107 + 6) = 101 \times 113\).

Textbook RSA Security

RSA in textbooks gives a public key \((N,e)\), and a secret key \((N,d)\). The encryption function is \(m^e = c\), and decrypt is \(c^d = m\), within \(\mathbb{Z}_N\).

This is similar to our definition, but we store \(p,q\) instead of \(N\), thus knowing the prime factorisation and having the ability to derive the public key.

Use in Practice

For RSA, we typically take 128-bit private RSA key, then preprocess it somehow. Following this preprocessing, we feed it into the RSA encryption algorithm, using the other person's public key which then allows us to establish an encrypted key session, provided we can guarantee that the public key belongs to the other user.

RSA Encryption Modes

As with AES, we make use of modes before encrypting and decrypting. The lecture slides mentions PKCS1 mode 2, which takes 16 bits for 02, then adds some random pad, terminates it with FF, then encrypts the message.

PKCS1 v1.5 has been proven vulnerable and multiple attacks on it exist.

Implementation Attacks

These are all side-channel attacks.

Timing Attacks

We can exploit timing variations that occur from the multiplication of a large vs. small number. In RSA, the time taken to compute \(y^d (\mod N)\) can expose \(d\). We can mask the times by adding random operations or delays to loops.

Modular Exponentiation

We can either compute a power as \(y^d = y y y y \cdots\), \(d\) times, giving a directly proportional time to the exponent value. The other main method is to use repeated squaring, to compute the same value, but with the following pseudocode implementation:

s = y
for i = 1 to m
  s = s^2 (mod n)
  if d_i == 1 then
    s = s*y (mod n)
  endif
next i
return s

Power Attacks

This is another side channel attack developed in the 1990s by Kocher et. al. The power consumption of a cipher hardware will be different under different input values. We can make use of this to infer the key. If we take a smart card, we can analyse the power consumption whilst it computes \(c^d (\mod N)\) to expose \(d\).

To counter this, we can mask the power consumption on chip, by completing redundant operations, or using power balanced circuitry.