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