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 ...
Number theory has many functions that are based on the arithmetical properties of a given input integer $n$. These functions are called number-theoretic functions. Well known examples are, e.g., the Euler's Totient Function and The Möbius Function. Since arithmetical properties often depend in one or the other way on the integer's prime factorization, these functions are usually hard to compute for large integers due to the factorization problem. One of these functions, that heavily depends on that factorization, is the Divisor Function.
Definition: Divisor Function
Given an integer $n$ then the divisor function $\sigma_k(n)$ is defined as $$ \sigma_k(n) := \sum_{d|n}d^k$$
If you set $k=0$, $\sigma_0(n)$ is equal to the number of divisors of an integer. For $k=1$ you get that $\sigma_1(n)$ is equal to the sum of all divisors of $n$. E.g. $\sigma_1(15) = 1 + 3 + 5 + 15 = 24$.
In order to compute this function one obviously needs to know the prime factors of $n$. Surprisingly, this function can be defined recursively, as proved by Leonard Euler
Definition: Divisor Function - recursive (Informal)
Given an integer $n$ then the divisor function $\sigma_1(n)$ [sum of divisors] can be defined as $$\small{ \sigma_1(n) = \sigma_1(n-1)+\sigma_1(n-2)-\sigma_1(n-5)-\sigma_1(n-7)+\sigma_1(n-12)+\sigma_1(n-15)-... }$$ If the input gets negative you stop. If the input gets zero, then $\sigma_1(0) = n$
The integers that are subtracted, i.e., $1,2,5,7,12,15,...$ are the generalized pentagonal numbers. They are defined as
$$ p(i) = \frac{3i^2-i}{2}$$ and the terms in the recursion are obtained by entering the values $0, -1, 1, -2, 2, -3, 3, ...$. One could write the recursion as $$\sigma_1(n) = \sum^{b_1}_{i=1} (-1)^{i+1}\sigma_1(n-p(i)) + \sum^{b_2}_{i=1} (-1)^{i+1}\sigma_1(n-p(-i))$$, whereof $b_1$ is the unique integer such that $n-p(b_1+1) < 0 \leq n-p(b_1)$ and $n-p(-(b_2+1)) \leq 0 < n-p(-b_2)$. Note, that these are efficiently computable, via solving a simple quadratic equation. Furthermore, as long as $n = d_1d_2$ and $d_1$ and $d_2$ are co-prime divisors we have $$\sigma_1(n) = \sigma_1(d_1d_2) = \sigma_1(d_1)\sigma_1(d_2)$$
If $n = pq$ with $p,q$ primes, the information $$\sigma_1(n) = 1 + p + q + n = (p+1)(q+1)$$ is already enough to factor $n$. It is $$\varphi(n) = (p-1)(q-1) = pq-p-q+1$$ hence, $$\varphi(n)+2(p+q) = \sigma_1(n)$$ From the point of view of a cryptographer, it seems a little bit strange, that one compute a function that reveals the factors of a certain integer $n$, only by the means of smaller integers, which might be easier to factorize. However, the total number of smaller integers that need to be factorized in this case is sufficiently large. So a direct approach to compute $\sigma_1(n)$ via that recursion is negligible. But are there any other valueable information that can be deduced from this recursion formula?
The value of $\sigma_1(n)$ is clearly always positive. The recursion, which is an alternating sum, must pick exactly those integers, that the final value is positive. If you, for example, pick $n = 35 = 5\cdot 7$, then you have
\begin{align*}
\small{\sigma_1(35)} = & \small{\sigma_1(34)+\sigma_1(33)-\sigma_1(30)-\sigma_1(28)+\sigma_1(23)+\sigma_1(20)-\sigma_1(13)-\sigma_1(9)+\sigma_1(0)}\\
= & \small{54 + 48 - 72 - 56 + 24 + 42 - 14 - 13 + 35 }\\
= & \small{48}
\end{align*}
\small{\sigma_1(35)} = & \small{\sigma_1(34)+\sigma_1(33)-\sigma_1(30)-\sigma_1(28)+\sigma_1(23)+\sigma_1(20)-\sigma_1(13)-\sigma_1(9)+\sigma_1(0)}\\
= & \small{54 + 48 - 72 - 56 + 24 + 42 - 14 - 13 + 35 }\\
= & \small{48}
\end{align*}
Although the final result is positive, several partial sums are negative — illustrating how delicately the recursion balances its terms. Euler’s recursion does not give a practical way to compute $\sigma_1(n)$ for large $n$, but it reveals a remarkable structural fact: arithmetic information that seems to require factorization can sometimes be encoded entirely through additive relations among smaller integers. Understanding why this works remains as interesting as the formula itself.
Comments
Post a Comment