Tuesday, January 08, 2008
JSH: Been here before, inertia still surprises
I still get surprised despite having had experience with mathematical proofs I discovered that were dramatic when things don't happen rapidly, but I just thought that with the factoring problem there was no way there could be a long delay, but I guess it shouldn't be a big surprise, and it's probably a good thing in terms of my security.
Like let's not kid ourselves, it's not a nice world. I have had little doubt over the years as I've thought about this route to ending the blocking of my research that mathematicians and politicians in my country were capable of killing me to protect themselves, and here we are and I'm still alive, so either they don't get it, or they're nicer than I thought!
I think they don't get it yet, which is good.
Some of you though may get it, and may appreciate beautiful and surprising mathematics, as who knew?
I didn't. I thought maybe there was a dramatic answer, but I've been looking for years and hadn't found anything, and for those factoring congruence to just pop out was like a miracle:
z^2 = y^2 + nT
you can solve for z modulo a given prime p coprime to y, z and nT with:
z = (2a)^{-1}(1 + 2a^2)k mod p
and
k^2 = (a^2+1)^{-1}(nT) mod p
where y^2 just needs to be greater than p in general, and they WILL work.
So now anyone with a little mathematical expertise and some computing power can just factor your public key by picking a p that is greater than sqrt(public key), and then the hardest part comes in if they want n=1, so they can pick 'a' and then pick 'n' and bounce around until they minimize 'n' and then they have z. And with z they can get y by resolving a quadratic residue modulo p, and all of that should be rather easily done.
Which means that someone should care, but it's still quiet. I've sent out emails to top mathematicians around the world, and not received a single reply. And the FBI hasn't shown up, neither has the NSA, nor Homeland Security.
Such a strange story here with the result that changes everything.
As we speak, nations around the world can have teams cracking information encrypted with RSA, and read it, and they will be allowed for a while for reasons that escape me, but maybe some of you know better why it is being allowed.
I'm puzzled and I wonder how long it will last.
Like let's not kid ourselves, it's not a nice world. I have had little doubt over the years as I've thought about this route to ending the blocking of my research that mathematicians and politicians in my country were capable of killing me to protect themselves, and here we are and I'm still alive, so either they don't get it, or they're nicer than I thought!
I think they don't get it yet, which is good.
Some of you though may get it, and may appreciate beautiful and surprising mathematics, as who knew?
I didn't. I thought maybe there was a dramatic answer, but I've been looking for years and hadn't found anything, and for those factoring congruence to just pop out was like a miracle:
z^2 = y^2 + nT
you can solve for z modulo a given prime p coprime to y, z and nT with:
z = (2a)^{-1}(1 + 2a^2)k mod p
and
k^2 = (a^2+1)^{-1}(nT) mod p
where y^2 just needs to be greater than p in general, and they WILL work.
So now anyone with a little mathematical expertise and some computing power can just factor your public key by picking a p that is greater than sqrt(public key), and then the hardest part comes in if they want n=1, so they can pick 'a' and then pick 'n' and bounce around until they minimize 'n' and then they have z. And with z they can get y by resolving a quadratic residue modulo p, and all of that should be rather easily done.
Which means that someone should care, but it's still quiet. I've sent out emails to top mathematicians around the world, and not received a single reply. And the FBI hasn't shown up, neither has the NSA, nor Homeland Security.
Such a strange story here with the result that changes everything.
As we speak, nations around the world can have teams cracking information encrypted with RSA, and read it, and they will be allowed for a while for reasons that escape me, but maybe some of you know better why it is being allowed.
I'm puzzled and I wonder how long it will last.