Cryptography Reference
In-Depth Information
A 128-bit session key can presumably not be found in this way. But 1024 or
2048 bits of 'real chaos' do stand out in memory.
As bad as this may sound, don't panic just yet. A private PGP key on a private
computer is still safe, at least it will be if you are paranoid about disconnecting
from the network as you encrypt it (just joking). With Web servers, however, the
owner should know that a hacker attack can jeopardize the ciphering security
even after the attack's traces were removed. Generating new keys is part of
damage repair. Someren recommends to keep private keys in hardware only,
and process them only there.
This attack doesn't actually belong in a topic on cryptology, because it is closely
related to computer security, a different (and endless) topic. Nevertheless, I
think the method for finding private keys is closer to cryptanalysis than it is to
computer security. Moreover, it is helpful to know that 1024 bits of randomness
cannot be hidden coherently 'somehow' within 2 gigabytes of data.
Risk 8: New Methods for Factoring Large Numbers; Quantum
Computers; Twinkle
The attacks discussed so far are directed against the procedure, i.e., the protocol,
rather than against RSA itself. A cryptanalysis in the sense considered so far
would be successful if we could factor module
n
. It is assumed that finding the
plaintext from the public key is equivalent to the problem of factoring
n
, but it
can't be proved (yet?) [BonVen]. We have seen earlier that finding the private
key enables factoring. But perhaps it is also possible without the private key.
Research work in this field is running at full speed. You may have heard of the
spectacular decryption of a 428-bit number (129 decimal places) in April 1994
[GarPGP, Chapter 4, 'RSA-129 Solved!'; SchnCr, 11.4]. A group of math-
ematicians under the supervision of Lenstra used a variant of the so-called
quadratic sieve
for factoring large numbers and coordinated huge computer
capacities on the Internet: 600 users had 1600 distributed computers work
for over eight months. This corresponded to between 4000 and 6000 MIPS-
years. 'MIPS' is a very blurred unit; it roughly means 'one million computing
operations per second'. This means that a total of 150 billion operations were
executed (whatever that may mean). By the way
...
notice something about
this number? A similar amount of decryptions is necessary to brute-force
attack DES.
This 129-digit number had long been known. Rivest published it as a riddle in
1977; he estimated that 40 quadrillion years would be required to decrypt that
