模相关攻击

1.暴力分解N:

可攻击特征:

在 N 的比特位数小于 512 的时候,可以采用大整数分解的策略获取 p 和 q。

攻击方法:

大整数分解一般有以下两种方法:

  1. 在线数据库查询:http://factordb.com/
  2. yafu工具 (适用于p和q相近或相差很多)
  3. 特别的,当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
2
3
4
5
6
7
8
9
phi = 1
n = 1
a = [p,q,r...]
for i in a:
if gmpy2.gcd(e,i-1) == 1:
phi = phi * (i-1)
n *= i
d = gmpy2.invert(e,phi)
print(long_to_bytes(pow(c,d,n)))

也可以直接使用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
2
c1 = m^e1 mod n
c2 = m^e2 mod n

2.得到了两个不同的密文c1,c2
因为公钥是公开的(e1,e2,n)已知
那么攻击者一共知道如下信息

1
2
3
gcd(e1, e2) = 1
m = c1^d1 mod n
m = c2^d2 mod n

3.若两个秘钥e互素根据扩展的欧几里得算法则存在s1,s2有:

e1s1+e2s2=1

所以

1
2
3
4
c1^s1 mod n=m^(e1*s1) mod n
c2^s2 mod n=m^(e2*s2) mod n
c1^s1*c2^s2 mod n=m^(e1*s1+e2*s2) mod n
c1^s1*c2^s2 =m mod n

4.也就是在完全不知道私钥的情况下,得到了明文m

也就是在完全不知道私钥的情况下,得到了明文m

1
m =  (c1^s1 * c2^s2) %n

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from gmpy2 import invert
import binascii
def gongmo(n, c1, c2, e1, e2):
def egcd(a, b):
if b == 0:
return a, 0
else:
x, y = egcd(b, a % b)
return y, x - (a // b) * y
s = egcd(e1, e2)
s1 = s[0]
s2 = s[1]

# 求模反元素
if s1 < 0:
s1 = - s1
c1 = invert(c1, n)
elif s2 < 0:
s2 = - s2
c2 = invert(c2, n)
m = pow(c1, s1, n) * pow(c2, s2, n) % n
return m
c1=
e1=
c2=
e2=
result = gongmo(n, c1, c2, e1, e2)
print(result)

print(binascii.unhexlify(hex(result)[2:].strip("L")))
//print(long_to_bytes(result))

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

则:

H5wYVO.png

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from gmpy2 import *
from Crypto.Util.number import *

def pollard(N):
a = 2
n = 2
while True:
a = powmod(a, n, N)
p = gcd(a-1, N)
if p != 1 and p != N:
return p
n += 1

n =
c =
e =

p = pollard(n)
q = n // p
d = invert(e, (p-1)*(q-1))
print(long_to_bytes(powmod(c, d, n)))

2.p+1光滑

当 p 是 N 的因数,并且 p+1 是光滑数,可能可以使用 Williams’ p + 1 算法来分解 N。

原理太过复杂,这里给出脚本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def mlucas(v, a, n):
""" Helper function for williams_pp1(). Multiplies along a Lucas sequence modulo n. """
v1, v2 = v, (v**2 - 2) % n
for bit in bin(a)[3:]: v1, v2 = ((v1**2 - 2) % n, (v1*v2 - v) % n) if bit == "0" else ((v1*v2 - v) % n, (v2**2 - 2) % n)
return v1

for v in count(1):
for p in primegen():
e = ilog(isqrt(n), p)
if e == 0: break
for _ in xrange(e): v = mlucas(v, p, n)
g = gcd(v-2, n)
if 1 < g < n: return g # g|n
if g == n: break