Столкнулся з розкодированием с помощю RSACryptoServiceProvider RSAшки созданой на CryptoAPI.
Очень помогла следующая статься — http://blogs.msdn.com/shawnfa/archive/2005/12/05/500144.aspx
Кстати, на сегодняшний день, максимальный масив байт который может закодировать RSACryptoServiceProvider — 117. И разкодировать тоже может . У меня Framework 3.5 SP1.