Git Heroku Permission Denied Public Key (after adding public key)

I experienced something similar - the same error message, from a very similar set up (latest heroku toolbelt, have Github windows client installed)

I think it is an assumption that git makes about the name of your public key file. Github's Windows client creates github_rsa and github_rsa.pub in your $HOME/.ssh directory. If you see only these in your ~/.ssh directory, try creating a new one with the standard name (id_rsa.pub), using ssh-keygen rather than the Github client.

I was able to solve this problem by following these steps.

Create a new public key using ssh-keygen:

$ ssh-keygen -t rsaGenerating public/private rsa key pair.Enter file in which to save the key (/root/.ssh/id_rsa): Enter passphrase (empty for no passphrase): Enter same passphrase again: ...

At this point I now have id_rsa and id_rsa.pub as well as the github keys in my .ssh directory.

Then re-upload it:

$ heroku keys:add ~/.ssh/id_rsa.pubUploading ssh public key...

(from http://www.whatibroke.com/?p=284 via git push heroku master Permission denied (publickey). fatal: The remote end hung up unexpectedly)

this is how i solved my problem:

i've installed heroku toobelt and used heroku keys:removeto remove my old key for this PC, then:

1.
add C:\Program Files (x86)\Git\bin to the %PATH% as in this answer https://stackoverflow.com/a/6318188/521088
(so heroku key:add can use ssh-keygen)

2.heroku keys:add

Done!