RSA算法小结

0x01 对称加密与非对称加密

1.1、加密和解密过程

对称加密过程和解密过程使用的同一个密钥，加密过程相当于用原文+密钥可以传输出密文，同时解密过程用密文-密钥可以推导出原文。但非对称加密采用了两个密钥，一般使用公钥进行加密，使用私钥进行解密。

1.2、加密解密速度

对称加密解密的速度比较快，适合数据比较长时的使用。非对称加密和解密花费的时间长、速度相对较慢，只适合对少量数据的使用。

1.3、传输的安全性

对称加密的过程中无法确保密钥被安全传递，密文在传输过程中是可能被第三方截获的，如果密码本也被第三方截获，则传输的密码信息将被第三方破获，安全性相对较低。

非对称加密算法中私钥是基于不同的算法生成不同的随机数，私钥通过一定的加密算法推导出公钥，但私钥到公钥的推导过程是单向的，也就是说公钥无法反推导出私钥。所以安全性较高。

0x02 RSA算法简介

RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。它的加密方式是用公钥进行加密，用私钥进行解密。

具体过程是：接收方拥有两把密钥，公钥和私钥，他把公钥发给发送方，发送方用公钥对要发送的信息（也就是明文）进行加密，然后把密文发给接收方，接收方再用私钥进行解密从而得到明文。

在这个过程中，私钥一直在接收方手里，即使在传输的过程中密文被截获，但截获方不知道私钥是什么，因此无法对密文进行解密，从而保证了信息的安全性。

对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。

到目前为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。

0x03 RSA加密过程

上图很好的概括了RSA公钥私钥生成，加密和解密的过程，下面我们来详细的分析一下这几个过程。

在这之前我们先了解一下什么叫质数（也就是素数）。

3.1、质数和互质数

质数：除了能被1和他本身整除以外，不能其他任何数整除的数叫质数。

互质数：公因数只有1的两个数叫互质数。

互质数的判断方法：

（1）两个不同的数一定是互质数。例如：7和13，19和17

（2）相邻的两个自然数是互质数。例如：15和16

（3）相邻的两个奇数是互质数。例如：23和25

（4）较大那个数是质数的两个数是互质数。例如：88和97

（5）其中一个是质数，另一个不为它的倍数的两个数是互质数。例如：3和10，5和27

（6）2和任何互质数都是互质数。例如：2和67

（7）1不是质数也不是合数，它和任何一个自然数在一起都是互质数。如1和9908

3.2、模运算和模幂运算

模运算：也就是取余运算，两整数相除，取其中的余数作为结果，例如：5 mod 3 = 2 ，4 mod 2 = 0 。

模幂运算：先进行幂运算再进行模运算。例如：5^2 mod 3 -> 25 mod 3 = 1

3.3、模反元素

如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。这时，b就叫做a对模数n的“模反元素”。ab ≡ 1(mod n)
比如，3和11互质，由于 (3 × 4)-1 可以被11整除，所以3的模反元素就是4。显然，模反元素不止一个， 4加减11的整数倍都是3的模反元素 {…,-18,-7,4,15,26,…}，即如果b是a的模反元素，则 b+kn 都是a的模反元素。

3.4、RSA算法

在分析之前，我们先回顾一下公式：

公钥KU：

n：两素数p和q的乘积（p和q必须保密）。

e：与（p-1)(q-1)互质的数。

私钥KR：

n：同上

d：ed ≡ 1 mod ((p-1)(q-1))中 d 的值

加密 ：

c = m^e mod n

解密 ：

m = c^d mod n

算法描述：

（1）选择一对不同的、足够大的质数 p ，q 。

假设p=61，q=53

（2）计算n=p*q。

则n=61*53=3233

（3）计算 φ(n) = (p-1)(q-1) 。

φ(n) = 60*52 =3120

（4）随机选择一个整数e，但 e 要与 φ(n) 互质，并且 1< e < φ(n) 。

我们随机取一个互质数，e=17

（5）计算 d ，根据公式 de ≡ 1 (mod φ(n)) 来计算，此时d为e的模反元素，所以该公式等价于：ed–kφ(n)=1。

将φ(n)=3120，e=17代入得：

17d-3120k=1

由扩展欧几里得算法得到一组解 d=-367，k=2

我们取d=d+kφ(n)= -367 + 1x3120 = 2753

扩展欧几里得算法要是手工算的话有点麻烦，于是小白在网上找到了一个脚本:

import math
def ex_gcd(a, b):
    if 0 == b:
        return 1, 0, a
    x2, y2, r = ex_gcd(b, a % b)
    temp = x2
    x1 = y2
    y1 = temp - int(math.floor(a / b)) * y2
    return x1, y1, r
a=17
b=3120
print(ex_gcd(a,b))

（6）公钥为：KU = (e,n)，私钥为：KR = (d,n)

所以公钥KU=(17,3233)，私钥KR = (2753,3233)

（7）加密时，把要加密的信息转化为小于n的数字m（可以去ascii或unicode值），如果信息非常长的话，可以把信息分为几段，然后每一段转换成数字m，然后再公钥进行加密：

c = m^e mod n

我们假设要发送的信息为一个字母“A”，我们先把“A”转换成ascii码65，

所以把公钥KU=(17,3233)代入公式得：

c = 65^17 mod 3233

这个运算量比较大，建议写个脚本来计算，或者用python的交互式编译器来计算，

反正不管怎么算能算出来就行。

然后得到密文c = 2790

（8）解密时用私钥进行解密：

m = c^d mod n

把私钥KR = (2753,3233)代入公式得：
     
m = 2790^2753 mod 3233

最后解出明文 m = 65，最后再转回字符“A”就行了

0x04 RSA解密脚本

#!/usr/bin/env python2
# -*- coding:utf-8 -*-
import gmpy2

p = 61
q = 53
e = 17
s = (p-1)*(q-1)
d = gmpy2.invert(e,s)
print "解密结果为 :",d

不过这个脚本需要模块 gmpy2 ，这里要python2的运行环境，本来想在python3上下gmpy2模块的，结果弄了半天也没弄好，于是就弄了python2的。

模块gmpy2的安装方法：https://www.cnblogs.com/pcat/p/5746821.html

总结： 在实际操作中，我们很少手动去计算RSA的算法过程，大多数都是用脚本跑，因为里面有些值手工算会很麻烦。但脚本只是个工具，我们要在会用脚本的同时知道它的运算原理，这样才能学到点东西。