20211206-GWB-CryproSecWriteUp

Posted on Edited on In , Views: Symbols count in article: 4.7k Reading time ≈ 4 mins.

 

signin

签到题，先base64解码得到的是题目代码，有两个不互素的指数，但公因子较小为3，共模攻击，最后开个3次根

flag{e6e5722e-4b9a-11ec-b784-00155d9a1603}

crypto2

考点

  • 多元coppersmith

题目描述

两层，第一层已知p的高位，求hint，这个不说了，基础攻击，也许还要爆破几位；第二层已知两个数的高位，求解这两个数以及一个26位的随机数r

1
2
3
4
5
6
7
8
9
10
secreteBitNum = 26
target_bits = int(256)
prime = getPrime(target_bits)
s = randint(prime>>10, prime)
r = getrandbits(secreteBitNum)
t = (r*(s^2 + 2*s)) % prime
gifts = [3, 2]
ks = [floor(target_bits * (gift / (gift + 1))) for gift in gifts]
leak1 = s >> (target_bits - ks[0])
leak2 = t >> (target_bits - ks[1])

这里ks是已知的，相当于leak1是s的高$\frac{3}{4}$位，leak2是t的高$\frac{2}{3}$位

解题思路

很显然的coppersmith解小根，coppersmith构造两元，但是coppersmith求小根的函数太慢了，这里要跑出r，我一台机子要跑大约2400h，多线多台电脑程优化下或许可以，毕竟也有师傅这样做出来了

别的思路，有没有发现可以把r也当成小根，然后使用三元coppersmith，挖藕，类似corCTF2021-babyrand

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
#!/usr/bin/env sage
# coding: utf-8
from Crypto.Util.number import long_to_bytes
from gmpy2 import invert
from sympy import nextprime
load("exploit/coppersmithSmallRoots.sage")
load("exploit/coppersmithPHighBits.sage")

get_flag = lambda c, p, q: long_to_bytes(pow(c, invert(e, p*q-p-q+1), p*q))

# get hint
tmp_N = 67275889677378946734903321404206582364153218707836044936581311977721676158433934674861722018390091292542128885311842688233567992017423854706617140651934525455990460080562308585391373661331461122947028205118969966760791488914164391921330229025670176008518053339148134137770309365614255463111202481834705060173
cx = 40399377632586118650556149454962332599993544072289982576457293479237148938553095258299197606759611718110458893982875730643146645623512300513916266262798465380752083932871857821720398540072426424439422364690204675516506456125988918985863308292449915493404572808822346197667419207669315093927318993921905479596
pbar = 4877155090632997781879191807827231697420271396210537080241322765167927413977000532975047982026915056
e = 0x10001
for i in range(3):
    p = known_hb(tmp_N, pbar, 512, i)
    if p:
        q = tmp_N // p
        print(get_flag(cx, p, q))
        break
secreteBitNum = 26

# get flag
prime = 82321753209337659641812698792368753307257174920293482309329229017641186204037
c = 4327179356609269294409009935591795772603625779675971467878490086808144060225614005300908314649047950861015994603326121468330956776913366179511247457747179889685304469999218104955814145411915021238933150884498316563808220329632240175418452382843973948334446343545955570063628905102384071000832724697885872043017030707897928
N = 43941665823196509154346632368475246193489316520677500866461851257383928558997955146720003171553041820199105630143274308184375615057136594812756966125202091119439909980006181740220827474838356621605513939553184451557022029987518161532780360148932769025277495283357745880781214097057768654158857096614016596756958574010574773
leak1 = 4392924728395269190263639346144303703257730516994610750658
leak2 = 838456777370923849008096179359487752850229097203212

sbits = 64
tbits = 86
rbits = secreteBitNum
s = leak1 << sbits
t = leak2 << tbits

Fp = Zmod(prime)
PR.<s0, t0, r0> = PolynomialRing(Fp)
f = r0 * ((s + s0) ^ 2 + 2 * (s + s0)) - (t + t0)
roots = small_roots(f, (2^sbits, 2^tbits, 2^rbits), 2)
s += int(roots[0][0])
t += int(roots[0][1])
r = int(roots[0][2])
p = nextprime((s*(nextprime(s) * nextprime(r) + t)))
if N % p == 0:
    q = N // p
    print(get_flag(c, p, q))

flag{bc33c490-4b95-11ec-ad04-00155d9a1603}

最后整理两个库文件吧，方便之后用到

coppersmithSmallRoots.sage

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
import itertools

def small_roots(f, bounds, m=2, 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 []

coppersmithPHighBits.sage

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#!/usr/bin/env sage
from tqdm import tqdm


def known_hb(n, pbar, pbits, bb = 0):
    # pbar: p's high bits
    # pbits: p's original bit length
    # bb: bits for brute-force, default to zero
    pbar = int(hex(pbar) + '0' * bb, 16)    # pbar >> p0bit << p0bit then turn to hex with bb's 0 padding for brute

    # brute 4*bb's bits, i.e. 2 ^ (4 * bb)
    for i in tqdm(range(2 ^ (4 * bb))):
        tp = pbar + i
        p0bit = pbits - tp.bit_length()
        Fn = Zmod(n)
        PR.<x> = PolynomialRing(Fn)
        tp <<= p0bit
        f = tp + x
        roots = f.small_roots(X=2^p0bit, beta=0.4)
        if roots:
            p = tp + int(roots[0])
            if n % p == 0:
                return p
    return []