Everything You Wanted To Know about Integer Factorization, but Were Afraid To Ask ..

Defining The Limits of RSA Cracking

Everything You Wanted To Know about Integer Factorization, but Were Afraid To Ask ..

Defining The Limits of RSA Cracking

Many of our public key methods involve the multiplication of prime numbers. For example the security of RSA is based on the multiplication of two prime numbers (P and Q) to give the modulus value (N). If we can crack the N value, we will crack the decryption key. Overall every integer — which is not prime — can be created as a multiplication of prime numbers.

For RSA, here is an example of the encryption key, the value of N, and the cipher, [here]:

Encryption parameters
e:	65537
N:	1034776851837418228051242693253376923
Cipher:	582984697800119976959378162843817868
We are using  60 bit primes

Now we have to crack N by finding the primes that make up the value.

If we use this [link], we get:

Factors
-------
1,034,776,851,837,418,228,051,242,693,253,376,923 = 1,086,027,579,223,696,553 x 952,809,000,096,560,291

p=1,086,027,579,223,696,553 q=952,809,000,096,560,291

Now we work out PHI, which is equal to (p−1)×(q−1):

>>>p=1086027579223696553
>>>q=952809000096560291
>>> print (p-1)*(q-1)
1034776851837418226012406113933120080

Now we find e^{−1} (mod PHI) (and where (d×e) (mod PHI)=1), such as using [here]:

Inverse of  65537  mod  1034776851837418226012406113933120080
Result: 568411228254986589811047501435713

This is the decryption key. Finally we decrypt with Message=Cipher^d (mod N):

>>> d=568411228254986589811047501435713
>>> cipher=582984697800119976959378162843817868
>>> N=1034776851837418228051242693253376923
>>> print pow(cipher,d,N)
345

The message is 345.

Finally, let’s check the answer. So we can recipher with the encryption key and we use Cipher=M^e (mod N):

>>> m=345
>>> e=65537
>>> N=1034776851837418228051242693253376923
>>> print pow(m,e,N)
582984697800119976959378162843817868

This is the same as the cipher, so the encryption and decryption keys have worked. Thus the encryption key is [65537, 1034776851837418228051242693253376923] and the decryption key is [568411228254986589811047501435713, 1034776851837418228051242693253376923]

So what methods can we use to factorize the modulus? Let’s look at a few.

Difference of squares

This is one of the simplest methods, and we factorize a value if we take a value and then add a square valued value. if they result is a square, we can use the difference of squares to determine the factors.

First we start with:

x²−y²=(x−y)(x+y)

If we now have a value of N which we can present as:

N=y²−x²

The factors of Nwill then be:

(x+y) and (x−y)

Now if we rearrange N=x²−y² we get:

N+y²=x²

We can thus take N and then take values of y, and see if the result is a square. If it is, we have found two factors. An example, if N is 4823, we can then take values of y:

x   N + (y*y)
------------ 
0  4823
1  4824
2  4827
3  4832
4  4839
5  4848
6  4859
7  4872
8  4887
9  4904
10 4923
11 4944
12 4967
13 4992
14 5019
15 5048
16 5079
17 5112
18 5147
19 5184 --> 5,284 = 72 * 72 ! We have found it!

In this case we have found that 4924+192=722

The factors are thus 72+19 and 72−19, or 91 and 53.

Finding factors for 4823
Factors: ( 72 + 19 ),( 72 - 19 )
Factors are:  (53, 91)

An outline of the code used is:

import math
value=32128
def getfactor(N):
        i=0
        while True:
                val = N + i*i
                sq = int(math.sqrt(val))
                if (sq*sq == int(val)):
                        return(sq-i,sq+i)
                i=i+1
                if (i==1000): return("Cannot find")
        return i
print getfactor(value)

A demo of this method is here, and here are some examples:

  • p=6,161 (Factors: 61 and 101) Try!
  • p=32,128 (Factors: 64 and 502) Try!
  • p=53,421 (Factor: 3 and 17,807) Try!

Quadratic residues mod n

If we have the form of x²=a(mod p), we must find a value of x which results in a value of a (mod p). It is actually a difficult problem to solve. If a solution exists, the value of a is a quadradic residue (mod n). In modular arithmetic this operation is equivalent to a square root of a number (and where x is the modular square root of a modulo p). In the following we will try and solve for the value of x, and also generate the Legendre symbol value.

If we have the form of:

x²=a (mod p)

we must find a value of x

which results in a value of a(modp). If a solution exists, the value of a is a quadradic residue (mod n). In modular arithmetic this operation is equivalent to a square root of a number (and where x is the modular square root of a modulo p).

For example, if we have a=969

and p=1223, we get:

x²=968(mod1223)

For this we get a solution of:

4532=968(mod1223)

If we have a=1203 and p=1223 , we get:

x²=1203(mod1223)

For this we get a solution of:

3752=969(mod1223)

Thus 968 and 1203 are quadratic residues modulo 1223.

The form of x²=a(mod p) is not always solvable:

For example, if we have a=209 and p=1223 , we get:

x²=209(mod1223)

x²=888(mod1223)

Also, if a shares a factor with p it is also not solvable. For example:

x²=39(mod13)

will return a zero value for x.

If we take a value of p=53, we get the following values [here]:

0, 1, 4, 6, 7, 9, 10, 11, 13, 15, 16, 17, 24, 25, 28, 29, 36, 37, 38, 40, 42, 43, 44, 46, 47, 49, 52

A sample run of the code gives:

Quadradic residue (mod n) solver
 a:	47
 p:	53
We need to solve for:
  val^2 =  47 (mod  53 )
-----------------------
Result: 10
( 10 )^2 =  47 (mod  53 )
-----------------------
For a prime number of  53 here are the residues up to p (or 100)
1 4 6 7 9 10 11 13 15 16 17 24 25 28 29 36 37 38 40 42 43 44 46 47 49 52

In this case we see that 10 is a possible quadratic residue for a p of 53. The solution is thus:

102=47(mod 53)

You can see a demonstration here and here are some examples:

  • Solve x²=12 (mod 13)[Ans: 8] Try!
  • Solve x²=968 (mod 1223) [Ans: 453] Try!
  • Solve x²=1203 (mod 1223) [Ans: 375] Try!
  • Solve x²=47 (mod 53) [Ans: 10] Try!
  • Solve x²=209 (mod 1223) [No solution!] Try!
  • Solve x²=888 (mod 1223) [No solution!] Try!
  • Solve x²=39 (mod 13) [No solution!] Try!

Elliptic curve factorization

The elliptic curve factorization methods (often known as Lenstra elliptic curve factorization) is the third fastest integer factorization method. It was developed by Hendrick Lenstra, and is particularly suitable to numbers with less than 60 digits and especially useful in finding small factors.

You can see a demonstration here.

Pollard’s ρ method

In this method we keep iterating until the gcd() value — the greatest common denominator — is not unity. The following are some examples:

  • The factors of 273 are 3 and 91. Pollard
  • The factors of 116,393 are 239 and 487. Pollard
  • The factors of 3,789,829 are 3209 and 1181. Pollard
  • The factors of 7,388,399 are 3571 and 2069. Pollard
  • The factors of 39,2524,199 are 919 and 427121. Pollard

The value returned from the non unity gcd() value is then the first factor, as shown in this demo:

A      B      GCD
7      52     1
52     104112 1
2707   212732 1
104112 214627 1
86677  44835  1
212732 192645 379
First factor is 379

The Python code is:

def gcd(x,y):
	if y==0:
		return x
	else:
		return gcd(y,x%y)
def f(x,n):
	return (x*x+3) %n
def pollardrho(a):
	print "A B GCD"
	x=2
	y=2
	d=1
	while d==1:
		x=f(x,a)
		y=f(f(y,a,),a)
		d=gcd(abs(x-y),a)
		print x,y,d
		if d>1 and a>d:
			return d
		if d==a:
			return -1
print "First factor is "+str(pollardrho(361187))

Conclusions

We must define hard problems in cryptography, and the hard problems we have in RSA encryption is the factorization of a value into its prime number factors. Our benchmark will thus be the speed in which we can factorize this. For 60-bit primes, it is easy, but for 1,024 bit primes it get extremely difficult, and will consume a great amount of energy.

Join Coinmonks Telegram Channel and Youtube Channel get daily Crypto News

Also, Read