Abstract: As a new architecture supporting general purpose computing on GPU，Compute Unified Device Architecture（CUDA） plays an important role in massive data parallel computing.RSA is a kind of computing concentrated public key cryptographic algorithm.To improve the performance of RSA algorithm，CUDA based high performance implementation is presented in this paper.The key of CUDA implementation of RSA is large amount of independent parallel Montgomery modular multiplication thread in the kernel side.The threads organization scheme and data structure of this implementation are also presented.Besides，shared memory based performance improvement method is also presented.According to the implementation method of this paper，the performance and throughput of RSA algorithm are obtained for a CUDA GPU.The experiment results show that the CUDA implementation can achieve more than 40 times speedup in comparison with general CPU implementation of RSA.

Key words: Compute Unified Device Architecture（CUDA）, RSA algorithm, Montgomery module multiplication

摘要： CUDA（Compute Unified Device Architecture）作为一种支持GPU通用计算的新型计算架构，在大规模数据并行计算方面得到了广泛的应用。RSA算法是一种计算密集型的公钥密码算法，给出了基于CUDA的RSA算法并行化高效实现技术，其关键为引入大量独立并发的Montgomery模乘线程，并给出了具体的线程组织、数据存储结构以及基于共享内存的性能优化实现技术。根据RSA算法CUDA实现方法，在某款GPU上测试了RSA算法的运算性能和吞吐率。实验结果表明，与RSA算法的通用CPU实现方式相比，CUDA实现能够实现超过40倍的性能加速。

关键词: 统一计算设备架构, RSA算法, Montgomery模乘