Policy For Sunsetting GPG Keys < 2048 Bits

[Martin Pitt]

Dimitri John Ledkov [2014-11-28 10:45 +0000]:
> My concern with ECC algorithms is smaller key sizes to match
> equivalent RSA security (e.g. 224 bit ECC key ~= 2048 bit RSA key).
> Which leads to requiring less quantum computing power to break ECC key
> over RSA key, thus if/when quantum computing takes off ECC keys will
> be broken ahead of RSA keys.

I don't understand that, why?

The relative key sizes of EC discrete logarithm vs. prime
factorization based algorithms correspond to the relative complexities
of the best currently known algorithm. So while a quantum computer
would have to grind through 2^224 possibilities for an EC key (it has
to, as there is no known algorithm for the discrete logarithm problem
better than O(2^n) brute force), it would certainly *not* grind
through 2^2048 possibilities for RSA. Even if the current best
(subexponential) algorithm for factorization would not immediately be
applicable to quantum computers, there are for sure variants of it
which are. I. e. it would only need a number of steps/possibilities
which is more like 2^224 than 2^2048.

I. e. if you had a quantum computer with 224 bits, ECC 224 bit vs. RSA
2048 bit shouldn't matter?

Martin

-- 
Martin Pitt                        | http://www.piware.de
Ubuntu Developer (www.ubuntu.com)  | Debian Developer  (www.debian.org)