Quantum Computers Break Encryption in China But Far From Cracking Bitcoin

Despite Chinese researchers’ claims of cracking RSA encryption with existing quantum computers, Bitcoin’s SHA256 encryption algorithm remains secure.

A team of 24 Chinese researchers claimed to have factored a 48-bit number with a 10-qubit quantum computer. This could be critical in breaking the RSA encryption algorithm, which is at the heart of much internet communication.

The researchers claim that they can solve a previously unsolvable step in Schnorr’s method of factoring large prime numbers using quantum computers. Solving the prime factors of a large number is an important step in decrypting the RSA encryption algorithm.

While the paper is theoretically sound, experts say it is difficult to demonstrate that today’s quantum computers will improve.

“In the absence of any analysis demonstrating that it will be faster, I suspect that the most likely scenario is that it will be only marginally faster,” said MIT scientist Peter Shor.

Through the use of public and private keys, the RSA algorithm ensures confidentiality between parties exchanging data. It is a bidirectional function. This means that the plaintext can be determined given the encrypted data and a private key.

Shor proposed in 1994 that quantum computing could break encryption schemes deemed “uncrackable” by conventional computers.

In contrast, SHA256 is used to ensure that data has not been altered. It’s a hashing function, not an encryption algorithm.

SHA256 is used on the Bitcoin network to prove that the data from a transaction block has not been tampered with. It is a one-way function, which means that the output cannot be used to predict the input.

While Shor’s work demonstrated that it is possible to solve for the prime factors of a large number, laying the groundwork for cracking RSA encryption, no known algorithms determine a hash function’s input given its output. SHA-256 is also said to be collision-resistant, which means that finding different inputs that yield the same output is nearly impossible.

To tailor the output of a SHA256 function so that it is less than a predefined number, a Bitcoin miner must continuously vary a number known as a nonce. 

The difficulty is adjusted based on how long it took miners to create the correct output of the previous 2016 blocks. If it took more than ten minutes to guess the correct output of the last 2016 blocks, the Bitcoin algorithm makes the difficulty target easier to guess, and vice versa. To make the most guesses in a second, the miner employs special computers known as ASICs.

According to a January 2022 paper from the University of Sussex, a quantum computer with 13 million qubits can “break Bitcoin encryption” in a day, whereas a 300 million qubit machine takes an hour. The paper does not specify whether it refers to the private and public keys used to exchange Bitcoin or the SHA256 hashing function.

With 433 qubits, US multinational IBM claims to have the world’s most powerful quantum computer. It intends to release a 1,000-qubit quantum computer in 2023, followed by a 4,000-qubit machine in 2025.

Fujitsu, the Japanese computing behemoth, is expected to deliver the country’s first 64-qubit domestic quantum computer in the spring of 2023. It recently signed a new agreement to supply the machine to a Spanish computing center. It signed an agreement with the RIKEN research institute last year to deliver a machine for medical research.

However, as with the Chinese researchers, breakthroughs may occur much more quickly than expected.