CN-120974034-B - RSA factorization method and system based on three-dimensional space search

Abstract

The invention discloses an RSA factorization method and system based on three-dimensional space search, the method comprises the steps of obtaining RSA modulus, setting maximum iteration times Enter a circulation step, take S + ＝F + (k, p, q) and S ‑ ＝F ‑ (k, p, q) are calculated, the hyperboloid is divided into four sub-surfaces by taking S + and S ‑ as base points, if N is on one sub-surface, the (k, p, q) is output, otherwise, the sub-surface dividing step is returned, until N is found or the searching limit is ended, and if N is not found, the next k cycle is entered. The system includes a memory and a processor for performing the above-described RSA factorization method based on stereo space searching. By using the invention, the large integer decomposition task can be completed. The invention can be widely applied to the technical field of cryptography.

Inventors

• WANG XINGBO
• LIU YAN
• HUANG YANBO

Assignees

• 广州应用科技学院

Dates

Publication Date

20260508

Application Date

20250804

Claims (4)

1. 1. An RSA factorization method based on three-dimensional space search is characterized by comprising the following steps: acquiring an RSA modulus N; Setting the maximum iteration number The method comprises the following steps: taking the initial value of the cyclic variable k as k max ; At the position of Optionally one number in the interval, denoted p, in Optionally selecting a number in the interval, and marking the number as q; calculating S + ＝F + (k,p,q)＝2 k pq+q and S - ＝F - (k,p,q)＝2 k pq-q; According to the quadtree division principle, taking S + and S - as base points, respectively dividing hyperboloid F + (k, p, q) and F - (k, p, q) into four sub-curved surfaces; Performing a decision that if a group of (k, p, q) exists such that n= k pq+q or n= k pq-q, indicating that N is found on the corresponding surface, outputting the (k, p, q), if not, re-dividing the surface on the sub-surface to perform the decision, cycling the surface dividing step and the decision step until N is found or the search limit is reached; if N is not found when the search limit is reached, k=k-1, and the next cycle is entered; the loop steps are iterated until N is found or k=1 is reached.
2. 2. The RSA factorization method based on stereoscopic space search of claim 1, wherein the search mode of the method is parallel search.
3. 3. The method of RSA factorization based on stereoscopic search of claim 1, wherein the method is a serial search.
4. 4. An RSA factorization system based on stereoscopic space searching, comprising: at least one processor; at least one memory for storing at least one program; The at least one program, when executed by the at least one processor, causes the at least one processor to implement an RSA factorization method based on a stereoscopic space search as claimed in any one of claims 1-3.

Description

RSA factorization method and system based on three-dimensional space search Technical Field The invention relates to the technical field of cryptography, in particular to an RSA factorization method and system based on three-dimensional space search. Background Integer decomposition (Integer Factorization) in cryptography refers to the process of decomposing an integer into products of two or more prime numbers. This process is central in modern cryptography, especially for the security of encryption algorithms such as RSA public key cryptosystems. The difficulty of integer decomposition depends on the size, form of a given number and its distribution of quality factors. For large integers, especially half-primes (i.e. the product of two different primes), the decomposition process is extremely difficult. There is no known polynomial time algorithm that can efficiently accomplish integer decomposition. Thus, integer decomposition is considered a "One-way Problem", i.e., easy to generate but difficult to solve in the reverse direction. The difficulty of integer decomposition is the theoretical basis for the security of many modern cryptosystems. For example, RSA public key cryptosystems are designed based on the difficulty of large integer decomposition. In the RSA system, the key generation process involves selecting two large prime numbers p and q and calculating their product n=pq. Encryption and decryption operations rely on modulo n operations. Since the difficulty of recovering p and q from n is extremely high, the security of RSA is ensured. Today, decomposition of large integers has been a difficult problem and no efficient decomposition method has emerged. Disclosure of Invention In view of this, in order to solve the technical problem of low decomposition efficiency in the existing integer decomposition method, the invention provides an RSA factorization method based on three-dimensional space search, which comprises the following steps: acquiring an RSA modulus N; the maximum number of iterations k max is set, Let the current iteration number k=k max, enter the iteration step: Taking at will Calculating S +＝F+(k,p,q)＝2k pq+q and S- =f- (k, p, q) =2 k pq-q; According to the quadtree partitioning principle, hyperboloid F + (k, p, q) and F - (k, p, q) are divided into four sub-surfaces, respectively, using S + and S - as base points, e.g And Judging if N is inOn, i.e. there is a set (k, p, q) such that n=2 k pq+q or n=2 k pq-q, output (k, p, q), stopping the operation, otherwise recursivelyRepeatedly dividing search and judgment until N is found or the search limit is terminated; if N is not found, judging that the k value fails, subtracting one from the k value, and then entering the next cycle; If N is not found yet when k becomes 1, then N decomposition failure is determined. In some embodiments, the RSA factorization method may be either serial or parallel. Based on the scheme, the invention provides an RSA factorization method and an RSA factorization system based on three-dimensional space search, which can efficiently search the factor of N by converting an RSA modulus N into data which can be represented in a three-dimensional cube with the height not exceeding log 2 N, dividing the data into log 2 N layers and performing recursive search by implementing a four-way search method on each layer. Drawings Fig. 1 is a perspective search space of an embodiment of the present invention. Detailed Description The following description of the embodiments of the present application will be made clearly and completely with reference to the accompanying drawings, in which it is apparent that the embodiments described are only some embodiments of the present application, but not all embodiments. All other embodiments, which can be made by those skilled in the art based on the embodiments of the application without making any inventive effort, are intended to be within the scope of the application. For convenience of description, only a portion related to the present application is shown in the drawings. Embodiments of the application and features of the embodiments may be combined with each other without conflict. It is to be understood that the terms "system," "apparatus," "unit," and/or "module" as used herein are one means for distinguishing between different components, elements, parts, portions, or assemblies at different levels. However, if other words can achieve the same purpose, the word can be replaced by other expressions. As used in the specification and in the claims, the terms "a," "an," "the," and/or "the" are not specific to a singular, but may include a plurality, unless the context clearly dictates otherwise. In general, the terms "comprises" and "comprising" merely indicate that the steps and elements are explicitly identified, and they do not constitute an exclusive list, as other steps or elements may be included in a method or apparatus. The inclusion of an element as defined by the