When China, the US or Google do break encryption they aren’t going to announce it.
google would publish a paper and let somebody else capitalize on the knowledge
The Chinese? Weird title.
Valid. Its referring to a research paper produced at a Chinese Uni that went viral a month ago
I thought it was already fairly well established that symmetric encryption is not something that a quantum computer could potentially crack, only asymmetric encryption is theoretically possible due to its use of a prime order field.
Shor’s algorithm is a quantum algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor.[1][2] It is one of the few known quantum algorithms with compelling potential applications and strong evidence of superpolynomial speedup compared to best known classical (non-quantum) algorithms
a quantum computer with a sufficient number of qubits could operate without succumbing to quantum noise and other quantum-decoherence phenomena, then Shor’s algorithm could be used to break public-key cryptography schemes, such as
- The RSA scheme
- The Finite Field Diffie-Hellman key exchange
- The Elliptic Curve Diffie-Hellman key exchange
Moreover:
The largest number reliably factored by Shor’s algorithm is 21 which was factored in 2012 (ie faster than a regular computer, the much higher records like 48 bit utilized pre and post processing and was faster on a regular computer).
Even if we go with the assumption that the military is 10 years ahead in technology and can factor 221 with Shor’s, that’s still nowhere near enough to break RSA. Much more efficient to attack all the systemic flaws in RSA, hence why 1024 is no longer considered secure, 2048 is assumed to be breakable by any 3 letter agency, 4096 is assumed to be safe (for now), but mostly the latest and greatest is elliptical ECDSA/Ed25519 (of which NIST has been accused of rigging ECDSA for easier cracking lol).
Yep. Technically you could in principle use Grover’s algorithm to speed up cracking a symmetrical cipher, but the size typically used for the keys is too large so even though it’d technically be faster it still not be possible in practice. Even with asymmetrical ciphers we already have replacements that are quantum safe, although most companies have not implemented them yet.
I’m sorry, what?
The original article smelled wrong when they claimed to have broken AES. Thankfully, Bruce Schneier is far more authoritative than I ever will be and gives a short and succinct list of links to debunkings of this.
So far the biggest achievement in quantum computing seems to either be making a super random number reasonably quickly, or figuring out what quantum computers might be good for some day. So breaking encryption seems like a big leap.
Honestly, the random number generation on quantum computers is practically useless. Speeds will not get anywhere near as close to a pseudorandom number generator, and there are very simple ones you can implement that are blazing fast, far faster than any quantum computer will spit out, and produce numbers that are widely considered in the industry to be cryptographically secure. You can use AES for example as a PRNG and most modern CPUs like x86 processor have hardware-level AES implementation. This is why modern computers allow you to encrypt your drive, because you can have like a file that is a terabyte big that is encrypted but your CPU can decrypt it as fast as it takes for the window to pop up after you double-click it.
While PRNG does require an entropy pool, the entropy pool does not need to be large, you can spit out terabytes of cryptographically secure pseudorandom numbers on a fraction of a kilobyte of entropy data, and again, most modern CPUs actually include instructions to grab this entropy data, such as Intel’s CPUs have an RDSEED instruction which let you grab thermal noise from the CPU. In order to avoid someone discovering a potential exploit, most modern OSes will mix into this pool other sources as well, like fluctuations in fan voltage.
Indeed, used to with Linux, you had a separate way to read random numbers directly from the entropy pool and another way to read pseudorandom numbers, those being /dev/random and /dev/urandom. If you read from the entropy pool, if it ran out, the program would freeze until it could collect more, so some old Linux programs you would see the program freeze until you did things like move your mouse around.
But you don’t see this anymore because generating enormous amounts of cryptographysically secure random nubmers is so easy with modern algorithms that modern Linux just collects a little bit of entropy at boot and it uses that to generate all pseudorandom numbers after, and just got rid of needing to read it directly, both /dev/random and /dev/urandom now just internally in the OS have the same behavior. Any time your PC needs a random number it just pulls from the pseudorandom number generator that was configured at boot, and you have just from the short window of collecting entropy data at boot the ability to generate sufficient pseudorandom numbers basically forever, and these are the numbers used for any cryptographic application you may choose to run.
The point of all this is to just say random number generation is genuinely a solved problem, people don’t get just how easy it is to basically produce practically infinite cryptographically secure pseudorandom numbers. While on paper quantum computers are “more secure” because their random numbers would be truly random, in practice you literally would never notice a difference. If you gave two PhD mathematicians or statisticians the same message, one encrypted using a quantum random number generator and one encrypted with a PRNG like AES or ChaCha20, and asked them to decipher them, they would not be able to decipher either. In fact, I doubt they would even be able to identify which one was even encoded using the quantum random number generator. A string of random numbers looks just as “random” to any random number test suite whether or not it came from a QRNG or a high-quality PRNG (usually called CSPRNG).
I do think at least on paper quantum computers could be a big deal if the engineering challenge can ever be overcome, but quantum cryptography such as “the quantum internet” are largely a scam. All the cryptographic aspects of quantum computers are practically the same, if not worse, than traditional cryptography, with only theoretical benefits that are technically there on paper but nobody would ever notice in practice.
