Quantum computing

[Ryan Malayter]

On 4/18/07, Anders Breindahl <skrewz at skrewz.dk> wrote:
>
> However, I assume you know what you talk about, when you say that we
> aren't likely to factor 256-bit-numbers ever. So please restate that --
> even in the face of quantum computers -- we won't ever factor 256 bit
> numbers.
>
> By the way, I realize that this is a more general question of gnupg's
> life expectancy in a quantum computer world. But it's interesting to get
> answered.

Robert was referring to a 256-bit key space, which refers to symmetric
encryption, such as AES,

Factoring, on the other hand, applies only to public-key RSA
encryption. There "bits" mean something totally different; a bit of
RSA key length is "worth less" than a bit of symmetric key length.
Numbers have already been factored in the ~600 bit range, so at least
1024 bits are recommended for RSA, and 2048 bits is a good idea.

The "keyspace" size of RSA is roughly equivalent to the
O(exp(64/9b)^(1/3)(log b)^(2/3)) that you quote; That is the number of
operations that must be performed to break the algorithm by brute
force. For strong symmetric algorithms,like AES or Twofish, the number
of operations required is simply two to the power of the number of
bits in the key,

Note that breaking Diffie-Hellman and other discrete logarithm based
algorithms is thought to be nearly equivalent to factoring, but has
not been proven to be so.

I suggest you borrow a copy of Bruce Schneier's _Applied
Cryptography_; it is a very good primer.


Regards,
Ryan