In this post I want to talk about a thing from the Kryptos universe that are not directly related to the statue. But i think it may be an indirect hint to some Kryptos related methods. The Mayan Symbols in Ed Scheidts driveway I think everyone who knows Kryptos knows Ed Scheidt. The former Chairman of the Cryptographic Center at the CIA and founder of the cryptosystems used around the Kryptos statue. As already shown in Part 4 of my Kryptos series, in the driveway of Ed Scheidts house, there are two symbols: Figure 1 - Garage driveway of Ed Scheidt We denote the left symbol set with $S_1$ and the right one with $S_2$. It took me a while to find his house on Google Maps - Street View. To save you some time, here is the link with a view on the driveway. I you go back in time in Streetview, you can see that the symbols were already there in 2012. But it is impossible to say when they were built. $S_1$ is clearly visible from the street, $S_2$ is hidden in the view. But you can u...
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?
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?
Comments
Post a Comment