RSA
Intro(RSA) #
前情提要 #
欧拉函数 #
欧拉函数 \(\varphi(n)\) 是小于等于 n 的正整数中与 n 互质的数的数目。
例如：\(\varphi(8) = 4\)，因为 1，3，5 和 7 均与 8 互质。
有如下性质：1.欧拉函数是积性函数，即是说若 m,n 互质，则 \(\varphi(m*n) = \varphi(m) * \varphi(n)\)。2.如果 n 为质数，则 \(\varphi(n) = n - 1\)。同余 #
对某两个整数 a b，若它们除以正整数 m 所得的余数相等，则称 a b 对于模 m 同余，也就是说，存在整数 k 使得 \(a - b = km\)，则称 a,b 对于 m 来说是同余的，一般记作 \(a \equiv b \pmod{m}\)。
比如 \(26 - 14 = 12 = 1 * 12\)
记作 \(26 \equiv 14 \pmod{12}\)模逆元 #
\(ab \equiv 1 \pmod{n}\)，
求整数 3 对同余 11 的模逆元素 x ：\(3x \equiv 1 \pmod{11}\) ==> \(3(4) \equiv 1 \pmod{11}\)，所以此处为 x = 4。
RSA 公私匙产生过程 #
Caution
1.:随意选择两个大质数 p,q。计算 \(N = pq\)。2.根据欧拉函数求得中间值 \(r = \varphi(N) = \varphi(p) * \varphi(q) = (p-1)(q-1)\)3.选择一个小于 r 的整数 e，使 e 与 r 互质。并求 e 关于 r 的模逆元，命名为 d，\(ed \equiv 1 \pmod{r}\)4.销毁 \(pq\)。
得出的 \((N,e)\) 是公匙，\((N,d)\) 是私匙
使用工具可以提取 RSA 中的 \((N,e,d)\)，参考： OPENSSL提取公私匙信息RSA 加密和解密 #
Tip
得到 N,e,d 后，将要加密的消息转化成 小于 N 的非负数 n。比如 N 为33，则可以使用 26个字母（a:1,b:2,c:3…）。
通过 \(c = n^e \mod N\) 加密
通过 \(n = c^d \mod N\) 解密计算过程简单示例 #
若质数 p = 11, q = 3， 则求得 N = 33, \(r = \varphi(N) = \varphi(p*q) = (p - 1)(q - 1) = 20\)。
在 20 中找一个与 20 互质的数，选择为 7，则 e = 7。（当然也可以选择其他的，9，11，13，17，19之类的)，真实公匙中的 e 一般选择为 65537。
代入 \(ed \equiv 1 \pmod{r}\)，得到 \(7(d) \equiv 1 \pmod{20}\)，当 d = 3 时，满足。
综上 \((N,e,d) = (33,7,3)\)。（根据 e 的选择，还可以有其他组合，比如 \((N,e,d) = (33,9,9),(33,11,11),(33,13,17),(33,17,13),(33,19,19)\))
假设要加密的内容为：i love rsa, 使用自定义编码规则，比如： [1,26] 表示 26 个字母，0 表示空格。
所以当前内容编码为：[9 0 12 15 22 5 0 18 19 1]。
加密如下对每一个字符进行 \(c = n^7 \mod 33\) 运算，
第一个i,对应字母位置为 9，则 c =echo '9 ^ 7 % 33' | bc= 15. 第二个空格对应0，则 c =echo '0 ^ 7 % 33' | bc= 0，其他同理。
综上得出加密内容为：[15 0 12 27 22 14 0 6 13 1]。
解密每一个字符通过 \(n = c^3 \mod 33\) 运算，
第一个数字为15，则 n =echo '15 ^ 3 % 33' | bc= 9. 第二个空格对应0，则 n =echo '0 ^ 3 % 33' | bc= 0，其他同理。
综上得出解密内容为：[9 0 12 15 22 5 0 18 19 1]。RSA 破解难点 #
Warning
在已知 \((N,e)\) 公匙的情况下，去获取 \((d)\)，如果能算出来，就是拿到私匙了。(可以为所欲为，冒充签名，拦截 https 流量冒充真实服务器等)。
因为 e 是可以随机选择的，所以跟 N 没有太大关系，现在就剩一个已知条件 N 了。
通过分解 N 得到 p,q，然后算出 \(\varphi(N) = (p - 1)(q - 1) \)，接着利用公式 \(e(d) \equiv 1 \pmod{\varphi(N)}\) 求得 d。
当 N 比较小的时候，比如 N = 33 = (3 * 11)，通过目前因式分解算法很容易算出来，
但是当 N 足够大，1024，2048位的时候，就力不从心了。
截至 2020 年，已知被破解的 RSA 最大长度为 829 位。
Reference #