[paper reading notes] - cryptographic analysis of short RSA secret exponents

1. Introduce

from RSA In the set of all key pairs of public key encryption system , Some key pairs have properties that can be used by various cryptanalysis attacks . Some of these attacks utilize modulus （N） To attack the weakness of , Others take advantage of the weakness of public or private keys . The weakness discussed in this article is the weakness that can complete the attack in modulus length and polynomial time （The weaknesses discussed here are those which allow an attack on RSA to be completed in a length of time which is polynomial in the length of the modulus.）

notes ： I can't understand what is called modulus length , The explanation given by Wikipedia is ： In Abstract Algebra , The length of a module is a generalization of the vector space dimension that measures its size . As for further understanding , Here is a link to Wikipedia ：Length of a module, I simply understand it as spatial complexity ..

in the light of RSA The target of modulus attack is to find this modulus N Two prime factors of p and q. One such attack occurs in p-1 or q-1 When the prime factor of is very small, it can be used to decompose the modulus N^[1]. And the modulus can also be in p+1 or q+1 When the prime factors of are very small, they are decomposed ^[2]. There is also a simple algorithm to decompose the modulus when the difference between two primes is only polynomial times greater than the square root of any primes . This algorithm is based on the following identity ：

\[(\frac{p+q}{2})^2-pq=(\frac{p-q}{2})^2 \]

stay \(\frac{p+q}{2}\) and \(\frac{p-q}{2}\) When known , Modulus can be decomposed , And the number \((\frac{p+q}{2})^2\) You can search linearly in complete square numbers larger than modulus . And the correct number k Then the conditions are met ：k-pq It's also a perfect square number .

The above formula explains \((\frac{p+q}{2})^2\) Greater than \(pq\).

Then it is about the large polynomial times mentioned in the article , Here you are ：

polynomially larger

source ：Meaning of "polynomially larger"

put questions to ：

For example

Is \(n\) polynomially larger than \(\frac{n}{\log n}\)? Than \(n\log n\)?

Is \(n^2\) polynomially larger than \(\frac{n}{\log n}\)? Than \(n\log n\)?

I am trying to understand the difference because apparently the first line isn't, but the second is (Master Theorem).

answer ：

"Polynomially larger" means that the ratio of the functions falls between two polynomials, asymptotically. Specifically, \(f(n)\) is polynomially greater than \(g(n)\) if and only if there exist generalized polynomials (fractional exponents are allowed) \(p(n),q(n)\) such that the following inequality holds asymptotically:

“Polynomially larger” The function ratio gradually falls between two polynomials . specifically ,\(f(n)\) about \(g(n)\) yes polynomially greater If and only if there is a generalized polynomial （ The exponent is allowed to be decimal ）\(p(n),q(n)\), Make the following inequality gradually hold ：

\[p(n)\le \frac{f(n)}{g(n)}\le q(n) \]

For the first problem, we have the ratio is equal to \(log⁡(n)\). It is not the case that there exist polynomials \(p(n),q(n)\) such that \(p(n)≤log(n)≤q(n)\) asymptotically, because no polynomial is a lower bound for \(log(n)\). Thus it is not polynomially bounded. \(nlog(n)\) is the same (even the same quotient if taken in the other order).

For the first question , We have ratio （ This ratio should be \(\frac{n}{\frac{n}{\log n}}\)) be equal to \(\log n\). Because there is no polynomial \(log(n)\) Lower bound of , So there is no polynomial \(p(n),q(n)\), bring \(p(n)\le\log (n)\leq(n)\) Gradually established . So this is not polynomial bounded . about \(n\log n\) Empathy （ Although we get the same quotient in different order , Reverse the order of numerator and denominator ）

For the second problem, we have the ratio is equal to \(nlog(n)\). It is the case that \(n≤nlog(n)≤n^2\) asymptotically, so it is polynomially bounded and therefore \(n^2\) is polynomially larger. \(\frac{n^2}{nlog(n)}=\frac{n}{log(n)}\), and we have that (asymptotically)

For the second question , We have a ratio equal to \(n\log n\). There is \(n≤nlog(n)≤n^2\) Gradually established , So this is polynomial bounded and therefore \(n^2\) yes polynomially larger. The ratio of the second case ：\(\frac{n^2}{nlog(n)}=\frac{n}{log(n)}\), We have （ Gradually ）：

\[n^{\frac{1}{3}}≤\frac{n}{log(n)}≤n \]

Another related question link ：asymptotically larger vs polynomially larger

About RSA There are many more attacks , Remove other conditions , Will require that the encryption or decryption index is small . In some cases , People will prefer to use a smaller encryption and decryption index , Because this can reduce the running time of encryption and decryption . This is because , For a fixed modulus size ,RSA The encryption and decryption time is simply proportional to the bit length of the index . If the computing performance difference between the devices at both ends of the communication is too large , In this case, using a small index will be particularly beneficial . An example is when RSA When the system is applied to the communication between smart card and mainframe computer . In this case , It is best to use a small decryption index for smart cards / Private key , Large computers use a small encryption index / Public key , This can reduce the process required for smart cartoon messages . However , People need to be vigilant about RSA Small exponential attack .

The small public key can be used when broadcasting the same message to multiple parties . To illustrate this attack , Suppose a message is broadcast to three parties m, Adopt public key \(e_1=e_2=e_3=3\) And modulus \(n_1,n_2,n_3\), Then the encrypted message is ：

\[m^3\ mod\ n_1,\ m^3\ mod\ n_2,\ m^3\ mod\ n_3 \]

Using the Chinese Remainder Theorem （CRT）, You can find it \(m^3\ mod\ n_1n_2n_3\), however ,\(m^3<n_1n_1n_3\) because \(m<n_1,n_2,n_3\). therefore ,\(m^3\) In the mold \(n_1n_2n_3\) Will not change , And the news \(m\) It can be recovered by opening the root of the third power .

In this paper , I will introduce a small key , Attack method based on continued fraction .

The application of the Chinese remainder theorem here requires RSA in , The size of plaintext is smaller than modulus .

2. Continuous score background knowledge

Continued fractions can be used to find the numerator and denominator of a fraction when the approximation of the fraction is close enough to be known . This will be the same as in Section 4 RSA of , The public key and modulus will be used to construct the estimated value of the score involving the private key .

This algorithm, which uses continued fractions to find the numerator and denominator of the fractional form of a given estimate, is called continued fraction algorithm here . This algorithm will be in 3 Section . The background knowledge about the continued fraction algorithm will be introduced in this section . A more in-depth discussion of continued fractions can be found in ^[3] Search for .

An expression of the following form of a continued fraction ：

\[\frac{a_1}{q_1+\displaystyle\frac{a_2}{q_2+\displaystyle\frac{a_3}{...\displaystyle\frac{}{q_{m-1}+\displaystyle\frac{a_m}{q_m}}}}}=a_1/(q_1+a_2/(q_2+a_3/(.../(q_{m-1}+a_m/q_m)...))). \tag 1 \]

The continued fraction we discuss is more in all \(a_i=1\) Under the circumstances . For convenience , Let's define ：

\[<q_0,q_1,...,q_m>=q_0+1/(q_1+1/(q_2+1/(.../(q_{m-1}+1/q_m)...))).\tag 2 \]

for example ：\(<0,2,1,3>=0+1/(2+1/(1+1/3))=\displaystyle\frac{4}{11}\).

\(<0,2,1,3>\) It's called \(\displaystyle\frac{4}{11}\) The continued fraction expansion of （ continued fraction expansion）. A positive rational number （ positive rational number）\(f\) The continued fraction expansion of is by subtracting \(f\) And take the reciprocal of the rest , Then subtract the integer part , Take the reciprocal , Repeat until the remainder is zero . set up \(q_i\) Is the integer part ,\(r_i\) It's No i The remainder of the step ,m Is the number of reciprocal , Then there are ：

\[\begin{equation} \begin{aligned} &q_0=\lfloor f \rfloor ,\ \ \ r_0=f-q_0,\ \ \ and \\ &q_i=\lfloor \frac{1}{r_{i-1}} \rfloor,\ \ \ r_i=\frac{1}{r_{i-1}}-q_i,\ \ \ for\ \ i=1,2,...,m \end{aligned} \tag 3 \end{equation} \]

because \(r_m\) by 0, We have \(f=<q_0,q_1,...,q_m>\).

There are two points to note about continued fractions , It will be very useful later . The first is \(q_i\ge 2\). because \(q_i=1\) signify \(r_{i-1}=1\), And it's impossible . The second is for any \(x>0\), Yes ：

\[\begin{equation} \begin{aligned} &\langle q_0,q_1,q_2,...,q_m\rangle\ <\ \langle q_0,q_1,...,q_{m-1},q_m+x\rangle \ \ \ m It's odd \\ &\langle q_0,q_1,q_2,...,q_m\rangle\ >\ \langle q_0,q_1,...,q_{m-1},q_m+x\rangle \ \ \ m For the even \end{aligned} \tag 4 \end{equation} \]

This can be verified by the continued fraction formula .

The first point here is that the subscripts in the original text are m, But here I think i More reasonable .

What we need to consider now is how to reconstruct through continued fraction expansion \(f\). According to the formula (2) To push backwards , Also is to \(q_m\) Take the bottom , And then add \(q_{m-1}\), Then count down …… Until \(q_0\). however , A more effective way is from \(q_0\) Start rebuilding \(f\). set up \(n_i\) and \(d_i,i=0,1,2,...,m\) Is a sequence of numerators and denominators as defined below ：

\[\frac{n_i}{d_i}=\langle q_0,q_1,...,q_i\rangle,\ \ \ gcd(n_i,d_i)=1\ \ \ i=1,2,...,m.\tag 5 \]

The process is as follows ：

\[\begin{equation} \begin{aligned} &n_0=q_0,&&d_0=1,\\ &n_1=q_0q_1+1,&&d_1=q_1\\ &n_i=q_in_{i-1}+n_{i-2},&&d_i=q_id_{i-1}+d_{i-2}\ \ \ i=2,3,...,m. \end{aligned} \tag 6 \end{equation} \]

The fraction can be reconstructed in this way \(f=\frac{n_m}{d_m}\).

There is a question about \(f\) The relationship between the numerator and denominator of , It will be useful later ：

\[n_id_{i-1}-n_{i-1}d_i=-(-1)^i\ \ \ \ i=1,2,...,m.\tag 7 \]

Now the background knowledge of even fraction algorithm has been introduced here .

For continued fractions, please refer to my previous article on continued fractions , It can be used as a reference ~

3. Continued fraction algorithm

Yes \(f\) Make a smaller estimate \(f'\)：

\[f'=f(1-\delta),\ \delta \ge 0.\tag 8 \]

set up \(q_i,r_i\) and \(q_i',r_i'\) Namely \(f,f'\) Of the i Integer and decimal parts . If \(\delta\) Small enough , that \(f\) The numerator and denominator of can be found by the following algorithm :

​ Repeat the following steps until \(f\) Found ：

​ - Generate \(f'\) Of the continued fraction expansion of i term （\(q_i\), Namely \(\langle q_1,q_2,...,q_i\rangle\)）

​ - Use formula （6） To rebuild the expansion into a number

​ If \(i\) For the even , The expansion is ：\(\langle q_0',q_1',...,q_{i-1}',q_i+1\rangle\)

​ If \(i\) It's odd , The expansion is ：\(\langle q_0',q_1',...,q_{i-1}',q_i\rangle\)

​ - Check whether this number is equal to \(f\)

My understanding of this algorithm is ： Heel formula (6) The principle of .\(i\) Not the last , So an odd number \(\langle q_1,q_2,...,q_i\rangle\) And then because \(f>f'\), therefore

The reason is in every （ It's not just the last one ） Even term （\(i\) For the even ） add 1, Because for \(f\) Guess （guess） Be greater than \(f'\)（ because \(f>f'\)）, And from the formula （4） It can be seen that ,\(\langle q_0',q_1',...,q_{i-1}',q_i'\rangle\) Less than \(f'=\langle q_0',q_1',...,q_{i-1}',q_i'+r_i'\rangle\). Note that there must be a test to determine for \(f\) Is your guess correct .

When ：

\[\langle q_0,q_1,...,q_{m-1},q_m-1\rangle<f'\le\langle q_0,q_1,...,q_m\rangle\ \ \ m For even when \\ \langle q_0,q_1,...,q_{m-1},q_m+1\rangle<f'\le\langle q_0,q_1,...,q_m\rangle\ \ \ m In an odd number of \tag 9 \]

The time continued fraction algorithm is correct .

My understanding of this place ：

When \(i=m\) when , Because at this time, even numbers are added 1, So it can meet when m When it is even and not the last item , Can still satisfy \(f'\le\langle q_0,q_1,...,q_m\rangle\), and \(\langle q_0,q_1,...,q_{m-1},q_m-1\rangle\) It is not necessarily less than \(f'\), It's less than \(\langle q_0,q_1,...,q_m\rangle\), Odd number homology . But I can't see why this condition must be met , Maybe it's to reflect \(f\) and \(f'\) Little difference （\(\delta\) Very small ）？

Now let's consider （9） about \(\delta\) The impact of size . about （8） solve , obtain ：

\[\delta =1-\frac{f'}{f}.\tag {10} \]

Analyze according to the following situations ：m=0,m=1,m Is even and m\(\ge 2\),m Is odd and m\(\ge 3\)

Below n and d And q The relationship can be in （6） View in

• m=0

  use （9） stay （10） Instead of \(f'\)（ hold （9） Into the （10））, Yes ：

  \[\delta <1-\frac{\langle q_0-1\rangle}{\langle q_0\rangle}\tag {11} \]

  combination （2）, It can be reduced to \(\delta < \displaystyle\frac {1}{q_0}\), This can also be written as （ set up \(n_0=q_0,d_0=1\)）：

  \[\delta < \frac{1}{n_0d_0}\tag {12} \]

• m=1

  use （9） stay （10） Instead of \(f'\), Yes ：

  \[\delta < 1-\frac {\langle q_0,q_1+1\rangle}{\langle q_0,q_1\rangle}\tag{13} \]

  combination （2）, It can be reduced to ：

  \[\delta < \displaystyle\frac {1}{(q_0q_1+1)(q_1+1)}\tag {14} \]

  As explained above ：\(q_m\ge 2\). stay （14） in \(q_1+1\le \displaystyle\frac{3}{2}q_1\). Combine this with （6） About China \(n_1,d_1\) The expression of （14） combination , Yes ：

  \[\delta < \frac{1}{\displaystyle\frac{3}{2}n_1d_1}\tag {15} \]

  Enough to ensure the success of the continued fraction algorithm .

• m It's even and m\(\ge 2\)

  use （9） stay （10） Instead of \(f'\), Yes ：

  \[\delta < 1-\frac {\langle q_0,q_1,...,q_{m-1}q_m-1\rangle}{\langle q_0,q_1,q_2,...,q_m\rangle}\tag{16} \]

  according to （6）, Yes （ Actually there are （5））：

  \[\begin{equation} \begin{aligned} &\langle q_0,q_1,...,q_{m-1}q_m-1\rangle &&=&&\frac{(q_m-1)n_{m-1}+n_{m-2}}{(q_m-1)d_{m-1}+d_{m-2}}\\ &\langle q_0,q_1,q_2,...,q_m\rangle &&=&&\frac{q_mn_{m-1}+n_{m-2}}{q_md_{m-1}+d_{m-2}} \end{aligned} \tag {17} \end{equation} \]

  Bring in （16）：

  \[\delta < \frac{n_{m-1}d_{m-2}-n_{m-2}d_{m-1}}{(q_mn_{m-1}+n_{m-2})(q_md_{m-1}+d_{m-2}-d_{m-1})}\tag{18} \]

  adopt （7） and （6） in \(n_m,d_m\) The expression of , Yes ：

  \[\delta <\frac{1}{n_m(d_m-d_{m-1})} \]

  therefore , You know

  \[\delta <\frac{1}{n_md_m} \]

  Enough to ensure the success of the continued fraction algorithm

• m It's odd and m\(\ge 3\)

  The analysis process is similar to the above , Yes ：

  \[\delta < \frac{1}{n_m(d_m+d_{m-1})}.\tag{21} \]

  because \(d_m=q_md_{m-1}+d_{m-2}\) also \(q_m\ge 2\), We got \(d_m+d_{m-1}\le \displaystyle\frac{3}{2}d_m\). therefore , You know ：

  \[\delta < \frac{1}{\displaystyle\frac{3}{2}n_md_m}\tag{22} \]

  Enough to ensure the success of the continued fraction algorithm .

  notes ：\(d_m+d_{m-1}\le \displaystyle\frac{3}{2}d_m\) The source of the ：

  \[\begin{equation} \begin{aligned} d_m&=q_md_{m-1}+d_{m-2}\\ d_m+d_{m-1}&=(q_m+1)d_{m-1}+d_{m-2}\\ \because q_m\ge &2,\ \therefore q_m+1\le \frac{3}{2}\\ \therefore d_m+d_{m-1}&=(q_m+1)d_{m-1}+d_{m-2}\le \end{aligned} \end{equation} \]

Combine the results of the four cases ,

\[\delta <\frac{1}{\displaystyle\frac{3}{2}n_md_m}\tag{23} \]

Enough to ensure the success of the continued fraction algorithm . And ,\(n_m,d_m\) Namely \(f\) The numerator and denominator of .

Let's now consider the execution time of this algorithm . set up \(x=max(n_m,d_m)\). Continued fraction expansion quotient （ This quotient is each of the continued fraction expansions \(q_i\)） The number of is \(O(\log x)\). For every quotient , Generate and test a for \(f\) Guess . Generate each one about \(f\) All the calculations needed to guess are \(\log x\) polynomial . So suppose for \(f\) The test of whether the guess is correct is \(\log x\) polynomial , Then the execution time of the continued fraction algorithm is \(\log x\) polynomial .

4. Continued fraction algorithm in RSA Application in

Public key \(e\) And a private key \(d\) The following relationships are found in references ^[4] Mentioned in ：

\[ed\equiv 1(mod\ LCM(p-1,q-1))\tag{24} \]

The relationship between public and private keys that are inverse elements of each other is necessary in seeking power . from （24） In the clear , There must be an integer \(K\)：

\[ed=K\cdot LCM(p-1,q-1)+1\tag{25} \]

If we set \(G=GCD(p-1,q-1)\), And make use of \(LCM(p-1,q-1)=\displaystyle\frac{(p-1)(q-1)}{G}\), You'll get ：

\[ed=\frac{K}{G}(p-1)(q-1)+1\tag{26} \]

\(K\) and \(G\) There may be a common factor . So define \(k=\displaystyle\frac{K}{GCD(K,G)},g=\displaystyle\frac{G}{GCD(K,G)}\), You'll get \(\displaystyle\frac{k}{g}=\displaystyle\frac{K}{G},GCD(k,g)=1\). We have ：

\[ed=\frac{k}{g}(p-1)(q-1)+1\tag{27} \]

（27） Divide two sides by \(dpq\)

\[\frac{e}{pq}=\frac{k}{dg}(1-\delta),\ \ \delta=\frac{p+q-1+\displaystyle\frac{g}{k}}{pq}\tag{28} \]

be aware \(\displaystyle\frac{e}{pq}\) It consists entirely of public information , And still \(\displaystyle\frac{k}{dg}\) A lower estimate of . Before using the continued fraction algorithm , We need to think that this algorithm is always looking for the simplest fraction （fractions in lowest terms）. from （25） Can be seen in \(GCD(K,d)=1\). because \(k\) Divisibility \(K\), You can get \(GCD(k,d)=1\). also \(GCD(k,g)\) It is in the previous definition . therefore \(GCD(k,dg)=1\), And the continued fraction algorithm can be used in \(\delta\) Small enough to be used to find \(k\) and \(dg\).

adopt （28） in \(\delta\) Expressions and （23） About China \(\delta\) Constraints , It can be seen that ：

\[kdg<\frac{pq}{\displaystyle\frac{3}{2}(p+q)}\tag{29} \]

Enough to make \(k\) and \(dg\) Found . Notice about \(\delta\) In the expression of \((-1-\displaystyle\frac{g}{k})\) Has been removed , This is because it is relative to \((p+q)\) It's too small . because \((-1-\displaystyle\frac{g}{k})\) It will decrease \(\delta\) Size , So this will not affect （29） The correctness of the .

The process is as follows ：

\[\begin{equation} \begin{aligned} \delta &<\frac{1}{\frac{3}{2}n_md_m}\\ \frac{p+q-1-\frac{g}{k}}{pq}&<\frac{1}{\frac{3}{2}kdg}\\ kdg&<\frac{pq}{\frac{3}{2}(p+q-1-\frac{g}{k})} \end{aligned} \end{equation} \]

Then remove the \((-1-\displaystyle\frac{g}{k})\), Will make \(kdg\) The constraints become more stringent , Smaller range , So there is no effect . And after removing , The formulas are all composed of known quantities .

Now let's consider how to test a test about \(k\) and \(dg\) My guess is correct . To simplify this test , We have to assume \(ed>pq\). This is not a very strict assumption , Because when \(e\) or \(d\) It's time to fix , The remaining value is close to \(\displaystyle\frac{pq}{G}\)（ Think about it \(G=GCD(p-1,q-1)\). Unless \(G\) A very large , otherwise \(ed>pq\). according to （27）,\(ed>pq\) One conclusion of is \(k>g\). Rearrange （27）, Yes ：

\[edg=k(p-1)(q-1)+g\tag{30} \]

I don't know why \(e,d\) A value in determines , Another value will be close \(\displaystyle\frac{pq}{G}\), But with this condition , set up \(e\) Is constant , that ：\(ed=e\cdot \displaystyle\frac{pq}{G}=\displaystyle\frac{e}{G}pq\), as long as \(G\) No more than \(e\), Then there will be \(ed>pq\). The latter one is because of expansion （27）, Yes \(ed=\displaystyle\frac{k}{g}pq-[\displaystyle\frac{k}{g}(p+q-1)-1]\), The brackets in the formula must be positive , therefore \(ed<\displaystyle\frac{k}{g}pq\Rightarrow\displaystyle\frac{k}{g}>1\Rightarrow k>g\)

We see when \(k>g\), take \(edg\) Divide \(k\) You will get a quotient \((p-1)(q-1)\) And the remainder \(g\). This provides an example of \((p-1)(q-1)\) and \(g\) guess . If this is about \((p-1)(q-1)\) My guess is 0, So this \(k\) and \(dg\) It's just wrong . This situation must be filtered out , Otherwise, this test will pq Decompose into pq and 1. About \((p-1)(q-1)\) The following formula can be used to create another one about \(\displaystyle\frac{p+q}{2}\) Guess ：

\[\frac{pq-(p-1)(q-1)+1}{2}=\frac{p+q}{2}\tag{31} \]

If （ adopt \((p-1)(q-1)\) Guess of ） About \(\displaystyle\frac{p+q}{2}\) Your guess is not an integer , So about \(k\) and \(dg\) Your guess is wrong . And this is about \(\displaystyle\frac{p+q}{2}\) Guess can also be created \(\displaystyle\frac{p-q}{2}\) Guess ：

\[(\frac{p+q}{2})^2-pq=(\frac{p-q}{2})^2\tag{32} \]

If （ Calculated ） About \((\displaystyle\frac{p-q}{2})^2\) Can be completely square , that , About \(k\) and \(dg\) Our original guess is correct . secret key \(d\) You can use \(dg\) Divide \(g\) To find the . Think about it , When \(edg\) Divide \(k\) when ,\(g\) Is the remainder . We can also from \(\displaystyle\frac{p+q}{2}\) and \(\displaystyle\frac{p-q}{2}\) To recover \(p,q\).

take \(\displaystyle\frac{edg}{k}\) Decimal part of , Multiply by what you get k, We can work out g

If no measures are taken to counter this kind of targeting RSA Even score attack , Then people can predict \(g\) Very small ,\(k<dg\). under such conditions , from （29） As you can see in, you can find keys with up to one fourth of the modulus in polynomial time . This attack cannot be extended to cases where the size of the key and modulus are similar . Because this attack relies on the information provided by the public key to help decompose the modulus , And under normal circumstances , The choice of public key is almost independent of modulus .

5. Example

In this section , The continued fraction algorithm will be applied to a small RSA Index alignment . for example ：

\[pq=8927,e=2621 \]

The continued fraction algorithm will be in \(\displaystyle\frac{e}{pq}=\displaystyle\frac{2621}{8927}\) On the implementation ：

Variable name	computing method	i=0	i=1	i=2
\(q_i'\)	(3)	0	3	2
\(r_i'\)	(3)	\(\displaystyle\frac{2621}{8927}\)	\(\displaystyle\frac{1064}{2621}\)	\(\displaystyle\frac{493}{1064}\)
\(\displaystyle\frac{n_i'}{d_i'}=\langle q_0',q_1',...,q_i'\rangle\)	(6)	\(\displaystyle\frac{0}{1}\)	\(\displaystyle\frac{1}{3}\)	\(\displaystyle\frac{2}{7}\)
\(\displaystyle\frac{k}{dg}\) My guess	\(i It's odd ：\langle q_0',q_1',...,q_i'\rangle\\i For the even ：\langle q_0',q_1',...,q_i+1'\rangle\)	\(\displaystyle\frac{1}{1}\)	\(\displaystyle\frac{1}{3}\)	\(\displaystyle\frac{3}{10}\)
\(edg\) My guess	\(e\cdot dg\)	2621	7863	26210
\((p-1)(q-1)\) My guess	\(\lfloor \displaystyle\frac{edg}{k}\rfloor\)	2621	7863	8736
\(g\) My guess	\(edg\mod k\)	0	0	2
\(\displaystyle\frac{p+q}{2}\) My guess	(31)	3153.5	532.5	96
\(\displaystyle\frac{p-q}{2}\) My guess	(32)			\(289=17^2\)
d	\(\displaystyle\frac{dg}{g}\)			5

In this case , Even score attack produced ：

\[d=5,p=113,q=79,k=3,g=2 \]

We can see that these values satisfy （27） Of , So we know \(d=5\) It's corresponding to \(e=2621\) In the mold \(pq=8927\) Key under . It can also be seen that these conditions also meet （29）.

This example illustrates the details of the even score attack , But considering the actual situation is more meaningful . hypothesis RSA Used 1024 Bit modulus . that \(p,q\) It's all close to \(2^512\). hypothesis \(g=2\), also \(e\approx pq\) bring \(k\approx dg\)（ see （28））. And then according to （29）, It can be seen that the size of the even score attack will be found to be about less than \(2^{255}\) The key of .

because \(pq\approx 2^{1024},p,q\approx 2^{512},k\approx dg\), Yes ：

\[\begin{equation} \begin{aligned} kdg<&\frac{pq}{\displaystyle\frac{3}{2}(p+q)}\\ 4d^2<&\frac{2^{1024}}{2^{512}}=2^{512}\\ 2d<&2^{256}\\ d<&2^{255} \end{aligned} \end{equation} \]

6. Yes RSA Counteraction of even score attack

There are two ways to reduce RSA The maximum range of keys that can be found by the continued fraction attack . from （29） It can be seen that , The two methods are to make \(k\) Grow and let \(g\) Bigger .

In order to make \(k\) Bigger , We need to make the public key \(e\) Bigger （ from （27） It is concluded that ）. This can give \(e\) add \(LCM(p-1.q-1)\) Multiple . hypothesis \(e>(pq)^{1.5}\). It means \(\displaystyle\frac{k}{dg}>(pq)^{0.5}\)（ from （28） obtain ）. take \(k=dg(pq)^{0.5}\) Plug in （29）, You can get \(d<1\). therefore , If \(e>(pq)^{1.5}\), Then no matter the key size , Even the fraction algorithm will fail . Improve \(e\) The size of will have the disadvantage of increasing the execution time of the encryption process . But this may be feasible in some systems .

hold \(k=dg(pq)^{0.5}\) Plug in （29）, Yes ：

\[\begin{equation} \begin{aligned} (dg)^2\sqrt{pq}&=\frac{pq}{\frac{3}{2}(p+q)}\\ (dg)^2&=\frac{\sqrt{pq}}{\frac{3}{2}(p+q)} \end{aligned} \end{equation} \]

According to the basic inequality \(\displaystyle\frac{a+b}{2}\ge \sqrt{ab}\), You know \(\sqrt{pq}\le \displaystyle\frac{a+b}{2}<\displaystyle\frac{3(p+q)}{2}\). and \(g\ge 1\), So you can get \(d<1\). And when \(e>(pq)^{1.5}\),\(\displaystyle\frac{k}{dg}>(pq)^{0.5}\), According to the same process , You can know \(d\) Definitely less than 1

In order to make \(g\) Bigger ,\(p,q\) Need to be carefully selected to meet \(GCD(p-1,q-1)\) Large enough . However, we can see later that it can be found under certain specific conditions \(g\) or \(g\) Factor of .

7. Improvements to attacks

In this section , Four possible improvements against short key attacks will be discussed . The first improvement is to allow the continued fraction algorithm to slightly exceed （29） Continue searching within the bounds of \(d\). This algorithm only guarantees that this limit can be reached , But in fact, it may continue to work slightly beyond this limit . This makes even the private key \(d\) The size of is one larger bit Left and right can also be found .

The second improvement is based on \(\displaystyle\frac{e}{pq}\) Denominator of （ This formula is \(\displaystyle\frac{k}{dg}\) A lower estimate of ） yes \((p-1)(q-1)\) A simple higher estimate of . One is closer \((p-1)(q-1)\) The higher estimate of is ：

\[\lfloor (\sqrt{pq}-1)^2\rfloor \]

Use this estimate ,（29） Will become ：

\[kdg<\frac{2}{3}(\frac{\sqrt{pq}-1}{\sqrt{p}-\sqrt{q}})^2 \]

This increases the range of private keys that can be found . And the improvement range increases with \(|p-q|\) Reduce and improve .

Throw away that and round it down , It's easy to see \((p-1)(q-1)<(\sqrt{pq}-1)^2<pq\). and ：

\[\begin{equation} \begin{aligned} &\ \frac{pq}{p+q},(\frac{\sqrt{pq}-1}{\sqrt{p}-\sqrt{q}})^2\\ \Rightarrow &\ \frac{pq}{p+q},\frac{pq-2\sqrt{pq}+1}{p+q-2\sqrt{pq}}\\ \Rightarrow &\ \frac{pq}{p+q}-1,\frac{pq-2\sqrt{pq}+1}{p+q-2\sqrt{pq}}-1\\ \Rightarrow &\ \frac{pq-p-q}{p+q},\frac{pq-p-q+1}{p+q-2\sqrt{pq}}\\ \end{aligned} \end{equation} \]

I think from the last formula , The formula on the left is obviously smaller than that on the right , So the range is increased , But I still don't know how this changed , I can only look back backwards like this ……

The third is in many \(\displaystyle\frac{k}{dg}\) Execute the algorithm on the conjecture . The execution algorithm may start with a small initial guess , And succeed in big guesses . In this case, it is necessary to \(\displaystyle\frac{k}{dg}\) Do a linear search . When the key is in （29） In the range of , The algorithm needs to perform polynomial , And the part beyond the scope , The number of times the algorithm must be executed will increase exponentially .

The fourth is to find \(g\) or \(g\) Factor of . Suppose that \(t\) yes \(g\) Factor of , So you can use it \(t(\displaystyle\frac{e}{pq})\) As \(\displaystyle\frac{k}{d(\displaystyle\frac{g}{t})}\) A lower estimate of .

under these circumstances ,（29） Will become ：

\[kd(\frac{g}{t})<\frac{pq}{\frac{3}{2}(p+q)} \]

This is done by looking \(t\) Improved what you can find \(d\) The scope of the . Now we need a way to find \(g\) Factor of . because \(g\) Divisibility \(GCD(p-1,q-1)\),\(g\) You can divide by \(p-1\) and \(q-1\). It means \(g\) You can also divide \(pq-1\). because ：

\[pq-1=(p-1)(q-1)+(p-1)+(q-1) \]

So maybe through decomposition \(pq-1\) To find \(g\) Factor of . But if \(g\) Big and all \(g\) The prime factors of are very large , This method will become very difficult , However , If \(g\) It's so big that \(\displaystyle\frac{p-1}{g}\) and \(\displaystyle\frac{q-1}{g}\) Very small , Then you can search \(\displaystyle\frac{p-1}{g}\) and \(\displaystyle\frac{q-1}{g}\) To find the possible value of \(g\).

8. Unresolved issues

The main reason for using low decryption index is to reduce the time spent in decryption . And there is a technology that can be used \(p,q\) Knowledge （ Not just \(pq\)） To reduce decryption time ^[5]. Using this technique requires two general size indexations . The first result is \(d_p=d\%(p-1)\), The second result is \(d_q=d\%(q-1)\). These two results can be combined by Chinese remainder theorem , Get the results . People can choose \(d\), bring \(d_p,d_q\) Are very small to reduce time . An interesting open question is when \(d_p,d_q\) Small but unequal , Is there an attack .

I don't understand much about the above paragraph , In order to reduce the decryption time, I guess , What the original text gives is secret key exponentiation time, Key indexing time . And I didn't completely understand this process

There is another open question about the size of the public key . Take a look back. , If the public key is at least better than \(pq\) Long 50%, Then the attack described in this article will fail . For some systems , In pursuit of speed , It's just a small price . The problem is , When the key is short , When the public key is greater than the modulus , Whether there is a target RSA The attack of .

9. summary

The continued fraction algorithm can find a sufficiently short key in polynomial time . For a typical case ：\(e<pq\),\(GCD(p-1,q-1)\) It's very small , and \(p,q\) With almost the same number of digits , At most, the algorithm can find a key with a length of about a quarter of the modulus .

There are some ways to combat this attack . if \(e>(pq)^{1.5}\), Then the even fraction algorithm cannot guarantee that it is valid for any number of private keys . also , People may choose \(GCD(p-1,q-1)\) The big picture , Because the key size that can be found is the same as \(GCD(p-1,q-1)\) Is inversely proportional to the size of . However , This will also lead to some problems .

Here we discuss several improved methods of continued fraction attack . However , They only increase the maximum digit quotient of the key that can be found in polynomial time bit. When the size of the key exceeds this maximum , The time to find the key will increase exponentially .

This attack cannot be extended to the normal case where the key is approximately equal to the modulus band .

References

---

1. Pollard, J.M., "Theorems on factorization and primality testing", Proc. Cambridge Philos. Soc., vol. 76, 1974, pp. 521-528. ︎

2. Williams, H.C., "A p+1 Method of Factoring", Mathematics of Computation, vol. 39, no. 159, July 1982, pp. 225-234. ︎

3. Knuth, D.E., Art of Computer Programming Volume 2 / Seminumerical Algorithms, Addison Wesley, 1969. ︎

4. Rivest, R.L., A. Shamir, and L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Communications of the ACM, vol. 21, no. 2, February 1978, pp. 158-164. 14 ︎

5. Quisquater, J.J. and C. Couvreur, "Fast Decipherment Algorithm for RSA Public Key Cryptosystem", Electronics Letters, vol. 18, no. 21, October 1982, pp. 905- 907. ︎