The basic thrust of my argument was that it wasn’t something he could just decide an answer to
If the question was whether prime factorisation was likely to become easy, then probably you’d be justified in saying, essentially, “you don’t get to have an opinion!”. But since RSA is only an implementation, not a pure essence of mathematics, it might be vulnerable in ways we don’t know about yet. It wouldn’t be the first time. (Of course your interlocutor might not have intended this interpretation.)
I think this is a good example of a common case, where our certainty concerning ideal objects like mathematics can blind us to the existence of uncertainty in the real world.
If someone designs an AI tomorrow and provides a proof of its friendliness, should we implement it?
This question nicely straddles the dichotomy between taxation (which has policy consequences and is somewhat subjective) and modular arithmetic (which has no policy consequences, and “can look after itself”).
To clarify, in the discussion in question I was trying to distinguish between software implementations of encryption and the underlying mathematics of those implementations. I am in doubt as to whether my colleague appreciated that distinction.
I’m slightly confused here. RSA could be viewed as an implementation, but it could also be viewed as an entirely abstract, platonic algorithm. While I agree it wouldn’t have been discovered by someone only interested in pure maths rather than applications, it is a strictly pure mathematical object, so you can write proofs about it which are just as absolute as any other.
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.
EDIT: The second paragraph is innaccurate, it can be safely treated as what I would say if I had a proof, which I thought I did until 5 minutes ago, (I never bothered to check it closely before because I thought it was knwon to be trivially true). Thanks to CipherGoth for pointing this out.
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 about weak key classes (i.e. particular classes of key that can be factorized quickly, possibly by special-purpose algorithms rather than general-purpose ones)? I’ve turned up several papers on the subject, but I don’t really have the maths to understand them, other than the take-home message that key generation is a minefield.
I don’t think key generation for RSA/Rabin is a minefield. There used to be a big list of precautions you were supposed to take, but the state of the art in factorization doesn’t care about those precautions, so just separately generate two primes of approximately the right size and multiply them together.
FWIW if you have a free choice of public key primitive, RSA should never be your choice; Rabin strictly dominates it. For most applications I’d recommend ECC of some kind.
I don’t know all the specifics which is what I meant when I said it could only be cracked by prime factorisation, rather than saying it couldn’t be cracked at all within reasonable time.
In fact, I do not know of any proof forbidding the existence of a quick algorithm for prime factorisation, although I would be surprised if this were not the case. (If I’m wrong and the impossibility has been proven then please tell me!)
If the question was whether prime factorisation was likely to become easy, then probably you’d be justified in saying, essentially, “you don’t get to have an opinion!”. But since RSA is only an implementation, not a pure essence of mathematics, it might be vulnerable in ways we don’t know about yet. It wouldn’t be the first time. (Of course your interlocutor might not have intended this interpretation.)
I think this is a good example of a common case, where our certainty concerning ideal objects like mathematics can blind us to the existence of uncertainty in the real world. If someone designs an AI tomorrow and provides a proof of its friendliness, should we implement it?
This question nicely straddles the dichotomy between taxation (which has policy consequences and is somewhat subjective) and modular arithmetic (which has no policy consequences, and “can look after itself”).
To clarify, in the discussion in question I was trying to distinguish between software implementations of encryption and the underlying mathematics of those implementations. I am in doubt as to whether my colleague appreciated that distinction.
I’m slightly confused here. RSA could be viewed as an implementation, but it could also be viewed as an entirely abstract, platonic algorithm. While I agree it wouldn’t have been discovered by someone only interested in pure maths rather than applications, it is a strictly pure mathematical object, so you can write proofs about it which are just as absolute as any other.
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.
EDIT: The second paragraph is innaccurate, it can be safely treated as what I would say if I had a proof, which I thought I did until 5 minutes ago, (I never bothered to check it closely before because I thought it was knwon to be trivially true). Thanks to CipherGoth for pointing this out.
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.
What about weak key classes (i.e. particular classes of key that can be factorized quickly, possibly by special-purpose algorithms rather than general-purpose ones)? I’ve turned up several papers on the subject, but I don’t really have the maths to understand them, other than the take-home message that key generation is a minefield.
I don’t think key generation for RSA/Rabin is a minefield. There used to be a big list of precautions you were supposed to take, but the state of the art in factorization doesn’t care about those precautions, so just separately generate two primes of approximately the right size and multiply them together.
FWIW if you have a free choice of public key primitive, RSA should never be your choice; Rabin strictly dominates it. For most applications I’d recommend ECC of some kind.
Fair point.
I don’t know all the specifics which is what I meant when I said it could only be cracked by prime factorisation, rather than saying it couldn’t be cracked at all within reasonable time.
In fact, I do not know of any proof forbidding the existence of a quick algorithm for prime factorisation, although I would be surprised if this were not the case. (If I’m wrong and the impossibility has been proven then please tell me!)
Proving that integer factorization could not be done in polynomial time would incidentally prove that P != NP.