深入理解RSA算法

本文结构：

假设alice想要通过rsa算法在公网上，将消息加密传递给bob，他们应该怎么做呢？分为以下几个步骤：1.bob生成一堆共私钥，将公钥在网上公开，私钥自己保存2.alice通过bob的公钥加密明文消息m，得到密文c，并将密文c传递给bob3.bob用自己的私钥解密密文c，得到明文m

特别的当n为质数时：a^(n-1)≡1modn

（ab-1被n整除，或者说ab被n除的余数是1）这时，b就叫做a的模反元素。

假设alice要向bob发送明文信息m，则用bob的公钥(n,e)对m进行加密。并且加密时必须将明文进行比特串分组，保证每个分组对应的十进制数小于n，即保证m<n。

这里m假设是65，那么可以算出下面的等式：65^17≡2790(mod3233)于是，c等于2790，alice就把2790发给了bob。

bob拿到2790以后，就用自己的私钥(n=3233,d=2753)进行解密。

现在c等于2790，私钥是(3233,2753)，那么bob算出2790^2753≡65(mod3233)因此bob知道了alice加密前的原文就是65。

对于密文的解密运算为：

现在来证明上面的公式恒成立。将c≡m^e(modn)代入右边，可得

又由于ed≡1(modφ(n))可知必有ed=kφ(n)+1，故有

下面分两种情况证明m^(kφ(n)+1)(modn)=m：1）明文m与n互质。那么由欧拉定理知

2）明文m与n不互质：m与n不互质，说明m与n有公因子。又因为n=pq，且p和q都为质数，所以n的因子只有p,q，那么m与n的公因子只能是p或者q。所以m为p或q的倍数。假设m=tp,(t为一正整数),且t与q互质（若t与q不互质，假设t=kq，则m=tp=kpq=kn，违反了m<n）因为m=tp与q互质，由欧拉定理知

两边同时取kφ(p)次方，得

m≡c^d(modn)得证。

回顾上面的密钥生成步骤，一共出现六个数字：

公钥用到了两个（n和e），私钥用到了两个（n和d）。那么有无可能在已知n和e的情况下，推导出d？

结论：如果n可以被因数分解，d就可以算出，也就意味着私钥被破解但是大整数的因数分解是非常困难的，n越大，算法约安全，目前推荐用的rsa秘钥长度为2018及上。

同秘钥RSA有乘法同态。简单来说：

原理：

同价加密的一些相关知识：https://yeasy.gitbooks.io/blockchain_guide/content/crypto/homoencryption.html