RSA算法原理详解（简单易懂）

本文主要是简单高效地讲解RSA算法的基本数学原理以及加解密的步骤，算法背景以及设计到的数学证明省略。本文主要参考wikipedia和博文《非对称加密算法–RSA加密原理》。 非对称公钥加密算法可以由下列几步实现：

可见，以上加密算法的关键角色是公钥和私钥的生成，以及加解密算法的具体操作。RSA算法就是一种实现上述公钥加密的算法。

RSA算法设计到欧拉函数相关知识，下面进行一些简单定义。对于一个整数 n n n，我们用欧拉函数 φ ( n ) \varphi (n) φ(n)来表示小于 n n n并与之互质的正整数。下面给出与欧拉函数相关的2条性质（证明忽略，记住就好）：

欧拉定理为：如果 m m m与 n n n互质，则 m φ ( n ) = k n + 1 m^{\varphi(n)}=kn+1 mφ(n)=kn+1，即模 n n n余1。 等式两边同时取整数 l l l次方，并再乘上 m m m得 m l φ ( n ) + 1 = m ( k n + 1 ) l = k ′ n + m m^{l\varphi(n)+1}=m(kn+1)^l=k^{'}n+m mlφ(n)+1=m(kn+1)l=k′n+m。可见，如果 m < n m