Digital Signatures

— Masud Rahman (github)

What are they for?

  1. Authentication
  2. Integrity
  3. Non-repudiation

How do you use it?

Some Abstract Algebra

Groups

  • Set $G$ with one binary operation
  • $x \cdot y \in G$
    Closed operation:
  • $x \cdot (y \cdot z) = (x \cdot y) \cdot z$
    Associative operation:
  • $1 \cdot x = x$
    Operation has an identity:
  • $x^{-1} \cdot x = 1$
    Operation has an inverse:
  • $x \cdot y = y \cdot x$
    If commutative, group is Abelian:

Generators

  • $x^3 = x \cdot x \cdot x$
    Powers indicate repeated operation:
  • Subgroup generated by subset $S$ of $G$:
    • Combinations of elements in $S$
    • Includes inverses
    • $s_1^{n_1} \cdot s_2^{n_2} \cdot s_3^{n_3} \cdot ..., s_1, s_2, s_3 \in S$
  • Generating subset generates the entire group
  • Generating subset of size one implies cyclic group

Symmetry group of a triangle

  • $G$ contains 3 elements: rotate by $0^\circ, 120^\circ, 240^\circ$
  • Closed
  • Associative
  • Identity
  • Inverse

Cyclic groups, $C_n$

  • Generated by a single element
  • e.g. symmetry groups are cyclic groups

Rings

  • Set with two binary operations
  • Distributes one operation over the other: $x \times (y + z) = (x \times y) + (x \times z)$
  • Closed, associative, has identity for both operations
  • Commutativity and inverse for one operation (addition), not necessarily for the other (multiplication)
  • If commutative for other operation (multiplication), ring is commutative

Modular Arithmetic, $\mathbb{Z}/n\mathbb{Z}$

  • $ 6 + 3 = 9 = 2\text{ (mod 7)} $
  • $ 6 \times 3 = 18 = 5\text{ (mod 7)} $
  • $ 6 \times 6 = 36 = 1\text{ (mod 7)} $
  • $ 6 ^ 3 = 6 \times 6 \times 6 = 216 = 6\text{ (mod 7)} $
  • $ 6 ^ {-1} = 6\text{ (mod 7)}$ (possible because $\text{gcd}(6,\ 7) = 1$)

Mult. group of integers mod n, $(\mathbb{Z}/n\mathbb{Z})^\times$

  • The elements of $\mathbb{Z}/n\mathbb{Z}$ coprime with $n$
  • Binary operation is multiplication
  • Cyclic if $n = 1, 2, 4, p^k, 2p^k$, where $p$ is prime
  • e.g. $(\mathbb{Z}/5\mathbb{Z})^\times \cong C_4$ (generator is $2$)

Fermat's Little Theorem

  • Separate from his famous Last theorem
  • Stated in 1640 without proof by Fermat
  • Proved by Euler in 1736
  • If:
    • $p$ is prime
    • $\text{gcd}(a, p) = 1$
    • $m \equiv n\text{ (mod $p - 1$)}$
  • Then:
    • $a^m \equiv a^n \text{ (mod $p$)}$

ElGamal Signature Scheme

  • Invented by Tahir ElGamal in 1984
  • Agree on:
    1. hashing algorithm $H(m)$
    2. prime $p$
    3. generator $g$ of $(\mathbb{Z}/p\mathbb{Z})^\times$

Key generation

  • Choose secret $x$ where $1 < x < p - 1$
  • Calculate public key $y = g^x \text{ (mod $p$)}$

Signing

  • Choose random $k$ where:
    1. $1 < k < p - 1$
    2. $\text{gcd}(k,\ p - 1) = 1$
  • Calculate:
    1. $r = g^k \text{ (mod $p$)}$
    2. Solve for $s$ in $H(m) = xr + ks \text{ (mod $p - 1$)}$:
      • $s = (H(m) - xr)k^{-1} \text{ (mod $p$)}$
      • possible because $\text{gcd}(k,\ p - 1) = 1$
  • If $s = 0$, start again

Verifying

  • $H(m) = xr + ks\text{ (mod $p - 1$)}$
  • $g^{H(m)} = g^{xr} g^{ks}\text{ (mod $p$)}$
  • $g^{H(m)} = (g^x)^ r(g^k)^s\text{ (mod $p$)}$
  • $g^{H(m)} = y^r r^s\text{ (mod $p$)}$

Thanks!

Questions?