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 {Z} /p\mathbb {Z} )^{*}$ such that $\beta =\alpha ^{a}{\pmod {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}{\pmod {p_{i}^{r_{i}}}}$ for all $i\in [1,n]$
3. Recover $a$ from $a_{1},\ldots ,a_{n}$ via the Chinese Remainder Theorem.

Main trick to (2) is to expand $a$ in base $p_{i}$: ${\begin{aligned}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{aligned}}$

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 {Z}$ and prime $p$, then $a^{p-1}\equiv 1{\pmod {p}}$.

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

${\begin{aligned}i\,a&\equiv j\,a{\pmod {p}}\\(i-j)\,a&\equiv 0{\pmod {p}}\\i-j&\equiv 0{\pmod {p}}\\i&\equiv j{\pmod {p}}\end{aligned}}$

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

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

If we multiply all elements of these sets, we get

${\begin{aligned}a^{p-1}\,(p-1)!&=(p-1)!{\pmod {p}}\\a^{p-1}&=1{\pmod {p}}\end{aligned}}$

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}}\leq n$, so

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

So checks take $O((\log {\log {n}})\,(\log ^{2}{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'={\frac {n}{3^{2^{j}}}}$

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

Note $n'\leq {\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 ^{2}{n}))$ time, the total work is:

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

Now $k=3+\epsilon$ for any $\epsilon >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}$).