Crypto-RSA:模相关攻击
模相关攻击
1.暴力分解N:
可攻击特征:
在 N 的比特位数小于 512 的时候,可以采用大整数分解的策略获取 p 和 q。
攻击方法:
大整数分解一般有以下两种方法:
- 在线数据库查询:http://factordb.com/
- yafu工具 (适用于p和q相近或相差很多)
- 特别的,当q时p的下一个素数时,可以使用以下方法求得p。
1 | p = prevprime(gmpy2.iroot(n,2)[0]) |
p或q选取不当分解N:
当 RSA 中 p 和 q 选取不当时,我们也可以进行攻击。比如一般有以下四种情况
|p-q|很大:当|p-q| 很大时,那么其中p或q有一个值一定很小,我们可以用试除法穷举p或q。
|p-q|很小:yafu分解或开根号后在附近枚举。
q ≈ t * p : 对n/t开根号,在附近找p。
2.多因子:
可攻击特征:
N可被分解为多个素数
原理:
如果选取两个以上的素数,记为 p1,p2,p3.,它们相乘得到 n,那么:
φ(n)=(p1−1)(p2−1)(p3−1)
欧拉函数性质:
(1) p^k型欧拉函数:
若N是质数p(即N=p), φ(n)= φ(p)=p-p^(k-1)=p-1。
若N是质数p的k次幂(即N=p^k),φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)。
(2)mn型欧拉函数
设n为正整数,以φ(n)表示不超过n且与n互素的正整数的个数,称为n的欧拉函数值。若m,n互质,
φ(mn)=(m-1)(n-1)=φ(m)φ(n)。
对于多个因子,n = p * q * r * s
求d时只对e互素的计算:
1 | phi = 1 |
也可以直接使用sagemath中的euler_phi:
1 | phi = euler_phi(n) |
(3)特殊性质:
若n为奇数时,φ(2n)=φ(n)。
对于任何两个互质 的正整数a,n(n>2)有:a^φ(n)=1 mod n (恒等于)此公式即 欧拉定理
当n=p 且 a与素数p互质(即:gcd(a,p)=1)则上式有: a^(p-1)=1 mod n (恒等于)此公式即 费马小定理
3.模不互素:
可攻击特征:
当存在两个公钥的 N 不互素时
原理:
当存在两个公钥的 N 不互素时,我们显然可以直接对这两个数求最大公因数,然后直接获得 p,q,进而获得相应的私钥。
4.共模攻击:
可攻击特征
当两个用户使用相同的模数 N、不同的私钥时,加密同一明文消息时即存在共模攻击。
具体说就是:明文m、模数n相同,公钥指数e、密文c不同,gcd(e1,e2)==1也就是e1和e2互质时候,可能导致共模攻击。
公式推导如下: 转载至 (https://blog.csdn.net/weixin_45859850/article/details/109556891)
1.假设有一条信息m,由两个不同的用户使用公钥进行加密(两个用户的e一般不同,模数n一般相同)
1 | c1 = m^e1 mod n |
2.得到了两个不同的密文c1,c2
因为公钥是公开的(e1,e2,n)已知
那么攻击者一共知道如下信息
1 | gcd(e1, e2) = 1 |
3.若两个秘钥e互素根据扩展的欧几里得算法则存在s1,s2有:
e1s1+e2s2=1
所以
1 | c1^s1 mod n=m^(e1*s1) mod n |
4.也就是在完全不知道私钥的情况下,得到了明文m
也就是在完全不知道私钥的情况下,得到了明文m
1 | m = (c1^s1 * c2^s2) %n |
exp:
1 | from gmpy2 import invert |
5.p-1/p+1光滑:
原理
光滑数(Smooth Number)指可以分解为小素数乘积的正整数。
1.p-1光滑
当 p 是 N 的因数,并且 p−1 是光滑数,可能可以使用 Pollard’s p − 1 算法来分解 N。
首先根据费马小定理:
如果 p 是一个质数,而整数 a 不是 p 的倍数,则有 a^(p−1) ≡ 1 mod p
则:
exp:
1 | from gmpy2 import * |
2.p+1光滑
当 p 是 N 的因数,并且 p+1 是光滑数,可能可以使用 Williams’ p + 1 算法来分解 N。
原理太过复杂,这里给出脚本:
1 | def mlucas(v, a, n): |