Cryptography Reference
In-Depth Information
the length of breakable RSA keys by 100 to 200 bits. However, Twinkle accel-
erates only the first step (the 'sieving') within the factoring process. The second,
much more memory-intensive step doesn't change.
An improved version of the device was discussed at the EUROCRYPT 2000
[Twinkle]; it is said to help factor 768-bit keys within nine months.
Unfortunately, it requires about 5000 upgraded Twinkle devices and 80 000
standard Pentium-II computers
...
Anyway, the example of the RSA method shows clearly how much direct
influence current research has on cryptological practice, how much knowledge
is buried in a good implementation, and how open the future of this algorithm
actually is.
Multiprime
The heading of this section is the buzzword a company used at the RSA
Conference 2000 in Munich, Germany, for their product — same security but
dramatically increased performance! What's behind it? One can modify the
RSA method by working not only with the product
N
=
pq
of two prime
numbers, but also by using several very large prime numbers:
N
=
p
1
p
2
...p
n
.
Everything runs analogously, and if the prime numbers used are large enough,
security won't suffer either. But since the computation time for multiplication
(or raising to power) grows quadratically in line with the bit length, things can
be speeded up; for example, you can do things twice as fast when using four
instead of two factors. That's all there is to it. Cryptologists had long been
aware of this, they just might have forgotten to tell software developers about
it. So, if a cryptocard takes 25 seconds to encrypt using a 'classic' key, then
this might be reduced to 8 seconds when using six factors. It still remains slow.
Patents
RSA was patented in the USA in 1983, and the patent expired on September
20, 2000; it hadn't been patented elsewhere. RSA is the de-facto standard for
asymmetric methods all over the world, except in the USA. Public Key Partners
(PKP) handle all patents for such methods. This company is part of RSA Data
Security, Inc. and Caro-Kahn. Though free licenses appear to have been granted,
everything remained secret, and no law suit against PKP ended with a non-
appeal judgment. This is probably the reason why much free software, e.g.,
PGP and SSH (see Chapter 7), prefer methods no longer patented, such as the
