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...
❚ Several weeks ago, i heard a nice talk from one of my colleagues about the Coppersmith method and it application to factoring integers. It is a very powerful method and can, e.g., be applied if partial information of $p$ or $q$ is known, the factors $p$ and $q$ of $N=pq$ have a small differences or to obtain a deterministic algorithm that returns a factor if a multiple of $\varphi(N)$ is known.
The trigger for the talk was a discussion about the risk if the inverse of one factor modulo the other factor of an RSA modulus is leaked. That means knowing the following integer $I$: $$I \equiv p^{-1} \pmod{q},\;p,q \in \mathbb{P},\;N=pq$$ Since the Coppersmith method is very powerful it is actually not surprising that it could be used to accomplish this task, at least partially.
Suppose you are given $N=pq$ and $I \equiv p^{-1}\mod{q}$ and $2^{n-1} < p < q < 2^n$, that is a balanced RSA-Modulus, which counts as a secure choice in cryptography. Then you have $$I \equiv p^{-1}\mod{q} \Leftrightarrow Ip = 1 + qk, k \in \mathbb{Z}$$ which is equivalent to $Ip^2 = p + Nk$, hence we get the monic polynomial $$f(x) = x^2 - xI^{-1} \equiv 0 \pmod{N}$$ of degree $\delta = 2$ that has $p$ as a root modulo $N$. If we assume that $p < q$, it is $p \leq N^{1/2}$ and $\gcd(f(p),N) = N$, hence $\beta = 1$. So indeed we have a case where our root is $|p| < N^{\beta^2/\delta} = N^{1/2}$ and we can find it in polynomial time.
But what if we have the inverse of $q^{-1} \pmod{p}$? In that case it is $$|q| > N^{1/2} = N^{1/2+\epsilon} = N^{\epsilon}N^{1/2} = cN^{1/2}$$
If $\epsilon = c'\log n/n$, for a constant $c'$, one gets $$N^{\epsilon} = N^{c'\log n/n} \approx 2^{n\cdot c'\log n/n} = 2^{c'\log n} = n^{c'}$$ But already a non-constant but slightly increasing $c' = n$ would lead to a quasi-polynomial complexity.
To give an example, take $n = 2048$ and $c' = 1$, which leads to $\epsilon = 11/2048 \approx 0.0050537$. So the algorithm will only be successful if the larger factor is not much larger than $\sqrt{N}$.
If you have both inverses, $p^{-1} \equiv I \pmod{q}$ and $q^{-1} \equiv J \pmod{p}$, you are done. Note that here $I$ and $J$ are both positive integers, hence they do not fulfill the equation $Ip + Jq = 1$ but $Ip + Jq = pq + 1$ It is easy to prove that $p < I + J < q+1$, so they can not be both small. Consequently, one of the two values $$I^{-1} \pmod{J} \; \text{or} \; J^{-1} \pmod{I}$$ yields either $p$ or $p - I$ or $p - J$, since at least one of $I$ and $J$ must be larger than $p/2$.
(Approach 1) Linear diophantine equation. Given the target integer $N=pq$, the most straight forward approach would be to find a linear diophantine equation $$ap + bq = c$$ with known $a$ and $c$. Given such an equation one could obtain the factor $q$ (with $Ip = 1+qk$) via $$\gcd(Ic-a,N) = q$$ since $$Ic = I(ap+bq) = a(1+qk) + Iqb = a + q(Ib+ak)$$ The method will only fail if $p | (Ib+ak)$. But how to find such an equation is not obvious.
(Approach 2) The inverse of I mod N. Another approach could be do compute the inverse of $I$ in $\mathbb{Z}^*_N$, denoted as $R$: $$IR \equiv 1 \pmod{N}$$ This $R$ must be of the form $$R = p + qs, s < p$$ It has the nice property that $R^e \equiv p^e + (qs)^e \pmod{N}$, for any integer $e$. Note that $R$ is actually a linear diophantine equation with known $a$ and $c$ but
\begin{align*}
IR & = Ip + qIs = 1 + qk + qIs \\
\Leftrightarrow & \\
IR-1 & = q(k+Is)
\end{align*}
But since $N|(IR-1)$, it is $p|(k+Is)$, so Approach 1 fails.
A representation of an integer $1\leq R \leq N$ as an linear combination of the two factors $p$ and $q$ is always possible, but what is special about $R$ is, that the coefficient of $p$ is not only known, but very small - it is ONE. This leaves much room to play and to learn something about the other coefficient $s$. But it seems, that this room is only half of the required size.
(Approach 3) Using the group order (p-1)(q-1). For an RSA modulus $N=pq$ Euler's Totient Function has the value $\varphi(N) = (p-1)(q-1)$. Hence for a co-prime integer $g$, it is $$g^{N+1} \equiv g^{p+q}\pmod{N}$$ Consequently, after subtracting $R$ in the exponent one gets is $$g^{N+1-R} \equiv g^{q(1-s)}\pmod{N}$$ The exponent, which is now a multiple of $q$, must be useful somehow, but not yet for me.
Likewise, the group order can be used to factor $$g^{N-1} \equiv g^{p + q - 2}$$ into the following two group elements. We know that $g^{q-2} \pmod{q}$ is the inverse element if $g$ in $\mathbb{Z}^*q$. So if we set $g = I$, we have
\begin{align*}I^{N-1} & \equiv I^{p+q-2} \equiv I^p\cdot I^{q-2} \pmod{N}\\
& \equiv (I+p\lambda)(p+q\gamma) \pmod{N}\\
\end{align*} for some integer $0 \leq \lambda_1 < q$ and $0 \leq \gamma_0 < p$.
❚ Perhaps since even the Coppersmith method isn't successful in solving this problem in every setup, the inability to find an easy elementary algorithm should be not surprising. However, i am not very pleased with this reasoning. If anyone of you knows a better way to do this or has some good ideas, leave me a note.
The trigger for the talk was a discussion about the risk if the inverse of one factor modulo the other factor of an RSA modulus is leaked. That means knowing the following integer $I$: $$I \equiv p^{-1} \pmod{q},\;p,q \in \mathbb{P},\;N=pq$$ Since the Coppersmith method is very powerful it is actually not surprising that it could be used to accomplish this task, at least partially.
| ❰Coppersmith's Theorem❱ Let $0 < \beta < 1$ and $c,N \geq 1$ and $f \in \mathbb{Z}[x]$ be a monic polynomial of degree $\delta$. The set of all integer $a \in \mathbb{Z}$ with $$\gcd(f(a),N) \geq N^\beta \; \text{and} \; |a| \leq cN^{\beta^2/\delta}$$ can be computed in time $\text{poly}(c,\delta,\log N)$. |
Suppose you are given $N=pq$ and $I \equiv p^{-1}\mod{q}$ and $2^{n-1} < p < q < 2^n$, that is a balanced RSA-Modulus, which counts as a secure choice in cryptography. Then you have $$I \equiv p^{-1}\mod{q} \Leftrightarrow Ip = 1 + qk, k \in \mathbb{Z}$$ which is equivalent to $Ip^2 = p + Nk$, hence we get the monic polynomial $$f(x) = x^2 - xI^{-1} \equiv 0 \pmod{N}$$ of degree $\delta = 2$ that has $p$ as a root modulo $N$. If we assume that $p < q$, it is $p \leq N^{1/2}$ and $\gcd(f(p),N) = N$, hence $\beta = 1$. So indeed we have a case where our root is $|p| < N^{\beta^2/\delta} = N^{1/2}$ and we can find it in polynomial time.
But what if we have the inverse of $q^{-1} \pmod{p}$? In that case it is $$|q| > N^{1/2} = N^{1/2+\epsilon} = N^{\epsilon}N^{1/2} = cN^{1/2}$$
If $\epsilon = c'\log n/n$, for a constant $c'$, one gets $$N^{\epsilon} = N^{c'\log n/n} \approx 2^{n\cdot c'\log n/n} = 2^{c'\log n} = n^{c'}$$ But already a non-constant but slightly increasing $c' = n$ would lead to a quasi-polynomial complexity.
To give an example, take $n = 2048$ and $c' = 1$, which leads to $\epsilon = 11/2048 \approx 0.0050537$. So the algorithm will only be successful if the larger factor is not much larger than $\sqrt{N}$.
Are there alternative Methods ?
❚ I was wondering if such a heavy weapon as the Coppersmith method is really necessary in this case. Intuitively, the integer $I$ should already give enough information to obtain the two factors $p$ and $q$ with more elementary methods than launching Coppersmith, lattice theory and the LLL algorithm. With "more elementary" i mean some basic group or integer operations that finally lead to an integer $t$ with $\gcd(N,t) > 1$. But it seems that my intuition is wrong in this case.If you have both inverses, $p^{-1} \equiv I \pmod{q}$ and $q^{-1} \equiv J \pmod{p}$, you are done. Note that here $I$ and $J$ are both positive integers, hence they do not fulfill the equation $Ip + Jq = 1$ but $Ip + Jq = pq + 1$ It is easy to prove that $p < I + J < q+1$, so they can not be both small. Consequently, one of the two values $$I^{-1} \pmod{J} \; \text{or} \; J^{-1} \pmod{I}$$ yields either $p$ or $p - I$ or $p - J$, since at least one of $I$ and $J$ must be larger than $p/2$.
(Approach 1) Linear diophantine equation. Given the target integer $N=pq$, the most straight forward approach would be to find a linear diophantine equation $$ap + bq = c$$ with known $a$ and $c$. Given such an equation one could obtain the factor $q$ (with $Ip = 1+qk$) via $$\gcd(Ic-a,N) = q$$ since $$Ic = I(ap+bq) = a(1+qk) + Iqb = a + q(Ib+ak)$$ The method will only fail if $p | (Ib+ak)$. But how to find such an equation is not obvious.
(Approach 2) The inverse of I mod N. Another approach could be do compute the inverse of $I$ in $\mathbb{Z}^*_N$, denoted as $R$: $$IR \equiv 1 \pmod{N}$$ This $R$ must be of the form $$R = p + qs, s < p$$ It has the nice property that $R^e \equiv p^e + (qs)^e \pmod{N}$, for any integer $e$. Note that $R$ is actually a linear diophantine equation with known $a$ and $c$ but
\begin{align*}
IR & = Ip + qIs = 1 + qk + qIs \\
\Leftrightarrow & \\
IR-1 & = q(k+Is)
\end{align*}
But since $N|(IR-1)$, it is $p|(k+Is)$, so Approach 1 fails.
A representation of an integer $1\leq R \leq N$ as an linear combination of the two factors $p$ and $q$ is always possible, but what is special about $R$ is, that the coefficient of $p$ is not only known, but very small - it is ONE. This leaves much room to play and to learn something about the other coefficient $s$. But it seems, that this room is only half of the required size.
(Approach 3) Using the group order (p-1)(q-1). For an RSA modulus $N=pq$ Euler's Totient Function has the value $\varphi(N) = (p-1)(q-1)$. Hence for a co-prime integer $g$, it is $$g^{N+1} \equiv g^{p+q}\pmod{N}$$ Consequently, after subtracting $R$ in the exponent one gets is $$g^{N+1-R} \equiv g^{q(1-s)}\pmod{N}$$ The exponent, which is now a multiple of $q$, must be useful somehow, but not yet for me.
Likewise, the group order can be used to factor $$g^{N-1} \equiv g^{p + q - 2}$$ into the following two group elements. We know that $g^{q-2} \pmod{q}$ is the inverse element if $g$ in $\mathbb{Z}^*q$. So if we set $g = I$, we have
\begin{align*}I^{N-1} & \equiv I^{p+q-2} \equiv I^p\cdot I^{q-2} \pmod{N}\\
& \equiv (I+p\lambda)(p+q\gamma) \pmod{N}\\
\end{align*} for some integer $0 \leq \lambda_1 < q$ and $0 \leq \gamma_0 < p$.
❚ Perhaps since even the Coppersmith method isn't successful in solving this problem in every setup, the inability to find an easy elementary algorithm should be not surprising. However, i am not very pleased with this reasoning. If anyone of you knows a better way to do this or has some good ideas, leave me a note.
Comments
Post a Comment