Correct me if I'm wrong on any of this.
My pleasure.
I just had the
intense disgust of entering a fairly large post, and while I was checking my facts in another safari window, safari spontaneously
reloaded my about-to-click-post window (which was BEHIND the frontmost window I was using), causing it to wipe my entire text. Nothing quite so annoying as watching a different window of your browser decide to go rogue. I don''t know how much of that I want to try to type up again but I'll give it a shot. Normally I copy a post in progress frequently in case of a browser crash etc, but I was copying a formula at the time...
*big sigh*
First thing I want to address is asymmetry. The public and private keys are NOT interchangeable. Here are two links you need to watch. The first one is better for the casual reader and gives an easier to follow example, but uses the same exponent for encrypt and decrypt which is downright confusing, and fails to describe the computation of D. The second one is a lot drier, but is complete.
http://www.youtube.com/watch?v=M7kEpw1tn50http://www.youtube.com/watch?v=Jt5EDBOcZ44(oh and btw, in safari as of this instant,
every single tab I have open reloads its page when I switch to that tab....
good grief... heck of a safari bug there)
Sorry but you will have to have that second one fresh on your mind for the following. I summarize his example:
P = 53 (prime 1, selected at random)
Q = 59 (prime 2, selected at random)
N = P*Q = 3127 (public key 'large component')
phi(E) = (P-1)(Q-1) = 3016 (this is merely used as a safety limit, E must be chosen LESS than this)
E = 3 (integer less than N, selected at random, not a factor of N (meaning not P or Q), less than phi(E)
Public key is (N,E)
this, combined with an address, would also be considered a public certificate, useful for encrypting and verifying signatures only
D = (2 phi(E) + 1 / E = 2011 (this is the secret part of your private key)
private key is (D,E) but is often referred to simply as D. E is however required for decrypting and signing
(N,E,D) is a private certificate, capable of encrypting, decrypting, signing, and verifying signatures, among other things)
(N,E) can be extracted at any time from (N,E,D), thus a public cert can be extracted from a private one.
When a CA sends you your private (N,E,D) key, they sign it, but only the (N,E) part, since you won't be revealing your D to anyone else.
note! D and N are
not interchangeable because D may be prime. (and in this example, I think NOT by coincidence, 2011
is prime) If N is prime, it has no factors P and Q with which to generate the complementary D. This key pair is
not symmetrical.
M = 89 (plaintext example message)
C = M^E mod N = 89^3 mod 3127 = 1394 (the encrypted message)
M = C^D mod N = 1394^2011 mod 3127 = 89 (the decrypted message, my calculator can't do that one)
That last one is the doozy that keeps the message safe. C may not be too big, but D is pretty good size, making C^D downright massive, even by modern computer standards, when D is 2048 bit for example.
And yes, due to the intense math in this process, it's only used to securely exchange a randomly generated symmetrical key (that is much faster to use) that is used to encipher the actual message.
(I wanted to see if the example D and N could be swapped and still continue to function, but I don't have any way to deal with numbers of that size)
Now that we have that cleared up, on to the "who has the private key" question.
When you request a cert from comodo etc, you just give them your email address, and not much else. THEY generate a P and a Q, calculate the N, calculate the phi(E), generate an E restricted to phi(E), and calculate the D. The N, D, and E are then wrapped up in a cert. They add in your email address and name etc, and sign all of it (except the D) fire off an email to you with a link for you to click, and then when you click that, it downloads the (N,D,E) private cert to your computer.
This is the ONLY thing on your computer with regard to this keypair. There is only the one cert, that is a full (N,E,D). (there's probably a name for that, I don't know what it is) When you email someone, or want to publish it, you are stripping out the D because you can't let anyone else see that.
anyone with that cert can look like you can decrypt messages encrypted with the (N,E) public cert made from it, and can sign something that your (N,E) will verify as authentic. There is nothing else on your computer that matters. Only what they send you in the form of that certificate. They go to the lengths of forcing you to use a link they emailed you to make sure nobody else gets ahold of it. If it wasn't the part that you were supposed to keep secure, they wouldn't need to do that. And since you can click that link a week from now and get it again, they're obviously keeping ahold of it.
Also of note, it's probably difficult for you to figure out the (P,Q) they selected for you, given only your cert. They have no actual reason to tell you what your P or Q are.
The other certificates on your computer, the anchors from places like verisign, are only (N,E) certs, and are good for encrypting and verifying only. When you send an email and sign it, your (N,E) is attached in addition to the signature, and the receiver can verify the cert because that part of it was signed by verisign, for which they have the public (N,E) cert as one of their anchors or within their chain of trust.
You can roll up your own key using openssl. I found several places online that show how. But it won't be signed by any authority, and will probably not be imported to your keychain automatically. At least not as trusted. I don't think comodo etc will let you send your public key to them to sign. That being the case, if you want the cert in your email to be trusted and used automatically, you have to let them roll it up for you, and that means they have your D. And the government that controls them can have it at any time too, without your knowledge. OR if they have a security breach,
anyone might end up with it.
If they were inclined to do it the "safe" way for you, here's how the process would have to work:
you run something on your own computer to generate P,Q. From there you also calculate N, phi(e), E, and D. You then send them your email address, as well as (N,E). You do NOT send them D, and certainly not P or Q. They sign that and send it back via email or whatnot. You assemble a (N,E,D) cert and tack on their signature, which will validate your email with N and E. Done. They don't have your D, and you have a signed cert that your email program can use to sign and extract/insert your (N,E) cert into.
But that's not how any of them do it. I could be tinfoil-hatty about it, but this is just people doing their jobs, and should be expected. And this is why I originally was asking how to roll my own cert. I can live without it auto-importing as trusted into others' keychains. I'd just like to know I'm
really the only one in the world that can read my mail, when I so choose to.
If the above is actually occurring on my computer when I request a cert, then ok it's safe. Considering some of the oddness that goes on when getting one of these certs, it wouldn't terribly surprise me if clicking the request cert form caused my computer to do the above local work and merely send them my email, N, and E, and then stash my D somewhere in a cookie or something. And then somehow be able to access it again when I click the email link, to assemble the single cert that has N, E, D, my email, and their sign all in it. But I'd have to have that explained to me to believe it's all happening that way. I've rolled up many an SSH keypair and it always takes openssl awhile to do it, and I've never seen that delay in my browser when I click to request the cert. I
do recall at least one of them telling me I had to do the retrieval on the same computer, using the same browser, so that raises my hopes a tad bit. "Pictures, or it didn't happen."
I have explained the process in greater detail rather than try to address your individual concerns one at a time. If you feel any of them have survived the above, speaketh
bonus addition after I re-read it... I think the reason they said that E must not be a factor of N is that I suspect for ease of P,Q generation, they select them from a (large) table of known primes, and then multiply them by another pair of randomly selected primes in their table, or perhaps a large fairly prime number. To make a P and Q that aren't "very" prime, but are close to it, to increase the size of N without having to try to find a large P and Q to work with. Then, E would need to be checked to make sure it's not a factor of N, (not P and not Q) because it may be a factor without being P or Q. interesting...
LAST edit. wolframalpha to the rescue! first make sure it can hack the normal N and D:
89^3 mod 3127 = 1394
1394^2011 mod 3127 = 89 booya, it works.
swapping N and D:
89^3 mod 2011 = 1119
1119^3127 mod 2011 = 146 bzzzzt, doesn't work! process is
not symmetrical.