2024数信杯半决赛部分复现

字数统计: 1.6k字   |   阅读时长≈ 8分

赛后向学长要的附件和wp，复现一手，算是加深对coppersmith的理解。

512RSA

tag：多轮AMM

task.py

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

def gen():
    e = getPrime(12)
    p = getPrime(512)
    while (p-1) % e != 0:
        e = getPrime(12)
        p = getPrime(512)
    return p, e * getPrime(300)

p1, e1 = gen()
p2, e2 = gen()
p3, e3 = gen()
p4, e4 = gen()

params = [(p1, e1), (p2, e2),(p3, e3),(p4, e4)]
params=sorted(params, key = lambda x : x[0])

m = bytes_to_long(flag)
c = pow(m, e1, p1)
c = pow(c, e2, p2)
c = pow(c, e3, p3)
c = pow(c, e4, p4)

p = [p1, p2, p3, p4]
e = [e1, e2, e3, e4]

print(f"p = {p}")
print(f"e = {e}")
print(f"c = {c}")

'''
p = [9971877305101532548667657113915432686374600625802767915440064066247538969690929504779569308758806158316830036732847609558927989368198515992358962884845999, 9686779713749996013370168873387336643810360139391110278373359707982679675197866831353082822950439414021110597331749608836927764104519058819809287999191277, 11738824822038281341750095913199075446517552586485188261315252543625912278840584386174541563838459902823978442587021089252281373649445095529570370997140353, 8385622786171806844076175753935694055996440456538617120122854340325548660120153189193604171523482203780916677672818268556891995843000386665967836853148101]
e = [3949210634899972905354615323966329995013354120760848313001868527895893105358656676275468825581, 3352586350227882729695194848291019666469497650929882112900986499971706693129836865558906119017, 2538382896284047546927213869533310553533512722671755934207012576147843086855632406951937438613, 5811018619884267813495708620058955656757034290452722071543724890613376672936415477627562597173]
c = 6584399172697878406122485312269951595848044260489518691299790064128553815820157618343563425157360368851091584911872688623840890520680003501265955854989154
'''

解析

e是p-1的一个因子，求$e * getPrime(300)$与$p-1$的最大公因数得到e，再用AMM算法解决

但这里我们遇到的是多轮加密，需要解4次

用AMM算法会产生很多种可能性

实际操作下来有

$2081·2539·2347·3413$种可能性

借助师傅们的文章

文章链接：crypto-AMM算法 - 先知社区 (aliyun.com)

image-20241008202155247

有

那么只有满足这个式子的$c_3$才能进入下一步，经过筛选

每一次的可能性结果降到了个位数。

跟师傅交流后，说

”这题有个非常简单的解法，sagemath 10.x有限域开根秒出结果“

等最近安装arch和sagemath后研究一下

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
# sagemath 9.3
# finish in 1m18.9s 
from Crypto.Util.number import *
import time
import random

# AMM算法得到一个解，About 3 seconds to run
def AMM(o, r, q):
    start = time.time()
    #print('\n----------------------------------------------------------------------------------')
    #print('Start to run Adleman-Manders-Miller Root Extraction Method')
    #print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
    g = GF(q)
    o = g(o)
    p = g(random.randint(1, q))
    while p ^ ((q-1) // r) == 1:
        p = g(random.randint(1, q))
    #print('[+] Find p:{}'.format(p))
    t = 0
    s = q - 1
    while s % r == 0:
        t += 1
        s = s // r
    #print('[+] Find s:{}, t:{}'.format(s, t))
    k = 1
    while (k * s + 1) % r != 0:
        k += 1
    alp = (k * s + 1) // r
    #print('[+] Find alp:{}'.format(alp))
    a = p ^ (r**(t-1) * s)
    b = o ^ (r*alp - 1)
    c = p ^ s
    h = 1
    for i in range(1, t):
        d = b ^ (r^(t-1-i))
        if d == 1:
            j = 0
        else:
            print('[+] Calculating DLP...')
            j = - dicreat_log(a, d)
            print('[+] Finish DLP...')
        b = b * (c^r)^j
        h = h * c^j
        c = c ^ r
    result = o^alp * h
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    #print('Find one solution: {}'.format(result))
    return result

# 找到所有的primitive nth root
def findAllPRoot(p, e):
    #print("Start to find all the Primitive {:#x}th root of 1 modulo {}.".format(e, p))
    start = time.time()
    proot = set()
    while len(proot) < e:
        proot.add(pow(random.randint(2, p-1), (p-1)//e, p))
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return proot

# 得到所有解 
def findAllSolutions(mp, proot, cp, p, e):
    print("Start to find all the {:#x}th root of {} modulo {}.".format(e, cp, p))
    start = time.time()
    all_mp = set()
    for root in proot:
        mp2 = mp * root % p
        #assert pow(mp2, e, p) == cp
        if pow(mp2, e, p) != cp:
            continue
        all_mp.add(mp2)
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return all_mp

def get_c(c, p, e, g):
    e = e // g
    d = inverse_mod(e, p-1)
    c = pow(c, d, p)
    # AMM
    e = g
    assert is_prime(p) == True 
    assert(p % pow(e, 2) % e == 1)
    cp = c % p
    mp = AMM(cp, e, p)
    p_proot = findAllPRoot(p, e)
    mps = findAllSolutions(mp, p_proot, cp, p, e)
    return mps

p = [9971877305101532548667657113915432686374600625802767915440064066247538969690929504779569308758806158316830036732847609558927989368198515992358962884845999, 9686779713749996013370168873387336643810360139391110278373359707982679675197866831353082822950439414021110597331749608836927764104519058819809287999191277, 11738824822038281341750095913199075446517552586485188261315252543625912278840584386174541563838459902823978442587021089252281373649445095529570370997140353, 8385622786171806844076175753935694055996440456538617120122854340325548660120153189193604171523482203780916677672818268556891995843000386665967836853148101]
e = [3949210634899972905354615323966329995013354120760848313001868527895893105358656676275468825581, 3352586350227882729695194848291019666469497650929882112900986499971706693129836865558906119017, 2538382896284047546927213869533310553533512722671755934207012576147843086855632406951937438613, 5811018619884267813495708620058955656757034290452722071543724890613376672936415477627562597173]
c = 6584399172697878406122485312269951595848044260489518691299790064128553815820157618343563425157360368851091584911872688623840890520680003501265955854989154

g = [gcd(p[i]-1, e[i]) for i in range(4)]
print(g)

c_list = [c]
for k in range(3,-1,-1):
    print("第{i}次".format(i=4-k))
    prev_list = []
    for c in c_list:
        prev_c = get_c(c, p[k], e[k], g[k])
        prev_list += prev_c
    prev_list = list(set(prev_list))
    prev_list = list(map(int, set(prev_list)))
    print(f'个数：{len(prev_list)}')
    c_list = []
    if k == 0:
        break
    for m in prev_list:
        if pow(int(m),(p[k-1]-1)//g[k-1],p[k-1]) == 1:
            c_list.append(int(m))

    print(f'筛选后的个数：{len(c_list)}')
for i in prev_list:
    if b'flag' in long_to_bytes(i):
        print("找到答案！")
        print(long_to_bytes(i))
        break

2024

tag：entropy，熵，主动消除+coppersmith p高位泄露

task.py

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


p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 0x10001

flag = open("flag1.txt", "r").readline().strip()
m = bytes_to_long(flag.encode())
c = pow(m, e, n)

entropy = 1
for _ in range(10):
    entropy *= random.randint(1, 2024)
hint = 2024 * (p+entropy) + 4202 * (q-entropy)

with open("flag1.enc", "w") as f:
    f.write(f"n: {n}\n")
    f.write(f"e: {e}\n")
    f.write(f"c: {c}\n")
    f.write(f"hint: {hint}\n")

另一个附件链接

1
2
通过网盘分享的文件：flag1.enc
链接: https://pan.baidu.com/s/1J6yosAEgzWkBZagwNmv5YA?pwd=g2h7 提取码: g2h7

解析

没看wp之前，因为测试过entropy最大范围在112位左右，想把hint的低112抹去减少entropy的影响，然后求p+q与n的方程式，得到高位p，最后coppersmith解p，但是没解出来（脚本如下）

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
# 想用抹去低位来消除entropy的影响，但没出
hint = hint>>112<<112
def get_full_p2(ph, n):
    PR.<x> = PolynomialRing(Zmod(n))
    nbits = n.nbits()
    phbits = ph.nbits()
    f = x + ph
    f = f.monic()
    roots = f.small_roots(X=2^112, beta=0.4)
    if roots != []:
        x = roots[0]
        p = gmpy2.gcd(int(x + ph), int(n))
        return int(p)

def find_p2_low(h, n):
    X = var('X')
    results = solve_mod([4202*n==X*(h - 2024*X)],2^h.nbits())
    for x in results:
        ph = ZZ(x[0])
        p = get_full_p2(ph, n)
        if p and p != 1 and p != n:
            return int(p)
        
p = find_p2_low(hint, n)
print(p) # None
1
初步鉴定solve_mod与roots求根的区别，没有mod，只是多项式，不是同余式

这里有未知数entropy来干扰我们通过hint获得p和q，经过测试entropy最大为110位（2^110）,跟1024位的p相比算小，通过这个式子

两边同时乘上p得到

因为我们不知道entropy的值，那么忽略它会造成影响的位数（舍去121位以下）

举个例子

1
2
3
4
5
 p = 0b1001001
 a = 0b0000011
hint = a + p

ph = 0b1001xxx  # 这里我们就忽略a的影响，第3位以上还是精确的

在这里，我们可以把small_roots()的参数尽量调高一些，$2178·entropy$理论最大值121位以上

解这个式子得到p的精确高位

再用coppersmith求值得到p

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
# sagemath 9.3
from Crypto.Util.number import *    
import gmpy2
from tqdm import trange
hint = 
n = 
c = 
e = 

RF = RealField(2048)
x = polygen(RF)
f = x*(hint - 2024*x) - 4202*n
high_p = int(f.roots()[0][0])

R.<x> = PolynomialRing(Zmod(n), implementation='NTL')  
f = high_p + x
f = f.monic()
x0 = f.small_roots(X = 2^121, beta = 0.4)[0] 
p = int(f(x0))
print(p)
p = int(p)
q = n//p
assert(p*q==n)
phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)
print(long_to_bytes(int(m)).decode())
主要涉及技术：
Crypto、Web
一位23级大学牲

联系QQ:2146983392

欢迎@我，交流闲聊，交换友链

技术只学到一些皮毛
谢谢师傅们的关照