自1978年R. L. Rivest、A. Shamir和L. Adleman提出著名的RSA公钥密码体制以来,随后的30多年里,众多学者和技术人员基于其他的数学困难问题提出了大量的公钥密码算法,如基于大整数因子分解困难问题的改进RSA算法和Rabin算法、基于有限域上离散对数困难问题的ElGamal算法、基于椭圆曲线上离散对数困难问题的密码算法等。RSA公钥密码算法的安全性基于大整数因子分解的困难性假定。随着人类计算能力的不断提高和整数分解技术的不断进步,RSA公钥密码系统所需的密钥长度越来越长,从而导致计算代价越来越高,速度越来越慢。本文在分析经典RSA公钥密码算法的基础上,提出了一种基于RSA公钥密码算法和模n的k次剩余理论的公钥密码算法,称为k次剩余子系下的RSA算法,命名为k-RSA公钥密码算法。算法的安全性基于大整数因子分解的困难性假定和离散对数困难问题。与RSA算法相比,在同样安全的前提下,k-RSA公钥密码算法通过使用较小的幂指数,来获得更快的加密、解密速度。k-RSA公钥密码算法的参数选择具有较高的灵活性,除了公钥密码算法应有的基本功能外,还可以方便的实现一些诸如分层次的密码系统、秘密分割方案、多人多部门共同签字等应用。在详细阐述k-RSA公钥密码算法及其应用的同时,本文对k-RSA公钥密码算法目前存在的问题也进行了分析,并针对其中的存储问题提供了一个折衷的解决方案。方案通过在加密步骤增加一些计算开销,有效解决了存储难题,同时还增强了系统的一些安全性。最后,本文列举了下一步可以进行的几点改进思路,包括更健壮的算法、更难破解的参数设置、计算的并行处理等,以便进一步提高k-RSA公钥密码算法的安全性和计算效率。