2022-05-02
The use of quantum computers in the field of asymmetric cryptography
Quantum computers are extremely complex devices that have been under research and development for many years. Their computing capabilities are also constantly increasing. And although these devices will be able to show their full potential probably only in a few years, increasingly newer areas of their application are constantly being created. One of them is asymmetric cryptography and the Public Key Infrastructure (PKI) technology.
The RSA algorithm, commonly used in the above-mentioned technology, bases its security on the problem of factorization of large numbers. In simple terms, it allows to create a pair of keys – public and private, which are mathematically connected to each other. They make it possible to sign messages (with the private key) and verify the correctness of the signature (with the public key).
The RSA algorithm uses large prime numbers and relatively prime numbers (numbers that have no common divisors). The above-mentioned key pair is created by using appropriate mathematical operations. The use of the Shor algorithm (developed by Peter Shor in the mid-90s and used to factorize numbers – look for their divisors) in traditional computers does not pose a threat to the security of the RSA algorithm.
“Trying to calculate a private key can take several hundred years, and security is easily increased by using longer keys – larger numbers, which again increases computing complexity and the time needed to decompose them. Today, keys between 2048 and 4096 bits in length are commonly used” – explains Robert Poznański, analyst at Asseco Data Systems. “Another technique used in asymmetric cryptography is Elliptic Curves Cryptography (ECC). It uses the problem of computing complexity of discrete logarithms on elliptic curves. Apart from this mathematical basis, the principle of using these algorithms and private-public key pairs to create electronic signatures is similar” – he adds.
Risk of breaking asymmetric algorithms
The use of quantum computers and the Shor algorithm on a quantum computer could potentially make it possible to quickly break the RSA algorithm or elliptic curve cryptography. Interestingly, at this point in time, the RSA algorithm appears to be more difficult to break than the ECC algorithms and requires a quantum computer with a larger number of qubits for this operation. Nevertheless, carrying out such an operation at present is far beyond the reach of the most powerful quantum computers. As experts estimate, they will achieve the required computing power only in the next 5-7 years.
For example, the number of qubits needed to break the RSA (3072 bit) and ECC (P-256) algorithms are 6146 and 2330 respectively. We should mention here that IBM is planning to create a quantum computer with 1000 qubits by the end of 2023. It should also be remembered that building a computer with a sufficient number of qubits does not mean that it will automatically break RSA or ECC algorithms. Such computer needs to be properly programmed and have access to its computing power.
“It is also worth mentioning that symmetric algorithms, i.e. using a single key to encrypt and decrypt messages, such as AES or Camellia, are not threatened by quantum computers. Their principles of operation are so different from asymmetric algorithms that finding a mechanism that would allow attacks using quantum computers is not possible” – assures Robert Poznański.
Algorithms of post-quantum cryptography
In the face of the upcoming more powerful and efficient quantum computers, we are not left defenseless. For several years work has been going on to select so-called post-quantum cryptography algorithms. The main core of activities is carried out by NIST (the National Institute of Standards and Technology) – an American institute dealing with research and standardization in the field of data communications. Currently, the third round of the competition for the selection of asymmetric cryptography algorithms that will be resistant to attack attempts using quantum computers is underway. The work is carried out in two main areas – algorithms for key negotiation, which may find application primarily in the SSL/TLS protocol, and algorithms for electronic signatures. In both of these categories, algorithms for key negotiation have been admitted to Round 3: Classic McEliece, SABER, CRYSTALS-KYBER, NTRU and for electronic signatures: CRYSTALS-DILITHIUM, FALCON, Rainbow. It will likely be at least another year before NIST announces the results of the competition and makes recommendations on which algorithms should be used in the future.
Of course, the use of post-quantum algorithms is already possible today. However, without proper standardization, these solutions are more like prototypes and only show the possibility of implementation and deployment than correspond to actual needs and threats, specialists reassure. They add that without proper standardization of algorithms, applications used for signature validation may have problems with correct recognition of such signed documents. Therefore, the most common are hybrid solutions, where post-quantum algorithms are used as a complement to classical cryptography based on the RSA and ECC algorithms.
“Looking ahead, a working group has been established at Asseco Data Systems to prepare our organization and the services we provide for the migration to post-quantum algorithms. We also want to raise market awareness of this topic and prepare our clients for the upcoming changes. The technology under development is expected to bring a new dimension of security to Certum brand products offered by Asseco, including SimplySign e-signature or SSL/TLS certificates” – concludes Robert Poznański.