Is it true that with the rise of quantum computers, which is pretty close these days, AES 128 and 256 are resistant? while PGP and RSA are not?


Not entirely. Symmetric cryptosystems, including those using AES, are not completely broken by quantum computing, as far as we know. However, Grover's algorithm does pose a significant threat:

Grover's algorithm is a quantum algorithm that finds with high probability the unique input to a black box function that produces a particular output value, using just O(N^(1/2)) evaluations of the function, where N is the size of the function's domain.

This means that, given a known plaintext-ciphertext pair, we could determine an AES-128 key using about (2^128)^(1/2) = 2^64 steps. In other words, AES-128 would be unusable.

There's a straightforward mitigation though: double the key size. In a post-quantum world, AES-256 is still comfortably secure.

PGP and GPG are programs that use a variety of cryptographic algorithms. All of their asymmetric operations use algorithms (such as RSA and ECDSA) that are vulnerable to quantum computing. It's likely that they will be updated, at some point, to use quantum resistant asymmetric algorithms, but that has not yet occurred.

  • 5
    "In other words, AES-128 would be unusable." Thomas Pornin makes a really good point in this answer (security.stackexchange.com/a/48027): "however, note that these are 2^64 quantum-computing operations; you cannot apply figures from studies with FPGA and GPU and blindly assume that if a quantum computer can be built at all, it can be built and operated cheaply." – John Peter Thompson Garcés Feb 11 '16 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.