Public key cryptography and RSA

Question 1

What is a one-way function?

Answer 1

Easy to compute f(x) given x, but computationally hard to compute f^-1(y) = x given y

Question 2

Name 2 one-way functions

Answer 2

Multiplication of large primes: inverse is integer factorisation

Exponentiation: Inverse if taking discrete logarithms

Question 3

What is a trap-door one-way function?

Answer 3

A one-way function, that given some additional information it is easy to compute f^-1

Question 4

Describe public key cryptography

Answer 4

Asymmetric

enc/dec uses different keys

Enc: public
Dec: Private

Question 5

What are some benefits of public key cryptography?

Answer 5

Simplified key management - don’t need key sharing

Digital signatures can be obtained

Question 6

How does public key work?

Answer 6

A stores public key PKa

Anyone can use this to encrypt a message:
Enc(M, PKa)

Only A can decrypt the message using the private key SKa:
Dec(C, SKa)

Question 7

What is a downside of public key encryption?

Answer 7

Computatinally much more expensive

Question 8

Describe hybrid encryption

Answer 8

Use public key cryptography to encrypt random key for a symmetric-key encryption algorithm

Encrypt the M using this symmetric key

1. B chooses random symmetric K, finds A’s public key PKa, computes C1 = E(K, PKa)
2. B computes C2 = E_symmetric(M, K)
3. B sends (C1, C2) to A
4. A recovers k=Dec(C1, SKa) and then M=Ds(C2, k)

Question 9

What is RSA?

Answer 9

Public-key cryptosystem and digital signature scheme

Based on integer factorisation

Question 10

How are keys generated in RSA?

Answer 10

1. Pick p, q randomly from a set of primes of a certain size
2. n=pq
3. Select e randomly with gcd(e, Ø(n)) = 1
   Ø(n) = (p-1)(q-1)
4. Compute d = e^-1 mod Ø(n)
5. Public: (n, e)
6. Private: (p, q, d)

Question 11

Describe RSA encryption

Answer 11

K_E = (n, e): public key

1. Input: M, 0 < M < n
   2 . C = E(M, K_E) = M^e mod n

Question 12

Describe RSA decryption

Answer 12

K_D = d: private key

1. D(C, K_D) = C^d mod n = M

Question 13

What are some applications of RSA?

Answer 13

Digital signatures

Key distribution for symmetric-key encryption (hybrid encryption)

Authentication

Question 14

What are some issues RSA need to handle?

Answer 14

1. Key generation (choice of e, generating large primes)
2. enc- and dec-algorithms (fast exponentiation, CRT for decryption)
3. formatting data (padding)

Question 15

How are primes generated for RSA?

Answer 15

p and q should be random and of a chosen length (recommended to at least 1024 bits)

Simple method of selecting a random prime:
1. Select random odd number of required length
2. Check if prime (i.e. Miller-Rabin)
2.1: yes - output this number
2.2: no - increment r by 2 and go to previous step

Question 16

What does the prime number theorem say?

Answer 16

The primes thin out as the numbers get larger

p(x) is all prime numbers less than.
The theorem says that the ratio of p(x) and x/ln(x) tends to 1 as x gets large.

This can be used to have a rule of thumb saying that the proportion of prime numbers up to size x is ln(x)

Question 17

How should e be selected in RSA?

Answer 17

Chosen at random

A smaller value of e can have a large effect on efficiency, though have possible security problems

Question 18

How is d selected in RSA?

Answer 18

To avoid known attacks, d should be at least square(n)

Question 19

What is fast exponentiation?

Answer 19

Basic idea behind it is square and multiply algorithm

Question 20

What is the square and multiply algorithm?

Answer 20

e in binary representation (ei are bits):
e = e02^0 + e12^1 + … + ek*2^k

Use the bits of e (ei)

M^e = m^e0 * (m^2)^e1 * (m^4)^e2…(m^2^k)^ek

Question 21

Why is padding used in RSA?

Answer 21

RSA with messages encoded as numbers without padding is weak.

Possible attacks:
- dictionary of known plaintext
- Guess plain, check if it encrypts to cipher
- Håstads attack

Padding is used to prepare for encryption. Padding includes redundancy and randomness

Question 22

What is Håstad’s attack?

Answer 22

Same message is encrypted without padding to multiple (3) recipients

Suppose the public exponent e=3 is used by all recipients

The cryptanalysis has 3 ciphertexts:
c1 = m^3 mod n1
c2 = m^3 mod n2
c3 = m^3 mod n3

These can be solved using CRT to obtain m^3

Question 23

Name 2 types of padding

Answer 23

PKCS #1

OAEP: Optimal Asymmetric Encryption Padding

Question 24

What is the PKCS #1 block format?

Answer 24

00 02 PS 00 D

00 and 02: bytes
PS: Pseudo random string of non-zero bytes (min 8 bytes)
D: Data to be encrypted

blocklength: Same as modulus

Question 25

What is the OAEP format?

Answer 25

OAEP is an encoding algorithm

The scheme includes k0 bits of randomness and k1 bits of redundancy into the message before encryption

2 hash functions G and H are used

Question 26

What is Miller theorem?

Answer 26

Determining d from e and n is as hard as factorising n

Question 27

What is Miller’s algorithm?

Answer 27

Define u,v such that ed-1 = 2^v * u, u is odd

consider the sequence a^u, a^2u,…,a^(2^vu), a^((2^v)u) mod n, a is random and 0 < a < n

there exist a square root of 1 somewhere in this sequence

With probability at least 0.5 the sequence contains a non-trivial square root of 1 mod n, thereby revealing the factors of n

if not, choose a new a and repeat

Question 28

What are 3 types of side channel attacks?

Answer 28

Timing attacks, power analysis, fault analysis

Question 29

What are timing attacks?

Answer 29

Use timing of private key operations to obtain info about the key.

For square-and-multiply:
Performs either a squaring or a square+multiplication in each step

Multiplication included when exponent bit is 1

These steps takes around twice as long

Question 30

What are power analysis?

Answer 30

Uses power usage profile of the private key operations to obtain info about the private key

Question 31

What are fault analysis?

Answer 31

Measure the effect of interfering with the private key operations to obtain information about the private key

Question 32

What are some countermeasures to side channel attacks?

Answer 32

Compute in constant time: when ei=0, run dummy multiplication

Montgomery ladder: Makes every operation depend on the key to avoid som fault attacks

Randomising the RSA message - mitigates “differential” attacks by preventing multiple timings on the same operation

Question 33

Summarize RSA

Answer 33

Should always use standardised padding

Factorisation of the modulus is the best known attack, in case where standardised padding is used

Finding private key from public is as hard as factorising the modulus

It is an open problem wether there is another way of breaking, besides factorising

Question 34

How secure is RSA?

Answer 34

An adversary would need to find the prime factors p and q of n.

From these, the attacker would be able to recover the private key d.

RSA is as hard to break as the RSA-problem.

It is as hard to find the private key from the public key, as it is factorising the modulus.