I started implementing an RSA2 encrypt / decrypt routine because I thought it would do what I need. Essentially a way to control the encryption and decryption in a way that is NOT machine specific, or using THE REGISTRY OR MACHINE STORE.
I really thought the .net libraries in RSA2 allow you to encrypt decrypt based on a private / public key combination. Am I mistaken? Do you still need to use the registry or machine store for RSA2 to work?
My experience is in C++, but the CryptoAPI library called underneath by both languages is the same so my advice should still work. It's just syntactical sugar that's different between the two.
First, you don't have to use the machine certificate store or the registry. You don't need a store at all. You just need to acquire a crypto context that includes the Microsoft Enhanced Provider, and uses the RSA Full provider.
You need a key pair. You can create a PRIVATEKEYBLOB structure yourself, if you want, but when I was playing with the library, I found it pretty easy to use the CryptoAPI to generate a key with CryptGenKey (make sure it's exportable) which I then exported using CryptExportKey using the PRIVATEKEYBLOB format, which will include the private and public keys. Now you have a formatted blob of memory that contains an RSA key pair. You can mess with this all you want.
Anyway, once you have stuck your key pair into a formatted PRIVATEKEYBLOB, you use CryptImportKey to import it back into the provider. After this, the provider is ready to encrypt and decrypt.
Now, call CryptEncrypt() and pass it the data you want encrypted. It'll use the public key to encrypt it. Pass the results back in to CryptDecrypt() and it'll decrypt it with the private key.
Everything you want to know about why you are failing at encryption can be learned by watching this video of a talk some security researchers gave about your specific issue. http://www.viddler.com/explore/rentzsch/videos/31