Number theory
=============

Outline:
    - Divisors and GCD
    - Inverses using GCD
    - Element order and Euler's function
    - Generators and discrete logs (DLP)
    - Finding generators
    - Typical public key crypto setup and groups

Why number theory?
    Crypto with modular arithmetic
    E.g. one-time MAC from last lecture
    Want to know
	(a) properties of modular arithmetic that we can rely on
	(b) what's easy vs. hard to compute (and how to compute),
	    so that our cryptosystem is hard to break
    We are going to talk about integers only (no reals, etc)
    Last lecture was about fields (i.e. two operators), today we will largely
	focus on groups (i.e. just one operator, which is usually "multiply")

Divisors
========

d|a: "d divides a", or equivalently, "a is a multiple of d"
    there exists some (integer) k, such that a=d*k
    corner cases:
	for all (integer) d, d|0: k=0
	for all (integer) a, 1|a: k=a
d is a divisor of a, if d|a, and d>=0
d is a common divisor of a and b, if d is a divisor of a, and of b

greatest common divisor of two integers -- gcd(a,b) -- is largest common divisor
    e.g. gcd(10,4)=2; gcd(7,5)=1; gcd(9,0)=9
    define gcd(0,0)=0, otherwise it could be anything since everything divides 0

if gcd(a,b)=1, we say a and b are relatively prime
Euclid's algorithm for finding gcd(a,b):

                / a,                   if b = 0
    gcd(a,b) = {
                \ gcd(b, a mod b),     otherwise

gcd(7,5) = gcd(5,2) = gcd(2,1) = gcd(1,0) = 1
    polynomial running time: k^2 bit operations, if a and b have <= k bits

intesting observation / theorem (Bezout's lemma, or Euclid's extended alg):
    gcd(a,b) can always be represented as ax+by, for some integer x and y

    proof sketch: in Euclid's alg, arguments to gcd(*,*) are of the form ax+by
	induction, base case: gcd(a,b):  a=a*1+b*0,  b=a*0+b*1
	inductive step: gcd(a,b)=gcd(b,a mod b)
	    a mod b = a-z*b
	    if a and b were of the right form, so is b and (a mod b)
	final step: gcd(a,0)=a, must be of the right form too

    e.g. for gcd(7,5):
	7 = 7*1    + 5*0
	5 = 7*0    + 5*1
	2 = 7*1    + 5*(-1)
	1 = 7*(-2) + 5*3

Inverses using GCD
==================

Z_n^*: multiplicative subgroup of Z_n
    consists of all elements from Z_n that are relatively prime to n
	Z_n^* = {a in Z_n: gcd(a,n)=1}
    e.g. recall Z_p^* = Z_p except for the "0" element
    in Z_n, mult. of two elements not relatively prime to n can result 0
    in Z_n^* it's possible to compute inverses because you never get 0

how to compute a^-1, if a is in Z_n^*?  assume gcd(a,n)=1
    if n is prime, then a^-1 = a^{n-2}, mod n  (from last lecture)
    if n is not prime (or even if it is), can find x,y such that ax+ny=1
	=> ax=1 (mod n) => x=a^{-1} (mod n)
	can find such decomposition by applying Euclid's alg -- i.e. gcd(a,n)
	e.g. want to find 5^{-1} (mod 7)
	    gcd(5,7) = ... = 7*(-2) + 5*3
	    thus, 5^{-1} = 3 (mod 7)
	can efficiently find inverses modulo non-primes!

Element order
=============

Euler's function phi(n): the number of elements of Z_n^*
			 that are relatively prime to n
    if p is prime, then phi(p)=p-1
    as a corner case, phi(1)=1
    observation: phi(n) = |Z_n^*|, pretty much by definition

    e.g. Z_{10}^* = {1, 3, 7, 9}
	 phi(10) = 4

theorem [Euler]: a^{phi(n)} = 1 (mod n)
    holds for all n, prime and composite

order of an element, denoted order_n(a): least positive t, s.t. a^t = 1 (mod n)
    let's look at powers of all elements of Z_7^*:

    x^1	x^2 x^3	x^4 x^5	x^6 x^7
    1	1   1	1   1	1   1		order(1) = 1
    2	4   1	2   4	1   2		order(2) = 3
    3	2   6	4   5	1   3		order(3) = 6
    4	2   1	4   2	1   4		order(4) = 3
    5	4   6	2   3	1   5		order(5) = 6
    6	1   6	1   6	1   6		order(6) = 2

			^
			|
			\--- x^{phi(7)} = x^6 = 1 (mod 7)
			     generalization of Fermat's Little Thm

consider the elements generated as powers of some initial element a
    define <a> = { a^i: i>=0 }, subgroup generated by a in Z_n^* (n implicit)
    e.g. <2> = {2, 4, 1}; <1> = {1}

theorem: order_n(a) = |<a>|
theorem: order_p(a) | p-1, if p is prime (e.g. see example table above)
theorem: order_n(a) | phi(n), in general
    or, |<a>| divides |Z_n^*|

Generators and Discrete Log Problem
===================================

definition: element g is a generator of Z_n^* if order_n(g) = phi(n)
    in other words, <g> = Z_n^* -- powers of g generate all of Z_n^*

theorem: if g is a generator mod n, then there's a unique solution to
	g^x=y mod n
    for each y in Z_n^*, and 0<=x<phi(n)
    x is called the "discrete log" of y, base g, mod n

when do these generators exist, and how many are there?

theorem: Z_n^* has a generator (Z_n^* is said to be cyclic),
    if and only if n is 2, 4, p^e, or 2*p^e, for prime p and integer e>=1

theorem: if p is prime, then Z_p^* has phi(p-1) generators
    e.g. p=11 -> Z_p^* has 10 elements -> phi(11-1)=phi(10)=4 generators
    generators are 2, 6, 7, 8

Finding generators
==================

assume we're interested in generators mod prime p
general plan: pick an element, check if it's a generator

1. how to check if an element x is a generator?
    need to ensure that (a) x^{phi(p)} = 1
			(b) x^y != 1, for any y<phi(p)
    (a) always holds, by Fermat's Little Theorem
    to check (b), recall that order_p(a) | phi(p) = p-1
    so, just need to check that x^y != 1 for all factors of p-1
    requires knowing factorization of p-1: hard if p is large (1024 bits)

    however, this would work well if we know p's factorization ahead of time
    "safe prime" p = 2q+1 (Sophie Germain prime)
    factors of p-1 are, thus, 2 and q
    can check (b) for y=2 and y=q only

2. how likely are we to find a generator?
    likely to work, at least for Z_p^*
    generators are dense: phi(p-1) >= (p-1) / (6 ln ln (p-1))
    for "safe" primes, phi(2q+1-1) = phi(2q) = q-1
	almost half the elements are generators

Typical public key crypto
=========================

to implement computationally-secure cryptosystems, must leverage a hard problem
    one example: DLP is (assumed to be) hard in Z_p^*, for large random p,
		 where p-1 is hard to factor (has a large prime factor),
		 e.g. "safe" primes: large prime factor q

Alice and Bob agree to prime p, generator g
Alice chooses x, 0<=x<p-1, as her secret key
Alice publishes y=g^x mod p as her public key
now, Bob can assume that only Alice knows x, but everyone knows g^x

groups typically relevant for crypto:
    modulo prime: Z_p^* (e.g. Diffie-Hellman, El-Gamal)
	Z_p^* = {a: 1<=a<p}
	|Z_p^*| = p-1
	often p=2q+1 ("safe" primes)
	always cyclic, many generators
	hard problem: computing the discrete log

    quadratic residues modulo prime: Q_p (e.g. Rabin)
	Q_p = {a^2: 1<=a<p}
	cyclic: can generate from any square
	    if <g>=Z_p^* then <g^2>=Q_p
	|Q_p| = |Z_p^*|/2 = (p-1)/2
	hard problem: computing the square root

    modulo composite: Z_n^* (e.g. RSA)
	{a: gcd(a,n)=1, 1<=a<n}
	|Z_n^*| = phi(n), by definition
	RSA: n=p*q, where p and q are distinct odd primes
	then Z_n^* is not cyclic (recall: Z_n^* cyclic only for 2, 4, p^k, 2p^k)
	hard problem: factoring n to compute phi(n)

	however, important optimization using CRT (chinese remainder theorem):
	    suppose we want to compute x^y mod n
	    x, y are large (about the size of n)
	    can compute mod p, mod q (each is 8 times faster)
	    then use CRT to combine results to obtain x^y mod n
	    net result: 4 times faster, minus conversion costs (cheap)
	    will talk more about this optimization later

    quadratic residues modulo composite: Q_n (e.g. oblivious transfer)
	{a^2: gcd(a,n)=1, 1<=a<n}
	if n=pq: |Q_n| = (p-1)/2 * (q-1)/2
		 Q_n is cyclic