$k = N^a \mod P$

The attacker knows the prime $P$ and $N$, which is also a prime and

(1.) prime root of $P$ or
(2.) has a cycle size of $s$, so $1 = N^s \mod P$, (and for $\forall s'<s$, $1 < N^{s'} \mod P$

The attacker want to resolve variable $a$ with some discrete log. algorithm for a certain $k$.

About the $k$ he knows:

$k = M^b \mod P$

With $M \neq N$ but $M$ has same properties as case (1.) or case (2.) (same cycle size as $N$). For this equation he knows all variables $k,b,M,P$. Does the attacker help this knowledge about $k$ (in case (1.) or (2.)?

(3.) Somehow the attacker got knowledge of all variables ($a,b,N,M,P$) for one $k$. Does it help him to resolve $a'$ for other $k'$ (with same $N,M,P$), in case (1.)/(2.)?


side node:

The sets of generated $k$ values are equal for $N$,$M$ in case (2.):

$\{N^c, \forall c \in \mathbb{N}\}=\{M^d, \forall d \in \mathbb{N}\}=S$

with $|S|=s$. The numbers in it have just a different order. (In case (1.) $s=P-1$)

(4.)side question:

bottleneck of this would be the size of $s$, right? No matter how big $P$ is, it would not help security with same $s$.


Does the attacker help this knowledge about $k$ (in case (1.) or (2.)?

No; suppose you had an Oracle that could recover $a$ given $N, P, k, b, M$, then you could recover $a$ just given $N, P, k$ (that is, solve the Discrete Log problem). Because we believe that the Discrete Log problem (given appropriate choices for $N, P$) is hard, we can conclude that constructing such an Oracle is also hard.

Here is how we would use such an Oracle; we already have been given $N, P, k$, and so all we need to do is construct $b, M$. This can be done by selecting a $b$ relatively prime to $P-1$ and random otherwise; we can then compute $M = k^{b^{-1} \bmod P-1} \bmod P$; such a $b, M$ pair satisfies $k = M^b \mod P$, and so satisfies the Oracle's preconditions. We then supply $N, P, k, b, M$ to the Oracle, and recover $a$

A similar method can be constructed for your question (3)

  • $\begingroup$ @J.Doe: first part says "no"; second part gives the reason (if there was a way, then the standard discrete log problem is easy) $\endgroup$ – poncho Apr 26 '19 at 2:24
  • $\begingroup$ Edit of my 1st comment: Thanks for answer but not sure if I got this. First part says no but second part yes. First part uses Oracle which don't need $b,M$, second part computes $b,M$ for the Oracle ($b,M$ was already given)). You saying it would be possible in case some scientist find a fast way to compute discrete log? In my use case k gets computed always with $k=M^b \mod P$ which is known by a potential attacker all the time. He shouldn't know how to resolve $a$ for N with same $k$ out of this. $\endgroup$ – J. Doe Apr 26 '19 at 8:37
  • $\begingroup$ Thanks again poncho. But why a $b$ gets constructed if it is already given? $\endgroup$ – J. Doe Apr 26 '19 at 8:45
  • $\begingroup$ @J.Doe: we're showing "if your problem is easy, then the DLog problem is easy"; so we're showing how to solve the DLog problem (assuming that your problem is solvable). In an instance of a DLog problem, we're not given $b$ (instead, we're given $N, P, k$); the solver for your problem expects a value for $b$, hence we construct one. $\endgroup$ – poncho Apr 26 '19 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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