Public key encryption
Secure TDF - G,F,F-1 is secure if F(pk, .) is a "one-way" function: can be evaluated but can't be inverted without sk(secret key). pk is public key.
Secret key is the trapdoor.
Public key encryption from TDFs
1. Choose a random x
2. k <= H(x) where H is a hasher
3. y = F(pk, x) where G,F,F-1 is a secure TDF and pk,sk are generated from G
4. c <= E(k,m) where E,D is symmetric auth. encryption defined over (K,M,C)
5. Output is y,c
1. x <= F-1(sk,y)
2. k = H(x)
3. m = D(k,c)
If we apply F directly to m, it becomes deterministic. There is no randomness (which was provided by X).
The RSA Trapdoor permutation
Review: arithmetic mod composites
Let N = p.q where p,q are primes and roughly same size => p,q are almost equal to sqrt(N)
Z_N = (0,1,2...N-1) and Z_N* = set of invertible elements in Z_N
x E Z_N is invertible if gcd(x,N) = 1
number of invertible elements = phi(N) = (p-1)(q-1) = N -p -q +1 ~= N - 2.sqrt(N) ~= N since N is very large(for e.g. 600 digits, so sqrt will be like 300 digits)
So Z_N* ~= Z_N => almost every element in Z_N will be invertible.
Euler's thm For all x E Z_N * => x ^ phi(N) = 1
How RSA works
0. choose random primes p,q roughly 1024 bits, set N = p*q
1. choose e,d s.t. e*d = 1 mod phi(N)
2. pk = (N,e), sk = (N,d) where e is encryption exponent and d is decryption exponent
3. for x E Z_N*, F(pk,x) is RSA(x), RSA(x) = x^e in Z_N
4. to decrypt
5. RSA_1(y) = y^d = (RSA(x))^d = (x^e)^d = x^(e*d), now e*d = 1 mod phi(N) means e*d = k*phi(N) + 1 where k is some integer
6. RSA_1(y) = x^(k*phi(N) + 1) = x^(k*phi(N))*x, from Euler's thm. x^(phi(N)) = 1 since x E Z_N* => RSA_1(y) = x
Textbook RSA is insecure
Encrypt C = m^e
Decrypt C^d = m
Uses RSA. Insecure since attacker could check if MSB of a cipher text's original message == 2. And could decode the entire message in this way. It's used in HTTPS so they fixed it by reverting to a random 46 byte string in case of erroneous message, so that attacker doesn't get any information about the message.
PKCS2 - OAEP (Optimal Asymmetric Encryption Padding)
Improvement over PKCS1
Public key encryption built from Diffie Hellman Protocol
IDH - Interactive Diffie Hellman