Brute Force is the only way!
Here is a script that helped me out:
https://code.google.com/p/android-keystore-password-recover/wiki/HowTo
Using a list of 5-10 possible words from memory, it recovered my password in <1 sec.
I want to refine this a little bit because down-votes indicate to me that people don't understand that these suggestions are like "last hope" approach for someone who got into the state described in the question.
Check your console input history and/or ant scripts you have been using if you have them. Keep in mind that the console history will not be saved if you were promoted for password but if you entered it within for example signing command you can find it.
You mentioned you have a zip with a password in which your certificate file is stored, you could try just brute force opening that with many tools available. People will say "Yea but what if you used strong password, you should bla,bla,bla..." Unfortunately in that case tough-luck. But people are people and they sometimes use simple passwords. For you any tool that can provide dictionary attacks in which you can enter your own words and set them to some passwords you suspect might help you. Also if password is short enough with today CPUs even regular brute force guessing might work since your zip file does not have any limitation on number of guesses so you will not get blocked as if you tried to brute force some account on a website.
As everyone has said, you definitely need the key. There's no workaround for that. However, you might be surprised at how good the data recovery software can be, and how long the key may linger on your systems -- it's a tiny, tiny file, after all, and may not yet be overwritten. I was pleasantly surprised on both counts.
I develop on an OSX machine. I unintentionally deleted my app key around 6 weeks ago. When I tried to update, I realized my schoolboy error. I tried all the recovery tools I could find for OSX, but none could find the file -- not because it wasn't there, but because these tools are optimized to find the sorts of files the majority of users want back (photos, Word docs, etc.). They're definitely not looking for a 1KB file with an unusual file signature.
Now this next part is going to sound like a plug, but it isn't -- I don't have any connection to the developers:
The only recover tool I found that worked was one called Data Rescue by Prosoft Engineering (which I believe works for other files systems as well -- not just HFS+). It worked because it has a feature which allows you to train it to look for any file type -- even an Android key. You give it several examples. (I generated a few keys, filling in the data fields in as like manner as possible to the original). You then tell it to "deep search". If you're lucky, you'll get your key back in the "custom files" section.
For me, it was a life saver.
It's $100 to purchase, so it's not cheap, but it's worth it if you've got a mass of users and no further means of feeding them updates.
I believe they allow you 1 free file recovery in demo mode, but, unfortunately, in my case, I had several keys and could not tell which one was the one I needed without recovering them all (file names are not preserved on HFS+).
Try it first in demo mode, you may get lucky and be able to recover the key without paying anything.
May this message help someone. It's a sickening feeling, I know, but there may be relief.
No, there is no chance to do that. You just learned how important a backup can be.
If you lost a keystore file, don't create/update the new one with another set of value. First do the thorough search. Because it will overwrite the old one, so it will not match to your previous apk.
If you use eclipse most probably it will store in default path. For MAC (eclipse) it will be in your elispse installation path something like:
/Applications/eclipse/Eclipse.app/Contents/MacOS/
then your keystore file without any extension. You need root privilege to access this path (file).
Source: Stackoverflow.com