# How do digital certificates work, and why is it not possible to reverse engineer one from a signed file?

Digital certificates are used quite commonly these days, for signing files. They are used by various operating systems to ensure reliability and security. For example, Android requires that each of the apps submitted on the Android Market is signed with a certificate, and any updates are signed with the same certificate. This prevents anyone who hacks the account from replacing the application with their own, possible malicious one.

My question has two parts:

1. How do these certificates actually work? Is it similar to how digital signatures work?
2. Why is it impossible to reverse engineer and create the certificate from a file that has been signed with it? Would the answer change if you have both a signed and an unsigned copy of the same file? Does this vary on an algorithm to algorithm basis?

To simplify, let's say that our certificate has been generated by the key tool in the Java JDK, uses the RSA algorithm, has a key size of 2048 bits (does this matter?) and has a validity of 10000 days.

-

Such certificates are basically just an implementation of digital signatures. One certificate is used to sign the data using a private key, and a corresponding verification certificate is given to the user along with the signature and the data. The user uses the verification certificate to verify that the file matches its signature.

You can't reverse engineer the signing certificate from the verification certificate because of the cryptographic properties of public/private keys. Whatever signing algorithm they are using, the private key should be underivable from the public key. Exactly why this is difficult (or at least believed to be difficult) depends on the exact algorithm being used, but as a general rule they all have this property.

An example situation, for a made-up app store/market system:

1. Developer creates an account in a market place through the Market Owner and gives the Market Owner a copy of their public certificate.
2. Developer signs an app with their private certificate and gives the app, signature, and public certificate to Market Owner.
3. Market Owner verifies that the certificate matches the one for Developer on their records.
4. Market Owner verifies that the signature of the app is valid using the public certificate.
5. Market strips off the signature and certificate from the app.
6. Market signs the app using their own private certificate and puts the signature and public certificate in the app.
7. Anyone who downloads the app verifies that the public certificate matches their device's local copy (it may have a built-in copy of said certificate) and they verify the app's signature from the Market Owner's public certificate.

There are a lot of variations and complexities that arise. What happens when a certificate is compromised, how to you revoke it? What if the user loses his certificate? What if the Market Owner wants to use multiple certificates? What about certificate expiry dates? Etc. But that's a general model for how the this kind of system could work using certificates.

-
What are these "public certificate"s and "private certificate"s? $\:$ I would imagine using "public key"s $\hspace{0.6 in}$ and "private key"s instead, with certificates for the public keys. $\;\;$ –  Ricky Demer Jun 14 '12 at 2:10
@Ricky: It's just an (informal) vocabulary thing. "Certificate" can sometimes be a package of stuff, such as a key and it's corresponding traditional certificate. It seemed simpler to package that together as a "certificate" for the explanation, as that detail didn't seem terribly relevant. –  B-Con Jun 14 '12 at 4:46
What about the 2048 bits part? Does that matter when creating a certificate? –  Raghav Sood Jun 14 '12 at 7:40
2048 bits refers to the size of the public/private key pair. It would probably mean that RSA is being used to do the signing/verifying. –  B-Con Jun 14 '12 at 15:23
Huh, why would the market strip of the original signature instead of simply adding another one (or doing nothing, the client can check the certificate chain)? –  Paŭlo Ebermann Jun 14 '12 at 19:30
show 1 more comment

1.
These certificates are a digital signature of a message containing a signature verification key,
an identity, and whatever other information it's supposed to have, all in a specified format.
(I don't know what that format is for any standard.)

2.
Because it's not impossible (in fact it's easy), and no. $\:$ One simply finds where the standard
says the certificate should be in the signed file, and outputs that section of the input.

What is expected is that it should be difficult to get a certificate for an identity that is not one's own.

-