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?
- 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?
- 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?
- 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