Blog

Categories:

23. 2. 2026

Security Cryptography

Comparing Digital and Quantum Computers, Part 3: The Discrete Logarithm Problem

Everyone in the IT world is wondering how big a threat quantum computers pose to cryptography and how to deal with the problem. This series of articles tries to explain the problem in a popular way. After factorization, we can look at the discrete logarithm problem.

Algorithms using the discrete logarithm problemu

Currently, we use algorithms based on the discrete logarithm problem in two main groups. The first of these groups is the classic and still used Diffie-Hellman (DH), then the now obsolete DSA (Digital Signature Algorithm), the ElGamal algorithm and the Schnorr signature. These are the most well-known algorithms, not a complete overview. The mentioned group of algorithms works on a limited group of integers (operation modulo prime number). This group uses keys with a size of kilobits, which has an impact on speed. Any operations with such large numbers are quite complex. The second group is the ECDH (Elliptic Curve Diffie-Hellman), ECDSA (Elliptic Curve DSA) and EdDSA (Edwards curve DSA) algorithms. These work in several variants. Either they are points of an elliptic curve over a number field, again limited by a prime number. Furthermore, it can be points of an elliptic curve over polynomials, bounded by an irreducible polynomial, or as a last option, field extensions are used. The keys to achieve the same level of security are an order of magnitude smaller than with the RSA algorithm and usually have a size of at most hundreds of bits. Theoretically, it is possible to use other approaches based on the discrete logarithm problem, but I do not know about their practical application, so I will not discuss them here.

So there are groups of systems that have similar properties, but as with the RSA algorithm, what are the attack possibilities? What is and is not within our power?

To attack the classic Diffie-Hellman, DSA, ElGamal and Schnorr, it is possible to use NFS-DL (Number Field Sieve – Discrete Logarithm). The first part of the calculation is sorting, it uses tens of thousands of instructions per step with difficult branch prediction, and it is also a memory-intensive operation. Therefore, a situation often arises when the necessary data is not in the cache. The next step is filtering, which requires about 500 instructions per step, again memory-intensive. The last part is evaluation, which uses few instructions, about 50 per step, but is again memory-intensive. The overall complexity of the algorithm can be expressed as follows.

$O\left( \sqrt[3]{\frac{64}{9}} + 2^{n^{\frac{1}{3}}\left( \log n \right)^{\frac{2}{3}}} \right)$

The memory load of the numerical sieve is also quite significant, with the expression

$M \approx O\left( {\sqrt[3]{\frac{64}{9}} + 2}^{n^{\frac{1}{3}}\left( \log n \right)^{\frac{2}{3}}} \right)$

The actual attack on the discrete logarithm problem over elliptic curves is still based on the Pollard 𝜌 (Pollard rho) algorithm. For this algorithm, the complexity can be defined as follows

$O \approx \left( \frac{2^{\frac{n}{2}}}{\sqrt[]{m}} \right)$

In this formula, n is the bit width of the key and m is the automorphism value. Of the curves used, the Weierstrass curves (NIST P-256, NIST P-384 and NIST P-521, as well as brainpoolP256r1, brainpoolP384r1, brainpoolP521r1) have automorphism m=2, and the community curves using Twisted Edwards (Ed25519 and Ed448) have the value m=8. The solution requires approximately 4000 instructions per step, and branch prediction problems very often occur. This means discarding the instruction queue and pausing the calculation for several tens to lower hundreds of cycles. On the other hand, in the case of an attack using Pollard 𝜌, the advantage is extremely low memory load.

Algorithm	Complexity	Operations	Instructions	Memory (B)	Time (years)	Energy (J)
DSA1024	2^48.7	1.21∙10¹⁴	1.81∙10¹⁸	1.21∙10¹⁴	5.76∙10⁰	5.05∙10⁶
DSA2048	2^62.8	8.09∙10¹⁸	1.21∙10²³	8.09∙10¹⁸	3.84∙10⁵	3.37∙10¹¹
DH1024	2^46.7	1.21∙10¹⁴	1.81∙10¹⁸	1.21∙10¹⁴	5.76∙10⁰	5.05∙10⁶
DH2048	2^62.8	8.09∙10¹⁸	1.21∙10²³	8.09∙10¹⁸	3.84∙10⁵	3.37∙10¹¹
DH3072	2^74.4	2.54∙10²²	3.81∙10²⁶	2.54∙10²²	1.20∙10⁹	1.05∙10¹⁵
DH4096	2^83.8	1.76∙10²⁵	2.64∙10²⁹	1.76∙10²⁵	8.36∙10¹¹	7.33∙10¹⁷
DH6144	2^99.0	6.77∙10²⁹	1.01∙10³⁴	6.77∙10²⁹	3.21∙10¹⁶	2.82∙10²²
DH8192	2^111.4	3.55∙10³³	5.33∙10³⁷	3.55∙10³³	1.68∙10²⁰	1.48∙10²⁶
brainpoolP256r1	2^127.5	2.40∙10³⁸	9.62∙10⁴¹	1	3.05∙10²⁴	1.0∙10¹⁰
brainpoolP384r1	2^191.5	4.43∙10⁵⁷	1.77∙10⁶¹	1	5.62∙10⁴³	4.93∙10⁴⁹
brainpoolP521r1	2^260.0	1.85∙10⁷⁸	7.41∙10⁸¹	1	2.34∙10⁶⁴	2.05∙10⁷⁰
NIST P-256	2^127.5	2.40∙10³⁸	9.62∙10⁴¹	1	3.05∙10²⁴	1.0∙10¹⁰
NIST P-384	2^191.5	4.43∙10⁵⁷	1.77∙10⁶¹	1	5.62∙10⁴³	4.93∙10⁴⁹
NIST P-521	2^260.0	1.85∙10⁷⁸	7.41∙10⁸¹	1	2.34∙10⁶⁴	2.05∙10⁷⁰
Curve25519	2^126.0	8.50∙10³⁷	3.40∙10⁴¹	1	1.07∙10²⁴	9.45∙10²⁹
Curve448	2^222.5	9.35∙10⁶⁶	3.81∙10⁷⁰	1	1.20∙10⁵³	1.05∙10⁵⁹

Again, these are ideal conditions. In the case of attacks on DH and DSA, the reality will be extremely different. Memory is again a bottleneck here, so access to data during the calculation will be limited by the speed of the storage. This is an extension of the calculation in the order of 10³ for NVMe disks, 10⁴ for SSD disks and 10⁷ for HDD (magnetic disks). At the same time, memory in the order of TB is needed for the 512b number itself. The memories themselves have a consumption that corresponds to another approximately 100 W per 1.5 TB. This corresponds to a small increase in power consumption in decimal places. Furthermore, especially when analyzing a matrix, which again has a huge range, cache misses will be a frequent phenomenon. Since these are memory-intensive operations, the data will not fit in the processor cache. As a result, access to memory will often be suspended for about 200 cycles, when the calculation will not be performed and the memory will be reloaded into the cache. This means a slowdown of about 5 orders of magnitude (10⁵ to 10⁹ depending on the technology used). In the case of elliptic curves, the only problem is branch prediction, which slows down the calculation by up to three orders of magnitude (10³ ).

As you can see, in terms of possibilities, an attack on DSA1024, DSA2048, DH1024 and DH2048 is within our capabilities. In the case of 1024b keys and smaller, these are capabilities available even to individuals, while for 2048b keys, these are capabilities available to large companies or state actors. As for larger keys or the elliptic curves that are still used today, the situation is not so simple. The question again is, are we able to carry out such an attack for these algorithms as well? We can look at it from several perspectives:

If we consider the time and ability to produce a sufficient number of computers? Intel and AMD have produced an estimated billions of processors in their entire history (we can consider 50 years), so we are in the order of 10⁹ . Since the first processors had a single core for several decades and only after 2006 did multiple cores begin to be used, it is possible to consider 2.5 cores per processor. The considered available performance will reduce the time accordingly, but in the overall scope this performance will rather eliminate the small fluctuation caused by problems with the availability of large data in the processor cache.
If we consider only time, the universe was created 18 billion years ago. This corresponds to the order of 10¹⁰ , so we are not able to perform such a calculation fast enough. The exceptions are DSA algorithms and DH algorithms up to key size 3072b.
If we consider only the required power input, we can think as follows. The entire human civilization had an electrical power input of around 30,000 TWh in 2025, i.e. in the order of 10¹⁶ Wh. The sun provides us with a source with a capacity of 10¹⁸ W (what we receive on the Earth's surface), so if we wanted to freeze, we could use the energy mentioned. In the case of harnessing the entire sun, we are talking about a source with a power of 10²⁶ W. The central black hole of our galaxy then gives 10²⁹ W and the entire galaxy then roughly 10³⁷ W. It is clear that even these sources are not sufficient.

To be continued in the next section Attacks with quantum computers (Mar 2nd 2026)

References:

Sage Math script - Pollard rho and NFS-DL
Source: https://cryptosession.info/ke-stazeni
An algorithm to solve the discrete logarithm problem with the number field sieve
Source: https://www.acm.org
NFS with Four Large Primes: An Explosive Experiment
Source: https://link.springer.com/
Computing Individual Discrete Logarithms Faster in GF(p^n) with the NFS-DL Algorithm
Source: https://eprint.iacr.org
On the Efficiency of Pollard's Rho Method for Discrete Logarithms
Source: https://maths-people.anu.edu.au/
About Pollard rho
Source: https://www.ams.org/

Autor článku:

Jan Dušátko

Jan Dušátko has been working with computers and computer security for almost a quarter of a century. In the field of cryptography, he has cooperated with leading experts such as Vlastimil Klíma or Tomáš Rosa. Currently he works as a security consultant, his main focus is on topics related to cryptography, security, e-mail communication and Linux systems.

1. Introductory Provisions

1.1. These General Terms and Conditions are, unless otherwise agreed in writing in the contract, an integral part of all contracts relating to training organised or provided by the trainer, Jan Dušátko, IČ 434 797 66, DIČ 7208253041, with location Pod Harfou 938/58, Praha 9 (next as a „lector“).
1.2. The contracting parties in the general terms and conditions are meant to be the trainer and the ordering party, where the ordering party may also be the mediator of the contractual relationship.
1.3. Issues that are not regulated by these terms and conditions are dealt with according to the Czech Civil Code, i.e. Act No.89/2012 Coll.
1.4. All potential disputes will be resolved according to the law of the Czech Republic.

2. Creation of a contract by signing up for a course

2.1. Application means unilateral action of the client addressed to the trainer through a data box with identification euxesuf, e-mailu with address register@cryptosession.cz or register@cryptosession.info, internet pages cryptosession.cz, cryptosession.info or contact phone +420 602 427 840.
2.2. By submitting the application, the Client agrees with these General Terms and Conditions and declares that he has become acquainted with them.
2.3. The application is deemed to have been received at the time of confirmation (within 2 working days by default) by the trainer or intermediary. This confirmation is sent to the data box or to the contact e-mail.
2.4. The standard time for registration is no later than 14 working days before the educational event, unless otherwise stated. In the case of a natural non-business person, the order must be at least 28 working days before the educational event.
2.5. More than one participant can be registered for one application.
2.6. If there are more than 10 participants from one Client, it is possible to arrange for training at the place of residence of the intermediary or the Client.
2.7. Applications are received and processed in the order in which they have been received by the Provider. The Provider immediately informs the Client of all facts. These are the filling of capacity, too low number of participants, or any other serious reason, such as a lecturer's illness or force majeure. In this case, the Client will be offered a new term or participation in another educational event. In the event that the ordering party does not agree to move or participate in another educational event offered, the provider will refund the participation fee. The lack of participants is notified to the ordering party at least 14 days before the start of the planned term.
2.8. The contract between the provider and the ordering party arises by sending a confirmation from the provider to the ordering party.
2.9. The contract may be changed or cancelled only if the legal prerequisites are met and only in writing.

3. Termination of the contract by cancellation of the application

3.1. The application may be cancelled by the ordering party via e-mail or via a data mailbox.
3.2. The customer has the right to cancel his or her application for the course 14 days before the course takes place without any fees. If the period is shorter, the subsequent change takes place. In the interval of 7-13 days, an administrative fee of 10% is charged, cancellation of participation in a shorter interval than 7 days then a fee of 25%. In case of cancellation of the application or order by the customer, the possibility of the customer's participation in an alternative period without any additional fee is offered. The right to cancel the application expires with the implementation of the ordered training.
3.3. In case of cancellation of the application by the trainer, the ordering party is entitled to a full refund for the unrealized action.
3.4. The ordering party has the right to request an alternative date or an alternative training. In such case, the ordering party will be informed about all open courses. The alternative date cannot be enforced or enforced, it depends on the current availability of the course. If the alternative training is for a lower price, the ordering party will pay the difference. If the alternative training is for a lower price, the trainer will return the difference in the training prices to the ordering party.

4. Price and payment terms

4.1. By sending the application, the ordering party accepts the contract price (hereinafter referred to as the participation fee) indicated for the course.
4.2. In case of multiple participants registered with one application, a discount is possible.
4.3. The participation fee must be paid into the bank account of the company held with the company Komerční banka č. 78-7768770207/0100, IBAN:CZ5301000000787768770207, BIC:KOMBCZPPXXX. When making the payment, a variable symbol must be provided, which is indicated on the invoice sent to the client by the trainer.
4.4. The participation fee includes the provider's costs, including the training materials. The provider is a VAT payer.
4.5. The client is obliged to pay the participation fee within 14 working days of receipt of the invoice, unless otherwise stated by a separate contract.
4.6. If the person enrolled does not attend the training and no other agreement has been made, his or her absence is considered a cancellation application at an interval of less than 7 days, i.e. the trainer is entitled to a reward of 25% of the course price. The overpayment is returned within 14 days to the sender's payment account from which the funds were sent. Payment to another account number is not possible.
4.7. An invoice will be issued by the trainer no later than 5 working days from the beginning of the training, which will be sent by e-mail or data box as agreed.

5. Training conditions

5.1. The trainer is obliged to inform the client 14 days in advance of the location and time of the training, including the start and end dates of the daily programme.
5.2. If the client is not a student of the course, he is obliged to ensure the distribution of this information to the end participants. The trainer is not responsible for failure to comply with these terms and conditions.
5.2. By default, the training takes place from 9 a.m. to 5 p.m. at a predetermined location.
5.3. The trainer can be available from 8 a.m. to 9 a.m. and then from 17 a.m. to 6 p.m. for questions from the participants, according to the current terms and conditions.
5.4. At the end of the training, the certificate of absorption is handed over to the end users.
5.5. At the end of the training, the end users evaluate the trainer's approach and are asked to comment on the evaluation of his presentation, the manner of presentation and the significance of the information provided.

6. Complaints

6.1. If the participant is grossly dissatisfied with the course, the trainer is informed of this information.
6.2. The reasons for dissatisfaction are recorded in the minutes in two copies on the same day. One is handed over to the client and one is held by the trainer.
6.3. A statement on the complaint will be submitted by e-mail within two weeks. A solution will then be agreed within one week.
6.4. The customer's dissatisfaction may be a reason for discontinuing further cooperation, or financial compensation up to the price of the training, after deduction of costs.

7. Copyright of the provided materials

7.1. The training materials provided by the trainer in the course of the training meet the characteristics of a copyrighted work in accordance with Czech Act No 121/2000 Coll.
7.2. None of the training materials or any part thereof may be further processed, reproduced, distributed or used for further presentations or training in any way without the prior written consent of the trainer.

8. Liability

8.1. The trainer does not assume responsibility for any shortcomings in the services of any third party that he uses in the training.
8.2. The trainer does not assume responsibility for injuries, damages and losses incurred by the participants in the training events or caused by the participants. Such costs, caused by the above circumstances, shall be borne exclusively by the participant in the training event.

9. Validity of the Terms

9.1 These General Terms and Conditions shall be valid and effective from 1 October 2024.

Blog

Comparing Digital and Quantum Computers, Part 3: The Discrete Logarithm Problem

Algorithms using the discrete logarithm problemu

References:

Autor článku:

Podobné články