Cryptography Reference
In-Depth Information
as the transmittal of secret key information to an attacker via an Internet
connection.
To get a grip on such problems, frequently, in practice, for cryptographic
operations, “security boxes,” or “S-Boxes” for short, are implemented, whose
hardware is protected against attack by encapsulation in conjunction with
detectors or sensors.
If all these known traps are avoided, then there remains only the risk that the
modulus will be factored, and this risk can be effectively eliminated by choosing
sufficiently large prime numbers. To be sure, it has not been proved that there
is no easier method to break the RSA algorithm than factorization, and there is
also no proof that factorization of large integers is truly as difficult a problem as
it presently seems to be, but these issues have not adversely affected the practical
application of the algorithm to date: The RSA algorithm is the most commonly
implemented asymmetric cryptosystem worldwide, and its use in the generation
of digital signatures continues to increase.
There are many places in the literature where it is recommended that
so-called
strong
primes
p
and
q
be used in order to protect the modulus against
some of the simpler factorization methods. A prime
p
is called
strong
in this
connection if
(i)
p −
1
has a large prime divisor
r
,
(ii)
p
+1
has a large prime divisor
s
,
(iii)
r
−
1
has a large prime divisor
t
.
The importance of strong prime numbers to the security of the RSA algorithm
is not everywhere equally emphasized. Recently, there has been an increase in
the number of voices that assert that while the use of strong prime numbers is
not harmful, it also does not accomplish a great deal (cf. [MOV], Section 8.2.3,
Note 8.8, as well as [RegT], Appendix 1.4) or even that they should not be used
(see [Schn], Section 11.5). In the program example that follows we shall therefore
do without the generation of strong primes. For those who are nonetheless
interested, we sketch here a procedure for constructing such primes:
1.
The first step in the construction of a strong prime
p
with
p
binary digits
consists in the search for primes
s
and
t
satisfying
log
2
(
s
)
≈
log
2
(
t
)
≈
1
1
is divisible by
t
,
by testing sequentially numbers of the form
r
=
k ·
2
t
+1
,
k
=1
,
2
,...
, for
primality until we encounter a prime number. This almost always occurs in
at most
2
p
−
log
2
p
.Thenwesearchforaprime
r
for which
r
−
2ln2
t
steps (cf. [HKW], page 418).
2.
We now invoke the Chinese remainder theorem (see page 203) to
calculate a solution of the simultaneous congruences
x ≡
1mod
r
and
