I believe RSA can only be cracked by prime factorisation with the same certainty that I believe the primes are infinite. The only scenario in which they are false is one in which I am insane.
WHAT? Why do you believe this? Rabin is known to be secure if integer factorization is hard, but the same is NOT true of RSA.
See Wikipedia on the RSA problem and in particular Breaking RSA may not be equivalent to factoring—which actually shows it’s a lot less likely than you might think that anyone is going to prove breaking RSA equivalent to integer factorization.
No cryptosystem that can be cracked given unbounded computing power can currently be “proven secure” since we’re a long way from showing that any useful problem is computationally hard. The best you can do is show that it’s hard given some assumption.
Not wishing to be rude, but what caused such incredible overconfidence that you would say
I believe RSA can only be cracked by prime factorisation with the same certainty that I believe the primes are infinite. The only scenario in which they are false is one in which I am insane.
without personally understanding a proof to that effect? I do personally understand a proof that certain Rabin-based cryptosystems are as hard as integer factorization to break, and I’m still less confident of their theoretical security than I am of the infinitude of primes.
EDITED TO ADD: I should put a massive caveat on my assertions about Rabin before anyone gets the wrong impression: the proof that the cryptosystem is as hard as factoring depend on what is known as the “random oracle model”, which is a very useful but unrealistically strong assumption about our hash functions.
The cause of my overconfidence was a combination of exaggeration, arrogance and thinking I had a proof to the effect. As I said above, I had read that the problem was easy and so when I found a ‘proof’ I assumed it to be correct.
It was, as you point out, a huge error. I will aim never to repeat it.
Fair enough, thanks for answering! If you’re interested in this stuff, the proof that integer factorization is reducible to finding square roots modulo the composite isn’t too hard to get into.
This may actually be an example of qualitative difference between maths arguments and fiscal policy arguments that the OP talked about. My error was mathematical, so once it was pointed I had no wiggle room to rationalize. If you had corrected me on a point of fiscal policy I’m not sure it would have been so easy for me to just say oops.
WHAT? Why do you believe this? Rabin is known to be secure if integer factorization is hard, but the same is NOT true of RSA.
Can I have a source for this? I was under the impression RSA was provably secure. If it is not then I will edit my previous post.
See Wikipedia on the RSA problem and in particular Breaking RSA may not be equivalent to factoring—which actually shows it’s a lot less likely than you might think that anyone is going to prove breaking RSA equivalent to integer factorization.
No cryptosystem that can be cracked given unbounded computing power can currently be “proven secure” since we’re a long way from showing that any useful problem is computationally hard. The best you can do is show that it’s hard given some assumption.
Not wishing to be rude, but what caused such incredible overconfidence that you would say
without personally understanding a proof to that effect? I do personally understand a proof that certain Rabin-based cryptosystems are as hard as integer factorization to break, and I’m still less confident of their theoretical security than I am of the infinitude of primes.
EDITED TO ADD: I should put a massive caveat on my assertions about Rabin before anyone gets the wrong impression: the proof that the cryptosystem is as hard as factoring depend on what is known as the “random oracle model”, which is a very useful but unrealistically strong assumption about our hash functions.
The cause of my overconfidence was a combination of exaggeration, arrogance and thinking I had a proof to the effect. As I said above, I had read that the problem was easy and so when I found a ‘proof’ I assumed it to be correct.
It was, as you point out, a huge error. I will aim never to repeat it.
Fair enough, thanks for answering! If you’re interested in this stuff, the proof that integer factorization is reducible to finding square roots modulo the composite isn’t too hard to get into.
Thanks for pointing it out!
This may actually be an example of qualitative difference between maths arguments and fiscal policy arguments that the OP talked about. My error was mathematical, so once it was pointed I had no wiggle room to rationalize. If you had corrected me on a point of fiscal policy I’m not sure it would have been so easy for me to just say oops.
Will you also dramatically reduce your belief in your own sanity?
If extreme overconfidence counts as insanity then yes I will.
I am strongly reminded by this whole conversation of http://www.spaceandgames.com/?p=27 & http://lesswrong.com/lw/mo/infinite_certainty/
just edit it.