Public key encryption

Broadly how does public key encryption work?

The public key is used by the sender to encrypt a message
The private key is used by the recipient to decrypt the message.

(Also called asymmetric key encryption)

What does public key encryption guarantee?

Confidentiality
Integrity

(both because only the recipient can decrypt)

What is a one-way function?

A function whose outputs can be quickly calculated and verified given the inputs
But whose inputs cannot be quickly verified given the outputs.

Under what conditions is f(x) = y^x \text{ mod } p a one-way function?

y is the primitive root mod p
p is a very large number (e.g. 512-bit)

Why is f(x) = y^x \text{ mod } p a one-way function?

• Each successive power of y is a value in the range [1, p - 1]

• The values of y are uniformly distributed across the range [1, p - 1]

• So if one were to guess the value of x, the probability of correctly guessing would be \frac{1}{p - 1}

• When p is large the probability of a correct guess would be very small, making it computationally infeasible to guess using brute force

What values are publicly known in an RSA encryption scheme?

n = p * q

e = A prime number in the range [1, (p - 1) * (q - 1)] that is coprime to (p - 1) * (q - 1)

What are the hidden values in an RSA encryption scheme?

p, q = Two very large, prime numbers
d = The private key, the modular inverse of e under mod (p - 1)*(q - 1)

e*d \equiv 1 \quad(\text{mod } (p - 1) * (q - 1))

Give a public key encryption scheme

RSA

What are the formulae for encryption and decryption in the RSA encryption scheme?

C = M^e\quad (\text{mod } n)

M = C^d\quad (\text{mod } n)