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

2024强网杯 WriteUp

crypto比赛

发布于：2024年12月24日

次浏览

apbq

加密代码：

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
from Crypto.Util.number import *
from secrets import flag
from math import ceil
import sys

class RSA():
    def __init__(self, privatekey, publickey):
        self.p, self.q, self.d = privatekey
        self.n, self.e = publickey

    def encrypt(self, plaintext):
        if isinstance(plaintext, bytes):
            plaintext = bytes_to_long(plaintext)
        ciphertext = pow(plaintext, self.e, self.n)
        return ciphertext

    def decrypt(self, ciphertext):
        if isinstance(ciphertext, bytes):
            ciphertext = bytes_to_long(ciphertext)
        plaintext = pow(ciphertext, self.d, self.n)
        return plaintext

def get_keypair(nbits, e = 65537):
    p = getPrime(nbits//2)
    q = getPrime(nbits//2)
    n = p * q
    d = inverse(e, n - p - q + 1)
    return (p, q, d), (n, e)

if __name__ == '__main__':
    pt = './output.txt'
    fout = open(pt, 'w')
    sys.stdout = fout

    block_size = ceil(len(flag)/3)
    flag = [flag[i:i+block_size] for i in range(0, len(flag), block_size)]
    e = 65537

    print(f'[+] Welcome to my apbq game')
    # stage 1
    print(f'┃ stage 1: p + q')
    prikey1, pubkey1 = get_keypair(1024)
    RSA1 = RSA(prikey1, pubkey1)
    enc1 = RSA1.encrypt(flag[0])
    print(f'┃ hints = {prikey1[0] + prikey1[1]}')
    print(f'┃ public key = {pubkey1}')
    print(f'┃ enc1 = {enc1}')
    print(f'----------------------')

    # stage 2
    print(f'┃ stage 2: ai*p + bi*q')
    prikey2, pubkey2 = get_keypair(1024)
    RSA2 = RSA(prikey2, pubkey2)
    enc2 = RSA2.encrypt(flag[1])
    kbits = 180
    a = [getRandomNBitInteger(kbits) for i in range(100)]
    b = [getRandomNBitInteger(kbits) for i in range(100)]
    c = [a[i]*prikey2[0] + b[i]*prikey2[1] for i in range(100)]
    print(f'┃ hints = {c}')
    print(f'┃ public key = {pubkey2}')
    print(f'┃ enc2 = {enc2}')
    print(f'----------------------')

    # stage 3
    print(f'┃ stage 3: a*p + q, p + bq')
    prikey3, pubkey3 = get_keypair(1024)
    RSA3 = RSA(prikey3, pubkey3)
    enc3 = RSA2.encrypt(flag[2])
    kbits = 512
    a = getRandomNBitInteger(kbits)
    b = getRandomNBitInteger(kbits)
    c1 = a*prikey3[0] + prikey3[1]
    c2 = prikey3[0] + b*prikey3[1] 
    print(f'┃ hints = {c1, c2}')
    print(f'┃ public key = {pubkey3}')
    print(f'┃ enc3 = {enc3}')

part1

这部分没什么好讲的，直接略过

part2

两种方法，一种是使用gro基加线性组合，另一种就是直接使用正交格

先说第一种，这边给了我们一百组等式，，也就是

a1∗p+b1∗q=x1a2∗p+b2∗q=x2…a100∗p+b100∗q=x100\begin{array}{l} a_1 *p + b_1 * q = x_1\\ a_2 *p + b_2 * q = x_2\\ \dots \\ a_{100} *p + b_{100} * q = x_{100} \end{array}

这很明显的思路就是造格了，我们肯定要去掉p和q之后规约出短向量a和b

消去p和q我们可以使用resultant结式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
R.<a1, a2, a3, a4, b1, b2, b3, b4, p, q, x1, x2, x3, x4> = Zmod(n)[]
f1 = a1 * p + b1 * q - x1
f2 = a2 * p + b2 * q - x2
f3 = a3 * p + b3 * q - x3
f4 = a4 * p + b4 * q - x4


tm_q_1 = resultant(f1, f2, p)
tm_q_2 = resultant(f1, f3, p)
ff = resultant(tm_q_1, tm_q_2, q)
print(ff)

tm_q_3 = resultant(f1, f4, p)
ff = resultant(tm_q_1, tm_q_3, q)
print(ff)
1
2
a1*a3*b2*x1 - a1*a2*b3*x1 - a1*a3*b1*x2 + a1^2*b3*x2 + a1*a2*b1*x3 - a1^2*b2*x3
a1*a4*b2*x1 - a1*a2*b4*x1 - a1*a4*b1*x2 + a1^2*b4*x2 + a1*a2*b1*x4 - a1^2*b2*x4

消掉共同拥有的a1a_1，对应

1
2
a3*b2*x1 - a2*b3*x1 - a3*b1*x2 + a1*b3*x2 + a2*b1*x3 - a1*b2*x3
a4*b2*x1 - a2*b4*x1 - a4*b1*x2 + a1*b4*x2 + a2*b1*x4 - a1*b2*x4

其实也就是对应如下的通式

(ai∗b2−a2∗bi)∗x1−(ai∗b1−a1∗bi)∗x2+(a2∗b1−a1∗b2)∗xi(a_i*b_2 - a_2*b_i) * x_1 - (a_i*b_1 - a_1*b_i)*x_2 + (a_2*b_1 - a_1*b_2)*x_i

通过测试可以知道我们需要三组等式就可以消掉p和q，那么我们就可以f1f_1和f2f_2为基准，然后从f3f_3开始到f100f_{100}就拿到98组等式，然后可以构造如下的格（这玩意的latex代码有点难写，这边列举一个简答的，大家懂我意思就行了）

image-20250218161942773

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
h = []  #数据太长不放了
n2, e = (83306955879576794663013877605008168868044098017133825299645318248190193317048264072881820370005988750003947150193243887515721618366600840067815060233979700844891922517920583102626051839017559245080706659940160476934158509162580386609219020570769224015646382223549048698724547720177511383657606919026442310347, 65537)

nums = 98
L = matrix(ZZ, 1+nums*2, 1+nums*3)
for i in range(1+nums*2):
    L[i,i] = 1
for i in range(nums):
    L[0,1+nums*2+i] = h[i+2]
    L[2*i+1,1+nums*2+i] = h[0]
    L[2*i+2,1+nums*2+i] = h[1]
L[:,-nums:] *= 2^512
L = L.LLL()

v,t,u = L[0,0],L[0,1],L[0,2]


from Crypto.Util.number import *
from gmpy2 import gcd
from itertools import product
from tqdm import trange
import sys


for i in trange(-10, 10):
    for j, k in product(range(-10, 10), repeat = 2):
        a1, a2, a3, b1, b2, b3 = QQ["a1,a2,a3,b1,b2,b3"].gens()  #这边要创建在QQ上才组合的出来，创建的ZZ或者模n意义下都不行
        # R.<a1, a2, a3, b1, b2, b3> = Zmod(n2)[]
        f1 = a3 * b2 - a2 * b3 - i * t
        f2 = a1 * b3 - a3 * b1 - j * u
        f3 = a2 * b1 - a1 * b2 - k * v
        poly = []
        poly.extend([f1, f2, f3])
        gb = Ideal(poly).groebner_basis() #就算这边gro的时候没有组合，也是可以的
        if 1:
            L = identity_matrix(3, 3).change_ring(QQ).augment(matrix(3, 1, list(gb)[1].coefficients()))  #这边的系数是分数
            L[:, -1] *= n2
            res2 = L.LLL()
            #爆破两次，一次是a1 a2 a3的，另一次是b1 b2 b3的
            for i1, j1 in product(range(-10, 10), repeat = 2):
                res = i1 * res2[0] + j1 * res2[1]
                if res[-1] == 0:
                    a1, a2, a3 = [tmp for tmp in res[:-1:]]
                    A = [a1, a2, a3]
                    if all(0 < a < 2 ^ 180 for a in A):
                        for i2, j2 in product(range(-10, 10), repeat = 2):
                            res_ = i2 * res2[0] + j2 * res2[1]
                            if res_[-1] == 0:
                                b1, b2, b3 = [tmp for tmp in res_[:-1:]]
                                B = [b1, b2, b3]
                                if all(0 < b < 2 ^ 180 for b in B):
                                        q = gcd(int(a2 * h[0] - a1 * h[1]), int(n2))
                                        if isPrime(q) and n2 % q == 0:
                                            p = n2 // q
                                            print(p)
                                            print(q)
                                            sys.exit()


除了使用上面的方法，这题其实还可以使用正交格来做，因为这个挺好转换为矩阵的，对于每组的等式，其实我们可以转换为如下的矩阵乘法

A100×2B2×1=C100×1\begin{array}{l} A_{100\times 2} B_{2\times 1}=C_{100\times 1} \end{array}

其中这边的B2×1B_{2\times 1}表示为(pq)2×1\begin{pmatrix} p \\ q \end{pmatrix}_{2\times 1}

虽然所这边我们想要求得的目标向量是B2×1B_{2\times 1}，但是我们转置之后会发现这玩意根本没有核空间，因为它本质上就是条向量，所以我们这边可以转过来先求A100×2A_{100\times 2}，而且A100×2A_{100\times 2}里面相对B2×1B_{2\times 1}都是短向量，更容易规约出来

也就是我们可以找到一个矩阵MM​满足

M98×100A100×2B2×1=M98×100C100×1\begin{array}{l} M_{98\times 100}A_{100\times 2} B_{2\times 1}=M_{98\times 100}C_{100\times 1} \end{array}

显然可以构造如下的格

[I100×100C100×101×100p]\begin{bmatrix} I_{100\times 100} & C_{100\times 1}\\ 0_{1\times 100} & p \end{bmatrix}

该格满足

( m1, m2, m3, ..., m100, k)∗[I100×100C100×101×100p]=( m1, m2, m3, ..., m100, 0)(\ m_1,\ m_2,\ m_3,\ ...,\ m_{100},\ k) * \begin{bmatrix} I_{100\times 100} & C_{100\times 1}\\ 0_{1\times 100} & p \end{bmatrix} = (\ m_1,\ m_2,\ m_3,\ ...,\ m_{100},\ 0)

此时有

M98×100A100×2=0M_{98\times 100}A_{100\times 2}=0

转置一下，有

A2×100TM100×98T=0A^T_{2\times 100}M^T_{100\times 98}=0

构造如下的格

[I100×100M100×98T]\begin{bmatrix} I_{100\times 100} & M^{T}_{100\times 98}\\ \end{bmatrix}

该格满足

( a1, a2, a3, ..., a100)∗[I100×100M100×98T]=( a1, a2, a3, ..., a100, 0, 0, …, 0⏟98个)(\ a_1,\ a_2,\ a_3,\ ...,\ a_{100}) * \begin{bmatrix} I_{100\times 100} & M^{T}_{100\times 98}\\ \end{bmatrix} = (\ a_1,\ a_2,\ a_3,\ ...,\ a_{100},\ \underbrace{0,\ 0,\ \dots,\ 0}_{98\text{个}})

直接拿我当时写的这里面题2的exp来用就行了

1
https://suhanhan-cpu.github.io/2024/12/25/%E6%AD%A3%E4%BA%A4%E6%A0%BC/

这边经过多次测试，发对于规约出来的矩阵A100×2A_{100\times 2}，这边检验了前两组，发现每组的第二个元素都是可以成功规约出来的，第一个元素一般规约不出来，但是他们的顺序不一定，因为p和q的顺序是可以调换的，这会导致矩阵A里面的元素的a和b也是可以调换的，但是无所谓，我们只要拿前两组等式消掉 p或者q之后和n做一下gcd就可以了

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

h = []
n2, e = (93172851530903280665698646277283403375770782366786869783590259544406324214779512142434711869404111971925289742354082360810829087299546165147248989707179460324393397783211164108966147109518988985549892657039106930772151406465434583994101602999929389467925165673484423421034035671458314305110697400859301468773, 65537)
C = Matrix(ZZ, 100, 1, h)

#求M
M = []
L1 = block_matrix(ZZ, [[identity_matrix(100), C], 
                       [Matrix(ZZ, 1, 100), n2]]) #不需要规约


res1 = L1.LLL()

for i in res1:
    if i[-1] == 0:
        M.append(i[:-1:])

M = Matrix(ZZ, 98, 100, M)


L2 = block_matrix([[identity_matrix(100), M.T]]) * diagonal_matrix(ZZ, [1] * 100 + [n2] * 98)
res2 = L2.LLL()

A_T = []
for i in res2:
    if all(j == 0 for j in i[-98::]):
        A_T.append(i[:-98:])
A = Matrix(ZZ, A_T).T
gcd(int(abs(A[0][1]) * h[1] - abs(A[1][1]) * h[0]), int(n2))

part3

给了如下的等式

c1=a∗p+qc2=p+b∗qn=p∗q\begin{array}{l} c_1 = a * p + q\\ c_2 = p + b * q\\ n = p*q \end{array}

给了c1c_1、c2c_2和nn，要求还原pp和qq

这边未知的变量太多了，如果我们使用resultant结式会发现很难凑出我们想要的等式，我们肯定要尽可能的消掉更多的未知量，要消到一个显然是不可能的，但是消到两个就可以打二元copper

这边的a和b可以这样消掉

c1−q=a∗pc2−p=b∗q\begin{array}{l} c_1 - q = a * p\\ c_2 - p = b * q \end{array}

两个相乘，在模n下，就可以消掉a和b

(c1−q)∗(c2−p)≡ 0 (mod n)(c_1 - q) * (c_2 - p) \equiv\ 0\ (mod\ n)

这时候的变量只剩下p和q，很有希望打二元

展开

c1∗c2−c1∗p−c2∗q≡0(mod n)c_1 * c_2- c_1 * p - c_2 * q\equiv 0(mod\ n)

显然我们可以构造如下的格

(100c1010c2001c1∗c2000n)\begin{pmatrix} 1 & 0 & 0 & c_1\\ 0 & 1 & 0 & c_2\\ 0 & 0 & 1 & c_1 * c_2\\ 0 & 0 & 0 & n \end{pmatrix}

该格满足

(−p,−q,1,k)(100c1010c1001c1∗c2000n)=(−p,−q,1,0)(-p, -q, 1, k) \begin{pmatrix} 1 & 0 & 0 & c_1\\ 0 & 1 & 0 & c_1\\ 0 & 0 & 1 & c_1 * c_2\\ 0 & 0 & 0 & n \end{pmatrix}= (-p, -q, 1, 0)

配平后实际测试会发现规约出来的比特位也是512位，但是规约不出来正确的

那应该就是差一点点就可以规约出来了，线性组合发现还是不行，简单爆破几个比特位后发现可以成功规约出来（无非就这两种方法）

这边我用的是二元，虽然速度慢点，但是格打不出来的二元有时候可以，反过来就不一样了，但是格速度更快，更适合爆破，这题的话是没差的，二元copper速度也很快

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


def small_roots(f, bounds, m=1, d=None):#多元copper
    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 []


c1 = 63368761932613842931186496815195302343816278778369820350680016031561260784146601113278597310189098581850115470098152301165931711345761664290778374659249559329035280283494371042474865722891532827897755000275687864176501132925347463999981764475333799411108459578435275445071666229681621879980239595445066509058
c2 = 140716656752513767303521116946576890451843673026395512785448654626202542315377688700861224898499523861864127538750879630242940209696550481440749930737413349006590385507088788522544403872190399702081066036559185560540710792209083159454133923277846222047802642033856060579088825468633118141806144027582327045847
n = 99720459301264425369585053508752620650615199220949113516774395393283229820439564403401565215598525216853592073661811471273389192191888623577728355790122863652012102195901985097819470227052958722886251736017915052150597294398696203295351320367071710305452460786240560165901336595444101053569653201485580740723


R.<ph, qh> = Zmod(n)[]
bound = 5
for i in trange(2 ^ bound):
    for j in range(2 ^ bound):
        f = c1 * c2 - c1 * (2 ^ bound * ph + i) - c2 * (2 ^ bound * qh + j)
        res = small_roots(f, bounds = (2 ^ (512 - bound), 2 ^ (512 - bound)), m = 3, d = 2)
        if res:
            for root in res:
                p = 2 ^ bound * abs(ZZ(root[0])) + i
                if isPrime(p) and n % p == 0:
                    print(p)
                    sys.exit()

更新于：2025年2月25日

评论

评论区