Cryptography Reference
In-Depth Information
Risk 1: Identical Prime Numbers in Different Modules
If somebody finds that his module
n
is not relatively prime to a third-party
module (as we know, the modules are integral parts of the public keys, i.e.,
they are generally known), then this person knows a factor of the third-party's
module, i.e., he can factor it without any problem. When millions of public
keys have been published one day sooner or later, there will be trillions of
pairs — there could at least be one pair with a common divisor, couldn't there?
Theoretically, yes; practically, no. The reason is that a well-known prime-
number theorem in number theory says that
π(N)
, the number of all prime
numbers smaller than number
N
for large
N
, is described as
n/
ln
N
by approx-
imation. More specifically,
π
(N) lnN/N
tends toward 1 as
N
tends toward infinity. This means that, between 2
512
and
2
513
, there are roughly as many prime numbers as there are between 1 and 2
512
,
and that's approximately 7.5*10
151
, a number for which human languages don't
have a suitable superlative to classify it. So, no risk whatsoever can emerge
from the set of possible prime numbers.
It is much more likely (certainly not 'only' 10
100
times) that several users
will hit the same prime number due to poorly chosen random numbers. This
risk has to be excluded by most careful implementation of the random number
generation!
Risk 2: Chosen-Plaintext Attack
This brief discussion refers to a cryptographic protocol that will be covered in
Chapter 6, namely digital signatures. Nevertheless, we have to jump ahead a
little since the issue relates to RSA.
In digital signatures, a character string is 'decrypted' with the private key
(naturally, gibberish comes out of it). The result can be re-encrypted with the
public key to check it, which means that it has the function of a signature (only
the owner of the private key was able to create this signature).
People who use RSA to decrypt third-party character strings and publish the
results can be compromised. This happens as follows: Eve, the eavesdrop-
per, intercepted one of Alice's encrypted session keys. From the mathematical
