I finally installed the Crypt::RSA module today. What I did was I completely did the installation in a totally-rebuilt perl environment (in RedHat 9).
Allowed CPAN to install all dependent modules all by its own. Manually installed Crypt::Primes and Crypt::Random and finally installed the RSA module. Went smoothly.

Thanks to everybody for their time...