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.

Discovery

• Whitfield Diffie worked in a “reportorial style”, combining interviews with others and his own thinking about the problem.
• He developed the concept of digital signatures first, which led him to the broader concept of public key cryptography.
• He considered the public key property, that the encryption key can be made public, the most remarkable aspect of the discovery.

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

The number of positive integers less than $n$ relatively prime to $n$. Denoted by $\phi(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 positive 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$:

The coprime condition $\gcd(a, n) = 1$ is mandatory. When it fails the theorem gives nothing. For $3^{40} \bmod 15$, $\gcd(3, 15) = 3 \neq 1$, so $3^{\phi(15)} \equiv 1 \pmod{15}$ cannot be assumed and the reduction must be done another way.