RSA加密算法笔记
阮一峰RSA算法原理一
阮一峰RSA算法原理二
- 历史 1977年三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。一直公开被破解的秘钥长度为768位，超过768位的可认为是安全的，1024长度的非常安全，2048位的极其安全
- 数学原理
- 互质关系
如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。
- 欧拉函数
任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？计算这个值的方法就叫做欧拉函数，以φ(n)表示。
- 欧拉定理
如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立：
aφ(n)≡1(mod n)
也就是说，a的φ(n)次方被n除的余数为1
- 模反元素 如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。
ab ≡ 1(mod n)
这时，b就叫做a的”模反元素”。
- 互质关系
- RSA密钥生成步骤
- 随机选择两个不相等的指数p和q 【RSA加密算法笔记】实际应用中，这两个质数越大，就越难破解。
- 计算p和q的乘积n。 n需要转换为二进制，二进制的位数就是密钥长度，一般密钥长为1024，重要场合用2048位
- 计算n的欧拉函数φ(n) 根据公式：φ(n) = (p-1)(q-1)
- 随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质 实际应用中，常常选择65537。
- 计算e对于φ(n)的模反元素d。 ed ≡ 1 (mod φ(n))
- 将n和e封装成公钥，n和d封装成私钥。 实际应用中，公钥和私钥的数据都采用ASN.1格式表达
- 随机选择两个不相等的指数p和q 【RSA加密算法笔记】实际应用中，这两个质数越大，就越难破解。
- RSA算法的可靠性 一共出现p q n φ(n) e d 这几个关键数字
d是最重要的是因为它和n组成了私钥
（1）ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。
（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。
（3）n=pq。只有将n因数分解，才能算出p和q。
所以，对n的因式分解的难度基本上等于RSA破解的难度。事实上人类已经分解的最大整数是232个十进制位，768个二进制位。比它更大的因数分解，还没有被报道过，因此目前被破解的最长RSA密钥就是768位。
- 加密和解密
- 加密要用公钥 (n,e) 所谓加密就是算出下式的c
me ≡ c (mod n)
- 解密要用私钥(n,d) 公式：cd ≡ m (mod n) m即为加密前的明文
你可能会问，公钥(n,e) 只能加密小于n的整数m，那么如果要加密大于n的整数，该怎么办？有两种解决方法：一种是把长信息分割成若干段短消息，每段分别加密；另一种是先选择一种”对称性加密算法”（比如DES），用这种算法的密钥加密信息，再用RSA公钥加密DES密钥。
- 加密要用公钥 (n,e) 所谓加密就是算出下式的c
- 私钥解密的证明 一系列数学公式【头晕】
推荐阅读
- 对称加密和非对称加密的区别
- Android中的AES加密-下
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列