2
$\begingroup$

On the group of multiplication modulo large prime $p$ of $m$ bits

Given $$ b_1^k=g_1 \;\text {mod}\;p$$ $$ b_2^k=g_2 \;\text{mod}\;p$$ $$ b_3^k=g_3 \;\text{mod}\;p$$ $$ \vdots $$ $$ b_n^k=g_n \;\text{mod}\;p$$

How many pairs are enough to computationally solve $k$ of this discrete logarithm problem? I have this question because if we erroneously use the random number generator in Elgamal encryption The masking key may have relation, e.g. the masking key is the square of previous one modulo $p$. We can decrypt the ciphertext easily, but we may still not know the private key of Bob (the receiver.), but we can know many pairs of relation like equations above. Are the pairs let we solve the private key of Bob(receiver)?

$\endgroup$
4
  • 1
    $\begingroup$ This looks like a small subgroup confinement attack. If you know $k = k_1 \mod r_1, k=k_2 \mod r_2, ... , k = k_n \mod r_n$, then by the Chinese remainder theorem, you need enough $r_i$ such that $\prod r_i > q$, the order of your finite group. But the fact that you have the same $k$ each time makes me think this isn't applicable. $\endgroup$
    – user47922
    Jun 7, 2017 at 2:04
  • $\begingroup$ In other words, if you know $b_1^{k_1} = g_1 \mod r_1, b_2^{k_2} = g_2 \mod r_2, ...$, where the $r_i$ are factors of $q-1$ where $q$ is the order of the group, I can compute $k$ from the $k_i$ and $r_i$. Is that what you're asking? $\endgroup$
    – user47922
    Jun 7, 2017 at 2:10
  • $\begingroup$ This is not what I am asking. Anyway, thank you for additional information. $\endgroup$
    – Rikeijin
    Jun 7, 2017 at 2:11
  • $\begingroup$ Okay, got it! :) $\endgroup$
    – user47922
    Jun 7, 2017 at 2:12

1 Answer 1

6
$\begingroup$

Having multiple sets $b_i^k = g_i$ with a common solution $k$ do not help you recover $k$; it cannot make the problem much easier than if you had the simple equation $b^k = g$.

Here's the proof; suppose that there was an efficient way to recover $k$ given a $n$ different $b_i^k = g_i$ equations.

Then, we can efficiently solve the simple equation $b^k = g$ by doing the following:

  • We select $n$ random values $r_1, ..., r_n$

  • We compute:

$$b_i = b^{r_i}$$

$$g_i = g^{r_i}$$

  • We have our $n$ equations, as $b_i^k = (b^{r_i})^k = (b^k)^{r_i} = g^{r_i} = g_i$, so we use the efficient way to recover $k$ given $n$ equations.

We then know the solution $k$ to the original equation, and the only extra time we took was to the time select $n$ random values and to compute $2n$ modular exponentiations.

$\endgroup$

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.