Open access peer-reviewed chapter - ONLINE FIRST

Survey of RSA Vulnerabilities

By Anthony Overmars

Submitted: November 16th 2018Reviewed: January 31st 2019Published: June 17th 2019

DOI: 10.5772/intechopen.84852

Downloaded: 140

Abstract

Rivest et al. patented (US) RSA. RSA forms the basis of most public encryption systems. It describes a public key encryption algorithm and certification process, which protects user data over networks. The patent expired in September 2000 and now is available for general use. According to Marketsandmarkets.com, the global network encryption market size is expected to grow from USD 2.9 billion in 2018 to USD 4.6 billion by 2023, at a compound annual growth rate (CAGR) of 9.8%. Major growth drivers for the market include increasing adoption of optical transmission, an increasing demand to meet various regulatory compliances and a growing focus on shielding organizations from network security breaches. In short, RSA forms the basis of almost all public encryption systems. This, however, is not without risk. This chapter explores some of these vulnerabilities in a mathematical context and provides the reader with an appreciation of the strength of RSA.

Keywords

  • survey
  • public keys
  • vulnerability

1. Introduction

Rivest et al. patented (US) RSA, which forms the basis for most public encryption systems. RSA describes a public key encryption algorithm and certification process, which protects user data over networks. The patent expired in September 2000 and now is available for general use. According toMarketsandmarkets.com[1], the global network encryption market size is expected to grow from USD 2.9 billion in 2018 to USD 4.6 billion by 2023, at a compound annual growth rate (CAGR) of 9.8%. Major growth drivers for the market include increasing adoption of optical transmission, an increasing demand to meet various regulatory compliances and a growing focus on shielding organizations from network security breaches. In short, RSA forms the basis of almost all public encryption systems. This, however, is not without risk. This chapter explores some of these vulnerabilities in a mathematical context and provides the reader with an appreciation of the strength of RSA.

RSA is secure and difficult to factorize in polynomial time. Conventional sequential computing machines, running in polynomial time, take an unfeasible amount of CPU cycles to find factorization solutions to RSA keys. Quantum computing holds great promise; this, however, is realistically still some way off. Opportunities exist using conventional computing (sequential and parallel) using better mathematical techniques. A discussion on exploiting implementation flaws is also considered.

Of keen interest is our lack of understanding of prime numbers and their structure. The current perception is that there appears to be some underlying structure, but essentially, primes are randomly distributed. This is explored in Sections 8 and 12. Vulnerabilities in the selection of primes are exploited in Section 5 using Euler’s factorization.

Poor RSA key design and their exploits are considered in Section 6 using Wiener’s method and in Sections 15–17 using a combination of LLL, Coppersmith and Pohlig-Hellman. All of these attacks can be mitigated by designing the RSA keys with these exploits in mind. RSA key design (Section 2) consists of two parts, a private key Ndand a public key Ne. A composite number N, is derived from two prime numbers. The denumbers are selected in an ad hoc manner using Euler’s totient.

Development of quantum computing is continuing at breakneck speed; however useful machines are yet to appear. Parallel computing however is here and now, and whilst factorizing RSA keys is not achievable on conventional computers in polynomial time, parallel computing has allowed for multiple solutions to be tested simultaneously. This is an area where research continues and new algorithms as shown in Sections 20 and 14 lend themselves well to GPU parallel processing systems.

2. Structure of RSA numbers

Consider RSA100 challenge number

RSA100=1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139=37975227936943673922808872755445627854565536638199×40094690950920881030683735292761468389214899724061

RSA100 is a 100 binary bit number made up of two 50 binary bit prime numbers. The motivation in breaking this composite number allows us to find the Euler’s totient number φn. Once this is known, using the public key PU=Ne, it is possible to derive the private key PR=Nd, and hence all cypher-text encrypted (e) messages can thus be decrypted back to plain text, using (d).

3. A simple RSA encryption/decryption example

Using two primes P1 and P2 to generate a composite number N,

N=P1P2=1462001×1462009=2137458620009

Totient φ (Euler’s totient function)

Calculate totient φn = (P1 − 1) (P2 − 1) = (1462001 − 1) (1462009 − 1) = 2137455696000

Arbitrarily choose a public key such that e is an integer, not a factor of modN, and 1<e<φ,e = 13

The public key is made up of N and e, such that PU=Ne=213745862000913. A private key is made up of N and d, such that PR=Nd=2137458620009d.

d, is determined using the extended Euclidean algorithm.

edmodφn=113dmod2137455696000=1d=1973036027077. Therefore, private key, PR=N1d=21374586200091973036027077.

Encrypt a message m, into cipher text C, with public key PU. Let the message m = 1461989. C=memodN=14619891313mod2137458620009=1912018123454. To recover the original message, decrypt using Private Key, PR= (N, d) = (1912018123454, 1973036027077) m=CdmodN=19120181234541973036027077mod2137458620009=1461989.

From this simple example, consider the following: How can we use a known public key PU = (N,e) to decrypt the original message? To decrypt the message, the private key is used: PR=Nd. How can d, be discovered? d is derived using Euler’s totient function [φn = (P1 – 1) (P2 – 1)], and the extended Euclidean algorithm edmodφn=1. However when a public key is transmitted, the totient φn and the two primes P1 and P2 remain secret. If φn, P1 or P2 can be determined, the private key will be compromised and the cypher-text will no longer be secure.

When the totient φn is known, d can be determined through the normal key generation processes, so the determination of the two primes (P1, P2) is not required to recover the message from the cypher-text. The following proof is provided for completeness and shows how the two primes P1, P2 can be recovered if the composite N and the totient φn are known.

4. If the composite N and the totient φnare known, the original primes can be recovered

The quadratic formula can be used to find P1 and P2 φn=P11P21,N=P1,P2. General quadratic form: ax2+bx+c=0=>x=b±b24ac2a

φn=P11P21=P1P2P1P2+1recallingN=P1P2φn=NP1P2+1

Express primes in terms of N, φn P1 = NφnP2 + 1, P2 = NφnP1 + 1N=P1P2substitute for P2 ⟹ N = P1 (Nφn−P1 + 1) = P1 NP1 φnP12 + P1

P12+P1φnN1+N=0ax2+bx+c=0:a=1,b=φnN1,c=N,x=b±b24ac2a
P1,P2=φnN1±φnN1241N21=φnN1±φnN124N2

When N and φn are known: N = 2137458620009, φn = 2137455696000

P1,P2=2924010±854983448010085498344800362=2924010±642=1462005±4
P1,P2=14620011462009

Using the quadratic formula, P1 and P2 can be recovered if the composite N and the totient φn are known.

5. Fermat’s factorization method

N=a2b2=aba+bis the difference of two squares.

P1=ab,P2=a+b,P1+P2=2a,P2P1=2b;a=P2+P12,b=P2P12
N=a2b2=P2+P122P2P122=14P2+P12P2P12=P1P2

As the first trial for a, a1=N,then check if Δa1=a12Nis a square number.

There are only 22 combinations of which the last two digits are a square number. The other 78 can be eliminated.

If Δa1is not a square number, then a2:a2=a1+1.

Now Δa2=a22Na1+12N=a12N+2a1+1=Δa1+2a1+1

Δa3=a32Na2+12N=a22N+2a2+1=Δa2+2a1+1+1=Δa2+2a1+3
Δa4=a42Na3+12N=a32N+2a3+1=Δa3+2a1+2+1=Δa3+2a1+5

so the subsequent differences are obtained by adding two.

Consider the example N = 2137458620009.

a1=N,a1=2137458620009a1=1462005

Check if Δa1=a12Nis a square number.

Δa1=a12N=146200522137458620009=21374586200252137458620009=16=42N=1462005242=146200541462005+4=14620011462009

Maurice Kraitchik, a Belgian mathematician, considered only values of aand b:a2b2modN.

a2b2modNΔ14620052mod213745862000916

6. Euler’s factorization method

Gaussian primes are of the form 4x1, and primes of the form 4x+1are Pythagorean. Fermat’s Christmas theorem on sum of two squares states that an odd prime can be expressed as P=x2+y2iff P1mod4.

Gaussian primes are of the form P3mod4and are not representable as the sum of two squares.

Consider a composite number N:N= P1P2 and P1: P1=a2+b2, P2:P2=c2+d2.

N=P1P2=a2+b2c2+d2=ac2+bc2+ad2+bd2letA2=ac2+ad2,B2=bc2+bd2,C2=ac2+bc2,D2=ad2+bd2N=P1P2=a2+b2c2+d2=ac2+bc2+ad2+bd2=A2+B2=C2+D2N=A2+B2=C2+D2A2C2=D2B2A2C2=D2B2ACA+C=DBD+BP1=gcdACDB22+gcdA+CD+B22,P2=gcdA+CDB22+gcdACD+B22

Consider the example N = 2137458620009; find the factorization values of P1 and P2.

Using the sum of squares, N=2137458620009=3244032+14255602=6436032+13127202.

Combining the even and odds: 14255602-13127202 = 6436032-3244032.

A2C2=D2B2ACA+C=DBD+B=968006319200=2738280112840

Using the greatest common divisor (gcd):

gcdACDB2=gcd96800627382802=1201,gcdA+CD+B2=gcd3192001128402=140gcdA+CDB2=gcd31920027382802=1140,gcdACD+B2=gcd9680061128402=403P1=gcdACDB22+gcdA+CD+B22=12012+1402=1462001P2=gcdA+CDB22+gcdACD+B22=11402+4032=1462009

7. Wiener attack

Wiener’s theorem. Let N=P1P2and P1<P2<2P1and a private key PR=Ndand a public key PU=Ne.Let d<13N14, given a public key PU=Ne, with ed1modφn. The attacker can efficiently recover d [2]. The attack uses the continued fraction method to expose the private key d, when d is small. It assumes eNkdφn=ed1k. Consider a public key PU=Ne:PU=21374586200091973036027077

Continued fraction 19730360270772137458620009=0111146841125110121111237117=

eNkd:eN=19730360270772137458620009=11+111+111=1213=kdφn=ed1k=197303602707713112=2564946835200012=2137455696000

As per Section 2, if the composite N and the totient φn are known, the original primes P1 and P2 can be recovered.

8. Sum of squares

Overmars [3] showed that all Pythagorean triples could be represented as N=n2+n+2m12. If the composite number N, is constructed using two Pythagorean primes (4x + 1) then two representations as the sum of two squares can be found. Euler’s Factorization Method (Section 4) can be applied. Finding these two representations is non-trivial and CPU-intensive. The equation Nmn=n2+n+2m12provides a course search using increments of n and fine convergence using m. In this way n is incremented and m is decremented about N to find the two solutions along the diagonal of a field of NmnN.

Consider the example, N=2137458620009.

Nm1n1=n12+n1+2m112=3244032+324403+2550579+12=3244032+14255602Nm2n2=n22+n2+2m212=6436032+643603+2334559+12=6436032+13127202N1324403550579=N2643603334559=2137458620009

For completeness N can be represented as two Pythagorean triangles as shown [3] ∆(m,n)=∆(a,b,c).

amn=2nn+2m1,bmn=2m12n+2m1,cm.n=n2+n+2m12Δm1n1=Δa1b1c1:Δ324403550579=Δ28197495801360835774088719129410042540009Δm2n2=Δa2b2c2:Δ643603334559=Δ1689741060320130900897679129410042540009

Once the two sum of two squares has been found, Euler’s factorization method (Section 4), can be used to find the prime constructions of N:N=P1P2.

If the composite number (N) is constructed using Pythagorean primes (4x+1), then a solution exists as two sums of two squares and Euler’s factorization method can be applied.

9. Gaussian and Pythagorean primes

As shown in Section 4, if Pythagorean primes (4x+14x3) are used to construct the composite number (N), a solution exists as two sums of two squares. However, if N is constructed using Gaussian primes (4x14x+3), then Euler’s sum of two squares method cannot be used. Is there a test that we can use to see if the composite has been constructed using Pythagorean primes? (Table 1)

4x − 14x + 1x,y=3,151113
4y – 116xy4x+y+116xy4xy159649767
4y + 116xy4yx116xy+4x+y+161671793

Table 1.

Possible composite constructs using Pythagorean and Gaussian primes.

Consider the following composite constructions:

  1. N=4x+14y+1using Pythagorean primes

  2. N=4x14y1using Gaussian primes

  3. N=4x+14y1using a mix of Pythagorean and Gaussian primes

    i. Pythagorean prime construction N=4x+14y+1=16xy+4x+y+1Two sum of two squares representations exist and Euler’s factorization can be used. 1Pmod4. 9Pmod16. See Section 4. 793=1361=32+282=82+272

    ii. Gaussian prime construction N=4x14y1=16xy4x+y+14m34n+1Sums of three squares exist. 1Pmod4. 9Pmod16.

    649=1159=12+182+182=32+82+242=62+172+182=82+122+212=102+152+182=122+122+192Legendre’s three-square theorem can test the composite: N=x2+y2+z2true ifN4a8b+7a,bZ,

    iii. Mixed Pythagorean-Gaussian prime construction N=4x+14y1=16xy4xy1,N=4x14y+1=16xy+4xy1.Sums of four squares exist. 3Pmod4. 1359=767

12+12+62+272=12+12++182+212=12+32+92+262=12+62+172+212=12+92+182+192=12+102+152+212=22+32+52+272=22+32+152+232=32+62+192+192=32+72+152+222=32+112+142+212=52+62+92+252=62+92+112+232=62+92+172+192=62+112+132+212=72+92+142+212=72+132+152+182=92+92+112+222=92+102+152+192=112+142+152+152

In summary, a composite whose construction is based upon both Pythagorean and Gaussian primes can easily be identified when Pmod43is true. However, sums of four squares exist and Euler’s factorization cannot be used. When Pmod41is true, the composite could be constructed using Pythagorean primes or Gaussian primes. Use the Legendre test to further discriminate. When the Pythagorean construct is confirmed, the two sums of two squares can be found, and Euler’s factorization can be used. If the composite construction is both Pythagorean and Gaussian, sums of three squares exist and Euler’s factorization cannot be used.

10. Overmars factorization method

Another classification of the composite number uses a different construct for primes and seeks to define the composite number as follows: Let N=P1P2and test N:N±1mod4=0. Two cases are considered in the classification, and this determines the constructs of the primes used. Note the sign of ±1 determines the case used, and the test is both simple and concise [4].

Case (1)  N+1mod4=0,P1=2mn+1,P2=2m+n1

  1. Let m0N2,mN+

  2. Let n0=4m02N+12,nN+?,nN+mx=m0+1

  3. Let n=4mx2N+12,nN+,mx=mx+1n:nN+

  4. P1=2mn+1,P2=2m+n1

Case (2) N1mod4=0,P1=2mn1,P2=2m+n1

  1. Let m0N+12,mN+

  2. Let n0=2m012N2,nN+?,nN+mx=m0+1

  3. Let n=2mx12N2,nN+,mx=mx+1n:nN+

  4. P1=2mn1,P2=2m+n1

Example N=5959

  1. Test N±1mod4=0: 5959+1mod4=0case1

  2. m0N2m0=59592m0=39,n=6.09,nN+

  3. m1=m0+1=39+1=40

  4. n=4m12N+12n1=44025959+12=11,n1N+

  5. P1=2mn+1P1=24011+1=59,P2=2m+n1P_2=240+111=101

N=P1P2=59x101=5959

This method is reasonable for small composites but becomes computationally unfeasible for large composites.

11. Extensions of the Overmars factorization method

Case (1) N+1moda2=0,P1=amn+1,P2=am+n1

N=amn+1am+n1=a2m2n2+2an1
N=am2an22an+1=am2an12

Case (2) N+1moda2=0,P1=amn1,P2=am+n+1

N=amn1am+n+1=a2m2n22an1
N=am2an2+2an+1=am2an+12

Case (1, 2) N+1a=am2n2±2na:aisafactor ofN+1

n=am2N±1a,mNam=N+an±12a2,

Case (3) N1moda2=0,P1=amn1,P2=am+n1

N=amn1am+n1=a2m2n22am+1
N=am22am+1an2=am12an2

Case (4) N1moda2=0,P1=amn+1,P2=am+n+1

N=amn+1am+n+1=a2m2n2+2am+1
N=am2+2am+1an2=am+12an2

Case (3, 4) N1a=am2n2±2ma:aisafactor ofN1

n=am±12Na2,mN1a,m=N+an2±1a

a:a=gcdmnfor all cases. Choosing the largest value of a ensures a rapid convergence to the solution. This is illustrated by example.

Consider N=211276133

Factors ofN+1211276133+1=2338814441possible values fora
Factors ofN12112761331=2252819033possible values fora

Case (3) N1moda22112761331mod4=0a=2

2mn12m+n1=211276133,m=10247,n=7223gcd102477223=1P1=21024772231=6047,P2=210247+72231=34939

Case (2) N+1moda2211276133+1mod9=0a=3

3mn13m+n1=211276133,m=6831,n=4815gcd68314815=927mn127m+n1=211276133,m=759,n=535gcd759535=1P1=277595351=6047,P2=27759+535+1=34939

Consider N=5959(Section 8)

Factors ofN159591=232331possible values fora
P1=3mn1,P2=3m+n1,m=27,n=7,gcd277=1
Factors ofN+15959+1=235149possible values fora
P1=20mn+1,P2=20m+n1,m=4,n=1,gcd41=1

Consider RSA100

P1=37975227936943673922808872755445627854565536638199P2=40094690950920881030683735292761468389214899724061
P1=2316736131659412543822590349622856694449324700910569+1P1=23352109409208398136023608949147216823230117591559766671
P2=22541211936360279972504921138273186726790856290328531+1P2=231159102965308040372062225690126586444448868040317731
N=P1P2=23352109409208398136023608949147216823230117591559766671     22541211936360279972504921138273186726790856290328531+1
factors ofN+1=22571326342183694613 (121238883482226494959007093210067761113089 3465646351221267386320068406978173999673)factors ofN1=232210974974123 (400944086233670527306310281636760087998315 351567377660286363410284049027879820778576767)

N + 1 is the better candidate, as it has more factors to try. So cases (1,2) are considered.

  1. Case (2) N=amn1am+n+1=a2m2n22an1N+1a=am2n22nTrya:a=25:N+1a=am2n22n,N+110=10m2n22n=N+120=5m2n2nmNa=3902057185540126551228957333948437101890500690019

N+1a=(1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139)+1/20=76130251396126668026780918906631871485903405748069034432895424729006148162947644882700017534600307
a=10m=3903495944393227747674630402410354812189021818113,n=105973150698860355393743126865792026732468154293gcdmn=1P1=10mn+1=37975227936943673922808872755445627854565536638199,P2=10m+n1=40094690950920881030683735292761468389214899724061

When a is small, this method becomes computationally unfeasible.

12. Overmars factorization using smooth factors

Consider the construction of primes (Sections 8 and 9), P=am±n±1. More generally, P:P=am±n±xConsider N=P1P28079781=1249×6469(Table 2).

Case (1) N+x2moda2=0,P1=amn+x,P2=am+nx

xN − x2±xamngcd(m,n)Smoothness
122353114331038626115-smooth
32247942172193113051
522367331366444351
7223210321791821414513-smooth
11223254488790432915-smooth
13223211319166414351
1722367329166464351
19223517892301288715-smooth
2322367327166474351
292234549871821614515-smooth

Table 2.

N − x2.

N=amn+xam+nx=a2m2n2+2anxx2
N=am2an22anx+1=am2anx2

Case (2) N+x2moda2=0,P1=amnx,P2=am+n+x

N=amn1am+n+1=a2m2n22anxx2
N=am2an2+2anx+1=am2an+x2

Case (1,2) N+x2a=am2n2±2nxa:aisafactor ofN+x2

n=am2N±xa,mN+ax2a,m=N+an±x2a2

Case (3) Nx2moda2=0,P1=amnx,P2=am+nx

N=amnxam+nx=a2m2n22amx+x2
N=am22amx+x2an2=amx2an2

Case (4) Nx2moda2=0,P1=amn+x,P2=am+n+x

N=amn+xam+n+x=a2m2n2+2amx+x2
N=am2+2amx+x2an2=am+x2an2

Case (3,4) Nx2a=am2n2±2mxa:aisafactor ofNx2

n=am±x2Na2,mNx2a,m=N+an2±x2a
N=904329119043+2911=1249×6469

When a smooth x can be found, larger a values allow for faster convergence to a solution. The selection of x and a is somewhat arbitrary and prime constructs are a modification of Fermat’s a2 − b2. Smooth factors of N±x2produce larger a values and convergence faster to a solution.

13. Primes

The current state of the art in prime number generation is Atkin’s sieve [5, 6].

The algorithm completely ignores any numbers with remainder mod 60 that is divisible by 2, 3 or 5, since numbers with a mod 60 remainder divisible by one of these three primes are themselves divisible by that prime. Atkin stated three theorems given below:

  1. All numbers n with mod 60 remainder 1, 13, 17, 29, 37, 41, 49 or 53 are mod 4 ≡ 1. These numbers are prime if the number of solutions to 4x2 + y2 = n is odd and the number is squarefree.

  2. All numbers n with mod 60 remainder 7, 19, 31 or 43 have a mod 6 ≡ 1. These numbers are prime if and only if the number of solutions to 3x2 + y2 = n is odd and the number is squarefree.

  3. All numbers n with mod 60 remainder 11, 23, 47 or 59 have a mod 12 ≡ 11. These numbers are prime if and only if the number of solutions to 3x2y2 = n is odd and the number is squarefree.

None of the primes are divisible by 2, 3 or 5 and are not divisible by their squares (22, 32, and 52). For a thorough analysis of “primes of the Form x2 + ny2” the reader is referred to a text by Cox [7].

The often overlooked works of Dubner, who is credited with the term “primorial” [8] are now considered [9, 10]. The primorial is a factorial of primes: 1#=2,2#=2x3=6,3#=2x3x5=30,4#=#3x7=210and so on. 0#=1. The primorial is by definition squarefree.

The nth primorial is the product of n primes, where πnis the prime counting function.

n#=i=1πnpi=pπn#

Using this structure, Dubner was able to create series of primes in a particular primorial.

It can be shown that the structure of primes is palindromic in the primorials [11].

For example, in Figure 1, take the discrete derivative of the numbers in the third primorial, 3#. The following palindromic sequence can be added to #3=30and subtracted from #4=210to determine all of the primes in that primorial:

Figure 1.

Creating primes using primorials.

30+1,10,2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,22101,10,2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2

This describes the second table in Figure 1. All of the primes in the third primorial can be found using 24 small numbers. Mod 7 is used to sieve and eliminate composite multiples of 7. Mod 11 and 13 are used to highlight further composites, but these are kept and used to generate primes in the next primorial.

Modulo testing: Pmodm=0,Pk<m<k+1#

For k=3,Pk:P3=5,Pk+1:P4=7,#3=30,#4=210,21014,m=7,11,13,eliminate Pk+1=7

As shown in Figure 2, 24 small numbers are used to derive 482 new values. This uses 10 modulo tests to identify composites and 1 modulo test to eliminate factors of 11 (Figure 3).

Figure 2.

Primes in the 4th primorial.

Figure 3.

Gaps between primes of each successive primorial.

Pn#, ΔPn1#Current primorial and the difference between primes from the previous. Simple array descriptor provides rich prime fields of higher densities. Small numbers describe primes of higher magnitude. Large arrays of primes can be stored in much less memory.

14. Number systems

Conventional numbering systems consist of a base (or radix).

The primorial number system is said to be ‘primoradic’; having a primorial base. The primorial number system is a mixed radix numeral system adapted to the numbering of the primorials (Table 3).

n7654321
pnn1713117532
n#5105103003023102103062
highestPn+1118161210641

Table 3.

Primorial radix number system.

General properties of mixed radix number systems apply to the base primorial system. The primorial number system OEIS A000040 is denoted by a subscript “∏”.

Consider the following example:

Primorial to decimal, Base to Base10

3 4 1 0 1 stands for 3443120110, whose value is

=3×p4#+4×p3#+1×p2#+0×p1#+1×p0#=3×210+4×30+1×6+0×2+1×1
=3×7+4×5+1×3+0×2+1×1=75710.

Decimal to primorial, Base10 into Base∏

75710 into a primorial representation by successive divisions:

757 ÷ 2 = 231, remainder 1

378 ÷ 3 = 126, remainder 0

126 ÷ 5 = 25, remainder 1

25 ÷ 7 = 3, remainder 4

3 ÷ 11 = 3, remainder 3 => 3 4 1 0 1

15. RSA100 factorization using primorials

N=P1P2=aPk#+caPk#+d=aPk#2+c+daPk#+cd
Pk#2N1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139/p31#2aPk#2N1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139/9p31#2
N=aPk#+caPk#+d=aPk#+cPk1#+eaPk#+dPk1#+fPk#=PkPk1#N=aPkPk1#+cPk1#+eaPkPk1#+dPk1#+f=(aPk+c)Pk1#+eaPk+dPk1#+fN=aPk+caPk+dPk1#2+(faPk+c)+eaPk+d)(Pk1#+ef
aPk+caPk+dPk1#2NaPk+caPk+d=NNmodPk1#2Pk1#2
N=1523830x2+27406046005166967437863263040740903499726862x+ 12231378224719217781270707850591564671548897759}

1523830=2×5×7×11×1979=7701979=12344641234+745Not symmetrical about square root [12]

1522868=22×317×1201=12011268=1234331234+34Symmetrical about square root.

N=aPk+caPk+dPk1#2+(faPk+c)+eaPk+d)(Pk1#+efaPk+caPk+dPk1#2NaPk+caPk+d=NNmodPk1#2Pk1#2
1521642935492617539765579106664136748401379615914312169315386041883234627722692028711378934397966800/p30#2

Consider each congruency and look for a factorization that is symmetrical about the square root.

In this case 1234 + 34 =1268, 1234 – 33 = 1201.

N=aPk+caPk+dPk1#2+(faPk+c)+eaPk+d)(Pk1#+ef
30431475913593577738588710930551227419722971658953x+151816659580901664885523419281115998823527019067345405631401183567090345342039152734187917869,
N=aPk+cPk1#+eaPk+dPk1#+f
k=31,P31=127,aPk+c=1201,aPk+d=12a=9,c=58,d=125,P31=127
N=9P31#+58P30#+e9P31#+125P30#+f
N=12011268P302+1201f+1268eP30+ef
N=a2+mP312+ac+d+nP31+cd
a2+m=NNmodPk2#Pk2#=94a=9,m=13
a2Pk#2+ac+d+mPk#Pk#+nPk#+cd
Pk#=PkPk1#N=12011268P302#+1201f+1268eP30#+ef
N=9P31#+58P30#+e9P31#+125P30#+f

Repeat these steps for P29#and so on… (Table 4)

k313029282726252423222120191817161
Pk127113109107103101978983797371676159532
P195841324310113146050543333212121
P2912546106759571792131958233230131

Table 4.

P1 and P2 as base Primorial numbers.

N=9P31#+58P30#+41P29#+g9P31#+125P30#+46P29#+h
N=1522868x2+3043147581359377738588710930551227419722971658953x+151816659580901664885523419281115998823527019067345405631401183567090345342039152734187917869.N=1268x+131416668713543553156137150841043477425966207411201x+11552313802126969246479999301689200142637563209,x=p30#)
N=9P31#+58P30#+e9P31#+125P30#+fN=9P31#+58P30#+115523138021269692464799993016892001426375632099P31#+125P30#+13141666871354355315613715084104347742596620741N=9P31#+58P30#+41P29#+g9P31#+125P30#+46P29#+hN=9P31#+58P30#+41P29#+831789325949168631706766649344199459626767799P31#+125P30#+46P29#+273857017733028251413011637989228497546748161

The conversion to a decimal from the base primorial (Section 12) provides P1 and P2

P1=3797522793694367392280887275544562785456553663819910P2=4009469095092088103068373529276146838921489972406110

16. Lenstra-Lenstra-Lavász lattice reduction (LLL)

The (LLL) forms the basis of the Coppersmith attack (Section 15), and a brief explanation is given here with further reading and references for the reader. The Lenstra-Lenstra-Lavász (LLL) lattice basis reduction algorithm [13] calculates an LLL-reduced, short, nearly orthogonal lattice basis, in time Od5nlog3B, where B is the largest length of bi under the Euclidean norm, given a basis B=b1b2bdwith n-dimensional integer coordinates, for a lattice L (a discrete subgroup of Rn) with dnand giving polynomial-time factorization of polynomials with rational coefficients.

A thorough explanation is given by Bosma [14], and a summary of the example contained in the reference is given below.

  1. INPUT: Let lattice basis b1,b2,b3Z3be given by the columns of 113105126

  2. OUTPUT: LLL-reduced basis 011100012

Using the Lenstra-Lenstra-Lavász lattice reduction (LLL), the short vectors in a lattice can be found. This is used by the Coppersmith attack. Coppersmith's algorithm uses the LLL to construct polynomials with small coefficients that all have the same root modulo. When a linear combination is found to meet inequality conditions, standard factorization methods can find the solutions over integers.

17. Coppersmith attack

When dis small andeis largeviathe Euler totient rule, the Wiener attack (Section 5) can be used. Conversely, when d is large, e is small. Particular applications of the Coppersmith method for attacking RSA include cases when the public exponent e is small or when partial knowledge of the secret key is available (Section 13) [15].

A small public exponent e, reduces the encryption time. Common choices for e are 3, 17 and 65537216+1[16]. These are Fermat primes Fx:Fx=22x+1and are chosen because the modular exponent derivation is faster. The Coppersmith method reduces the solving of modular polynomial equations to solving polynomial equations over integers.

Let Fx=xn+an1xn1++a1x+a0and Fx00modMfor an integer x0<M1n. Coppersmith can find the integer solution for x0by finding a different polynomial frelated to Fthat has the root x0modMbut only has small coefficients. The small coefficients are constructed using the LLL (Section 14). Given F, the LLL constructs polynomials p1x,p2x,pnxthat all have same root x0modMa,aZ.adepends on the degree of Fand the size of x0. Any linear combination has the same root x0modMa.

The next step is to use LLL to construct a linear combination fx=cipixof the pixso that the inequality fx0<Maholds. Then standard factorization provides the zeroes of fxover Z.

Let Nbe an integer and fZxbe a monic polynomial of degree d, over integers such that xd+cn1xd1++c2x2+c1x+c0. Set X=N1dfor 1d>>0. Given Nfthen all integers x0<X:fx00modNcan now be found. All roots of fmodN, smaller than X=N1dcan be found.

18. Pohlig-Hellman

The Pohlig-Hellman [17] algorithm is a method to compute a discrete logarithm (which is a difficult problem) on a multiplicative group. The order of which is a smooth number (also called friable), meaning its order can be factorized into small primes. A positive integer is called B-smooth if none of its prime factors is greater than B. For example, 1620 has prime factorization 22 × 34 × 5; therefore 1620 is 5-smooth because none of its prime factors are greater than 5. This is similar to that of the Overmars factorization method (Section 10). The Pohlig-Hellman [17] algorithm applies to groups whose order is a prime power. The basic idea is to iteratively compute the p-adic digits of the logarithm by repeatedly “shifting out” all but one unknown digit in the exponent and computing that digit by elementary methods. This is a similar idea to Section 13.

INPUT: A cyclic group Gof order nwith a generator g, an element hG, and a prime factorization n=i=1rpieiOUTPUT: The unique integer x0n1:gx=h

Example: Let p=41,α=7,β=12solve 12=7xmod41

  1. Find the prime factors of p1411=40=235gs=2,5. Find one xfor each g.

  2. For g=2,x=20x0+21x1+22x223cubicthree terms

    i. x0:βp1g0=αp1gX012402=7402x01mod41=1x0mod41test forx0:x0=0,1,2,

    1mod4110mod411mod4111mod41hencex0=1

ii. x1:β1=β0αx0=1271=31mod41

β1p1g1=αp1gX1,g1=2231404=7402x13110=720x131101mod41hencex1=0

iii. x2:β2=β1αx1=3170=31mod41

β2p1g2=αp1gX2,g2=2331408=7402x2315=720x21mod41=112mod41 hencex2=1

Recall: X=20x0+21x1+22x2soX=1.1+2.0+4.1=5x=5mod23=5mod8. Now we need another xfrom the other g

  • For g=5,x=50x0onlyone5,onlyoneterm.

    i.x0:βp1g0=αp1gX012405=7405x0128=78x01837x0mod41

  • x00,1tryx0=218372mod4118373mod41hencex=50x0=13=3
    Hencex=3mod5,sox=5mod8andx=3mod5

    By the Chinese remainder theorem, x=13mod40since the exponentsarep1=411=40hence12713mod41.So the solution to 12=7xmod41x=13.

    19. Shor’s algorithm

    Shor’s algorithm [18], factors composite numbers, N=P1P2, consisting of two primes in polynomial time using quantum computing techniques. The algorithm evaluates the period of axmodnwhere gcdan=1.This is inefficient using sequential computing on a conventional computer. When run on a quantum computer, a congruence of squares with probability 0.5 occurs in polynomial time. For two co-prime sinusoids of period P1 and P2, at what point do they zero-cross each other? The phase of each sinusoid at any given point is observed, and if they are factors of N then the phase of P1 and P2 is zero. Shor’s algorithm tests the phase of P1=P2=N=0(Figure 4).

    Figure 4.

    N as a composite of two Sinusoids P1 and P2 [19].

    Phase estimation is well suited to quantum computers and hence this factorization technique produces solutions in polynomial time. For further information on quantum phase estimation, the reader is directed to WIKI [20]. The impact of this type of attack is discussed in detail by Mosca [21].

    1. Choose a<N

    2. Find the period rof anmodN(using Quantum computing)

    3. Check ris even:ar2+10modN

    4. P1=gcdar21N,P2=gcdar2+1N

    Consider N=35,

    1. a:a<N,choosea=8

    2. Find the period rof anmodN

      1. 81mod35=8

      2. 82mod35=29

      3. 83mod35=22

      4. 84mod35=1

      5. 85mod35=8periodr=4

    3. r:reven,r=4is even

    4. P1=gcdar21N=gcd842135=gcd6335=7P2=gcdar2+1N=gcd6535=5

      Euler’s factorization (Section 6) cannot be used because 7 has no sum of squares nor does 35.

    Fermat’s factorization (Section 5)

    N=aba+b=a2b2=361=6212=616+1=57=35

    Overmars factorization (Section 10)

    N=amn+1am+n+1=242+1[24+2+1=57

    Overmars triangles (Section 8) ∆(m,n) = ∆(a,b,c): ∆(3,1)=∆(12,35,37)Recalling bmn=2m12n+2m1b31=57

    20. Attacking public key infrastructure

    Public infrastructure cryptographic hardware uses a library RSALib. This is found in both NIST FIPS 140-2 and CC EAL 5+. These are certified devices for use in identity cards, passports, Trusted Platform Modules, PGP and tokens for authentication and software signing. This is in use in tens of millions of devices worldwide. Nemec et al. [22] have identified a vulnerability that allows for the factorization of 1024 and 2048 bit keys in less than 3 CPU months.

    RSALib primes are of the form p=kM+65537amodM.

    These can be fingerprinted using the discrete logarithm log65537NmodM.

    N=P1P2=kM+65537amodMlM+65537bmodMN65537a+b65537cmodM

    The public modulus Nis generated by 65537 in the multiplicative group ZM. The public modulus of RSALib can thus be fingerprinted with the discrete logarithm c=log65537NmodM. This can be factorized using Pohlig-Hellman (Section 16). The group G=65537is smooth G=2434527111317232937415383for RSA512 keys. The smoothness of G is due to the smoothness of M being Primorial.

    Factorization is achieved using the Coppersmith algorithm with a known pmodM:65537amodM. Nemec et al used the Howgrave-Graham[23] implementation of the Coppersmith’s algorithm to find a small solution x0of: fx=x+Mp1modN65537amodMmodN

    A summary of RSALib vulnerability and its impact is now given and the reader is directed to Memec et al. [22] for further detail. eIDs used in passports for citizens are affected. Code signing is vulnerable. Twenty-four percent of TPMs used in laptops are affected (sample size 41). A third of PGP, used in email systems could be factorizable. There was no observable impact on TLS/HTTPS. One hundred percent of SCADA systems sampled were affected (sample 15). E-health and EMV payment cards were also likely to be susceptible.

    Mitigating the impact of the RSALib vulnerability requires changing the algorithm. This requires a firmware replacement which is not possible in already deployed devices such as smartcards and TPMs whose code is stored in read-only memory. Key lengths not of 512, 1024, 2048 and 4096, such as RSA3936 appear to be resilient. The use of key pairs outside of vulnerable devices could be deployed using another library. Changes to RSALib are required so that proveable safe primes are constructed not using the vulnerability.

    21. Overmars factorization, bringing it together

    Section 11 considered the following cases. The following discussion generalizes these cases and provides the structure for algorthmic solutions to be found. The palindromic nature of primes (Section 12) can be exploited further to explore solutions in a particular Primorial range. Recall;

    Case12N+x2moda2=0,P1=amn±x,P2=am+nxN=amn±xam+nx=a2m2n22anxx2=am2anx2N+x2a=am2n2±2nxa:aisasmooth factor ofN+x2
    n=am2N±xa,m:N+ax2am<m=+anx2aP1=amnx=amam2NNmodamam2N0
    Case34Nx2moda2=0,P1=amnx,P2=am+nxN=amnxam+nx=a2m2n22amx+x2=amx2an2Nx2a=am2n22mxa:aisasmooth factor ofNx2n=amx2Na,m:N+a2±x2am<,m=N+an2±x2aP1=amnx=amxamx2NNmodamxamx2N0

    Now we need to develop the methodology for finding (selecting) aand x. This brings together the concepts of primorials [9], Smooth [24], small factors [17], factorization (Fermat), modulo testing as per Atkin’s Sieve [5] and the structure of primes (Sections 12 and 18), to find as large an a as possible so that Overmars Factorization [4] converges more rapidly to a solution.

    Recall the following (Section 12). Primes are of the form P=4x±1andP=6x±1. Composite numbers, constructed from these primes: N=P1P2, are a combination of Pythagorean and Gaussian primes. The following test N±1mod40can be used to determine which combination of primes was used to construct the composite. If N+1mod40is true a mix of Pythagorean and Gaussian primes was used. If N1mod40is true then the composite consists of only Gaussian or only Pythagorean primes. The Sieve of Atkin [5] uses mod120and mod600. This is now applied as per Overmars [4] in the following manner, if mod120is true then a=6, if mod600is true let a=30. The ideas of Atkin are further extended in both directions: mod40a=2,mod4200a=210,mod46200a=2310,mod600600a=30030

    This is Primorial, Pk#:Pk#,kthPrimorialis”Smooth”. The general form (Section 19) is now given: Case (1 , 2 ) N+x2a=am2n2±2nx, N+x2moda0,a:a=2Pk#,x:1xNaCase (3 , 4 ) Nx2a=am2n22mx,Nx2moda0,a:a=2Pk#,x:1xNa

    If a:a=2Pk#can be choosen, then we search xin the primes to find solutions to N±x2mod2Pk#0A solution is found for P1m, when P1Z. Case (1 , 2 ) NmodP10,P1:P1=amam2NCase (3 ,4) NmodP10, P1:P1=amxamx2N

    Consider Section 11 example, N=P1P28079781=12496469

    Integer solutions x=N2bPk#. From Table 5, determining which x value should be used is not clear. Whilst x=1should work, no solutions will be found if a:a=30.From Table 5 only when x=11or19do we find solutions. Ranking the possible solutions in terms of factors 29 (8) would be first, 19 (7) second and 11 (6) third.

    xmod60mod180mod1620N − x2±xbamngcd(m,n)Smoothness
    1022353114331038626115-smooth
    102235311433664343515-smooth
    11002232544887390432915-smooth
    1902235178921301288715-smooth
    290002234549871821614515-smooth

    Table 5.

    Smooth candidates of the factors of N − x2.

    Based upon low order factors the rankings would be 29 2234first and 11 2232second. Setting a=30,x=29will not find solutions for m,n. Setting a=30,x=11m=129,n=57,gcd12957=3,so the optimal value for a=90.P1=30m1130m112N. Look for solutions to 30m112Nwhich are a perfect square. In this case, m=129301291128079781=6812100=26102.

    Recall that the starting value for m:N+a2±x2am<N12a99m<134663, 30 iterations.

    Whilst this is quite a good result the first failure needs also to be taken into account. This would be bound by the Primorial and P1:1<P1<N:amam2N=1m<N+12a

    Here m:N+a2±x2am<N+12a123m<134663134540iterations.

    This can be further bound by the Primorial. In the case of RSA numbers, the binary bits available to represent a particular prime number range can also be used to bound the range (Table 6).

    xModulo testingN − x2amngcd(m,n)Smoothness
    60420462060060
    10233251014611423305-smooth
    11025351397157251305524200225-smooth
    1900243357157753121078928617-smooth
    610002435711310667231011-smooth
    401000023357211131914933003013-smooth
    160100002333571113216973003013-smooth
    4528100002335711131815013003013-smooth
    455890000253571113453173003042213-smooth

    Table 6.

    Smooth candidates of the factors of N − x2.

    Consider N=23852269081.

    In this case, solutions using modulo testing generate good candidates to solve for (m, n), however for a=30030, three of the candidates have no solution. Using sequential programing, each possible candidate is considered one after another, until the maximum m value. However, using parallel programing techniques on GPUs (such as nVIDIA P100s), all of the candidates can be tested simultaneously and the processes are all terminated when one of the processes finds a solution. This is very efficient and effective in finding P1, P2. Once these are known, along with the public key Pu=Ne, using Euler’s totient, the private key PR=Ndcan be determined. Once the private key is known the cypher-text is no longer secure.

    22. Conclusion

    In short RSA is secure and difficult to factorise. Conventional sequential computing machines, running in polynomial time, take an infeasible amount of CPU cycles to find factorization solutions to RSA keys. Quantum computing holds great promise and Shor’s algorithm [18] demonstrates how this can be achieved. However, quantum computing is realistically still some way off. Opportunities exist using conventional computing (sequential and parallel) with better mathematical techniques. Section 18 showed how implementation vulnerabilities are introduced when “clever” low cost (CPU cycles) are implemented. The case in point showed methods for signature identification, upon which tailored targeted attacks could be launched against infrastruture FIPS140-2 devices, such as cryptographic routers. These sorts of attacks can be deployed in polynomial time using sequential programing techniques. Section 20, Overmars shows how factorization can be implemented using parellel processing techniques.

    There is still much to be done and areas of further interest are a better understanding of the structure of primes. This will lead to faster prime number generating algorithms and hence faster solutions to the factorization problem. This will also lead to the generation of more robust primes that are less susceptible to factorization methods. An example of this is the use of non-Pythagorean primes. Section 5 showed how Euler’s factorization could be used to attack such composite numbers. Hence a simple method to thwart this would be to use a mix of Pythagorean and Gaussian primes. Section 6 showed how small dvalues in the RSA private key PR=Ndcould be attacked using Wiener’s method. Small evalues in the public key PU=Necan be attacked using a combination of LLL, Coppersmith and Pohlig-Hellman (Sections 15–17). All of these attacks can be mitigated by choosing dandecarefully and ensuring that both are sufficiently large.

    Development of quantum computing is continuing at break-neck speed, however useful machines are yet to appear. Parallel computing however is here and now and whilst factorizing RSA keys is not achievable on conventional computers in polynomial time, parallel computing has allowed for multiple solutions to be tested simultaneously. This is an area where research continues and new algorithms such as shown in Sections 20 and 14 lend themselves well to GPU parallel processing systems.

    There are known knowns. These are things we know that we know. There are known unknowns. That is to say, there are things that we know we don't know. But there are also unknown unknowns. There are things we don't know we don't know” [25].

    Download

    chapter PDF

    © 2019 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

    How to cite and reference

    Link to this chapter Copy to clipboard

    Cite this chapter Copy to clipboard

    Anthony Overmars (June 17th 2019). Survey of RSA Vulnerabilities [Online First], IntechOpen, DOI: 10.5772/intechopen.84852. Available from:

    chapter statistics

    140total chapter downloads

    More statistics for editors and authors

    Login to your personal dashboard for more detailed statistics on your publications.

    Access personal reporting

    We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

    More About Us