То есть вы по незащищённому каналу передаёте шифротекст и закрытый ключ?) Но при этом боитесь передать публичный ключ?)) А зачем такое шифрование нужно,, если вы ключ рядом с шифром передаёте?
И да, RSACryptoProvider для расшифровки требует абсолютно все те же значения, что были использованы при генерации ключей.