0x80090016 – Keyset does not exist

This blog post describes one possible cause for the “Keyset does not exist” error when trying to access/use a non-exportable private key via the Microsoft CNG or CryptoAPI.

The situation was that the certificate was installed to the user’s Current User Personal Store, but the corresponding private key was stored in the Local Machine Key Store (machine keyset).  There were additional restrictions in place at the File System level which prevented users, that are not members of the Administrators group, from accessing LM Private Keys; even when access to the keys has been granted within the MMC snap-in.

The solution is to install the private key to the Current User Protected Store.