抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

Common Prime RSA

crypto日常学习

发布于：2024年12月23日

次浏览

这种类型的话，一般有

p=2∗g∗a+1q=2∗g∗b+1h=2∗g∗a∗b+a+bn=2∗g∗h+1\begin{array}{l} p=2*g*a + 1\\ q=2*g*b+1\\ h=2*g*a*b+a+b\\ n=2*g*h+1\\ \end{array}

也就是有

n=2∗g∗(2∗g∗a∗b+a+b)+1n=4∗g2∗a∗b+2∗g∗a+2∗g∗b+1\begin{array}{l} n=2*g*(2*g*a*b+a+b) + 1\\ n=4*g^2*a*b+2*g*a+2*g*b+1 \end{array}

一般的生成算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
try:
    gcd
except NameError:
    from math import gcd

def gen_prime(nbits: int, gamma: float):
    g = getPrime(int(nbits * gamma))
    alpha = 0.5 - gamma
    while True:
        a = getRandomNBitInteger(int(alpha * nbits))
        p = 2 * g * a + 1
        if isPrime(p):
            b = getRandomNBitInteger(int(alpha * nbits))
            q = 2 * g * b + 1
            h = 2 * g * a * b + a + b
            while not isPrime(q) or isPrime(h) or gcd(a, b) != 1:
                b = getRandomNBitInteger(int(alpha * nbits))
                h = 2 * g * a * b + a + b
                q = 2 * g * b + 1
            return p, q
print(gen_prime(512, 0.48))

这边的0.48就是γ\gamma

对于不同的情况，有不同的解决方法

当γ\gamma的值接近12\frac{1}{2}的时候

这时候是可以被快速分解的，对应的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
from Crypto.Util.number import *
from gmpy2 import invert

f = lambda x,n: (pow(x, n - 1, n) + 3) % n
def phllard_rho(n):
    i = 1
    while True:
        a = getRandomRange(2, n)
        b = f(a, n)
        j = 1
        while True:
            p = GCD(abs(a - b), n)
            if p == n:
                break
            elif p > 1:
                return (p, n // p)
            else:
                a = f(a, n)
                b = f(f(b, n), n)
            j += 1
        i += 1

n = 
p,q = phllard_rho(n)
print(p)
print(q)

比如下面这道题

加密代码：

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

def gen_prime(nbits, gamma):
    g = getPrime(int(nbits * gamma))  #491
    alpha = 0.5 - gamma  #0.02
    while True:
        a = getRandomNBitInteger(int(alpha * nbits))  #20
        p = 2 * g * a + 1
        if isPrime(p):
            b = getRandomNBitInteger(int(alpha * nbits))  #20
            q = 2 * g * b + 1
            h = 2 * g * a * b + a + b
            while not isPrime(q) or isPrime(h) or gmpy2.gcd(a, b) != 1:
                b = getRandomNBitInteger(int(alpha * nbits))
                q = 2 * g * b + 1
            return p, q

def encrypt(nbits, gamma):
    p, q = gen_prime(nbits, gamma)
    n = p * q
    e = getPrime(16)
    while gmpy2.gcd(e, gmpy2.lcm(p-1,q-1)) != 1:
        e = getPrime(16)
    m = bytes_to_long(flag)
    c = pow(m, e, n)
    return n, e, c

n, e, c = encrypt(1024, 0.48)
print 'n =', n
print 'e =', e
print 'c =', c

# n = 84236796025318186855187782611491334781897277899439717384242559751095347166978304126358295609924321812851255222430530001043539925782811895605398187299748256080526691975084042025794113521587064616352833904856626744098904922117855866813505228134381046907659080078950018430266048447119221001098505107823645953039
# e = 58337
# c = 13646200911032594651110040891135783560995665642049282201695300382255436792102048169200570930229947213493204600006876822744757042959653203573780257603577712302687497959686258542388622714078571068849217323703865310256200818493894194213812410547780002879351619924848073893321472704218227047519748394961963394668

很明显这边的γ\gamma是接近12\frac{1}{2}​，可以直接尝试分解

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

f = lambda x,n: (pow(x, n - 1, n) + 3) % n
def phllard_rho(n):
    i = 1
    while True:
        a = getRandomRange(2, n)
        b = f(a, n)
        j = 1
        while True:
            p = GCD(abs(a - b), n)
            if p == n:
                break
            elif p > 1:
                return (p, n // p)
            else:
                a = f(a, n)
                b = f(f(b, n), n)
            j += 1
        i += 1

n = 84236796025318186855187782611491334781897277899439717384242559751095347166978304126358295609924321812851255222430530001043539925782811895605398187299748256080526691975084042025794113521587064616352833904856626744098904922117855866813505228134381046907659080078950018430266048447119221001098505107823645953039
p,q = phllard_rho(n)
print(p) #9983140483800634632426126985832058062766650402234684899412786169759602188949733747138853010482968306554808689182393249326088351886439191015684338347893201
print(q) #8437905502983445042677582637893534375137565614989838462475696727313788501904161403475771835934720130340799646782932619714906025013322551788559197469878239

当的γ\gamma值很小的时候

一般在0.10左右，可以尝试使用yafu分解N−12\frac{N-1}{2}，或者使用上面的板子

已知a、b的值

这时候关于n的等式就只有g一个未知量，直接roots来解就可以了

1
2
3
4
5
6
7
8
9
10
11
12
a = 
b = 
N = 
P.<g> = ZZ[]   #因为这边我们只需要整数解，所以限制在整数环上面就行了
f = 4 * a * b * g ^ 2 + 2 * (a + b) * g - N + 1
g = f.roots()
if g:
    g = g[0][0]
    p = 2 * g * a + 1
    q = 2 * g * b + 1
    print(g)
    assert p * q == N

已知g的值

这时候就要继续分情况讨论了

当g=a+bg=a+b​的时候

这时候可能会想到使用resultant结式联立n和g的等式消去一个未知量，然后直接root解，但是实测的话在模N下是解不出来的，所以这边还是只能我们自己动手去推导

想偷懒一下都不行吗o(￣ヘ￣o＃)

哦，不对，还是可以偷懒的，定义在整环ZZ下就可以了

1
2
3
4
5
6
7
8
9
10
11
from sage.matrix.matrix2 import Matrix

def resultant(f1, f2, var):
    return Matrix.determinant(f1.sylvester_matrix(f2, var))

R.<a, b, g, N> = ZZ[] 

f1 = a + b - g
f2 = 4 * g ^ 2 * a * b + 2 * g * a + 2 * g * b + 1 - N
f = resultant(f1, f2, b)
f  #-4*a^2*g^2 + 4*a*g^3 + 2*g^2 - N + 1

然后这个然后是在模N下是解不出来的，但是毕竟只有一个变量，我们直接在ZZ下解就行了

1
2
3
4
5
6
7
8
9
10
11

g = 
N = 
R.<a> = ZZ[] 
f = -4*a^2*g^2 + 4*a*g^3 + 2*g^2 - N + 1
res = f.roots()
if res:
    a, b = res[0][0], res[1][0]
    p = 2 * g * a + 1
    q = 2 * g * b + 1
    assert p * q == N

好了，又是一个偷鸡小技巧（这是可以说的吗(o゜▽゜)o☆）

当g>a+bg\gt a+b​的时候

因为有

n=4∗g2∗a∗b+2∗g∗a+2∗g∗b+1n=4*g^2*a*b+2*g*a+2*g*b+1

那么就有

n−12g=2∗g∗a∗b+a+b\frac{n-1}{2g}=2*g*a*b+a+b

因为g>a+bg\gt a+b，所以

n−12g=a+b (mod g)\frac{n-1}{2g}=a+b\ (mod\ g)

这时候的a+ba+b并不会有损失，这时候就是有两个等式了

f1=a+bf2=4∗g2∗a∗b+2∗g∗a+2∗g∗b+1−n\begin{array}{l} f1=a+b\\ f2=4*g^2*a*b+2*g*a+2*g*b+1-n \end{array}

同样的resultant消元，然后放到ZZ下来解即可

1
2
3
4
5
6
7
8
9
10
11
from sage.matrix.matrix2 import Matrix

def resultant(f1, f2, var):
    return Matrix.determinant(f1.sylvester_matrix(f2, var))

R.<a, b, g, N, a_b> = ZZ[] 

f1 = a + b - a_b
f2 = 4 * g ^ 2 * a * b + 2 * g * a + 2 * g * b + 1 - N
f = resultant(f1, f2, b)
f #-4*a^2*g^2 + 4*a*g^2*a_b + 2*g*a_b - N + 1
1
2
3
4
5
6
7
8
9
10
11
12

g = 
N = 
a_b = (N-1) // 2 * g % g
R.<a> = ZZ[] 
f = -4*a^2*g^2 + 4*a*g^2*a_b + 2*g*a_b - N + 1
res = f.roots()
if res:
    a, b = res[0][0], res[1][0]
    p = 2 * g * a + 1
    q = 2 * g * b + 1
    assert p * q == N
当g<a+bg\lt a+b的时候

更改如下的脚本即可，原理等后面有空具体研究一下，这边先放个板子

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
from sage.groups.generic import bsgs

N=
e=
g=

nbits = int(N).bit_length()
gamma = 500/nbits   #这边的500对应g的比特位数
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

但是这个板子要求很严格需要满足γ\gamma接近14\frac{1}{4}，但是又不会相等

如下面这道例题：

加密代码：

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
#encoding:utf-8
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 product(self):
		self.show()

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


RSAEncryptor()
'''
N=26005937557411457773415104712687923981958755473506446663774354743446702887557393848515957310055343031127074388584187739151750523461366718355001995395113884068006630821692993063059549799441333418271253093941588741870878785667152341074932343265084080139221714990314995739280763137797280758506338351720888316917601527463221950775802676869588615999400620834056236313070088726529781646541497548614202898587851359593285898060344866484564367904750568908201545891253232303978570139348974091301774444701610137908047244074909242353098017743632877219044720807811092641512633223203140867206728757485578721117491783151523429194419
e=65537
g=2446839601304155895653963400578736293320638961351117859255440735801540879759272109341822530346649969440187735574065108743968558847316987473244750100027
'''

这边目的只在于分解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
from sage.groups.generic import bsgs

N=26005937557411457773415104712687923981958755473506446663774354743446702887557393848515957310055343031127074388584187739151750523461366718355001995395113884068006630821692993063059549799441333418271253093941588741870878785667152341074932343265084080139221714990314995739280763137797280758506338351720888316917601527463221950775802676869588615999400620834056236313070088726529781646541497548614202898587851359593285898060344866484564367904750568908201545891253232303978570139348974091301774444701610137908047244074909242353098017743632877219044720807811092641512633223203140867206728757485578721117491783151523429194419
e=65537
g=2446839601304155895653963400578736293320638961351117859255440735801540879759272109341822530346649969440187735574065108743968558847316987473244750100027

nbits = int(N).bit_length()
gamma = 500/nbits   #这边的500对应g的比特位数
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

但是对于这种类型的话，如果g和a和b位数比较相近的话，是可以爆破的

思路如下：

因为是有

n−12g=2∗g∗a∗b+a+b\frac{n-1}{2g}=2*g*a*b+a+b

然后这边的g是500比特，a和b都是523比特左右，那么我们对等式两边再除以2g，得到

n−14g2=a∗b+δ\frac{n-1}{4g^2}=a*b+\delta

其中这边的δ\delta为误差值，数量级应该最多在23或者24比特左右，还是可以爆破的，那么我们只要爆破到2242^{24}，直到找到真正的a*b的值就行了，进而得到

a+b=n−14g2−2∗g∗a∗ba+b=\frac{n-1}{4g^2}-2*g*a*b

两个方程，两个未知量，直接解就行了

不过这边有个要注意的点，直接用solve函数，效率肯定不会高，所以这边还得动手推一下

t1=a+bt2=a∗b\begin{array}{l} t_1=a+b\\ t_2=a*b\\ \end{array}

很容易得到

b2−t1∗b+t2=0b^2-t_1*b+t_2=0

只要判断判别式Δ\Delta能不能开方就行了

Δ=t12−4∗t2\Delta = t_1^2-4*t_2

然后就可以得到b，进而得到a

b=t1±Δ2a=t1−b\begin{array}{l} b = \frac{t_1 \pm \sqrt{\Delta}}{2}\\ a=t_1-b \end{array}

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
from tqdm import trange
from gmpy2 import iroot

N=26005937557411457773415104712687923981958755473506446663774354743446702887557393848515957310055343031127074388584187739151750523461366718355001995395113884068006630821692993063059549799441333418271253093941588741870878785667152341074932343265084080139221714990314995739280763137797280758506338351720888316917601527463221950775802676869588615999400620834056236313070088726529781646541497548614202898587851359593285898060344866484564367904750568908201545891253232303978570139348974091301774444701610137908047244074909242353098017743632877219044720807811092641512633223203140867206728757485578721117491783151523429194419
e=65537
g=2446839601304155895653963400578736293320638961351117859255440735801540879759272109341822530346649969440187735574065108743968558847316987473244750100027



tmp = (N - 1) // (4 * g ** 2)
for delta in trange(2**24):  #13604329
    t2 = tmp - delta
    t1 = (N - 1) // (2 * g) - 2 * g * t2
    try:
        if iroot(int(t1 ** 2 - 4 * t2), 2)[1]:
            b1 = t1 + iroot(int(t1 ** 2 - 4 * t2), 2)[0]
            b2 = t1 - iroot(int(t1 ** 2 - 4 * t2), 2)[0]
            print(b1)
            print(b2)
            break
    except:
        continue
'''
75984990255105522277123737447899034732298722659016072338588517286955101351071497204465517515847485307456282331331753980137107903253530287573382849205838913290
57165459894716665666278225910252233185844239496347476646744474610426233681395911567316282808980366661042221085902846190715030622879238507132547836265709386324
'''

Mumtaz-Luo攻击

最后还有一种Mumtaz-Luo攻击，等我找到对应的例题再来写写

参考：https://hasegawaazusa.github.io/common-prime-rsa.html#已知-g

更新于：2024年12月23日

评论

评论区