RSA初学者适用

csx

RSA在软件安全中应用广泛，对于初学者，我总结了一部分知识点。
一、模数分解如果n的大小不太大（不大于512位），可以尝试因式分解。常用方法有：在线因子查询网站factordb，Yafu，SageMath，python第三方库factordb-pycli。
factordb-pycli :  factordb n
Yafu :  如果数比较小可以直接 yafu-x64 factor()如果数比较大，需要将数保存成一个txt，然后使用yafu-x64 "factor(@)" -batchfile n.txt（注意：n为十进制，txt文件结尾必须有一个换行符，该命令会删除这个txt注意保存）可以实现对有缺陷的n(pq相差较大或者较小)快速分解。
原理：     （针对大整数的分解有很多种算法，性能上各有优异，有指数级分解方法：Fermat平方差方法，Pollard 方法（ρ，ρ-1），二次型分解算法，椭圆曲线分解法（ECM）和亚指数级分解方法：连分数分解算法，筛法（二次筛选法（QS），一般数域筛法（GNFS））等等。yafu可以自动化的完成分解，不论n的大小）
sagemath ：一般在KALI上使用

公因数攻击（模n不互素攻击）e = 63357较大
如果题目中两次公钥加密给出了n1和n2有相同的素因子，那么可以通过gmpy2.gcd求出素因子p，然后在分别对n1和n2求出q1和q2。这种需要利用公约数的题目，通常情况下给出的n长度都在2048bit，4096bit，无法强行破解。

（遍历所有n的组合对，有非1公约数的n分解，就可得到p)


二、低加密指数攻击
RSA中，e是加密指数，由于e是从（1 ， varphi）之间与 varphi 互素的数中任意选取的。为了缩短加密时间，有时可以选取较小的e。
加密指数e = 3较小，明文加密后不是太大。故可以由c = pow(m , e) + kn得


三、共模攻击
共模攻击即用两个及以上的公钥(n,e)来加密同一条信息m
已知有密文：
c1 = pow(m, e1, n)
c2 = pow(m, e2, n)
当e1，e2互质，则有gcd(e1,e2)=1。根据扩展欧几里德算法，对于不完全为 0 的整数 a，b，gcd（a，b）表示 a，b 的最大公约数。那么一定存在整数 x，y 使得 gcd（a，b）=ax+by

所以得到：e1*s1+e2*s2 = 1
四、低解密指数攻击
若提供的公钥e非常大，那么由于ed在乘积时地位对等，d的值很可能较小。尝试本方法




五、dp，dq泄露
m1 ≡ c^dp  mod p     m2 ≡ c^dq  modq (由中国剩余定理可得crt)
m =( (m2 - m1) *p^-1(mod q)) * p + m1(mod n)

((m2 - m1) * invert(p , q) (mod q)) * p + m1(mod n)