Public key cryptography and RSA Flashcards
What is a one-way function?
Easy to compute f(x) given x, but computationally hard to compute f^-1(y) = x given y
Name 2 one-way functions
Multiplication of large primes: inverse is integer factorisation
Exponentiation: Inverse if taking discrete logarithms
What is a trap-door one-way function?
A one-way function, that given some additional information it is easy to compute f^-1
Describe public key cryptography
Asymmetric
enc/dec uses different keys
Enc: public
Dec: Private
What are some benefits of public key cryptography?
Simplified key management - don’t need key sharing
Digital signatures can be obtained
How does public key work?
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)
What is a downside of public key encryption?
Computatinally much more expensive
Describe hybrid encryption
Use public key cryptography to encrypt random key for a symmetric-key encryption algorithm
Encrypt the M using this symmetric key
- B chooses random symmetric K, finds A’s public key PKa, computes C1 = E(K, PKa)
- B computes C2 = E_symmetric(M, K)
- B sends (C1, C2) to A
- A recovers k=Dec(C1, SKa) and then M=Ds(C2, k)
What is RSA?
Public-key cryptosystem and digital signature scheme
Based on integer factorisation
How are keys generated in RSA?
- Pick p, q randomly from a set of primes of a certain size
- n=pq
- Select e randomly with gcd(e, Ø(n)) = 1
Ø(n) = (p-1)(q-1) - Compute d = e^-1 mod Ø(n)
- Public: (n, e)
- Private: (p, q, d)
Describe RSA encryption
K_E = (n, e): public key
- Input: M, 0 < M < n
2 . C = E(M, K_E) = M^e mod n
Describe RSA decryption
K_D = d: private key
- D(C, K_D) = C^d mod n = M
What are some applications of RSA?
Digital signatures
Key distribution for symmetric-key encryption (hybrid encryption)
Authentication
What are some issues RSA need to handle?
- Key generation (choice of e, generating large primes)
- enc- and dec-algorithms (fast exponentiation, CRT for decryption)
- formatting data (padding)
How are primes generated for RSA?
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
What does the prime number theorem say?
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)
How should e be selected in RSA?
Chosen at random
A smaller value of e can have a large effect on efficiency, though have possible security problems
How is d selected in RSA?
To avoid known attacks, d should be at least square(n)
What is fast exponentiation?
Basic idea behind it is square and multiply algorithm
What is the square and multiply algorithm?
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
Why is padding used in RSA?
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
What is Håstad’s attack?
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
Name 2 types of padding
PKCS #1
OAEP: Optimal Asymmetric Encryption Padding
What is the PKCS #1 block format?
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
