2024网鼎杯

记录2024网鼎杯Crypto部分题解

青龙组

Crypto01

task.py

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 = 73787944575265560659337066998651559854008554735456318333076159883563615536562553619509791556832630227860528135540580555475313775587694656733939337337162684083504013096398383073623252469953554083296109377792508578226035938969407231689553680824348024184291021105154956244179599769690508760502010020180061720019
e = 29567393844922147731100606267534953994449203725806042726345753844983783164567752859600595704301680439820601788437000356006329166887506988972343037285018001864800437750191409728833296698465447150521119258782212680439802048101817052671603259114861564484544609221844909301043673563931709693327971992359139371227
c = 45450360465574139870481845301350579669043708378076876540990465420189044791001300484095663295849190297258585508686905534568744689506644183459090297899984297370341547866178062353877908003401151052692574668213473397829536065790283637478791675039086877921443504800597649778898977086137114431286134700385182325815
hint1 = 954676601865566077628
hint2 = 599256795156046227992

和2023领航杯复赛的bd一模一样，之前有记录过，可以看我的这篇博客2023江苏省领航杯 | DexterJie’Blog

exp

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
    print(nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")

# 显示带有 0 和 X 的矩阵
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 += '~'
        #print (a)

# 尝试删除无用的向量
# 从当前 = n-1（最后一个向量）开始
def remove_unhelpful(BB, monomials, bound, current):
    # 我们从当前 = n-1（最后一个向量）开始
    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
 
            # 等级：0
            # 如果没有其他载体最终受到影响
            # 我们删除它
            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
 
           # 等级：1
            #如果只有一个受到影响，我们会检查
            # 如果它正在影响别的向量
            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]):
                    #print ("* removing unhelpful vectors", ii, "and", affected_vector_index)
                    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
    # nothing happened
    return BB
 
""" 
Returns:
* 0,0   if it fails
* -1，-1 如果 "strict=true"，并且行列式不受约束
* x0,y0 the solutions of `pol`
"""
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
    """
    Boneh and Durfee revisited by Herrmann and May
 
 在以下情况下找到解决方案：
* d < N^delta
* |x|< e^delta
* |y|< e^0.5
每当 delta < 1 - sqrt（2）/2 ~ 0.292
    """
 
    # substitution (Herrman and May)
    PR.<u, x, y> = PolynomialRing(ZZ)   #多项式环
    Q = PR.quotient(x*y + 1 - u)        #  u = xy + 1
    polZ = Q(pol).lift()
 
    UU = XX*YY + 1
 
    # x-移位
    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()
 
    # 单项式 x 移位列表
    monomials = []
    for polynomial in gg:
        for monomial in polynomial.monomials(): #对于多项式中的单项式。单项式（）：
            if monomial not in monomials:  # 如果单项不在单项中
                monomials.append(monomial)
    monomials.sort()
 
    # y-移位
    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) # substitution
 
    # 单项式 y 移位列表
    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            monomials.append(u^kk * y^jj)
 
    # 构造格 B
    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)")
 
    # display the lattice basis
    if debug:
        matrix_overview(BB, modulus^mm)
 
    # LLL
    if debug:
        print ("optimizing basis of the lattice via LLL, this can take a long time")
 
    #BB = BB.BKZ(block_size=25)
    BB = BB.LLL()
 
    if debug:
        print ("LLL is done!")
 
    # 替换向量 i 和 j ->多项式 1 和 2
    if debug:
        print ("在格中寻找线性无关向量")
    found_polynomials = False
 
    for pol1_idx in range(nn - 1):
        for pol2_idx in range(pol1_idx + 1, nn):
 
            # 对于i and j, 构造两个多项式
 
            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)
 
    # solutions
    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 =time.perf_counter
    start =time.clock()
    size=512
    length_N = 2*size;
    ss=0
    s=70
    M=1   # the number of experiments
    delta = 299/1024
    # p =  random_prime(2^512,2^511)
    for i in range(M):
#         p =  random_prime(2^size,None,2^(size-1))
#         q =  random_prime(2^size,None,2^(size-1))
#         if(p<q):
#             temp=p
#             p=q
#             q=temp
        N = 73787944575265560659337066998651559854008554735456318333076159883563615536562553619509791556832630227860528135540580555475313775587694656733939337337162684083504013096398383073623252469953554083296109377792508578226035938969407231689553680824348024184291021105154956244179599769690508760502010020180061720019
        e = 29567393844922147731100606267534953994449203725806042726345753844983783164567752859600595704301680439820601788437000356006329166887506988972343037285018001864800437750191409728833296698465447150521119258782212680439802048101817052671603259114861564484544609221844909301043673563931709693327971992359139371227
        c = 45450360465574139870481845301350579669043708378076876540990465420189044791001300484095663295849190297258585508686905534568744689506644183459090297899984297370341547866178062353877908003401151052692574668213473397829536065790283637478791675039086877921443504800597649778898977086137114431286134700385182325815
        hint1 = 954676601865566077628  # p高位
        hint2 = 599256795156046227992  # q高位
#         print ("p真实高",s,"比特：", int(p/2^(512-s)))
#         print ("q真实高",s,"比特：", int(q/2^(512-s)))
 
#         N = p*q;
 
 
    # 解密指数d的指数( 最大0.292)
 
 
 
        m = 7   # 格大小（越大越好/越慢）
        t = round(((1-2*delta) * m))  # 来自 Herrmann 和 May 的优化
        X = floor(N^delta)  # 
        Y = floor(N^(1/2)/2^s)    # 如果 p、 q 大小相同，则正确
        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);
        #A = N+1
            P.<x,y> = PolynomialRing(ZZ)
            pol = 1 + x * (A + y)  #构建的方程
 
            # Checking bounds
            #if debug:
                #print ("=== 核对数据 ===")
                #print ("* delta:", delta)
                #print ("* delta < 0.292", delta < 0.292)
                #print ("* size of e:", ceil(log(e)/log(2)))  # e的bit数
                # print ("* size of N:", len(bin(N)))          # N的bit数
                #print ("* size of N:", ceil(log(N)/log(2)))  # N的bit数
                #print ("* m:", m, ", t:", t)
 
            # boneh_durfee
            if debug:
                ##print ("=== running algorithm ===")
                start_time = time.time()
 
 
            solx, soly = boneh_durfee(pol, e, m, t, X, Y)
 
 
            if solx > 0:
                #print ("=== solution found ===")
                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))
            #break
        print("ss=",ss)
                            #end=time.process_time
        end=time.clock()
        print('Running time: %s Seconds'%(end-start))
if __name__ == "__main__":
    example()  

这个脚本是基于人家实验的，有点乱

跑出d之后解RSA

d = 687038469975940863290260221773243585573217566356221334458982642899243861704377289553340363
n = 73787944575265560659337066998651559854008554735456318333076159883563615536562553619509791556832630227860528135540580555475313775587694656733939337337162684083504013096398383073623252469953554083296109377792508578226035938969407231689553680824348024184291021105154956244179599769690508760502010020180061720019
c = 45450360465574139870481845301350579669043708378076876540990465420189044791001300484095663295849190297258585508686905534568744689506644183459090297899984297370341547866178062353877908003401151052692574668213473397829536065790283637478791675039086877921443504800597649778898977086137114431286134700385182325815

m = pow(c,d,n)
print(bytes.fromhex(hex(m)[2:]))
# wdflag{39769372-2155-4c99-9ec2-6683c4451ed6}

Crypto02

task.py

# 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 = 80932673752923845218731053671144903633094494351596082125742241568755353762809
# r2 = 80932673752923845218731053671144903633094494351596082125742241568755353762809
# s1 = 11239004842544045364097722042148768449026688243093666008376082303522447245154
# s2 = 97301123368608673469588981075767011435222146576812290449372049839046298462487
# z1 = 84483328065344511722319723339101492661376118616972408250436525496870397932079
# z2 = 114907157406602520059145833917511615616817014350278499032611638874752053304591
# ('Encrypted flag (AES in CBC mode, hex):', u'd8851c55edec1114a6d7a4d6d5efbba4611a39216ec146d2e675194dd0d5f768bee1b09799a133ffda1d283c4f6db475834cbe52c38c88736c94795c137490be')

首先是ECDSA签名k的复用，原理如下
$$
s_1 \equiv k^{-1}(z_1 + r_1d_A) \mod n
$$

$$
s_2 \equiv k^{-1}(z_2 + r_2d_A) \mod n
$$

这里$r_1 = r_2$，所以两式相减有
$$
s_1 - s_2 \equiv k^{-1}(z_1-z_2) \mod n
$$
所以
$$
k \equiv (z_1-z_2)\times (s_1-s_2)^{-1} \mod n
$$
有了k之后根据$s\equiv k^{-1}(z + rd_A)\mod n$就可以恢复$d_A$

然后解CBC得到victory_encrypted_flag

再根据加密逻辑写一个解密代码即可，最后把大写符号改为小写符号

exp

from Crypto.Cipher import AES
from Crypto.Util.number import *
import gmpy2
from hashlib import *
from Crypto.Util.Padding import unpad

def victory_decrypt(ciphertext, key):
    key = key.upper()
    key_length = len(key)
    m = ""
    for i,char in enumerate(ciphertext):
        if ord('A') <= char <= ord('Z') or ord('a') <= char <= ord('z'):
            shift = ord(key[i % key_length]) - ord('A')
            tmp = chr((char - ord('A') - shift) % 26 + ord('A'))
            m += tmp
        else:
            m += chr(char)
    return m

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
a = 0
b = 7
xG = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
yG = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
G = (xG, yG)
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
r1 = 80932673752923845218731053671144903633094494351596082125742241568755353762809
r2 = 80932673752923845218731053671144903633094494351596082125742241568755353762809
s1 = 11239004842544045364097722042148768449026688243093666008376082303522447245154
s2 = 97301123368608673469588981075767011435222146576812290449372049839046298462487
z1 = 84483328065344511722319723339101492661376118616972408250436525496870397932079
z2 = 114907157406602520059145833917511615616817014350278499032611638874752053304591
victory_key = "WANGDINGCUP"

c = bytes.fromhex("d8851c55edec1114a6d7a4d6d5efbba4611a39216ec146d2e675194dd0d5f768bee1b09799a133ffda1d283c4f6db475834cbe52c38c88736c94795c137490be")

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

d = ((k * s1) - z1)*r_ % n

key = sha256(long_to_bytes(d)).digest()
iv = c[:16]
encrypted_flag = c[16:]
cipher = AES.new(key, AES.MODE_CBC,iv)
decrypted_flag = cipher.decrypt(encrypted_flag)
print(decrypted_flag)
flag = victory_decrypt(unpad(decrypted_flag,16),victory_key)
print(flag)
# WDFLAG{27F8DECFDB040ABB2D0DDBA70AD0484D}
print(flag.lower())
# wdflag{27f8decfdb040abb2d0ddba70ad0484d}

白虎组

Crypto01

task.py

from sage.all import *
from Crypto.Util.number import *

block_size = 64
rounds = 14

P_permutation = Permutations(list(range(block_size))).random_element()
inverse_P_permutation = [P_permutation.index(i) for i in range(block_size)]

MASK = 0b1110001001111001000110010000100010101111101100101110100001001001
IV = 7

b2i = lambda x: Integer(sum([x[i] * 2**i for i in range(len(x))]))

def pad(x):
    padlen = block_size - len(x) % block_size
    return x + bytes([padlen] * padlen)

def P(x):
    bit_x = x.bits()
    if len(bit_x) < block_size:
        bit_x.extend([0] * (block_size - len(bit_x)))
    bit_x = [bit_x[P_permutation[i]] for i in range(block_size)]
    return b2i(bit_x)

def P_inv(x):
    bit_x = x.bits()
    if len(bit_x) < block_size:
        bit_x.extend([0] * (block_size - len(bit_x)))
    bit_x = [bit_x[inverse_P_permutation[i]] for i in range(block_size)]
    return b2i(bit_x)

def S(x):
    x1 = x
    x2 = x << IV & MASK
    x3 = x << IV & ((1 << block_size) - 1) | MASK
    return x1 ^ x2 ^ x3

def encrypt(message_block, key):
    ret = message_block
    for i in range(rounds):
        ret = P_inv(S(P(ret)) ^ key)
    return ret

from secret import flag
from hashlib import md5

message = pad(flag)
message = [Integer(bytes_to_long(message[i:i+8])) for i in range(0, len(message), 8)]

key = int(md5(flag).hexdigest(), 16) & ((1 << block_size) - 1)

ciphertext = [encrypt(m, key) for m in message]

print(ciphertext)
print(P_permutation)
"""
[]
[]
"""

这题主要是encrypt中14轮ret = P_inv(S(P(ret)) ^ key)的迭代，逐一分析P(x),S(x),P_inv(x)

可以知道P(x)和P_inv(x)就是单纯的置换。可以把置换用矩阵的形式表达
$$
P(x) =
\begin{pmatrix}
P_{1,1} & … & P_{1,64}\
\vdots & \ddots & \vdots \
P_{64,1} & … & P_{64,64}
\end{pmatrix}
\times
\begin{pmatrix}
x_1 & … & x_{64}
\end{pmatrix}
$$

P_matrix = matrix(GF(2),64,64)
for i, perm_index in enumerate(P_permutation):
    P_matrix[i,perm_index] = 1
    
def P(x):
    bit_x = x.bits()
    if len(bit_x) < block_size:
        bit_x.extend([0] * (block_size - len(bit_x)))
    bit_x = P_matrix * vector(GF(2),bit_x)
    return b2i(vector(ZZ,bit_x).list())

这样就用矩阵的形式等效替代了原来的P(x)

同理P_inv就很简单了，用$P^{-1}$乘上$x$向量就好了

def P_inv(x):
    bit_x = x.bits()
    if len(bit_x) < block_size:
        bit_x.extend([0] * (block_size - len(bit_x)))
    bit_x = P_matrix^(-1) * vector(GF(2),bit_x)
    return b2i(vector(ZZ,bit_x).list())

接下来分析S(x)

def S(x):
    x1 = x
    x2 = x << IV & MASK
    x3 = x << IV & ((1 << block_size) - 1) | MASK
    return x1 ^ x2 ^ x3

这里的x3其实等效于x3 = x << IV & ((1 << block_size) - 1)

此时S(x)中只有&和^两个运算。我们可以用GF(2)下的矩阵乘法表示&，用GF(2)下的加法表示^，那么就有
$$
S(x) =\begin{pmatrix}
A_{1,1} & … & A_{1,64}\
\vdots & \ddots & \vdots \
A_{64,1} & … & A_{64,64}
\end{pmatrix}
\times
\begin{pmatrix}
x_1 & … & x_{64}
\end{pmatrix}
+
\begin{pmatrix}
b_1 & … & b_{64}
\end{pmatrix}
$$

A = matrix(GF(2),64,64)
for i in range(64):
    A[i,i] = 1
    
for i in range(64):
    j = i - IV
    if j >= 0:
        A[i,j] = 1

b = vector(GF(2),64)
for i in range(64):
    if (MASK >> i) & 1:
        b[i] = 1

def S(x):
    bit_x = x.bits()
    if len(bit_x) < block_size:
        bit_x.extend([0] * (block_size - len(bit_x)))
    bit_x = vector(GF(2),bit_x)
    res = A * bit_x + b
    return b2i(vector(ZZ,res))

目前为止我们已经用矩阵的形式表示了三个函数

再看加密函数

def encrypt(message_block, key):
    ret = message_block
    for i in range(rounds):
        ret = P_inv(S(P(ret)) ^ key)
    return ret

^key可以看作再加上一个k向量,k是key的二进制形式

一轮加密：
$$
ret = P^{-1}(A(Px) + b + k)
$$
展开有
$$
ret = P^{-1}APx + P^{-1}b + P^{-1}k
$$
记$T = P^{-1}AP$,$U = P^{-1}b$。那么14轮加密后
$$
ret = T^{14}x + (T^{13}+T^{12} +…+I)U + (T^{13}+T^{12} +…+I)P^{-1}k
$$
注意到加密的时候是把flag的每八位进行分组之后再加密。那我们可以利用flag头wdflag{，再爆破一位，即可获得第一组明文(此外,密文的最后两个值是一样的，可以说明后面两组明文是填充，也可以爆破填充内容来获得另外的明密文对，都可以解得k)。那么对于上面的式子，我们只有k是未知的，可以解矩阵方程得到k
$$
k = (T^{13}+T^{12} +…+I)^{-1}P[ret - T^{14}x -(T^{13}+T^{12} +…+I)U]
$$
求得k之后再解密即可

利用flag头

from Crypto.Util.number import *

cipher = 
P_permutation = 
block_size = 64
rounds = 14

inverse_P_permutation = [P_permutation.index(i) for i in range(block_size)]

MASK = 0b1110001001111001000110010000100010101111101100101110100001001001
IV = 7

b2i = lambda x: Integer(sum([x[i] * 2**i for i in range(len(x))]))

P_matrix = matrix(GF(2),64,64)
for i, perm_index in enumerate(P_permutation):
    P_matrix[i,perm_index] = 1

def P(x):
    bit_x = x.bits()
    if len(bit_x) < block_size:
        bit_x.extend([0] * (block_size - len(bit_x)))
    bit_x = P_matrix * vector(GF(2),bit_x)
    return b2i(vector(ZZ,bit_x).list())

def P_inv(x):
    bit_x = x.bits()
    if len(bit_x) < block_size:
        bit_x.extend([0] * (block_size - len(bit_x)))
    bit_x = P_matrix^(-1) * vector(GF(2),bit_x)
    return b2i(vector(ZZ,bit_x).list())

A = matrix(GF(2),64,64)
for i in range(64):
    A[i,i] = 1
    
for i in range(64):
    j = i - IV
    if j >= 0:
        A[i,j] = 1

b = vector(GF(2),64)
for i in range(64):
    if (MASK >> i) & 1:
        b[i] = 1

def S(x):
    bit_x = x.bits()
    if len(bit_x) < block_size:
        bit_x.extend([0] * (block_size - len(bit_x)))
    bit_x = vector(GF(2),bit_x)
    res = A * bit_x + b
    return b2i(vector(ZZ,res))


T = P_matrix^(-1)*A*P_matrix
U = P_matrix^(-1)*b
tmp = sum(T^i for i in range(rounds))

keys=[]
for i in "0123456789abcdef":
    c = cipher[0].bits()
    while len(c) != 64:
        c += [0]
    c = vector(GF(2),c)
    m = b"wdflag{" + i.encode()
    x = Integer(bytes_to_long(m)).bits()
    while len(x) != 64:
        x += [0]
    x = vector(GF(2),x)
    c -= T^rounds * x
    c -= tmp*U
    try:    
        P_invk = tmp.solve_right(c)
        k = P_matrix*P_invk
        key = sum([int(k[j])*2^j for j in range(len(k))])
        keys.append(key)
    except:
        pass
    
def decrypt(c,key):
    ret = c.bits()
    k = key.bits()
    while len(ret) != 64:
        ret += [0]
    while len(k) != 64:
        k += [0]
    ret = vector(GF(2),ret)
    k = vector(GF(2),k)
    ret -= tmp * P_matrix^(-1) * k
    ret -= (tmp * U)
    x = (T^14)^(-1) * ret
    m = long_to_bytes(b2i(vector(ZZ,x)))
    return m

for key in keys:
    m = [decrypt(c,key) for c in cipher]
    flag = b""
    for i in m:
        flag += i
    print(flag)

爆破填充内容

from Crypto.Util.number import *

cipher = []
P_permutation = []
block_size = 64
rounds = 14

inverse_P_permutation = [P_permutation.index(i) for i in range(block_size)]

MASK = 0b1110001001111001000110010000100010101111101100101110100001001001
IV = 7

b2i = lambda x: Integer(sum([x[i] * 2**i for i in range(len(x))]))

P_matrix = matrix(GF(2),64,64)
for i, perm_index in enumerate(P_permutation):
    P_matrix[i,perm_index] = 1

def P(x):
    bit_x = x.bits()
    if len(bit_x) < block_size:
        bit_x.extend([0] * (block_size - len(bit_x)))
    bit_x = P_matrix * vector(GF(2),bit_x)
    return b2i(vector(ZZ,bit_x).list())

def P_inv(x):
    bit_x = x.bits()
    if len(bit_x) < block_size:
        bit_x.extend([0] * (block_size - len(bit_x)))
    bit_x = P_matrix^(-1) * vector(GF(2),bit_x)
    return b2i(vector(ZZ,bit_x).list())

A = matrix(GF(2),64,64)
for i in range(64):
    A[i,i] = 1
    
for i in range(64):
    j = i - IV
    if j >= 0:
        A[i,j] = 1

b = vector(GF(2),64)
for i in range(64):
    if (MASK >> i) & 1:
        b[i] = 1

def S(x):
    bit_x = x.bits()
    if len(bit_x) < block_size:
        bit_x.extend([0] * (block_size - len(bit_x)))
    bit_x = vector(GF(2),bit_x)
    res = A * bit_x + b
    return b2i(vector(ZZ,res))


T = P_matrix^(-1)*A*P_matrix
U = P_matrix^(-1)*b
tmp = sum(T^i for i in range(rounds))

keys=[]
for i in range(1,32):
    c = cipher[-1].bits()
    while len(c) != 64:
        c += [0]
    c = vector(GF(2),c)
    m = bytes([i]) * 8
    x = Integer(bytes_to_long(m)).bits()
    while len(x) != 64:
        x += [0]
    x = vector(GF(2),x)
    c -= T^rounds * x
    c -= tmp*U
    try:    
        P_invk = tmp.solve_right(c)
        k = P_matrix*P_invk
        key = sum([int(k[j])*2^j for j in range(len(k))])
        keys.append(key)
    except:
        pass
    
def decrypt(c,key):
    ret = c.bits()
    k = key.bits()
    while len(ret) != 64:
        ret += [0]
    while len(k) != 64:
        k += [0]
    ret = vector(GF(2),ret)
    k = vector(GF(2),k)
    ret -= tmp * P_matrix^(-1) * k
    ret -= (tmp * U)
    x = (T^14)^(-1) * ret
    m = long_to_bytes(b2i(vector(ZZ,x)))
    return m

for key in keys:
    m = [decrypt(c,key) for c in cipher]
    flag = b""
    for i in m:
        flag += i
    print(flag)

Crypto02

task.py

from Crypto.Util.number import getPrime, isPrime, GCD, inverse

nbits = 2048
gbits = 1000
g = getPrime(int(gbits))
while True:
    a = getPrime(int(nbits*0.5)-gbits)
    p = 2*g*a + 1
    if isPrime(p):
        break

while True:
    b = getPrime(int(nbits*0.5)-gbits)
    q = 2*g*b + 1
    if p!=q and isPrime(q):
        break
N = p*q
e = 65537

def str2int(s):
    return int(s.encode('latin-1').hex(),16)

def int2str(i):
    tmp=hex(i)[2:]
    if len(tmp)%2==1:
        tmp='0'+tmp
    return bytes.fromhex(tmp).decode('latin-1')

with open('pubkey.txt','w') as f:
    f.write(str(e)+'\n')
    f.write(str(N)+'\n')

with open('flag.txt') as f:
    plain = str2int(f.read())

c = pow(plain,e,N)
with open('cipher.txt','wb') as f:
    f.write(int2str(c).encode('latin-1'))

根据p,q的生成方式(Pollard’s ρ algorithm)，可以找到博客[密码学学习笔记 之 浅析Pollard’s rho algorithm及其应用 | Van1sh的小屋](https://jayxv.github.io/2019/11/11/密码学学习笔记之浅析Pollard's rho algorithm及其应用/)

基本上算是原题，拿博客的板子打就好了

exp

from Crypto.Util.number import *

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

def mapx(x):
    x=(pow(x,n-1,n)+3)%n    #pow(x,n-1,n)是为了减小数值，加速运算，
    return x

def pollard_rho(x1,x2):
    while True:
        x1=mapx(x1)
        x2=mapx(mapx(x2))
        p=gcd(x1-x2,n)
        if (p == n):
            print("fail")
            return
        elif (p!=1):
            print("p: "+str(p))
            print("q: "+str(n // p))
            return p,n // p

n = 49025724928152491719950645039355675823887062840095001672970308684156817293484070166684235178364916522473822184239221170514602692903302575847326054102901449806271709230774063675539139201327878971370342483682454617270705142999317092151456200639975738970405158598235961567646064089356496022247689989925574384915789399433283855087561428970245448888799812611301566886173165074558800757040196846800189738355799057422298556992606146766063202605288257843684190291545600282197788724944382475099313284546776350595539129553760118549158103804149179701853798084612143809757187033897573787135477889183344944579834942896249251191453
p,q = pollard_rho(1,1)

c = open("cipher.txt",'rb').read()
c = int(c.hex(),16)

d = inverse(65537,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m).decode())

朱雀组

Crypto01——unsolved

easy_MNTRU.py

from sage.all import *
from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler
from secret import flag

std_limit = 0.01


def get_accurate_Discrete_Gaussian(sigma, limit=std_limit):
    factor = 1
    while True:
        Df = DiscreteGaussianDistributionIntegerSampler(sigma * factor)
        if abs(RR(std([Df() for _ in range(2 ** 15)])) - sigma) / sigma < limit:
            return Df
        factor += 0.01


def ZZ_to_Fq(_vector, _q, _n):
    return [int(i % _q) if abs(_q - int(i % _q)) > int(i % _q) else (int(i % _q) - _q) for i in _vector] + [0] * (
            _n - len(_vector))


def My_generator(Sampler, _n, limit=std_limit):
    while True:
        tmp = [Sampler() for _ in range(_n)]
        if abs(RR(std(tmp)) - Sampler.sigma) < limit:
            return tmp


def generate_key():
    while True:
        F = Matrix([[PRz(My_generator(Df, d)) for _ in range(n)] for _ in range(n)])
        G = Matrix([[PRz(My_generator(Df, d)) for _ in range(k)] for _ in range(n)])
        try:
            H = F.change_ring(PRqm).inverse() * G.change_ring(PRqm)
            H = Matrix([[PRz(Hij.lift()) for Hij in Hi] for Hi in H.transpose()]).transpose()
            return F, G, H
        except ArithmeticError:
            continue


d = 64
q = 12289
p = 17
n = 2
k = 1
sigma_f, sigma_s, sigma_e = 0.4, 0.6, 0.6

PRq = PolynomialRing(Zmod(q), 'xq')
PRp = PolynomialRing(Zmod(p), 'xp')
PRz = PolynomialRing(ZZ, 'xz')
mod_polynomial = PRz.cyclotomic_polynomial(d * 2)
PRqm = PRq.quotient(mod_polynomial)
PRpm = PRp.quotient(mod_polynomial)
Df = get_accurate_Discrete_Gaussian(sigma_f)
Ds = get_accurate_Discrete_Gaussian(sigma_s)
De = get_accurate_Discrete_Gaussian(sigma_e)
m = []
base = int.from_bytes(flag, byteorder='big')
while base > 0:
    m.append(int(base % p))
    base = base // p
m = PRz(m)

s = vector([PRz(My_generator(Ds, d)) for _ in range(n)])
e = PRz(My_generator(Ds, d))
open('data.txt', 'w').write('H = ' + str([list(vi) for vi in H]) + '\n' + 'c = ' + str(c) + '\n')
"""
H = [[10164*xz^63 + 9000*xz^62 + 8286*xz^61 + 5227*xz^60 + 6181*xz^59 + 5761*xz^58 + 7446*xz^57 + 10719*xz^56 + 12069*xz^55 + 934*xz^54 + 7301*xz^53 + 10310*xz^52 + 3397*xz^51 + 474*xz^50 + 4342*xz^49 + 11687*xz^48 + 3326*xz^47 + 10295*xz^46 + 4112*xz^45 + 12233*xz^44 + 9436*xz^43 + 2831*xz^42 + 6611*xz^41 + 7190*xz^40 + 4559*xz^39 + 5945*xz^38 + 9605*xz^37 + 8836*xz^36 + 7632*xz^35 + 11091*xz^34 + 11966*xz^33 + 6096*xz^32 + 4209*xz^31 + 8470*xz^30 + 3059*xz^29 + 1260*xz^28 + 131*xz^27 + 6057*xz^26 + 4237*xz^25 + 6208*xz^24 + 3906*xz^23 + 9797*xz^22 + 11804*xz^21 + 8216*xz^20 + 4697*xz^19 + 9711*xz^18 + 10839*xz^17 + 2198*xz^16 + 9361*xz^15 + 10790*xz^14 + 2727*xz^13 + 7269*xz^12 + 10677*xz^11 + 12195*xz^10 + 11451*xz^9 + 752*xz^8 + 1282*xz^7 + 2990*xz^6 + 4491*xz^5 + 5352*xz^4 + 3448*xz^3 + 7551*xz^2 + 4702*xz + 427], [2097*xz^63 + 5773*xz^62 + 9022*xz^61 + 8544*xz^60 + 10555*xz^59 + 12163*xz^58 + 514*xz^57 + 5992*xz^56 + 2822*xz^55 + 7486*xz^54 + 9950*xz^53 + 6333*xz^52 + 8917*xz^51 + 4097*xz^50 + 11713*xz^49 + 7495*xz^48 + 1989*xz^47 + 10468*xz^46 + 3808*xz^45 + 5333*xz^44 + 1184*xz^43 + 6871*xz^42 + 4944*xz^41 + 630*xz^40 + 4644*xz^39 + 5582*xz^38 + 2200*xz^37 + 2970*xz^36 + 11908*xz^35 + 1946*xz^34 + 9833*xz^33 + 4771*xz^32 + 652*xz^31 + 3287*xz^30 + 2660*xz^29 + 5133*xz^28 + 6935*xz^27 + 2833*xz^26 + 10788*xz^25 + 12068*xz^24 + 362*xz^23 + 7765*xz^22 + 11454*xz^21 + 6499*xz^20 + 8140*xz^19 + 9100*xz^18 + 1642*xz^17 + 3282*xz^16 + 2028*xz^15 + 3867*xz^14 + 6458*xz^13 + 7408*xz^12 + 2944*xz^11 + 12257*xz^10 + 9911*xz^9 + 6711*xz^8 + 11102*xz^7 + 5603*xz^6 + 2554*xz^5 + 298*xz^4 + 9782*xz^3 + 1928*xz^2 + 2535*xz + 3668]]
c = 6085*xz^63 + 9658*xz^62 + 8682*xz^61 + 2660*xz^60 + 9268*xz^59 + 8059*xz^58 + 6842*xz^57 + 7810*xz^56 + 9166*xz^55 + 10543*xz^54 + 5037*xz^53 + 624*xz^52 + 8735*xz^51 + 7393*xz^50 + 1587*xz^49 + 11955*xz^48 + 9867*xz^47 + 8488*xz^46 + 6883*xz^45 + 8323*xz^44 + 4607*xz^43 + 195*xz^42 + 1357*xz^41 + 4753*xz^40 + 2225*xz^39 + 6728*xz^38 + 9472*xz^37 + 5292*xz^36 + 1132*xz^35 + 8998*xz^34 + 7379*xz^33 + 3055*xz^32 + 4360*xz^31 + 5320*xz^30 + 10615*xz^29 + 7225*xz^28 + 9062*xz^27 + 2879*xz^26 + 2527*xz^25 + 7636*xz^24 + 6341*xz^23 + 456*xz^22 + 1517*xz^21 + 10366*xz^20 + 5444*xz^19 + 2507*xz^18 + 8567*xz^17 + 12055*xz^16 + 6353*xz^15 + 8241*xz^14 + 7436*xz^13 + 11704*xz^12 + 5722*xz^11 + 3808*xz^10 + 11866*xz^9 + 4663*xz^8 + 11430*xz^7 + 7288*xz^6 + 9504*xz^5 + 10292*xz^4 + 1089*xz^3 + 6380*xz^2 + 6417*xz + 1991
"""

Crypto02

各位朱雀组参赛选手请注意，平台新增“CRYPTO02”赛题提示：
提示信息如下：请根据提示信息进一步完成解题。

（1）RSA模数 n：

0x00b8cb1cca99b6ac41876c18845732a5cbfc875df346ee9002ce608508b5fcf6b60a5ac7722a2d64ef74e1443a338e70a73e63a303f3ac9adf198595699f6e9f30c009d219c7d98c4ec84203610834029c79567efc08f66b4bc3f564bfb571546a06b7e48fb35bb9ccea9a2cd44349f829242078dfa64d525927bfd55d099c024f

（2）素数 p 的高位：

0xe700568ff506bd5892af92592125e06cbe9bd45dfeafe931a333c13463023d4f0000000000000000000000000000000000000000000000000000000000000000

（3）加密指数 e：

0x10001

（4）加密消息文件：flag.enc，你需要读取并解密此文件。

你的任务是通过给定的信息恢复素数 p，计算私钥 d，并解密加密消息以获得 flag。@全体成员 

flag.enc

p7盡債3噮?%H仧?C垂粂跈[羀鮟zi盐誗迉??U<§鄡7-筙
党
猑徽狶€W?5醭*輑8' ?噉H传丏朠	颬/?w?鎬袆4技E\爙d?萘緍僞tx>?

给出p的高256位，爆8位coppersmith

exp

from Crypto.Util.number import *
from tqdm import trange
import gmpy2

n = 0x00b8cb1cca99b6ac41876c18845732a5cbfc875df346ee9002ce608508b5fcf6b60a5ac7722a2d64ef74e1443a338e70a73e63a303f3ac9adf198595699f6e9f30c009d219c7d98c4ec84203610834029c79567efc08f66b4bc3f564bfb571546a06b7e48fb35bb9ccea9a2cd44349f829242078dfa64d525927bfd55d099c024f
p_high = 0xe700568ff506bd5892af92592125e06cbe9bd45dfeafe931a333c13463023d4f
pbits = 512
e = 0x10001
c = bytes_to_long(open('flag.enc','rb').read())


for i in trange(2**8):
     p4 = p_high<<8			#这里需要先爆破8位，使得知道264位以后再恢复p
     p4 = p4 + i
     kbits = pbits - p4.nbits()
     p4 = p4 << kbits
     R.<x> = PolynomialRing(Zmod(n))
     f = x + p4
     x = f.small_roots(X=2^kbits, beta=0.4, epsilon=0.01)
     if x:
         p = p4 + int(x[0])
         q = n // p
         d = gmpy2.invert(e,(p-1)*(q-1))
         m = pow(c,d,n)
         print(long_to_bytes(int(m)))
         break

Crypto03

task.py

#!/usr/bin/env python3

import random
from sympy import nextprime
from gmpy2 import is_prime
from Crypto.Util.number import getPrime, bytes_to_long
from Secret import flag

m = bytes_to_long(flag)

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 2999

f = open("out.txt", 'w')

p1 = getPrime(1024)
q1 = nextprime(2024 * p1)
n1 = p1 * q1
f.write("n1 = {0}\n".format(n1))

p2 = getPrime(1024)
q2 = 1
while q2 < p2:
    q2 = getPrime(1024)
n2 = p2 * q2
n22 = p2 * p2 + q2 * q2
f.write("n2 = {0}\n".format(n2))
f.write("n22 = {0}\n".format(n22))

r = random.getrandbits(1024)
p3 = r
while not is_prime(p3):
    p3 += random.getrandbits(400)
q3 = r
while q3 < p3:
    q3 += random.getrandbits(500)
while not is_prime(p3):
    q3 += random.getrandbits(500)
n3 = p3 * q3
f.write("n3 = {0}\n".format(n3))

m1 = p1 * m * m + p2 * m + p3
m2 = q1 * m * m + q2 * m + q3
c1 = pow(m1, e, n)
c2 = pow(m2, e, n)

f.write("n = {0}\n".format(n))
f.write("c1 = {0}\n".format(c1))
f.write("c2 = {0}\n".format(c2))
"""
n1 = 
n2 = 
n22 = 
n3 = 
n = 
c1 = 
c2 = 
"""

part1

第一部分
$$
n_1 = p\times (2024p + x)
$$
把n1 // 2024开根号，爆破一点即可分解n1

part2

第二部分，利用下面两个式子分解n2
$$
n_2 = p\times q
$$

$$
n_{22} = p^2 + q^2
$$

那么有
$$
p+q = \sqrt{n_{22}+ 2n_2}
$$

$$
p-q = \sqrt{n_{22}- 2n_2}
$$

part3

经过测试

记t = gmpy2.iroot(n3,2)[0]，会发现要么p3 + q3 = 2 * t，要么p3 + q3 = 2*t + 1

那么我们就有了p3 + q3，这很容易就能分解出p3,q3了。

但实际的使用利用的等式是p3 * q3 == n3，p3 + q3 == 2*t + 2有点奇怪

三个n都分解了之后用相关消息攻击，e为2999，比较大，用H-GCD

exp

from Crypto.Util.number import *
import gmpy2
import sys

def HGCD(a, b):
    if 2 * b.degree() <= a.degree() or a.degree() == 1:
        return 1, 0, 0, 1
    m = a.degree() // 2
    a_top, a_bot = a.quo_rem(x^m)
    b_top, b_bot = b.quo_rem(x^m)
    R00, R01, R10, R11 = HGCD(a_top, b_top)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    q, e = c.quo_rem(d)
    d_top, d_bot = d.quo_rem(x^(m // 2))
    e_top, e_bot = e.quo_rem(x^(m // 2))
    S00, S01, S10, S11 = HGCD(d_top, e_top)
    RET00 = S01 * R00 + (S00 - q * S01) * R10
    RET01 = S01 * R01 + (S00 - q * S01) * R11
    RET10 = S11 * R00 + (S10 - q * S11) * R10
    RET11 = S11 * R01 + (S10 - q * S11) * R11
    return RET00, RET01, RET10, RET11
    
def GCD(a, b):
    print(a.degree(), b.degree())
    q, r = a.quo_rem(b)
    if r == 0:
        return b
    R00, R01, R10, R11 = HGCD(a, b)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    if d == 0:
        return c.monic()
    q, r = c.quo_rem(d)
    if r == 0:
        return d
    return GCD(d, r)

sys.setrecursionlimit(500000)

n1 = 
n2 = 
n22 = 
n3 = 
n = 
c1 = 
c2 = 
e = 2999

# factor n1
t1 = gmpy2.iroot(n1 // 2024,2)[0]
for i in range(-100000,100000):
    p1 = t1 + i
    if n1 % p1 == 0:
        q1 = n1 // p1
        break
if p1 > q1:
    p1,q1 = q1,p1

# factor n2
p_add_q = gmpy2.iroot(n22 + 2*n2,2)[0]
p_sub_q = gmpy2.iroot(n22 - 2*n2,2)[0]
p2 = (p_add_q + p_sub_q) // 2
q2 = n2 // p2

if p2 > q2:
    p2,q2 = q2,p2
    
# factor n3
t3 = 2*gmpy2.iroot(n3,2)[0] + 2
p_add_q = t3
p_sub_q = gmpy2.iroot((p_add_q)**2 - 4*n3,2)[0]
p3 = (p_add_q + p_sub_q) // 2
q3 = (p_add_q - p_sub_q) // 2

if p3 > q3:
    p3,q3 = q3,p3

p1,q1 = int(p1),int(q1)
p2,q2 = int(p2),int(q2)
p3,q3 = int(p3),int(q3)

###### Franklin-Reiter
R.<x> = PolynomialRing(Zmod(n))
f = (p1 * x * x + p2 * x + p3)^e - c1
g = (q1 * x * x + q2 * x + q3)^e - c2

res = GCD(f,g)

m = -res.monic().coefficients()[0]
print(m)
flag = long_to_bytes(int(m))
print(flag)

玄武组

Crypto01——unsolved

task.sage

# SageMath version 10.0, Release Date: 2023-05-20

from sage.all import *
from Crypto.Util.number import *

from secret import flag
flag = flag.lstrip(b"wdflag{").rstrip(b"}")

class ShamirSS:
    def __init__(self, coefs, value):
        self.coefs = coefs
        self.value = value

class ShamirProtocol:
    def __init__(self, n_players, threshold, modulus):
        self.n_players = n_players
        self.threshold = threshold
        
        assert isPrime(modulus), "Modulus must be a prime number"
        self.modulus = modulus
        
        
    def input_share(self, values):
        coefs = [
            [getRandomRange(1, self.modulus) for _ in range(self.threshold)]
            for _ in range(self.n_players)
        ]

        randoms = values + [getRandomRange(1, self.modulus) for _ in range(self.threshold - len(values))]

        values = [
            sum([r * c for r, c in zip(randoms, coef)]) % self.modulus
            for coef in coefs
        ]

        shares = [ShamirSS(coef, value) for coef, value in zip(coefs, values)]
        return shares
    


protocol = ShamirProtocol(len(flag), len(flag) * 2, 257)
values = list(flag)

import os
os.mkdir("shares")

for i in range(10000):
    shares = protocol.input_share(values)
    save(shares, f"shares/share_{i}.sobj")

shares数据太大

Crypto02

main.py

from Crypto.PublicKey import RSA
from Crypto.Cipher import AES
from pkcs1 import encode, decode
import os
import hashlib
import signal


FLAG = os.getenv("FLAG", "wdflag{******************************}")

class RSA_OT:
    
    def __init__(self, key: RSA):
        self.key = key
        self.n = key.n
        self.e = key.e
        self.d = key.d
        self.nbyte = key.size_in_bytes()
        
    @staticmethod
    def new(nbits: int) -> "RSA_OT":
        key = RSA.generate(nbits)
        return RSA_OT(key)
        
    def encrypt(self, message: bytes) -> bytes:
        padded = encode(message, self.nbyte)
        ct = self.key._encrypt(padded)
        return int(ct).to_bytes(self.nbyte, "big")
    
    def decrypt(self, ciphertext: bytes) -> bytes:
        padded = self.key._decrypt(int.from_bytes(ciphertext, "big"))
        return decode(padded)
    
    def show_public_key(self):
        print("[+] n =", self.n)
        print("[+] e =", self.e)
        
    def run(self, m0, m1):
        print("[+] OT Protocol Starts")
        m0 = int.from_bytes(encode(m0, self.nbyte), "big")
        m1 = int.from_bytes(encode(m1, self.nbyte), "big")
        x0 = int.from_bytes(os.urandom(self.nbyte), "big") % self.n
        x1 = int.from_bytes(os.urandom(self.nbyte), "big") % self.n
        print(f"[+] x0 = {x0}")
        print(f"[+] x1 = {x1}")
        v = int(input("[+] v = "))
        M0 = (m0 + pow(v - x0, self.d, self.n)) % self.n
        M1 = (m1 + pow(v - x1, self.d, self.n)) % self.n
        print(f"[+] M0 = {M0}")
        print(f"[+] M1 = {M1}")
        print("[+] OT Protocol Ends")
        
def xor(a: bytes, b: bytes) -> bytes:
    return bytes(x ^ y for x, y in zip(a, b))
        
def challenge(rounds = 70):
    aes_key = os.urandom(32)
    xor_key = os.urandom(32)
    aes = AES.new(aes_key, AES.MODE_ECB)
    rsa_ot = RSA_OT.new(1024)
    secrets = [os.urandom(32) for i in range(rounds)]
    message_pairs = [(aes_key, xor_key)]
    message_pairs += [(aes.encrypt(secret), xor(xor_key, secret)) for secret in secrets]
    signal.alarm(120)
    print("[+] Sharing secrets through aes or xor, I won't know which one is used.")
    rsa_ot.show_public_key()
    for i, (m0, m1) in enumerate(message_pairs):
        print(f"[+] Round {i + 1}")
        rsa_ot.run(m0, m1)
    print("[+] All OTs Done!")
    verify_hash = hashlib.sha256(b''.join(secrets)).hexdigest()
    credential = input("[+] prove that you are honest: ").strip()
    if credential == verify_hash:
        print("[+] You are an honest player.")
    else:
        print("[+] Lies detected.")
        return
    
    master = hashlib.sha256(aes_key + xor_key).hexdigest()
    credential = input("[+] prove that you know both keys: ").strip()
    
    if credential == master:
        print(f"[+] Here is your flag: {FLAG}")
    else:
        print("[+] You are too honest!")
        return

if __name__ == "__main__":
    challenge()

pkcs1.py

import os

def encode(message, k, ps=None):
    '''Take a message of length inferior to k - 11 and return
       the concatenation of length k:

        0x00 || 0x02 || PS || 0x00 || message

       where PS is a random string containing no zero byte of length
       k - len(message) - 3.

       message - the message to encode, a byte string
       k - the length of the padded byte string
       ps - a fixed string to use instead of generating a random one, it's
       necessary for testing using test vectors,
       rnd - the random generator to use, it must conform to the interface of
       the random.Random class.
    '''
    m_len = len(message)
    if m_len > k - 11:
        raise Exception('MessageTooLong')
    ps_len = k - len(message) - 3
    if ps:
        if len(ps) != ps_len:
            raise Exception('wrong ps length', len(ps), ps_len)
    else:
        ps = b""
        while len(ps) != ps_len:
            byte = os.urandom(1)
            if byte != b"\x00":
                ps += byte
    return b'\x00\x02' + ps + b'\x00' + message

def decode(message: bytes):
    '''
       Verify that a padded message conform to the PKCSv1 1.5 encoding and
       return the unpadded message.
    '''
    if message[:2] != b'\x00\x02':
        raise Exception('DecryptionError')
    i = message.find(b'\x00', 2)
    if i == -1:
        raise Exception('DecryptionError')
    if i < 10:
        raise Exception('DecryptionError')        
    return message[i+1:]