1
$\begingroup$

Let's say I have

$p, g$ - known constant, $p$ is prime number, $g$ is composite.

$x$ - unknown random number, $2 < x < p - 1$

$k$ - my input

$S = k^x \bmod p$

$1 < S < p-1$

So, what $k$ should I use to make $S$ predictable? I mean, I want to know exactly what is $S$ equal to.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Why did you define $g$, is it a generator and $S=g^k$? $\endgroup$
    – kelalaka
    Commented Jun 1, 2021 at 19:29
  • 1
    $\begingroup$ Hint: your first step is to find small to moderates factors of $(p-1)/2$. On second thought, $g$ will help, though you certainly can do without. $\endgroup$
    – fgrieu ♦
    Commented Jun 1, 2021 at 19:32
  • $\begingroup$ $g$ can be used for guessing $S$, but is not used anywhere in calculations. $\endgroup$
    – Krasnopolskiy
    Commented Jun 1, 2021 at 19:32
  • $\begingroup$ $(p - 1) / 2$ has only two factors, but I don't know what to do next $\endgroup$
    – Krasnopolskiy
    Commented Jun 1, 2021 at 19:35
  • $\begingroup$ If $(p-1)/2$ is prime, well, there's no much you can do; any way of reducing the possible number of values of $S$ would depend on a small factor of $p-1$, and if $k=1$ and $k=p-1$ (which uses the factor 2) are not available, you're stuck. $\endgroup$
    – poncho
    Commented Jun 1, 2021 at 19:37

1 Answer 1

Reset to default
2
$\begingroup$

If $p-1$ has a factor of 348419, then you could reduce the number of possible values of $S$ to 348418 (or 1, which you said was not allowed).

One way to do this would be to pick a random value $r$, and compute $k = r^{(p-1)/348419} \bmod p$; if $k$ is something other than 1, then that's your value; the eventual $S$ value will be $k^x \bmod p$ for some $1 \le x < 348419$.

For this particular $p$ (and the constraints you have listed), that's the best you can do.

Improve this answer
$\endgroup$
3
  • $\begingroup$ It worked (I used $r=2$), thank you very much $\endgroup$
    – Krasnopolskiy
    Commented Jun 2, 2021 at 13:30
  • $\begingroup$ Yes, this is the way and a nice addition that the probability of a random value will not be 1 is $(p-1)/348418$, right? $\endgroup$
    – kelalaka
    Commented Jun 2, 2021 at 19:32
  • $\begingroup$ @kelalaka: actually, the probability that it's not 1 is $1 - 1/348419$ $\endgroup$
    – poncho
    Commented Jun 2, 2021 at 19:35

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.