MATH 470 Lecture 15

« previous | Tuesday, March 5, 2013 | next »

Midterm

Midterm Thursday after Spring Break

Material is anything up to today.

Practice midterm available on web page

Review

Powering mod $n$ is easy but slow.
Computing square roots mod prime $p$ is easy-ish
Computing square roots mod any integer $n$ is hard: in fact, deciding whether ${\sqrt {a}}\in [1,b]$ is NP-Complete
Deciding existence of square roots mod $p$ can be done by powering, but is faster via quadratic reciprocity of Jacobi symbols
Factoring appears hard, but is easy if computing square roots mod $n$ is easy.

El Gamal

Large prime $p$ , with $p-1$ having at least one huge prime factor
Generator $\alpha$ for $\left(\mathbb {Z} /p\mathbb {Z} \right)^{*}$
Number $a\in [2,2]$
$\beta =\alpha ^{a}{\pmod {p}}$

$(p,\alpha ,\beta )$ are public, recipient holds $a$ secret.

to transmit a message $m\in \left(\mathbb {Z} /p\mathbb {Z} \right)^{*}$ , the sender computes a random $k\in [2,p-2]$ , $\alpha ^{k}$ , and $\beta ^{k}$ ; and then sends $(\alpha ^{k},\beta ^{k}\,m){\pmod {p}}$

To decode, the recipient computes ${\frac {\beta ^{k}\,m}{(\alpha ^{k})^{a}}}={\frac {\text{2nd}}{\text{1st}}}{\pmod {p}}$

Questions:

How does this hide $m$ ? ( $\beta ^{k}$ appears random, and multiplication by it scrambles $m$ )
why does decryption work? ${\frac {\beta ^{k}\,m}{(\alpha ^{k})^{a}}}={\frac {\beta ^{k}\,m}{(\alpha ^{a})^{k}}}={\frac {\beta ^{k}\,m}{\beta ^{k}}}=m{\pmod {p}}$

Crypytanalysis

Most obvious: find $a$ .

Finding $a$ involves solving $\alpha ^{a}\equiv \beta {\pmod {p}}$ for $a$ . This involves solving the discrete log problem, which is appears to be hard

Example

$p=1009$
$\alpha =101$ (i.e. $\left\{\alpha ^{1},\ldots ,\alpha ^{1008}\right\}=\left\{1,\ldots ,1008\right\}$ )
$m=559$
pick $k=291$ at random and transmit $(\alpha ^{k},\beta ^{k}\,m)=(421,661)$

Pohlig-Hellman

Recall:

If $\beta$ is a square mod $p$ , then $\left({\tfrac {\beta }{p}}\right)\equiv \beta ^{\frac {p-1}{2}}\equiv 1{\pmod {p}}$ .
If $\beta$ is a non-square mod $p$ , then $\left({\tfrac {\beta }{p}}\right)\equiv \beta ^{\frac {p-1}{2}}\equiv -1{\pmod {p}}$ .

So if $\beta =\alpha ^{a}$ , we see that

when $a$ is even, then $\beta ^{\frac {p-1}{2}}\equiv 1{\pmod {p}}$
when $a$ is odd, then $\beta ^{\frac {p-1}{2}}\equiv -1{\pmod {p}}$

That is, you can tell the parity of $a$ (the last base-2 digit).

Example

$p=211$ , $\alpha =2$ , $a=?$ , and $\beta =5$

Notice that $p-1=210=2\cdot 3\cdot 5\cdot 7$ . This would be a bad choice.

Note: Fermat primes are of the form

2^{n}+1

We want to find $a$ with $2^{a}\equiv 5{\pmod {211}}$ . Is $a$ odd or even? (check Legendre symbol)

5^{\frac {p-1}{2}}\equiv 5^{105}\equiv 1{\pmod {211}}

So $a$ is even and $a\equiv 0{\pmod {2}}$ .

Now we want to find $a{\pmod {3}}$

5^{\frac {p-1}{3}}\equiv 5^{70}\equiv 2^{\left({\frac {p-1}{2}}\right)\,a_{0}}

Where $a_{0}\in [0,2]$ is the last digit mod 3.

We find $5^{7}0\equiv 1\equiv (2^{70})^{a_{0}}\equiv (-15)^{a_{0}}$ , so $a_{0}$ must be 0.

So $a\equiv 0{\pmod {3}}$

Now we want to find $a{\pmod {5}}$

5^{\frac {p-1}{5}}\equiv (\alpha ^{a})^{\frac {p-1}{5}}\equiv (\alpha ^{\frac {p-1}{5}})_{0}^{a}\equiv 2^{\left({\frac {p-1}{5}}\right)\,a_{0}}

$a_{0}\in [0,4]$ , and by brute force, $a_{0}=2$ .

So $a\equiv 2{\pmod {5}}$

Yada yada, $a\equiv 6{\pmod {7}}$

The Chinese Remainder Theorem states that we have a unique $a$ such that it is equivalent to (0,0,2,6) mod (2,3,5,7), respectively.

Combine $a\equiv 0{\pmod {2}}$ and $a\equiv 0{\pmod {3}}$ to get $a\equiv 0{\pmod {6}}$
Combine that with $a\equiv 6{\pmod {7}}$ to get $a\equiv 6{\pmod {42}}$
Combine that with $a\equiv 2{\pmod {5}}$ to get $a\equiv 132{\pmod {211}}$ .