RSA security systems based on numbers
-
RSAm = Prime1 * Prime2
-
A product of two large primes
-
RSAm has m decimal digits
-
RSA corporation recommends m>=200
|
|
Bank of England and English Savings and Loan based on m=155 (512 binary digits)
|
|
RSA129 cracked by factoring with email team using sophisticated version of Quadratic Sieve. RSA155 will use better Number Field Sieve
|
|
Need x2 = y2 mod(RSAm) as then gcd(x+y,RSAm) likely to be interesting factor
|
Find x and y by finding lots of interesting a's
-
a = product of small primes = b2 mod(RSAm)
|
|
Given these a's factored into primes, multiply together so powers of primes are even. This gves desired x
|
|
This last step requires graph theory and solution (for Bank of England) of 5 million linear equations
|
