密码学RSA非对称算法原理
首先我们看一个非对称加密在现实中的具体应用(笑
有学生没带作业, 老师需要在群里提醒家长, 但直接发学生的照片就会被所有家长知道没带作业的学生是谁, 这样会导致学生和家长都很没面子.
- 所以老师使用了公钥(大家都能看到的): 学生的鞋子.
- 大家看到的只是三个学生的鞋子, 并不知道学生具体是谁, 即看到的是密文.
- 家长看到了鞋子, 因为拥有私钥(即只有家长自己知道自己家孩子穿的什么样的鞋), 所以可以知道老师发的照片中学生是谁, 破解了密文, 这就完成了一次非对称性的加密和解密.
换成严谨一点的语言描述, 如下:
- A要向B发送信息，A和B都要产生一对用于加密和解密的公钥和私钥。
- A的私钥保密，A的公钥告诉B；B的私钥保密，B的公钥告诉A。
- A要给B发送信息时，A用B的公钥加密信息，因为A知道B的公钥。
- A将这个消息发给B（已经用B的公钥加密消息）。
- B收到这个消息后，B用自己的私钥解密A的消息。其他所有收到这个报文的人都无法解密，因为只有B才有B的私钥。
从上文可以看出, 非对称加密体系不要求通信双方事先传递密钥或有任何约定就能完成保密通信，并且密钥管理方便，可实现防止假冒和抵赖，因此，更适合网络通信中的保密通信要求.
原理
根据数论，寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥.
获取公钥私钥过程
- 选择两个很大的素数p和q
这里取$p=67,q=71$
- 计算$n=p⋅q, n$公开, 即为公钥的一部分.
(如果$n=p⋅q=4757_{(10)}=1001010010101_{(2)}$, 二进制的n为13位, 则称该加密为13位加密, 实际应用中一般才用1024位或2048位的加密来保证安全).
- 计算 n 的欧拉函数 $φ(n)$
设$m=φ(n)=φ(q)⋅φ(q)=(q−1)(p−1)=66×70=4620.$
在数论，对正整数n，欧拉函数φ(n)是小于或等于n的正整数中与n互质的数的数目（因此φ(1)=1(1), φ(8)=4(1,3,5,7）, 这里的p,q都是质数, 所以从1到(n-1)都与其互质, φ(n)=n−1
- 再选一个数字e, e与m互质, 且1<e<m, e也是公开的, 即公钥的另一部分.
这里取e=101, 这里e的选择有一个小坑, 我们一会再说
- 找到一个整数 d，可以使得 e∗d
等价于$e*d−1=y∗m, y∈N+$, 将数字带入$101×d−1=y×4757$,
这里可用扩展欧几里得算法解, 下文给出过程, 这里省略. 给出结果$(d,y)=(1601,35)$, 即$d=1601$, 从这里可以看出, d是由我们上面第4步任意取的e决定的, 所以我们只要选取不同的e, 就可以得到不同的d, 就是不同的密钥对.
- 现在我们得到了公钥(n,e)=(4757,101)和私钥(n,d)=(4757,1601), (n,e)=(4757,101)是公开的.
如果我们想通过(n,e)得到(d), 我们就需要知道m, 而想要知m就需要我们对n进行因数分解, 分解成两个质数, 我们粗略的估算一下时间
根据素数分布理论 $$ \pi(x)=\int_{2}^{x} \frac{d t}{\ln t}+O\left(x e^{-\frac{1}{15} \sqrt{\ln x}}\right) \approx \frac{x}{\ln x} $$ 关系式中间项的右边第二项是误差估计, 详见大O符号
定义 π(x) 为素数计数函数，也就是小于等于x 的素数个数。例如 $\pi(10)=4 \Rightarrow \frac{10}{\ln (10)}=\frac{10}{2.30258}=4.34294$，因为共有 4 个素数小于等于 10，分别是 2,3,5,7.
那么如果是1024位即21024≈10309, 那么$π(10309)=10309309*ln(10)≈1.4×10307$, 即大概存在这么多的质数.
不考虑你是否有储存这么多质数的内存(大概10290T**b), 即使真的能算, 按照天河二号的峰值速度54,902.4TFLOPS（万亿次浮点运算）, 即5.49024×1016 次每秒,
也需要 $$ \frac{1.4 \times 10^{307}}{5.49024 \times 10^{16}}=2.55 \times 10^{299} s $$ 即$808∗10^{280}$年.
加密解密过程
比如Alice要给Bob发送汉字’中’, 公钥密钥如上文所示. 那么加解密的过程
加密
- 将’中’的utf-8 编码 [e4 b8 ad](也可以是ascii 值或unicode值), 转换为10进制[228,184,173].
- 公钥(n，e)=(4757,101), 通过公钥加密上述数字, 公式为a**e, %是取模符号
计算 [228,184,173]的密文：
$$ \begin{array}{l}228^{101} \operatorname{Mod} 4757=4296 \ 184^{101} \operatorname{Mod} 4757=2458 \ 173^{101} \operatorname{Mod} 4757=3263\end{array} $$ 得到 [4296，2458，3263]
这样, 没有密钥, 谁也无法从 [4296，2458，3263] 这串还原出[228,184,173]
解密
- 公式同样为a**d
- 私钥(n,d)=(4757,1601)
密文 [4296，2458，3263]的明文如下
$$ \begin{aligned} 4296^{1601} \operatorname{Mod} 4757 & =228 \ 2458^{1601} \operatorname{Mod} 4757 & =184 \ 3263^{1601} \operatorname{Mod} 4757 & =173\end{aligned} $$
得到 [228,184,173] 将[228,184,173] 再按 utf-8 解码为汉字 “中”，至此解密完毕。
在上面加解密的过程中, 公式都是一样的, 所以可以把(n,d)和(n,e)互换, 结果同样可以进行加解密, 所以公钥私钥是相对的, 不是绝对的.
这同样也是数字签名的原理
关于大数的质数分解困难的解释
todo:
- e的坑
- 大数质数分解的困难
- 具体代码实现
我们上面提到了e的一个小坑, 我们这里说一下. e要在(1,4620)的区间里面, 但e不能取4619.
假设e=4619, 那么4619⋅d−1=y∗4757, 可以得到$d=``