OSX restricts the size of the keys that can be imported into the KeyChain app and instead of telling you what exactly the problem is it throws error codes back.

Thankfully, Tom Cramer found the solution in the Apple Support forums, https://discussions.apple.com/thread/2668985 still I’m posting this as a reminder to myself.

Paste this into your terminal and change the key size accordingly if you have even bigger keys than me:

defaults write /Library/Preferences/com.apple.crypto RSAMaxKeySize -int 16384

Now restart the KeyChain App using Cmd+Q. After re-opening KeyChain your key should be accepted and be ready to be verified against.