RSA简介

RSA密钥体制做个简略的介绍。

1.选择两个大的参数，计算出模数 N = p * q
2.计算欧拉函数 φ = (p-1) * (q-1)，然后选择一个e(1<e<φ)，并且e和φ互质（互质：公约数只有1的两个整数）
3.取e的模反数d，计算方法为:e * d ≡ 1 (mod φ) （模反元素：如果两个正整数e和n互质，那么一定可以找到整数d，使得 e * d - 1 被n整除，或者说e * d被n除的余数是1。这时，d就叫做e的“模反元素”。欧拉定理可以用来证明模反元素必然存在。两个整数a,b，它们除以整数M所得的余数相等：a ≡ b(mod m)，比如说5除3余数为2，11除3余数也为2，于是可写成11 ≡ 5(mod 3)。）
4.对明文m进行加密：c = pow(m, e, N),可以得到密文c。
5.对密文c进行解密：m = pow(c, d, N),可以得到明文m。

整理：

p 和 q：两个大的质数，是另一个参数N的的两个因子。
N：大整数，可以称之为模数
e 和 d：互为无反数的两个指数
c 和 m：密文和明文
(N, e)：公钥
(N, d)：私钥
pow(x, y, z)：效果等效pow(x, y)1 % z， 先计算x的y次方，如果存在另一个参数z，需要再对结果进行取模。
密钥长度：n以二进制表示的的位数，例如密钥长度为512代表n用二进制表示的长度为512bit。
dp≡dmod(p−1)
dq≡dmod(q−1)

RSA安全性分析

对于RSA加密算法，公钥(N, e)为公钥，可以任意公开，破解RSA最直接（亦或是暴力）的方法就是分解整数N，然后计算欧拉函数φ(n)=(p-1) * (q-1),再通过d * e ≡ 1 mod φ(N)，即可计算出 d，然后就可以使用私钥(N, d)通过m = pow(c,d,N)解密明文。
保障RSA的安全性

1.定期更换密钥
2.不同的用户不可以使用相同的模数N
3.p与q的差值要大，最好是差几个比特
4.p-1与q-1都应该有大的素因子，一般建议选择的两个大素数p、q使得p=2p+1和q=2q+1也是素数
5.e的选择不要太小
6.d的选择也是不可以太小，最好满足d>=n的4分之1

常见攻击手段

0x 01 dp,dp泄露

场景描述：

假设题目仅给出p，q，dp，dq，c，即不给公钥e

这种参数是为了让解密的时候更快速产生的

dp≡d%(p-1)
dq≡d%(q-1)