Cryptography Reference
In-Depth Information
(c) If
j>
0 and
z
1, then
p
is a composite number, i.e., it won't
pass the test. We start all over again from Step 1.
=
(d) We increase
j
by 1 and decide:
•
If
z
=
p
−
1, then
p
passed the test for this
a
.
z
2
•
If
j<b
and
z
=
p
−
1, then we calculate
z
=
mod
p
and
return to (c).
(e) That leaves us with
j
=
b
and
z
=
p
−
1: so,
p
failed the test and
we start again.
Non-mathematicians will presumably find it hard to understand how this test
can work: the residual classes modulo
p
form a field only for prime numbers
p
. In it, each square has exactly two roots; in particular 1 has the roots 1 and
p
−
1. As the test runs, number
z
is continually squared. When it first takes on
the value 1 without previously having taken on the value
p
−
1, then 1 has to
have a third root, i.e., the residual classes modulo
p
cannot form a field, and
p
cannot be a prime number in this case.
The above test will be rejected with a probability of at least 75 % if
p
is not a
prime number [Knuth2, 4.5.4]. In practice, things look much more optimistic
(see above).
The costliest operation in this test is computing
a
m
mod
p
in Step (b). Accord-
ing to [SchnCr, 11.5], finding a 512-bit prime number on a Sparc II takes
about 24 seconds; with 1024 bits, this can easily increase to well over 5 min-
utes. Consequently, generating keys for the RSA method is not a matter of
fractions of seconds, even when using modern, faster computers (aside from
the fact that we have to create two prime numbers). But that shouldn't pose a
problem since it is extremely seldom that we'd have to create keys.
As a sideline, we don't have to choose
p
randomly every time. After the first
step, we can cleverly increase
p
in every step so that divisibility by small prime
numbers, such as 2, 3, or 5, is avoided from the outset.
See [SchnCr, 11.5] for more tests and literature references.
We will now discuss the security of the RSA method. Of course, the security
stands or falls with the possibility of factoring very large numbers; in this case
computing these prime numbers from the product of two prime numbers at an
acceptable cost. People have worked on this problem for decades. Before we
get to it, we will have a look at several other security aspects.
