CN-121547179-B - RSA algorithm key cracking method, RSA algorithm key cracking device, electronic equipment and storage medium

CN121547179BCN 121547179 BCN121547179 BCN 121547179BCN-121547179-B

Abstract

The invention belongs to the field of information security, and relates to a method, a device, an electronic device and a storage medium for cracking an RSA algorithm key, wherein the method comprises the steps of utilizing a known prime database to obtain half prime numbers from the RSA key Trial removal was performed assuming that , , Is a natural number, is an intermediate variable in the Fermat decomposition method, All are prime numbers, determining whether a predefined prime number is contained or not by trial division, determining the lower bound of a traversal parameter, dividing the traversal range into a plurality of subareas, dynamically distributing the subareas to parallel computing nodes to realize task-level parallelization, executing traversal computation on each parallel node, and positioning the nodes by multistage screening and step optimization Natural number being the complete square number And verifying the candidate solution obtained by node calculation, and adding the prime factors obtained by decomposition into a known prime database. The factorization and cracking calculation speed can be greatly improved.

Inventors

QI JIANHUAI
HU JINHUA
WANG MINGSHUAI
HAN DANDAN
LI YUXIN
WANG YINCHENG
ZHENG WEIFAN
CHENG YANG
XU GUOQIAN

Assignees

深圳市永达电子信息股份有限公司

Dates

Publication Date: 20260512
Application Date: 20260121

Claims (10)

1. The method for cracking the RSA algorithm key is characterized by comprising the following steps: for half prime numbers obtained from RSA keys using a library of known prime numbers accumulated in the historical decomposition results Trial removal was performed assuming that , , Is a natural number, is an intermediate variable in the Fermat decomposition method, Are all prime numbers, are half prime numbers Is a factor of two of (1); If half prime number Cannot be directly decomposed by a known prime database, and then half prime numbers are judged by trial and error of a group of predefined prime numbers Whether the decomposition factors are contained or not, and determining the lower bound of the traversal parameters; dividing the traversal range into a plurality of subareas, dynamically distributing the subareas to parallel computing nodes, and realizing task-level parallelization; Performing traversal calculation on each parallel node, and positioning by multistage screening and step optimization Natural number being the complete square number ; Verifying the candidate solution obtained by node calculation to ensure that the decomposition result is correct and correct; And adding prime factors obtained by successful decomposition into a known prime database, and updating the access frequency of the prime factors to realize the self-optimization of the system.
2. The method according to claim 1, wherein the known prime number library accumulated in the historical decomposition result is used for obtaining half prime numbers from the RSA key Trial removal was performed assuming that , , Is a natural number, is an intermediate variable in the Fermat decomposition method, Are all prime numbers, are half prime numbers The steps of the two factors of (a) specifically include: based on half-primes derived from RSA keys Searching and matching in a known prime number library accumulated in the historical decomposition result; Assume that , All are prime numbers, and the accessed frequency is recorded for each prime number in a known prime number library, and the prime numbers are arranged according to the descending order of frequency during searching, so that the high-frequency prime numbers are preferentially detected.
3. The method of claim 1, wherein the half prime numbers are the same as the half prime numbers Cannot be directly decomposed by a known prime database, and then half prime numbers are judged by trial and error of a group of predefined prime numbers The step of determining whether the decomposition factor is contained or not and determining the lower bound of the traversal parameter specifically includes: generating a dynamic prime number set according to Dynamic determination of small prime number set Wherein Is associated with A configurable parameter related to the number of bits; Performing integer division judgment; If all small prime numbers cannot be divided Record the maximum trial divisor As prime numbers To derive natural number Is the traversal upper limit of (c).
4. A method for decrypting an RSA algorithm key according to claim 3, wherein the step of dividing the traversal range into a plurality of sub-regions and dynamically allocating the plurality of sub-regions to the parallel computing nodes, and implementing task-level parallelization specifically comprises: calculating the traversing range, and calculating natural numbers according to prime number filtering results Upper and lower bounds of (2); performing dynamic division of traversal regions, and dividing natural numbers Dynamic division of successive intervals of (a) into A sub-region in which ; And intelligent task scheduling and load balancing are performed, a master-slave architecture is adopted, and a master node is responsible for task allocation, state monitoring and fault tolerance processing.
5. The method of claim 1, wherein the performing traversal computation on each parallel node locates by multi-level filtering and step optimization Natural number being the complete square number The method specifically comprises the following steps: Using the limited possibility of the last two digits of the full square number, the invalid natural number is eliminated ; Performing dynamic multimode secondary residual screening; dynamic step optimization is performed when the natural number By screening but When the number is not the full square number, the minimum jump step length is calculated Intermediate invalid values are skipped.
6. The method for decrypting the RSA algorithm key according to claim 1, wherein the step of verifying the candidate solution obtained by the node calculation to ensure that the decomposition result is correct comprises: Performing complete square number confirmation, and returning natural number to node Recalculating And verify Whether or not it is an integer; Performing factor calculation and product verification, and calculating according to the Fermat decomposition formula And And verifies whether the product is ; Performing result output and exception handling, and outputting if the verification is passed And Otherwise, returning an error state, and triggering recalculation or task redistribution.
7. The method for decrypting the RSA algorithm key according to any one of claims 1 to 6, wherein the step of adding the prime factors obtained by successful decomposition to a known prime library and updating the access frequency thereof to achieve the self-optimization of the system specifically comprises: performing factor de-duplication and merging, and checking newly obtained prime numbers Sum prime number Whether or not it is already present in the prime number library; frequency sorting optimization is carried out, and a prime number library is reordered according to hit counts, so that high-frequency prime numbers are retrieved preferentially; And carrying out prime number library persistence and version management, storing the prime number library in a periodical persistence manner, and supporting version backtracking and merging.
8. An apparatus for cracking an RSA algorithm key, comprising: A trial-division module for dividing half prime numbers obtained from RSA key by using the known prime number library accumulated in the historical decomposition result Trial removal was performed assuming that , , Is a natural number, is an intermediate variable in the Fermat decomposition method, Are all prime numbers, are half prime numbers Is a factor of two of (1); a judging module for judging if half prime number Cannot be directly decomposed by a known prime database, and then half prime numbers are judged by trial and error of a group of predefined prime numbers Whether the decomposition factors are contained or not, and determining the lower bound of the traversal parameters; The distribution module is used for dividing the traversal range into a plurality of subareas and dynamically distributing the subareas to the parallel computing nodes so as to realize task-level parallelization; The calculation module is used for executing traversal calculation on each parallel node, and positioning the nodes through multi-stage screening and step optimization Natural number being the complete square number ; The verification module is used for verifying the candidate solution obtained by node calculation to ensure that the decomposition result is correct; and the updating module is used for adding prime factors obtained by successful decomposition into a known prime database, and updating the access frequency of the prime factors to realize the self-optimization of the system.
9. An electronic device comprising a memory and a processor, the memory having stored therein computer readable instructions which when executed by the processor implement the steps of the RSA algorithm key cracking method of any one of claims 1 to 7.
10. A computer readable storage medium having stored thereon computer readable instructions which when executed by a processor implement the steps of the RSA algorithm key cracking method of any one of claims 1 to 7.

Description

RSA algorithm key cracking method, RSA algorithm key cracking device, electronic equipment and storage medium Technical Field The present invention relates to the field of information security technologies, and in particular, to a method and an apparatus for cracking an RSA algorithm key, an electronic device, and a storage medium. Background Password security is a key stone of modern network information security. The proposal of RSA encryption algorithm marks the modern cryptography to enter a new era. The security guarantee is that when the RSA encryption algorithm mainly adopts the principle that most prime numbers are decomposed into two prime factors, each public key corresponds to a unique private key due to the uniqueness of a decomposition result, and meanwhile, when the half prime number N is large enough, the private key is reversely deduced from the public large number N and is basically equivalent to decomposing N into original prime factors p and q, so that the decomposition difficulty is huge. Therefore, the computational complexity based on the large integer decomposition problem directly determines the security of the RSA cryptographic algorithm. For the problem of large number decomposition related to RSA encryption algorithm, researchers have proposed many more common factorization methods, and the main methods mainly comprise a trial method, a Fermat decomposition method, a Polard 'srho decomposition method, a Polard's P-1 decomposition method, a Dixon decomposition method, a continuous fraction decomposition method, a secondary screening method, a number domain screening method, an elliptic curve method, a quantum algorithm (requiring a quantum computer) and the like. When N is greater than a certain degree (e.g., on the order of 2 2048), the computational and time requirements required by the prior art methods tend to be enormous and thus difficult to crack. In order to evaluate the security of the RSA encryption algorithm, a method and a system for large-number decomposition in a limited computing resource and time range are needed to verify the security of the specific engineering implementation process of the RSA encryption algorithm with higher bit number. Disclosure of Invention In order to solve the technical problems, on the one hand, the invention provides a method for cracking an RSA algorithm key, which adopts the following technical scheme that the method comprises the following steps: for half prime numbers obtained from RSA keys using a library of known prime numbers accumulated in the historical decomposition results Trial removal was performed assuming that,,Is a natural number, is an intermediate variable in the Fermat decomposition method,Are all prime numbers, are half prime numbersIs a factor of two of (1); If half prime number Cannot be directly decomposed by a known prime database, and then half prime numbers are judged by trial and error of a group of predefined prime numbersWhether the decomposition factors are contained or not, and determining the lower bound of the traversal parameters; dividing the traversal range into a plurality of subareas, dynamically distributing the subareas to parallel computing nodes, and realizing task-level parallelization; Performing traversal calculation on each parallel node, and positioning by multistage screening and step optimization Natural number being the complete square number; Verifying the candidate solution obtained by node calculation to ensure that the decomposition result is correct and correct; And adding prime factors obtained by successful decomposition into a known prime database, and updating the access frequency of the prime factors to realize the self-optimization of the system. Preferably, the known prime number library accumulated in the historical decomposition result is used for obtaining half prime numbers from RSA keysTrial removal was performed assuming that,,Is a natural number, is an intermediate variable in the Fermat decomposition method,Are all prime numbers, are half prime numbersThe steps of the two factors of (a) specifically include: based on half-primes derived from RSA keys Searching and matching in a known prime number library accumulated in the historical decomposition result; Assume that ,All are prime numbers, and the accessed frequency is recorded for each prime number in a known prime number library, and the prime numbers are arranged according to the descending order of frequency during searching, so that the high-frequency prime numbers are preferentially detected. Preferably, the several half prime numbersCannot be directly decomposed by a known prime database, and then half prime numbers are judged by trial and error of a group of predefined prime numbersThe step of determining whether the decomposition factor is contained or not and determining the lower bound of the traversal parameter specifically includes: generating a dynamic prime number set according to Dynamic determination of