RSA加密解密原理

加密过程

加密过程可以通过如下公式表示

C=Memodn

C ：加密后的密文。
M ：表示要加密的明文数据块。将要加密的明文分成若干个消息块，然后将消息块中的字符转换为数字，这样就得到了一个很大的整数M。
e ：公钥之一
n ：公钥之一

解密过程

解密过程可以通过如下公式表示

M=Cdmodn

其中 C 和 M 与上面的定义一致。 d 就是使用者的私钥。

它是如何工作的？

举一个简单的例子

1. 首先选择两个素数，比如我们选11和23
2. 计算他们的乘机，得到 n 。即 n=11∗23=253 .
3. 现在计算私钥 d ， d 要与 (p−1)(q−1) 互质。这样的数有很多个，这里我们选19，即 d=19
4. 公钥 e 可由公式 19e(mod220)=1 计算出。计算得到 e=139
5. 这样，我们得到了公钥 (e,n)=(139,253) 和私钥 d=19

现在尝试加密数据“Hi”

1. 查“Hi”的ASCII值，得到明文 (72,105)
2. 用公钥对明文进行加密

72139(mod253)=2105139(mod253)=101

得到密文 (2,101)
3. 使用私钥 d ，将密文还原成明文

219(mod253)=7210119(mod253)=105

4. 将明文转换为对应的ASCII字符，得到“Hi”

工作原理

欧拉函数

欧拉函数定义

欧拉函数 φ(n) 是小于或等于n的正整数中与n互质的数的数目。
如小于 5 且与 5 互质的数有 1,2,3,4 ，所以 φ(5)=4 。又比如小于 8 且与 8 互质的数有 1,3,5,7 ，所以 φ(8)=4

欧拉函数的值

1. φ(1)=1
2. 若 n 是质数 p 的 k 次幂，则 φ(n)=pk−pk−1=(p−1)pk−1 。
   如 φ(25)=φ(52)=52−51=20
3. 若 m,n 互质，则 φ(mn)=φ(m)∗φ(n) 。
   如 φ(72)=φ(8∗9)=φ(23∗32)=φ(23)∗φ(32)=(8−4)∗(9−3)=24

欧拉定理

若 n,a 是正整数，且 n,a 互质，则

aφ(n)≡1(modn)

其中 φ(n) 欧拉函数。
比如 a=3,n=5 ，则 φ(5)=4,aφ(n)=34=81 。
而 81≡80+1≡1(mod5)

欧拉定理可以用来简化幂运算，如计算 7222 的个位数。由于 7 和 10 互素，且 φ(10)=4 。由欧拉定理知 74≡1(mod10) 。所以 7222=74⋅55+2=(74)55⋅72≡155⋅72≡49≡9(mod10) 。

RSA模型

1. 首先要选两个很大的素数 p,q ，并计算 n=p∗q 作为公钥的一部分，但选择的 p,q 需要保密。
2. 此时欧拉函数 φ(n)=φ(pq)=(p−1)(q−1)
3. 像上面的例子一样，选择一个 d ，保证 min(p,q)≤d≤φ(n) ，且 d 与 φ(n) 互质。
4. 通过 edmodφ(n)=1 得到 e 。此时已得到全部公钥 e,n 和私钥 d ，且 ed=1+rφ(n)

5. 加密过程为 C=Memodn ，解密过程为 M′=Cdmodn 。等式成立的推导过程为：
   

   M′=Cdmodn=(Memodn)dmodn =Medmodn=M1+rφ(n)modn=M∗(Mφ(n))rmodn
   
   由欧拉定理， Mφ(n)≡1(modn) ，所以
   
   M∗(Mφ(n))rmodn=M∗1rmodn=Mmodn

   此时说明明文 M 经过编码为 C 再经过解码为 M′ 时, M′=Mmodn 。但我们在做编码解码时, 限制 0≤M′<n,0≤M<n ，所以编码和解码后的结果是相同的，即 M=M′ 。

证毕。