В SDK найдите keytool, выполните
keytool -genkey -v -keystore my-release-key.keystore -alias alias_name -keyalg RSA -keysize 2048 -validity 10000
Это ечли вам нужен "релизный" ключ, если "дебажный" то
To fix this problem, simply delete the debug.keystore file. The default storage location for AVDs is in ~/.android/ on OS X and Linux, in C:\Documents and Settings\\.android\ on Windows XP, and in C:\Users\\.android\ on Windows Vista and Windows 7.
Больше информации -
developer.android.com/tools/publishing/app-signing.html 
