CSE4303 Introduction to Computer Security (Lecture 13)

Asymmetric Encryption

Public-key building block: Trapdoor function (TDF)

Definition of trapdoor function

A trapdoor function $X\to Y$ is a triple of efficient algorithms $(G,F,F^{-1})$ such that:

• $G(\circ)$ is randomized algorithm outputs a key pair $(pk,sk)$.
• $F(pk,\circ)$ is a deterministic algorithm that takes as input a public key $pk$ and a message $m$ and outputs a ciphertext $c$.
• $F^{-1}(sk,\circ)$ is a deterministic algorithm that takes as input a secret key $sk$ and a ciphertext $c$ and outputs a message $m$.

more precisely: $\forall(pk,sk)$ outputs by $G$, $\forall x\in X: F^{-1}(sk,F(pk,x))=x$.

RSA cryptosystem

RSA cryptosystem 

Setup

• $n = pq$, with $p$ and $q$ primes
• $e$ relatively prime to $\varphi(n) = (p-1)(q-1)$
• $d$ inverse of $e$ in $\mathbb{Z}_{\varphi(n)}$

Keys

• **Public key:*- $K_E = (n, e)$
• **Private key:*- $K_D = d$

Encryption

• Plaintext $M \in \mathbb{Z}_n$
• $C = M^e \bmod n$

Decryption

• $M = C^d \bmod n$

RSA cryptosystem: challenge

• The implementation of the RSA cryptosystem requires various algorithms.

• Overall

  • Representation of integers of arbitrarily large size and arithmetic operations on them

• Encryption

  • Modular power

• Decryption

  • Modular power

• Setup

  • Generation of random numbers with a given number of bits (to generate candidates $p$ and $q$)
  • Primality testing (to check that candidates $p$ and $q$ are prime)
  • Computation of the GCD (to verify that $e$ and $\varphi(n)$ are relatively prime)
  • Computation of the multiplicative inverse (to compute $d$ from $e$)

RSA: basis of security

For all efficient algorithms $A$:

where $p,q \leftarrow$ $n$-bit primes, $N \leftarrow pq$, and $y \leftarrow \mathbb{Z}_N$.

Diffie-Hellman key exchange

Based on hardness of “discrete log problem”:

Given $p$, $g$, $y=g^x \pmod p$, what is $x$?

• Eavesdropper sees: $p$, $g$, $A=g^a \pmod p$, and $B=g^b \pmod p$.
• How hard is it to compute $g^{ab} \pmod p$?
• More generally: define $DH_g(g^a, g^b) = g^{ab} \pmod p$.

Elliptic Curve Cryptography (ECC)

• Parameters: curve, modulus, initial point
  • Curve: $y^2 = x^3 + ax^2 + bx + c$
  • Modulus: large prime number
  • Initial point: large $(x, y)$
• Operations: addition, point doubling, dot (see tutorial)
  • Repeated addition $\sim$ multiplication
  • Point doubling $\sim$ multiplying by $2$
  • Repeated point doubling $\sim$ multiplying by powers of $2$

Hard problem: analogue of discrete-log problem using elliptic curves in particular geometric space

• See ArsTechnica tutorial, or many videos online
• Reversing the dot and point-doubling operators in the finite field defined by the curve and modulus
• Example: Let the finite field be defined by $y^2 = x^3 + 7 \pmod{31}$ with initial point $(x, y)$.
  • Question: Suppose we see a new point $(x_2, y_2)$ and we know $(x_2, y_2) = n \cdot (x, y)$. What is $n$?
  • I.e., how many times must we add $(x, y)$ to itself to get $(x_2, y_2)$?
  • Public key: $(x_2, y_2)$ and parameters of the ECC system
  • Private key: $n$
  • Encryption: embed message as points on the EC, run EC ops on them

Public-key encryption from TDFs

Security Theorem:

• If $(G, F, F^{-1})$ is a secure trapdoor function (TDF),
• $(E_s, D_s)$ provides authenticated encryption,
• and $H : X \to K$ is modeled as a random oracle (RO),

then $(G, E, D)$ is CCA$_{\text{RO}}$ secure.

• That is, it is CCA-secure in the random oracle model.
• An additional extension is required to obtain full CCA security in the standard model, and such constructions are known.

Summary

Wrapup: symmetric vs. asymmetric systems

1. Symmetric: faster, but key distribution hard
2. Asymmetric: slower, but key distribution/management easier
3. Application: secure web sessions (e.g. online shopping visit)
   1. Use symmetric-key-encrypted sessions
   2. Exchange symmetric keys with asymmetric scheme
   3. Authenticate public keys (using PKI or web of trust)