RSA公钥算法研究与快速模幂运算设计

RSA public key algorithm and design of fast modular exponentiation operation

RSA公钥密码体制是一种非对称加密体系,其安全性是基于大整数因子分解在计算上是不可行的,并且利用陷门函数来构造加解密规则,使通信双方无须事先交换密钥就可建立起保密通信,是目前应用最广泛的一种公开密码体制。但大整数运算所需的计算速度和资源成为其应用的一大瓶颈,尤其是模幂运算,其计算复杂性和冗余性制约了RSA的速度,因此在研究RSA密码体制基本理论的基础上,应用著名的平方-乘算法将模幂运算转化为模乘运算,使运算过程简便快捷,同时借助强大的Matlab仿真软件深入研究RSA密码系统中的关键算法,如欧几里得及其扩展定理、素数检测和模乘运算。Matlab仿真结果表明:平方-乘算法切实可行,其他关键算法也得到了充分验证,为后续的硬件实现奠定了基础和思路。

RSA public-key cryptosystem is an asymmetric encryption system. Its security is based on factoring large numbers which is computationally infeasible and using trapdoor function to construct encryption and decryption rules, making communication established in a safe channel without previous exchange of key, so currently, RSA is the most widely used public cryptosystem. However, the speed and resources needed in large integer arithmetic computation become a major bottleneck in its application, especially modular exponentiation, whose computational complexity and redundancy greatly restrict the speed of RSA. So, this article, base on the research of the basic theory of the RSA cryptosystem, apply the famous square - multiplication algorithm, which can turn modular exponentiation into modular multiplication, making the computing process simple and quickly. Meanwhile, use Matlab simulation software to further study key algorithm in RSA cryptosystem, such as Euclidean and its extension theorem, prime number test and modular multiplication. The Matlab simulation results show that： the square-multiply algorithm is feasible, and other key algorithms have also been fully validated and laid the foundation for subsequent hardware implementation.