Public Key Encryption

Define the (G, E, D):

  • G: randomize algorithm to generate key pairs (pk, sk).
  • E(pk, m) takes mMm\in M and output cCc\in C.
  • D(sk, c) takes cCc \in C and outputs mMm \in M or \perp.

Define Trapdoor function(TDF)

  • G: randomize algorithm to generate key pairs (pk, sk).
  • F(pk,)F(pk, \cdot) maps XYX \to Y.
  • F1(pk,)F^{-1}(pk, \cdot) maps YXY \to X, that inverts F(pk,)F(pk, \cdot).

TDF is secure if F(pk,)F(pk, \cdot) can be evaluated, but cannot be inverted without sk.


Use secure TDF, symmetric auth encryption defined over (K, M, C) and hash function HKH \to K(also called random oracle):

E(pk, m):

  • xXx \leftarrow X, yF(pk,x)y \leftarrow F(pk, x)
  • kH(x)k \leftarrow H(x), cE(k,m)c \leftarrow E(k, m)
  • output (y, c)

D(sk, (y, c))

  • xF1(sk,y)x \leftarrow F^{-1}(sk, y)
  • kH(x)k \leftarrow H(x), mD(k,c)m \leftarrow D(k, c)
  • output m

Never use TDF to encrypt the message directly!

RSA Trapdoor permutation

GG: choose random p,q1024bitsp, q \approx 1024 bits, set N=pqN = p \cdot q. choose integers e,de, d, such that ed=1(mod ϕ(N))e \cdot d = 1 (mod \ \phi(N)). output pk=(N,e)pk = (N, e), sk=(N,d)sk = (N, d).

F(pk,x):RSA(x)=xeZnF(pk, x): RSA(x) = x^e \in Z_n F1(sk,y)=yd=RSA(x)d=xed=xkϕ(N)+1=(xϕ(N))kx=xF^{-1}(sk, y) = y^d = RSA(x)^d = x^{ed} = x^{k\phi(N) + 1} = (x^{\phi(N)})^k \cdot x = x

E, D: symmetric encryption. H: ZNKZ_N \to K

E(pk,m)E(pk, m):

  1. choose random x in ZNZ_N.
  2. yRSA(x)=xe,kH(x)y \leftarrow RSA(x) = x^e, k \leftarrow H(x)
  3. output (y, E(k, m))

D(sk,(y,c))D(sk, (y, c)): output D(H(RSA1(y)),c)mD(H(RSA^{-1}(y)), c) \to m.

If we use RSA directly to exchange the session key, kk, the server send the public key, (e, N), and the client returns c=RSA(k)c = RSA(k).

Assume k=k1,k2k = k_1, \cdot k_2, thus c=k1ek2ec/k1e=k2ec = k_1^e \cdot k_2^e \to c/k_1^e = k_2^e, if k is 64 bit, the chance for k1,k2<234k_1, k_2 < 2^34 is roughly 20%. The attacker can build a lookup table to enumerate k1,k2k_1, k_2 from 1 to 2342^{34} for a mid-way attack!


The PKCS1 v1.5 mode 2, used in HTTPS:


The random pad does not contain FF.

Bleichenbacher 1998 attack:

  • choose rZNr \in Z_N, computer crec=(rPKCS1(m))ec\prime \leftarrow r^e \cdot c = (r \cdot PKCS1(m))^e
  • send c’ to web server.l

The attacker can recover m with many trials. / HTTPS Defence(RFC 5246) treats the incorrect formated messages indistinguishable from correctly formatted RSA blocks.

PKCS1 v2.0: OAEP


Assume H, and G are random oracles, typically use SHA-256

RSA security analysis

Use d2128d \approx 2^{128}:

  • Weiner ‘87: if d<N0.25d < N^{0.25}, RSA is insecure.
  • BD’98: if d<N0.292d < N^{0.292}, RSA is insecure. 0.292=1120.292 = 1 - \frac{1}{\sqrt{2}}

Wiener’s attack

ed=1( mod ϕ(N))ed=kϕ(N)+1e \cdot d = 1 (\ mod\ \phi(N)) \to e \cdot d = k \cdot \phi(N) + 1. thus : eϕ(N)kd=1dϕ(N)<1N|\frac{e}{\phi(N)} - \frac{k}{d}| = \frac{1}{d\cdot \phi(N)} < \frac{1}{\sqrt{N}}. Nϕ(N)p+q3N|N -\phi(N)| \le p + q \le 3 \sqrt{N}.


eNkdeNeϕ(N)+eϕ(N)kde3NNϕ(N)+1N3N+1N12d21N+1N=12d2\begin{align*} | \frac{e}{N} - \frac{k}{d} | & \le |\frac{e}{N} - \frac{e}{\phi(N)}| + |\frac{e}{\phi(N)} - \frac{k}{d}| \\ & \le |\frac{e \cdot 3 \sqrt{N}}{N \phi(N)}| + \frac{1}{\sqrt{N}} \\ & \le \frac{3}{\sqrt{N}} + \frac{1}{\sqrt{N}} \\ & \le \frac{1}{2d^2} - \frac{1}{\sqrt{N}} + \frac{1}{\sqrt{N}} \\ & = \frac{1}{2d^2} \end{align*}

Fault Attack

When decrypting RSA, we can gain 4x speedup with:

  • Decrypt mod p xp=cdZpx_p = c^d \in Zp
  • Decrypt mod q xq=cdZpx_q = c^d \in Z_p

then combine them to get x=cdZNx = c^d \in Z_N.

Suppose error occurs when computing xqx_q, but not in xpx_p, the output is xx\prime, and gcd((x)ec,N)=pgcd((x\prime)^e -c, N) = p, thus we can recover p.

Bad random generate may get the same p, different q, then gcd(N1,N2)=pgcd(N_1, N_2) = p to recover the p.

ElGamal Public-key System

We can use Diffie-Hellman protocol to build public key. Intuitively: Use A as public key: A=gaA = g^a Bob sends B=gbg^b || message encrypted with k=gabk = g^{ab}.

Key generator:

  • choose random geneator g in G, and random a in ZnZ_n.
  • output sk = a, pk = (g, h=gah=g^a).

H: G2KG^2 \to K, a hash function.

Encryption: E(pk=(g,h),m)E(pk=(g, h), m):

  • bZN,ugb,vhbb \in Z_N, u \leftarrow g^b, v \leftarrow h^b
  • kH(u,v),cE(k,m)k \leftarrow H(u, v), c \leftarrow E(k, m)
  • output (u, c)


  • vuav \leftarrow u^a
  • kH(u,v),mD(k,c)k \leftarrow H(u, v), m \leftarrow D(k, c)
  • output m

Encryption is 3x expensive as decryption, while RSA decryption is more expensive.

Twin ElGamal, use (a1,a2)ZN(a_1, a_2) \in Z_N for the private keys.