RSA是一种非对称加密算法，其理论基础是模运算和欧拉定理。许多地方介绍RSA算法时，都比较详细地说明了RSA算法的基本步步骤即：

随机生成两个质数p，q，计算得到n=pq；
选择加密因子e，使gcd(e,φ(n))=1，同时根据ed≡1(mod φ(n))求出d，数对(e,n)为公钥，数对(d,n)为私钥；
加密公式为c=m^e(mod n)，解密公式为m=c^d(mod n)。

显然，当e很大时，只知道e、n和c直接求m需要开e次方，很困难。但为什么拿密文再计算d次方就得到明文，也就是解密公式m=c^d(mod n)为什么成立大多数资料都没有给出证明而是举例说明。这里需要一个解释，并且还不是一句“根据欧拉定理可以得到”就能敷衍的。

实际上，需要证明的是(m^e)^d≡m(mod n)。根据模运算的性质，(m^e)^d≡m^ed(mod n)很好理解，但下一步不能把ed≡1代入，因为ed≡1是基于模φ(n)的，模n的情况下ed就不一定为1了。当然，ed≢1也可以证明m^ed(mod n)≡m。

∵ed≡1(mod φ(n))
∴ed=hφ(n)+1

如果m与n互质，根据欧拉定理有m^φ(n)≡1(mod n)，那么 m^ed≡m^hφ(n)+1≡(m^φ(n))^h∙m≡1^h∙m≡m(mod n)命题成立。

如果m与n不是互质的，由于n是两个质数p和q的积，那么p

m或q

m，不妨设p

m，即m=kp，这时,k与q必然互质，根据费马小定理（其实就是欧拉定理的特例）有(kp)^q-1≡1(mod q)。进而有

[(kp)^q-1]^h(p-1)∙kp≡kp(mod q)，即

(kp)^{h(p-1)(q-1)+1}=(kp)^hφ(n)+1≡kp(mod q)也就是

(kp)^ed≡kp(mod q)可得到(kp)^ed=tq+kp，这个等于左边含有因子p，右边kp也含有p，所以tq也必須含有p作为因子，即t必然能够被p整除，设t=t^’p就得到(kp)^ed=t^’pq+kp，则pq=n所以在模n情况下(kp)^ed≡kp，即m^ed≡m(mod n)命题得证。

已知p、q、e求d

算法第二个步骤是已知p、q、e求d。亦即模φ(n)的乘法逆元问题。根据ed≡1(mod φ(n))可得ed=1+kφ(n)，即找整数d、k使等式ed-kφ(n)=1成立。普通的欧几里德算法（辗转相除法）在计算gcd(e,φ(n))的过程中商被丢弃了，如果保存下来就可以得到d、k。当然也可以求φ(φ(n))，然后根据欧拉定理求e^φ(φ(n))-1即可，虽然φ(n)=(p-1)(q-1)但是p-1、q-1已经不是素数了，所以还是要进行因式分解，然后还要乘方，更麻烦一点。当然，也可以尝试1+kφ(n)能不能被e整除（其中k=1,2,……）一般k都不会太大的。