本文共 3785 字，大约阅读时间需要 12 分钟。

非对称加密之RSA

• 场景
  • Alice和Bob通过互联网连接。Alice如何在不共享加密密钥的情况下加密给Bob的消息M ?
  • Alice可以使用# email # SMS # post # social media发送密钥给Bob吗？
  • Bob收到一条来自Alice的消息M，Bob如何证明Alice是唯一可能创建信息M的人呢?
  • Alice连接到一个网站。Alice怎么能确定这个网站是真的呢?
• 所有这些都可以使用非对称密钥加密来解决。

1 非对称密钥加密操作

• Alice希望加密给Bob的消息M。
• Bob有一个公私钥对hkB, pub, kB,pri。Bob将他的公钥发送给Alice

Alice------------------------←kB, pub--------------酒吧Bob-------------------
加密M: ---------------------------------------- 解密:------------------------------
C = E(M)kB,pub-------------C→---------------M = D(E(M)kB,pub)kB,pr

• 如果M用公钥加密，只能用私钥解密，反之亦然。
• 类比：Bob买了一把挂锁，保留了钥匙，然后把锁送给Alice。Alice拿到一个盒子，把文件放进去，用Bob的挂锁锁住盒子，然后把它送给Bob。此时只有Bob可以用密钥打开盒子并检索文档。

非对称密钥密码技术：2种主要的PKC算法- RSA, DH

1. 公钥和私钥对，<Kpub, Kpr>。
2. 单向函数-不可逆转，即给定kpub & C = E(M)kpub -在没有kpr的情况下无法求出E−1
3. 存在一个活板门函数D，可以很容易地使用kpr反转加密，即D(E(M)kpub, kpr) = M
   有两种主要类型的PKC算法:
   • RSA - Rivest, Shamir, and Adleman (1978)
   • DH - Diffie and Hellmann (1976)
     

2 RSA算法

RSA的数学基础

模算术和等价类

• 表达式x ≡ y (mod n)表示当y除以n时，余数为x
• 可以写成y = k·n + r，其中k是一个正整数。
• 例如4 ≡ 25 mod 7，或用括号(mod 7)写。
• 等价类:mod 7操作中，4和25是等价的，即25属于等价类4。
• 同样，{4,11,18,25,32，···}在mod 7中是等价的。
• 在密码学中使用模块化操作，因为它将所有数字保持在同一个集合中，例如mod 7，所有数字都在{1，···，6}中

数论的一些结果

• 考虑正整数，即a, b∈{1，···，n−1}。
• 相对素数:如果gcd(a, b) = 1，则a, b是相对素数(素数)。它们之间的最大公约数是1。例3、5、8、11……相对’。
• 乘数函数:φ(n)为{1，…中正整数的个数
  例如，当n = 10时，{1,3,7,9}对10是素数，φ(10) = 4。
• 欧拉定理:如果a相对于n是素数，则a φ(n)≡1 mod n
• 费马小定理:如果p是素数，那么对于所有a ={1,2，···，p−1}，p−1≡1 mod p
  例如，求p = 31,61,389, 571, 709,937

《孙子算经》中的余数思想和中国剩余定理

“There are certain things whose number is unknown. If we count them by threes, we have two left over; by fives, we have three left over; and by sevens, two are left over. How many things are there?”
这是我们老师放的英文版本，我去找了一下，原文应该是这样一个问题：
“今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何？”
用现在的数学符号表示就是：
x ≡ 2 mod 3
x ≡ 3 mod 5
x ≡ 2 mod 7
发展出中国剩余定理（CRT, Chinese remainder theorem）

• CRT用于证明RSA和解密操作的正确性。

• 定理：只考虑两个等价性。如果p和q是互质数，给出：
  x ≡ a mod p
  x ≡ b mod q
  然后
  x ≡ z mod pq
  当且仅当 z ≡ (p + q)−1(qa + pb) mod pq 时z有唯一解。

• 例子：问：哪个数除以5等于4，除以7等于3?

RSA

RSA加解密的详细过程

1. 选择两个不同的质数p, q，计算n = p·q。
   小于n且相对素数为n的正整数的数目为φ(n) = (p−1)(q−1)
2. 计算公开指数和私有指数<e, d>
   • 计算e, d小于n，e = d, e·d≡1 mod φ
     即对于整数k e·d = kφ + 1
   • 或选择一个合适的值e，使gcd(e，φ) = 1，
     则d ≡ e−1 mod φ
     密钥对:私钥<d, n>，公钥<e, n>
3. 加密消息M, C ≡ M^emod n
4. 解密密文C^d ≡ (M^e)^d mod n

一个简单的例子

• Bob的公私密钥:选择素数p = 5, q = 13
  计算n = p·q = 5 × 13 = 65
  φ = (p−1)(q−1)= 4 × 12 = 48
  找到不同的e, d < n，使得： e·d ≡ 1(mod 48)
  比如e = 5, d = 29，验算：5 × 2 = 145≡1(mod 48)
  可以得到：
  - 私钥：<d, 65> = <29, 65>
  - 公钥： <e, 65> = <5, 65>
• Alice获得Bob的公钥<e, n>，加密M = 33发送给Bob
  C ≡ M^e ≡ 33⁵(mod 65) = 63
• Bob获得C，解密
  Cd ≡ 63²⁹(mod 65) = 33 = M

RSA的正确性演算

• 解密C ≡ M^e mod n
• 如果 gcd(M, n) ≠ 1 ，即M, n是相对素数，设k为整数，得
  P ≡ C^d mod n≡M^ed mod n≡M^kφ(n)+1 mod n
  根据欧拉定理，M^φ(n)≡1 mod n
  那么 P ≡ M·Mkφ(n)≡M mod n
• 如果gcd(M, n) ≠ 1
  让P ≡ C^d mod P并且P ≡ C^d mod q
  根据CRT（中国剩余定理）
  P ≡ (p + q)−1(qC^d + pC^d) mod q≡C^d mod pq
  即 P ≡ C^d mod n
  考虑求解P ≡ C^d mod P而不是 P ≡ C^d mod n
  现在，P ≡ (M^e)^d≡(M)^ed≡M^kφ(n)+1 mod p
  因为p是质数，(M^k(q−1))^(p−1) mod p ≡ 1 mod p
  那么P = M·(M^k(q−1))^p−1 ≡ M mod P
  类似地，有P ≡ C^d mod q

PKC实现

• 模运算
  • 求幂 -平方乘，滑动窗口求幂等。
  • 乘法 -空手道法
  • 还原 - Barrett方法，Montgomery算法
• Openssl库

实现注意事项

• 使用平方乘的模乘法:例如
• 使用短的公开指数进行快速加密，例如 e = 3, 17, 2, 16 + 1
• •如果p和q已知，使用中国剩余定理(CRT)快速解密

发现大质数

• 一个奇数P1是质数的概率P(p1)，根据素数定理是约等于 2/(ln(p1))
  例如，找到512位质数的概率≈1/177
• 素性测试
• 费马检验:选择一个数a，如果 a^p1-1 ≡ 1 mod p1，那么p1可能是质数
  需要运行几次，并且不能是一个“卡迈克尔数”，它不是质数，但行为像一个，例如561
• Rabin-Miller测试

3 RSA的安全性

RSA的安全基础

• 如果n很大(≥1024位)，则不可分解为两个质数。2018年，762位的数字被解出。
  • 所需时间随n的大小呈指数增长
  • 如今，使用1024位、2058位或4096位或更多，量子计算机可以轻松快速地分解大数字，破解RSA
• 在实践中，私钥<d, n>, d通常非常大，即私钥操作非常缓慢。所以私钥必须存储得非常隐秘。
• 在实践中，公钥<e, d>, e非常小，也就是说公钥操作要快得多，公钥可以自由分发。

RSA怎样破解？

• 理论上来说，RSA相当安全，但存在执行缺陷
• 当以下情况发生时，破解RSA会比较简单：
  1. 质数p, q的选择不当时
     • (p−1), (q−1), (p+1)或(q+1)的因子太小
     • 当p/q≈1时，可以用费马法因式分解
  2. 弱键
     • 低熵
     • 小型私有指数，尤指 d< (n^1/4 )/3时
• 侧信道攻击-功耗等
• 故障注入
• 由于量子计算机的迅速发展，量子算法可能会在20到25年内使RSA失效
• 为了安全起见，至少使用1024位，最好是2048位，或者更多

RSA攻击 - 边信道攻击

4 RSA的应用

RSA有两个主要的应用程序，它们被广泛使用，并在互联网上实现安全交易。

1. 会话密钥传输(密钥交换)
2. 数字签名——用于身份验证和不可否认
   • 使用包含数字签名的证书进行原产地认证——广泛用于互联网。
   • 区块链技术

转载地址：http://xujh.baihongyu.com/