RSA加密算法原理

RSA简介

RSA公钥加密算法是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。

RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击，已被ISO推荐为公钥数据加密标准。

算法描述

随机选取两个大 的素数p和q，n = p×q φ(n)=(q−1)(p−1) 找到一个在 [1,φ(n)] 之间的数 e ，gcd(e,φ(n))=1; 找到e在模 φ(n) 下的数论倒数d， 即 ed≡1(modφ(n)) 假设明文是M，加密后的密文是C 加密过程

Memod n=C

解密过程

Cdmod n=M

原理

要用到的定理和公式：

欧拉定理，这里只要用到： 两素数 p,q ， n=pq ，欧拉函数 φ(n) = (p−1)(q−1) ， a 和n互素， aφ(n) = 1 (mod n) 一个素数 p ，欧拉函数φ(p) = p−1， a 和p互素， aφ(p) = 1 (mod p) 以下两个可能是都知道的吧，也很容易证明，但本人数学渣渣，还是写上万一哪天忘了。 a=b (mod c)⟹ad=bd (mod c) a=b (mod c)⟹ad=bd (mod c)

证明M经过加密解密之后可以得到M

Me mod n = C 因为 Me=C+kn 所以 C=Me−kn Cd=(Me−kn)d≡Med (mod n) 即我们要证明 Med≡M (mod n) 因为 ed=1 (mod φ(n)) 所以 ed=kφ(n)+1 Med=Mkφ(n)+1 即要证 Mkφ(n)+1≡M (mod n) 下面分两种情况： 情况一：gcd(M,n) = 1 由欧拉定理知 Mφ(n)≡1 (mod n) 进一步，得证 Mkφ(n)+1≡M (mod n)

情况二： gcd(M,n)≠1 M一定有因子p或q，不妨设 M=jq 由于M与p互素，由欧拉定理

Mp−1≡1 (mod p) 乘方后再乘上M M(p−1)(q−1)kM≡Mkφ(n)+1≡Med≡M(mod p) 由于 M=jq (jq)ed=jq+lp 则q能整除l,设 l=Lq 最后 (jq)ed=jq+Ln Med≡M (mod n)

证明完毕