<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#ffffff" text="#000000">
On 1/19/2011 4:41 AM, Legrandin wrote:
<blockquote
cite="mid:AANLkTi=+2NpC_rRbT4kG9rvhiROZ9q2LAWcUvrShtC0Z@mail.gmail.com"
type="cite">
<pre wrap="">Hi all,
I have noticed that - when generating an RSA key - a special check is
made to ensure that p<q.
</pre>
</blockquote>
That's interesting. This is what I found, which seems to suggest the
exact opposite:<br>
<br>
>><br>
To generate the primes <var>p</var> and <var>q</var>, generate a
random number of bit length b/2 where
<var>b</var> is the required bit length of <var>n</var>; set the
low bit (this ensures the number is odd) and set the <em>two</em>
highest bits (this ensures that the high bit of <var>n</var> is
also set); check if prime (use the <dfn>Rabin-Miller</dfn> test);
if not, increment the number
by two and check again until you find a prime. This is <var>p</var>.
Repeat for <var>q</var> starting with a random integer of length
b-b/2.
If p<q, swap <var>p</var> and <var>q</var> (this only matters
if you intend using the CRT form of the private key).
In the extremely unlikely event that p = q, check your random number
generator. Alternatively, instead of incrementing by 2, just
generate another random number each time.
<p>
There are stricter rules in <a
href="http://www.di-mgt.com.au/rsa_alg.html#x931">ANSI X9.31</a>
to produce <dfn>strong primes</dfn>
and other restrictions on <var>p</var> and <var>q</var> to
minimize the possibility of known techniques being
used against the algorithm. There is much argument about this
topic. It is probably better just to use a longer key length.<br>
>><br>
</p>
Taken from <a class="moz-txt-link-freetext" href="http://www.di-mgt.com.au/rsa_alg.html">http://www.di-mgt.com.au/rsa_alg.html</a><br>
<br>
That snippet suggests that p>q is desired if using the CRT form
of the private key. And we seem to be doing the exact opposite,
swapping p and q if p>q.<br>
<br>
<br>
</body>
</html>