Problemas con servicios web y cifrado

pues eso, que estoy realizando una aplicacion en c# que necesita enlazar una
base de datos local con una q esta en internet, y para hacerlo mas o menos
seguro he hecho una clase q gestiona la conexion (en plan autenticacion y
firma con el algoritmo rsa, e intercambio de clave para funcionar con el
algoritmo rijndael)y la usan tanto el servicio web como la aplicacion, el
caso es q de forma local el servicio responde bien, genera sus claves de
escandalo y manda la informacion cifrada y ejecuta las instrucciones en el
servidor sin problemas, el problema ha llegao hoy cuando to contento he ido
a probarlo en internet y al intentar intercambiar las claves para iniciar la
comunicacion cifrando con rijndael (la manda el cliente cifrada con rsa) el
servidor me lanza una excepcion cryptogtaphicexception: no se pudo adquirir
un proveedor de servicios criptograficos (csp) cryptoApi para esta
implementacion at System.SecurityRSACryptoServiceProvider

Total, que parece que no sea capaz la maquina servidora de internet de
descifrar con rsa. Utilizo claves de 1024 bits y el servidor usa IIS, pero
no se que version ni el sistema operativo que usa.

Es "solo" eso, si alguien sabe por que puede ser pos me haria un favor
mu gordo si me lo dijese. Ale, muchas gracias