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:


How do these certificates actually work? Is it similar to how digital signatures work?
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:


Developer creates an account in a market place through the Market Owner and gives the Market Owner a copy of their public certificate.
Developer signs an app with their private certificate and gives the app, signature, and public certificate to Market Owner.
Market Owner verifies that the certificate matches the one for Developer on their records.
Market Owner verifies that the signature of the app is valid using the public certificate.
Market strips off the signature and certificate from the app.
Market signs the app using their own private certificate and puts the signature and public certificate in the app.
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.