Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

As in the title, given $g$, $g^{ab}$ are big elements in a prime group $Z_p$ and $b$ in prime group $Z_r$ ($p > r$, $g$ is one generator of $Z_p$). $a$ is unknown and also in $Z_r$, is finding $g^a$ a hard problem?

update $a$, $b$ and $ab$ are group elements of $Z_r$..

share|improve this question
    
By "in group $\mathbb Z_r$" are you meaning $a$ and $b$ are in $\mathbb N$ and less than $r$, or that $a\cdot b$ is computed in that group? –  fgrieu Jul 17 at 13:45
1  
@fgrieu $a$ and $b$ are group elements of $Z_r$, and $a.b$ should be computed in that group. –  Loi.Luu Jul 17 at 13:59
    
@fgrieu its just a mathematics group, am I having something confusing here? en.wikipedia.org/wiki/Group_(mathematics) –  Loi.Luu Jul 17 at 14:48
4  
Probably $r$ is the order of $g$ in $\mathbf{Z}_p^*$, otherwise it makes no sense that the exponents should be in $\mathbf{Z}_r$... –  fkraiem Jul 17 at 14:49
4  
@Loi.Luu I'm sorry but no, unless $r$ is the order of $g$ in $\mathbf{Z}_p^*$ or a multiple thereof, the exponents being in $\mathbf{Z}_r$ makes no sense, because you could have $a = b$ in $\mathbf{Z}_r$ but $g^a \ne g^b$ in $\mathbf{Z}_p^*$. –  fkraiem Jul 17 at 14:57

2 Answers 2

up vote 3 down vote accepted

The question as currently worded, and considering comments by its author, would boil down to: is it a hard problem finding $g^a\bmod p$, given

  • large prime $p$
  • large integer $g$ less than $p$ that is a generator of $\mathbb Z_p$ [see note 1]
  • prime $r$ less than $p$
  • knowledge that unknown $a$ is a positive integer less than $r$
  • positive integer $b$ less than $r$
  • $g^{a\cdot b\bmod r}\bmod p$ [see note 2]

Note 1: We can safely assume I have assumed this means $g$ is a generator of the multiplicative group $\mathbb Z_p^*$ of $\mathbb Z_p$; that is, the application $x\to g^x\bmod p$ is a mapping over the set of positive integers less than $p$; this can be efficiently tested when the factorization of $p-1$ is known, by checking $g^{(p-1)/q}\bmod p\;\ne1$ for every prime $q$ dividing $p-1$.

Note 2: The statement uses the notation $g^{ab}$, with the indication that $g$ is in prime group $\mathbb Z_p$ [which we can safely assume is the multiplicative group $\mathbb Z_p^*$], meaning that element $g^{ab}$ of $\mathbb Z_p$ is given as the integer $g^{ab}\bmod p$; and the indication that $a$ and $b$ are in prime group $\mathbb Z_r$, with comment that $ab$ is computed in $\mathbb Z_r$ [which I similarly assume is the multiplicative group $\mathbb Z_r^*$], and comment suggesting that an element of $\mathbb Z_r$ is assimilated to a non-negative integer less than $r$; hence my interpretation that the given stated as $g^{ab}$ really is $g^{a\cdot b\bmod r}\bmod p$.

We can NOT guess/hope/assume that $g^r\bmod p\;=1$ [including that $r=p-1$, the order of $g$], because that would contradict the givens that $p$ and $r$ are primes [see comment] with $p$ large and larger than $r$, and $g$ is a generator. Thus $g^{a\cdot b}\bmod p$ with $a\cdot b$ obtained by integer multiplication has no reason to be $g^{a\cdot b\bmod r}\bmod p$, and typically is not.

Right now I do not see how to solve that problem in the general case, or even count its solutions. That's far fetched from a justification of my impression that it might be a hard problem for some parameters.

If we knew $g^{a\cdot b}\bmod p$ [rather than $g^{a\cdot b\bmod r}\bmod p$, as I assume we do], we could ignore the given $r$ and often solve the problem by the method outlined in that other answer, since that method works when $\gcd(b,p-1)=1$. Depending on $p$ that might be common, or not; e.g. for the prime $p=$1719620105458406433483340568317543019584575635895742560438771105058321655238562613083979651479555788009994557822024565226932906295208262756822275663694111, $\gcd(b,p-1)=1$ when $b$ has no divisor less than 383, and that occurs for few $b$.


Update: it is now asked in comment if we could compute $c=b^{−1}$ in $\mathbb Z_r$, and then compute $(g^{ab})^c$ to get $g^a$. This suggests something is wrong in my interpretation of the statement above, despite the answer being accepted.

That method won't work for most primes $r$ less than $p$ and most pairs $(a,b)$, no matter if $ab$ is computed in $\mathbb Z_r$ or in $\mathbb N$.

That does work if $g^r\bmod p\;=1$ and $\gcd(b,r)=1$, for either way to compute $ab$ (which become equivalent). However, if we trust the given that $g$ is a generator, the only $r$ less than $p$ with $g^r\bmod p\;=1$ is $r=p-1$. And [using that $p$ is huge], such $r=p-1$ is not prime, contrary to $r$ prime suggested by the statement and confirmed in comment. Also that won't works with $b$ even, or otherwise not co-prime with $p-1$.

Illustrations with small values $p=23$, $g=19$ [which matches the condition that $g$ is a generator], $r=17$ unless otherwise stated, $a=8$, and $b=6$ :

  • with multiplication in $\mathbb Z_r$: $ab=14$, $g^{ab}=18$, $c=3$, $(g^{ab})^c=13$, not matching $g^a=9$

  • with multiplication in $\mathbb N$: $ab=48$, $g^{ab}=3$, $c=3$, $(g^{ab})^c=4$, not matching $g^a=9$

  • replacing $r$ with $p-1=22$: $ab=14$ or $48$, $g^{ab}=18$ [either way], $c$ can not be computed.


My final(?) guess of the intended statement is that $g$ is NOT a generator, contrary to the question as currently worded, but rather that

$g$ is an element of prime order $r$ in the multiplicative group $\mathbb Z_p^*$

Notice how this creates a condition linking $r$ to $p$ (and $g$), absent from the question's wording! With that novelty, it holds that $g^r\bmod p\;=1$, therefore it does not matter if $g^{ab}$ is computed with the product ${ab}$ in $\mathbb Z_r$ or in $\mathbb N$. It also holds that $\gcd(b,r)=1$ [since $r$ is prime], thus the method in the recent comment always work, and the answer is NO.

We could illustrate this with $p=23$, $g=13$ [which is not a generator since $g^{11}\bmod p\;=1$], $r=11$ [which is prime], $a=8$, and $b=6$ :

  • $ab=14$ or $48$, $g^{ab}=18$ [either way], $c=2$, $(g^{ab})^c=2$, matching $g^a=2$.
share|improve this answer
1  
Is this true if we compute $c = b^-1$ in $Z_r$ and then compute ${g^{ab}}^c$ to get $g^a$? –  Loi.Luu Jul 18 at 3:13

Not at all. It's very trivial: $$(g^{ab})^{b^{-1}}=g^a$$

share|improve this answer
2  
In what group is $b^{-1}$ computed? –  mikeazo Jul 17 at 13:24
    
I guess in $\mathbb{Z}_p$ after finding it's inverse –  curious Jul 17 at 13:27
    
@curious Sorry, but is it gonna work in $Z_p$? –  Loi.Luu Jul 17 at 13:40
4  
@curious: I can't parse what "it's" refers to in your previous comment. Rather, my bets are on the inverse $\pmod{p-1}$ –  fgrieu Jul 17 at 13:41
1  
@curious p is known, and r is known also. –  Loi.Luu Jul 17 at 13:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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