I was getting this error while attempting to encrypt with an RSA instance created by the RSA.Create function too. My problem ended up being that my public key was exported from an RSACryptoServiceProvider; when I made sure the two RSA instances were both RSACryptoServiceProviders, the error cleared up. You can try either checking the source of your PEM key, or switching from RSA.Create to instantiating a new instance of a derived RSA class and seeing if that works?