Public Key Cryptography

Public key cryptography (PKC) uses a key pair, a public key and a private key, rather than a single shared secret key. It is based on Number Theory, not substitution-permutation networks, and is asymmetric.

Motivation

• Key distribution
  Symmetric cryptography requires either a pre-shared key or a trusted key distribution center (KDC), which must itself be trusted with confidentiality.
• Digital signatures
  Electronic documents need a signature scheme that is easy to sign and verify, but difficult to forge, with universal verifiability.

PKC Framework

A key pair’s public key is known to everyone. The private key is known only to its owner. Given the public key and the algorithm, it is computationally infeasible to derive the private key.

• Confidentiality
  Sender encrypts with the receiver’s public key. Only the receiver, holding the private key, can decrypt.
• Authentication
  Signer encrypts a fingerprint (authenticator) of the message with their private key. Anyone can verify it using the signer’s public key. The authenticator must be infeasible to forge without changing the message.

Groups Over Finite Sets

Number-theoretic PKC computes over finite groups, since infinite groups ($\mathbb{Q}, \mathbb{Z}, \mathbb{R}$) are unusable for computation.

• $\mathbb{Z}_n$
  The group of integers modulo $n$: $\{0, 1, \dots, n-1\}$.
• $\mathbb{Z}_n^*$
  The subgroup of $\mathbb{Z}_n$ relatively prime to $n$, excluding 0 by convention.

If $n$ is prime, every nonzero element of $\mathbb{Z}_n$ is coprime to $n$, so $\mathbb{Z}_n^* = \{1, \dots, n-1\}$.

The order of a group is its number of elements. $|\mathbb{Z}_n| = n$, and for prime $p$, $|\mathbb{Z}_p| = p$.

Example: $\mathbb{Z}_{10}^* = \{1, 3, 7, 9\}$, removing multiples of the prime factors 2 and 5 from $\mathbb{Z}_{10}$.

Euler’s Totient Function

$\phi(n)$: the number of positive integers less than $n$ relatively prime to $n$.

• $\phi(p) = p - 1$ for prime $p$.
• $\phi(pq) = \phi(p)\phi(q) = (p-1)(q-1)$ for distinct primes $p, q$.

Fermat’s Theorem

For prime $p$ and integer $a$ not divisible by $p$:

Euler’s Theorem

Generalizes Fermat’s theorem to any modulus. For $a, n$ relatively prime:

For $n = pq$ (distinct primes) and $0 < m < n$: