Factorizing Integers with the Rho Method

Factorizing Integers with the Rho Method

I start with a statement … “Integer factorization is not in NP-Complete!”. So why is it the source of many public key methods, such as RSA? Well, it is a hard problem at the current time, but with the advent of quantum computers, it will not be.

Cracking RSA

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]

Pollard’s rho algorithm

Many problems in public key encryption derive the security strength from the difficulity in factorizing a number into its prime number elements. In RSA, if we can factorize the modulus (N) into its prime numbers (p and q), and can easily crack the cipher. The Pollard’s rho algorithm can be ued to factorize integers, and was iinvented by John Pollard in 1975. Its main advantage is that it only requires a small amount of memory. Also its run time is proportional to the square root of the smallest prime factor. The basic algorithm takes a value (n) and a function g(x) and which is a polynomial in x computed modulo p. Normally g(x)=(x²+1)(mod n).

A basic algorithm is [here]:

package main

import (
    "fmt"
    "strconv"
    "os"

)

func g(x,p int) int {

    return (x*x +1) % p
}

func gcd(x, y int) int {
    for y != 0 {
        x, y = y, x%y
    }
    return x
}
func abs(x int) int {
    
    if (x<0) { return -x }
    return x
}

func main() {

    x := 2
    y := 2
    d := 1
    p:=8051
    i:=1

    argCount := len(os.Args[1:])

        if (argCount>0) { p,_= strconv.Atoi(os.Args[1])}

    fmt.Printf("i\tx\ty\n-------------------\n")
    for d == 1 {
    fmt.Printf("%d\t%d\t%d\n",i,x,y)
        x = g(x,p)
        y = g(g(y,p),p)

        d = gcd(abs(x-y), p)

    i=i+1
    }
    fmt.Printf("\n%d=%dx%d",p,d,p/d)

}

A sample run of factoring 8,051 gives [here]:

i   x   y
-------------------
1   2   2
2   5   26
3   26  7474

8051=97x83