= 27d567bc2d48d9f40e9ccc20ea370b15)
jfm comments on Bullying the Integers - Less Wrong Discussion
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (33)
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 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.