Cryptography course week 6

Public key encryption

Trapdoor function(TDF)

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

Encryption

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

Decryption

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

PKCS1

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

ElGamal

IDH - Interactive Diffie Hellman

Twin ElGamal