CSPで暗号化する場合、非対称秘密キーをローカルなんかに平文で保存しないでください。

[方法：キーコンテナに非対称キーを格納する]
http://msdn.microsoft.com/ja-jp/library/tswxhw92.aspx

非対称秘密キーは、ローカルコンピュータにそのまま平文として保存しないでください。
秘密キーを格納する必要がある場合は、キーコンテナを使用することをお勧めします。
キーコンテナの詳細については、プラットフォーム SDK ドキュメント
(http://www.microsoft.com/japan/msdn) の「CryptoAPI」セクションを参照してください。

.NET(C#またはVB.NET)でRSA暗号化を行う場合、
素因数分解の原理を用いてゼロからゴリゴリ実装するゼ！というマゾはまずいないと思います。
通常、暗号サービスプロバイダ(CSP : Cryptographic Service Provider)によって提供された
RSA暗号化アルゴリズムを使用するRSACryptoServiceProviderクラスを使うのが一般的でしょう。

CSPによって提供される暗号化の処理というのは、なんらかの暗号化エンジン*1に鍵の種と暗号化されるデータを渡し、
その結果を受け取ることを言います。このときCSP内部の鍵が格納される場所をキーコンテナといいます。
このキーコンテナに格納された非対称秘密キーは、明示的に削除しない限り、安全に保存され続けます。
ですから、アプリケーションが終了したとしても、再び同じ秘密キーを利用することができます。
もちろんマシンを再起動したとしても、キーコンテナに格納された秘密キーを再び得ることができます。

というわけで、セキュリティ的な意味で、暗号の非対称秘密キーを保存しておく必要があるような場合は、
キーコンテナを利用してください。お願いします。

非対称秘密キーをキーコンテナに保存するサンプル

RSACryptoServiceProviderクラスでキーコンテナを利用したサンプルです。
WindowsXp以降のバージョンか否か判断することで、OAEPパディングの利用有無を自動的に判断しています。

using System;
using System.Collections.Generic;
using System.Text;
using System.Security.Cryptography;

namespace ConsoleApplication1
{
    public static partial class Utility
    {
        /// <summary>
        /// RSA暗号の公開鍵と秘密鍵を生成します
        /// </summary>
        /// <param name="keyContainerName">キーコンテナ名</param>
        /// <returns></returns>
        public static KeyValuePair<string, string> CreateKeysOfRSA(string keyContainerName)
        {
            var cspp = new CspParameters();
            cspp.KeyContainerName = keyContainerName;
            var rsa = new RSACryptoServiceProvider(cspp);
            return new KeyValuePair<string, string>(rsa.ToXmlString(false), rsa.ToXmlString(true));
        }

        /// <summary>
        /// 公開鍵を使って文字列をRSA暗号化します
        /// </summary>
        /// <param name="str">暗号化する文字列</param>
        /// <param name="publicKey">暗号化に使用する公開鍵(XML形式)</param>
        /// <returns>暗号化された文字列</returns>
        public static string EncryptOfRSA(string source, string publicKey)
        {
            var rsa = new RSACryptoServiceProvider();
            rsa.FromXmlString(publicKey);

            byte[] data = Encoding.UTF8.GetBytes(source);
            //暗号化（Windows XP以降の場合のみ2項目にtrueを指定してOAEPパディングが使える）
            byte[] encryptedData = rsa.Encrypt(data, IsXpOrMore());

            return System.Convert.ToBase64String(encryptedData);
        }

        /// <summary>
        /// 秘密鍵を使って文字列をRSA復号化します
        /// </summary>
        /// <param name="str">Encryptメソッドにより暗号化された文字列</param>
        /// <param name="privateKey">復号化に必要な秘密鍵(XML形式)</param>
        /// <returns>復号化された文字列</returns>
        public static string DecryptOfRSA(string str, string privateKey)
        {
            var rsa = new RSACryptoServiceProvider();
            rsa.FromXmlString(privateKey);

            byte[] data = System.Convert.FromBase64String(str);
            //復号化
            byte[] decryptedData = rsa.Decrypt(data, IsXpOrMore());

            return System.Text.Encoding.UTF8.GetString(decryptedData);
        }

        /// <summary>
        /// キーコンテナからRSA暗号キーを削除します。
        /// </summary>
        /// <param name="keyContainerName"></param>
        public static void DeleteKeyFromContainerOfRSA(string keyContainerName)
        {
            CspParameters cp = new CspParameters();
            cp.KeyContainerName = keyContainerName;
            var rsa = new RSACryptoServiceProvider(cp);
            rsa.PersistKeyInCsp = false;
            rsa.Clear();
        }

        /// <summary>
        /// WindowsXp以降のバージョンか否かを取得します。
        /// </summary>
        /// <returns></returns>
        public static bool IsXpOrMore()
        {
            OperatingSystem osInfo = Environment.OSVersion;
            switch (osInfo.Platform)
            {
                case PlatformID.Win32Windows:  // Windows 9x系
                    return false;
                case PlatformID.Win32NT:  // Windows NT系
                    if (osInfo.Version.Major == 4) return false;//Windows NT 4.0
                    if (osInfo.Version.Minor <= 0) return false; //Windows2000
                    return true;
                default: return true;
            }
        }
    }
}

お試し

using System;

namespace ConsoleApplication1
{
    static class Program
    {
        static void Main()
        {
            var keyContainerName = "キーコンテナの名前です。なんでもいいです。";

            for (var i = 0; i < 4; i++)
            {
                var keys = Utility.CreateKeysOfRSA(keyContainerName);
                Console.WriteLine("{0}:{1}", keys.Key, keys.Value);
                Console.WriteLine();

                Console.WriteLine("暗号化");
                var enc = Utility.EncryptOfRSA("あいうえお", keys.Key);
                Console.WriteLine(enc);
                Console.WriteLine();
                Console.WriteLine("復号化");
                var dec = Utility.DecryptOfRSA(enc, keys.Value);
                Console.WriteLine(dec);
            }
            //Utility.DeleteKeyFromContainerOfRSA(keyContainerName);
            Console.ReadKey();
        }
    }
}

コメントアウトしている

Utility.DeleteKeyFromContainerOfRSA(keyContainerName);

を有効にするとキーコンテナが削除されることとなり、
毎回新たな秘密キーがキーコンテナに格納されます。

*1:ブラックボックス化された何か