I am working on a system in which a web server will contain the Public
Key from an RSA Key Pair and it will be stored in a key store (in
machine keys). This key will be used to encrypt data.

A second machine that is in another location will have the public and
private key stored in a key store (also in machine keys). This key
will be used to decrypt data that was encrypted on the web server.

The problem that I am having is that if both the public and private
keys are not stored on the web server (in the key store at the time the
data is encrypted) then the second machine is unable to decrypt the
data and instead the following message is returned:

Exception Type: System.Security.Cryptography.CryptographicExceptio n
Message: Bad Data.

However, if the web server has the complete pair in it's key store,
everything works as expected.

The following scenario shows the same behavior but it can be performed
on a single machine. Can anyone explain why?

1. Generate a key pair using the RSACryptoServiceProvider
2. Persist the key pair to an xml file (using ToXMLStringMethod)
3. Persist the public key only to an xml file (also using
ToXMLStringMethod)
4. Load the Public Key only into a key store (I'm using machine keys
store)
5. Encrypt some data (using key in new key store) and record the output
6. Delete the key store created in step 4.
7. Load the Key Pair (public and private) into a key store
9. Decrypt the output created in step 5 with key found in store created
in step 7 and notice that an error message occurs:

Exception Type: System.Security.Cryptography.CryptographicExceptio n
Message: Bad Data.

Any insight would be much appreciated. Thanks!