W'Blog

Wbuildings的自勉小屋

0%

湖南省网络攻防邀请赛初赛复现

发表于 分类于 Valine：
本文字数： 6.1k 阅读时长 ≈ 6 分钟

发表的晚了点

复现的晚了点，下次跟上

Babystream

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
from Crypto.Util.number import *
import gmpy2
def get_params():
    while True:
        a,b = [getPrime(128) for _ in range(2)]
        a,b = [bin(i)[2:].zfill(128) for i in [a,b]]
        p = int((a + b),2)
        q = int((b + a),2)
        if isPrime(p) and isPrime(q):
            a, b = int(a, 2), int(b, 2)
            return p,q,a,b

flag = b'flag{*****}'
m = bytes_to_long(flag)
p,q,a,b = get_params()
if p > q:
    p,q = q,p
n = p * q
stream = [q]
for i in range(114):
    num = (a * stream[-1] + b) % p
    stream.append(num)
e = gmpy2.next_prime(stream[1] * stream[14] + stream[51] * stream[4])
c = pow(m,e,n)
print(f'n = {n}')
print(f'c = {c}')
# n = 10787879094547634536418400489544495490920545668797140045606047169206620885051312335135831508173231222095307914925085736895140618767731141232201839054986089
# c = 6231259964139423317420399259419242000626426110518752018384660416595264962435087677191600419542766152613241809444876652160722765670645883113456355844854019# 256205479281287561054456695429182604991

提示是观察 n的生成

那我们就看看：

方法一：

所以 n 的高128位为 ab 的高位，n的低128位为 ab 的低位，即可得 ab 的乘积（有进位影响）

在线网站分解一下得 a，b ， 需要注意一下a，b两个数的取值

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
import libnum
import gmpy2

c = 6231259964139423317420399259419242000626426110518752018384660416595264962435087677191600419542766152613241809444876652160722765670645883113456355844854019# 256205479281287561054456695429182604991
n = 10787879094547634536418400489544495490920545668797140045606047169206620885051312335135831508173231222095307914925085736895140618767731141232201839054986089

ab_high = bin(n)[2:130]
ab_low = bin(n)[-128:]

ab = (int(str(ab_high),2)-2)*2**128+int(str(ab_low),2) #  -2 自己调试得出
# print(ab)
# 在线分解一下 ab
b = 281016216346353051804623567458939631077
a = 331532263240160487350391899818281252661

p = a*2**128+b
q = b*2**128+a

if p > q:
    p,q = q,p
n = p * q
stream = [q]
# print(stream)

for i in range(114):
    num = (a * stream[-1] + b) % p
    stream.append(num)
e = gmpy2.next_prime(stream[1] * stream[14] + stream[51] * stream[4])
# print(e)

phi = (p-1)*(q-1)
d = libnum.invmod(e,phi)
m = pow(c,d,n)
print(libnum.n2s(int(m)))

# b'flag{efc296e5dedb426c492bd7eeb5514394}'

方法二：

官方wp思路和上面大差不差，脚本写得优雅一点

通过分别取⾼低位可以得到ab之积的绝⼤部分值，爆破差值即可。由于ab均为素数，所以可以通过判 断是否有⼩素数来粗略筛选ab的值。由于不知道求得a和b是否与⽣成数字的a和b位置相同，因此可以 简单⽣成两个stream，观察哪个能得到flag即可：

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

# def small_factor(ab):
#     for i in range(2,1000):
#         if n%i == 0:
#             return False
#         return True

def attack(ab):
    a,b = sympy.symbols("a b")
    f1 = a*b-ab
    f2 = (a* 2**128 + b)*(b* 2**128 + a) - n
    result = sympy.solve([f1,f2],[a,b])
    # print(result)
    if len(result)>0:
        a,b = list(map(abs,result[0]))
        # print(list(map(abs,result[0])))
        return a,b
    return None

c = 6231259964139423317420399259419242000626426110518752018384660416595264962435087677191600419542766152613241809444876652160722765670645883113456355844854019# 256205479281287561054456695429182604991
n = 10787879094547634536418400489544495490920545668797140045606047169206620885051312335135831508173231222095307914925085736895140618767731141232201839054986089

tmp1 = bin(n)[2:][:123]
tmp2 = bin(n)[2:][-128:]

ab1 = []
for i in range(2**5):
    pad = bin(i)[2:].zfill(5)
    ab = int(tmp1+ pad +tmp2,2)
    # if small_factor(ab) == True:
    ab1.append(ab)

for ab in tqdm(ab1):
    ans = attack(ab)
    if ans != None:
        a,b = ans
        break

p = 2 ** 128 * a + b
q = 2 ** 128 * b + a
assert p * q == n
if p > q:
    p,q = q,p

phi = int((p - 1) * (q - 1))
stream1 = [q]

for i in range(114):
    num = (a * stream1[-1] + b) % p
    stream1.append(num)

# stream2 = [q]
# for i in range(114):
#     num = (b * stream2[-1] + a) % p
#     stream2.append(num)

e1 = gmpy2.next_prime(int(stream1[1] * stream1[14] + stream1[51] * stream1[4]))
# e2 = gmpy2.next_prime(int(stream2[1] * stream2[14] + stream2[51] * stream2[4]))
# print(e1,e2)
d1 = gmpy2.invert(e1,phi)
# d2 = gmpy2.invert(e2,phi)
m1 = pow(c,d1,n)
# m2 = pow(c,d2,n)
print(long_to_bytes(m1))
# print(long_to_bytes(m2))

方法三：

二元copper解：

a、b 是128bit 的素数，所以最高位和最低位一定是 1

所以实际中求的是a、b 中间的126位的值

其实是看得懂的，只是未接触

最难的部分也即是 自定义的 small_roots ，网上搜得到，有区别于 多项式的求根 

1
f.small_roots(X=2^(340),beta=0.4,epsilon=0.03)
1
def small_roots(f, bounds, m=1, d=None):

其中m为移位（shifts），d 为多项式中的最高幂。

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

import itertools
 
def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m+1):
        base = N^(m-i) * f^i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1/factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B*monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

n = 10787879094547634536418400489544495490920545668797140045606047169206620885051312335135831508173231222095307914925085736895140618767731141232201839054986089
c = 6231259964139423317420399259419242000626426110518752018384660416595264962435087677191600419542766152613241809444876652160722765670645883113456355844854019# 256205479281287561054456695429182604991

R.<x,y> = PolynomialRing(Zmod(n))
a = 2^127 + 2*x + 1
b = 2^127 + 2*y + 1
f = (a*2^128+b)*(b*2^128+a)

bound = (2^126,2^126)
res = small_roots(f,bound,m=2,d=2)
if res !=[]:
    for sol in res:
        a = 2^127 + 2*int(sol[0]) + 1
        b = 2^127 + 2*int(sol[1]) + 1
        p = int((bin(a)[2:].zfill(128) + bin(b)[2:].zfill(128)),2)
        q = int((bin(b)[2:].zfill(128) + bin(a)[2:].zfill(128)),2)
        if p > q:
            p, q = q, p
        n = p * q
        stream = [q]
        for i in range(114):
            num = (a * stream[-1] + b) % p
            stream.append(num)
        e = gmpy2.next_prime(stream[1] * stream[14] + stream[51] * stream[4])
        d = gmpy2.invert(e,(p-1)*(q-1))
        m = pow(c,d,n)
        flag = long_to_bytes(int(m))
        if b'flag' in flag:
            print(flag)
1
2
a = 2^127 + 2*x + 1
b = 2^127 + 2*y + 1

乘以 2 是因为它的最低位处于第二位

二元copper：

以后回来再看：

二元coppersmith - 顶真珍珠 - 博客园 (cnblogs.com)

ch19.pdf (auckland.ac.nz)

-------------　　　　本文结束　　感谢阅读　　　　-------------