Public-Key Cryptography and RSA

Lecturer:

Prof. Dr. Michael Eichberg

Version:
2023-10-19
Based on:

Cryptography and Network Security - Principles and Practice, 8th Edition, William Stallings

Misconceptions Concerning Public-Key Encryption

Principles of Public-Key Cryptosystems

Principles of Public-Key Cryptosystems

Whitfield Diffie and Martin Hellman from Stanford University achieved a breakthrough in 1976 by coming up with a method that addressed both problems and was radically different from all previous approaches to cryptography.

Ingredients of Public-Key Cryptosystems

  1. Plaintext: The readable message or data that is fed into the algorithm as input

  2. Encryption algorithm: Performs various transforma-tions on the plaintext

  3. Public Key: Used for encryption or decryption

  4. Private Key: Used for encryption or decryption

  5. Ciphertext: The scrambled message produced as output

  6. Decryption algorithm: Accepts the ciphertext and the matching key and produces the original plaintext.

Encryption with Public Key

Encryption with public key

Encryption with Private Key

Encryption with private key

Conventional and Public-key Encryption

Conventional Encryption

Needed to Work:

  1. The same algorithm with the same key is used for encryption and decryption.

  2. The sender and receiver must share the algorithm and the key.

Needed for Security:

  1. The key must be kept secret.

  2. It must be impossible or at least impractical to decipher a message if the key is kept secret.

  3. Knowledge of the algorithm plus samples of ciphertext must be insufficient to determine the key.

Public-Key Encryption

Needed to Work:

  1. One algorithm is used for encryption and a related algorithm for decryption with a pair of keys, one for encryption and one for decryption.

  2. The sender and receiver must each have one of the matched pair of keys (not the same one).

Needed for Security:

  1. One of the two keys must be kept secret.

  2. It must be impossible or at least impractical to decipher a message if one of the keys is kept secret.

  3. Knowledge of the algorithm plus one of the keys plus samples of ciphertext must be insufficient to determine the other key.

Public-Key Cryptosystem: Confidentiality

Confidentiality

Public-Key Cryptosystem: Authentication

Authentication

Public-Key Cryptosystem: Authentication and Secrecy

Authentication and Secrecy

Applications for Public-Key Cryptosystems

Applications for Public-Key Cryptosystems

Algorithm

Encryption/Decryption

Digital Signature

Key Exchange

RSA

Yes

Yes

Yes

Elliptic Curve

Yes

Yes

Yes

Diffie-Hellman

No

No

Yes

DSS

No

Yes

No

DSS = Digital Signature Standard developed by the NSA (National Security Agency)

Public-Key Requirements

Conditions that these algorithms must fulfill:

Public-Key Requirements

Public-Key Cryptanalysis

Rivest-Shamir-Adleman (RSA) Algorithm

RSA Algorithm

Algorithm Requirements

The RSA Algorithm

Key Generation by Alice

Encryption by Bob with Alice's Public Key

Decryption by Alice with Alice's Private Key

Example of RSA Algorithm

p and q:

\(p = 11; q = 17; n = 187\)

Plaintext:

88

Encryption:

\(PU =\lbrace e= 7, n= 187 \rbrace\):

\(88^7\;mod\; 187 = 11 = C\)

Decryption:

\(PR =\lbrace d= 23, n = 187 \rbrace\):

\(11^{23}\; mod\; 187 = 88 = P\)

Exponentiation in Modular Arithmetic

Algorithm for Computing \(a^k\; mod\; n\)

(Square and Multiply)

The integer \(b\) is expressed as a binary number b[k]b[k-1]...b[0]:

c := 0; f := 1
for i := k downto 0
    do c := 2 * c
       f := (f * f) mod n
    if b[i] = 1
        then c := c + 1
             f := (f * a) mod n
return f

Result of the Fast Modular Exponentation Algorithm for \(a^b\;mod\;n\)

\(a=7; b = 560 = 1000110000_b\), and \(n=561\)

i

9

8

7

6

5

4

3

2

1

0

\(b_i\)

1

0

0

0

1

1

0

0

0

0

c

1

2

4

8

17

35

70

140

280

560

f

7

49

157

526

160

241

298

166

67

1

Efficient Operation Using the Public Key

Efficient Operation Using the Private Key

Key Generation

Before the application of the public-key cryptosystem each participant must generate a pair of keys:

  • Determine two prime numbers \(p\) and \(q\)

  • Select either \(e\) or \(d\) and calculate the other

  • Because the value of n = pq will be known to any potential adversary, primes must be chosen from a sufficiently large set.

  • The method used for finding large primes must be reasonably efficient.

    The Miller-Rabin Algorithm can, e.g., be used.

The Security for RSA - Five possible approaches to attacking RSA

Factoring Problem

We can identify three approaches to attacking RSA mathematically:

  1. Factor \(n\) into its two prime factors. This enables calculation of \(\phi(n) = (p - 1) \times (q - 1)\), which in turn enables determination of \(d = e^{-1} (mod\; ø(n))\).

  2. Determine \(\phi(n)\) directly without first determining \(p\) and \(q\). Again, this enables determination of \(d = e^{-1} (mod\; \phi(n))\).

  3. Determine \(d\) directly without first determining \(\phi(n)\).

Timing Attacks

Countermeasures

Constant exponentation time:

Ensure that all exponentiations take the same amount of time before returning a result; this is a simple fix but does degrade performance.

Random delay:

Better performance could be achieved by adding a random delay to the exponentiation algorithm to confuse the timing attack.

Blinding:

Multiply the ciphertext by a random number before performing exponentiation; this process prevents the attacker from knowing what ciphertext bits are being processed inside the computer and therefore prevents the bit-by-bit analysis essential to the timing attack

Fault-Based Attack

Chosen Ciphertext Attack (CCA)