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!)
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.