Blog
Comparison of Digital and Quantum Computers, Part 1
Everyone in the IT field is interested in how big a threat quantum computers are to cryptography and how to deal with the problem. This series of articles tries to explain this problem in a popular way.
Threats to Asymmetric Cryptography
Dr. Michael Mosca published a simple equation around 2015 describing data protection. If I need to
protect data for a certain period of time, the attack time ( Z ) must be greater than the sum
of the time needed to ensure data protection ( X ) and the time to switch to another algorithm
( Y ). If the attack time is shorter, the attacker has a chance to obtain data or key material.
All of this has significant implications for security.
What does it look like in reality? How long does the attack take and how demanding is it
on classical digital or upcoming quantum computers? Is it a cryptographic, theoretical or
practical threat? These are questions that probably bother everyone whose work touches
on computer science and security. If it is a cryptographic threat, it is usually just
a mathematical curiosity. In the case of a theoretical threat, such a threat may be realized
at some point in the future. Finally, a practical threat means that this attack is or
will be possible to realize.
This document tries to explain the basic features in an understandable way, which can lead
to oversimplification. I also use the classic explanation of the algorithms here so that
they can be easier to imagine, and the attack calculations are also based on this version.
At the same time, the whole procedure explains why it is important to have control over
your assets and protect them accordingly. This also means quickly and easily changing
the cryptography settings in all the systems you use.
Even in computer science, it is appropriate to follow the motto of Vegetius: "Si vis pacem,
para bellum", i.e. "If you want peace, prepare for war". Security is currently
a very turbulent area with a large number of warlords trying to capitalize on any opportunity.
This is exactly the reason why it is necessary to approach this material with a certain
skepticism and caution, development may cause it to become obsolete soon. In such a case,
the comments written here would not necessarily lead to an expansion of knowledge, but to
a wrong decision. Quantum computers will come, the question is when and how powerful they
will be. The operating temperatures listed here may change with new technology, which
significantly changes the power requirements. Similarly, changes may occur at other
levels with similar impacts.
Time needed to attack current asymmetric algorithms using digital computers
Current asymmetric algorithms are based on one-way operations. It is very easy to perform
such an operation in one direction, but extremely difficult or impossible to perform
it in the opposite direction. Current algorithms are therefore considered invincible
by digital computers. More precisely, at the current level of knowledge, we do not know
how to attack such an algorithm. The question is, what does invincible actually mean?
Is it possible to somehow describe such an attack and compare it to the events taking
place around us? And how do the upcoming quantum computers fit into this?
Until 2030, we will still use the RSA, DH, ECDH algorithms for key agreement. If nothing
changes, by 2035 we will use the ECDSA algorithms for digital signature algorithms,
the RSA and DSA algorithms are already excluded from this list. However, this article
will not describe the weaknesses, it will focus on the conditions of such an attack.
The goal is to provide an approximate time, energy and memory requirements of the attack
to determine the size of the threat. Unfortunately, the calculations are very approximate,
they do not consider the problems of current technologies with the size of available
memory, cache miss, branching, as well as the impacts of developments in mathematics,
physics, material sciences and other important fields. The article is intended only
as a warning about the likely impacts. So this is an optimistic approach, reality can
always surprise us.
The advent of quantum computers is relegating the aforementioned algorithms to a later
stage. Instead of RSA, DH, ECDH, Krystal Cyber is coming, standardized as FIPS 203 ML-KEM,
and in the near future HQC, which should be the FIPS 207 HQC-KEM standard. The postquantum
key exchange algorithms should be deployed by 2030. Instead of RSA, DSA and ECDSA,
Krystal Dilithium is standardized as FIPS 204 ML-DSA, SPHINCS+ is standardized
as FIPS 205 SHL-DSA or the upcoming Falcon, which should be standardized as FIPS 206 FN-DSA.
Replacement algorithms for digital signatures should be implemented by 2035. In connection
with the transition, a suitable approach issue is crypto-agility, i.e. the ability
to flexibly change the cryptography used, but this issue is not part of this article.
From the list of current algorithms, only RSA is based on the factorization problem,
while other algorithms are usually based on the discrete logarithm problem (DLP). But
what does this mean? Factoring a number means finding prime factors. In the case of
the RSA algorithm, a large n-bit number is created based on two large primes, the mutual
relationship of the primes used provides information for creating a private key and
subsequently a public key. Thanks to this, both encryption and decryption of the content
are possible. In contrast, the discrete logarithm is built on a different problem. If
we work with modular operations (actually the remainder after division), the number
range is limited by the divisor. The divisor itself must be only a prime number from
among very specific ones. In such a number range, it is easy to create a power, but it
is extremely challenging to find the corresponding square root based on the knowledge
of the power. And since this problem is used in both DH algorithms and, with some
modification, in ECDH algorithms, it is extremely difficult to break the codes mentioned.
So how difficult is it in reality?
To be continued in The RSA Algorithm and the Factorization Problem
Autor článku:
