You uploaded an APK that is signed with an insecure certificate. RSA or DSA key size must be at least 2048 bits.

Uploading to Android Market
But I am getting this error.

Do I have to make my Key Size bigger?

Ok, so this appears to be some sort of thing with the way that Unity generates this keystore files - so the solution to this is to generate this on your own, not using Unity to create this key.
I believe that when you use Unity to generate this keystore file, it is set to less than 2048, and it appears that Google have just made that a minimum.

It is not hard to generate this key, just open up cmd/powershell in windows and find the following path (may vary): c:\Program Files\Java\jdk1.8.0_40\bin
in here you give the following command (replace the stuff in “”)
C:\Program Files\Java\jdk1.8.0_40\bin> .\keytool -genkey -v -keystore “princessunicorn.keystore” -alias “pau” -keyalg RSA -keysize 4096 -validity 10000

This should bring up a password dialouge - after setting your password, it is time to define stuff about the game, your location, company, name etc.

Once you have the key - just use that in the player settings

I have no idea what to do with games that is published with a below 2048 keysize? I am unsure if it is possible to change the keysize of an already generated keystore file?

Looks like you do need to, yes. How are you generating the key?
Maybe this question helps.

I just ran across this problem an hour ago. Went a bit crazy as I had uploaded an .apk just a few days ago without any error. Here is the solution that worked for me:

Open cmd, navigate to your normal .keystore location. Type:

keytool -genkey -v -keystore NAMEofFILE.keystore -alias alias_name -keyalg RSA -keysize 2048 -validity 10000

REMEMBER to replace alias_name with your valid alias name and NAMEofFILE with the name you want for your new key.

Keytool will ask for the regular information you normally give Unity when creating a key from the Build Settings Tab. At the end, if you succeeded, it will say “[Saving NAMEofFile.keystore]”.

Now go back to Unity, Build Setting Tab, Player Settings → Publishins settings, and click “Browse keystore”. Select the file you just generated using Keytool. Give it the password you set using keytool, if all went well you should see the alias_name that you replaced in the previous step. Build your .apk and upload it sucessfully to google play store!

Hope this helps!
MasterCardX

This thread suggests it’s a bug on Google side:
http://stackoverflow.com/questions/35348448/play-store-error-you-uploaded-an-apk-that-is-signed-with-an-insecure-certificat

It’s a really recent issue, I am currently trying to upload my first alpha apk, and wondering if I should go for the manual key, or wait for Google and/or Unity to fix the potential bug. Any recommendation ?

Open cmd(run as admin), goto the directory to …Java/jdk/bin(something like “C:\Program Files (x86)\Java\jdk6\bin” where the java has been installed). And enter the following code:-

keytool -genkey -v -keystore my-release-key.keystore -alias alias_name -keyalg RSA -keysize 2048 -validity 10000

Now build the apk with this keystore values… You will be able to upload the apk…

Note:- The keystore will be in the jdk folder…

Google has confirmed it is a bug.

See: This Thread