2024网鼎杯

本人的第一篇blog，顺便记录一下前几天打的网鼎杯青龙组预赛，完成两道Crypto题和一道misc的解答。

战队获得2490分，排名150名左右。

Crypto

Crypto1

题目：

from Crypto.Util.number import *
from secret import flag

p = getPrime(512)
q = getPrime(512)
n = p * q
d = getPrime(299)
e = inverse(d,(p-1)*(q-1))
m = bytes_to_long(flag)
c = pow(m,e,n)
hint1 = p >> (512-70)
hint2 = q >> (512-70)

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"hint1 = {hint1}")
print(f"hint2 = {hint2}")

n = 65318835751656706270462803918372182811096669561139853833192009681234356986381524661604904085035483519298788284835759796179173585004238691057332447589167439506386243352011548441011828732868691543989256629925692290088144403935880664585931943707422938295860559274669263630591393175387389387981929391774213395003
e = 40738963799387627677248718814260921636491770341278750841486515130562842134876396915106681433734276005332410415984785584884091334455816402584507178231273998519376915363193650533215442952274343814099450187672503465016280527554101223321817109358581483535333734940968961773897326303002987203525415266163296607215
c = 28858301095788879003830568949705095027466057921892765321643055383309726369907606901866332954652632036004551285284813812187678314978562231120323470819722044516158810710408496414616381570397632550468546302235826400628265458069027801013266037490695637948933487646553291637002155559023268928639502489285322508063
hint1 = 624859718207126357681
hint2 = 810475217500119132950

发现是论文题，利用coppersmith来进行约束求解

参考了该论文https://eprint.iacr.org/2023/367.pdf

在github中找到了类似的代码，加以修改得：

import time
time.clock = time.time
 
debug = True
 
strict = False
 
helpful_only = True
dimension_min = 7 

def helpful_vectors(BB, modulus):
    nothelpful = 0
    for ii in range(BB.dimensions()[0]):
        if BB[ii,ii] >= modulus:
            nothelpful += 1

def matrix_overview(BB, bound):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii,jj] == 0 else 'X'
            if BB.dimensions()[0] < 60: 
                a += ' '
        if BB[ii, ii] >= bound:
            a += '~'
            
def remove_unhelpful(BB, monomials, bound, current):
    if current == -1 or BB.dimensions()[0] <= dimension_min:
        return BB
 
    for ii in range(current, -1, -1):

        if BB[ii, ii] >= bound:
            affected_vectors = 0
            affected_vector_index = 0

            for jj in range(ii + 1, BB.dimensions()[0]):

                if BB[jj, ii] != 0:
                    affected_vectors += 1
                    affected_vector_index = jj

            if affected_vectors == 0:
                #print ("* removing unhelpful vector", ii)
                BB = BB.delete_columns([ii])
                BB = BB.delete_rows([ii])
                monomials.pop(ii)
                BB = remove_unhelpful(BB, monomials, bound, ii-1)
                return BB

            elif affected_vectors == 1:
                affected_deeper = True
                for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
                    if BB[kk, affected_vector_index] != 0:
                        affected_deeper = False

                if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
                    BB = BB.delete_columns([affected_vector_index, ii])
                    BB = BB.delete_rows([affected_vector_index, ii])
                    monomials.pop(affected_vector_index)
                    monomials.pop(ii)
                    BB = remove_unhelpful(BB, monomials, bound, ii-1)
                    return BB
    return BB
 

def boneh_durfee(pol, modulus, mm, tt, XX, YY):

    PR.<u, x, y> = PolynomialRing(ZZ)   
    Q = PR.quotient(x*y + 1 - u)        
    polZ = Q(pol).lift()
 
    UU = XX*YY + 1

    gg = []
    for kk in range(mm + 1):
        for ii in range(mm - kk + 1):
            xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
            gg.append(xshift)
    gg.sort()

    monomials = []
    for polynomial in gg:
        for monomial in polynomial.monomials(): 
            if monomial not in monomials: 
                monomials.append(monomial)
    monomials.sort()

    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
            yshift = Q(yshift).lift()
            gg.append(yshift) 

    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            monomials.append(u^kk * y^jj)

    nn = len(monomials)
    BB = Matrix(ZZ, nn)
    for ii in range(nn):
        BB[ii, 0] = gg[ii](0, 0, 0)
        for jj in range(1, ii + 1):
            if monomials[jj] in gg[ii].monomials():
                BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)

    if helpful_only:
        BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
        nn = BB.dimensions()[0]
        if nn == 0:
            print ("failure")
            return 0,0

    if debug:
        helpful_vectors(BB, modulus^mm)

    det = BB.det()
    bound = modulus^(mm*nn)
    if det >= bound:
        print ("We do not have det < bound. Solutions might not be found.")
        print ("Try with highers m and t.")
        if debug:
            diff = (log(det) - log(bound)) / log(2)
            print ("size det(L) - size e^(m*n) = ", floor(diff))
        if strict:
            return -1, -1
    else:
        print ("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")

    if debug:
        matrix_overview(BB, modulus^mm)

    if debug:
        print ("optimizing basis of the lattice via LLL, this can take a long time")

    BB = BB.LLL()
 
    if debug:
        print ("LLL is done!")

    if debug:
        print ("在格中寻找线性无关向量")
    found_polynomials = False
 
    for pol1_idx in range(nn - 1):
        for pol2_idx in range(pol1_idx + 1, nn):
            PR.<w,z> = PolynomialRing(ZZ)
            pol1 = pol2 = 0
            for jj in range(nn):
                pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
                pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)
            PR.<q> = PolynomialRing(ZZ)
            rr = pol1.resultant(pol2)
            if rr.is_zero() or rr.monomials() == [1]:
                continue
            else:
                print ("found them, using vectors", pol1_idx, "and", pol2_idx)
                found_polynomials = True
                break
        if found_polynomials:
            break
 
    if not found_polynomials:
        print ("no independant vectors could be found. This should very rarely happen...")
        return 0, 0
 
    rr = rr(q, q)
    soly = rr.roots()
 
    if len(soly) == 0:
        print ("Your prediction (delta) is too small")
        return 0, 0
 
    soly = soly[0][0]
    ss = pol1(q, soly)
    solx = ss.roots()[0][0]
    return solx, soly
 
def example():
    start =time.clock()
    size=512
    length_N = 2*size;
    ss=0
    s=70;
    M=1   
    delta = 299/1024
    for i in range(M):
        N = 65318835751656706270462803918372182811096669561139853833192009681234356986381524661604904085035483519298788284835759796179173585004238691057332447589167439506386243352011548441011828732868691543989256629925692290088144403935880664585931943707422938295860559274669263630591393175387389387981929391774213395003
        e = 40738963799387627677248718814260921636491770341278750841486515130562842134876396915106681433734276005332410415984785584884091334455816402584507178231273998519376915363193650533215442952274343814099450187672503465016280527554101223321817109358581483535333734940968961773897326303002987203525415266163296607215
        c = 28858301095788879003830568949705095027466057921892765321643055383309726369907606901866332954652632036004551285284813812187678314978562231120323470819722044516158810710408496414616381570397632550468546302235826400628265458069027801013266037490695637948933487646553291637002155559023268928639502489285322508063
        hint1 =   624859718207126357681
        hint2 =   810475217500119132950

        m = 7  
        t = round(((1-2*delta) * m))  
        X = floor(N^delta)  
        Y = floor(N^(1/2)/2^s)    
        for l in range(int(hint1),int(hint1)+1):
            print('\n\n\n l=',l)
            pM=l;
            p0=pM*2^(size-s)+2^(size-s)-1;
            q0=N/p0;
            qM=int(q0/2^(size-s))
            A = N + 1-pM*2^(size-s)-qM*2^(size-s);
            P.<x,y> = PolynomialRing(ZZ)
            pol = 1 + x * (A + y)
            
            if debug:
                start_time = time.time()
            solx, soly = boneh_durfee(pol, e, m, t, X, Y)
 
 
            if solx > 0:
                if False:
                    print ("x:", solx)
                    print ("y:", soly)
 
                d_sol = int(pol(solx, soly) / e)
                ss=ss+1

                print ("=== solution found ===")
                print ("p的高比特为：",l)
                print ("q的高比特为：",qM)
                print ("d=",d_sol) 
 
            if debug:
                print("=== %s seconds ===" % (time.time() - start_time))
        print("ss=",ss)
        end=time.clock()
        print('Running time: %s Seconds'%(end-start))
if __name__ == "__main__":
    example()  

解得：

d=514966421261428616864174659198108787824325455855002618826560538514908088230254475149863519

然后用正常的rsa解密即可

d=514966421261428616864174659198108787824325455855002618826560538514908088230254475149863519
e=40738963799387627677248718814260921636491770341278750841486515130562842134876396915106681433734276005332410415984785584884091334455816402584507178231273998519376915363193650533215442952274343814099450187672503465016280527554101223321817109358581483535333734940968961773897326303002987203525415266163296607215
n=65318835751656706270462803918372182811096669561139853833192009681234356986381524661604904085035483519298788284835759796179173585004238691057332447589167439506386243352011548441011828732868691543989256629925692290088144403935880664585931943707422938295860559274669263630591393175387389387981929391774213395003
c=28858301095788879003830568949705095027466057921892765321643055383309726369907606901866332954652632036004551285284813812187678314978562231120323470819722044516158810710408496414616381570397632550468546302235826400628265458069027801013266037490695637948933487646553291637002155559023268928639502489285322508063
from Crypto.Util.number import *
m=pow(c,d,n)
print(long_to_bytes(m))
#wdflag{097e0b16-3991-488a-b512-c3dbfb86db4a}

Crypto2

题目：

# coding: utf-8
#!/usr/bin/env python2

import gmpy2
import random
import binascii
from hashlib import sha256
from sympy import nextprime
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes
from FLAG import flag
#flag = 'wdflag{123}'

def victory_encrypt(plaintext, key):
    key = key.upper()
    key_length = len(key)
    plaintext = plaintext.upper()
    ciphertext = ''

    for i, char in enumerate(plaintext):
        if char.isalpha():
            shift = ord(key[i % key_length]) - ord('A')
            encrypted_char = chr((ord(char) - ord('A') + shift) % 26 + ord('A'))
            ciphertext += encrypted_char
        else:
            ciphertext += char

    return ciphertext

victory_key = "WANGDINGCUP"
victory_encrypted_flag = victory_encrypt(flag, victory_key)

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
a = 0
b = 7
xG = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
yG = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
G = (xG, yG)
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
h = 1
zero = (0,0)

dA = nextprime(random.randint(0, n))

if dA > n:
    print("warning!!")

def addition(t1, t2):
    if t1 == zero:
        return t2
    if t2 == zero:
        return t2
    (m1, n1) = t1
    (m2, n2) = t2
    if m1 == m2:
        if n1 == 0 or n1 != n2:
            return zero
        else:
            k = (3 * m1 * m1 + a) % p * gmpy2.invert(2 * n1 , p) % p
    else:
        k = (n2 - n1 + p) % p * gmpy2.invert((m2 - m1 + p) % p, p) % p
    m3 = (k * k % p - m1 - m2 + p * 2) % p
    n3 = (k * (m1 - m3) % p - n1 + p) % p
    return (int(m3),int(n3))

def multiplication(x, k):
    ans = zero
    t = 1
    while(t <= k):
        if (k &t )>0:
            ans = addition(ans, x)
        x = addition(x, x)
        t <<= 1
    return ans

def getrs(z, k):
    (xp, yp) = P
    r = xp
    s = (z + r * dA % n) % n * gmpy2.invert(k, n) % n
    return r,s

z1 = random.randint(0, p)
z2 = random.randint(0, p)
k = random.randint(0, n)
P = multiplication(G, k)
hA = multiplication(G, dA)
r1, s1 = getrs(z1, k)
r2, s2 = getrs(z2, k)

print("r1 = {}".format(r1))
print("r2 = {}".format(r2))
print("s1 = {}".format(s1))
print("s2 = {}".format(s2))
print("z1 = {}".format(z1))
print("z2 = {}".format(z2))

key = sha256(long_to_bytes(dA)).digest()
cipher = AES.new(key, AES.MODE_CBC)
iv = cipher.iv
encrypted_flag = cipher.encrypt(pad(victory_encrypted_flag.encode(), AES.block_size))
encrypted_flag_hex = binascii.hexlify(iv + encrypted_flag).decode('utf-8')

print("Encrypted flag (AES in CBC mode, hex):", encrypted_flag_hex)

# output
# r1 = 76712729228617953759327460769502934288442352683563219334681162937413283736816
# r2 = 76712729228617953759327460769502934288442352683563219334681162937413283736816
# s1 = 61142716522536931000933884258275974451672976799526648226417247076297644105637
# s2 = 110325312844668993695487572180262093359430311098679377435432296948029997765038
# z1 = 98842149708744845426265508894541731680137086618921535447693509433269270288237
# z2 = 78136168258634736524120345789104208327951990634981072456222624757958532742853
# ('Encrypted flag (AES in CBC mode, hex):', u'12d5174f2548c179287c7a2ce98a60b20a2dea24611a10d05a8dda9e7bda5f00e260e0c75e62ef6cb1e3341361ddb36b665b471be124ae3a9271da69a21ce8d6')

解答：

一步一步分析即可，首先逆向解出k和dA，这个直接做运算即可

然后把三轮的r和s放进去

将s分为两部分 取前十六位作为初始化的向量 后面是正常的加密的部分

然后计算私钥dA对应的 SHA-256 哈希值作为密钥key_temp。使用CBC 模式，以key_temp为密钥，flag_1为初始化向量，对enflag进行解密，得到decrypted_flag。

最后用题目提供的解密函数进行解密即可，得到flag

py：

from gmpy2 import *
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
a = 0
b = 7
xG = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
yG = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
G = (xG, yG)
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
h = 1
zero = (0,0)

r1=76712729228617953759327460769502934288442352683563219334681162937413283736816

s1 = 61142716522536931000933884258275974451672976799526648226417247076297644105637
s2 = 110325312844668993695487572180262093359430311098679377435432296948029997765038
z1 = 98842149708744845426265508894541731680137086618921535447693509433269270288237
z2 = 78136168258634736524120345789104208327951990634981072456222624757958532742853

k=(gmpy2.invert(s1-s2,n)*(z1-z2)+n)%n
dA=gmpy2.invert(r1,n)*(k*s1-z1)%n

s=u'12d5174f2548c179287c7a2ce98a60b20a2dea24611a10d05a8dda9e7bda5f00e260e0c75e62ef6cb1e3341361ddb36b665b471be124ae3a9271da69a21ce8d6'
ans=binascii.unhexlify(s)
flag_1=ans[:16]
enflag=ans[16:]
key_temp = sha256(long_to_bytes(dA)).digest()
cipher = AES.new(key_temp, AES.MODE_CBC,flag_1)
decrypted_flag = unpad(cipher.decrypt(enflag), AES.block_size)

def victory_decrypt(ciphertext, key):
    key = key.upper()
    key_length = len(key)
    plaintext = ''

    for i, char in enumerate(ciphertext):
        if char.isalpha():
            shift = ord(key[i % key_length]) - ord('A')
            decrypted_char = chr((ord(char) - ord('A') - shift) % 26 + ord('A'))
            plaintext += decrypted_char
        else:
            plaintext += char

    return plaintext

victory_encrypted_flag = decrypted_flag.decode()
victory_key = "WANGDINGCUP"
flag = victory_decrypt(victory_encrypted_flag, victory_key)
print(flag.lower())
#wdflag{d4d98e3c6224cb3f641483f31d33ce58}

Misc

Misc4

是一种皮亚诺曲线的加密

解密脚本如下：参考了https://almostgph.github.io/2024/01/08/IrisCTF2024/

from PIL import Image
from tqdm import tqdm

def peano(n):
    if n == 0:
        return [[0,0]]
    else:
        in_lst = peano(n - 1)
        lst = in_lst.copy()
        px,py = lst[-1]
        lst.extend([px - i[0], py + 1 + i[1]] for i in in_lst)
        px,py = lst[-1]
        lst.extend([px + i[0], py + 1 + i[1]] for i in in_lst)
        px,py = lst[-1]
        lst.extend([px + 1 + i[0], py - i[1]] for i in in_lst)
        px,py = lst[-1]
        lst.extend([px - i[0], py - 1 - i[1]] for i in in_lst)
        px,py = lst[-1]
        lst.extend([px + i[0], py - 1 - i[1]] for i in in_lst)
        px,py = lst[-1]
        lst.extend([px + 1 + i[0], py + i[1]] for i in in_lst)
        px,py = lst[-1]
        lst.extend([px - i[0], py + 1 + i[1]] for i in in_lst)
        px,py = lst[-1]
        lst.extend([px + i[0], py + 1 + i[1]] for i in in_lst)
        return lst

order = peano(6)

img = Image.open(r"C:\Users\Lenovo\Desktop\1.png")

width, height = img.size

block_width = width # // 3
block_height = height # // 3

new_image = Image.new("RGB", (width, height))

for i, (x, y) in tqdm(enumerate(order)):
    # 根据列表顺序获取新的坐标
    new_x, new_y = i % width, i // width
    # 获取原图像素
    pixel = img.getpixel((x, height - 1 - y))
    # 在新图像中放置像素
    new_image.putpixel((new_x, new_y), pixel)

new_image.save("rearranged_image.jpg") 

跑出来的结果存在了anaconda目录下 打开得到二维码

扫描二维码得到flag

wdflag{b9367dd6-2d7e-4ef7-ba5c-270a6c6220cd}