模相关攻击

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，进而获得相应的私钥。

1
2
3
4
5
6
7
8
9
n=[n0,n1,n2,n3,n4,n5,n6,n7,n8,n9,n10,n11,n12,n13,n14,n15,n16,n17,n18,n19]
c=[c0,c1,c2,c3,c4,c5,c6,c7,c8,c9,c10,c11,c12,c13,c14,c15,c16,c17,c18,c19]

for i in range(len(n)):
    for j in range(len(n)):
        if(i!=j):
            if(gcd(n[i],n[j])!=1):   #对不同的n进行 欧几德得 算法，以求出最大公约数
                print(i,j)
                print("p =",gcd(n[i],n[j]))

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
33
from gmpy2 import *
from Crypto.Util.number import *
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

6、Common Prime RSA

摘自大佬：Common Prime RSA 笔记 | 独奏の小屋

就是p-1或q-1有一个大数因子。

例题：强网杯2024初赛easyrsa

题目：

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
33
34
35
36
37
38
39
40
from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime
import random, gmpy2

class RSAEncryptor:
	def __init__(self):
		self.g = self.a = self.b = 0
		self.e = 65537
		self.factorGen()
		self.product()

	def factorGen(self):
		while True:
			self.g = getPrime(500)
			while not gmpy2.is_prime(2*self.g*self.a+1):
				self.a = random.randint(2**523, 2**524)
			while not gmpy2.is_prime(2*self.g*self.b+1):
				self.b = random.randint(2**523, 2**524)
			self.h = 2*self.g*self.a*self.b+self.a+self.b
			if gmpy2.is_prime(self.h):
				self.N = 2*self.h*self.g+1
				print(len(bin(self.N)))
				return

	def encrypt(self, msg):
		return gmpy2.powmod(msg, self.e, self.N)


	def product(self):
		with open('/flag', 'rb') as f:
			self.flag = f.read()
		self.enc = self.encrypt(self.flag)
		self.show()
		print(f'enc={self.enc}')

	def show(self):
		print(f"N={self.N}")
		print(f"e={self.e}")
		print(f"g={self.g}")

RSAEncryptor()

其中

1
2
3
p = 2ga + 1
q = 2gb + 1 
g ≈ n ^ 0.244

这显然是个已知g的Common Prime RSA攻击,直接套板子：

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
N=18609249586511447022929188601029606630816796460795187470065452150283160549624372398383148374249992521068549349516037511009027303530058706112191091689108542770802393390942693648814845389265858611340109158309645284100825624911741650444467173946569096983438455034895955228543351436008546035535031019474847660151534447157873386841134028651786166708821300066332734338450150803713659027324704224480646285707278634645234095122804559045312923819794776928194098487972764363649361713512731460059740929840789043447155551107435766468071813945331313861835289050624825980714650042186547867057986370794200778277570803957071502251887
e=65537
g=2157382166227048008151606160068683153029902706798753603550075684775242674106840467207794609506075603345430902709796320595040305496549488048759451499003
enc=1706676139782916859705617140716929473350550599143215409850324617375385155893376548401557158261122335220199922229225746433590875391358929714141838314015655361989993985070285957305126847445442699828095001203266978036575956723172054402632901673504599481917025056824986547174258708944098866240451432510310007060414500907941107101001004474036283249456230343043785187819423163986135104740039129111213967847515011092231384245986891933365405336421413444499204268699546739391271911481490278065027465465222639265899471823742196086481403499948301061349936225773314002398442541447810628796808530412232638250097430811300924120316
gamma = 500/(1024*2)
cbits = ceil(nbits * (0.5 - 2 * gamma))

M = (N - 1) // (2 * g)
u = M // (2 * g)
v = M - 2 * g * u
GF = Zmod(N)
x = GF.random_element()
y = x ^ (2 * g)
# c的范围大概与N^(0.5-2*gamma)很接近
c = bsgs(y, y ^ u, (2**(cbits-1), 2**(cbits+1)), operation='*')
#(a, b, bounds, operation='*', identity=None, inverse=None, op=None)
ab = u - c
apb = v + 2 * g * c
P.<x> = ZZ[]
f = x ^ 2 - apb * x + ab
a = f.roots()
if a:
    a, b = a[0][0], a[1][0]
    p = 2 * g * a + 1
    q = 2 * g * b + 1
    assert p * q == N

from Crypto.Util.number import *
print(long_to_bytes(int(pow(enc,inverse(e,(p-1)*(q-1)),N))))
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
33
34
35
36
37
38
39
40
from tqdm import trange
from Crypto.Util.number import *
N=54642322838521966106812419124141939188989640814860878861908076164639367595914512196689546261469345514255441116302800139668437203232194709285409075862419734007902906374266399946334745212375047784704524011282117381662325280446704897787659122983658402386409111680527237824015035597005313191262677046034069311159229487077629209355803968123085023774573470039717820771904932963580385259183454286138826580540970458295849974865118842313357636425032600607639797650353675780470249861726402474026943128529940611865467085977350731870140237435132883515585257875892835970695457915025407153187085139372317622088931196367733198938707
e=65537
g=3040871967959800581351382295274005388082419270793259228509099272494086612979335548205806725469849481228948811909984262857772287453967175931780503026101
enc=16921727990128654940541048454609306049800635968567290885504606585088535877841115259199326146892596740059029032943069902149992954013354005954650241368176166717262074930938187076093385743103257206008984426730319621844540768570052906856372814131242671511736639583796446042340818796492567054682875526286521771179572697525973157614384591867911200189677177846743548750073412797016862500896375745125624115608433787391085807075889515255210830361622016035288935853286037510176320800234097566590023615892000758981191932044064959498134955967145300788171021729870111273798593291304516871631013979858203217888740299565006817016165
h = (N-1)//(2*g)
# print(h)
from gmpy2 import iroot
ab_ = h//(2*g)
# print(ab - a*b)

# print((ab - a*b).bit_length())

# print(2**24-13699487)

# for i in trange(2**24):
#     ab = ab_ - i
#     absum = h - 2*g*ab
#     if absum**2-4*ab < 0:
#         continue
#     abdiff = iroot(absum**2-4*ab, 2)[0]
#     a = (absum + abdiff) // 2
#     b = (absum - abdiff) // 2
#     if a*b == ab:
#         print(a)
#         print(b)
#         break

a = 47937386938884458900370786879118057275877357467300250370371787390211867366084642223134071188443797365024207320451316918915461052607536742271505969247375076726
b = 30817580160697031122119466051933934199293816720246050921169947835585517577173054601468730432823632268542332991565084729244237756343912826384891209074376593659

p = 2*g*a + 1
q = 2*g*b + 1

assert p*q == N
phi = (p-1)*(q-1)
d = pow(65537, -1, phi)
m = pow(enc,d,N)
print(long_to_bytes(m))