The improved algorithm to limit scope for recovering private key in Multi-Prime RSA by utilizing Quantum Fourier Transform

Abstract

Rivest–Shamir–Adleman (RSA) is widely recognized as one of the most effective and well-known public key encryption techniques. This technology has the capability for both data encryption and digital signature purposes. The private key is the primary target for unauthorized individuals attempting to damage the security of the RSA. In fact, recovering the private key becomes a challenging task when only the modulus and the public key are disclosed. The aim of this research is to present a methodology that may be employed to retrieve the private key and other alternative keys. This methodology is specifically designed to recover the plaintext through modular exponentiation. Periodic result from Quantum Fourier Transform (QFT) is an important part of this method. The process is split into two steps. In the first step, QFT is used in a quantum environment to find the periodic result of modular exponentiation. This result is then used to find the private key and alternative keys in a classical computing setting. When considering the generation of modulus from multiple primes, it is imperative to note that Shor’s algorithm requires a minimum of two factoring steps to get the expected outcomes. On the other hand, the proposed method may be executed in a single step. Furthermore, the odd periodic outcome that is not solvable by Shor’s algorithm can be chosen to find the results by using the proposed method. In addition, this approach can also reveal other keys that may be considered as possible candidates for the private key. The experimental results emphasize the effectiveness of the utilized method in accurately identifying the private key and possible alternative candidates when implemented in instances of lower size. Moreover, the periodic outcome ensures accurate achievement of objectives in classical computing; it is different from Shor’s algorithm, which must generate a new periodic outcome when the result is not in the condition.

Keywords:

• QFT
• RSA
• Shor’s algorithm
• periodic

Reviewing Editor:

• Jenhui Chen, Chang Gung University, Taiwan; Dhiya Al-Jumeily, Liverpool John Moores University, United Kingdom

Subjects:

• Applied Mathematics
• Computing & IT Security
• Computation

1. Introduction

RSA, known as Rivest–Shamir–Adleman (Rivest et al., 1978) is well-known public key cryptography in the field of modern cryptography. The flexibility is based on the mathematical complexity associated with breaking down large numbers into prime factors. RSA, developed by R. L. Rivest, A. Shamir and L. Adleman in 1978, enables secure online transactions, ensures confidentiality and provides authentication (Diffie & Hellman, 1976). It operates by generating a public key for encryption and a private key for decryption. Due to the complexity of prime factorization, which becomes increasingly difficult with larger numbers, the security strength of RSA has demonstrated remarkable resilience against classical computers. This has solidified RSA’s significance as a valuable instrument for protecting the confidentiality and integrity of sensitive data in the digital age (Paar & Pelzl, 2010). Although many factoring algorithms, including Trial division (Nidhi et al., 2014), Fermat’s Factorization (McKee, 1999) and their improvements (Somsuk & Tientanopajai, 2017; Somsuk, 2018; Tahir et al., 2021; Wu et al., 2014), Pollard’s rho algorithm (Pollard, 1978), Quadratic Sieve (Lenstra et al., 1982), General Number Field Sieve (GNFS) (Hamdi et al., 2014) and Elliptic Curve Factorization (Pollard, 1974), have been presented, it is important to note that none of these methods relying on classical computer have demonstrated the ability to efficiently solve this problem within polynomial time.

Shor’s algorithm, which was first proposed by P. Shor (1994), represents an important development in the field of quantum computing. The utilization of this method provides a robust approach for factorizing extremely large numbers with exponential efficiency in comparison with standard approaches. This algorithm exploits the foundational principles of quantum superposition and entanglement to efficiently execute the factorization of composite numbers, a task that provides an important challenge for traditional computers. The importance of Shor’s algorithm is in its relevance to RSA encryption, because its capacity to effectively factorize large numbers presents a potential threat to the security of RSA. Nevertheless, in cases when it is necessary to utilize multiple primes, exceeding two prime numbers, for the generation of both the public key and private key, the implementation of Shor’s algorithm requires at least two processes. Furthermore, if the result of the periodicity test is an odd number, it is essential to repeat the procedure using a different base.

The aim of this research is to propose an approach for identifying the private key or prospective alternate keys that could serve as the private key. The implementation consists of two distinct parts. The first phase of the analysis involves the computation of a periodic result using Quantum Fourier Transform (QFT). In fact, the result of this method may appear as either an odd or even number. Furthermore, in situations where RSA requires the use of several prime factors for generating keys, the incorporation of the quantum component enables the efficient calculation of the periodic output in one step, therefore decreasing the computational burden inside the quantum domain. In contrast, the following section is concerned with the classical computer. The periodic outcome serves as an essential parameter. The core principle involves the recognition of a wide range of values that may serve as the private key.

The rest of the paper is structured in the following form. Section 2 provides an extensive review of relevant research, containing significant works that include RSA, Quantum computing, QFT and Shor’s algorithm. Section 3 presents the proposed method that utilizes the periodic outcome derived from the quantum component to calculate the private key, as well as alternative keys that can potentially serve as the decryption key in replacement of the private key. Section 4, the experimental results and analyses are presented. The final portion will address that aspect of the conclusion.

2. Related works

This section aims to present a comprehensive examination of four essential domains of understanding: RSA, quantum computing, QFT and Shor’s algorithm.

2.1. RSA cryptography

RSA is the public key cryptography. The benefit is in its efficient utilization of prime factorization complexity to guarantee secure data transmission and digital identification. It serves as the foundation for ensuring secure online transactions, implementing digital signatures (Somsuk &Thakong, 2020; Yang et al., 2021), and facilitating the exchange of secret information (Vishwakarma & Gupta, 2021; Wahab et al., 2021). The possible impact on the security assumptions of RSA could be influenced by the emergence of computational paradigms and advanced methodologies. Moreover, RSA constitutes an algorithm that exhibits substantial resistance against attacks employing classical computer algorithms, such as factorization or brute force attack (Somsuk, 2022, 2021).

In truth, confidentiality and authentication are two crucial features of information security in the context of the RSA. Confidentiality refers to the securing of information to prevent unauthorized access or disclosure. It is accomplished by the process of encrypting data utilizing the public key of the intended receiver, followed by the subsequent decryption of the encrypted data using the private key. Moreover, authentication refers to the process of validating the identity of an individual, device, or institution. The utilization of digital signatures is integral to the functionalities of RSA. Therefore, the process of authentication plays an essential part in defending the integrity and validity of data. The application of this method engenders confidence among recipients by providing confidence that the received data is unmodified and originated from the claimed sender.

RSA consists of three primary components in its implementation. The initial aspect relates to the procedure of generating the essential components, including the modulus, the public key, and the private key. Assuming, n = $\prod _{i\in {\mathbb{Z}}^{+}}{\mathit{p}}_{\mathit{i}}$ where p_i represents a prime number and n stands as the modulus, a situation involving several prime numbers occurs when the number of prime factors exceeds two. Subsequently, Euler function ($\Phi$ (n)) can be computed from $\Phi$(n) = $\prod _{i\in {\mathbb{Z}}^{+}}\mathit{(}{\mathit{p}}_{\mathit{i}}-1).$ Following toward, the selection of the public key, denoted as e, can be made while adhering to a certain condition: 1 < e < $\Phi$(n) and gcd(e, $\Phi$(n)) = 1. The last step in this process is to compute the private key, d, from e*d mod $\Phi$(n) = 1. The next step involves the encryption procedure, where the plaintext is encoded by employing the following equation: c = m^e mod n, where m is the plaintext and c is the ciphertext. The final step entails the decryption procedure, attempting to recover the plaintext by employing the equation: m = c^d mod n. The original message will be recovered after the decrypting process is finished.

At present, there is not an efficient algorithm within the fields of digital technology that is able to destroy RSA in polynomial time. However, if the ongoing development of quantum computers reaches a state of perfection, it is possible that the RSA encryption method might be compromised by the utilization of specific algorithms designed for quantum computers, such as Shor’s algorithm.

2.2. Overview of quantum computing

Quantum computing shows a significant progression in computational capabilities, employing the principles of quantum mechanics to fundamentally transform approaches for information processing (Harrow et al., 2009). In contrast to classical bits, quantum bits, also known as qubits, contain the unusual property to be able to exist simultaneously in several states. The possible applications of quantum computing include a wide range of disciplines, including the optimization of intricate systems, the simulation of quantum processes, the study of encryption and the development of new drugs. In addition, Shor’s algorithm, a factorization method implemented on a quantum device, is attracting attention due to its potential to compromise classical cryptography systems such as RSA.

However, the field of quantum computing is presently in its early stages of development, encountering several challenges such as the demand for stable qubits and the requirement for error correction systems (Majumdar & Sur-Kolay, 2020). Therefore, the complete achievement for the potential of quantum computers to effectively compromise RSA has not been achieved at yet. The security of RSA encryption relies on the assumption that classical computers face significant challenges in factoring huge numbers into their prime factors. This assumption remains resilient and reliable.

2.3. Quantum Fourier Transform

QFT (Song et al., 2018; Wang et al., 2007) is a linear transformation that operates on qubits and serves as the quantum counterpart of the Discrete Fourier transform (DFT) (Rocca et al., 2022). QFT stands as a fundamental concept within the field of quantum computing. Based on the fundamental principles of quantum mechanics, QFT arises as a powerful instrument for various computing tasks, including modular exponentiation and factoring (Kulkarni & Kaushik, 2019). This research paper examines the considerable significance of QFT within the field of cryptography, factorization problem. An example can be observed in Shor’s algorithm, wherein the QFT effectively finds the period of a periodic function, which is a crucial stage in the process of factoring large integers. Furthermore, quantum simulation, optimization issues, and quantum phase estimation are further instances where QFT has been successfully employed, demonstrating its adaptability.

In this study, the utilization of QFT is selected as a method for identifying repetitive patterns to address the problem of retrieving the private key and other keys that could potentially serve as candidates for a private key in Multi-Prime RSA configurations.

In fact, the mathematical representation of QFT in relation to n qubits of quantum states $|\mathit{x}〉$ and $|\mathit{y}〉$ is defined as follows: (1) $$\mathit{\text{QFT}}{|\mathit{x}〉}_{\mathit{n}}=\left(\frac{\mathit{1}}{\sqrt{{\mathit{2}}^{\mathit{n}}}}\sum _{\mathit{y}=\mathit{0}}^{{\mathit{2}}^{\mathit{n}}-\mathit{1}}{\mathit{e}}^{\frac{\mathit{2}\pi \mathit{\text{ixy}}}{{\mathit{2}}^{\mathit{n}}}}\right){|\mathit{y}〉}_n$$(1)

2.4. Shor’s algorithm

Shor’s algorithm, proposed by P. Shor in 1994, stands as a remarkable breakthrough in quantum computing. It addresses a fundamental problem in number theory: the factorization of large integers into their prime components. This has crucial implications for cryptography, as the security of many classical encryption methods relies on the difficulty of factoring large numbers. Prior to the development of Shor’s algorithm, classical algorithms had significant challenges in efficiently factoring large integers. However, Shor’s algorithm demonstrated that a quantum computer could solve this problem exponentially faster than any classical computer. By exploiting the unique properties of qubits and quantum parallelism, Shor’s algorithm can compute the prime factors in polynomial time, a feat considered intractable for classical computers. In fact, Shor’s algorithm leverages two main principles: QFT and modular exponentiation. It uses these principles to transform the factorization problem into a period-finding problem (Zhang et al., 2007), which can be solved exponentially faster on a quantum computer.

Assume that n is generated from the multiplication between two prime numbers, there are two separate parts involved in the utilization of Shor’s technique for the retrieval two prime factors. These components consist of a quantum part and a classical part.

In the quantum domain, its purpose is to deduce the periodic outcome from the modular exponentiation equation.

Given, f(x) = a^x mod n, 1 < a < n, the procedure for recovering the periodic result, r, is as follows:

Notation:

1. The symbol is Hadamard gate to change the qubit to super position state

2. The symbol is the measurement that a qubit will collapse in pure state

3. B_f is to compute f(x) = a^x mod n

4. $|\mathit{0}〉$ is a single qubit that is equivalent to a 0

5. $|\mathit{1}〉$ is a single qubit that is equivalent to a 1

Figure 1 shows the circuit utilized for determining the value of r in the quantum domain. The process involves a total of seven sequential phases, which are outlined as follows:

Figure 1. Quantum circuit to find periodic result of modular exponentiation.

Step 1: $|{\mathit{\psi }}_{\mathit{1}}〉=|0^{\otimes \mathit{m}}〉|0^{\otimes \mathit{m}}〉$

Step 2: $|{\mathit{\psi }}_{\mathit{2}}〉=H^{\otimes \mathit{m}}|{\mathit{\psi }}_{\mathit{1}}〉=\frac{1}{\sqrt{2^n}}{\sum }_{x=0}^{2^n-1}|\mathit{x}〉|{\mathit{0}}^{\otimes \mathit{m}}〉$

Step 3: $|{\mathit{\psi }}_{\mathit{3}}〉=B_f|{\mathit{\psi }}_{\mathit{2}}〉=\frac{1}{\sqrt{2^n}}{\sum }_{x=0}^{2^n-1}|\mathit{x}〉|{\mathit{a}}^x\mathit{\text{mod}}\mathit{ n}〉$

Step 4: Measure the 2^nd Register to get $|{\mathit{\psi }}_{\mathit{4}}〉$

Step 5: Normalize $|{\mathit{\psi }}_{\mathit{4}}〉$ before using QFT to find $|{\mathit{\psi }}_{\mathit{5}}〉$

Step 6: Measure $|{\mathit{\psi }}_{\mathit{5}}〉$

Step 7: Repeat the process until r is found

After the value of r is determined, if r is an even number, it will be selected as the parameter for computation in the classical phase. On the other hand, the determination of r requires reassessment in cases when it is an odd integer. Assuming r is an even number, the next process will continue in the classical part by using the formulas below to find two prime factors: $$p_1=\mathit{\text{gcd}}(a^{\frac{r}{2}}-1,n)\text{and}{p}_2=\mathit{\text{gcd}}(a^{\frac{r}{2}}+1,n)$$ where n = p₁p₂.

3. The proposed method

This study introduces a method for determining the value of d or identifying the other keys that can also recover the original plaintext. The methodology is divided into two main phases. The first step involves the quantum aspect, utilizing QFT to determine the periodic result. The next part is focused on studying the utilization of the resultant periodicity as a significant factor in the determination of a comprehensive collection that contains the variable d and its associated alternatives. In addition, in situations when the value of n is derived from the multiplication of many prime numbers, the method under consideration demonstrates superior effectiveness when compared to Shor’s algorithm. This assumption is based on the requirement of Shor’s algorithm to perform at least two consecutive factoring operations within the quantum component, whereas the proposed method necessitates a singular step to determine the periodic outcome.

Theorem 1:

Assigning, i, j, k and h $\in \mathbb{Z},$ where k > j, j and k is the first and second minimal integers that are larger than 0, m^jr+1 mod n = m^kr+1 mod n = m and jr + 1 mod e = kr + 1 mod e = 0, then (2) $$\left(\text{jr}+\text{1}\right)+{\text{hr}}_2\text{mod e}=0$$(2) where r₂ = (k–j)r is the periodic to find d

Proof:

After the period of r is determined, it may be shown that m⁰ mod n = m^r mod n = m^2r mod n = m^3r mod n = $\cdots$= 1, therefore m¹ mod n = m^r+1 mod n = m^2r+1 mod n = m^3r+1 mod n = $\cdots$= m.

From,   jr + 1 mod e = 0

And,     kr + 1 mod e = 0

Then,   (kr + 1)–(jr + 1) mod e = 0

Or,

     (k–j)r mod e = 0

Because,   r₂ = (k–j)r,

Then,   r₂ mod e = 0

Or,     hr₂ mod e = 0, where h $\in \mathbb{Z}$  

Therefore, it implies that:

(jr + 1) + hr₂ mod e = 0                                                              

In fact, the information in Equation (2)(2) $$\left(\text{jr}+\text{1}\right)+{\text{hr}}_2\text{mod e}=0$$(2) will be utilized to determine the value of d in Theorem 2.

Theorem 2:

Assigning h $\in \mathbb{Z},$ d can be recovered by using Equation (3)(3) $$d=\frac{(\mathit{\text{jr}}\mathit{+}1)\mathit{+h}{\mathit{r}}_{\mathit{2}}}{\mathit{e}}$$(3) (3) $$d=\frac{(\mathit{\text{jr}}\mathit{+}1)\mathit{+h}{\mathit{r}}_{\mathit{2}}}{\mathit{e}}$$(3)

Proof:

From,  m = c^d mod n = (m^e)^d mod n = m^ed mod n

From Theorem 1,

 m^{jr + 1} mod n = m and m^{kr + 1} mod n = m, k > j

It implies that,

 m^(k-j)r+1 mod n = m

Or,    $m^{\mathit{h}(k-j)\mathit{r}+1}$ mod n = m

Then,

 $m^{(\mathit{j\; +\; h}(k-j))\mathit{r}+1}$ mod n = m

Or,    $m^{\mathit{\text{jr}}\mathit{+}1+\mathit{h}(k-j)\mathit{r}}$ mod n = m

Because, r₂ = (k–j)r,

 $m^{(\mathit{\text{jr}}\mathit{+}1)+\mathit{h}{\mathit{r}}_2}$ mod n = m

Then, 

  ed = (jr + 1) + hr₂

Because (jr + 1) + hr₂ mod e = 0, then it implies that the result of d = $\frac{(\mathit{\text{jr}}\mathit{+}1)\mathit{+h}{\mathit{r}}_{\mathit{2}}}{\mathit{e}}$ is certainly an integer.

Therefore,   d = $\frac{(\mathit{\text{jr}}\mathit{+}1)\mathit{+h}{\mathit{r}}_{\mathit{2}}}{\mathit{e}}$                                                

In fact, after finding r in quantum computing process, the algorithm to find d in classical computer is as follows:

Assuming d_i = {d₀, d₁, d₂, d_i-1}, t = $\frac{(\mathit{\text{jr}}\mathit{+}1)}{\mathit{e}}$ and u = $\frac{\mathit{h}{\mathit{r}}_{\mathit{2}}}{\mathit{e}},$ it implies that $$d_0=t,d_1=t+u,d_2=t+2u,\dots ,d_{i-1}=t+(i-1)u$$

Therefore, Algorithm 1 is the method to recover d_i.

Algorithm 1:

The Proposed Method (Classical Part)

Input: n, e, r

Output: d_i = {d₀, d₁, d₂, d_i-1}, i $\in \mathbb{Z}$ and one of the members is the private key

1. Find j which is the minimal integer that jr + 1 mod e = 0 and m^jr+1 mod n = m

2. Find k which is the second minimal integer (k > j) that kr + 1 mod e = 0 and m^kr+1 mod n = m

3. t ← jr + 1

4. r₂ ← (k–j)r

5. w ← 1

6. s ←$\frac{\mathit{t}}{\mathit{e}}$

7. u ← $\frac{{\mathit{r}}_{\mathit{2}}}{\mathit{e}}$

8. d₀ ← s

9. While s is less than n Do

10. s ← s + u

11. d_w ← s

12. w ← w + 1

13. End While

14. Remove d_w-1

If d_i is identified, it could be verified that one of the elements in d_i is equivalent to d. To determine the value of d, it is imperative to carefully choose multiple plaintext values and thereafter validate their correspondence with the goal through the utilization of d_i.

Example 1:

Assuming n = 77, e = 7 and m = 9, after r is calculated by using Shor’s algorithm in quantum part (r = 15), Find d_i

←Sol: From Algorithm 1,

Step 1: j = 6, (jr + 1 = 6(15) + 1 = 91, 91 mod 7 = 0)

Step 2: k = 13, (kr + 1 = 13(15) + 1 = 196, 196 mod 7 = 0)

Step 3–8: t = 91, r₂ = 105, w = 1, s = 13, u = 15 and d₀ = 13

Loop 1: 13 < 77 (the condition is true)

Step 10–12: d₁ = s = 28 and w = 2

Loop 2: 28 < 77 (the condition is true)

Step 10–12: d₂ = s = 43 and w = 3

Loop 3: 43 < 77 (the condition is true)

Step 10–12: d₃ = s = 58 and w = 4

Loop 4: 58 < 77 (the condition is true)

Step 10–12: d₄ = s = 73 and w = 5

Loop 5: 75 < 77 (the condition is true)

Step 10–12: d₅ = s = 88 and w = 6

Loop 6: 88 < 77 (the condition is false)

Therefore d_i = {13, 28, 43, 58, 73}

Example 2:

Assuming n = 77, e = 7 and m = 19, after r is calculated by using Shor’s algorithm in quantum part (r = 30), Find d_i

←Sol: From Algorithm 1,

Step 1: j = 3, (jr + 1 = 3(30) + 1 = 91, 91 mod 7 = 0)

Step 2: k = 10, (kr + 1 = 10(30) + 1 = 301, 301 mod 7 = 0)

Step 3–8: t = 91, r₂ = 210, w = 1, s = 13, u = 30 and d₀ = 13

Loop 1: 13 < 77 (the condition is true)

Step 10–12: d₁ = s = 43 and w = 2

Loop 2: 43 < 77 (the condition is true)

Step 10–12: d₂ = s = 73 and w = 3

Loop 3: 73 < 77 (the condition is true)

Step 10–12: d₃ = s = 103, w = 4

Loop 4: 103 < 77 (the condition is false)

Therefore d_i = {13, 43, 73}

The examples mentioned above demonstrate a significant implication: under the condition of constant values for e and n, distinct periods are observed for different plaintext. Therefore, it is apparent that the utilization of QFT is expected to yield frequent outcomes in the attempt to effectively reveal the private key. However, the task of deducing d necessitates a nuanced approach. In the process of selecting m values for implementation, it is crucial to pay careful attention to exclude numbers that do not accurately represent d. It is important to emphasize that the value potentially corresponding to d must consistently reflect in all occurrences of m. Given the inherent property of d as an odd number, the set is effectively purged of all even numbers, further refining the selection process.

Example 3:

Assuming n = 105, e = 5 and m = 23, after r is calculated by using Shor’s algorithm in quantum part (r = 12), Find d_i

Sol: From Algorithm 1,

Step 1: j = 2, (jr + 1 = 2(12) + 1 = 25, 25 mod 5 = 0)

Step 2: k = 7, (kr + 1 = 7(12) + 1 = 85, 85 mod 5 = 0)

Step 3–8: t = 25, r₂ = 60, w = 1, s = 5, u = 12 and d₀ = 5

Loop 1: 5 < 105 (the condition is true)

Step 10–12: d₁ = s = 17 and w = 2

Loop 2: 17 < 105 (the condition is true)

 Step 10–12: d₂ = s = 29 and w = 3

Loop 3: 29 < 105 (the condition is true)

Step 10–12: d₃ = s = 41 and w = 4

Loop 4: 41 < 105 (the condition is true)

Step 10–12: d₄ = s = 53 and w = 5

Loop 5: 53 < 105 (the condition is true)

Step 10–12: d₅ = s = 65 and w = 6

Loop 6: 65 < 105 (the condition is true)

Step 10–12: d₆ = s = 77 and w = 7

Loop 7: 77 < 105 (the condition is true)

Step 10–12: d₇ = s = 89 and w = 8

Loop 8: 89 < 105 (the condition is true)

Step 10–12: d₈ = s = 101 and w = 9

Loop 9: 101 < 105 (the condition is true)

Step 10–12: d₉ = s = 113 and w = 10

Loop 10: 113 < 105 (the condition is false)

Therefore d_i = {5, 17, 29, 41, 53, 65, 77, 89, 101}

In Example 3, the value of n is determined as 105, which can be expressed as the product of three prime numbers, 105 = (3)(5)(7). In the context of employing Shor’s algorithm for the retrieval of prime factors, it becomes imperative to address two distinct challenges within the quantum part. Specifically, when considering n as the product of three distinct primes, p₁, p₂, and p₃, the primary challenge pertains to calculate both the combinations of p₁p₂ and p₃. Additionally, the secondary challenge involves the determination of p₁ and p₂. In contrast, the proposed method requires the solution of a single quantum problem, demonstrating the efficiency and benefit inherent in its implementation.

4. Experimental results and analysis

In this section, comprehensive analysis is conducted on experimental findings obtained from smaller sample sizes, with a thorough examination of the given data. The decision to utilize lower numbers is determined by the current limitations within the quantum domain, which is still in its preliminary phases. On a contrasting note, for the classical counterpart, the selection of the BigInteger class from the Java library imparts an elegant solution, allowing for the manipulation of data without the confines of size limitations. The crucible of these experiments rests upon a computing environment featuring a 2.53 GHz Intel^® Core i5 processor, accompanied by a robust 8 GB of RAM–orchestrating an environment where uniformity in parameter control is seamlessly maintained.

The outcomes of the dᵢ and computation time for n = 105 are presented in Table 1. This value is derived from the combination of three prime numbers, 3, 5 and 7. The experimental results provide on the reliability of time measurements across all possible combinations of the variables e and m. However, it becomes evident that the value of dᵢ is greatly affected by the selection of m. Furthermore, attempting to attain improved outcomes epitomizes the most advantageous track. This necessitates the inclusion of numerous m values for the implementation to achieve the desired outcome. Intriguingly, even when m remains constant, the number of members within dᵢ exhibits stability, despite being computed from varying e values.

Table 1. Diverse results of d_i and time calculations for n = 105 across varied public keys and plaintexts.

e	m	r	di	Time (ms)
5	11	6	{5, 11, 17, 23, 29, 35, 41, 47, 53, 59, 65, 71, 77, 83, 89, 95, 101}	0.35
	13	4	{1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77, 81, 85, 89, 93, 97, 101, 105}	0.47
	23	12	{5, 17, 29, 41, 53, 65, 77, 89, 101}	0.32
7	11	6	{1, 7, 13, 19, 25, 31, 37, 43, 49, 55, 61, 67, 73, 79, 85, 91, 97, 103}	0.27
	13	4	{3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63, 67, 71, 75, 79, 83, 87, 91, 95, 99, 103}	0.32
	23	12	{7, 19, 31, 43, 55, 67, 79, 91, 103}	0.21
11	11	6	{5, 11, 17, 23, 29, 35, 41, 47, 53, 59, 65, 71, 77, 83, 89, 95, 101}	0.25
	13	4	{3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63, 67, 71, 75, 79, 83, 87, 91, 95, 99, 103}	0.33
	23	12	{11, 23, 35, 47, 59, 71, 83, 95}	0.22

The significance of bold values are the shortest period of computation for each category.

Furthermore, the data presented in Table 1 provides clear support for the selection of r as a suitable parameter for calculating d_i using the proposed method. In contrast to Shor’s algorithm, it is necessary to compute the new value when an odd integer is present as r in the computation.

In addition, this research offers a unique methodology that involves a single computational process within quantum space. This contrasts with the operational procedure of Shor’s algorithm, which requires a minimum of two sequential actions to effectively navigate the complexities associated with three prime factors.

According to the data presented in this table, it can be concluded that the value of m = 23 is the best option for determining d_i, as it corresponds to the highest value of r.

Because of the small number of n = 105, an inclusive methodology has been employed for the implementation process. This approach includes all values of m, ranging from 2 to 104, while maintaining a fixed value of e for evaluating the results. Experimental results indicate that a wide range of numbers, spanning from 1 to n, demonstrate the capacity to serve as a private key. For example, when n is assigned as 105 and e is assigned as 11, it could be concluded that d is equal to 35. However, a range of alternative exponent values arises as potential options for consideration, including 11, 23, 47, 59, 71, 83 and 95. These values exhibit a smooth alignment with the set of d_i when they are coupled with 35, as shown in Table 1. It is obvious that all the values in the final row should be considered as potential private keys. Therefore, assume many values of m are chosen for the implementation with the same e and n. The members which occur in all d_i are high possible to be chosen as the private key.

Table 2 presents the derivation of n = 2145, which is obtained through the multiplication of four distinct prime integers: 2145 = (3)(5)(11)(13). The experimental findings demonstrate a correlation with the patterns observed in Table 1. Despite the increasing number of prime numbers, the proposed method retains its inherent property of requiring a singular processing step within the quantum domain. It is important to note that, when compared to Shor’s algorithm, the proposed method effectively simplifies the computational process, resulting in a decrease of the quantum computational steps necessary for its execution.

Table 2. Diverse results of d_i and time calculations for n = 2145 across varied public keys and plaintexts.

e	m	r	di	Time (ms)
11	101	30	{11, 41, 71, 101, 131, 161, 191, 221, 251, 281, 311, 341, 371, 401, 431, 461, 491, 521, 551, 581, 611, 641, 671, 701, 731, 761, 791, 821, 851, 881, 911, 941, 971, 1001, 1031, 1061, 1091, 1121, 1151, 1181, 1211, 1241, 1271, 1301, 1331, 1361, 1391, 1421, 1451, 1481, 1511, 1541, 1571, 1601, 1631, 1661, 1691, 1721, 1751, 1781, 1811, 1841, 1871, 1901, 1931, 1961, 1991, 2021, 2051, 2081, 2111, 2141}	0.63
	113	60	{11, 71, 131, 191, 251, 311, 371, 431, 491, 551, 611, 671, 731, 791, 851, 911, 971, 1031, 1091, 1151, 1211, 1271, 1331, 1391, 1451, 1511, 1571, 1631, 1691, 1751, 1811, 1871, 1931, 1991, 2051, 2111}	0.54
17	101	30	{23, 53, 83, 113, 143, 173, 203, 233, 263, 293, 323, 353, 383, 413, 443, 473, 503, 533, 563, 593, 623, 653, 683, 713, 743, 773, 803, 833, 863, 893, 923, 953, 983, 1013, 1043, 1073, 1103, 1133, 1163, 1193, 1223, 1253, 1283, 1313, 1343, 1373, 1403, 1433, 1463, 1493, 1523, 1553, 1583, 1613, 1643, 1673, 1703, 1733, 1763, 1793, 1823, 1853, 1883, 1913, 1943, 1973, 2003, 2033, 2063, 2093, 2123}	0.67
	113	60	{53, 113, 173, 233, 293, 353, 413, 473, 533, 593, 653, 713, 773, 833, 893, 953, 1013, 1073, 1133, 1193, 1253, 1313, 1373, 1433, 1493, 1553, 1613, 1673, 1733, 1793, 1853, 1913, 1973, 2033, 2093}	0.48
23	101	30	{17, 47, 77, 107, 137, 167, 197, 227, 257, 287, 317, 347, 377, 407, 437, 467, 497, 527, 557, 587, 617, 647, 677, 707, 737, 767, 797, 827, 857, 887, 917, 947, 977, 1007, 1037, 1067, 1097, 1127, 1157, 1187, 1217, 1247, 1277, 1307, 1337, 1367, 1397, 1427, 1457, 1487, 1517, 1547, 1577, 1607, 1637, 1667, 1697, 1727, 1757, 1787, 1817, 1847, 1877, 1907, 1937, 1967, 1997, 2027, 2057, 2087, 2117}	0.69
	113	60	{47, 107, 167, 227, 287, 347, 407, 467, 527, 587, 647, 707, 767, 827, 887, 947, 1007, 1067, 1127, 1187, 1247, 1307, 1367, 1427, 1487, 1547, 1607, 1667, 1727, 1787, 1847, 1907, 1967, 2027, 2087}	0.51

However, according to the data presented in Table 2, choosing m = 113 as the value for calculating d_i is more advantageous compared to selecting m = 101, mostly because of the larger r value.Therefore, to identify the optimal outcome for d_i, it might be necessary to explore various values of m to determine the intersecting result across all d_i values.

Assigning, d_i1 is d_i of m₁, d_i2 is d_i of m₂, $\cdots ,$ d_in is d_i of m_n, then d_i that all members are high possible to be the key for decryption process can be found by using Equation (4)(4) $$d_i=d_{i1}\cap d_{i2}\cap \cdots \cap d_{\mathit{\text{in}}}$$(4) . (4) $$d_i=d_{i1}\cap d_{i2}\cap \cdots \cap d_{\mathit{\text{in}}}$$(4)

Table 3 illustrates a comparison of the processes in the quantum phase between the proposed method and Shor’s Algorithm using three different problems. The proposed method demonstrates greater efficiency compared to Shor’s algorithm across these problems.

Table 3. Comparison the process in quantum phase between the proposed method and Shor’s algorithm.

Problem	Ability in quantum part
	The proposed method	Shor’s algorithm
An odd Periodic outcome	This result can be utilized to determine di within the classical segment	This result cannot be employed to ascertain di within the classical segment
Two Primes of modulus	Any arbitrary value of r can be selected to determine the value of di within the classical section	Only even value of r can be chosen for determining the di value within the classical segment
Multi Prime (More than 2) of modulus	A single r value can be employed to resolve the outcome in the classical segment	An even value of r to identify the factors of n, some or all outcomes may not be prime factors

In fact, the primary objective of this study is to present the utilization of Shor’s method in the quantum domain to obtain the periodic result, denoted as r. Subsequently, r is chosen to compute the set of d_i in the digital component through the utilization of the proposed method. The subsequent illustration serves to demonstrate the comprehensive approach to identify d_i, which is divided into two distinct components: the quantum part and the digital part. In the following example, d_i is derived from the parameters n = 15, e = 7, and m = 2.

4.1. Quantum part

Python and Qiskit (Mounica et al., 2021) and (Fortunato et al., 2022) have been chosen as the programming languages and frameworks, respectively, for the development of the quantum circuit designed to identify periodic results. Qiskit, an open-source software development kit (SDK) designed for quantum computing, was established by IBM Research. It enables users to engage with quantum computers at the level of pulses, circuits, and application modules. The different versions of each tool within the Qiskit framework for this study are presented below by using qiskit.__qiskit_version__ .

Table

{'qiskit-terra’: '0.25.1', 'qiskit’: '0.44.1', 'qiskit-aer’: '0.12.2', 'qiskit-ignis’: None, 'qiskit-ibmq-provider’: '0.20.2', 'qiskit-nature’: '0.6.2', 'qiskit-finance’: None, 'qiskit-optimization’: '0.5.0', 'qiskit-machine-learning’: '0.6.1'}

Figure 2 depicts the quantum circuit employed in the determination of the period of the function f(x) = 2^x mod 15, utilizing the Qiskit framework. In this experimental study, a total of five qubits are allocated for the computational process. Following the completion of the measuring procedure, the value of r is revealed to be 4. As a result, this value serves as the primary determinant for the proposed method in the digital domain.

Figure 2. Shor’s algorithm in quantum part using Qiskit.

4.2. Digital part

The target will be disclosed by applying the proposed method. Indeed, when Algorithm 1 is implemented with the values r = 4, n = 15, m = 2 and e = 7, the resulting parameters are revealed as follows: j = 5, k = 12, t = 21, r₂ = 28, w = 1, s = 3 and u = 4. Therefore, the set d_i = {3, 7, 11, 15, 19} can be computed iteratively.

The Java code for determining d_i using the proposed method (Algorithm 1) is presented below. Indeed, the values of m, r, n, and e can be modified sequentially in line 22, 23, 24, and 25. In addition, the method find_MinValue() is utilized to calculate the values of j and k.

Table

1.	package find_di;
2.	import java.math.BigInteger;
3.	import java.util.ArrayList;
4.	public class Find_di {
5.	static BigInteger find_MinValue(BigInteger j, BigInteger r, BigInteger n, BigInteger e, BigInteger m){
6.	boolean t = true;
7.	BigInteger t1, t2, t3;
8.	while(t){
9.	t1 = j.multiply(r).add(BigInteger.ONE);
10.	t2 = t1.mod(e);
11.	t3 = m.modPow(t1, n);
12.	if((t2.equals(BigInteger.ZERO)) && t3.equals(m)){
13.	t = false;
14.	}
15.	else{
16.	j = j.add(BigInteger.ONE);
17.	}
18.	}
19.	return j;
20.	}
21.	public static void main(String[] args) {
22.	BigInteger m = new BigInteger("2");
23.	BigInteger r = new BigInteger("4");
24.	BigInteger n = new BigInteger("15");
25.	BigInteger e = new BigInteger("7");
26.	BigInteger j = find_MinValue(BigInteger.ONE, r, n, e, m);
27.	BigInteger k = find_MinValue(j.add(BigInteger.ONE), r, n, e, m);
28.	BigInteger t = j.multiply(r).add(BigInteger.ONE);
29.	BigInteger r2 = k.subtract(j).multiply(r);
30.	BigInteger s = t.divide(e);
31.	BigInteger u = r2.divide(e);
32.	ArrayList < BigInteger > di = new ArrayList < BigInteger>();
33.	di.add(s);
34.	while(s.min(n).equals(s)){
35.	s = s.add(u);
36.	di.add(s);
37.	}
38.	System.out.println("j = "+j);
39.	System.out.println("k = "+k);
40.	System.out.println("di = "+di);
41.	}
42.	}

5. Conclusion

This article presents an improved method for recovering RSA’s private key or alternative keys through modular exponentiation, using the QFT to derive crucial periodic outcome. The process consists of two phases: utilizing QFT in a quantum computational framework to compute modular exponentiation results, and then leveraging the periodic result to determine private key or the other values which can be selected as the private key in a classical computational setting. Notably advantageous for cases with odd periodic results, the proposed method potentially requires a single step compared to Shor’s algorithm. Furthermore, it consistently reveals the private key set and uncovers potential alternative candidates. The use of QFT ensures precise classical target execution, distinguishing it from Shor’s algorithm. This methodology holds promise for enhancing cryptographic techniques, particularly in challenging scenarios where classical methods fall short, contributing to the security of RSA-based systems.

Disclosure statement

No potential conflict of interest was reported by the author.

Additional information

Notes on contributors

Kritsanapong Somsuk

Kritsanapong Somsuk is an associate professor at the Department of Computer and Communication Engineering, Faculty of Technology, Udon Thani Rajabhat University, Udon Thani, Thailand. He obtained his M.Eng. (Computer Engineering) from Department of Computer Engineering, Faculty of Engineering, Khon Kaen University, M.Sc. (Computer Science) from Department of Computer Science, Faculty of Science, Khon Kaen University and his Ph.D. (Computer Engineering) from Department of Computer Engineering, Faculty of Engineering, Khon Kaen University. The researcher’s area of study includes computer security, cryptography, integer factorization techniques quantum computing and Shor’s algorithm.