RSA加密算法简介-工具盒子

概述 {#概述}

RSA加密算法是一种非对称加密算法，在公开密钥加密和电子商业中被广泛使用。RSA是由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）在1977年一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

前置知识 {#前置知识}

欧拉函数 {#欧拉函数}

在数论中，对正整数 n ，欧拉函数 $φ ( n ) \displaystyle \varphi (n)$ φ ( n ) 是小于等于 $n \displaystyle n$ n 的正整数中与 $n \displaystyle n$ n 互质的数的数目。例如 $φ ( 8 ) = 4 \displaystyle \varphi \left(8\right)=4$ φ ( 8 ) = 4 ，因为1、3、5和7均与8互质。

欧拉函数是积性函数，即是说若 $m , n \displaystyle m,n$ m , n 互质，则：

φ ( m n ) = φ ( m ) φ ( n ) \\displaystyle \\varphi (mn)=\\varphi (m)\\varphi (n)

φ ( mn ) = φ ( m ) φ ( n )

使用中国剩余定理有较简略的证明：设 $A , B , C \displaystyle A,B,C$ A , B , C 是跟 $m , n , m n \displaystyle m,n ,mn$ m , n , mn 互质的数的集，据中国剩余定理， $A × B \displaystyle A\times B$ A × B 和 $C \displaystyle C$ C 可建立双射（一一对应）关系，因此两者元素个数相等。

欧拉定理 {#欧拉定理}

在数论中，欧拉定理（也称费马-欧拉定理）是一个关于同余的性质。欧拉定理表明，若 $n , a \displaystyle n,a$ n , a 为正整数，且 $n , a \displaystyle n,a$ n , a 互素（即 $gcd ⁡ ( a , n ) = 1 \displaystyle \gcd(a,n)=1$ g cd ( a , n ) = 1 ），则：

a φ ( n ) ≡ 1 ( m o d n ) \\displaystyle a\^{\\varphi (n)}\\equiv 1{\\pmod {n}}

a φ ( n ) ≡ 1 ( mod n )

即 $a φ ( n ) \displaystyle a^{\varphi (n)}$ a φ ( n ) 与 $1 \displaystyle 1$ 1 在模 $n \displaystyle n$ n 下同余。欧拉定理实际上是费马小定理的推广。

模逆元 {#模逆元}

模逆元（Modular multiplicative inverse）也称为模倒数、数论倒数。

一整数 $a \displaystyle a$ a 对同余 $n \displaystyle n$ n 之模逆元是指满足以下公式的整数 $b \displaystyle b$ b ：

a − 1 ≡ b ( m o d n ) . \\displaystyle a\^{-1}\\equiv b{\\pmod {n}}.

a − 1 ≡ b ( mod n ) .

也可以写成 $a b ≡ 1 ( m o d n ) \displaystyle ab\equiv 1{\pmod {n}}$ ab ≡ 1 ( mod n ) 或者 $a b m o d n = 1 \displaystyle ab\mod {n}=1$ ab mod n = 1 。

整数 $a \displaystyle a$ a 对模数 $n \displaystyle n$ n 之模逆元存在的充分必要条件是 $a \displaystyle a$ a 和 $n \displaystyle n$ n 互素，若此模逆元存在，在模数 $n \displaystyle n$ n 下的除法可以用和对应模逆元的乘法来达成，此概念和实数除法的概念相同。

RSA算法 {#RSA算法}

公钥与私钥的产生 {#公钥与私钥的产生}

假设Alice想要通过不可靠的媒体接收Bob的私人消息。她可以用以下的方式来产生一个公钥和一个私钥：

随意选择两个大的素数 $p \displaystyle p$ p 和 $q \displaystyle q$ q ， $p \displaystyle p$ p 不等于 $q \displaystyle q$ q ，计算 $N = p q \displaystyle N=pq$ N = pq 。
根据欧拉函数，求得 $r = φ ( N ) = φ ( p ) × φ ( q ) = ( p − 1 ) ( q − 1 ) \displaystyle r=\varphi (N)=\varphi (p)\times \varphi (q)=(p-1)(q-1)$ r = φ ( N ) = φ ( p ) × φ ( q ) = ( p − 1 ) ( q − 1 ) 。
选择一个小于 $r \displaystyle r$ r 的整数 $e \displaystyle e$ e ，使 $e \displaystyle e$ e 与 $r \displaystyle r$ r 互质。并求得 $e \displaystyle e$ e 关于 $r \displaystyle r$ r 的模逆元，命名为 $d \displaystyle d$ d （求 $d \displaystyle d$ d 令 $e d ≡ 1 ( m o d r ) \displaystyle ed\equiv 1{\pmod {r}}$ e d ≡ 1 ( mod r ) ）。（模逆元存在，当且仅当 $e \displaystyle e$ e 与 $r \displaystyle r$ r 互质。）
将 $p \displaystyle p$ p 和 $q \displaystyle q$ q 的记录销毁。

其中， $( N , e ) \displaystyle (N,e)$ ( N , e ) 是公钥， $( N , d ) \displaystyle (N,d)$ ( N , d ) 是私钥。Alice将她的公钥 $( N , e ) \displaystyle (N,e)$ ( N , e ) 传给Bob，而将她的私钥 $( N , d ) \displaystyle (N,d)$ ( N , d ) 藏起来。

加密消息 {#加密消息}

假设Bob想给Alice送消息 $m \displaystyle m$ m ，他知道Alice产生的 $N \displaystyle N$ N 和 $e \displaystyle e$ e 。他使用起先与Alice约好的格式将 $m \displaystyle m$ m 转换为一个小于 $N \displaystyle N$ N 的非负整数 $n \displaystyle n$ n ，比如他可以将每一个字转换为这个字的Unicode码，然后将这些数字连在一起组成一个数字。假如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为 $n \displaystyle n$ n 。用下面这个公式他可以将 $n \displaystyle n$ n 加密为 $c \displaystyle c$ c ：

c = n e m o d N \\displaystyle c=n\^{e}{\\bmod {N}}

c = n e mod N

这里的 $c \displaystyle c$ c 可以用模幂算法快速求出来。Bob算出 $c \displaystyle c$ c 后就可以将它传递给Alice。

解密消息 {#解密消息}

Alice得到Bob的消息 $c \displaystyle c$ c 后就可以利用她的密钥 $d \displaystyle d$ d 来解码。她可以用以下这个公式来将 $c \displaystyle c$ c 转换为 $n \displaystyle n$ n ：

c = n e m o d N \\displaystyle c=n\^{e}{\\bmod {N}}

c = n e mod N

与Bob计算 $c \displaystyle c$ c 类似，这里的 $n \displaystyle n$ n 也可以用模幂算法快速求出。得到 $n \displaystyle n$ n 后，她可以将原来的信息 $m \displaystyle m$ m 重新复原。

解码的原理是

c d ≡ n e ⋅ d ( m o d N ) \\displaystyle c\^{d}\\equiv n\^{e\\cdot d}\\ (\\mathrm {mod} \\ N)

c d ≡ n e ⋅ d ( mod N )

已知 $e d ≡ 1 ( m o d r ) \displaystyle ed\equiv 1{\pmod {r}}$ e d ≡ 1 ( mod r ) ，即 $e d = 1 + h φ ( N ) \displaystyle ed=1+h\varphi (N)$ e d = 1 + h φ ( N ) 。那么有

n e d = n 1 + h φ ( N ) = n ⋅ n h φ ( N ) = n ( n φ ( N ) ) h \\displaystyle n\^{ed}=n\^{1+h\\varphi (N)}=n\\cdot n\^{h\\varphi (N)}=n\\left(n\^{\\varphi (N)}\\right)\^{h}

n e d = n 1 + h φ ( N ) = n ⋅ n h φ ( N ) = n ( n φ ( N ) ) h

若 $n \displaystyle n$ n 与 $N \displaystyle N$ N 互素，则由欧拉定理得：

n e d ≡ n ( n φ ( N ) ) h ≡ n ( 1 ) h ≡ n ( m o d N ) \\displaystyle n\^{ed}\\equiv n\\left(n\^{\\varphi (N)}\\right)\^{h}\\equiv n(1)\^{h}\\equiv n{\\pmod {N}}

n e d ≡ n ( n φ ( N ) ) h ≡ n ( 1 ) h ≡ n ( mod N )

若 $n \displaystyle n$ n 与 $N \displaystyle N$ N 不互素，则不失一般性考虑 $n = p h \displaystyle n=ph$ n = p h ，以及 $e d − 1 = k ( q − 1 ) \displaystyle ed-1=k(q-1)$ e d − 1 = k ( q − 1 ) ，得：

n e d = ( p h ) e d ≡ 0 ≡ p h ≡ n ( m o d p ) \\displaystyle n\^{ed}=(ph)\^{ed}\\equiv 0\\equiv ph\\equiv n{\\pmod {p}}

n e d = ( p h ) e d ≡ 0 ≡ p h ≡ n ( mod p )

n e d = n e d − 1 n = n k ( q − 1 ) n = ( n q − 1 ) k n ≡ 1 k n ≡ n ( m o d q ) \\displaystyle n\^{ed}=n\^{ed-1}n=n\^{k(q-1)}n=(n\^{q-1})\^{k}n\\equiv 1\^{k}n\\equiv n{\\pmod {q}}

n e d = n e d − 1 n = n k ( q − 1 ) n = ( n q − 1 ) k n ≡ 1 k n ≡ n ( mod q )

故 $n e d ≡ n ( m o d N ) \displaystyle n^{ed}\equiv n{\pmod {N}}$ n e d ≡ n ( mod N ) 得证。

签名消息 {#签名消息}

RSA也可以用来为一个消息署名。假如Alice想给Bob传递一个署名的消息的话，那么她可以为她的消息计算一个散列值（Message digest），然后用她的私钥"加密"（如同前面"加密消息"的步骤）这个散列值并将这个"署名"加在消息的后面。这个消息只有用她的公钥才能被解密。Bob获得这个消息后可以用Alice的公钥"解密"（如同前面"解密消息"的步骤）这个散列值，然后将这个数据与他自己为这个消息计算的散列值相比较。假如两者相符的话，那么Bob就可以知道发信人持有Alice的私钥，以及这个消息在传播路径上没有被篡改过。

RSA安全性 {#RSA安全性}

假设偷听者Eve获得了Alice的公钥 $N \displaystyle N$ N 和 $e \displaystyle e$ e 以及Bob的加密消息 $c \displaystyle c$ c ，但她无法直接获得Alice的密钥 $d \displaystyle d$ d 。要获得 $d \displaystyle d$ d ，最简单的方法是将 $N \displaystyle N$ N 分解为 $p \displaystyle p$ p 和 $q \displaystyle q$ q ，这样她可以得到同余方程