blob: 97ae97ce76acf0f4dfb77d6251f7f7fa6d4c4778 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
<tt>
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"><br>
<html><br>
<head><br>
<meta content="text/html; charset=ISO-8859-1"<br>
http-equiv="Content-Type"><br>
</head><br>
<body bgcolor="#ffffff" text="#000000"><br>
On 1/19/2011 4:41 AM, Legrandin wrote:<br>
<blockquote<br>
cite="mid:AANLkTi=+2NpC_rRbT4kG9rvhiROZ9q2LAWcUvrShtC0Z@mail.gmail.com"<br>
type="cite"><br>
<pre wrap="">Hi all,<br>
<br>
I have noticed that - when generating an RSA key - a special check is<br>
made to ensure that p&lt;q.<br>
</pre><br>
</blockquote><br>
That's interesting. This is what I found, which seems to suggest the<br>
exact opposite:<br><br>
<br><br>
&gt;&gt;<br><br>
To generate the primes <var>p</var> and <var>q</var>, generate a<br>
random number of bit length b/2 where<br>
<var>b</var> is the required bit length of <var>n</var>; set the<br>
low bit (this ensures the number is odd) and set the <em>two</em><br>
highest bits (this ensures that the high bit of <var>n</var> is<br>
also set); check if prime (use the <dfn>Rabin-Miller</dfn> test);<br>
if not, increment the number<br>
by two and check again until you find a prime. This is <var>p</var>.<br>
Repeat for <var>q</var> starting with a random integer of length<br>
b-b/2.<br>
If p&lt;q, swap <var>p</var> and <var>q</var> (this only matters<br>
if you intend using the CRT form of the private key).<br>
In the extremely unlikely event that p = q, check your random number<br>
generator. Alternatively, instead of incrementing by 2, just<br>
generate another random number each time.<br>
<p><br>
There are stricter rules in <a<br>
href="http://www.di-mgt.com.au/rsa_alg.html#x931">ANSI X9.31</a><br>
to produce <dfn>strong primes</dfn><br>
and other restrictions on <var>p</var> and <var>q</var> to<br>
minimize the possibility of known techniques being<br>
used against the algorithm. There is much argument about this<br>
topic. It is probably better just to use a longer key length.<br><br>
&gt;&gt;<br><br>
</p><br>
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>
<br><br>
That snippet suggests that p&gt;q is desired if using the CRT form<br>
of the private key. And we seem to be doing the exact opposite,<br>
swapping p and q if p&gt;q.<br><br>
<br><br>
<br><br>
</body><br>
</html><br>
</tt>
|