MATH 470 Lecture 20

« previous | Tuesday, April 2, 2013 | next »

Provably Good Hash Function

Why do we care about hash functions?

• Vital for signatures (sign a message digest instead of the whole message)
• message padding
• Error-checking

Chaum, Van Hiejst, Pfitzman, 1992:

Following construction is strongly-collision-resistant, assuming discrete log is hard:

1. Find large prime $p$ with $q=\frac{p-1}{2}$ also prime.
   • in practice, pick $q$ and then check if $p=2q+1$ is prime
   • easy via Prime Number Theorem and assumption of randomness of primes: for 100-digit number, there are approx. $\frac{10^{100}}{\log 10^{100}}$ primes in $\{1,\dots ,10^{100}\}$.
2. Pick 2 (distinct) generators $\alpha$ and $\beta$ for ${(\mathbb{\mathbb{Z}}/p\mathbb{\mathbb{Z}})}^{*}$
3. $H:\mathbb{\mathbb{Z}}/q^2\mathbb{\mathbb{Z}}\to {(\mathbb{\mathbb{Z}}/p\mathbb{\mathbb{Z}})}^{*}$ is defined by $H(x)={\alpha }^{x_0}{\beta }^{x_1}(\mathrm{mod}p)$, where $x=(x_1,x_0{)}_q$ are the base-$q$ numbers of $x$
   • Converting from $2{\log }_{10}q$ digits to ${\log }_{10}p={\log }_{10}q+C$ digits.

good

"provably good"

bad

Too inefficient for practical applications

Only halves the number of digits

ugly

In practice, a simpler (Ad-Hoc) construction is used: SHA-1

Proof

Proposition. $H$ is (2) pre-image resistant and (3) strongly-collision-resistant.

Proof. Let's prove (3) first.

Assumptions:

• discrete logarithm is not computable in polynomial time.
• we can find $x,x^{\prime }\in \mathbb{\mathbb{Z}}/q^2\mathbb{\mathbb{Z}}$ with $H(x)=H(x^{\prime })$ in polynomial time.

If we find such $x$ and $x^{\prime }$, then we have

$\begin{array}{rl}x& =x_0+x_{1}q\\ x^{\prime }& ={x_0}^{\prime }+{x_1}^{\prime }q\end{array}$

and

${\alpha }^{x_0}{\beta }^{x_1}\equiv {\alpha }^{{x_0}^{\prime }}{\beta }^{{x_1}^{\prime }}(\mathrm{mod}p)$

Now since $\alpha$ is a generator for ${(\mathbb{\mathbb{Z}}/p\mathbb{\mathbb{Z}})}^{*}$, $\beta ={\alpha }^a$ for some $a$ we don't know.

In fact, $a$ is the discrete log of $\beta$ to the base $\alpha$, mod $p$.

Therefore

$\begin{array}{rl}{\alpha }^{x_0}{\alpha }^{a{x}_1}& ={\alpha }^{{x_0}^{\prime }}{\alpha }^{a{x_1}^{\prime }}(\mathrm{mod}p)\\ {\alpha }^{a(x_1-{x_1}^{\prime })}& ={\alpha }^{{x_0}^{\prime }-x_0}(\mathrm{mod}p)\\ a(x_1-{x_1}^{\prime })& ={x_0}^{\prime }-x_0(\mathrm{mod}p-1)\end{array}$

This congruence has a solution for $a$ iff $\mathrm{G}\mathrm{C}\mathrm{D}(x_1-{x_1}^{\prime },p-1)\mid ({x_0}^{\prime }-x_0)$.

So what can that GCD be?

$x_1,{x_1}^{\prime }\in \{0,\dots ,q-1\}$ by construction, so $-(q-1)\le x_1-{x_1}^{\prime }\le q-1$

Also, $p-1=2q$, so the GCD is either 1 or 2, $q$, or $2q$. $q$ and $2q$ are too big, so only 1 and 2 remain.

Solution can now be found in poly time: Just try solutions!

$\begin{array}{rl}{\alpha }^{a_1}& {=}^{?}\beta \\ {\alpha }^{a_2}& {=}^{?}\beta \end{array}$

We've just found the discrete log!

Now if ${x_1}^{\prime }=x_1$ then $x_0={x_0}^{\prime }$ and $x=x^{\prime }$. CONTRADICTION!

Therefore, if $H$ is not strongly-collision-resistant, then the discrete logarithm must be easy!

(2) is easy to prove, but we'll get to that later.

Q.E.D.

Pseudo-Random Generators

"Something even more fundamental"

Polynomial Congruential

One of Simplest PRGs: Linear congruential:

$\begin{array}{rl}{x}_0& =seed\in \{0,m-1\}\\ x_{n+1}& =a{x}_n+b(\mathrm{mod}m)a,b\in (\mathbb{\mathbb{Z}}/m\mathbb{\mathbb{Z}})\end{array}$

This "smells" random, but is terribly insecure: If you can find 3 consecutive $x_i$s, then you can easily find $a$ and $b$:

$\begin{array}{rl}{x}_i& =a{x}_{i-1}+b\\ x_{i+1}& =a{x}_i+b\end{array}$

Linear system is solvable given $x_{i-1}\equiv ̸x_i(\mathrm{mod}m)$

In fact, any polynomial congruential generators are insecure due to predictability.

Blum-Blum-Shub Random Bit Generator

More Sophisticated:

1. Pick large primes $p$ and $q$ with $p\equiv q\equiv 3(\mathrm{mod}p)$, let $n=pq$, and pick a random $x\in {(\mathbb{\mathbb{Z}}/n\mathbb{\mathbb{Z}})}^{*}$ Let seed be $x_0=x^2(\mathrm{mod}n)$
2. </math>x_{n+1} = x_n^2 \pmod{n}</math> Return $b_n$ be the last bit of $x_n$.

Theorem

Assume computing Jacobi symbol $\left(\frac{u}{n}\right)$ is not doable in polynomial time. Then the BBS Bit Generator is indistinguishable from a truly random bit stream, by any polynomial time algorithm.

Note: In modern analysis, how much time do you wish to invest to prove randomness?

Random numbers have certain properties according to probability

Elliptic Curves

Elliptic Curve Cryptography (ECC) is already being used in smart cards in Europe as an extra layer of security.

Using RSA, high security implies huge keys and slow computation

ECC allows "high security" using 300-bit keys (maybe equiv 4000-bit RSA key)

Idea: work with a more general "group" than ${(\mathbb{\mathbb{Z}}/p\mathbb{\mathbb{Z}})}^{*}$ or ${(\mathbb{\mathbb{Z}}/pq\mathbb{\mathbb{Z}})}^{*}$. Instead, ECC uses points on a curve over a finite field.