By "symmetrical" I was thinking "interchangeable". By A and B symmetrical you're meaning x = A((B(x)) = B(A(x)) I believe
Yes, "interchangeable" is a better word. In cryptography, a "symmetric cipher" is one that uses the same key for both encryption and decryption (usually by running the algorithm backwards for decryption), and public key cryptography is decidedly not a symmetric cipher. By "symmetric", I did mean that A(B(x)) = B(A(x)).
I'd like to believe that they're doing this in php etc locally on my machine. The process you've explained looks plausible on a laptop in fast time... any idea then why it takes openssl so long to generate an ssh keypair?
Not php, which is usually run server-side. They're (probably) using cryptographic features that are new in HTML5. (Those features haven't been officially standardized yet, but that doesn't stop anyone from implementing them now.)
Specifically, under HTML5, Javascript can set up a custom
algorithm (for example, to generate RSA keys of a specified length) and then invoke its
generateKey method. The key is generated asynchronously. That is, the Javascript can start the calculation running and then go off and do other things (like, waiting for you to press a "Submit" button). Eventually, the Javascript tells the algorithm either "OK, now I need the result. I'll wait for you to finish if you haven't yet" or "Never mind, I don't need it." It may still take several seconds to generate the key pair, but you won't notice because its done in the background, in anticipation of being needed.
Looking at E and D as the things being reversed, I assume they are selecting an E that is going to make a similar magnitude D, regulated by N?
I thought of that, but can't see an easy way to do that. This is closely related to the "discrete logarithm" problem. What they could do is generate several (E,D) pairs and pick the one they like best. (Once you've got phi(N), calculating an (E,D) pair is very fast, so they can afford to generate several.)
But I can't see why they would want to. I also thought this
might be useful, but on reconsideration couldn't find a justification. The motivation for always using E=3 was that that would be convenient for "the public". When ssl was new, the private keys were all being used on powerful servers and the public keys were being handed out to browsers often running on woefully underpowered client machines. That asymmetry no longer exists.
Still, it might be "polite" to pick E small, and let D fall wherever it may. Trying to make them both small is too hard. Consider, if you're generating 2048-bit keys, phi(N) will also be nearly 2^2048. Only one one-millionth of the possible values for E will have fewer than 2028 bits, and likewise for D. Only one in a trillion pairs will have both E and D shorter than 2028 bits. That's a lot of work for not much gain.
For your example, with phi(N)=3016, the pair (E,D) that has the smallest sum is (95,127), both of which are larger than sqrt(N) and therefore each have more than half as many bits as N. That suggests that at best you're not going to be able to reduce the total time to encrypt/decrypt to less than half what you'd get with a random pair.
The pair with the smallest product is (7,431), but you wouldn't want to use that, because it gives a hint at phi(N). (The smallest product comes from factoring phi(N)+1. In this case 7*431 = 3017 = phi(N)+1. Just knowing 7 tells the bad guy that phi(N) is one less than a multiple of 7, which is way more than you want them to know.)
