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...
❚ 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