RSA算法简介
灌水乐园
4 953
莫尘 2018-03-29
积分：1
RSA体制是PKI最出名的体制，其他两种著名的公钥体制是离散对数体制和椭圆曲线体制(后续会慢慢介绍这两种体制的本质)。在介绍RSA体制前，先做一些简单的数学知识介绍。
众所周知，RSA算法的安全性基于将一个大数(非素数)分解为素数因子是及其困难的，可是大家可能并没有想过一个数(非素数)为什么一定可以因式分解，在很多人看来或许这是个无需证明的推论。此处我也不准备证明这个推论，不过我给出这个推论的严格定义，该推论名为算术基本定理(具体的证明，大家可以用数学归纳法证明)，算术基本定理的定义如下:
-
- 任意数字 n 都可以以某种方式分解成素数乘积
- 仅有一种这样的因式分解(不考虑顺序)
至于因式分解的复杂度具体多少，因为本人水平有限，无法给出具体的推论以及证明。接下来我简单介绍一下RSA算法。
密钥生成:
1. 生成两个长度相等的随机大素数 p, q
2. 计算 n = pq, φ(n) = (p - 1)(q - 1)，此处gcd(p, q) = 1，所以欧拉函数的值等于(p - 1) * (q - 1)，具体欧拉函数的一些推论以及证明有机会和大家讨论
3. 随机选择整数 e,e 满足 1 < e < φ(n) 且 gcd(e, φ(n)) = 1
4. 计算整数 d, d 满足 1 < d < φ(n),ed ≡ 1 (mod φ(n))，≡为同余符号
5. (n, e) 为公钥,d 为私钥
私钥签名:
1. h = H(m)，其中 H 是任意一个杂凑函数(比如sm3，md5)，m为明文
2. s = h ^ d mod n，s 即为签名结果
公钥签名验证:
1. h = H(m), m 为明文
2. h1 = s ^ e mod n, s 为签名结果
3. if h == h1 return true else return false
具体的实现还需要加入一些随机值来保证安全性，为了性能考虑还会引入蒙哥马利等算法提升性能，具体的细节有机会和大家讨论，接下来我简单证明一下签名和验签:
因为 ed ≡ 1 (mod φ(n)), 所以 ed = mφ(n) + 1
因为s = h ^ d mod n, 所以 h ^ d ≡ s (mod n)
因为 h ^ d ≡ s mod n, 所以 s = h ^ d - kn, k 为整数
因为 h1 = s ^ e mod n,所以 s ^ e ≡ h1 mod n
因此要证明签名验证算法的正确性只需证明 h ≡ s ^ e mod n
因为 s = h ^ d - kn,所以代入式中得 h ≡ (h ^ d − kn) ^ e mod n
因为 kn 是 n 的倍数,所以只需证明 h ≡ (h ^ d ) ^ e mod n 即可
因为 ed = mφ(n) + 1,所以只需证明 h ≡ h ^ (mφ(n)+1) mod n 即可
因为 h ≡ h ^ (mφ(n)+1) mod n, 所以只需证明 h ≡ h1 h ^ (φ(n) ^ m) mod n 即可
根据欧拉定理 a ^ φ(n) ≡ 1 mod n 可得 h ≡ h 1 mod n,至此,证明完毕
灌水贴，大致扯了一下RSA算法，有机会和大家好好讨论
Jacklli
yason.li
LMOS
yuan郭
近一月发帖榜 - TOP 12
LMOS
4帖子
Jacklli
3帖子
- 最近热帖
- RSA算法简介 952
- Git常用的命令速查 925
- 灌水第一楼 904
- 一次在STM32F00X 上的诡异Bug排查手记 879
- 向Linux内核发信的一点小注意事项 859
- Mark一下希望能与社区一起成长 838
- 很高兴今天加入LMOS社区和大家一起学习 818
- 大家多多发言 802
- 美国留学生考试作弊本科没毕业申诉之旅何时结束，申请硕士来圆梦 77
- 精选帖子
- 零门槛为LMOS做contribution系列 1091
- 裸机版HelloWorld 1579
- PC机上调试lmosem操作系统内核 1773
友情链接
捐赠我们
- 请使用支付宝扫码捐赠，您的支持是我们前进的动力！