This is a note of week 6 of the Coursera course Cryptography I. The topic is public key encryption.
1 Definitions and Security
A public-key encryption (PKE) system is a triple of algorithms: (G, E, D)
:
G()
: randomized algorithm outputs a key pair(pk, sk)
E(pk, m)
: randomized algorithm that encryptsm
and outputsc
D(sk, c)
: deterministic algorithm that decryptc
and outputsm
orbottom
(invalid).
For PKE, one time security is the same as many-time security. This is not the case for symmetric ciphers.
In the Chosen Ciphertext Attack(CCA), the attacker can see plaintext for any ciphertext before and after (except the two challenge messages) the challenge.
A Trapdoor Function(TDF) uses G
and a inversable functions F
for encryption and its inverse F'
for decryption. It is secure if F(pk, _)
is a one-way funciton: the attack cannot find the input from output without sk
.
With a TDF, we can construct a CCA-secure PKE using the ISO standard.
(G, F, F')
: secure TDF defined overX -> Y
(Es, Ds)
: symmetric authenticated cipher defined over(K, M, C)
H: X -> K
: a hash funciton
Use the TDF G
for PKE, the E(pk, m)
is constructed as follows:
- select a uniform random value
x
y = F(pk, x)
,k=H(x)
,c=Es(k, m)
- output
(y, c)
The D(sk, (y,c))
is:
x = F'(sk, y)
k = H(x)
,m = Ds(k, c)
- output
m
It is important to introduce random value of x
so the encryption is not deterministic. Never apply the trapdoor function directly to the message.
2 The RSA Trapdoor Permutation
RSA trapdoor perputation was published in 1977 and was widely used in SSL, TLS, secure email and file systems. It is defined as follows:
- choose random primes
p, q
about1024
bits - set
N = pq
- choose intergers
e, d
such thated = 1 mod phi(N)
. G()
producespk = (N, e)
,sk = (N, d)
F(pk, x) = x ^ e
,F'(sk, y) = y^d
.
RSA is one-way permutation because the probability of computing the result of y^(1/e)
is negligible.
Since ISO standard is not often used, RSA in practice like PKCS1 developed in 1980s uses an expanded key generated from a given symmetric key. It was used in HTTPS but is insecure. New verisons such as RSA-OAEP fixed the bug but there are many details.
3 PKE from DH
It is easy to convert DH to PKC by treating A
of A=g^a
as a public key and a
as a private key. The ElGamal system by letting
G
: finite cyclic group of ordern
(Es, Ds)
: symmetric authenticated encryptioin defined over(K, M, C)
H: G^2 -> K
: a has function
To construct a PKE system (Gen, E, D)
:
- Key generation
Gen
: choose ramdom generatorg
inGen
and randoma
inZn
, computeh=g^a
and outputsk = a
,pk = (g, h)
E(pk, m)
- select random
b
fromZn
,u = g^b
,v = h^b
,k = H(u, v)
- create ciphertext
c = Es(k, m)
, output(u, c)
- select random
D(sk, (u, c))
- get
v = u^a
,k = H(u, v)
- then output
m = Ds(k, c)
- get