2
$\begingroup$

I have done some research about how the DH key exchange is unsafe if an unsafe prime p is used (that is, $p-1$ has a lot of small factors). Many answers here on StackExchange claim that for any factor $r$ where $g^{\frac{p-1}{r}}\neq1$, if given $g$ and $g^x \bmod p$, one can determine the value of $x \bmod r$ in $O(\sqrt{r})$ time (See this and this answer).

The latter of the two answers even includes an outline of a way to do this. However, this requires $A^{\frac{p-1}{r}}$ with $A$ being the public key to be calculated. For a large $A$ and $p$ (say 4096 bits for both) and a small $r$ (8 bits or less), for me this does not seem to be computationally possible. Therefore, I was wondering how one would write a solution to this problem which is possible to execute with finite time and memory.

Improve this question
$\endgroup$
1
  • $\begingroup$ By definition if p is prime then all p-1 have a small factor (2) ,) $\endgroup$
    – eckes
    Nov 12, 2017 at 6:26

1 Answer 1

Reset to default
4
$\begingroup$

For a large $A$ and $p$ (say 4096 bits for both) and a small $r$ (8 bits or less), for me this does not seem to be computationally possible.

Actually, it's straightforward to compute $A^{\frac{p-1}{r}} \bmod p$; one straightforward way is to use the binary exponentiation algorithm.

If $\frac{p-1}{r} < 2^n$, then this will take no more than $2n$ modular multiplications (and so, in your example, fewer than 8184 modular multiplications); one could do somewhat better, but this is good enough to show that it is practical.

Note: you use those same algorithms to make the computations within DH (computing $g^x \bmod p$ for large $x$) feasible.

Note on the notation (which might be what is confusing you): sometimes, we leave off the $\bmod p$; at those times, we assume that the reader will understand that we are not working in $\mathbb{Z}$, but instead in the field $\mathbb{Z}/p$, and hence the $\bmod p$ operations are implicit. This is similar to how, in other branches of math, you are assumed to know whether we're working in $\mathbb{Z}$ or $\mathbb{R}$ or $\mathbb{C}$...

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thank you very much, this cleared up almost all my questions. However, there is one more thing I am unsure of: if A^(p-1)/r mod p equals 1, then there is no k which would fulfill the equation. What would one do in this case? $\endgroup$
    – Lukor
    Nov 9, 2017 at 22:22
  • $\begingroup$ @Lukor: actually, every $k$ would fulfull the equation, as both sides evaluate to one (assuming the original DLog problem had a solution), and so you get $1^k = 1$. Anyways, in that case, you can't deduce anything; the size of the subgroup that $A$ generates does not have $r$ as a factor; you're out of luck; that is, it would appear that whoever picked $A$ knew what they were doing... $\endgroup$
    – poncho
    Nov 9, 2017 at 22:28
  • $\begingroup$ in the example I'm working on, there is a factor r for which the left side A^(...) evaluates to one while the right side g^(...) does not. Can there be a reason for that or is that just a mistake in my code? $\endgroup$
    – Lukor
    Nov 9, 2017 at 22:32
  • $\begingroup$ @Lukor: you're working on the discrete log problem $g^k = A$? If so, then it's easy; $k = 0 \bmod r$. $\endgroup$
    – poncho
    Nov 9, 2017 at 22:59
  • $\begingroup$ okay, I probably have a really simple mistake here, but my situation is this: A mod p is some big number, g is a generator with order p-1, A^(q/r) mod p is 1, g^(q/r) mod p is some other large number $\endgroup$
    – Lukor
    Nov 9, 2017 at 23:03

Your Answer

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

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