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 posts, i talked about the possibilities to insert backdoors in prime numbers (beside the property that $p-1$ is smooth). One of the potential ideas for a backdoor was to generate primes that allow an easy lift from $\mathbb{Z}/p$ to $\mathbb{Z}/{p^2}\mathbb{Z}$. But under the consideration of the $l$-Hensel Discrete Logarithm Assumption, this should be actually hard in the general case.
Because if you could successfully lift the element $e\equiv g^x\pmod{p}$ to $E\equiv g^x\pmod{p^2}$, then you could, as long as $x < \mathsf{ord}_p(g) = r$, compute
\begin{align*}
\left(g^x\right)^{r} \equiv (g^{r})^x \equiv (1+p\lambda)^x \pmod{p^2}
\end{align*}
Next, the Binomial Theorem gives
\begin{align*}
(1+p\lambda)^x \equiv \sum^x_{i=0}\binom{x}{i}p^i\lambda^i \equiv 1 + xp\lambda\pmod{p^2}
\end{align*}
and hence
\begin{align*}
\frac{E^{r} - 1}{p\lambda} \equiv x \pmod{p}
\end{align*}
So, if you are able to compute the lifted element $E$, you could compute the discrete logarithm $x$. However, as also mentioned in the $l$-Hensel Discrete Logarithm Assumption, it is not allowed to be $g^r \equiv 1\pmod{p^2}$. Because in that case, you could indeed compute $E$. But don't get exited, it does not help you to get $x$.
To see this, assume again $e\equiv g^x\pmod{p}$ and this time $g$ is also a $r$-th root of unity in $\mathbb{Z}/{p^2}\mathbb{Z}$. Note that such primes are called Generalized Wieferich Primes or Base-g Wieferich Primes. So you have
\begin{align*}
\left(g^x\right)^{r} \equiv (e+pX)^{r} \equiv E^r \equiv 1 \pmod{p^2}
\end{align*}
The integer $e$ is known, but we want to have $X$. We could further write
\begin{align*}
1 \equiv (e+pX)^r & \equiv \sum^{r}_{i=0}\binom{r}{i}e^{r-i}p^iX^i \pmod{p^2}\\
& \equiv e^{r} + re^{r-1}pX \pmod{p^2}
\end{align*} so
\begin{align*}
\frac{1-e^r}{re^{r-1}p} \equiv X \pmod{p}
\end{align*}
and hence we get $E = e + pX$. But in that case, you can not apply the previous algorithm to compute $x$, since we are in a group of order $r$ with $r|(p-1)$ and hence $\left( g^x \right)^r \equiv 1$, so $\lambda = 0$ which cancels the possibility to get $x$.
$E$ can be computed even simpler without the need to involve the Binomial Theorem. It holds that $$e^p \equiv E \pmod{p^2}$$ Based on Fermat Little Theorem $E$ must be $E\equiv e\pmod{p}$ And since $E$ is a $p$-th residue, it must hold $E^{p-1}\equiv 1\pmod{p^2}$. And since $E$ is the unique $p$-th residue with $E\equiv e\pmod{p}$ it is completely determined by $e^p\pmod{p^2}$.
Could the setup $g,p$ whereof $p$ is a $g$-base Wieferich Prime be utilized as a backdoor, i.e. an unsecure setup for a cryptosystem?
Because if you could successfully lift the element $e\equiv g^x\pmod{p}$ to $E\equiv g^x\pmod{p^2}$, then you could, as long as $x < \mathsf{ord}_p(g) = r$, compute
\begin{align*}
\left(g^x\right)^{r} \equiv (g^{r})^x \equiv (1+p\lambda)^x \pmod{p^2}
\end{align*}
Next, the Binomial Theorem gives
\begin{align*}
(1+p\lambda)^x \equiv \sum^x_{i=0}\binom{x}{i}p^i\lambda^i \equiv 1 + xp\lambda\pmod{p^2}
\end{align*}
and hence
\begin{align*}
\frac{E^{r} - 1}{p\lambda} \equiv x \pmod{p}
\end{align*}
So, if you are able to compute the lifted element $E$, you could compute the discrete logarithm $x$. However, as also mentioned in the $l$-Hensel Discrete Logarithm Assumption, it is not allowed to be $g^r \equiv 1\pmod{p^2}$. Because in that case, you could indeed compute $E$. But don't get exited, it does not help you to get $x$.
To see this, assume again $e\equiv g^x\pmod{p}$ and this time $g$ is also a $r$-th root of unity in $\mathbb{Z}/{p^2}\mathbb{Z}$. Note that such primes are called Generalized Wieferich Primes or Base-g Wieferich Primes. So you have
\begin{align*}
\left(g^x\right)^{r} \equiv (e+pX)^{r} \equiv E^r \equiv 1 \pmod{p^2}
\end{align*}
The integer $e$ is known, but we want to have $X$. We could further write
\begin{align*}
1 \equiv (e+pX)^r & \equiv \sum^{r}_{i=0}\binom{r}{i}e^{r-i}p^iX^i \pmod{p^2}\\
& \equiv e^{r} + re^{r-1}pX \pmod{p^2}
\end{align*} so
\begin{align*}
\frac{1-e^r}{re^{r-1}p} \equiv X \pmod{p}
\end{align*}
and hence we get $E = e + pX$. But in that case, you can not apply the previous algorithm to compute $x$, since we are in a group of order $r$ with $r|(p-1)$ and hence $\left( g^x \right)^r \equiv 1$, so $\lambda = 0$ which cancels the possibility to get $x$.
$E$ can be computed even simpler without the need to involve the Binomial Theorem. It holds that $$e^p \equiv E \pmod{p^2}$$ Based on Fermat Little Theorem $E$ must be $E\equiv e\pmod{p}$ And since $E$ is a $p$-th residue, it must hold $E^{p-1}\equiv 1\pmod{p^2}$. And since $E$ is the unique $p$-th residue with $E\equiv e\pmod{p}$ it is completely determined by $e^p\pmod{p^2}$.
Could the setup $g,p$ whereof $p$ is a $g$-base Wieferich Prime be utilized as a backdoor, i.e. an unsecure setup for a cryptosystem?
Comments
Post a Comment