1
$\begingroup$

$g^{ab} \pmod{p} = B^a \pmod{p}$ where all variables are known except $a$. In this case, I have an equivalent value for $a'*b'$, but this is not the same as the real values of $a*b$ due to the modulus.

Everything else including the generator, the prime, $B$ public, the shared secret (or value of both sides of the equation) are known.

Since $p$ is a 90-bit value, this is would be difficult to calculate, but if there is some $\mathcal{O}(\sqrt{n})$ optimization, this may put it on the edge of the possibility to brute force.

$\endgroup$
2
  • 2
    $\begingroup$ 90-bit is too easy even for ECDH. $\endgroup$
    – DannyNiu
    Oct 10, 2020 at 1:40
  • $\begingroup$ Looks like a challenge from a competition.. $\endgroup$
    – Fractalice
    Oct 10, 2020 at 11:49

1 Answer 1

2
$\begingroup$

Yes, this is totally feasible. Unless $p$ is purposely chosen as a safe prime, there's a good chance that's easy.

Computing $a$ given $B$, $p$, and $C=B^a\bmod p$ is a Discrete Logarithm Problem in the multiplicative group modulo prime¹ $p$, of order $r=p-1$.

For any DLP problem, there is a generic attack of cost a few times $\sqrt r$ group operations, Pollard's rho. Not only is $2^{\approx45}$ multiplications modulo 90-bit $p$ feasible, but that can be efficiently distributed on independent machines, see Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, 1999, following their article in proceedings of CCS 1994).

Also, there is the generic Pohlig-Hellman DLP method, which can help if $r$ is of known factorization.Here for we can factor the 89-bit $r/2$ in a breeze. The main DLP reduces to a few easier DLPs in groups of smaller prime order. These can be solved by Baby-step/Giant-step for small ones, or Pollard's rho and it's distributed variant for large ones. A typical factorization of $r$ has a largest prime factor $q$ of multiplicity 1 and much larger than other primes dividing $r$, so that the work is dominated by $\sqrt q$ group operations. Here, it is not told if $p$ was chosen such that $q=r/2$ is prime (which would make Pohlig-Hellman pointless), thus there is a fair chance that $q$ is sizably less than 89-bit, easing attack greatly.

There are even more efficient methods in the case of the multiplicative group $\mathbb Z_p^*$ that we target:


¹ The question's mention of Diffie-Hellman key exchange suggests $p$ is prime. If not, we can factor $p$ into $\prod{p_i}^{\alpha_i}$, solve for $a_i$ the problems $B^{a_i}\equiv C\pmod{{p_i}^{\alpha_i}}$, then use the Chinese Remainder Theorem modulo the ${p_i}^{\alpha_i-1}\,(p_i-1)$ to find a solution $a$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.