The apk must be signed with the same certificates as the previous version

Nothing. Read the documentation: Publishing Updates on Android Market

Before uploading the updated application, be sure that you have incremented the android:versionCode and android:versionName attributes in the element of the manifest file. Also, the package name must be the same and the .apk must be signed with the same private key. If the package name and signing certificate do not match those of the existing version, Market will consider it a new application and will not offer it to users as an update.

Did you sign with the debug key by mistake?

Google Play does not allow you to publish an app signed with your debug keystore. If you try to upload such an APK, Google Play will fail with the message "You uploaded an APK that was signed in debug mode. You need to sign your APK in release mode."

However, if you try to upload an update which is signed with the debug keystore, you will not see this message; Google Play will display the message shown in the question, referring to SHA1 fingerprints.

So firstly, check whether you signed the app with your debug key by mistake.

How do I check which signing keys were used?

Gather the information from the APK

You can check which certificates the original APK and update APK were signed with by using these commands, using the Java keytool:

keytool -printcert -jarfile original.apkkeytool -printcert -jarfile update.apk

This shows you detailed information about the how an APK was signed, for example:

Owner: CN=My App, O=My Company, L=Somewhere, C=DEIssuer: CN=My App, O=My Company, L=Somewhere, C=DESerial number: 4790b086Valid from: Mon Nov 11 15:01:28 GMT 2013 until: Fri Mar 29 16:01:28 BST 2041Certificate fingerprints:  MD5:  A3:2E:67:AF:74:3A:BD:DD:A2:A9:0D:CA:6C:D4:AF:20  SHA1: A6:E7:CE:64:17:45:0F:B4:C7:FC:76:43:90:04:DC:A7:84:EF:33:E9  SHA256: FB:6C:59:9E:B4:58:E3:62:AD:81:42:...:09:FC:BC:FE:E7:40:53:C3:D8:14:4F         Signature algorithm name: SHA256withRSA         Version: 3

The important parts to note here — for each APK — are the SHA1 fingerprint value, the Owner identity value, and the Valid from/until dates.

If that keytool command doesn't work (the -jarfile option requires Java 7), you can get more basic information via the jarsigner command:

jarsigner -verify -verbose:summary -certs original.apkjarsigner -verify -verbose:summary -certs update.apk

This unfortunately does not show the SHA1 fingerprint, but does show the X.509 owner identity, along with the certificate expiry dates. For example:

sm  4642892 Thu Apr 17 10:57:44 CEST 2014 classes.dex (and 412 more)    X.509, CN=My App, O=My Company, L=Somewhere, C=DE    [certificate is valid from 11/11/13 12:12 to 29/03/41 12:12]    [CertPath not validated: Path does not chain with any of the trust anchors]

You can ignore any "CertPath not validated" message, along with warnings about certificate chains or timestamps; they're not relevant in this case.

Compare the Owner, SHA1 and Expiry values between the APKs

• If the Owner/X.509 identity value is CN=Android Debug, O=Android, C=US, then you have signed the APK with your debug key, not the original release key

• If the SHA1 fingerprint value is different between the original and update APKs, then you did not use the same signing key for both APKs

• If the Owner/X.509 identity values are different, or the certificate expiry dates differ between the two APKs, then you did not use the same signing key for both APKs

Note that even if the Owner/X.509 values are identical between the two certificates, this doesn't mean that the certificates are identical — if anything else does not match — such as the fingerprint values — then the certificates are different.

Search for the original keystore, check backups

If the two APKs have different certificate information, then you must find the original keystore, i.e. the file with the first SHA1 fingerprint value that Google Play (or keytool) told you.

Search through all the keystore files you can find on your computer, and in any backups you have, until you have the one with the correct SHA1 fingerprint:

keytool -list -keystore my-release.keystore

Just press Enter if prompted for the password — you don't necessarily have to enter it if you just want to quickly check the SHA1 value.

I can't find the original keystore anywhere

If you cannot find the original keystore, you will never be able to publish any updates to this particular app.

Android mentions this explicitly on the Signing Your Application page:

Warning: Keep your keystore and private key in a safe and secure place, and ensure that you have secure backups of them. If you publish an app to Google Play and then lose the key with which you signed your app, you will not be able to publish any updates to your app, since you must always sign all versions of your app with the same key.

After the first release of an APK, all subsequent releases must be signed with the exact same key.

Can I extract the original signing key from the original APK?

No. This is not possible. The APK only contains public information, and not your private key information.

Can I migrate to a new signing key?

No. Even if you do find the original, you can't sign an APK with key A, then sign the next update with both keys A and B, then sign the next update after that with only key B.

Signing an APK (or any JAR file) with multiple keys is technically possible, but Google Play no longer accepts APKs with multiple signatures.

Attempting to do so will result in the message "Your APK has been signed with multiple certificates. Please only sign it with one certificate and upload it again."

What can I do?

You will have to build your app with a new application ID (e.g. change from "com.example.myapp" to "com.example.myapp2") and create a brand new listing on Google Play.

Possibly you will also have to change your code so that people can install the new app even if they have the old app installed, e.g. you need to make sure that you don't have conflicting content providers.

You will lose your existing install base, reviews etc., and will have to find a way to get your existing customers to uninstall the old app and install the new version.

Again, ensure you have secure backups of the keystore and password(s) you use for this version.

Nothing - Google says it clearly that the application is identified by the keys used to sign it. Consequently if you've lost the keys, you need to create a new application.