Cryptography

Notes from MATH 470 — Communications and Cryptography at Texas A&M. Based off of lectures by Dr. Josiah Park, and An Introduction to Mathematical Cryptography by J. Hoffstein, J. Pipher, and J.H. Silverman.

Notation§

• $\mathbb{Z}_n$ and $\mathbb{Z}/n\mathbb{Z}$ are used interchangably; as are $\left(\mathbb{Z}_n\right)^\times$ and $\left(\mathbb{Z}/n\mathbb{Z}\right)^\times$.
• $\mathbb{N}$ is the set of natural numbers without 0.
• $\mathbb{P}$ is the set of all prime integers.
• $a \equiv_n b \iff a \equiv b \pmod{n}$.
• $[a\dots b], (a\dots b), (a\dots b], [a\dots b)$ uses the regular interval notation of (in|ex)clusivity, except over the integers rather than reals.
• DLP is the discrete logarithm problem, over any of $\left(\mathbb{Z}_n\right)^\times$, $\mathbb{F}_p$, or $E(\mathbb{F}_p)$.
• CRT is the Chinese Remainder Theorem.

Contents§

• 1
  Number Theory: Modular Arithmetic
• 2
  Intermezzo: Algebraic Structures
• 3
  Number Theory: GCD, Euclid, Diophantus, and Bézout
• 4
  Number Theory: Exponentiation with Fast Powering and Montgomery Ladder
• 5
  Number Theory: Euler's and Carmichael's Totient, Euler's Theorem
• 6
  Number Theory: Discrete Log Problem and Primitive Roots
• 7
  Diffie-Hellman Key Exchange
• 8
  Elgamal Cryptosystem
• 9
  Discrete Logarithm in $\mathbb{F}_p$: Pohlig-Hellman
• 10
  Discrete Logarithm in $\mathbb{F}_p$: $\text{ord}_p(g)$ is a Prime Power
• 11
  Discrete Logarithm in $\mathbb{F}_p$: Shank's Baby-Step Giant-Step
• 12
  Discrete Logarithm in $\mathbb{F}_p$: Index Calculus Method
• 13
  RSA Cryptosystem
• 14
  Primality Testing: Naïve Test
• 15
  Primality Testing: Fermat Primality Test and Carmichael Numbers
• 16
  Primality Testing: Miller-Rabin
• 17
  Primality Testing: Baillie-PSW ^[$\dag$]
• 18
  Factorization: Pollard's $\rho$ method
• 19
  Factorization: Pollard's $p-1$ method
• 20
  Factorization: Quadratic Sieve
• 21
  Factorization: General Number Field Sieve
• 22
  Elliptic Curves over $\mathbb{F}_p$
• 23
  Factorization: Lenstra Elliptic-Curve Factorization
• 24
  Elliptic Curves: ECDH, EC Elgamal, Curve25519
• 25
  Signature Algorithms: RSA and DSA
• 26
  Signature Algorithms: ECDSA
• 27
  Discrete Logarithm in $E\left(\mathbb{F}_p\right)$
• 28
  Subliminal Channels ^{[$\text{\P}$][$\dag$]}