3
$\begingroup$

Say you have an integer that is produced by multiplying two random numbers

$$x_1 = a \cdot b_1 \bmod(p-1)$$ where $a$ and $b_1$ are relatively prime to $p-1$ and $p$ being a large prime.

Knowing $x_1$ leaves you with $p-1$ pairs of numbers for $a$ and $b_1$, so guessing the correct factorization is hard (right?).

Do you get any advantage in finding the correct pair if you get more $x_i$ where one of the factors is re-used? E.g.: $$x_2 = a \cdot b_2 \bmod(p-1)$$

$\endgroup$
  • $\begingroup$ This is about the same problem as recovering the private key from DSA signatures: You always have at least one more unknown variable than equations. $\endgroup$ – SEJPM Dec 17 '16 at 13:25
  • $\begingroup$ With a single pair, you have many possible solution, but the set of valid solutions is easy to compute, it cannot be seen as a hard problem. With two equations, you get the common factor by computing a gcd, and recovering the remaining factors takes one inversion and two modular multiplications then. $\endgroup$ – Geoffroy Couteau Dec 17 '16 at 14:02
  • $\begingroup$ Knowing $x_1$ really leaves you with $\varphi(p−1)$ possible pairs of numbers, where $\varphi$ is the Euler totient function. Hint: show that for any fixed $a\in\mathbb Z_{p-1}^*$ (the subset of $\mathbb Z_{p-1}$ wich elements are coprime with $p-1$), the function $b_j\to x_j$ is a permutation of $\mathbb Z_{p-1}^*$; conclude. $\endgroup$ – fgrieu Dec 17 '16 at 17:49
  • $\begingroup$ @fgrieu: Could you elaborate on your comment? What does it mean that every $b_j \rightarrow x_j$ is a permutation for my question? Does it help you find $a$? $\endgroup$ – ChaosCoder Dec 18 '16 at 12:58
  • $\begingroup$ @ChaosCoder, Hint: do you learn anything about a permutation when given the images $x_j$ of unknown random elements $b_j$ by this permutation? $\endgroup$ – fgrieu Dec 19 '16 at 8:12
3
$\begingroup$

The question performs arithmetic in ${\mathbb Z_{p-1}}^*$, the integers reduced modulo $p-1$ that are coprime with this modulus. There are $\varphi(p-1)$ of these, where $\varphi$ is the Euler totient function. It is irrelevant that $p$ is prime, and the question has little to do with integer factorization.

For any $a\in{\mathbb Z_{p-1}}^*$, the application $\scr F_a:{\mathbb Z_{p-1}}^*\to{\mathbb Z_{p-1}}^*$, $b\to x=a\cdot b\bmod(p-1)$ is a permutation of ${\mathbb Z_{p-1}}^*$ (since $a$ has a multiplicative inverse). If follows that if $b$ is uniformly random on the set ${\mathbb Z_{p-1}}^*$, then $x$ is.

Therefore, no information is learned about $\scr F_a$, thus about $a$, from any number of $x_j$ disclosed without the corresponding $b_j$ (assumed independent and uniformly random on ${\mathbb Z_{p-1}}^*$), regardless of the size of parameters or computing power of adversary.

$\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.