Today: Crypto math, Monday, March 3rd

Finding primes

Generate & test method

do 
    p <- k-bit integer
until p is prime

What we need:

Prime number theorem: about 2^k/log(2^k) k-bit primes. One out of 0.69k k-bit integers is a prime.

Primality test: if p is a prime, then 2^(p-1) = 1 (mod p). The other way is not necessarily true, but we can be fairly confident that if 2^(p-1) = 1 (mod p) and p was chosen randomly then p is prime. (Why? How confident?)

Other primality testing algorithms:

One-time MAC

    A           m, t=MAC(t)            B
        ---------------------------->

            T
                    key = (slope,y-intercept) coordinates of the line?
            |     / 
        tag |----*
            |   /|
            |  / |
            | /  |
            |/   |
            ------------------ M
                msg

Security: If Eve learns (M,T) on the line and replaces with (M', T') then Pr[ Bob accepts M', T' ] = 1/p

Proof:

For fixed m, m', t s.t. t = am + b (mod p) (Equation 1)

For each T', \exists exactly one key (a,b) that satisfies Eq. 1 and T' = aM' + b (mod p)

Note: If you MAC two messages with the same a,b,p then you break the security

Divisors

Notation: d divides a or d is a divisor of a -> d | a <=> \exists k, s.t. a = dk

How can we find the gcd of two numbers?

Euclid's algorithm

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

Example:

gcd(7,5) = gcd(5, 2) = gcd(2,1) = gcd(1,0) = 1

Running time:

lg(b)lg(a) bit operations

Extended Euclidian algorithm

\forall (a,b), \exists (x,y) s.t. ax + by = gcd(a,b)

When a=7, b=5, what is x,y?

7 = 7*1 + 5*0
5 = 7*0 + 5*1

2 = 7*1 + 5*-1 
1 = 7*-2 + 5*3

=> (x,y)=(-2,3)

In previous lecture we said, that if a \in Z*_p, then a^-1 = a^(p-2) mod p

What if a \in Z*_n = {x | 1 <= x <= n-1, gcd(x,n) = 1}, where n is not prime?

How to find a^-1:

a^-1 = ?
\exists x,y s.t ax + ny = 1 ax = 1 (mod n) => a^-1 = x (mod n)

Order of elements

Let Z*_n denote the group of elements that are coprime with n. Sometimes this is denoted as Z/nZ when n is not prime and Z_p or Z*_p when p is prime.

Notion: The order of an element in a group like Z*_p or Z*_n

Definition: order_n(a) = smallest t such that a^t = 1 (mod n), if a \in Z*_n

If n=p prime, then t=p-1

In general, Euler's theorem: \forall n, \forall a \in Z*_n, a^\phi(n) = 1 (mod n), where \phi(n) is the totient function, \phi(n) = # of elements relatively prime to n = | Z*_n |

Example:

Z*_10 = {1, 3, 7, 9}

\phi(10) = 4

3^4 = 7^4 = 9^4 = 1 (mod n)

Order:

a, t, and a^t, n = 7

a\t    1   2   3   4   5   6
1      1   1   1   1   1   1    order_7(1) = 1
2      2   4   1   2   4   1    order_7(2) = 3
3      3   2   6   4   5   1    order_7(3) = 6
4      4   2   1   4   2   1    order_7(4) = 3
5      5   4   6   2   3   1    order_7(5) = 6
6      6   1   6   1   6   1    order_7(6) = 2

Generators, definition of group generated by a: <a> = { a^t : t >= 0 }

<a> is a subgroup of Z*_n (<a> \includedin Z*_n)

Example:

<2> = {2, 4, 1}

Theorem: The cardinatlity |<a>| of <a> is the order of a (i.e order_n(a))

Theorem: |<a>| divides |Z*_n| <=> order_n(a) | \phi(n)

Theorem: If p prime, then |<a>| divides p-1 because \phi(p) = p-1

Generators

Def: If p prime and order_p(g) = p-1, then g is a generator of Z*_p

Notation: <g> = Z*_p

Theorem: If p is prime, g is generator mod p, then g^x = y (mod p) \forall y has unique solution x

Theorem: Z*_n has generator iff n is 2, 4, p^m, 2*p^m, where p is an odd prime & m >= 1

Theorem: If p prime, then # of generators in Z*_p is \phi(p-1)

How to find generators

Idea: Need to factor the size of our group \phi(p) = p-1 so that we'll know what are all the possible subgroup sizes we can get from a generator. Then, we make sure our randomly-picked generator does not generate the other smaller-sized subgroups.

Definition: If p,q primes, p=2q+1 then p is a safe prime and q is a Sophie Germain prime

Emipirically, prime p is safe with probability ~= 1/ln(p)

Examples:

p = 23, q = 11
p = 11, q = 5
p = 59, q = 29
...

Lagrange's theorem: The order of any subgroup divides the order of its parent group. (See more here)

Theorem: If p is a safe prime (then p-1 = 2q), then the size of Z_p's sub groups can be either 1, 2, q, 2q (because they have to divide the size of Z_p which is p-1 = 2q)

\forall a \in Z*p, order_p(a) \in {1, 2, q, 2q}

To generate Z*_p we need a generator a s.t. order_p(a) = p-1 = 2q

Fermat's little theorem (generalization of Euler's theorem): a^(p-1) = 1 (mod p), if p prime

Euler's theorem: a^\phi(n) = 1 (mod n), \forall n and a, s.t. gcd(a,n) = 1

Note that according to Fermat/Euler, we can check a potential generator a \in Z*_p for what size subgroup it generates by checking if a^(guessed size) = 1 (mod p). But that's not enough. We need to check that a^(potential smaller size) != 1 (mod p) or we could be picking a smaller group of size s' which divides the desired size s (i.e. if a^2q = 1, that could be because a^2 = 1 and a generates a subgroup of size 2).

Finding generators in Z*_p (p is a safe prime):

do
    g <- Z*_p
until |<g>| = p-1

How do we know that |<g>| = p-1? We check that:

g != 1 (mod p)
g^2 != 1 (mod p)
g^q != 1 (mod p)
g^2q = 1 (mod p) (p-1 = 2q and Fermat's little theorem)

Theorem: If p is a safe prime, then # generators is \phi(p-1) = q-1

General theorem: If p prime, then # of generators is \phi(p-1) >= (p-1)/(6*ln(ln(p-1)))

Common public-key setup

Public parameters:

Alice's secret key is x \in Z*_p, 1 <= x <= p-1, the public key is g^x = y (mod p)