Policy For Sunsetting GPG Keys < 2048 Bits

[Dimitri John Ledkov]

On 28 November 2014 at 11:54, Martin Pitt <martin.pitt at ubuntu.com> wrote:
> 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?

Both RSA and ECC have more efficient implementations for solving the
underlying equation, more efficient than brute force.
Shor's algorithm for factorisation, and modified Shor's algorithm for
solving elliptic curve equations.
The quantum algorithm is slightly beyond my math profeciency (or I
need more time on this) to calculate the number of qubits required to
solve each of the algorithms.

>
> 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?
>

However, if wikipedia is to be trusted, a 2048 RSA keys and 224 ECC
keys are considered to be of equivalent strength, however to directly
solve with quantum computer 4096 qubits are needed for RSA whilst only
1300 - 1600 qubits to solve the ECC key.

512-qubit CPU capable computer has already been built ( D-Wave Two )
however each qubit only communicates with the 6 others, thus it's not
a full / complete 512-qubit computer and is very slow, slower than
commodity binary CPUs at the moment. Thus is not yet an actual threat
- and we will probably migrate to simply bigger in size keys or some
new quantum keys. ECC keys however are cheaper and easier to implement
in hardware, thus I already have Yubico Security Key which uses ECC in
the U2F authentication as seen on google accounts.

-- 
Regards,

Dimitri.