After a bit more digging I found better information on this process:
http://wiki.cacert.org/EmailCertificates(this may apply more to email and web servers, ssl certs, rather than strictly private email certs, but the process should be fundamentally the same)
The key to keeping your private key safe is to extract a "Certificate Signing Request" (CSR) and send
that to the CA. It's your full cert with the D removed, ready to be signed. They verify your identity (however they do it) then sign it and return it to you to have your D merged back in. So the D never leaves your computer, they never see it. (and most certainly aren't the ones
generating it)
The core question remains, in the above process with comodo etc, is the php or whatnot running on your machine
really generating (Q,P), rolling up the other stuff to make a CSR, sending that, and then stashing it somewhere locally to be reassembled when you click the link they email you? (Or is it generating those things for you and just sending you back a full (N,E,D) certificate with your secrets already in it?)
It might be. But I still would expect a substantially longer delay in the process, as generating a suitable (Q,P) is usually a lengthy process on a home computer, taking at
least several seconds here. Generating a DES public key pair for ssh takes between 3 and 15 seconds when I roll one up, depending on the machine, and those are fewer bits iirc.
