Здравствуйте, DragonMaster, Вы писали:

DM>

DM>certificate = new X509Certificate2("cert.pfx", "password");
DM>

DM>Это сертификат, выданный мной. Публичный ключ от этого сертификата находится на принимающей стороне.

А в сертификате точно лежит ключ RSA? Может там DSA на самом деле. Или на принимающей стороне его считают как DSA.