MATH 470 Lecture 16

« previous | Thursday, March 7, 2013 | next »

Pohlig-Hellman

Recall:

• The security of RSA is based on the (apparent) hardness of integer factoring.
• The security of El Gamal is based on the (apparent) hardness of discrete logarithms.

For El Gamal, you should really only use $p$ with $p-1$ having at least 1 large factor. Otherwise, you can easily break El Gamal easily via the Pohlig-Hellman method:

input: prime $p$, $\alpha ,\beta \in (\mathbb{\mathbb{Z}}/p\mathbb{\mathbb{Z}}{)}^{*}$ such that $\beta ={\alpha }^a(\mathrm{mod}p)$

output: $a$

1. factor $p-1$ as $2^{r_1}\cdot 3^{r_2}\dots p_n^{r_n}$
2. find an $a_i$ with $a\equiv a_i(\mathrm{mod}{p}_i^{r_i})$ for all $i\in [1,n]$
3. Recover $a$ from $a_1,\dots ,a_n$ via the Chinese Remainder Theorem.

Main trick to (2) is to expand $a$ in base $p_i$: $\begin{array}{rlr}a& =d_0+d_1{p}_i+d_2{p}_i^2+\dots +d_n{p}_i^n& =\left({\alpha }^{d_0}\right){\left({\alpha }^{d_1}\right)}^{p_i}\dots {\left({\alpha }^{d_n}\right)}^{p_i^n}\end{array}$

Example

Last time, we used a prime with $p-1$ having many small primes and no power greater than 1.

This time, we'll use a prime with $p-1$ having only one prime and a large power:

p = 65537 R = Integers(p) alpha = R(3) beta = R(2) factor(p-1) # => 2^16




1. 1. FIND d0 ##

1. beta^((p-1)/2) == (alpha^a)^((p-1)/2)

beta^((p-1)/2) # => 1

1. (alpha^a)^((p-1)/2) == (3^d0)^((p-1)/2) * (3^(2*d1))^((p-1)/2) * ...
2. == (3^((p-1)/2))^d0 * (3^(p-1))^d1 * ...
3. == 3^(d0*(p-1)/2) * 1 * 1 * ...

3^((p-1)/2) # => -1

1. d0 == 0 since (-1)^d0 == 1

d0 = 0

1. 1. FIND d1 ##

1. beta = (alpha^d0) * (alpha^d1)^2 * ... * (alpha^d15)^(2^15)
2. therefore beta/alpha^d0 == (alpha^d1)^2 * ... * (alpha^d15)^(2^15)

beta/alpha^d0 # => 2

1. raise both sides to the (p-1)/2^2 th power
2. 2^((p-1)/2^2) == alpha^(2*d1*(p-1)/2^2) * alpha^(2^2*d1*(p-1)/2^2) * ... * alpha^(2^15*d15*(p-1)/2^2)
3. == (alpha^((p-1)/2))^d1 * 1 * 1 * ... * 1

R(2)^((p-1)/2^2) # => 1 alpha^((p-1)/2) # => -1

1. d1 == 0 since (-1)^d0 == 1

d1 = 0

1. 1. FIND d2 ##

1. beta/alpha^(d0+2*d1) == alpha^(d2*2^2) * alpha^(d15*2^15)

beta/alpha^(d0+2*d1) # => 2

1. raise to (p-1)/2^3 power
2. 2^((p-1)/2^3) == alpha^(4*d2*(p-1)/2^3) * 1 * ... * 1

R(2)^((p-1)/2^3) # => 1 alpha^(4*(p-1)/2^3) #=> -1

1. d2 == 0 since (-1)^d2 == 1

d2 = 0

1. 1. CONTINUE IN SAME WAY ##
2. . . .
3. a = 55296

Proof Example

Prove Fermat's Little Theorem.

Proposition. Given any $a\in \mathbb{\mathbb{Z}}$ and prime $p$, then $a^{p-1}\equiv 1(\mathrm{mod}p)$.

Proof. Consider the numbers $a$, $2a$, …, $(p-1)a$. They are distinct mod $p$ since

$\begin{array}{rl}ia& \equiv ja(\mathrm{mod}p)\\ (i-j)a& \equiv 0(\mathrm{mod}p)\\ i-j& \equiv 0(\mathrm{mod}p)\\ i& \equiv j(\mathrm{mod}p)\end{array}$

We can divide by $a$ in step 3 since $\mathrm{G}\mathrm{C}\mathrm{D}(a,p)=1$.

So then $\{a,2a,3a,\dots ,(p-1)a\}=\{1,\dots ,p-1\}$

If we multiply all elements of these sets, we get

$\begin{array}{rl}{a}^{p-1}(p-1)!& =(p-1)!(\mathrm{mod}p)\\ a^{p-1}& =1(\mathrm{mod}p)\end{array}$

Q.E.D.

Non-Computational Example

Find $k$ such that computing the exact power of 3 dividing $n$ is doable in time $O({\log }^k(N))$

Hint: You may assume that multiplying or dividing two numbers no bigger than $n$ takes time $O({\log }^{2}n)$

Solution: Use binary search

Check if $N$ is divisible by 3, 3², 3⁴, etc.

At a certain point, we get $3^{2^j}\mid n$, but $3^{2^{j+1}}\nmid n$. Note $3^{2^j}\le n$, so

$\begin{array}{rl}{3}^{2^j}& =n\\ 2^j& ={\log }_{3}n\\ j& ={\log }_2({\log }_{3}n)\end{array}$

So checks take $O((\log \log n)({\log }^{}n))$.

Suppose $n=645,700,815$. $3^{2^4}\mid n$, but $2^4$ is not the highest power dividing $n$.

Replace $n$ by $n^{\prime }=\frac{n}{3^{2^j}}$

Example: $n^{\prime }=\frac{n}{3^{2^4}}=15$

Note $n^{\prime }\le \frac{n}{3}$ since $3^{2^{j+1}}\nmid n$. Now proceed recursively:

This takes at most ${\log }_{3}n$ binary searches, and since each binary search takes $O((\log \log n)({\log }^{}n))$ time, the total work is:

$O((\log \log n)({\log }^{}n))$

Now $k=3+ϵ$ for any $ϵ>0$ since we have that $\log \log n$ factor.

Moral

Factoring $n$ may take exponential time (in $\log n$), but computing the unique $j$ with $n=p^{j}m$ for $p\nmid m$ is doable in polynomial time (in $\log n$).