0
$\begingroup$

Suppose we have $g^x \equiv h \pmod N$ Where $N = pq$ and $p$, $q$ are distinct primes. Also $(p-1)/2$ and $(q-1)/2$ are primes.

If we know what $x$, $g$ and $h$ are, is it possible for us to know what $p$ and $q$ are? I'm trying to find out but I'm running into closed doors.
I tried the following:
$gcd(p-1 , q-1) = 2$
$g^{(p-1)(q-1)/2} \equiv 1 \pmod {pq}$
so $1 \equiv h^{(p-1)(q-1)/2} \pmod {pq}$

Any help is appreciated.

$\endgroup$
  • $\begingroup$ For the question "If we know what $x$, $g$ and $h$ are, is it possible for us to know what $p$ and $q$ are?", I doubt there is a positive answer $\;$ However another interesting question is: "If we knew a method to find $x$ such that $ g^x\equiv h\pmod N$ given $(g,h)$, would it be possible for us to know what $p$ and $q$ are?" $\endgroup$ – fgrieu Mar 5 '15 at 7:49
1
$\begingroup$

As a hint, suppose we pick a random $h$, and compute $g = h^3 \bmod N$. We then find the minimal value $x$ where $g^x \equiv h \pmod{N}$ (and, yes, such an $x$ will exist, assuming $p, q > 7$).

What can we deduce from such a value of $x$?

$\endgroup$
  • $\begingroup$ For this to work, $x$ must be $-3 \pmod {\phi (N)}$ right? $\endgroup$ – mike russel Mar 4 '15 at 14:41
  • $\begingroup$ @mikerussel: Actually, $3^{-1}$, not $-3$. $\endgroup$ – poncho Mar 4 '15 at 14:45
  • $\begingroup$ Okay so how does this help us retrieve $p$ and $q$? $\endgroup$ – mike russel Mar 4 '15 at 14:45
  • $\begingroup$ @mikerussel: What is $3x-1 \bmod {(p-1)(q-1)/2}$ with good probability? $\endgroup$ – poncho Mar 4 '15 at 14:59
  • $\begingroup$ We know $x = 3^{-1}$ so $3x-1= 0$ So $(p-1)(q-1)/2$ divides $3x-1$. $\endgroup$ – mike russel Mar 4 '15 at 15:02
0
$\begingroup$

Just knowing any such triple would not help at all. Reason:

Choose $g$ and $x$ arbitrarily, calculate $h$. Now you got such a triple, but it shouldn't help you factorize $N$, unless you have another interesting property.

If on the other hand you can somehow calculate roots (given $x$ and $h$, and then find $g$), then you can break RSA: Choose $x=e$, and your root algorithm finds the plaintext to a ciphertext.

If you can find square roots (and there are always 4 of them with $n=pq$), then you can actually factorize $N$, the attack basically works like the chosen ciphertext attack on Rabins encryption scheme: Choose $a$, calculate $a^2$, apply your algorithm to $a^2$ to find a square root. Since it only has $a^2$ as input, it will result in one of the four square roots, but not necessarily the one you started with. If the result is not $a$ or $-a$, then you can factorize $N$.

$\endgroup$

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.