EASTNORTHEAST - This is not exactly the hint Jim Sanborn (JS) gave for K4 on the 29th of January this year. He only gave NORTHEAST - which refers to the positions 26-34 of K4's plaintext. Beside BERLIN and CLOCK it is the third revealed plaintext word of K4. However, also this hint does not seem to help much. However, it just so happened, that a member in the yahoo kryptos group had a conversation with Jim Sanborn due to a submitted solution. Sandborn's answer to the question contained again the last clue which surprisingly was EASTNORTHEAST at position 22-34. Jim Sanborns compass rose at CIA There is disagreement if Jim revealed this on purpose or he did it accidentially, but the new extended clue seem to be serious and valid.Interestingly, EASTNORTHEAST is exactly the direction which is illustrated on the compass rose on one of the stones around kryptos, also created by Jim Sanborn. Actually, i dont really kn...
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