Saturday, January 05, 2008

 

Factoring relations and RSA

There are a couple of questions that have to be answered to determine if RSA encryption is ended as a viable approach by my factoring relations.

Those relations, which I posted before with a derivation are:

Given

z^2 =3D y^2 + nT

you can solve for z modulo a given prime p coprime to y, z and nT with:

z =3D (2=E1)^{-1}(1 + 2=E1^2)k mod p

and

k^2 =3D (=E1^2+1)^{-1}(nT) mod.

With n=3D1, if you can solve the quadratic residues modulo a prime p where p>sqrt(T), then you can just solve for z mod p, and y mod p, and get a factor from z-y mod p or z+y mod p as one of them will equal the smaller factor.

So the question to understand the implications for RSA here is, how hard is it to find k for a quadratic residue q modulo p, where

k^2 =3D q mod p

if p is approximately sqrt(public key)?

That is the most direct approach to factoring a public key using those congruences.

Alternatively, if it is difficult to just use a large prime p because solving the quadratic residues modulo p is difficult, you can (as pointed out to me by Enrico) use the Chinese Remainder Theorem with smaller primes, which brings the second question:

How feasible is it with T =3D public key, to use a bunch of primes with the Chinese Remainder Theorem to find z and y with the congruence relations?

The answers to those two questions determine the fate of RSA encryption.





<< Home

This page is powered by Blogger. Isn't yours?