In this article, we demonstrate a subtle but devastating backdoor in finite-field Diffie–Hellman. By computing public keys modulo $p^2$ instead of $p$ while restricting the secret exponent to $x \leq p-1$, the discrete logarithm becomes efficiently recoverable using Fermat quotients. We show the full derivation and provide a working Sage implementation. Backdoors are always bad — but they are catastrophic when they are embedded in a fundamental primitive like Diffie–Hellman key exchange. If your browser shows a green lock, you assume your connection is secure. But what if the implementation of Diffie–Hellman contains a tiny change that looks harmless in code review — and yet allows an attacker to recover the private exponent in milliseconds? In this post I’ll show a nasty little backdoor that requires only a tiny modification: using a modulus of $p^2$ instead of $p$, while keeping the secret exponent bounded by $p$ This ...
To show that quantum computers are indeed able to solve some problems more efficiently than classical computers, one of the first problems that were published was Simon's problem.
As usual the $\oplus$ is the bitwise XOR-function. On a classical computer, Simon's problem can only be solved in time that is exponential in $n$, whereof on a QC already $\mathcal{O}(n)$ queries are enough.
Simon's problem can also be seen as some kind of period finding problem. Assume you have a function $f$ and for $f$ it holds that:
\begin{align}
f(1) &= e_1 \\
f(2) &= e_2 \\
... &\\
f(a-1) &= e_{a-1}\\
f(a) &= e_a = 1\\
f(a+1) &= f(1) = e_1\\
f(a+2) &= f(2) = e_2 \\
... &
\end{align}
A non-trivial function that behaves like this is, e.g., the function $f_{p,g}(x) = g^x \pmod{p}$, if $a$ is the order of $g$ in $\mathbb{F}^*_p$ and whenever $x \oplus a = x+a$. This is a very special setup and is almost always not fulfilled for random primes $p$. But, e.g., whenever $a = 2^t$ and $p-1=2^{t+1}$ this holds. For example $p=17$ and $g=2$. Then $f_{17,2}(x)$ has the described property and is a valid function according to Simon's problem definition.
I mention this here, because finding the order of a given integer $a \in \mathbb{Z}^*_n$ is exactly what Shor's quantum algorithm does and thus can be seen as a generalisation of this algorithm.
Where a classical computer is limited to execute the function $f$ for one integer after another, a QC does the following:
Assume that $n = 4$ and we take the function $f_{17,2}$. We prepare two quantum registers of $n=4$ bits, that are all initialized with $0$'s.
\begin{align}
R_1 &= \left(1\cdot |0\rangle + 0\cdot |1\rangle\right) \left(1\cdot |0\rangle + 0\cdot |1\rangle\right) \left(1\cdot |0\rangle + 0\cdot |1\rangle\right) \left(1\cdot |0\rangle + 0\cdot |1\rangle\right) \\
R_2 &= \left(1\cdot |0\rangle + 0\cdot |1\rangle\right) \left(1\cdot |0\rangle + 0\cdot |1\rangle\right) \left(1\cdot |0\rangle + 0\cdot |1\rangle\right) \left(1\cdot |0\rangle + 0\cdot |1\rangle\right) \\
\end{align} First, the Hadamard-Operation $\mathcal{R}_n$
\begin{equation}
\mathcal{R}_n: |x\rangle \mapsto \frac{1}{2^{n/2}}\sum^{2^n-1}_{u=0}(-1)^{x\odot u}|u\rangle
\end{equation}
is applied to the first register, which creates the uniform state, i.e., every integer from $0$ to $15$ is measured with the same probability of $1/16$. The operation $\odot$ is the following:
If the binary representation of $u$ and $x$ are $u_{n-1}u_{n-2}...u_1u_0$ and $x_{n-1}x_{n-2}...x_1x_0$ respectively, then $x\odot u = \sum^{n-1}_{i=0}u_ix_i $. So we can write $R_1$ as
\begin{align}
R_1 &= \\
& \left(\frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle\right) \left(\frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle\right) \left(\frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle\right) \left(\frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle\right)\end{align}
and written in another way (after using the distributive law) it is
\begin{align}
R_1 = &\frac{1}{4}|0000\rangle + \frac{1}{4}|0001\rangle + \frac{1}{4}|0010\rangle + \frac{1}{4}|0011\rangle\\
&\frac{1}{4}|0100\rangle + \frac{1}{4}|0101\rangle + \frac{1}{4}|0110\rangle + \frac{1}{4}|0111\rangle\\
&\frac{1}{4}1000\rangle + \frac{1}{4}|1001\rangle + \frac{1}{4}|1010\rangle + \frac{1}{4}1011\rangle\\
&\frac{1}{4}|1100\rangle + \frac{1}{4}|1101\rangle + \frac{1}{4}|1110\rangle + \frac{1}{4}|1111\rangle\\
= &\frac{1}{4}\sum^{15}_{x=0} |x\rangle
\end{align} So each value is measure with the probablity $(1/4)^2 = 1/16$. Then the function $f_{17,2}$ is applied, thereby entagling the first register $R_1$ with the $R_2$.
\begin{align}
R_2 = &\frac{1}{4}|f_{17,2}(0)\rangle + \frac{1}{4}|f_{17,2}(1)\rangle + \frac{1}{4}|f_{17,2}(2)\rangle + \frac{1}{4}|f_{17,2}(3)\rangle\\
&\frac{1}{4}|f_{17,2}(4)\rangle + \frac{1}{4}|f_{17,2}(5)\rangle + \frac{1}{4}|f_{17,2}(6)\rangle + \frac{1}{4}|f_{17,2}(7)\rangle\\
&\frac{1}{4}|f_{17,2}(8)\rangle + \frac{1}{4}|f_{17,2}(9)\rangle + \frac{1}{4}f_{17,2}(10)\rangle + \frac{1}{4}|f_{17,2}(11)\rangle\\
&\frac{1}{4}|f_{17,2}(12)\rangle + \frac{1}{4}|f_{17,2}(13)\rangle + \frac{1}{4}|f_{17,2}(14)\rangle + \frac{1}{4}|f_{17,2}(15)\rangle\\
= &\frac{1}{4}\sum^{15}_{x=0} |f_{17,2}(x)\rangle
\end{align} Writing this together in one equation is
\begin{equation}
R_1R_2 = \frac{1}{4}\sum^{15}_{x=0}|x\rangle|f_{17,2}(x)\rangle
\end{equation}
We next apply the Hadamard operations $\mathcal{R}_{4}$ to the first register $R_1$
\begin{align}
R_1R_2 &= \frac{1}{4}\sum^{15}_{x=0} \frac{1}{4}\sum^{15}_{u=0}(-1)^{x\odot u}|u\rangle|f_{17,2}(x)\rangle\\
&= \frac{1}{16}\sum^{15}_{x=0} \sum^{15}_{u=0}(-1)^{x\odot u}|u\rangle|f_{17,2}(x)\rangle
\end{align} If we define $\mathcal{S}$ to be the subset of $\{0,1,2,...,15\}$, that contains all integers that create distinct $f$ values (in our particular case $\mathcal{S}$ would be $\{0,1,...,7\}$ since $x \oplus a = x + a$) we can write
\begin{align}
R_1R_2 &= \frac{1}{16}\sum_{x\in \mathcal{S}} \sum^{15}_{u=0}\left((-1)^{x\odot u}+(-1)^{(x\oplus a) \odot u}\right)|u\rangle|f_{17,2}(x)\rangle
\end{align} and this is the only step were we used that $f(x) = f(x\oplus a)$. Furthermore, since the base element is $(-1)$ and thus we are actually working modulo $2$, for the $\odot$ operation and the $\oplus$ operation the following holds $$(-1)^{(x\oplus a) \odot u} = (-1)^{x\odot u}(-1)^{a\odot u}$$
Proof. We have to show that $(x\oplus a)\odot u \equiv x\odot u + a\odot u \pmod{2}$. Let $x\oplus a = z = z_{u-1}z_{u-2}...z_1z_0$ in binary form. Then it is to $z_i \equiv x_i + a_i \pmod{2}$ so
\begin{align}
(x\oplus a)\odot u & = z\odot u \\
& \equiv \sum^{n-1}_{i=0} z_iu_i \pmod{2}\\
& \equiv \sum^{n-1}_{i=0} (x_i+a_i)u_i \pmod{2}\\
& \equiv \sum^{n-1}_{i=0} x_iu_i+\sum^{n-1}_{i=0}a_iu_i \pmod{2}\\
& \equiv x\odot u+ a\odot u \pmod{2}
\end{align} Q.e.d.
Using this result, we can rewrite the last equation for $R_1R_2$ to
\begin{align}
R_1R_2 &= \frac{1}{16}\sum_{x\in \mathcal{S}} \sum^{15}_{u=0}(-1)^{x\odot u}\left(1+(-1)^{a\odot u}\right)|u\rangle|f_{17,2}(x)\rangle
\end{align} Lets take a look at the term $(-1)^{x\odot u}(1+(-1)^{a\odot u})$, which defines the probability to measure a certain state $|u\rangle$. So this is
\begin{equation}
(-1)^{x\odot u}(1+(-1)^{a\odot u}) =
\begin{cases}
0, & \text{if }\sum^{n-1}_{i=0}a_iu_i \equiv 1\pmod{2}\\
(-1)^{x\odot u}2, & \text{if }\sum^{n-1}_{i=0}a_iu_i \equiv 0\pmod{2}\\
\end{cases}
\end{equation} But this means, that, if me measure the first register $R_1$, we will only see states (i.e. integers) $|u\rangle$ that have $\sum^{n-1}_{i=0}a_iu_i \equiv 0\pmod{2}$. And each of this states is measured with equal probability. Other states $|u\rangle$ can not be measured, since their probability to occur is zero.
If we repeat this $n$-times, we get $n$ different integers $u$, hence we get (probably) $n$ independent equations (if not, repeat this a few more times) of the form
\begin{align}
a \odot u^1 & = a_{n-1}u^1_{n-1} + a_{n-2}u^1_{n-2} + ... + a_1u^1_{1} + a_0u^1_0 \equiv 0 \pmod{2}\\
... & = ... \\
a \odot u^n & = a_{n-1}u^n_{n-1} + a_{n-2}u^n_{n-2} + ... + a_1u^n_{1} + a_0u^n_0 \equiv 0 \pmod{2}
\end{align} with known $u^i_j$ and only $n$ unkowns $a_i$. This equation system can be uniquely solved for these $a_i$ which are the bits of $a$.
Is it possible to cover more problems than Simon's problem with this approach? E.g., some variation of the definition. For example from $f(x) = f(x\oplus a)$ to e.g. $f(x) = f(x\;\text{AND}\;a)$ or $f(x) = f(x\;\text{OR}\;a)$? For the latter, the resulting probablity term is $$(-1)^{x\odot u}(1+(-1)^{a\odot u - x\odot a\odot u})$$ and the $x$ in the exponent $x\odot a\odot u$ is very annoying.
| Definition [Simon's problem] Let $f:\{0,1\}^n \rightarrow \{0,1\}^n$ with the property that for $x,y \in \{0,1\}^n$ it is $f(x) = f(y)$ if and only if $x = y \oplus a$, for some fix value $a \in \{0,1\}^n$. Given $f$, the task is to find $a$. |
As usual the $\oplus$ is the bitwise XOR-function. On a classical computer, Simon's problem can only be solved in time that is exponential in $n$, whereof on a QC already $\mathcal{O}(n)$ queries are enough.
Simon's problem can also be seen as some kind of period finding problem. Assume you have a function $f$ and for $f$ it holds that:
\begin{align}
f(1) &= e_1 \\
f(2) &= e_2 \\
... &\\
f(a-1) &= e_{a-1}\\
f(a) &= e_a = 1\\
f(a+1) &= f(1) = e_1\\
f(a+2) &= f(2) = e_2 \\
... &
\end{align}
A non-trivial function that behaves like this is, e.g., the function $f_{p,g}(x) = g^x \pmod{p}$, if $a$ is the order of $g$ in $\mathbb{F}^*_p$ and whenever $x \oplus a = x+a$. This is a very special setup and is almost always not fulfilled for random primes $p$. But, e.g., whenever $a = 2^t$ and $p-1=2^{t+1}$ this holds. For example $p=17$ and $g=2$. Then $f_{17,2}(x)$ has the described property and is a valid function according to Simon's problem definition.
I mention this here, because finding the order of a given integer $a \in \mathbb{Z}^*_n$ is exactly what Shor's quantum algorithm does and thus can be seen as a generalisation of this algorithm.
Where a classical computer is limited to execute the function $f$ for one integer after another, a QC does the following:
Assume that $n = 4$ and we take the function $f_{17,2}$. We prepare two quantum registers of $n=4$ bits, that are all initialized with $0$'s.
\begin{align}
R_1 &= \left(1\cdot |0\rangle + 0\cdot |1\rangle\right) \left(1\cdot |0\rangle + 0\cdot |1\rangle\right) \left(1\cdot |0\rangle + 0\cdot |1\rangle\right) \left(1\cdot |0\rangle + 0\cdot |1\rangle\right) \\
R_2 &= \left(1\cdot |0\rangle + 0\cdot |1\rangle\right) \left(1\cdot |0\rangle + 0\cdot |1\rangle\right) \left(1\cdot |0\rangle + 0\cdot |1\rangle\right) \left(1\cdot |0\rangle + 0\cdot |1\rangle\right) \\
\end{align} First, the Hadamard-Operation $\mathcal{R}_n$
\begin{equation}
\mathcal{R}_n: |x\rangle \mapsto \frac{1}{2^{n/2}}\sum^{2^n-1}_{u=0}(-1)^{x\odot u}|u\rangle
\end{equation}
is applied to the first register, which creates the uniform state, i.e., every integer from $0$ to $15$ is measured with the same probability of $1/16$. The operation $\odot$ is the following:
If the binary representation of $u$ and $x$ are $u_{n-1}u_{n-2}...u_1u_0$ and $x_{n-1}x_{n-2}...x_1x_0$ respectively, then $x\odot u = \sum^{n-1}_{i=0}u_ix_i $. So we can write $R_1$ as
\begin{align}
R_1 &= \\
& \left(\frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle\right) \left(\frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle\right) \left(\frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle\right) \left(\frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle\right)\end{align}
and written in another way (after using the distributive law) it is
\begin{align}
R_1 = &\frac{1}{4}|0000\rangle + \frac{1}{4}|0001\rangle + \frac{1}{4}|0010\rangle + \frac{1}{4}|0011\rangle\\
&\frac{1}{4}|0100\rangle + \frac{1}{4}|0101\rangle + \frac{1}{4}|0110\rangle + \frac{1}{4}|0111\rangle\\
&\frac{1}{4}1000\rangle + \frac{1}{4}|1001\rangle + \frac{1}{4}|1010\rangle + \frac{1}{4}1011\rangle\\
&\frac{1}{4}|1100\rangle + \frac{1}{4}|1101\rangle + \frac{1}{4}|1110\rangle + \frac{1}{4}|1111\rangle\\
= &\frac{1}{4}\sum^{15}_{x=0} |x\rangle
\end{align} So each value is measure with the probablity $(1/4)^2 = 1/16$. Then the function $f_{17,2}$ is applied, thereby entagling the first register $R_1$ with the $R_2$.
\begin{align}
R_2 = &\frac{1}{4}|f_{17,2}(0)\rangle + \frac{1}{4}|f_{17,2}(1)\rangle + \frac{1}{4}|f_{17,2}(2)\rangle + \frac{1}{4}|f_{17,2}(3)\rangle\\
&\frac{1}{4}|f_{17,2}(4)\rangle + \frac{1}{4}|f_{17,2}(5)\rangle + \frac{1}{4}|f_{17,2}(6)\rangle + \frac{1}{4}|f_{17,2}(7)\rangle\\
&\frac{1}{4}|f_{17,2}(8)\rangle + \frac{1}{4}|f_{17,2}(9)\rangle + \frac{1}{4}f_{17,2}(10)\rangle + \frac{1}{4}|f_{17,2}(11)\rangle\\
&\frac{1}{4}|f_{17,2}(12)\rangle + \frac{1}{4}|f_{17,2}(13)\rangle + \frac{1}{4}|f_{17,2}(14)\rangle + \frac{1}{4}|f_{17,2}(15)\rangle\\
= &\frac{1}{4}\sum^{15}_{x=0} |f_{17,2}(x)\rangle
\end{align} Writing this together in one equation is
\begin{equation}
R_1R_2 = \frac{1}{4}\sum^{15}_{x=0}|x\rangle|f_{17,2}(x)\rangle
\end{equation}
We next apply the Hadamard operations $\mathcal{R}_{4}$ to the first register $R_1$
\begin{align}
R_1R_2 &= \frac{1}{4}\sum^{15}_{x=0} \frac{1}{4}\sum^{15}_{u=0}(-1)^{x\odot u}|u\rangle|f_{17,2}(x)\rangle\\
&= \frac{1}{16}\sum^{15}_{x=0} \sum^{15}_{u=0}(-1)^{x\odot u}|u\rangle|f_{17,2}(x)\rangle
\end{align} If we define $\mathcal{S}$ to be the subset of $\{0,1,2,...,15\}$, that contains all integers that create distinct $f$ values (in our particular case $\mathcal{S}$ would be $\{0,1,...,7\}$ since $x \oplus a = x + a$) we can write
\begin{align}
R_1R_2 &= \frac{1}{16}\sum_{x\in \mathcal{S}} \sum^{15}_{u=0}\left((-1)^{x\odot u}+(-1)^{(x\oplus a) \odot u}\right)|u\rangle|f_{17,2}(x)\rangle
\end{align} and this is the only step were we used that $f(x) = f(x\oplus a)$. Furthermore, since the base element is $(-1)$ and thus we are actually working modulo $2$, for the $\odot$ operation and the $\oplus$ operation the following holds $$(-1)^{(x\oplus a) \odot u} = (-1)^{x\odot u}(-1)^{a\odot u}$$
Proof. We have to show that $(x\oplus a)\odot u \equiv x\odot u + a\odot u \pmod{2}$. Let $x\oplus a = z = z_{u-1}z_{u-2}...z_1z_0$ in binary form. Then it is to $z_i \equiv x_i + a_i \pmod{2}$ so
\begin{align}
(x\oplus a)\odot u & = z\odot u \\
& \equiv \sum^{n-1}_{i=0} z_iu_i \pmod{2}\\
& \equiv \sum^{n-1}_{i=0} (x_i+a_i)u_i \pmod{2}\\
& \equiv \sum^{n-1}_{i=0} x_iu_i+\sum^{n-1}_{i=0}a_iu_i \pmod{2}\\
& \equiv x\odot u+ a\odot u \pmod{2}
\end{align} Q.e.d.
Using this result, we can rewrite the last equation for $R_1R_2$ to
\begin{align}
R_1R_2 &= \frac{1}{16}\sum_{x\in \mathcal{S}} \sum^{15}_{u=0}(-1)^{x\odot u}\left(1+(-1)^{a\odot u}\right)|u\rangle|f_{17,2}(x)\rangle
\end{align} Lets take a look at the term $(-1)^{x\odot u}(1+(-1)^{a\odot u})$, which defines the probability to measure a certain state $|u\rangle$. So this is
\begin{equation}
(-1)^{x\odot u}(1+(-1)^{a\odot u}) =
\begin{cases}
0, & \text{if }\sum^{n-1}_{i=0}a_iu_i \equiv 1\pmod{2}\\
(-1)^{x\odot u}2, & \text{if }\sum^{n-1}_{i=0}a_iu_i \equiv 0\pmod{2}\\
\end{cases}
\end{equation} But this means, that, if me measure the first register $R_1$, we will only see states (i.e. integers) $|u\rangle$ that have $\sum^{n-1}_{i=0}a_iu_i \equiv 0\pmod{2}$. And each of this states is measured with equal probability. Other states $|u\rangle$ can not be measured, since their probability to occur is zero.
If we repeat this $n$-times, we get $n$ different integers $u$, hence we get (probably) $n$ independent equations (if not, repeat this a few more times) of the form
\begin{align}
a \odot u^1 & = a_{n-1}u^1_{n-1} + a_{n-2}u^1_{n-2} + ... + a_1u^1_{1} + a_0u^1_0 \equiv 0 \pmod{2}\\
... & = ... \\
a \odot u^n & = a_{n-1}u^n_{n-1} + a_{n-2}u^n_{n-2} + ... + a_1u^n_{1} + a_0u^n_0 \equiv 0 \pmod{2}
\end{align} with known $u^i_j$ and only $n$ unkowns $a_i$. This equation system can be uniquely solved for these $a_i$ which are the bits of $a$.
Is it possible to cover more problems than Simon's problem with this approach? E.g., some variation of the definition. For example from $f(x) = f(x\oplus a)$ to e.g. $f(x) = f(x\;\text{AND}\;a)$ or $f(x) = f(x\;\text{OR}\;a)$? For the latter, the resulting probablity term is $$(-1)^{x\odot u}(1+(-1)^{a\odot u - x\odot a\odot u})$$ and the $x$ in the exponent $x\odot a\odot u$ is very annoying.
Comments
Post a Comment