RSA加密算法原理
阿牛哥 Lv4

RSA是经典的非对称加密算法,自从1977年诞生以来,一直是加密通信世界最重要的算法,当你在网上购物、刷卡,甚至目前浏览HTTPS网站,几乎都会用到这种算法。

RSA加密算法

RSA名字来自于它的三位发明人,数学家Rivest、Shamir和Adleman,他们的发明受到了Diffie-Hellman密钥交换算法的启发。

Rivest、Shamir和Adleman

通信的双方可以各自生成两把钥匙(公钥和私钥),在开始正式发送消息前,双方先将各自的公钥(公钥是公开的,任何人都可以知晓)告知对方。

例如,当甲要向乙发送消息时,用乙的公钥加密消息,而收到消息后,乙用自己的私钥(私钥是保密的,只有自己知道)解密。

非对称密钥加密和解密通信

知道了非对称加密的基本概念后,我们来看看RSA的加密解密过程和它数学原理。

数学基础

基本概念:

互质关系:两个正整数 pp qq 没有公约数,就称这两个数互质。比如5和18,20和21。

欧拉函数 φ(n)\varphi ( n ) 与正整数 nn 构成互质关系且小于n数字的个数。比如5的欧拉函数 φ(5)=4\varphi ( 5 ) = 4 ,1、2、3、4和5都构成互质关系; φ(2)=1\varphi ( 2 ) = 1 ,1和2互质; φ(10)=4\varphi ( 10 ) = 4 ,1、3、7、9和10构成互质关系。

欧拉函数有个性质,如果 n=p×qn = p \times q ,那么 φ(n)=φ(p)×φ(q)\varphi ( n ) = \varphi ( p ) \times \varphi ( q ) 。比如 φ(10)=φ(5)×φ(2)=4×1=4\varphi ( 10 ) = \varphi ( 5 ) \times \varphi ( 2 ) = 4 \times 1 = 4

模反元素:如果 aa nn 互质,那么必定存在 bb ,使得 a×b=k×n+1a \times b = k \times n + 1 ,即: (a×b) mod n=1( a \times b ) \ mod \ n = 1 。此时,bb 就是 aa 的模反元素。比如a = 5,n = 11,那么5的模反元素就是9, 因为 5×9=4×11+15 \times 9 = 4 \times 11 + 1

两个公式:

  1. 公式一:对于互质的两个数字 aa nn ,有如下关系:

aφ(n)1 (mod n)a ^{\varphi(n)} \equiv 1 \ (mod \ n)

  1. 公式二:假设 aa pp 均为质数,则存在 0<x<p0 < x < p 0<y<p0 < y < p , 使得:

(ax mod p)y mod p=ax×y mod p(a ^{x} \ mod \ p)^{y} \ mod \ p = a^{x \times y} \ mod \ p

RSA算法的计算过程

  1. 随机选出两个足够大的质数 pp qq

  2. 计算 pp qq 的乘积 nn n=p×qn = p \times q

  3. 计算 nn 的欧拉函数 φ(n)=φ(p×q)=φ(p)×φ(q)=(p1)×(q1)\varphi ( n ) = \varphi ( p \times q ) = \varphi ( p ) \times \varphi ( q ) = ( p - 1 ) \times ( q - 1 )

  4. 选择一个与 φ(n)\varphi ( n ) 互质的整数 ee ,且 1<e<φ(n)1 < e < \varphi ( n )

  5. 计算 ee 对于 φ(n)\varphi ( n ) 的模反元素 dd ,使得 (d×e) mod φ(n)=1( d \times e ) \ mod \ \varphi (n) = 1

经过以上步骤,得出公钥为 (e, n),私钥为 (d, n)。使用e和n加密的消息,可以用d和n解密。举个例子,比如消息是M,那么加密和解密过程为:

  • 加密: Memod n=CM ^{e} mod \ n = C

  • 解密: Cdmod n=MC ^{d} mod \ n = M

反之,如果C是明文,那么加密结果就是M。

所以公钥加密后的密文只能用私钥解密;而私钥加密后的密文只能用公钥解密。

RSA算法的简单证明

要证明M加密后得到的C能再次解密得到M,就是要证明:

M=(Memod n)dmod nM = (M ^{e} mod \ n ) ^{d} mod \ n

根据前文公式二可知:(Memod n)d mod n=Medmod n(M^e mod \ n)^d \ mod \ n= M^{ed} mod \ n ,于是上式简化为:

M=Me×d mod nM = M ^{e \times d} \ mod \ n

因为 dd ee 的模反元素,也就有 k×φ(n)+1=e×dk \times \varphi ( n ) + 1 = e \times d

M=Mk×φ(n)+1 mod nM = M ^{k \times \varphi ( n ) + 1} \ mod \ n

M=(Mk×φ(n)×M) mod nM = ( M ^{k \times \varphi ( n ) } \times M ) \ mod \ n

因为 n=p×qn = p \times q ,显然 nn 只能被 11 pp qq nn 整除。在加密的时候,对信息尽量切分,使得 MM 足够小,那么 MkM ^ {k} 就远小于 nn ,同时 MkM ^ {k} 会和 nn 互质。根据前文公式一:如果 aa nn 互质,那么 aφ(n)1 (mod n)a ^{\varphi(n)} \equiv 1 \ (mod \ n) 。也就是:

(Mk)φ(n) mod n=1(M ^{k})^{\varphi(n)} \ mod \ n= 1

因为 nn 是一个很大的数,而 MkM ^{k} 远小于 nn ,所以上式等价于:

(Mk)φ(n)=1(M ^{k}) ^{\varphi(n)} = 1

于是 M=(Mk×φ(n)×M) mod nM = (M ^ {k \times \varphi(n)} \times M) \ mod \ n 得到证明。