Is this even possible? The RSA group is not cyclic, so usually you wouldn't find a generator for accessing all group elements. What happens if you use the RSA group in a scenario where you want that the discrete log problem is difficult. If you cannot find a generator, you want at least find an element with a high order, or?
$\begingroup$
$\endgroup$
6
-
4$\begingroup$ If you choose a SAFE rsa modulus (one written as (2p+1)(2q+1) with p,q,2p+1,2q+1 all primes) the order of the group is 4pq and is relatively easy to find elements of high order $\endgroup$– antosecretJan 24, 2013 at 19:50
-
$\begingroup$ Thanks for your answer. Maybe I am thinking to complicated but how can I find such elements and how can I be sure that they have maximum order? $\endgroup$– user4811Jan 24, 2013 at 20:22
-
2$\begingroup$ Choose a random element. Since its order must divide the group order, if it is not 2 or 4, then it must be as big as the smallest between p and q. However, I do not know about how difficult the discrete log is in such group $\endgroup$– antosecretJan 24, 2013 at 22:44
-
2$\begingroup$ Actually, you can make a stronger statement with these SAFE RSA modulii: if you pick a value $r$ where all three of $r, r-1, r+1$ are relatively prime to $n = (2p+1)(2q+1)$, then the order of $r$ will be at least $pq$. $\endgroup$– ponchoJan 24, 2013 at 23:23
-
$\begingroup$ @poncho And if you picked an $r$ (or $r+1$, $r-1$) which is not relative prime to $n$, you've got the factorization of $n$, don't you? $\endgroup$– Paŭlo EbermannJan 26, 2013 at 22:27
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
As for the question "how difficult would it be to solve a random instance of a discrete log problem modulo an RSA modulus", well, it turns out that we can give a fairly solid answer; which is essentially "about as difficult as factoring the modulus".
Here's is a demonstration that the discrete log problem is not drastically easier than factoring the modulus": if you have a procedure that solves a random instance of a DLOG problem in a composite modulus with nontrivial probability, then you have a procedure that factors that composite modulus with nontrivial probability".
This is a well-known observation; one way to arrive at that is "if you can compute DLOGs, you can compute (a multiple of) the order of a random element, and if you can do that, you can factor".
To compute this order using an Oracle that can compute random logs, you take your random element $r$, select a random exponent $k>1$ ($k$ needs to be relatively prime to $(p-1)(q-1)$, making it a large random prime works), and then query your DLOG oracle for discrete log $(r^k)^m = r$; once you know $m$, you also know that $r^{km-1} = 1$; that is, the order of $r$ is a divisor of $km-1$.
Once you have that multiple of an order $x = km-1$, you can then factor $n=pq$ by considering the odd value $y = x/2^j$, and then for random values of $s$ ($r$ works well for an initial guess), consider the sequence $(s^y, s^{2y}, s^{4y}, ..., s^{x})$. If we see a 1 in the sequence proceeded by a value $z$ other than 1 or $n-1$, then we can factor; the factors are $gcd(n, z-1)$ and $gcd(n, z+1)$. And, if $r$ was chosen randomly, then with high probability this procedure will find a factorization after a modest number of random $s$ values.
As for the demonstration that the discrete log problem is unlikely to be drastically harder than factoring the modulus, well, that's just the observation that the DLOG problem can be solved by factoring the modulus, and then solving the DLOG problem in the smaller groups modulo $p$ and $q$. As far as we know, solving the DLOG problem in those smaller groups is considerably easier than factoring, hence the factorization is the main effort.
What does this all mean? Well, it implies that it's actually safe to pick a random generator; if there is a nontrivial probability that the generator is weak, then there's a nontrivial probability that RSA is weak as well.
Now, does this mean that the extra effort that antosecret suggested is not worth while? Well, that's actually a matter of opinion; is it better to do a simpler method (with a provably tiny chance of failing); or is it better to do a more complex method (that avoids that specific failure mode)? Personally, I don't care for unnecessary complexity; you would need to make up your own mind.
