RSA

Prime Numbers & RSA Encryption Algorithm - ComputerphileComputerphile · primes and how RSA works, 15 minPublic Key Cryptography - ComputerphileComputerphile · public-key cryptography in plain words, 6 minThe RSA Encryption Algorithm (1 of 2: Computing an Example)Eddie Woo · a small RSA example: n, phi(n), e, d, 9 minPublic Key Cryptography: RSA EncryptionArt of the Problem · why RSA works: Euler's theorem and modular exponentiation, 16 min

Public-key principlesSearch on YouTubeBookmarkSaved

Private-key cryptographySearch on YouTubeBookmarkSaved

Traditional private / secret / single key cryptography uses one key. The sender and the receiver share that key. If the key is disclosed, the communications are compromised. The scheme is also symmetric, because the parties are equal.

Because both parties hold the same key, the scheme does not protect the sender. The receiver can forge a message and claim that the sender sent it.

Why public keySearch on YouTubeBookmarkSaved

Public-key cryptography uses two keys: a public key and a private key. It is asymmetric, because the parties are not equal. It uses number theory concepts. It complements private-key cryptography. It does not replace it.

Public-key cryptography was developed to address two key issues:

• Key distribution: secure communication without the need to trust a KDC with your key.
• Digital signatures: a method to verify that a message comes intact from the claimed sender.

The public invention is by Whitfield Diffie and Martin Hellman at Stanford University in 1976. The classified community knew the idea earlier.

Two-key cryptographySearch on YouTubeBookmarkSaved

Public-key / two-key / asymmetric cryptography uses two keys:

• A public key. Anybody can know it. It can encrypt messages and verify signatures.
• A related private key. Only the recipient knows it. It decrypts messages and signs (creates) signatures.

It is infeasible to find the private key from the public key. The scheme is asymmetric because the parties that encrypt messages or verify signatures cannot decrypt messages or create signatures.

Encryption with a public keySearch on YouTubeBookmarkSaved

The slide figure "(a) Encryption with public key" shows these steps:

1. Bob has a public key ring with the public keys of Joy, Mike, Ted and Alice.
2. Bob encrypts the plaintext $X$ with Alice's public key $PU_a$ (for example, with RSA).
3. The transmitted ciphertext is $Y = E[PU_a, X]$.
4. Alice decrypts with her private key $PR_a$: $X = D[PR_a, Y]$.

Symmetric vs public keySearch on YouTubeBookmarkSaved

Public-key cryptosystemsSearch on YouTubeBookmarkSaved

The "Public-Key Cryptosystems" figure gives secrecy and authentication together. Source A has the key pair $(PU_a, PR_a)$. Destination B has the key pair $(PU_b, PR_b)$.

Source A                                         Destination B
X --E(PRa)--> Y --E(PUb)--> Z ----> Z --D(PRb)--> Y --D(PUa)--> X

• A encrypts $X$ with its own private key $PR_a$. This step gives authentication (a signature).
• A encrypts the result $Y$ with B's public key $PU_b$. This step gives secrecy.
• B decrypts $Z$ with $PR_b$ to get $Y$. Then B decrypts $Y$ with $PU_a$ to get $X$.

$Z = E\big(PU_b,\, E(PR_a, X)\big) \qquad X = D\big(PU_a,\, D(PR_b, Z)\big)$

Uses and requirementsSearch on YouTubeBookmarkSaved

ApplicationsSearch on YouTubeBookmarkSaved

The uses fall into 3 categories:

• Encryption/decryption: provides secrecy.
• Digital signatures: provide authentication.
• Key exchange: of session keys.

Some algorithms are suitable for all uses. Other algorithms are specific to one use.

RequirementsSearch on YouTubeBookmarkSaved

Public-key algorithms rely on two keys with these properties:

• It is computationally infeasible to find the decryption key from only the algorithm and the encryption key.
• It is computationally easy to encrypt or decrypt messages when the related key is known.
• For some algorithms, either of the two related keys can encrypt, and the other key decrypts.

These requirements are formidable. Only a few algorithms satisfy them.

Trapdoor one-way functionsSearch on YouTubeBookmarkSaved

A public-key scheme needs a trapdoor one-way function. A one-way function is easy in the forward direction and infeasible in the inverse direction:

$Y = f(X) \ \text{easy} \qquad X = f^{-1}(Y) \ \text{infeasible}$

A trap-door one-way function has these properties:

• $Y = f_k(X)$ is easy, if $k$ and $X$ are known.
• $X = f_k^{-1}(Y)$ is easy, if $k$ and $Y$ are known.
• $X = f_k^{-1}(Y)$ is infeasible, if $Y$ is known but $k$ is not known.

A practical public-key scheme depends on a suitable trap-door one-way function. In RSA, the trapdoor is the factorization of $n$.

Security of public-key schemesSearch on YouTubeBookmarkSaved

A brute-force exhaustive search attack is always possible in theory, as with private-key schemes. But the keys are too large (more than 512 bits). Security relies on a large difference in difficulty between the easy problem (encrypt/decrypt) and the hard problem (cryptanalysis).

The hard problem is known, but it is made too hard to break in practice. This requires very large numbers. Thus public-key schemes are slow compared to private-key schemes.

The RSA algorithmSearch on YouTubeBookmarkSaved

OverviewSearch on YouTubeBookmarkSaved

Rivest, Shamir and Adleman of MIT made RSA in 1977. It is the best known and most widely used public-key scheme. It uses large integers (for example, 1024 bits). Its security comes from the cost of factoring large numbers.

Encryption and decryptionSearch on YouTubeBookmarkSaved

To encrypt a message $M$, the sender gets the recipient's public key $PU = \{e, n\}$ and computes:

$C = M^{e} \bmod n \qquad\text{where } 0 \le M \lt n$

To decrypt the ciphertext $C$, the owner uses the private key $PR = \{d, n\}$ and computes:

$M = C^{d} \bmod n$

The message $M$ must be smaller than the modulus $n$. Break a long message into blocks if necessary.

Key setupSearch on YouTubeBookmarkSaved

Each user makes a public/private key pair with these steps:

1. Select two large primes at random: $p$, $q$.
2. Compute the system modulus $n = p \cdot q$. Also compute $\phi(n) = (p-1)(q-1)$.
3. Select at random the encryption key $e$, where $1 \lt e \lt \phi(n)$ and $\gcd(e, \phi(n)) = 1$.
4. Solve $e \cdot d = 1 \bmod \phi(n)$, with $0 \le d \le n$, to find the decryption key $d$.
5. Publish the public encryption key: $PU = \{e, n\}$.
6. Keep the private decryption key secret: $PR = \{d, n\}$.

Figure 9.5 (The RSA Algorithm) gives the same steps in a table:

Why RSA worksSearch on YouTubeBookmarkSaved

RSA works because of Euler's theorem:

$a^{\phi(n)} \bmod n = 1 \qquad\text{where } \gcd(a, n) = 1$

In RSA, $n = p \cdot q$ and $\phi(n) = (p-1)(q-1)$. The values $e$ and $d$ are inverses mod $\phi(n)$. Thus $e \cdot d = 1 + k \cdot \phi(n)$ for some integer $k$. Therefore:

$C^{d} = M^{e \cdot d} = M^{1 + k \cdot \phi(n)} = M^{1} \cdot \left(M^{\phi(n)}\right)^{k} = M^{1} \cdot (1)^k = M^{1} = M \bmod n$

RSA worked exampleSearch on YouTubeBookmarkSaved

Key setup exampleSearch on YouTubeBookmarkSaved

The slide example has seven steps:

The $\gcd$ check: $160 = 2^{5} \times 5$. The prime 7 is not a factor of 160, thus $\gcd(7, 160) = 1$.

Encryption exampleSearch on YouTubeBookmarkSaved

The message is $M = 88$ ($88 \lt 187$). Encryption with $e = 7$:

$C = 88^{7} \bmod 187 = 11$

Trace of $88^{7}$, with $7 = 2 \times 3 + 1$:

Decryption exampleSearch on YouTubeBookmarkSaved

Decryption with $d = 23$:

$M = 11^{23} \bmod 187 = 88$

Square-and-multiply trace for $11^{23}$, with $23 = 16 + 4 + 2 + 1$:

Multiply the remainders of $11^{16}$, $11^{4}$, $11^{2}$ and $11^{1}$. Reduce mod 187 after each multiplication.

Key generation in practiceSearch on YouTubeBookmarkSaved

The users of RSA must:

• Find two primes at random: $p$, $q$.
• Select either $e$ or $d$, and compute the other.

An attacker must not be able to find the primes $p$, $q$ easily from the modulus $n = p \cdot q$. Thus the primes must be sufficiently large. Typically, you guess a candidate and use a probabilistic primality test. The exponents $e$ and $d$ are inverses, so use the inverse algorithm (extended Euclid) to compute one from the other.

Attacks on RSASearch on YouTubeBookmarkSaved

Attack typesSearch on YouTubeBookmarkSaved

The possible approaches to attack RSA are:

Factoring problemSearch on YouTubeBookmarkSaved

The mathematical approach takes 3 forms:

• Factor $n = p \cdot q$, then compute $\phi(n)$ and then $d$.
• Find $\phi(n)$ directly and compute $d$.
• Find $d$ directly.

Timing attacksSearch on YouTubeBookmarkSaved

Paul Kocher developed timing attacks in the mid-1990s. The attack uses timing variations in operations. For example, a multiplication by a small number takes a different time than a multiplication by a large number. IF statements also change which instructions execute.

The attacker infers the operand size from the time taken. In RSA, the attacker uses the time taken in exponentiation. The countermeasures are:

• Use a constant exponentiation time.
• Add random delays.
• Blind the values used in calculations.

Chosen ciphertext attacksSearch on YouTubeBookmarkSaved

RSA is vulnerable to a Chosen Ciphertext Attack (CCA). The attacker chooses ciphertexts and gets the decrypted plaintext back. The attacker chooses the ciphertexts to use the properties of RSA. The results give information that helps cryptanalysis.

The countermeasures are a random pad of the plaintext, or Optimal Asymmetric Encryption Padding (OAEP).

Quick self-testSearch on YouTubeBookmarkSaved