Thursday, May 25, 2017

Do you really need quantum mechanics to solve RSA?

Suppose for example you could calculate the square root of an arbitrary number modulo the product of two primes. What would the implications be?

There is an algorithm to compute the square root modulo a prime number.  Daniel Shanks was a brilliant mathematician who came up with really interesting equations...

One of them being Shanks-Tonelli.  Or Tonelli-Shanks... ;-)

So who the really cares.  Well, in some circles, Daniel Shank's work is considered very important...  I leave it to the reader to determine that.

Here is some math.

Suppose you need to calculate the square root of 18 mod 23.

How would you do this?  You need to find a such that a^2 == 18 mod 23

Take a minute to work that out.

The answer is of course 15.  or 8 since 8 + 15 == 23 or 0 mod 23

But what if you could compute a square root modulo the product of two primes?

Lets take 17 x 23 = 391

Now, you need to calculate the square root of 179 modulo 391...

Pretty easy since 391 is small.  Check this out

http://www.numbertheory.org/php/squareroot.html

So who cares?

Well... the square root is 54 or 337
or maybe 31 or 360

Ah Ha....  so 54^2 == 179 modulo 391
So does 31^2 == 179 modulo 391

HOLY SHIT, maybe lol

so wtf if you take gcd(54 -31,391)  ???

suddenly you see that 54-31 == 23 which is a factor of 391.

Well that sucks right?

Cause your RSA  crypto depends on people not knowing the factors...  And your crypto probably depends on the human spirit giving up and not trying to solve this equation...

I hope you didn't choose a weak prime.  Such that square roots can be computed by a^(p+1)/4...

If you think that RSA has not been solved...  Well, it probably has been (Pure speculation lol)  But some agencies hire the best and brightest Mathematical minds)  Check out this for reading (https://www.amazon.com/Delusions-Intelligence-Enigma-Secure-Ciphers/dp/0521736625)

Ok so if a generalized version of Shanks-Tonelli is known... Then RSA and other crypto systems fall...

Thats all for now.




Heavily influence by "The Truth" IPA

Cheers

Casey
@subTee