> From: [email protected] On Behalf Of PS > Sent: Tuesday, 20 July, 2010 14:40 > To: [email protected] > Subject: Public/Private Key Pair Unique?
> Let us say I have a certificate and a private key pair (C1, K1) > Now, lets say I received a Certificate, C2 on the wire. Now, > I want to know whether the pvt-key K1 corresponds to the private key of C2. > One method is encrypt a Known random number with pub-key in C2 and decrypt > with K1 and see if the number is same. But this is expensive. Apparently you mean RSA keypairs/keys (and certs), as that's the only (common?) PK algorithm that supports encryption. > I thought of another method and wanted to know if this is correct: > Do a byte-for-byte compare of the pub-key in C1 with that of C2. > If they are same, then we can assume that K1 must be the private-key of C2. > Am I correct? Considering your subject line, you're worried that someone else may have somehow gotten the same keypair as you? For RSA if the modulus (n) and public exponent (e) of two publickeys are the same, the keypairs they came from are functionally equivalent. AIUI there can sometimes(?) be multiple private exponents d that satisfy the RSA condition d*e = 1 mod phi(n) so there could be two technically different privatekeys, but they are both able to decrypt the same data. In practice d is computed by the extended Euclidean algorithm and is deterministic for given n and e. And e can be and usually is fixed. So what this comes down to is the chance that someone else chose (or worse, guessed) the same factors p,q and thus modulus n. For RSA sizes of at least 1k bits, the minimum for good practice now and it should go up to 2k within a few years at most, for this to happen just by chance -- IF both used a good random number source to choose p and q -- is roughly 10^300 against. This is effectively impossible; if everyone in the world did one (good) RSA generation every second for the life of the universe, the chance of any duplication occurring ever (much less being found and misused) is still extremely tiny. OTOH if your keypair generation didn't use a good random process, and an adversary knows or guesses what its weaknesses were, there is a better chance they can guess your privatekey -- and since your cert containing your publickey will normally get exposed during use they can probably verify their guess. This is effectively what happened with an early version of Netscape (for client keys IIRC), and openssh key generation using a mistakenly-weakened openssl in some Linux distros about a year ago. And of course if someone is able to get a copy of your privatekey, they can probably get a certificate ascribing your publickey to them. I wouldn't even call it a false certificate, since they do possess the privatekey, they just shouldn't. Even without a cert, they can decrypt data encrypted under your publickey presumably for you. As for the actual comparison, what you really need to compare is the values of n and e, although as noted e is often fixed. You can compare byte-for-byte if both keys are encoded the same way. The files created by openssl (for rsa -pubout, x509 -pubout, etc.) do use the same encoding as an X.509 cert (PublicKeyInfo as DER). Though the files by default are in PEM 'armoring', while data on wire isn't, in which case you must remove one or add the other. DER is defined so that a given value always encodes the same. Although, you might want to ignore/skip the AlgorithmIdentifier. openssl always uses the standard OID for rsaEncryption, but a crook might use a different one to cause confusion. I don't know of any other working OID(s) for the usual RSA schemes, but with the huge number of people assigning OIDs there could well be one. Even if it isn't widely implemented, or even implemented at all. If you don't have both publickeys in the same encoding, you can either convert so they are, or just extract n and e and compare those. ______________________________________________________________________ OpenSSL Project http://www.openssl.org User Support Mailing List [email protected] Automated List Manager [email protected]
