Will the quantum encryption algorithm become a joke after a 10-year-old desktop computer breaks it in 4 minutes?
- An American company made 0.7nm chips: EUV lithography machines can’t do it
- CVE-2007-4559 Python vulnerability ignored for 15 years puts 350,000 projects at risk of code execution
- RISC-V only takes 12 years to achieve the milestone of 10 billion cores
- 14000 cores + 450W: RTX 4080 graphics card perfectly replaces the RTX 3080
- Big upgrade: The difference between Bluetooth 5.0 and 5.2
- Geeks Disappointed that RTX 4080/4090 doesn’t come with PCIe 5.0
- What are advantages and disadvantages of different load balancing?
Will the quantum encryption algorithm become a joke after A 10-year-old desktop computer breaks it in 4 minutes?
A 10-year-old desktop computer broke the quantum encryption algorithm in 4 minutes. No one has cracked it for 12 years. The core principle comes from 25 years ago.
It only took 4 minutes to crack the key of the quantum encryption algorithm. I still use a desktop computer that is 10 years old.
It only takes 62 minutes to completely crack it, and it can be done with a single CPU core.
The news that two KU Leuven scholars have cracked a quantum encryption algorithm based on mathematical theory has recently caused a sensation in the cryptography community.
You know, the algorithm they cracked, SIKE, has always been high hopes, and no one has cracked it in the past 12 years.
In the post-quantum standard algorithm announced by the United States not long ago, it is one of the four candidates, and it is likely to be added to the standard algorithm in the future.
The principle of the method they used was actually proposed 25 years ago.
This has triggered a re-investigation of SIKE by a number of tech giants such as Microsoft and Amazon.
At the same time, many cryptography bigwigs began to sigh with emotion. To understand the cryptographic system, we still have to pay attention to the basic theory of mathematics!
Once cracked the algorithm that has not been broken for 12 years
The SIKE algorithm mentioned above is a PQC (Post Quantum Computing) algorithm.
With the emergence of quantum computing, many problems of super computational complexity have been solved, but classical encryption algorithms have also been threatened.
For example, the famous RSA algorithm, whose 2048-bit long encrypted information, takes 80 years to crack, while quantum computing brute force cracking only takes 8 hours.
Therefore, the academic community proposes the concept of post-quantum cryptography to resist the cracking of quantum computers.
Recently, the National Institute of Standards and Technology (NIST) has just announced the first batch of post-quantum cryptographic standard algorithms, a total of 4.
The other 4 algorithms, including SIKE, are identified as candidates and will enter the next round of screening.
The full name of SIKE is Supersingular Isogeny Key Encapsulation.
This is an encryption algorithm that uses elliptic curves as the theorem, and looks like it can be expressed by a y²=x³+Ax+B, where A and B are numbers.
The key to this method is the use of Isogenies, that is, mapping the points of one elliptic curve to another elliptic curve.
Then, based on the Supersingular Isogeny Diffie-Hellman (SIDH) key exchange protocol, post-quantum key encapsulation is realized.
The method can be abstracted into a process like this:
Suppose there are two parties, Alice and Bob, who want to exchange information secretly, but in an insecure environment.
Alice and Bob can be understood as two graphs, they have the same points but different edges.
Among them, each point represents a different elliptic curve.
If an elliptic curve can be transformed into another elliptic curve in a specific way, that is, by drawing an edge between two points, this edge represents a homologous relationship.
Alice and Bob have different edges, which means they are defined by different homology relations.
Now, Alice and Bob start from the same point, each jumping randomly along the edges on their own graph, and following the path from one point to the other.
The two then announce the intermediate point they reached, but the path is kept secret.
Then, the two exchange positions, repeating their previous secret path, so that they will eventually reach the same point.
Since this endpoint can be determined secretly, it can be used as a shared key.
The biggest advantage of this encryption method is that even if the attacker knows the intermediate point that Alice and Bob send to each other, he cannot know the intermediate process.
There is no way to find the final destination.
SIDH/SIKE is also considered to be one of the earliest used homology-based encryption protocols.
But this method has a problem, that is, it must provide an auxiliary torsion point (auxiliary torsion points), that is, some information other than the public exchange site of Alice and Bob.
A lot of cracking methods have tried to exploit this information, and this time too.
Scholars from the University of Leuven in Belgium explained the cracking method in detail in a paper on August 5.
Author Thomas Decru said that although an elliptic curve is one-dimensional, in mathematics, it can be visually represented as two-dimensional or any dimension, so mapping relationships can be created between these generalized objects.
Decru and Castryck calculate the product of Alice’s starting point elliptic curve and the elliptic curve that was exposed to Bob, which results in an Abelian surface .
Then through a mathematical theorem that can link Abelian surfaces to elliptic curves, and information on auxiliary torsion points, they can find Alice and Bob’s shared secret.
The key theorem used in the crack comes from a paper published in 1997 by mathematician Ernst Kani.
In practice, the researchers found the SIKE key in just 4 minutes using a 10-year-old desktop computer.
It only took 62 minutes to completely break the SIKE algorithm, and only a single core was used in the whole process.
In this regard, encryption algorithm expert Christopher Peikert said that when an encryption algorithm is proposed, there are often many cracking methods immediately, but SIKE has never been cracked in the 12 years since it was proposed. “.
SIKE was not selected as the PQC standard, also because the academic community was worried that it had not been fully studied and there was a possibility of major attacks.
This time, the key to SIKE’s cracking is attributed to the application of mathematical theory.
University of Auckland mathematician Steven Galbraith believes the core theory used in the crack comes from mathematics.
This is also verified to a certain extent. For the study of cryptography, the accumulation of basic mathematical theories is very important.
One of the proposers of SIKE, David Jao, a professor at the University of Waterloo in Canada, affirmed this work:
Although at first I was sad that SIKE was broken, this method of breaking through math is really cool.
At the same time, he is also glad that SIKE was cracked before being widely deployed.
However, although SIKE has been cracked, other encryption methods using the same-origin method (CSIDH\SQsign) have not been cracked.
It is worth mentioning that this is not the first PQC algorithm to be cracked this year.
In February of this year, the multivariate algorithm Rainbow was also cracked.
Ward Beullens, a scholar at the IBM Research Institute in Zurich, used his laptop to calculate for a weekend (53 hours) and cracked Rainbow’s key.
This algorithm is also one of the candidates for the NIST PQC standard algorithm.
- DIY a PBX (Phone System) on Raspberry Pi
- How to host multiple websites on Raspberry Pi 3/4?
- A Free Intercom/Paging system with Raspberry pi and old Android phones
- DIY project: How to use Raspberry Pi to build DNS server?
- Raspberry Pi project : How to use Raspberry Pi to build git server?