ycdxsb CTF / crypto8 分钟 读完 (大约 1264 个字)  0次访问

Bypass Miller Rabin Test

在一道密码学题目中碰到的问题，需要绕过Miller-Rabin素性测试，稍微记录一下

题目要求在2**600到2**900范围内找到一个数，这个数不是质数，但可以通过Miller-Rabin素性测试

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
def generate_basis(n):
    basis = [True] * n
    for i in range(3, int(n**0.5)+1, 2):
        if basis[i]:
            basis[i*i::2*i] = [False]*((n-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3, n, 2) if basis[i]]


def miller_rabin(n, b):
    """
    Miller Rabin test testing over all
    prime basis < b
    """
    basis = generate_basis(b)
    if n == 2 or n == 3:
        return True

    if n % 2 == 0:
        return False

    r, s = 0, n - 1
    while s % 2 == 0:
        r += 1
        s //= 2
    for b in basis:
        x = pow(b, s, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True
  
miller_rabin(p,64)

从虽然从参考资料中的论文给出了一些示例，但都不符合题目的限制，不过好在参考资料的appendix A里给了十分完整的示例，可以对着复现和验证

假设我们的伪素数$n = p_1 p_2…p_h$，其中$p_i$是不同的素数，使得$n$是基${a_1,a_2…a_t}$下的伪素数，在本文中，$h=3$

论文中的方法是先找到一个$p_1$，然后生成$p_i = k_i(p_i-1)+1$，最后合成伪素数$n$

找$p_1$的步骤如下

Step1：求Sa#

image-20201009203311692

显然对于miller_rabin(p,64)而言，我们的A为64以下的所有质数，求A如下

1
2
3
4
5
6
7
8
9
10
def generate_basis(n):
    basis = [True] * n
    for i in range(3, int(n**0.5)+1, 2):
        if basis[i]:
            basis[i*i::2*i] = [False]*((n-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3, n, 2) if basis[i]]

A = generate_basis(64)
print('A:', A)
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61]

而我们要求的Sa集合，它要求，对于每个基a，在3~(4*a-1)范围内所有与a的Jacobi结果为-1的数字的集合，如下

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
Sa = {}
print("Sa: ")
for a in A:
    Sa[a] = []
    for _ in range(3, 4*a-1, 2):
        if libnum.jacobi(a, _) == -1:
            Sa[a].append(_)
    print(a, Sa[a])
'''
Sa:
2 [3, 5]
3 [5, 7]
5 [3, 7, 13, 17]
7 [5, 11, 13, 15, 17, 23]
11 [3, 13, 15, 17, 21, 23, 27, 29, 31, 41]
13 [5, 7, 11, 15, 19, 21, 31, 33, 37, 41, 45, 47]
17 [3, 5, 7, 11, 23, 27, 29, 31, 37, 39, 41, 45, 57, 61, 63, 65]
19 [7, 11, 13, 21, 23, 29, 33, 35, 37, 39, 41, 43, 47, 53, 55, 63, 65, 69]
23 [3, 5, 17, 21, 27, 31, 33, 35, 37, 39, 45, 47, 53, 55, 57, 59, 61, 65, 71, 75, 87, 89]
29 [3, 11, 15, 17, 19, 21, 27, 31, 37, 39, 41, 43, 47, 55, 61, 69, 73, 75, 77, 79, 85, 89, 95, 97, 99, 101, 105, 113]
31 [7, 13, 17, 19, 21, 29, 35, 37, 39, 47, 51, 53, 57, 59, 61, 63, 65, 67, 71, 73, 77, 85, 87, 89, 95, 103, 105, 107, 111, 117]
37 [5, 13, 15, 17, 19, 23, 29, 31, 35, 39, 43, 45, 51, 55, 57, 59, 61, 69, 79, 87, 89, 91, 93, 97, 103, 105, 109, 113, 117, 119, 125, 129, 131, 133, 135, 143]
41 [3, 7, 11, 13, 15, 17, 19, 27, 29, 35, 47, 53, 55, 63, 65, 67, 69, 71, 75, 79, 85, 89, 93, 95, 97, 99, 101, 109, 111, 117, 129, 135, 137, 145, 147, 149, 151, 153, 157, 161]
43 [5, 11, 15, 23, 29, 31, 33, 35, 37, 45, 47, 59, 61, 65, 67, 69, 73, 77, 79, 83, 85, 87, 89, 93, 95, 99, 103, 105, 107, 111, 113, 125, 127, 135, 137, 139, 141, 143, 149, 157, 161, 167]
47 [3, 5, 7, 13, 27, 29, 33, 41, 45, 51, 55, 57, 59, 63, 69, 71, 73, 75, 77, 79, 83, 85, 93, 95, 103, 105, 109, 111, 113, 115, 117, 119, 125, 129, 131, 133, 137, 143, 147, 155, 159, 161, 175, 181, 183, 185]
53 [3, 5, 19, 21, 23, 27, 31, 33, 35, 39, 41, 45, 51, 55, 61, 65, 67, 71, 73, 75, 79, 83, 85, 87, 101, 103, 109, 111, 125, 127, 129, 133, 137, 139, 141, 145, 147, 151, 157, 161, 167, 171, 173, 177, 179, 181, 185, 189, 191, 193, 207, 209]
59 [3, 7, 13, 15, 19, 27, 33, 35, 37, 51, 61, 63, 65, 69, 71, 73, 75, 77, 79, 87, 89, 93, 95, 97, 101, 107, 109, 113, 117, 119, 123, 127, 129, 135, 139, 141, 143, 147, 149, 157, 159, 161, 163, 165, 167, 171, 173, 175, 185, 199, 201, 203, 209, 217, 221, 223, 229, 233]
61 [7, 11, 17, 21, 23, 29, 31, 33, 35, 37, 43, 51, 53, 55, 59, 63, 67, 69, 71, 79, 85, 87, 89, 91, 93, 99, 101, 105, 111, 115, 129, 133, 139, 143, 145, 151, 153, 155, 157, 159, 165, 173, 175, 177, 181, 185, 189, 191, 193, 201, 207, 209, 211, 213, 215, 221, 223, 227, 233, 237]
'''

Step2：求Sb#

image-20201009204918929

在求Sb前，我们需要先指定$k_i$的值(只要是质数就行)，这里我们指定$k_2 = 701、k_3 = 257$

我们可以看到Sb其实就是取了一个$k_i^{-1}(Sa+k_i-1)$的交集

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
print("Sb:")
Sb = {}
for a in A:
    result = []
    for b in Sa[a]:
        if((k2*(b-1)+1) % (4*a) in Sa[a] and (k3*(b-1)+1) % (4*a) in Sa[a]):
            result.append(b)
        Sb[a]=result
    print(a,Sb[a])
'''
Sb:
2 [3, 5]
3 [7]
5 [7, 17]
7 [11, 13, 15]
11 [17, 23, 41]
13 [21, 47]
17 [29, 63]
19 [29, 39, 47, 55]
23 [5, 31, 47, 59, 61]
29 [21, 41, 55, 79, 99, 113]
31 [17, 19, 37, 39, 63, 95]
37 [13, 17, 19, 23, 29, 31, 45, 61, 69, 87, 91, 93, 97, 103, 105, 119, 135, 143]
41 [17, 35, 63, 67, 69, 99, 117, 145, 149, 151]
43 [31, 33, 35, 37, 47, 61, 85, 87, 89, 105, 143]
47 [41, 45, 59, 69, 71, 79, 95, 103, 147, 161, 181]
53 [27, 61, 65, 67, 75, 83, 85, 87, 133, 167, 171, 173, 181, 189, 191, 193]
59 [33, 51, 69, 79, 95, 97, 113, 119, 127, 141, 157, 159, 165, 185]
61 [7, 17, 23, 55, 59, 69, 105, 111, 129, 139, 145, 177, 181, 191, 227, 233]
'''

Step3 ：CRT求p1#

image-20201009205950893

最后从每个基的Sb​集合中选择一个，进行CRT求出p1

由于是随机选取，所以CRT未必满足条件，因此要多次random选出能成功CRT的序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
p1 = - inverse(k3, k2) % k2
p2 = - inverse(k2, k3) % k3
print(p1, p2)
print(isPrime(k2), isPrime(k3))
for i in range(0, 100000):
    try:
        crt_A = []
        crt_B = []
        for a in A:
            crt_A.append(random.choice(Sb[a]))
            crt_B.append(4*a)
        crt_A.append(p1)
        crt_A.append(p2)
        crt_B.append(k2)
        crt_B.append(k3)
        print(crt(crt_A, crt_B))
        print(crt_A)
        print(crt_B)
        break
    except:
        continue

p1 = crt(crt_A, crt_B)

然后求一下p1的模数，根据$p_i = k_i(p_1-1)+1$求出其余的数，稍微调整一下大小到600bits-900bits之间即可

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
d = {}
for n in crt_B:
    k = factorize(n)
    for key in k.keys():
        if(key in d.keys()):
            if(d[key] < k[key]):
                d[key] = k[key]
        else:
            d[key] = k[key]
mod_number = 1
for key in d.keys():
    mod_number *= pow(key, d[key])
print('mod:', mod_number)
for _ in range(100000):
    if(_ % 10000 == 0):
        print(_)
    p1 = p1+mod_number*_*pow(2,100)
    p2 = k2*(p1-1)+1
    p3 = k3*(p1-1)+1
    if(isPrime(p1) and isPrime(p2) and isPrime(p3)):
        n = p1*p2*p3
        if(miller_rabin(n, 64)):
            print(p1, p2, p3)
            print(n)
            print(miller_rabin(n, 64))
            break

完整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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
# https://eprint.iacr.org/2018/749.pdf
import libnum
from libnum.factorize import factorize
from sage.all import *
import random
from Crypto.Util.number import inverse, isPrime

def generate_basis(n):
    basis = [True] * n
    for i in range(3, int(n**0.5)+1, 2):
        if basis[i]:
            basis[i*i::2*i] = [False]*((n-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3, n, 2) if basis[i]]


def miller_rabin(n, b):
    """
    Miller Rabin test testing over all
    prime basis < b
    """
    basis = generate_basis(b)
    if n == 2 or n == 3:
        return True

    if n % 2 == 0:
        return False

    r, s = 0, n - 1
    while s % 2 == 0:
        r += 1
        s //= 2
    for b in basis:
        x = pow(b, s, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True


A = generate_basis(64)
print('A:', A)
Sa = {}
print("Sa: ")
for a in A:
    Sa[a] = []
    for _ in range(3, 4*a-1, 2):
        if libnum.jacobi(a, _) == -1:
            Sa[a].append(_)
    print(a, Sa[a])

k2 = 701
k3 = 257

print("Sb:")
Sb = {}
for a in A:
    result = []
    for b in Sa[a]:
        if((k2*(b-1)+1) % (4*a) in Sa[a] and (k3*(b-1)+1) % (4*a) in Sa[a]):
            result.append(b)
        Sb[a]=result
    print(a,Sb[a])
p1 = - inverse(k3, k2) % k2
p2 = - inverse(k2, k3) % k3
print(p1, p2)
print(isPrime(k2), isPrime(k3))
for i in range(0, 100000):
    try:
        crt_A = []
        crt_B = []
        for a in A:
            crt_A.append(random.choice(Sb[a]))
            crt_B.append(4*a)
        crt_A.append(p1)
        crt_A.append(p2)
        crt_B.append(k2)
        crt_B.append(k3)
        print(crt(crt_A, crt_B))
        print(crt_A)
        print(crt_B)
        break
    except:
        continue

p1 = crt(crt_A, crt_B)
d = {}
for n in crt_B:
    k = factorize(n)
    for key in k.keys():
        if(key in d.keys()):
            if(d[key] < k[key]):
                d[key] = k[key]
        else:
            d[key] = k[key]
mod_number = 1
for key in d.keys():
    mod_number *= pow(key, d[key])
print('mod:', mod_number)
for _ in range(100000):
    if(_ % 10000 == 0):
        print(_)
    p1 = p1+mod_number*_*pow(2,100)
    p2 = k2*(p1-1)+1
    p3 = k3*(p1-1)+1
    if(isPrime(p1) and isPrime(p2) and isPrime(p3)):
        n = p1*p2*p3
        if(miller_rabin(n, 64)):
            print(p1, p2, p3)
            print(n)
            print(miller_rabin(n, 64))
            break

'''
A: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61]
Sa:
2 [3, 5]
3 [5, 7]
5 [3, 7, 13, 17]
7 [5, 11, 13, 15, 17, 23]
11 [3, 13, 15, 17, 21, 23, 27, 29, 31, 41]
13 [5, 7, 11, 15, 19, 21, 31, 33, 37, 41, 45, 47]
17 [3, 5, 7, 11, 23, 27, 29, 31, 37, 39, 41, 45, 57, 61, 63, 65]
19 [7, 11, 13, 21, 23, 29, 33, 35, 37, 39, 41, 43, 47, 53, 55, 63, 65, 69]
23 [3, 5, 17, 21, 27, 31, 33, 35, 37, 39, 45, 47, 53, 55, 57, 59, 61, 65, 71, 75, 87, 89]
29 [3, 11, 15, 17, 19, 21, 27, 31, 37, 39, 41, 43, 47, 55, 61, 69, 73, 75, 77, 79, 85, 89, 95, 97, 99, 101, 105, 113]
31 [7, 13, 17, 19, 21, 29, 35, 37, 39, 47, 51, 53, 57, 59, 61, 63, 65, 67, 71, 73, 77, 85, 87, 89, 95, 103, 105, 107, 111, 117]
37 [5, 13, 15, 17, 19, 23, 29, 31, 35, 39, 43, 45, 51, 55, 57, 59, 61, 69, 79, 87, 89, 91, 93, 97, 103, 105, 109, 113, 117, 119, 125, 129, 131, 133, 135, 143]
41 [3, 7, 11, 13, 15, 17, 19, 27, 29, 35, 47, 53, 55, 63, 65, 67, 69, 71, 75, 79, 85, 89, 93, 95, 97, 99, 101, 109, 111, 117, 129, 135, 137, 145, 147, 149, 151, 153, 157, 161]
43 [5, 11, 15, 23, 29, 31, 33, 35, 37, 45, 47, 59, 61, 65, 67, 69, 73, 77, 79, 83, 85, 87, 89, 93, 95, 99, 103, 105, 107, 111, 113, 125, 127, 135, 137, 139, 141, 143, 149, 157, 161, 167]
47 [3, 5, 7, 13, 27, 29, 33, 41, 45, 51, 55, 57, 59, 63, 69, 71, 73, 75, 77, 79, 83, 85, 93, 95, 103, 105, 109, 111, 113, 115, 117, 119, 125, 129, 131, 133, 137, 143, 147, 155, 159, 161, 175, 181, 183, 185]
53 [3, 5, 19, 21, 23, 27, 31, 33, 35, 39, 41, 45, 51, 55, 61, 65, 67, 71, 73, 75, 79, 83, 85, 87, 101, 103, 109, 111, 125, 127, 129, 133, 137, 139, 141, 145, 147, 151, 157, 161, 167, 171, 173, 177, 179, 181, 185, 189, 191, 193, 207, 209]
59 [3, 7, 13, 15, 19, 27, 33, 35, 37, 51, 61, 63, 65, 69, 71, 73, 75, 77, 79, 87, 89, 93, 95, 97, 101, 107, 109, 113, 117, 119, 123, 127, 129, 135, 139, 141, 143, 147, 149, 157, 159, 161, 163, 165, 167, 171, 173, 175, 185, 199, 201, 203, 209, 217, 221, 223, 229, 233]
61 [7, 11, 17, 21, 23, 29, 31, 33, 35, 37, 43, 51, 53, 55, 59, 63, 67, 69, 71, 79, 85, 87, 89, 91, 93, 99, 101, 105, 111, 115, 129, 133, 139, 143, 145, 151, 153, 155, 157, 159, 165, 173, 175, 177, 181, 185, 189, 191, 193, 201, 207, 209, 211, 213, 215, 221, 223, 227, 233, 237]
Sb:
2 [3, 5]
3 [7]
5 [7, 17]
7 [11, 13, 15]
11 [17, 23, 41]
13 [21, 47]
17 [29, 63]
19 [29, 39, 47, 55]
23 [5, 31, 47, 59, 61]
29 [21, 41, 55, 79, 99, 113]
31 [17, 19, 37, 39, 63, 95]
37 [13, 17, 19, 23, 29, 31, 45, 61, 69, 87, 91, 93, 97, 103, 105, 119, 135, 143]
41 [17, 35, 63, 67, 69, 99, 117, 145, 149, 151]
43 [31, 33, 35, 37, 47, 61, 85, 87, 89, 105, 143]
47 [41, 45, 59, 69, 71, 79, 95, 103, 147, 161, 181]
53 [27, 61, 65, 67, 75, 83, 85, 87, 133, 167, 171, 173, 181, 189, 191, 193]
59 [33, 51, 69, 79, 95, 97, 113, 119, 127, 141, 157, 159, 165, 185]
61 [7, 17, 23, 55, 59, 69, 105, 111, 129, 139, 145, 177, 181, 191, 227, 233]
30 246
1 1
61933256682223994457337248907
[3, 7, 7, 11, 23, 47, 63, 39, 31, 79, 39, 103, 151, 31, 59, 87, 127, 111, 30, 246]
[8, 12, 20, 28, 44, 52, 68, 76, 92, 116, 124, 148, 164, 172, 188, 212, 236, 244, 701, 257]
mod: 84521291682266726685731893560
0
434373326067214608775878317645775351280862168574601991542247144587 304495701573117440751890700669688521247884380170795996071115248354787 111633944799274154455400727634964265279181577323672711826357516158603
14765242572717201537350357000818561932573315288396435774266341361498670863676541981221739664014401028330587564384701242669740856196369695370339038363927740181650866851457768843113763288312682772243647307
True
'''

参考资料#

#

喜欢这篇文章？打赏一下作者吧

评论

关注我

链接

归档

订阅更新

邮件订阅，更新早知道

分类

最新文章

标签

AI2
CTF48
CVE4
Fuzz1
FuzzingBook1
HEVD5
NLP1
PyQt512
ROP Emporium2
Toddler's Bottle21
Web1
automatic analyse10
binary analyse1
codeql5
crypto7
fuzz3
life2
linux kernel2
machine learning1
mobile security1
others1
paper18
pentest3
pwn24
pwnable.kr21
re5
research20
security18
security situation awareness2
stack overflow3
tools2
windows8
work1
writeup5
数据库11
×