Thursday, September 26, 2013

Backdooring Discrete Logarithms in $\mathbb{Z}^*_p$

In one of my previous post, i talked about the (potential) backdoor in the pseudo random number generator described in SP800-90 Dual Ec PRNG. The backdoor could be exploited by the usage of some perhaps existing secret relation among two given constants.

The concept of elliptic curves cryptography and its whole theory is much more complicated than the cryptography based on the finite fields $\mathbb{F}_p$ for a large prime number $p$. Implementing a backdoor in that case seems to be harder. Some people indeed say, that we should switch back to the good old fields $\mathbb{Z}^*_p$ to increase the confident in our systems.



But also those prime numbers $p$ could be chosen very badly. E.g. the prime factorization of $\varphi(p) = p-1$ must not be smooth to prevent information leakage via the Pohlig-Hellman Algorithm (PHA). 

It is convenient to pick for $p$ a Sofie-Germain prime number. These primes are also called safe-primes. They are of the form $p = 2p'+1$ and $p'$ is again a prime number. If you pick an element from the group of order $p'$ you can feel safe and also the Decisional Diffie-Hellman Assumption holds in this group.
The NIST published prime numbers that they recommend to use for elliptic curve cryptography. It is a bad idea to use this primes $p$ for cryptography in $\mathbb{Z}^*_p$, since their bit size is too small and for example for the recommend prime $p_{224}$ $$p_{224} = 2^{224} - 2^{96} + 1$$ it is $$p_{224} - 1 = 2^{96}\cdot 3\cdot 5\cdot 17\cdot 257\cdot 641\cdot 65537\cdot 274177\cdot 6700417\cdot 67280421310721$$ and is completely vulnerable to PHA.

A system normally generates a safe prime number by picking a candidate for $p'$ that is in the correct size and then tests if $2p'+1$ is again a prime number.

This is the only check that i am aware of. So the question i asked myself is: Is it possible to choose a "safe prime" $p$ in a certain way, such that it still has a backdoor to certain (helpful) information?
  1. What about $\varphi(\varphi(p)) = \varphi(p-1)$? That number is equal to the number of primitive roots in $\mathbb{Z}^*_p$. Does it matter if it is smooth? For example, the Blum-Blum-Shub PRNG has a period length of $\varphi(\varphi(N))$. Is it crucial if this period contains many small primes?
  2. Discrete logarithms are easy in $\mathbb{Z}^*_{p^2}$ (i.e., integers modulo $p^2$), as long as the exponent is less than $p$. It is possible to create $p$ in such a way that lifting the problem from $\mathbb{Z}^*_p$ to $\mathbb{Z}^*_{p^2}$ is easy? E.g., using some kind of Hensel-Lifting or similar techniques?
  3. Transferring the discrete logarithm from $\mathbb{Z}^*_p$ to $\mathbb{Z}^*_q$ for a different prime number $q$ seems to be hard in the general case. Or is there a class of prime number that allow such transfers?



No comments:

Post a Comment