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


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, 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.


  • 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[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 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,


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


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


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


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.


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


so the subsequent differences are obtained by adding two.

Consider the example N = 2137458620009.


Check if Δa1=a12Nis a square number.


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


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.


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.


Using the greatest common divisor (gcd):


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=


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.


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


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


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


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


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


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


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


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


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


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


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


Consider N=5959(Section 8)

Factors ofN159591=232331possible values fora
Factors ofN+15959+1=235149possible values fora

Consider RSA100

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


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

Table 2.

N − x2.


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


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


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


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


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


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.


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.


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).


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


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=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.


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

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


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


Table 4.

P1 and P2 as base Primorial numbers.


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


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,


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


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.


  • x00,1tryx0=218372mod4118373mod41hencex=50x0=13=3

    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)


    Overmars factorization (Section 10)


    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.


    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
    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

    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

    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].


    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