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
What is the OAEP format?
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
What is Miller theorem?
Determining d from e and n is as hard as factorising n
What is Miller’s algorithm?
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
What are 3 types of side channel attacks?
Timing attacks, power analysis, fault analysis
What are timing attacks?
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
What are power analysis?
Uses power usage profile of the private key operations to obtain info about the private key
What are fault analysis?
Measure the effect of interfering with the private key operations to obtain information about the private key
What are some countermeasures to side channel attacks?
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
Summarize RSA
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
How secure is RSA?
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.
