Cryptography Reference
In-Depth Information
2
r
−
1
s
mod
rs
,where
r
−
1
is the
x
≡−
1mod
s
, by setting
x
0
:= 1
−
multiplicative inverse of
r
modulo
s
.
3.
For our prime number search we use an odd initial value: We generate
a random number
z
with a number of digits close to but less than
(sometimes denoted by
) the desired length of
p
, and set
x
0
←
x
0
+
z
+
rs
x
0
+
rs
.With
x
0
in hand we begin our determination of
p
. We test the values
p
=
x
0
+
k ·
2
rs
,
k
=0
,
1
,...
, until the desired number of digits
p
for
p
is reached and
p
is prime. If an RSA key is to contain a specified public exponent
e
, then it
is worthwhile to ensure additionally that
gcd(
p −
1
,e
)=1
. The above
conditions on
p
have now been completely fulfilled. For the prime number
tests we use the Miller-Rabin test implemented in the function
prime_l()
.
−
(
z
mod
rs
)
.If
x
0
is even, then we set
x
0
←
Whether or not strong primes are used for keys, in every case it is practical
to have available a function that generates primes of a specified length or
within a specified interval. A procedure for this that additionally ensures that a
prime
p
thus generated satisfies the further condition
gcd(
p −
1
,f
)=1
for a
specified number
f
is given in [IEEE], page 73. Here is the algorithm in a slightly
altered form.
Algorithm to generate a prime
p
such that
p
min
≤
p
≤
p
max
1.
Generate a random number
p
,
p
min
≤
p
≤
p
max
.
2.
If
p
is even, set
p
←
p
+1
.
3.
If
p>p
max
, set
p
←
p
min
+
p
mod (
p
max
+1)
and go to step 2.
4.
Compute
d
:= gcd(
p −
1
,f
)
(cf. Section 10.1). If
d
=1
, test
p
for primality
(cf. Section 10.5). If
p
is prime, then output
p
and terminate the algorithm.
Otherwise, set
p ← p
+2
and go to step 3.
A realization of this procedure as a C++ function is contained in the FLINT/C
package (source file
flintpp.cpp
).
