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...
The discrete logarithm problem is one of the cornerstones of modern asymmetric cryptography. Several algorithms exist and each approaches the problem in different ways. For example, the Pohlig-Hellman algorithm exploits smooth group orders, the index calculus algorithm uses a small set of known discrete logarithms in order to combine them to solve the problem in question and Pollards Rho-Algorithms makes use of the birthday paradox.
I am not aware of any approach that makes use of the fact, that the residues $r_i$ in the group $\mathcal{G} \subseteq \mathbb{F}_p$ generated by the element $g$ are often nearly equal distributed. Ok, this is not always true and there are some deep and highly non-trivial theorems about the distribution of these group elements. But for our purposes we can assume that the average size of a group element is $(p-1)/2$. That means, if we assume that $g$ is a primitive root, hence $\mathcal{G} = \mathbb{F}^*_p$, and $r_i \equiv g^i\pmod{p}$ it holds: $$ \sum^e_{i=1} r_i \approx e\cdot \frac{p-1}{2} $$ And since $e < p$ it in particular holds $$ S := \sum^e_{i=1} r_i = e\cdot \frac{p-1}{2} + \mathcal{O}(p^{1/2}) < p^2 $$ So if we can compute $S$ we get a very good approximation of $e$ since $$ \frac{2\cdot S}{p-1} = e + \mathcal{O}(1) $$
Input: $(g,r_e,p)$. In order to get $S$, we can start and use our lovely Chinese Remainder Theorem (CRT). We can get the remainder of $S$ modulo $p$ easily via the following computation:
\begin{align*}
\sum^e_{i=1} r_i & \equiv \sum^e_{i=1} g^i \pmod{p}\\
&= \frac{g^{e+1}-g}{g-1} \equiv \frac{r_{e+1}-g}{g-1} \pmod{p}\\
&\equiv \frac{gr_e-g}{g-1} = R_1 \pmod{p}
\end{align*}
The computation of the value $R_1$ from the given input triple $(g,r_e,p)$ is already half of the work. Because another reduction by an integer of similar size as $p$ would immediately give us the entire sum $S$ using the CRT.
We assume that $S < p\cdot g$ which is not a real constraint since one could use the self-reducibility of the discrete logarithm together with the fact, that one could reduce the exponent $e$ "a little bit" by taking square roots and keeping track of all possibilities. But getting this other residue is of course as hard as the discrete logarithm problem.
So perhaps this is not the best sum to target. Fortunately, there are other sums which would also be worth to know, since they all depend heavily on the secret exponent $e$:
We write the dlp congruence as an equation $$\text{(Eq. 0)}\;\;\;g^e = r_e + p\sum^{e-1}_{j=0}k_{e,j}g^j$$, whereof the integers $k_{e,j}$ are the coefficients of the $g$-adic representation of the integer $(g^e-r_e)/p$. Next, we span an equation system:
\begin{align*}
g^1 & = r_1 + pk_{1,0} \\
g^2 & = r_2 + p(k_{2,1}g+k_{2,0}) \\
g^3 & = r_3 + p(k_{3,2}g^2+k_{3,1}g + k_{3,0}) \\
\ldots & = \ldots \\
g^{e-1} & = r_{e-1} + p(k_{e-1,e-2}g^{e-2}+\ldots+k_{e-1,0}) \\
g^e & = r_e + p(k_{e,e-1}g^{e-1}+\ldots+k_{e,0}) \\
\end{align*} Note that two coefficients $k_{i,j}$ and $k_{u,v}$ are equal if $i-j = u-v$. Knowing this, we can sum up the equations and get
\begin{align*}
\text{(Eq. 1)}\;\;\;\sum^e_{j=1} g^j = \sum^e_{j=1} r_j + p \sum^{e-1}_{j=0}k_{e,e-1-j}\sum^{e-1-j}_{i=0}g^i
\end{align*} If we reduce Eq. (1) modulo $g$, we get
\begin{align*}
\text{(Eq. 2)}\;\;\;0 & \equiv \sum^e_{j=1} r_j + p\sum^{e-1}_{j=0}k_{e,e-1-j}\pmod{g}\\
& \equiv S + p\sum^{e-1}_{j=0}k_{e,j} \pmod{g}
\end{align*} If we reduce Eq. (1) modulo $g-1$, we get
\begin{align*}
\text{(Eq. 3)}\;\;\;e & \equiv \sum^e_{j=1} r_j + p\sum^{e-1}_{j=0}(e-j)k_{e,e-1-j}\pmod{g-1}\\
& \equiv S + p\sum^{e-1}_{j=0}(j+1)k_{e,j} \pmod{g-1}
\end{align*} If we reduce Eq. (1) modulo $g+1$, we get (after some skipped computation)
\begin{align*}
\text{(Eq. 4)}\;\;\;-1 + r_{e+1} - pk_{e+1,0} \equiv 2S+ p\sum^{e-1}_{j=0}k_{e,j} \pmod{g+1}
\end{align*}
We multiply Eq. 2 by $2$ and use Eq. 4:
\begin{align*}
0 & \equiv 2S + 2p\sum^{e-1}_{j=0}k_{e,j}\pmod{g} \\
-1 + r_{e+1} - pk_{e+1,0} & \equiv 2S+ p\sum^{e-1}_{j=0}k_{e,j} \pmod{g+1} \\
\end{align*} The target is the entire sum $2S + p\sum^{e-1}_{j=0}k_{e,j}$, since it heavily depends on $e$. The left sides would be equal if $2p \equiv x\pmod{g}$ and $p \equiv x\pmod{g+1}$. Clearly, this is almost never true.
But (and this is connected with the problem to backdoor discrete logarithms in $\mathbb{F}_p$) is there at least a potential setup with $2p \equiv x\pmod{g}$ and $p \equiv x\pmod{g+1}$? And does this setup allow the combined sum $2S + p\sum^{e-1}_{j=0}k_{e,j}$ to be smaller than $g(g+1)$?
A rough estimation yields
\begin{align*}
2S + x\sum^{e-1}_{j=0}k_{e,j} & = 2e\frac{p-1}{2} + 2\mathcal{O}(p^{1/2}) + xe\frac{g-1}{2} + x\mathcal{O}(g^{1/2})\\
& \approx ep + xe\frac{g-1}{2}
\end{align*}
So, to make this work, we first test, if such a prime $p$ and an integer $g$ can be found theoretically: For the prime $p$ it must hold
\begin{align*}
2p \equiv x(g+1)I_1 + 2xgI_2 \pmod{g(g+1)}
\end{align*} whereof $I_1(g+1) \equiv 1\pmod{g}$ and $I_2g \equiv 1\pmod{g+1}$. Hence $I_1 = 1$ and $I_2 = -1$, so we have
\begin{equation}
p = \frac{x(g+1)}{2} - xg + \frac{g(g+1)}{2}K
\end{equation} We required that $$ ep + xe\frac{g-1}{2} < g(g+1) $$ If we use our computed $p$ value we get
\begin{align*}
ep + xe\frac{g-1}{2} & = e\left(\frac{x(g+1)}{2} - xg + \frac{g(g+1)}{2}K\right) + xe\frac{g-1}{2} \\
& = \frac{ex(g+1)}{2} - exg + \frac{eg(g+1)}{2}K + xe\frac{g-1}{2} \\
& = \frac{exg}{2}+\frac{ex}{2} - exg + \frac{eg(g+1)}{2}K + \frac{xeg}{2}-\frac{xe}{2} \\
& = \frac{eg(g+1)}{2}K \leq_? g(g+1)\\
\end{align*} Thus only for $e \leq 2$ the last inequality holds. So this particular approach does not work. But does this approach perhaps leads to some success, e.g. $e < c\cdot \log p$ regarding other or similar sums?
I am not aware of any approach that makes use of the fact, that the residues $r_i$ in the group $\mathcal{G} \subseteq \mathbb{F}_p$ generated by the element $g$ are often nearly equal distributed. Ok, this is not always true and there are some deep and highly non-trivial theorems about the distribution of these group elements. But for our purposes we can assume that the average size of a group element is $(p-1)/2$. That means, if we assume that $g$ is a primitive root, hence $\mathcal{G} = \mathbb{F}^*_p$, and $r_i \equiv g^i\pmod{p}$ it holds: $$ \sum^e_{i=1} r_i \approx e\cdot \frac{p-1}{2} $$ And since $e < p$ it in particular holds $$ S := \sum^e_{i=1} r_i = e\cdot \frac{p-1}{2} + \mathcal{O}(p^{1/2}) < p^2 $$ So if we can compute $S$ we get a very good approximation of $e$ since $$ \frac{2\cdot S}{p-1} = e + \mathcal{O}(1) $$
Input: $(g,r_e,p)$. In order to get $S$, we can start and use our lovely Chinese Remainder Theorem (CRT). We can get the remainder of $S$ modulo $p$ easily via the following computation:
\begin{align*}
\sum^e_{i=1} r_i & \equiv \sum^e_{i=1} g^i \pmod{p}\\
&= \frac{g^{e+1}-g}{g-1} \equiv \frac{r_{e+1}-g}{g-1} \pmod{p}\\
&\equiv \frac{gr_e-g}{g-1} = R_1 \pmod{p}
\end{align*}
The computation of the value $R_1$ from the given input triple $(g,r_e,p)$ is already half of the work. Because another reduction by an integer of similar size as $p$ would immediately give us the entire sum $S$ using the CRT.
We assume that $S < p\cdot g$ which is not a real constraint since one could use the self-reducibility of the discrete logarithm together with the fact, that one could reduce the exponent $e$ "a little bit" by taking square roots and keeping track of all possibilities. But getting this other residue is of course as hard as the discrete logarithm problem.
So perhaps this is not the best sum to target. Fortunately, there are other sums which would also be worth to know, since they all depend heavily on the secret exponent $e$:
We write the dlp congruence as an equation $$\text{(Eq. 0)}\;\;\;g^e = r_e + p\sum^{e-1}_{j=0}k_{e,j}g^j$$, whereof the integers $k_{e,j}$ are the coefficients of the $g$-adic representation of the integer $(g^e-r_e)/p$. Next, we span an equation system:
\begin{align*}
g^1 & = r_1 + pk_{1,0} \\
g^2 & = r_2 + p(k_{2,1}g+k_{2,0}) \\
g^3 & = r_3 + p(k_{3,2}g^2+k_{3,1}g + k_{3,0}) \\
\ldots & = \ldots \\
g^{e-1} & = r_{e-1} + p(k_{e-1,e-2}g^{e-2}+\ldots+k_{e-1,0}) \\
g^e & = r_e + p(k_{e,e-1}g^{e-1}+\ldots+k_{e,0}) \\
\end{align*} Note that two coefficients $k_{i,j}$ and $k_{u,v}$ are equal if $i-j = u-v$. Knowing this, we can sum up the equations and get
\begin{align*}
\text{(Eq. 1)}\;\;\;\sum^e_{j=1} g^j = \sum^e_{j=1} r_j + p \sum^{e-1}_{j=0}k_{e,e-1-j}\sum^{e-1-j}_{i=0}g^i
\end{align*} If we reduce Eq. (1) modulo $g$, we get
\begin{align*}
\text{(Eq. 2)}\;\;\;0 & \equiv \sum^e_{j=1} r_j + p\sum^{e-1}_{j=0}k_{e,e-1-j}\pmod{g}\\
& \equiv S + p\sum^{e-1}_{j=0}k_{e,j} \pmod{g}
\end{align*} If we reduce Eq. (1) modulo $g-1$, we get
\begin{align*}
\text{(Eq. 3)}\;\;\;e & \equiv \sum^e_{j=1} r_j + p\sum^{e-1}_{j=0}(e-j)k_{e,e-1-j}\pmod{g-1}\\
& \equiv S + p\sum^{e-1}_{j=0}(j+1)k_{e,j} \pmod{g-1}
\end{align*} If we reduce Eq. (1) modulo $g+1$, we get (after some skipped computation)
\begin{align*}
\text{(Eq. 4)}\;\;\;-1 + r_{e+1} - pk_{e+1,0} \equiv 2S+ p\sum^{e-1}_{j=0}k_{e,j} \pmod{g+1}
\end{align*}
We multiply Eq. 2 by $2$ and use Eq. 4:
\begin{align*}
0 & \equiv 2S + 2p\sum^{e-1}_{j=0}k_{e,j}\pmod{g} \\
-1 + r_{e+1} - pk_{e+1,0} & \equiv 2S+ p\sum^{e-1}_{j=0}k_{e,j} \pmod{g+1} \\
\end{align*} The target is the entire sum $2S + p\sum^{e-1}_{j=0}k_{e,j}$, since it heavily depends on $e$. The left sides would be equal if $2p \equiv x\pmod{g}$ and $p \equiv x\pmod{g+1}$. Clearly, this is almost never true.
But (and this is connected with the problem to backdoor discrete logarithms in $\mathbb{F}_p$) is there at least a potential setup with $2p \equiv x\pmod{g}$ and $p \equiv x\pmod{g+1}$? And does this setup allow the combined sum $2S + p\sum^{e-1}_{j=0}k_{e,j}$ to be smaller than $g(g+1)$?
A rough estimation yields
\begin{align*}
2S + x\sum^{e-1}_{j=0}k_{e,j} & = 2e\frac{p-1}{2} + 2\mathcal{O}(p^{1/2}) + xe\frac{g-1}{2} + x\mathcal{O}(g^{1/2})\\
& \approx ep + xe\frac{g-1}{2}
\end{align*}
So, to make this work, we first test, if such a prime $p$ and an integer $g$ can be found theoretically: For the prime $p$ it must hold
\begin{align*}
2p \equiv x(g+1)I_1 + 2xgI_2 \pmod{g(g+1)}
\end{align*} whereof $I_1(g+1) \equiv 1\pmod{g}$ and $I_2g \equiv 1\pmod{g+1}$. Hence $I_1 = 1$ and $I_2 = -1$, so we have
\begin{equation}
p = \frac{x(g+1)}{2} - xg + \frac{g(g+1)}{2}K
\end{equation} We required that $$ ep + xe\frac{g-1}{2} < g(g+1) $$ If we use our computed $p$ value we get
\begin{align*}
ep + xe\frac{g-1}{2} & = e\left(\frac{x(g+1)}{2} - xg + \frac{g(g+1)}{2}K\right) + xe\frac{g-1}{2} \\
& = \frac{ex(g+1)}{2} - exg + \frac{eg(g+1)}{2}K + xe\frac{g-1}{2} \\
& = \frac{exg}{2}+\frac{ex}{2} - exg + \frac{eg(g+1)}{2}K + \frac{xeg}{2}-\frac{xe}{2} \\
& = \frac{eg(g+1)}{2}K \leq_? g(g+1)\\
\end{align*} Thus only for $e \leq 2$ the last inequality holds. So this particular approach does not work. But does this approach perhaps leads to some success, e.g. $e < c\cdot \log p$ regarding other or similar sums?
Comments
Post a Comment