Cryptography Reference
In-Depth Information
F.4 Generation of Random Primes
When we talked about SRP on page 200, we discussed safe primes,
p
, those
for which (
p
−
1)
/
2 is also prime. Safe primes are also important in selecting
an RSA modulus
n
=
pq
since, if
p
and
q
are safe primes, then RSA is not
vulnerable to
p
1 and
p
+ 1 factoring methods discussed in Section C.3 (see
page 514). In general, having safe primes in the modulus makes it more diGcult
to factor. However, finding such primes is also more diGcult. We present the
following algorithm for so doing, which is taken from [170].
−
Algorithm for Generating (Probable) Safe Primes
Let
b
be the input bitlength of the required prime. Execute the following
steps.
(1) Select a (
b
−
1)-bit odd random
n
∈
N
and a smoothness bound
B
(deter-
mined experimentally).
(2) Trial divide
n
by primes
p
B
.If
n
is divisible by any such
p
, go to step
(1). Otherwise, go to step (3).
≤
(3) Use the Miller-Selfridge-Rabin test on page 552 to test
n
for primality. If
it declares that “
n
is probably prime”, then go to step (4). Otherwise, go
to step (1).
(4)
Compute 2
n
+1 =
q
and use the Miller-Selfridge-Rabin test on
q
.Ifit
declares
q
to be a probable prime, terminate the algorithm with
q
as a
“probable safe prime”. Otherwise go to step (1).
There are primes that have even more constraints to ensure security of the
RSA modulus. They are given as follows.
Definition F.1
(
Strong Primes
)
A prime
p
is called a
strong prime
if each of the following hold.
(1)
p
−
1
has a large prime factor
q
.
(2)
p
+1
has a large prime factor
r
.
(3)
q
−
1
has a large prime factor
s
.
The following algorithm was initiated in [113].
Gordon's Algorithm for Generating (Probable) Strong Primes
(1)
Generate two large (probable) primes
r
=
s
of roughly equal bitlength
using the Miller-Selfridge-Rabin test.
(2) Select the first prime in the sequence
{
2
js
+1
}
j
∈
N
, and let
q
=2
js
+1
be that prime.
Search WWH ::
Custom Search