CN111193593B - RSA public key password cracking method - Google Patents

Abstract

The invention discloses a method for cracking RSA public key ciphers. By establishing a prime number factorial table in advance, only 234 columns of tables are needed to include all prime factor combinations of integers with 617 decimal digits (RSA‑2048 is 617 digits), namely To decompose an integer with a maximum of 617 decimal digits, you only need to traverse the prime factorial table with about 132 columns at most, find the candidate numbers in each column and add them up. With the traditional need to traverse all not greater than

Compared with the trial division integer decomposition method, the number of comparisons and the amount of calculation are reduced. It provides a useful reference for the security analysis of the RSA encryption algorithm; the present invention is a method that can quickly decompose a composite number with two factors whose digits are relatively close, and it is mainly used in the scene of RSA large modulus decomposition, which has a large impact on the utilization of decomposition The attack method of modulus cracking the RSA cryptosystem has a promotion effect.

Description

A method for cracking RSA public key password

Technical Field

The present invention relates to the technical field of integer decomposition, and in particular to a method for cracking an RSA public key password.

Background Art

With the introduction of prime numbers and the fundamental theorem of arithmetic, the concept of integer factorization came into being as early as 300 BC. The early development of mathematics was mainly driven by daily life and business, and integer factorization did not play a big role in these two fields, so the research on integer factorization could only rely on interest. It was not until the late 1970s that the study of public key cryptography became the main driving force for the study of integer factorization. Trial division is the earliest known integer factorization method. Fermat proposed some ideas about integer factorization in 1643, which are still at the core of integer factorization today. Fermat proposed to write an integer as the difference of two square numbers. If a composite number N is known, try to find two integers x and y so that N can be written as, then the two factors of N are and.

As a prolific mathematician, Euler also studied the problem of integer decomposition and developed Fermat's method. But Euler's method only focuses on integers with special forms, such as. Euler's method is similar to Fermat's, finding two integers x and y so that N can be written as above. Using this method, Euler successfully decomposed some larger integers at the time. French mathematician Legendre proposed a method based on the congruence of squares, which is the core of many modern integer decompositions. But at that time, computing power was limited, and Legendre's decomposition method could only decompose a limited number of integers. When computing power is more considerable, Legendre's method is indeed the most effective decomposition method. In 1801, German mathematician Gauss published his book "Disquisitiones Arithmeticae". The book mentions many ideas and methods about integer decomposition. Gauss's method is very complicated but can be compared to the sieve of Ehrlich. In simple terms, this method eliminates many prime numbers that may be factors by finding a large number of quadratic residues modulo n. This screening idea is the most important idea in modern integer decomposition methods. For many years after Legendre and Gauss, no new integer decomposition methods appeared. Even with Legendre and Gauss's method, decomposing 10-15 digit integers still requires a lot of work due to limited computing power.

In the late 19th century, several people around the world independently built various machines for performing tedious calculations. In 1896, Lawrence described a machine that used a movable paper tape passing through a movable gear, where the number of teeth represented the exclusion modulus and the position of the penetration on the paper represented the acceptable remainder. Although this machine was never actually built, it inspired others to build similar machines. After 1910, Maurice Kraitchik built a machine using Lawrence's ideas. At the same time, Geraerardin and the Carissan brothers built similar machines, but after World War I, the Carissan brothers built the first viable sieving machine that showed good results (the machine was manually operated). The most successful machine builder was Lehmer, who seemed unaware of the work of the Carissans and Kraitchiks for many years and built a large number of sieving devices, some of which advanced the modern technology of his time. Kraitchik and Lehmer's machines and the algorithms they used were very similar to the quadratic sieving algorithms that were later developed.

It was not until the 1970s that the study of integer decomposition became practical due to the improvement of computer computing power and the development of public key cryptography. John Pollard proposed an algorithm in 1974, and a year later he proposed another algorithm. Both algorithms are only for special forms of integers. In 1975, Morrison and Brillhart proposed the continued fraction decomposition algorithm, which was the first fast decomposition algorithm applicable to all integers. In 1982, Carl Pomerance proposed the quadratic sieve. Using the quadratic sieve, the number of bits of integer decomposition was increased to 71 bits in 1983. On August 31, 1988, John Pollard wrote a letter to A.M.Odlyzko and forwarded a copy to Richard P.Brent, J.Brillhart, H.W.Lenstra, C.P.Schnorr and H.Suyama. In this letter, John Pollard proposed the idea of using algebraic number fields to decompose special forms of integers. Soon after, the number field sieve method was formally proposed. The number field sieve method is the most complex integer decomposition algorithm, but it is currently the fastest integer decomposition algorithm. The number field sieve method has successfully decomposed 768 bits. However, the number field sieve method is a probabilistic integer decomposition method with a certain degree of randomness, so there are few breakthroughs in the field of integer decomposition.

Summary of the invention

The purpose of the present invention is to avoid the shortcomings of the prior art and provide a RSA public key cryptography decryption method.

In order to solve the above technical problems, a technical solution adopted by the present invention is: to provide an RSA public key password cracking method, comprising:

The natural numbers are divided into regions with different prime factorials as intervals, and a prime factorial table is established according to the region size and region boundary; wherein, the construction principle of the prime factorial table is: the integers in the first row of each column represent the product of the first n prime factorials, denoted as P _n !, and the numbers in the remaining rows of each column are the products of the numbers in the first row multiplied in sequence by a positive integer not greater than the n+1th prime number p _n+1 ;

的位数，记其位数为s；Get the modulus of the RSA public key cipher, record the modulus as M, take the square root of M and round it, and calculate

The number of digits is recorded as s;

整除

Use the first row element of the corresponding digit column s in the prime factorial table

Divisibility

Among them, Q means that the number in the Qth row is selected in the sth column as the middle number for subsequent search for prime factors;

Take the sth column and Qth row as the middle number, select an integer a ₀ and b ₀ in the upper and lower directions of the Qth row, multiply them, and subtract them from the middle number, traverse all possible values, and select the set of numbers with the smallest difference;

Find two integers _ai and b _i in the si-th column such that the difference between ( _a0 + _a1 +…+a _i )·( _b0 + _b1 +…+b _i ) and the modulus M of the RSA public key cryptography is minimal; if any two integers have ( _a0 + _a1 +…+a _i )·( _b0 + _b1 +…+b _i )>M, then only one number is selected from this column and the other integer is set to 0, that is,

(a ₀ +a ₁ +…+a _i-1 +0)·(b ₀ +b ₁ +…+b _{i_1} +b _i )

or

(a ₀ +a ₁ +…+a _i-1 +a _i )·(b ₀ +b ₁ +…+b _{i_1} +0)

This step is repeated column by column until the second column;

的位数，记其位数为s；Get the modulus of the RSA public key cipher, record the modulus as M, take the square root of M and round it, and calculate

The number of digits is recorded as s;

整除

Use the first row element of the corresponding digit column s in the prime factorial table

Divisibility

Among them, Q means that the number in the Qth row is selected in the sth column as the middle number for subsequent search for prime factors;

Take the sth column and Qth row as the middle number, select an integer a ₀ and b ₀ in the upper and lower directions of the Qth row, multiply them, and subtract them from the middle number, traverse all possible values, and select a set of numbers with the smallest difference;

Find two integers _ai and b _i in the si-th column such that the difference between ( _a0 + _a1 +…+a _i )·( _b0 + _b1 +…+b _i ) and the modulus M of the RSA public key cryptography is minimal; if any two integers have ( _a0 + _a1 +…+a _i )·( _b0 + _b1 +…+b _i )>M, then only one number is selected from this column and the other integer is set to 0, that is,

(a ₀ +a ₁ +…+a _{i_1} +0)·(b ₀ +b ₁ +…+b _i-1 +b _i )

or

(a ₀ +a ₁ +…+a _{i_1} +a _i )·(b ₀ +b ₁ +…+b _i-1 +0)

This step is repeated column by column until the second column;

Determine the prime factor type of the modulus M. If M is an integer of type M = 6n+1, then find two integers α ₁ and α ₂ or ε ₁ and ε ₂ in the 6n+1 prime numbers in the attribute column, such that

(a ₀ +a ₁ +…+a _i +α ₁ )·(b ₀ +b ₁ +…+b _i +α ₂ )=M

or

(a ₀ +a ₁ +…+a _i +ε ₁ )·(b ₀ +b ₁ +…+b _i +ε ₁ )=M

If M is a composite number of type M=6n-1, then find an integer α ₁ and ε ₁ in the 6n+1 region and 6n-1 region of the attribute column respectively, so that

(a ₀ +a ₁ +…+a _i +α ₁ )·(b ₀ +b ₁ +…+b _i +ε ₁ )=M

or

(a ₀ +a ₁ +…+a _i +ε ₁ )·(b ₀ +b ₁ +…+b _i +α ₁ )=M

Then find the two prime factors of the modulus M and crack the RSA public key cryptography.

的试除整数分解方法相比，降低了比较次数和计算量。为RSA加密算法的安全性分析提供了有益参考。Different from the prior art, the RSA public key password cracking method of the present invention establishes a prime factorial table in advance, and only needs a table of 234 columns to include all prime factor combinations of integers with 617 decimal digits (RSA-2048 is 617 digits). That is, to decompose an integer with a maximum of 617 decimal digits, it is only necessary to traverse the prime factorial table of about 132 columns at most, find the candidate numbers in each column and add them up.

Compared with the trial division integer decomposition method, it reduces the number of comparisons and the amount of calculation. It provides a useful reference for the security analysis of the RSA encryption algorithm.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG1 is a logic diagram of an RSA public key password cracking method provided by the present invention;

FIG. 2 is a schematic diagram of a flow chart of selecting candidate numbers for each column in a method for cracking an RSA public key password provided by the present invention.

DETAILED DESCRIPTION

The technical solution of the present invention is further described in more detail below in conjunction with specific implementation methods. Obviously, the described embodiments are only part of the embodiments of the present invention, rather than all of the embodiments. Based on the embodiments of the present invention, all other embodiments obtained by ordinary technicians in this field without making creative work should belong to the scope of protection of the present invention.

As shown in FIG1 , the present invention provides a method for cracking an RSA public key password, comprising the steps of:

The natural numbers are divided into regions with different prime factorials as intervals, and a prime factorial table is established according to the region size and region boundary; wherein, the construction principle of the prime factorial table is: the integers in the first row of each column represent the product of the first n prime factorials, denoted as P _n !, and the numbers in the remaining rows of each column are the products of the numbers in the first row multiplied in sequence by a positive integer not greater than the n+1th prime number p _n+1 ;

的位数，记其位数为s；Get the modulus of the RSA public key cipher, record the modulus as M, take the square root of M and round it, and calculate

The number of digits is recorded as s;

整除

Use the first row element of the corresponding digit column s in the prime factorial table

Divisibility

Among them, Q means that the number in the Qth row is selected in the sth column as the middle number for subsequent search for prime factors;

Take the sth column and Qth row as the middle number, select an integer a ₀ and b ₀ in the upper and lower directions of the Qth row, multiply them, and subtract them from the middle number, traverse all possible values, and select the set of numbers with the smallest difference;

Find two integers _ai and b _i in the si-th column such that the difference between ( _a0 + _a1 +…+a _i )·( _b0 + _b1 +…+b _i ) and the modulus M of the RSA public key cryptography is minimal; if any two integers have ( _a0 + _a1 +…+a _i )·( _b0 + _b1 +…+b _i )>M, then only one number is selected from this column and the other integer is set to 0, that is,

(a ₀ +a ₁ +…+a _i-1 +0)·(b ₀ +b ₁ +…+b _i-1 +b _i )

or

(a ₀ +a ₁ +…+a _i-1 +ai)·(b ₀ +b ₁ +…+b _i-1 +0)

This step is repeated column by column until the second column;

的位数，记其位数为s；Get the modulus of the RSA public key cipher, record the modulus as M, take the square root of M and round it, and calculate

The number of digits is recorded as s;

整除

Use the first row element of the corresponding digit column s in the prime factorial table

Divisibility

Among them, Q means that the number in the Qth row is selected in the sth column as the middle number for subsequent search for prime factors;

Take the sth column and Qth row as the middle number, select an integer a ₀ and b ₀ in the upper and lower directions of the Qth row, multiply them, and subtract them from the middle number, traverse all possible values, and select a set of numbers with the smallest difference;

Find two integers _ai and b _i in the si-th column such that the difference between ( _a0 + _a1 +…+a _i )·( _b0 + _b1 +…+b _i ) and the modulus M of the RSA public key cryptography is minimal; if any two integers have ( _a0 + _a1 +…+a _i )·( _b0 + _b1 +…+b _i )>M, then only one number is selected from this column and the other integer is set to 0, that is,

(a ₀ +a ₁ +…+a _{i_1} +0)·(b ₀ +b ₁ +…+b _{i_1} +b _i )

or

(a ₀ +a ₁ +…+a _{i_1} +ai)·(b ₀ +b ₁ +…+b _{i_1} +0)

This step is repeated column by column until the second column;

Determine the prime factor type of the modulus M. If M is an integer of type M = 6n+1, then find two integers α ₁ and α ₂ or ε ₁ and ε ₂ in the 6n+1 prime numbers in the attribute column, such that

(a ₀ +a ₁ +…+a _i +α ₁ )·(b ₀ +b ₁ +…+b _i +α ₂ )=M

or

(a ₀ +a ₁ +…+a _i +ε ₁ )·(b ₀ +b ₁ +…+b _i +ε ₁ )=M

If M is a composite number of type M=6n-1, then find an integer α ₁ and ε ₁ in the 6n+1 region and 6n-1 region of the attribute column respectively, so that

(a ₀ +a ₁ +…+a _i +α ₁ )·(b ₀ +b ₁ +…+b _i +ε ₁ )=M

or

(a ₀ +a ₁ +…+a _i +ε ₁ )·(b ₀ +b ₁ +…+b _i +α ₁ )=M

Then find the two prime factors of the modulus M and crack the RSA public key cryptography.

The purpose of the present invention is to decompose a large integer using a prime factorial table constructed by a prime factorial, so that the complexity of decomposing the large integer is reduced.

In summary, the method of the present invention comprises two parts:

1) Construct a prime factorial table for decomposing large integers;

2) Use the prime factorial table to decompose the RSA modulus.

From the Scheher sieve, we know that all prime numbers can be represented as prime numbers of the type α=6n+1 and ε=6n-1.

The composite number M of type α＝6n+1 has two prime factor product forms, namely:

(1)M=(α·α)=(6n ₁ +1)(6n ₂ +1)=6(6n ₁ n ₂ +n ₁ +n ₂ )+1;

(2)M=(ε·ε)=(6n ₁ -1)(6n ₂ -1)=6(6n ₁ n ₂ -n ₁ -n ₂ )+1;

The composite number M of type ε＝6n-1 has a prime factor product form, which is:

M=(α·ε)=(6n ₁ +1)(6n ₂ -1)=6(6n ₁ n ₂ +n ₁ -n ₂ )-1

From the above two properties, if the type of composite number M is known, the types of its two prime factors can be inferred.

When constructing a prime factorial table, as shown in Table 1, only factorials consisting of prime numbers are prime factorials, where _Pn is the nth prime value, and _Pn ! represents the prime factorial of the first n prime numbers, then _Pn ! = _P1 * _P2 … _Pn .

Table 1 Prime factorial table

In Table 1, starting from the second column, the first row of the nth column represents the prime factorials of the first n+1 prime numbers. For example, P ₃ ! = 2*3*5 = 30, P ₄ ! = 2*3*5*7 = 210, P ₅ ! = 2*3*5*7*11 = 2310, ..., and so on for the remaining columns. The value of each column represents the product of the current prime factorial as a multiple of the base. For example, the product of the row number in the nth column and the prime factorial, where the maximum row number is the value of the n+2th prime, and so on for the remaining columns.

Based on this logic, we construct the prime factorial table required to decompose large integers as shown in Table 1.

In the process of using the attribute columns in the prime factorial table, the concept of prime factor range is first introduced through an example.

For example, the sum of the number 30 in the first row of the second column and the number 7 in the first row of the attribute column is 37, which can be expressed as:

P ₃ ! ·1+7

=2×3×5×1+7

=(2×3)×5×1+7

=6×5+7=6×(5+1)+1.

This corresponds to the 6n+1 type in the attribute column of the table.

For example, the sum of the number 210 in the 7th row of the second column and the number 29 in the 5th row of the attribute column is 239, which can be expressed as

P ₃ ! ·7+29

=30×7+29=6×(35+5)-1.

This corresponds to the 6n-1 type in the attribute column of the table.

Add all the numbers in the second column to all the numbers in the attribute column. You can get 6n+1 numbers ranging from 37 to 241 and 6n-1 numbers ranging from 35 to 239, including all prime numbers in this range.

Similarly, by randomly selecting a number from the third column, the second column, and the attribute column and adding them together, and traversing all possible values in the three columns, we can obtain 6n+1 numbers ranging from 247 to 2551 and 6n-1 numbers ranging from 245 to 2549, which include all prime numbers in this range.

Since the sum of any number in each column and the upper and lower parts in the attribute column is a number of the type 6n+1 and 6n-1, it can be inferred that the sum of the numbers in each column in the prime factorial table can represent all prime numbers.

The present invention provides an example of decomposing a large RSA integer using the method of the present invention.

In this embodiment, since the number of digits of the RSA modulus actually used is too large to be conducive to display, an RSA56 (17 decimal digits) integer is selected here as an example, and its implementation method and process are exactly the same as those of the RSA modulus with large digits.

Assume that the integer to be decomposed is M = 19852601254923961.

The first step is to determine the scope of application of the prime factorial table shown in Table 1.

As shown in FIG1 , when m is divided by 6, the quotient Q=3308766875820660 is obtained, and the remainder R=1.

According to Scheher's sieve theory, if the integer m is a composite number, then its two factors have

1. (6n ₁ +1)(6n ₂ +1) form.

2. (6n ₁ -1)(6n ₂ -1) form.

Therefore, as shown in FIG1 , when an integer is decomposed using the prime factorial table, the attribute column selects only the (6n+1) part, or only the (6n-1) part.

其位数s为9位。Then take the square root of the integer m and round it to the integer, and we get

The number of digits s is 9.

小于第八列第一行的数223092870。则将素数阶乘表中的第七列选为分解整数的起始列。The seventh and eighth columns of the prime factorial table contain 9 digits, and

is smaller than the number in the first row of the eighth column, 223092870. Then the seventh column in the prime factorial table is selected as the starting column for factoring integers.

Next, starting from the qi1th column, two numbers a _i , b _i are selected from each column in turn as candidate numbers for each column, as shown in Figure 2.

For the seventh column, multiply any two numbers in the seventh column and subtract them from the integer M, and take two numbers whose product is not greater than the integer M as the two candidate numbers a ₇ , b ₇ in this column. If the product of two numbers is equal to M, the decomposition is terminated, as shown in Figure 2.

Here we choose 126095970*155195040=19569469107988800. 126095970 and 155195040 are two alternative numbers in this column.

For the sixth column, select any two numbers that can be repeated in the sixth column and add them to a ₇ , b ₇ in the seventh column and multiply them. Take two numbers whose product is not greater than the integer M as the two candidate numbers a ₆ , b ₆ in this column. If the product of two numbers is equal to M, the decomposition is terminated.

Here we choose (126095970+1021020)(155195040+510510)=19792820842294500. 1021020 and 510510 are two alternative numbers in this column.

For each of the fifth to attribute columns, two numbers are repeatedly selected from this column, added to the selected candidate numbers, and then multiplied, and two numbers whose product is not greater than the integer M are selected as the two candidate numbers a _i , b _i in this column. The process and results of each column are arranged as follows:

Fifth column:

(126095970+1021020+330330)*(155195040+510510+30030)=19848082299645600. Among them, 330330 and 30030 are alternative numbers in this column.

Fourth column:

(126095970+1021020+330330+18480)*(155195040+510510+30030+11550)＝19852432523154000

Third column:

Since the product of any two numbers in this column and the candidate numbers in the previous columns is greater than the integer M, only one candidate number is selected here, as shown in Figure 2, as follows,

(126095970+1021020+330330+18480+0)*(155195040+510510+30030+11550+1050)=19852566362244000.

Second column:

(126095970+1021020+330330+18480+0+90)*(155195040+510510+30030+11550+1050+120)=19852595675487000.

The above selects the candidate numbers in columns 2 to 7. Next, select the candidate numbers in the attribute column.

According to the Scheher sieve method, the two candidate numbers in the attribute column can only come from the (6n+1) part or the (6n-1) part. We search through the (6n+1) part and find that there is no candidate number that meets the conditions.

Traverse and search for the numbers in the (6n-1) part, and find two alternative numbers 17 and 23, as follows,

(126095970+1021020+330330+18480+0+90+17)*(155195040+510510+30030+11550+1050+120+23)＝

127465907*155748323=19852601254923961. At this point, the decomposition of the integer M is complete.

As shown in Figure 1, if no alternative number combination whose product is equal to the integer M is found after traversing all columns, then the integer M cannot be decomposed and is a prime number.

的试除整数分解方法相比，降低了比较次数和计算量。为RSA加密算法的安全性分析提供了有益参考。Different from the prior art, the RSA public key password cracking method of the present invention establishes a prime factorial table in advance, and only needs a table of 234 columns to include all prime factor combinations of integers with 617 decimal digits (RSA-2048 is 617 digits). That is, to decompose an integer with a maximum of 617 decimal digits, it is only necessary to traverse the prime factorial table of about 132 columns at most, find the candidate numbers in each column and add them up.

Compared with the trial division integer decomposition method, it reduces the number of comparisons and the amount of calculation. It provides a useful reference for the security analysis of the RSA encryption algorithm.

The above description is only an implementation mode of the present invention, and does not limit the patent scope of the present invention. Any equivalent structure or equivalent process transformation made by using the contents of the present invention specification and drawings, or directly or indirectly applied in other related technical fields, are also included in the patent protection scope of the present invention.

Claims (1)

1. A RSA public key password cracking method is applied to security analysis of an RSA encryption algorithm and is characterized by comprising the following steps:

dividing the natural number into regions at intervals by factoring different prime numbers, and establishing a prime number factorization table according to the size of the regions and the boundaries of the regions; the construction principle of the prime factorization table is as follows: the attribute column is a first column, starting from a second column, a first row of an nth column represents prime number factorization of the first n +1 prime numbers, the value of each column represents the multiple product of the current prime number factorization as a base number, row numbers in the nth column are respectively multiplied by the prime number factorization, the maximum value of the row numbers is n +2 prime number values, and the numbers in the rest rows in each column are the numbers of the first row and are not more than n +1 prime numbers p _n+1 The product of multiplication by a positive integer of (d);

obtaining the modulus of RSA public key password, recording the modulus as M, squaring and rounding M, and calculating

The number of the bits is recorded as s;

using the first row element of the corresponding digit sequence s in the prime factorization table

Adjusting and removing device>

Wherein, Q represents the number of the s column selecting the Q row as the intermediate number of the subsequent searching prime factor;

selecting an integer a in the upper and lower directions of the No. Q row with the No. s row and No. Q row as the middle number ₀ And b ₀ Multiplying, and making difference with the intermediate number, traversing all possible value-taking conditions, and selecting a group of numbers with the minimum difference;

looking for two integers a in the s-i column _i And b _i So that (a) ₀ +a ₁ +…+a _i )·(b ₀ +b ₁ +…+b _i ) The difference value with the modulus M of the RSA public key password is minimum; if optionally both integers have (a) ₀ +a ₁ +…+a _i )·(b ₀ +b ₁ +…+b _i ) If M is greater than M, only one number is selected from the row, and the other integer is set to 0, that is

(a ₀ +a ₁ +…+a _{i_1} +0)·(b ₀ +b ₁ +…+b _{i_1} +b _i )

Or

(a ₀ +a ₁ +…+a _{i_1} +a _i )·(b ₀ +b ₁ +…+b _{i_1} +0)

Decreasing the number of rows to the second row;

judging the prime factor type of the modulus M, if M is an integer of M =6n +1 type, respectively searching two integers alpha in prime numbers of 6n +1 type in an attribute column ₁ And alpha ₂ Or epsilon ₁ And ε ₂ So that

(a ₀ +a ₁ +…+a _i +α ₁ )·(b ₀ +b ₁ +…+b _i +α ₂ )＝M

Or

(a ₀ +a ₁ +…+a _i +ε ₁ )·(b ₀ +b ₁ +…+b _i +ε ₁ )＝M

If M is the number of M =6n-1 type, respectively searching an integer alpha in a 6n +1 region and a 6n-1 region of the attribute column ₁ And epsilon ₁ So as to satisfy

(a ₀ +a ₁ +…+a _i +α ₁ )·(b ₀ +b ₁ +…+b _i +ε ₁ )＝M

Or

(a ₀ +a ₁ +…+a _i +ε ₁ )·(b ₀ +b ₁ +…+b _i +α ₁ )＝M

Two prime factors of the modulus M are found, and the RSA public key password is cracked.

Images