Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Международный журнал информационных технологий и энергоэффективности

РАЗРАБОТКА СИМУЛЯТОРА КВАНТОВОГО АЛГОРИТМА ШОРА ДЛЯ ДЕМОНСТРАЦИИ ЭТАПОВ КРИПТОАНАЛИЗА КРИПТОСИСТЕМ С ОТКРЫТЫМ КЛЮЧОМ

А.Г. Ерохин

Published Aug 11, 2024• 0 citations
OpenAlex

Abstract

The article discusses the quantum algorithm of discrete logarithm of Shore and the program that simulates its operation. The algorithm is divided into stages, each of which is described in detail. The simulator performs these steps and displays the states of the quantum registers, which provides a clear and visual study of the Shore algorithm. The conclusion is made about the prospects of the developed simulator for cryptanalysis of public key systems.

Related papers

Threats Related to the Use of Quantum Effects in Cryptography

Mikhail Alekseevich Cherepnev, S. S. Gracheva

In December 2022, an article was published on the implementation of the Shore algorithm in China on a quantum computer, where a 48-bit number was factorized and a prediction was made about the possibility of decomposing the RSA-2048 number using a similar technique. In this article, based on the experimental results presented in it, some conclusions are drawn about the possibility of practical use of the Shor algorithm and similar algorithms on quantum computers for attacks on information security systems based on solving integer factorization and discrete logarithm problems. The question of the dependence of the accuracy of calculations on the number of qubits in the system used and the depth of the program (the number of consecutive quantum operations on a quantum system) is considered. A brief overview of the history of the emergence and development of quantum key distribution technology, as well as other crypto protocols based on the physical properties of switching networks, is presented. A comparison is made with similar technologies in digital cryptography. In some cases, the advantage of the latter is shown in their ease of use, performance and provable durability.

INFORMACIONNYE TEHNOLOGII•Aug 13, 2024•4 citations

Basic Algorithms Quantum Cryptanalysis

Alexei Petrenko, Sergei Petrenko

Purpose of the article: development of quantum algorithms for efficient solution of cryptanalysis problems of asymmetric encryption schemes (RSA, ElGamal) and digital signature (DSA, ECDSA or RSA-PSS), based on computationally difficult problems of factorization and discrete logarithm.Research methods: Methods of quantum cryptanalysis based on the algorithms of Shor, Grover, Simon, etc.Results: algorithms for solving problems of quantum cryptanalysis of two-key cryptography schemes in polynomial time.Practical relevance: consists in developing a solution for computationally difficult problems of factorization and discrete logarithm in polynomial time, taking into account the security of the discrete algorithm (DLP) and the discrete elliptic curve algorithm (ECDLP). The obtained scientific results formed the basis for the development of a special Software Development Kit, SDK for cryptanalysis “Kvant-K”. The Certificate of state registration of the computer program No. 2020665981 was received.

Voprosy kiberbezopasnosti•Jan 1, 2023•7 citations

Аналіз шляхів розвитку криптографії після появи квантових комп’ютерів

Ю.І. Горбенко, Роман Сергійович Ганзя

Наведено оцінки стійкості сучасних популярних асиметричних та симетричних криптосистем проти квантового криптоаналізу на основі алгоритмів Шора та Гровера, а також проти класичних алгоритмів криптоаналізу. Окреслено основні напрями розвитку постквантової криптографії та проведено оцінку можливостей застосування на практиці криптосистем, що є стійкими, на цей момент, до квантового криптоаналізу. The article presents the evaluation of the resistance of modern popular asymmetric and symmetric cryptosystems against cryptanalysis based on quantum Shor’s algorithm and Grover’s algorithm and against classical algorithms of cryptanalysis. There we present basic directions of postquantum cryptography and possibilities of the practical application of cryptosystems that are stable at the moment against the quantum cryptanalysis.

•Jan 1, 2014•0 citations

Сравнительный анализ существующих протоколов обмена ключами для симметричных криптосистем

Яна Николаевна Крохалева, Elena Krotova

This article is devoted to the current problem - the distribution of keys in cryptographic systems. In the work, two basic methods of key distribution, which are currently used in the designof cryptographic systems, are examined and compared in detail. The Diffie-Hellman algorithmis the primary key distribution method in existing protocols for automated distributed systems.The technologies of quantum cryptography are getting more and more development and require analysis and comparison with other methods of classical cryptography regarding competitiveness.

Journal of the Ural Federal district Information security•Dec 30, 2019•0 citations

Моделирование быстрого алгоритма квантового поиска на классических компьютерах: информационный анализ проблемы останова

Сергей Викторович Ульянов, S.V. Ulyanov, В.С. Ульянов +1 more

The paper describes the simplest technique for simulating a quantum algorithm based on the direct matrix representation of quantum operators.This approach is stable and precise, but it requires allocation of operator's matrices in the computer memory.Since the size of the operators grows exponentially, this approach is useful for simulating quantum algorithms with a relatively small number of qubits (e.g., approximately 11 qubits on a typical desktop computer).This approach enables relatively simple simulation of the operation of the solution quality control system and performance of a reliability analysis.A more efficient fast quality control simulation method is based on computing all or a part of operator matrices as needed on a current computational basis.This method makes it possible to avoid storing all or a part of the operator matrices.In this case, the number of qubits to be simulated (e.g., the number of input qubits or the number of qubits in the system state register) is affected by: (I) the exponential growth in the number of operations required to calculate the result of matrix products; and (II) the size of the state vector allocated in computer memory.It is reasonable if one embodiment of this approach involves simulating up to 19 or more qubits on typical desktop computer, and even more in a system with a vector architecture.Due to particularities of the memory addressing and access processes in a typical desktop computer (such as, for example, a Pentium PC), when a number of qubits is relatively small, the on-demand computing tends to be faster than the direct storage approach.The compute-on-demand approach benefits from applying the results of studying quantum operators and their structure that enables computing the matrix elements more efficiently.The paper considers effective simulation of Grover's quantum search algorithm using a computer with classical architecture.

Международный журнал Программные продукты и системы•Aug 28, 2023•2 citations

Algorithms for quantum computation: discrete logarithms and factoring

Peter W. Shor

A computer is generally considered to be a universal computational device; i.e., it is believed able to simulate any physical computational device with a cost in computation time of at most a polynomial factor: It is not clear whether this is still true when quantum mechanics is taken into consideration. Several researchers, starting with David Deutsch, have developed models for quantum mechanical computers and have investigated their computational properties. This paper gives Las Vegas algorithms for finding discrete logarithms and factoring integers on a quantum computer that take a number of steps which is polynomial in the input size, e.g., the number of digits of the integer to be factored. These two problems are generally considered hard on a classical computer and have been used as the basis of several proposed cryptosystems. We thus give the first examples of quantum cryptanalysis.>

Annual Symposium on Foundations of Computer Science•Dec 17, 2002•8,719 citations
The article discusses the quantum algorithm of discrete logarithm of Shore and the program that simulates its operation. The algorithm is divided into stages, each of which is described in detail. The simulator performs these steps and displays the states of the quantum registers, which provides a clear and visual study of the Shore algorithm. The conclusion is made about the prospects of the developed simulator for cryptanalysis of public key systems.
In December 2022, an article was published on the implementation of the Shore algorithm in China on a quantum computer, where a 48-bit number was factorized and a prediction was made about the possibility of decomposing the RSA-2048 number using a similar technique. In this article, based on the experimental results presented in it, some conclusions are drawn about the possibility of practical use of the Shor algorithm and similar algorithms on quantum computers for attacks on information security systems based on solving integer factorization and discrete logarithm problems. The question of the dependence of the accuracy of calculations on the number of qubits in the system used and the depth of the program (the number of consecutive quantum operations on a quantum system) is considered. A brief overview of the history of the emergence and development of quantum key distribution technology, as well as other crypto protocols based on the physical properties of switching networks, is presented. A comparison is made with similar technologies in digital cryptography. In some cases, the advantage of the latter is shown in their ease of use, performance and provable durability.
Purpose of the article: development of quantum algorithms for efficient solution of cryptanalysis problems of asymmetric encryption schemes (RSA, ElGamal) and digital signature (DSA, ECDSA or RSA-PSS), based on computationally difficult problems of factorization and discrete logarithm.Research methods: Methods of quantum cryptanalysis based on the algorithms of Shor, Grover, Simon, etc.Results: algorithms for solving problems of quantum cryptanalysis of two-key cryptography schemes in polynomial time.Practical relevance: consists in developing a solution for computationally difficult problems of factorization and discrete logarithm in polynomial time, taking into account the security of the discrete algorithm (DLP) and the discrete elliptic curve algorithm (ECDLP). The obtained scientific results formed the basis for the development of a special Software Development Kit, SDK for cryptanalysis “Kvant-K”. The Certificate of state registration of the computer program No. 2020665981 was received.
Наведено оцінки стійкості сучасних популярних асиметричних та симетричних криптосистем проти квантового криптоаналізу на основі алгоритмів Шора та Гровера, а також проти класичних алгоритмів криптоаналізу. Окреслено основні напрями розвитку постквантової криптографії та проведено оцінку можливостей застосування на практиці криптосистем, що є стійкими, на цей момент, до квантового криптоаналізу. The article presents the evaluation of the resistance of modern popular asymmetric and symmetric cryptosystems against cryptanalysis based on quantum Shor’s algorithm and Grover’s algorithm and against classical algorithms of cryptanalysis. There we present basic directions of postquantum cryptography and possibilities of the practical application of cryptosystems that are stable at the moment against the quantum cryptanalysis.
This article is devoted to the current problem - the distribution of keys in cryptographic systems. In the work, two basic methods of key distribution, which are currently used in the designof cryptographic systems, are examined and compared in detail. The Diffie-Hellman algorithmis the primary key distribution method in existing protocols for automated distributed systems.The technologies of quantum cryptography are getting more and more development and require analysis and comparison with other methods of classical cryptography regarding competitiveness.
The paper describes the simplest technique for simulating a quantum algorithm based on the direct matrix representation of quantum operators.This approach is stable and precise, but it requires allocation of operator's matrices in the computer memory.Since the size of the operators grows exponentially, this approach is useful for simulating quantum algorithms with a relatively small number of qubits (e.g., approximately 11 qubits on a typical desktop computer).This approach enables relatively simple simulation of the operation of the solution quality control system and performance of a reliability analysis.A more efficient fast quality control simulation method is based on computing all or a part of operator matrices as needed on a current computational basis.This method makes it possible to avoid storing all or a part of the operator matrices.In this case, the number of qubits to be simulated (e.g., the number of input qubits or the number of qubits in the system state register) is affected by: (I) the exponential growth in the number of operations required to calculate the result of matrix products; and (II) the size of the state vector allocated in computer memory.It is reasonable if one embodiment of this approach involves simulating up to 19 or more qubits on typical desktop computer, and even more in a system with a vector architecture.Due to particularities of the memory addressing and access processes in a typical desktop computer (such as, for example, a Pentium PC), when a number of qubits is relatively small, the on-demand computing tends to be faster than the direct storage approach.The compute-on-demand approach benefits from applying the results of studying quantum operators and their structure that enables computing the matrix elements more efficiently.The paper considers effective simulation of Grover's quantum search algorithm using a computer with classical architecture.
A computer is generally considered to be a universal computational device; i.e., it is believed able to simulate any physical computational device with a cost in computation time of at most a polynomial factor: It is not clear whether this is still true when quantum mechanics is taken into consideration. Several researchers, starting with David Deutsch, have developed models for quantum mechanical computers and have investigated their computational properties. This paper gives Las Vegas algorithms for finding discrete logarithms and factoring integers on a quantum computer that take a number of steps which is polynomial in the input size, e.g., the number of digits of the integer to be factored. These two problems are generally considered hard on a classical computer and have been used as the basis of several proposed cryptosystems. We thus give the first examples of quantum cryptanalysis.>