Cryptography Reference
In-Depth Information
text. Within a little less time, namely in 17 years, he could read his plaintext
to his great surprise, as nobody had expected to ever see it printed:
THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE.
But this speaks against the theory rather than against Rivest. This success wasn't
initially a real risk for the public keys in use. Factoring a 512-bit number would
have taken a hundred times longer (for a key only 84 bits longer!).
However, the theory behind this attack was five years old. Meanwhile, another
variant by the name of
number-field sieve
(
NFS
) was developed [Lenstra].
NFS would have made the attack ten times faster. For large numbers with
many decimal digits, the cost for factoring a number,
n
, by NFS is roughly
e
(
1923
+
o
(
1
))
f
(
n
)
where
f
stands for
f(n) = (ln n)
1
/
3
(ln n)
2
/
3
.
(As usual in higher mathematics, o(1) denotes a quantity the value of which
gradually reduces as
n
increases.) If we were able to reduce the constant 1923
to 1.5 today, then factoring 1024-bit numbers, which are secure by current
standards, would already be real. But it hasn't happened yet.
By the time this topic goes to print new findings will have been published.
Perhaps somebody may even have made a 'great breakthrough', or perhaps
such a breakthrough is not even possible.
People also have great hopes of
quantum computers
, which will be discussed
in Section 5.9. It is currently believed that, with their help, factoring very large
numbers might become a 'kid's game'. Unfortunately, quantum computers have
a serious drawback: they don't exist yet, and it is in the lap of the gods whether
and when we will ever have one.
Conversely, an opto-electronic device called
Twinkle
(
T
he
W
eitzman
IN
stitute
K
ey
L
ocating
E
ngine) by Shamir appears to be much more realistic. Shamir
introduced it at the EUROCRYPT '98; he estimates that the device can increase
