本文主要介绍RSA的数学原理、以及RSA的代码演示


引子

密码学

是指研究信息加密、破解密码的技术科学。最早可以追溯到追溯到2000年前。而当今的密码学是以数学为基础的。

密码学发展史

  • 在1976年以前，所有的加密方法都是同一种模式：加密、解密使用同一种算法。在交互数据的时候，彼此通信的双方就必须将规则告诉对方，否则没法解密。那么加密和解密的规则（简称密钥），它保护就显得尤其重要。传递密钥就成为了最大的隐患。这种加密方式被成为对称加密算法（symmetric encryption algorithm）

  • 1976年，两位美国计算机学家 迪菲（W.Diffie）、赫尔曼（ M.Hellman ） 提出了一种崭新构思，可以在不直接传递密钥的情况下，完成密钥交换。这被称为“迪菲赫尔曼密钥交换”算法。开创了密码学研究的新方向

RSA数学原理

上世纪70年代产生的一种加密算法。其加密方式比较特殊，需要两个密钥：公开密钥简称公钥（publickey）和私有密钥简称私钥（privatekey）。公钥加密，私钥解密；私钥加密，公钥解密。这个加密算法被称为的RSA

离散对数问题

现在想实现这一种 加密容易，但是破解很难的加密算法，利用数***算，如mod取模，有如下方案：

  • 用质数做模数，例如17

  • 找一个比17小的数作为n次方的基数，例如3

  • 找出基数的n次方 mod 质数 = 固定的数，求n

3^? mod 17 = 12，此时的`？`是多少呢？（mod -> 求余数,在西方被称为时钟算数）

从下方的规律中可以看出，3的1次方~16次方 mod 17 得到的结果都是不同的，且结果分布在 [1,17)上。此时将 3 称为 17 的原根

首先作为一个开发者，有一个学习的氛围跟一个交流圈子特别重要，这是一个我的iOS开发公众号：编程大鑫，不管你是小白还是大牛都欢迎入驻 ，让我们一起进步，共同发展！

所以根据图中所示，? 可能是13，可能是29等。即从这里可以看出：通过 12 去反推3的?次方是很难的。如果质数加大，反推的难度也会加大。

质数：公约数只有1和自己，其中2是一个特殊质数

欧拉函数φ（读 fai）

定义

任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？计算这个值的方式就叫做欧拉函数，使用Φ(n)表示

互质关系

如果两个正数，除了1以外，没有其他公因数，就称这两个数是互质关系（comprime）

欧拉函数特点

  • 1、当n是质数时，Φ(n) = n - 1

  • 2、如果n可以分解成两个互质的整数之积，例如 n = A * B，则Φ(A * B) = Φ(A) * Φ(B)

所以，根据欧拉函数的以上两个特点，可以得到如下结论：

  • 如果N是两个互质数P1和P2的乘积，则Φ(N) = Φ(P1 * P2) = Φ(P1) * Φ(P2) = (P1-1) * (P2-1)

练习

  • 计算8的欧拉函数：和8互质的有4个，即Φ(8) = 4（ 1，2，3，4，5，6，7，8 - 1-8中有4个数和8互质）

  • 计算7的欧拉函数：和7互质的有6个，即Φ(7) = 6（1，2，3，4，5，6，7 - 1-7中有6个数和7互质）

  • 计算56的欧拉函数：Φ(56) = Φ(7 * 8) = Φ(7) * Φ(8) = 6 * 4 = 24

欧拉定理

欧拉定理

如果两个正整数 m 和 n 互质，那么 m 的Φ(n)次方减去1，可以被n整除。即 (m^Φ(n) - 1) / n ≡ 0 ==> m^Φ(n) mod n ≡ 1

费马小定理（欧拉定理的特殊情况）

如果两个正整数 m 和 n 互质，而且 n 为质数，那么 Φ(n) 结果就是 n-1，即 m^(n-1) mod n = 1

  • 例如 m=6，n=5，那么 6^(5-1) mod 5 = 1

公式转换

前提：m和n互为质数，且n为质数，有公式m^Φ(n) mod n ≡ 1

  • 由于1^k ≡ 1 ==> m^k*Φ(n) mod n ≡ 1

    • 推导：将x = m^Φ(n) mod n 看作一个整体 ==> x^k = m^(Φ(n)*k) mod n（是一个定理） 成立

    • 例如：m=6，n=7，则6^(7-1) mod 7 = 1 ==> 6^(6*2) mod 7 = 1

  • 由于1*m ≡ m ==> m^（k*Φ(n)+1） mod n ≡ m（成立条件：m 要比 n小）

    • 例如：m=6,n=7,则6^(6*3+1) mod 7 = m

模反元素

如果两个正整数 e 和 x 互质，那么一定就可以找到整数d，使得 ed - 1 被x整除（即 (ed - 1)/x = 1），那么 d 就是 e 对于 x 的模反元素

  • e * d mod x = 1
    • 理解： e * d - 1 = x * k ==> e * d ≡ k*x + 1
  • e * d ≡ k*x + 1 ===> m^(e*d) mod n = m（条件：d 是相对于 Φ(n) 的模反元素）

    • kx + 1 = kΦ(n)+1 ==> m^(e*d) mod n = m

    • 例如：

- m ：4
- n ：15
- Φ(n)：8
- e：（和Φ(n)互质）3
- d：3d-1=8k ==> d=(8k+1)/3 ==> d=11 19
- 4**(3*11)%5 = 4
- 4**(3*19)%5 = 4

迪菲赫尔曼密钥交换

如下图所示，是一个典型的迪菲赫尔曼密钥交换过程

  • 1、服务端先取一个随机数15，通过 3^15 mod 17 = 6，将6传给客户端（第三方可以窃取这个6）

  • 2、客户端通用的取一个随机数13，通过3^13 mod 17 = 12，将12传给服务器（第三方同样可以窃取这个12）

  • 3、客户端拿到服务器传过来的6，通过6^13 mod 17 = 10，得到10

  • 4、服务端拿到客户端传过来的12，通过12^15 mod 17 = 10，得到10

  • 所以综上所述，服务端和客户端想交换的数字是 10

以下是迪菲赫尔曼密钥交换的原理，最终经过两次计算，客户端和服务端都会得到一个相同的数字，用于数据的传输

  • 客户端：3 ^ 15 mod 17 = 6 + 6^13 mod 17 = 10 ==> 3 ^ （15 * 13） mod 17 = 10

  • 服务端：3 ^ 13 mod 17 = 12 + 12^15 mod 17 = 10 ==> 3 ^ （13 * 15） mod 17 = 10

RSA的诞生

由上面的迪菲赫尔曼密钥交换原理可知，由以下三个公式

- 1、m^e mod n = C
- 2、C^d mod n = m^(e*d) mod n
- 3、m^(e*d) mod n = m

其中c^d mod n = m ，主要是源于 c^d mod n = m^(e*d)mod n = m ，且d 是 e 相对于 φ(n)的模反元素。需要注意的是：m 和 n 既为互质，也为原根，即m 是n的原根

RSA算法

所以最终RSA算法的加解密公式为：

  • 加密：m^e mod n = c

  • 解密：c^d mod n = m

  • 公钥：n和e

  • 私钥：n和d

  • 明文：m

  • 密文：c

其中涉及的公钥、私钥、密文、明文有如下说明

  • 1、n会非常大，长度一般为1024个二进制位（目前人类已经分解的最大整数，232个十进制位，768个二进制位）

  • 2、由于需要求出φ(n)，所以根据欧拉函数特点，最简单的求解φ(n)方式：n由两个质数相乘得到 质数：p1、p2

    • Φ(n) = (p1 -1) * (p2 - 1)

  • 3、最终由 Φ(n) 得到 e 和 d

  • 所以综上所述，总共生成6个数字：p1、p2、n、Φ(n)、e、d

算法演示

m：取值 3 或 12
n：3*5（两个质数相乘）

- φ(n) = （3-1）*（5-1）= 8
- e：3（e和Φ(n)互质）
- d：3d-1=8k ==> d = 11 / 19（由公式 e * d mod x = 1 求解）
- 加密：`m^e mod n = c` ==> 3^3 mod 8 = 3
- 解密：`c^d mod n = m` ==> 3^11 mod 8 = 3

关于RSA的安全说明
除了公钥用到了n和e，其余的4个数字是不公开的，目前破解RSA得到d的方式如下：

  • 1、要想求出私钥 d，由于 e*d = φ(n)*k + 1。要知道e和φ(n)

  • 2、e是知道的，但是要得到 φ(n)，必须知道p1 和 p2。

  • 3、由于 n=p1*p2。只有将n因数分解才能算出。

RSA算法说明

  • RSA效率不高，因为是数***算，且m不能大于n，大数据不适合用RSA加密，一般用对称加密（用key）

    • 交换key时，用RSA加密

    • 大数据传递，其中大数据用key（即对称算法）加密

RSA终端命令

由于Mac系统内置OpenSSL（开源加密库），所以在mac的终端可以直接使用OpenSSl玩RSA，OpenSSL中RSA算法常用命令有3个

命令 含义
genrsa 生成并输入一个RSA私钥
rsautl 使用RSA密钥进行加密、解密、签名和验证等运算
rsa 处理RSA密钥的格式转换等问题

终端演示

  • 1、生成RSA私钥，密钥成都为1024bit

    • 命令：openssl genrsa -out private.pem 1024

    • 查看 cat private.pem文件，其中是base64编码

  • 2、从私钥中提取公钥（即 n和e）

    • 命令：openssl rsa -in private.pem -pubout -out public.pem

    • 查看公钥：cat public.pem

  • 3、生成的文件如下

  • 4、将私钥转换为明文

    • 命令：openssl rsa -in private.pem -text -out private.txt

      image

  • 5、通过公钥加密数据，私钥解密数据

    • 生成明文文件： vi message.txt

    • 查看文件内容：cat message.txt

    • 通过公钥进行加密：openssl rsautl -encrypt -in message.txt -inkey public.pem -pubin -out enc.txt

    • 通过私钥进行解密：openssl rsautl -decrypt -in enc.txt -inkey private.pem -out dec.txt
      生成的文件如下所示

  • 6、通过私钥加密数据，公钥解密数据

    • 通过私钥进行加密（签名）： openssl rsautl -sign -in message.txt -inkey private.pem -out enc.txt

    • 通过公钥进行解密（验证）：openssl rsautl -verify -in enc.txt -inkey public.pem -pubin -out dec.txt

总结

  • 对称加密（传统加密算法）：公钥、私钥采用同一个key

  • RSA非对称加密（现代加密算法）：加解密原理来源迪菲赫尔曼密钥交换

    • 欧拉函数：如果N是两个互质数P1和P2的乘积，则Φ(N) = Φ(P1 * P2) = Φ(P1) * Φ(P2) = (P1-1) * (P2-1)

    • 欧拉定理：如果两个正整数 m 和 n 互质，那么 m 的Φ(n)次方减去1，可以被n整除。即 (m^Φ(n) - 1) / n ≡ 0 ==> m^Φ(n) mod n ≡ 1

    • 费马小定理：如果两个正整数 m 和 n 互质，而且 n 为质数，那么 Φ(n) 结果就是 n-1，即 m^(n-1) mod n = 1

    • 迪菲赫尔曼密钥交换原理

      • m^e mod n = C

      • C^d mod n = m^(e*d) mod n

      • m^(e*d) mod n = m

  • RSA算法

    • RSA原理：拆解两个（大）质数的乘积很难，所以RSA相对安全

    • 加密：M ^ e % N = C

    • 解密：C ^ d % N = M

    • 密文（加密后的）：C

    • 明文（解密后的）：M

    • 公钥：N 和 E

    • 私钥：N 和 D

    • RSA成立条件（总共有6个数字）：

      • N 是由两个很大的质数（P1、P2）相乘得到！为了方便求出φ(N)（其中φ(n) = (p1-1)*(p2-1)）
      • D 是 E (一般是65537，0x10001（从终端演示中得出）) 相对于φ(N)的模反元素