- finding primes
- one time MAC
- divisors, GCD, extended GCD, inverses
- order of elements
- generators

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

What we need:

- Are there a lot of
`k`

-bit primes? - Do we have a fast enough test to see if
`p`

is prime?

**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:

- Miller-Rabin
- AKS deterministic polytime

```
A m, t=MAC(t) B
---------------------------->
T
key = (slope,y-intercept) coordinates of the line?
| /
tag |----*
| /|
| / |
| / |
|/ |
------------------ M
msg
```

`p`

large prime 128-bits- key
`(a,b), 1 <= a,b <= p-1`

`a = slope`

`b = y-intercept`

`T = MAC_k(m) = am+b (mod p)`

**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

Notation: `d`

divides `a`

or `d`

is a divisor of `a`

-> `d | a <=> \exists k, s.t. a = dk`

`\forall d, d | 0`

`\forall a, 1 | 0`

- if
`d`

divisor of`a`

and`b`

then`d`

is a*common divisor* - greatest common divisor (gcd)
`gcd(0,0) = 0`

by definition`gcd(5,0) = 5`

`gcd(24,30) = 6`

`gcd(33,12) = 3`

`gcd(a, b) = 1 <=> a`

and`b`

are*relatively prime*

```
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
```

`\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?

- this is called a multiplicative group
`mod n`

How to find `a^-1`

:

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

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`

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`

- the discrete logarithm using the generator
`g`

base`p`

of`y`

`x = dlog_p,g(y)`

*Theorem:* `Z*_n`

has generator iff `n`

is 2, 4, `p^m`

, `2*p^m`

, where `p`

is an
odd prime & `m >= 1`

- we call such groups which have generators
**cyclic groups**

*Theorem:* If `p`

prime, then # of generators in `Z*_p`

is `\phi(p-1)`

`p=7 => \phi(6) = |{1,5}| = 2`

`p=11 => \phi(10) = |{1,3,7,9}| = 4`

*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*

`\phi(p) = p-1 = 2q`

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)))`

Public parameters:

`p`

large prime (2048 bit)`g`

generator of`Z*_p`

Alice's secret key is `x \in Z*_p, 1 <= x <= p-1`

, the public key is `g^x = y (mod p)`

- given
`y`

there is a unique solution`x`

for the equation - given
`y`

it is assumed to be very hard to find`x`