Search

CN-122027156-A - Prime power RSA modular decomposition method, system, medium and equipment

CN122027156ACN 122027156 ACN122027156 ACN 122027156ACN-122027156-A

Abstract

The invention discloses a prime power RSA modulus decomposition method, a system, a medium and equipment, wherein the method comprises the following steps of utilizing a private key Part of the high order bits of the leakage, the RSA modulus of prime powers Small public key exponent Obtain the information Using the obtained information to recover prime numbers The partial information of (a) specifically comprises constructing a modular equation to solve prime numbers Constructing two functions, approximating prime numbers by using binary search mode by utilizing magnitude relation of function values Obtaining prime numbers Partial high bit information; using recovered primes Constructing a one-time modular equation, and recovering the complete prime number by combining Coppersmith algorithm Using prime numbers Sum modulus Decomposition of . The invention utilizes fewer private keys Bit information, complete modulus The decomposition of (2) realizes the security analysis of the prime power RSA cryptographic algorithm.

Inventors

  • LIU ZHEN
  • LIU HAIYANG
  • Xiao Guanju
  • Pi Shuhuan
  • LI LISHA

Assignees

  • 湖北大学

Dates

Publication Date
20260512
Application Date
20260205

Claims (8)

  1. 1. A prime power RSA modulus decomposition method is characterized by comprising the following steps: RSA modulus of prime powers Small public key index And full size private key , Wherein the prime powers RSA modulus Private key Wherein As a prime number in the cryptographic algorithm, , ; Using private keys Part of the high order bits of the leakage, the RSA modulus of prime powers Small public key exponent Is obtained from the information of (a) Is a value of (2); Recovering prime numbers using the obtained information Constructing a modular equation to solve prime numbers Constructing two functions, approximating prime numbers by using binary search mode by utilizing magnitude relation of function values Obtaining prime numbers Part of the high order bit information of (2); Using recovered primes Constructing a one-time modular equation, and recovering the complete prime number by combining Coppersmith algorithm ; Using prime numbers Sum prime power RSA modulus Decomposing the prime power RSA modulus 。
  2. 2. The method of claim 1, wherein a private key is utilized Part of the high order bits of the leakage, the RSA modulus of prime powers Small public key exponent Is obtained from the information of (a) The specific steps of the values of (a) are: collecting RSA modulus of prime powers Public key And private key Part of the high order bit information that is leaked is noted as ; According to , And Calculation of , And (3) with The difference between them is small, through poor search A nearby section is obtained Is recorded as the exact value of (2) Wherein Is that Is a similar value to (a) in the above.
  3. 3. The method of claim 2, wherein the prime numbers are recovered using the obtained information The specific steps of the partial information of (a) are as follows: According to , , , Obtaining Is a part of the information of: construction equation Wherein = Solving the equation to obtain Is recorded as the value of ; Respectively constructing two functions Wherein Using the magnitude relation of the two functions to find prime numbers Is recorded as a high-order approximation of ; The specific details are as follows: easily-known Definition of , , ; Mode 1 if Then update in order , , If (3) Then update in order , ; When (when) At the time, the method is continuously updated in the mode 1 , , To thereby narrow the interval ; When (when) At this time As a means of Is a value of (a).
  4. 4. The method of claim 3, wherein an equation is constructed Wherein Solving the model equation by Coppersmith algorithm Obtaining the root of the Chinese herb Equation of substitution Obtaining prime numbers 。
  5. 5. The method of claim 4, wherein prime numbers are utilized And Calculated prime number RSA modulus of prime powers The decomposition is completed.
  6. 6. A prime power RSA modulus decomposition system, characterized by being adapted to perform the steps of the prime power RSA modulus decomposition method of any one of claims 1-5.
  7. 7. A computer-readable storage medium, on which a computer program is stored, characterized in that the program, when being executed by a processor, implements the steps of the prime power RSA modulus decomposition method according to any one of claims 1 to 5.
  8. 8. A computer device comprising a memory, a processor and a computer program stored on the memory and executable on the processor, wherein the processor performs the steps in the prime power RSA modulus decomposition method according to any one of claims 1 to 5 when the program is executed.

Description

Prime power RSA modular decomposition method, system, medium and equipment Technical Field The invention belongs to the technical field of information security, and particularly relates to a prime power RSA modulus decomposition method, a prime power RSA modulus decomposition system, a prime power RSA modulus decomposition medium and prime power RSA modulus decomposition equipment. Background In the field of public key cryptography, RSA has been the most commonly used cryptographic algorithm since its proposal in 1978 by Rivest, shamir and Adleman. Wiener has proposed an important conclusion about RSA that if the private key isThe modulus can be decomposed in polynomial time. Later Boneh and durbee improved this limit to。 For efficiency and safety considerations, a number of RSA variant algorithms have emerged. Among them, prime power RSA has received extensive attention, its modulusIs in the form of(Wherein),. Such a kind ofThe modulus of the form was used at the earliest by Fujioka et al in European cipher conference 1991, on European cipher conference 1998, okamoto et al also adoptedTo design public key cryptosystems. In 1996 Crypto conference, kocher proposed a new attack mode, namely a partial key leakage attack for the first time. He indicates that an attacker can obtain the private key by analyzing the timing characteristics of the RSA encryption deviceIs a part of bit information of the (b). In recent years, with the rise of side channel attack technologies such as fault attack and power consumption analysis, an attacker can acquire part of information of a private key from physical manifestation of an encryption device. These advances have made the partial key-leakage attack of RSA one of the research hotspots in this field. May studied the modulus in PKC conference 2004Partial key leakage attack of prime power RSA. I.e. when the private key is knownHigh order bit information of (2)Satisfy the following requirementsWhen it is used, it can be decomposed in polynomial time. Lu et al optimized the above results, demonstrating that whenCan be completed in timeIs decomposed. Sakar et al subsequently studied on private keysIn the case of (1)Can be completed in timeIs decomposed. While RSA-type cryptographic algorithms involve modular exponentiation, the use of a small public key exponent may improve system performance by reducing the number of modular exponentiations, which is particularly important in scenarios where a large number of users verify signatures at the same time or server-side encryption is frequent. Although the prior art focuses on the key leakage attack of prime power RSA, under the small private key exponent, the partial private key leakage attack still has the optimization space. Once the modulus is decomposed, the private key is also compromised so that further attacks or security analysis can be performed. Disclosure of Invention In view of the above problems, the present invention provides a method for decomposing modulus in the case of leakage of high bits of small public key exponent and private key dIs a method of (2). The private key can be recovered by modulus decompositionThereby realizing the security analysis of the prime power RSA cryptographic algorithm. Aiming at prime number power RSA cryptographic algorithm, the invention utilizes the full-size private key under the condition of small public key index() Information of high bit leakage, design method for recovering prime factorsIs finally combined with Coppersmith algorithm to recover the complete prime factorsCompleting the modulusAnd (5) decomposing. Compared with the prior art, the invention can utilize fewer private keysBit information, complete modulusThis presents a certain challenge to the security of small public key exponential prime power RSA cryptographic algorithms. In order to solve one of the above technical problems, according to an aspect of the present invention, there is provided a prime power RSA modulus decomposition method, including the steps of: RSA modulus of prime powers Small public key indexAnd full size private key() Wherein the prime powers RSA modulusPrivate keyWhereinAs a prime number in the cryptographic algorithm,,; Using private keysPart of the high order bits of the leakage, the RSA modulus of prime powersSmall public key exponentIs obtained from the information of (a)Is a value of (2); Recovering prime numbers using the obtained information Constructing a modular equation to solve prime numbersConstructing two functions, approximating prime numbers by using binary search mode by utilizing magnitude relation of function valuesObtaining prime numbersPartial high bit information; Using recovered primes Constructing a one-time modular equation, and recovering the complete prime number by combining Coppersmith algorithm; Using prime numbersSum prime power RSA modulusDecomposing the prime power RSA modulus。 Further, private key is utilizedPart of the high order bits of the leakage, the RSA m