Just tried this, and apparently Github doesn't recognize my key... I have a master key, and three subkeys (encryption, signing and authentication).
I guess that's the way they check if you are the owner of that key.
Edit: clarified
> There was an error parsing that key. Check that the key is valid and try again.
PS: the problem was that I had multiple keys locally... but weirdly, now that I managed to upload my correct one, my commits are still seen as unsigned