3

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?

Michael
  • 2,432
  • 2
  • 20
  • 37
torhub1
  • 115
  • 1
  • 2
  • 3
  • Can you link sources for that? – StackzOfZtuff Oct 23 '15 at 20:20
  • i read it on a book called "understanding bitcoin", page 63, – torhub1 Oct 23 '15 at 20:49
  • Find the answers yourself. https://en.wikipedia.org/wiki/Grover%27s_algorithm and https://en.wikipedia.org/wiki/Shor%27s_algorithm The short answer is that yes, AES is more quantum computer resistant than RSA is. The long answer is that we're a long way away from quantum computers able to tackle these problems. – Steve Sether Oct 23 '15 at 21:39

1 Answers1

3

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.

Tim McLean
  • 248
  • 1
  • 9
  • 6
    "In other words, AES-128 would be unusable." Thomas Pornin makes a really good point in this answer (http://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 Thompson Feb 11 '16 at 21:18