2023-鹏城杯-wp-crypto

包含全四道赛题的题解

LeakyRSA

题目描述：

这个RSA好像泄露了什么？

题目：

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

nbits=512
p=getPrime(nbits)
q=getPrime(nbits)

leakBits = 262
leak = (p ^ q)  >> (nbits - leakBits)

n=p*q
e=65537
m = bytes_to_long(flag)
c = pow(m,e,n)
print(p)
print(q)
print("n=%d" %n)
print("c=%d" %c)
print("leak=%d" %leak)
# n=73822410148110759760164946405270228269255384237831275745269402590230495569279769799226813942899942423718229747478982630879557319063920515141217164980012063064986634632452289290326704640527699568662492105204165609614169349755365956569362139057327962393611139347462018186440108621311077722819578905265976612923      
# c=71808322808599218331233291542779486534747913572475630198802984648982830332628443972652322590637382696027943799004331488098592525306523343649935216419522329722152742610560398216737030893090641493326477786720839849938277402743820773957184083430369443325368720115515840174745825798187125454448297155036065857691      
# leak=2223117424030234543005449667053988296724455736030907136592525175314696509716321

题目给了一个泄漏了高262位的leak，满足：

$$leak = p \oplus q$$

那么运用深搜，可以找到多组满足条件的p、q高位，不明白深搜思路的师傅可以看我之前写的这篇，第二题第一小问：

Crypto趣题-剪枝 | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

那么接下来的自然想法，就是对找到的这些可能的p、q高位依次进行copper恢复低位。但是有一点小问题：

• 未知的低位有250比特，对于copper来说比较紧

所以我们要想办法提高可解根的上界，而我们知道，copper的可解根上界如下：

$$n^{\frac{\beta^2}{d}-\epsilon}$$

其中，d是构造的待求解多项式的度，这里也就是1；beta是指多项式建立在有限域Z(p)上，p是n的因子且满足b>n^beta；epsilon就是small_roots的一个参数。

那么可以运用下面三个思路更好的利用copper：

• 每一组比较p、q高位的大小，取较大的那一个值来恢复低位，这样可以将beta取为0.5，提高能求解的理论上界
• epsilon取0.01，这样会变慢，但同样可以提高能求解的理论上界
• 由于p为素数，将待求的p最低位赋为1，可以缩小根的上界(同理，可以爆破几位进一步缩小上界，但这里不需要了)

然后就可以恢复p，进而求解明文。

exp：

from Crypto.Util.number import *
import sys
sys.setrecursionlimit(1500)

nbits=512
leakBits = 262
leakbits = nbits - leakBits
e = 65537

n=73822410148110759760164946405270228269255384237831275745269402590230495569279769799226813942899942423718229747478982630879557319063920515141217164980012063064986634632452289290326704640527699568662492105204165609614169349755365956569362139057327962393611139347462018186440108621311077722819578905265976612923      
c=71808322808599218331233291542779486534747913572475630198802984648982830332628443972652322590637382696027943799004331488098592525306523343649935216419522329722152742610560398216737030893090641493326477786720839849938277402743820773957184083430369443325368720115515840174745825798187125454448297155036065857691      
leak=2223117424030234543005449667053988296724455736030907136592525175314696509716321

leak = leak << leakbits


a1 = "0" + str(bin(leak)[2:])
def find(p,q):
    l = len(p)
    tmp0 = p + (512-l)*"0"
    tmp1 = p + (512-l)*"1"
    tmq0 = q + (512-l)*"0"
    tmq1 = q + (512-l)*"1"
    if(int(tmp0,2) < int(tmq0,2)):
        return 
    if(int(tmp0,2)*int(tmq0,2) > n):
        return 
    elif(int(tmp1,2)*int(tmq1,2) < n):
        return

    if(l == 512 - leakbits):
        pp = int(tmp0,2)
        PR.<x> = PolynomialRing(Zmod(n))
        f = pp + x*2 + 1
        f = f.monic()
        res = f.small_roots(X=2^leakbits-1, beta=0.5, epsilon=0.01)
        if(res):
            try:
                plow = int(res[0])
                p = pp + plow * 2 + 1
                q = n // p
                d = inverse(e,(p-1)*(q-1))
                print(long_to_bytes(int(pow(c,d,n))))
            except:
                pass
                    
    else:
        if(a1[l] == "1"):
            find(p+"1",q+"0")
            find(p+"0",q+"1")
        else:
            find(p+"0",q+"0")
            find(p+"1",q+"1")

tempp = ""
tempq = ""
find(tempp,tempq)

#flag{6eb67115-38b1-4e75-b3fc-de3a9697e565}

SecretShare

题目描述：

Alice把flag分享了给你，快把他恢复吧。flag格式：flag{可见字符串}

题目：

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

n = 21
t = 21

A = [secret]
for i in range(n-1):
    A.append(random.getrandbits(1024))

X = []
for i in range(n):
    X.append(random.getrandbits(1024))

p = getPrime(1026)

def f(x):
    res = 0
    tmp = 1
    for i in range(n):
        res = (res + tmp * A[i]) % p 
        tmp = tmp * x % p
    return res % p

R = []
for i in range(n):
    R.append(f(X[i]))

P = secret
Q = getPrime(1024)
N = P * Q
m = bytes_to_long(flag)
e = 65537
c = pow(m, e, N)
phi=(P - 1) * (Q - 1)
d = pow(e,-1,phi)
print(long_to_bytes(pow(c,d,N)))

fi = open('output.txt','w')
for i in range(t-1):
    fi.write(str(X[i])+' '+str(R[i])+'\n')
print("leak = %d"%R[-1])
print("p = %d"%p)
print("c = %d"%c)
print("N = %d"%N)

# leak = 158171468736013100218170873274656605219228738469715092751861925345310881653082508445746109167302799236685145510095499361526242392251594397820661050281094210672424887670015189702781308615421102937559185479455827148241690888934661637911906309379701856488858180027365752169466863585611322838180758159364570481257
# p = 667548632459029899397299221540978856425474915828934339291333387574324630349258515018972045406265448494845331262999241448002076917383740651362641947814545076390796789402373579283727117618532504865966299599663825771187433223531022829811594806917984414530614469374596457149431218829297339079019894262229453357029   
# c = 9658009093151541277762773618550582280013680172161026781649630205505443184765264518709081169475689440555639354980432557616120809346519461077355134139495745998317849357705381020225760061125236265304057301286196004542729553944161451832173970613915423841610378207266606500956362098150141825329354727367056070349148059780287916811442861961254066733726576151134458892613951223277692935141880749737598416235307087782001086096114978527447987308876878393763055893556123029990282534497668077854186604106027698257663251502775547705641708624619340185646943640576690633662704397191379303254341343433077302686466850600522990402912
# N = 11790604055677230214731474049594783873473779547159534481643303694816346271798870343160061559787963631020684982858033776446193418629055210874285696446209220404060653230407249409973790191858423402504530660556839353260629987853933304089439885784684686555554108157760445567974629355878575105480273451284714281430590737346099023372211403461861104391534461524711472734572409128196536805998116015230502045333769525693468193385557827209520108839913096017750428926467123493650506193757937746017474062985480713594474378324234033232933140389879312722642144536418253323908290256009510135710208223393009237664704631175216240376891

这个题目将最终RSA的一个私钥P当作secret，藏在A数组的第一个，然后分别按如下方式生成各个数组：

A = [secret]
for i in range(n-1):
    A.append(random.getrandbits(1024))

X = []
for i in range(n):
    X.append(random.getrandbits(1024))

并以A、X数组为基础，计算R数组，R数组的每个值如下：

$$R_i = \sum_{j=0}^{20}{A_jX_i^j} \quad(mod\;p)$$

直观一点举个例子就是：

$$R_0 = A_0 + A_1X_0^1 + A_2X_0^2 + ... A_{20}X_0^{20} \quad(mod\;p)$$

然后，题目给了模数p和完整的R数组，以及缺了最后一个的X数组。可以想到，目的是用这些值还原出A数组，从而用上面的等式解出A0，然后得到最终RSA的分解进而求解明文。

很显眼的一点是，他随机数采用了：

random.getrandbits(1024)

然后又知道X数组的20个值，20个1024大于32*624，因此有足够的state来逆向twist，就可以得到全部A，然后随便挑一个Ri的计算等式就能解出A0，就有n的分解了。

对MT19937逆向过程不太明白的可以看这两篇文章，前段时间尝试完成西湖论剑的Oracle时才研究过，所以还有印象：

浅析MT19937伪随机数生成算法-安全客 - 安全资讯平台 (anquanke.com)

MT19937 - Cryptography-Wiki

我的exp也基本是用的这里面的脚本。

exp：

import random 
from Crypto.Util.number import *

#twist
def inverse_right_mask(res, shift, mask=0xffffffff, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp >> shift & mask
    return tmp

def inverse_left_mask(res, shift, mask=0xffffffff, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp << shift & mask
    return tmp

def recover(y):
    y = inverse_right_mask(y,18)
    y = inverse_left_mask(y,15,4022730752)
    y = inverse_left_mask(y,7,2636928640)
    y = inverse_right_mask(y,11)
    return y&0xffffffff


def inv_twist(state):
    high = 0x80000000
    low = 0x7fffffff
    mask = 0x9908b0df

    def recover(i):
        y = state[i + 624] ^ state[i + 397]
        if y & high == high: # 异或了常数
            y ^= mask
            y <<= 1
            y |= 1
        else: # 没有异或常数
            y <<= 1
        return y

    for i in range(len(state)-625, -1, -1):
        # 得到s_i的最高位
        state[i] = recover(i) & high
        # 对s_{i-1}做同样操作得到2-32位
        state[i] |= recover(i-1) & low
    return state


#recover state
def inverse_right(res,shift,bits=32):
    tmp = res
    for i in range(bits//shift):
        tmp = res ^ tmp >> shift
    return tmp
# right shift with mask inverse
def inverse_right_values(res,shift,mask,bits=32):
    tmp = res
    for i in range(bits//shift):
        tmp = res ^ tmp>>shift & mask
    return tmp
# left shift inverse
def inverse_left(res,shift,bits=32):
    tmp = res
    for i in range(bits//shift):
        tmp = res ^ tmp << shift
    return tmp
# left shift with mask inverse
def inverse_left_values(res,shift,mask,bits=32):
    tmp = res
    for i in range(bits//shift):
        tmp = res ^ tmp << shift & mask
    return tmp
def recover_state(out):
    state = []
    for i in out:
        i = inverse_right(i,18)
        i = inverse_left_values(i,15,0xefc60000)
        i = inverse_left_values(i,7,0x9d2c5680)
        i = inverse_right(i,11)
        state.append(i)
    return state

X = []
R = []
with open(r"E:\题\鹏城杯 2023\secretshare\output.txt","r") as f:
    for i in range(20):
        temp = f.readline().split(" ")
        X.append(int(temp[0]))
        R.append(int(temp[1]))

state = []
for i in range(20):
    temp = X[i]
    for j in range(32):
        state.append(temp&0xffffffff)
        temp >>= 32

state = inv_twist([0]*640 + recover_state(state[:624]))
state = state[:624]

from random import Random
prng = Random()
prng.setstate((3,tuple(state+[0]),None))
A = []
for i in range(20):
    A.append(prng.getrandbits(1024))

tX = [] 
for i in range(21):
    tX.append(prng.getrandbits(1024))

#print(tX[:20] == X)

leak = 158171468736013100218170873274656605219228738469715092751861925345310881653082508445746109167302799236685145510095499361526242392251594397820661050281094210672424887670015189702781308615421102937559185479455827148241690888934661637911906309379701856488858180027365752169466863585611322838180758159364570481257
p = 667548632459029899397299221540978856425474915828934339291333387574324630349258515018972045406265448494845331262999241448002076917383740651362641947814545076390796789402373579283727117618532504865966299599663825771187433223531022829811594806917984414530614469374596457149431218829297339079019894262229453357029   
c = 9658009093151541277762773618550582280013680172161026781649630205505443184765264518709081169475689440555639354980432557616120809346519461077355134139495745998317849357705381020225760061125236265304057301286196004542729553944161451832173970613915423841610378207266606500956362098150141825329354727367056070349148059780287916811442861961254066733726576151134458892613951223277692935141880749737598416235307087782001086096114978527447987308876878393763055893556123029990282534497668077854186604106027698257663251502775547705641708624619340185646943640576690633662704397191379303254341343433077302686466850600522990402912
N = 11790604055677230214731474049594783873473779547159534481643303694816346271798870343160061559787963631020684982858033776446193418629055210874285696446209220404060653230407249409973790191858423402504530660556839353260629987853933304089439885784684686555554108157760445567974629355878575105480273451284714281430590737346099023372211403461861104391534461524711472734572409128196536805998116015230502045333769525693468193385557827209520108839913096017750428926467123493650506193757937746017474062985480713594474378324234033232933140389879312722642144536418253323908290256009510135710208223393009237664704631175216240376891

R.append(leak)

secret = R[0]
for i in range(1,21):
    secret = (secret - pow(tX[0],i)*A[i-1]) %p

P = secret
Q = N//P
d = inverse(65537,(P-1)*(Q-1))
print(long_to_bytes(pow(c,d,N)))

#flag{2f43430b-3c31-03ee-0a92-5b24826c015c}

Neltharion and Arthas

题目描述：

Neltharion and Arthas

题目：

import binascii
import hashlib
from flag import flag
from Crypto.Cipher import AES
from Crypto.Util import *
import os

key1 = os.urandom(32)
key2 = b'tn*-ix6L*tCa*}i*'
key_len = len(key2)
assert flag.startswith(b'flag{')
assert (flag[13] == 45 and flag[18] == 45 and flag[23] == 45 and flag[28] == 45)
flag1 = b"2023: "+flag[:13]+flag[14:18]+flag[19:23]
flag2 = 

h = binascii.unhexlify(hashlib.sha256(key2).hexdigest())[:11]
gift1 = b'***********************************************************************************************'
gift2 = b'I tell you this, for when my days have come to an end , you, shall be King.'+h


def encrypt1(message, key):
    cipher = AES.new(key, AES.MODE_CTR, counter=Counter.new(128))
    ciphertext = cipher.encrypt(message)
    return ciphertext.hex()


def encrypt2(message, key, iv):
    padding = bytes((key_len - len(message) % key_len) * '&', encoding='utf-8')
    message += padding
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext = cipher.encrypt(message)
    return ciphertext.hex()


print("enc_gift1 = "+encrypt1(gift1, key1))
print("enc_flag = "+encrypt1(flag1, key1))
print("enc_gift2 = "+encrypt2(gift2, key2, flag2))

output：

enc_gift1 = bad7dbcff968d7cdbf51da011fe94e176fc8e7528e4dd85d2d5fc20ba69cefb7bfd03152a2874705bd2d857ea75b3216a830215db74772d9b9e9c218271d562694d3642d2917972fdb8c7363d8125730a50824cd8dc7e34cd4fa54be427cca
enc_flag = c1c78891e30cd4c0aa5ed65c17e8550429c4e640881f9f1d6a56df
enc_gift2 = ********c********b**************4***5********3****6a*****a**2********c*8******7***********3***5***2********e*5*************a******5**c***74***********fee046b4d2918096cfa3b76d6622914395c7e28eef

我个人觉得这个题复杂度设置的有点高了，导致debug有点不是很方便，中途发现写错了，幸好及时修改，差点就没出。

回到题目，他将题目分为了两部分，对应flag的两半：

• 第一部分，将flag1用AES_CTR加密，并对gift1同样进行AES_CTR加密，并给出两个密文。同时，隐去gift1，并且密钥key是未知的随机字节
• 第二部分，将flag2当作AES_CBC模式的iv，对gift2加上一段哈希并padding的明文进行加密，并给出部分密文

接下来分两个部分分别阐述：

第一部分

首先能注意到，对flag1和gift1的加密共用了一个counter以及密钥，因此由CTR的加密方式我们知道：

$$flag1 = encflag1 \oplus encgift1 \oplus gift1$$

对CTR加密不太清楚的可以看我写的另一篇文章的第三题：

Crypto趣题-分组密码 | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

那么也就是说，如果我们能有gift1，就可以还原出flag1.但是问题就是：gift1被隐去了。

但是我们有flag的前六个字节”2023: “，同样运用异或就可以得到gift1的前六个字节，是：

"I am D"

接下来略脑洞(不过其实也还好，提示很明显)，由题目标题Neltharion and Arthas可以搜到这是两个魔兽世界的人物，而gift2是第二个人物的台词。那么结合这个前缀，合理推测gift1也是一句台词，果然就搜到：

I am Deathwing, the destroyer, the end of all things. Inevitable. Indomitable. I. am. the Cataclysm...!

对其中一些大小写以及空格略作修改后，上面这一行gift1就可以解密出正确flag1了。

第二部分

有一个地方我看了很久才反应过来，就是这个key2：

key2 = b'tn*-ix6L*tCa*}i*'

由于它本身也有一些不是字母数字的字符，这导致我开始没有意识到这个*符号是对key2的涂抹，还以为他本来就是key2的字符。

弄清楚这一点就好办了，爆破四个可见字符，并以enc_gift2的最后一个完整密文分组为基础，依次解每个密文分组，就能得到正确的iv也就是flag2。

只是4个可见字符确实要的时间也比较久，再晚一点发现程序写错了的话，比赛时间内还真出不了了。

exp：

import binascii
import hashlib
from Crypto.Cipher import AES
from Crypto.Util import *
from pwn import xor
from Crypto.Util.number import *
from tqdm import *

#part1 CTR
gift1 = b"I am Deathwing, the destroyer, the end of all things. Inevitable. Indomitable. I. am. the Cataclysm...!"
enc_gift1 = "bad7dbcff968d7cdbf51da011fe94e176fc8e7528e4dd85d2d5fc20ba69cefb7bfd03152a2874705bd2d857ea75b3216a830215db74772d9b9e9c218271d562694d3642d2917972fdb8c7363d8125730a50824cd8dc7e34cd4fa54be427cca"
enc_flag =  "c1c78891e30cd4c0aa5ed65c17e8550429c4e640881f9f1d6a56df"
enc_gift1 = long_to_bytes(int(enc_gift1,16))
enc_flag = long_to_bytes(int(enc_flag,16))

print(xor(xor(enc_gift1,enc_flag),gift1)[:27])

#part2 CBC
def decrypt2(c, kkey, m):
    temp = long_to_bytes(int(c,16))
    cipher = AES.new(kkey, AES.MODE_ECB)
    ciphertext = cipher.decrypt(temp)
    return xor(ciphertext,m).hex().zfill(32)

key2 = b'tn*-ix6L*tCa*}i*'
key_len = 16
gift2 = b'I tell you this, for when my days have come to an end , you, shall be King.'
padding = 10*b"&"

enc_gift2 = "********c********b**************4***5********3****6a*****a**2********c*8******7***********3***5***2********e*5*************a******5**c***74***********fee046b4d2918096cfa3b76d6622914395c7e28eef"
suffix = enc_gift2[-32:]
table = [chr(i) for i in range(32,128)]

#21
for i in table[21:]:
    for j in tqdm(table):
        for k in table:
            for oo in table:
                kkey = b'tn'+ i.encode() + b"-ix6L" + j.encode() + b"tCa" + k.encode() + b"}i" + oo.encode()
                h = binascii.unhexlify(hashlib.sha256(kkey).hexdigest())[:11]
                C = [suffix]

                temp11 = gift2 + h + padding
                M = [temp11[16*tt:16*tt+16] for tt in range(6)]
                temp = decrypt2(C[0], kkey, M[5])

                if(temp.endswith("fee046b4d2")):
                    for tt in range(6):
                        C.append(decrypt2(C[tt], kkey, M[5-tt]))
                    flag2 = long_to_bytes(int(C[-1],16))
                    for nn in C[::-1]:
                        print(nn,end = "")
                    print(flag2)

#2023: flag{4ff732dd-2b74-45fd-a3ea-e82b4c491e0e}

colorful_matrix

题目描述：

colorful_matrix

题目：

import random
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import gmpy2
import os
import hashlib
def xor(a, b):
    return bytes([a[i%len(a)] ^ b[i%len(b)] for i in range(max(len(a), len(b)))])
flag = b'flag{xxxxxx}'
key1 = hashlib.md5(os.urandom(16)).hexdigest().encode()
key2 = hashlib.md5(os.urandom(16)).hexdigest().encode()
num1 = 5
p = int(gmpy2.next_prime(bytes_to_long(key1 + os.urandom(64))))
ms = [random.getrandbits(256) for _ in range(num1)]
qs = [getPrime(1024) for _ in range(num1)]
ns = [p * qs[_] + ms[_] for _ in range(num1)]

num2 = 37
x = bytes_to_long(key2 + os.urandom(32))
A = []
B = []
for i in range(num2):
    a = random.getrandbits(512)
    b = a * x % p
    gift = (2 ** 128 - 1) * 2 ** 400
    A.append(a)
    B.append((b & gift) >> 400)

iv = long_to_bytes(random.getrandbits(128))
key = xor(key1,key2)
aes = AES.new(key1,AES.MODE_CBC,iv)
enc = aes.encrypt(pad(flag,48))
print(f'ns = {ns}')
print(f'A = {A}')
print(f'B = {B}')
print(f'enc = {enc}')
# ns = [38630062416586710341458654419912504176237737247477839749085033080367529539859992076587411537805430366799412095876782912512744262957062106155418341531142309858429218208463637096843365217114990765965110566415965985105403996944993619708417839598461935470469097206342256014086162845948208599334925650727933097059538199199685364793545286980392966271769914201657672004082101110775504946586957241075964270454872257405872181588544468173017149763827540561921126826597515171761064800381983526515300315517818122598179574900255685121991744205071544970, 41522753602903133841910260331594875922287719226997542592715810409935551768308104573333760854332533376702631593490915962706512143045107096658851885513727202513616813054397657610854303071682604806070009002234312854968365250748142324994926715544722158698813288131533399544263105858513134170084625526223987620550110255872688155827773099232631041345207194483609514502522566888883736218471849075697433311580004701384847571029783514418685068903758509270527252444771313048094566344002411364378658592832008194309873599342916391769027015343562030852, 41542983120532762175372001624404625565366126179958909731196555044290633581761361918706298428954501507557598076910710787422049443564800530253137695341299743714514361560156305534490483794181933110893966453220306980682146624294992100948497284459992930850081254114996830645068636306625330524465991656430799359422407117440063911943625477783216502523414967017151717597372146324488526509879620785458016456593044828784565522423332830549325397893426472247197776412026158371655860380929692662547882654137064941217130915364306358205055760044763651406, 42853015443318352230776688785915441259875645365236808434164117288657978345098324019250085686482568413223085548506789311679316323466083886556772338612177680666217592255234589446979456714341877135596118517098603502394776049958587301113539552072352462301070489369653155854389890761241450743607560719433910573462283304103064437843063566946231984094581307498714742271881862348689297267558023093643893310002803310596286441071314219020032740336515363830250477649030557311461077069407775907176409762823453607196260454965048316567154365877848652918, 31152961872836435078296602982779340735140569916125711058616435902653202922218293684857125091648631460215120167354825278469413413558325850576700866199515219603448136082693185200558425103833947831228064760642508443585470729998592994719564254894176473779555436230174300038353978808432410463449170865897259181312953584408177790825688497584119467820716449210429423337019604137134889051973100340798405991782200038835066294194815913887924272593864934325496116821854183293510325217934617021428710898873475027666892706022106386340733691632884942848]
# A = [12789809461864875489953273982997537541385904671489556544122095227619591140533414669794423644619127980362623481580128258914287474542792728686579090501397390, 10463950513938701625808784986819665844287315724639315128677227520960105897990256530542006653611594269012930935073966767351788182657861624733138283749460454, 5253244650607533810967862436125419800679723144526973463211784033045021824966560017919956773745212139142517766154626849426827164032731516615725539069585525, 5644589184984504085855423002268477365020278981591337230721358313393863912025011466727192648804002734561676112555123877764178690726130713927642577324443238, 4231732567865883627242742552738439372803539125622706171540910152922080004603138662537022248675968288205781990968838888633816697065257733344028576518431020, 2483388920404524165854675814798022834892112957478917588986471421083048888193527751575039626887367465858751417977246719312923814782809309525841102293919541, 3252353812256192711411255830105475125944842449239880454539397067913664088094160819193268643401968970009466652179043139341471403913410402646923633696154454, 11575010486066232687430367040977113580882826853104996856464797182632266635060724100357205810604915010810884387573114266349621457564659060272935537811111850, 116107444921917032985259963199427176510900273385517435613848456370557161312731449337837406563733552524777525870560544042690403987311424820755256727586807, 5859050133610438843641532306693688255014116940390205022708310454673159702673207152462501010791971695002865650407033762568636006764435795015869726867643634, 5954075553161305677556950650395792531753502207483036473422070018485916621872566706504374038792527687442272405589975343003802956899043321092006127828986114, 4571747544457157571652286537158051402285727327066029382085461714597609990601683125994983291866807816649968826930652068427193317966970789937746419206862747, 7166507561570980603812241332170524724051295937096000768984168029904561160020043035660087151672164814332446644696618077835020463308343415953131944864257266, 4852042788460566411381271873349329096978244586097817622748766708426751073559942708861852208085367014057217116211249133109246735634468823924185525972777655, 11962941918999276757181090570698839032103646409734781047194175833198626142790676141060052011581957980660140931408560130449153056874213033784715711461403345, 10324508881746579337486319574059121005227580732153432145860775835052420139026016902518605634385512021513380467928195663920843022679549517463264144660593354, 13276257094435850052122403884510025189232513948002582716865201271569293297601525601586036713056700716929820641888489806178376555435219630186396004003438962, 6525051273399089095687950615197786094425890004112675057642687348101531212837185750558500720306108976630502328600886080197626115513445112562084719104488315, 12922888505610354933000354792496863801007995464403098763485264334670452387681468617068312646367483171083114539083453125614861357751571161533921864394641576, 9489726784141062031514945333087338495823600723655465328127755755022980083351477888038160719541864899912899592065620071698977397662002448273876711116012763, 10630316198843195148937849513165933809121991192035364160395429088101265852052098101114542104327663563661384303617672183366879116750889320604308038959012109, 12675564142993964272844760955973914547747654087592111324261755301551267959231076883765863344473167582531968290671984039948163579495803204811731286282708940, 11847724105274460405216443356582445218232627275228120716891711887600046501095390733716854871561352002320819466803698088448952127166615410820121973485089326, 5131676593756685549522564504727003861447389891839469018437277330988047271086971907217360711863971849879439418231726349935396008040776952541710218842744018, 8049060452950901277510497437779182190254362319091882684392717180429468875432078713802857488901441344429723298843967365750616860588029426099852763482179470, 2365060249260571713545479629411006471094806409182638354076861269679377537605360223984548798658469783472746989448405310909017645138161178501458084966625559, 7467521246204465304438401242342633361751371318557249418344587207503257890765643838557008735305668588521988487342275527781708126255070883848829062790678347, 5841608816993144092409175658260479687582056537041472535819914412630519543198558564258699185557903902095773598614097026740427138629173672250387442834578787, 3935779917509948624841228665498558015416911059417306651751360048412619176423173794541812556512582747588138532941031730797102738268660078594473168666677171, 1459083415233950534805962555425717865938763752937036513111696179351002303817986848490146888626704327653287774806488952733813718461674376764427084478395399, 6426876689549337938550615491086475536072547585103523407263007393570982327518298678278232288342601754164640081474537962710401178482959474762541185760732929, 5241364650650467046722868257809607948071188801137204831449976666385482519613365369974704486723941517654753205012497273820309153659423928739972270634209996, 6387483223002092292686097811446217867743566298067033295601210265979889577756648605354064672061975949925472022416479935990178719227937307079186916383092053, 170562164015232424518655058158727202269056868720093972639058422975773575660534168774299548952867348396798580779605954510297102765330549642318362861226163, 10004133230245713370426176448219282796530473722412487408402635996842671302539458739305597027107498342509248085998067976408732789438099488867425813748783724, 12325342879747412722323355648741345730921040452129462974449188258885453690169624888480720109964630270938743431623479816739889661554987977051169401841580388, 641543989928732942291347866597230552820621633110802944556141221591498546555080480758772801043509130524233886009444044150447511986129019395067102094826363]
# B = [108715652691370707411987210267535348806, 131676833696101475747102644851662113271, 122436706338521558335484593966234623745, 255864866572301552398412638474857375629, 81098761191414480003681301866161112100, 322322463176364397336266169283851913620, 198167679309202772183020662350938553923, 326360662842236388778385468938922853242, 241812832858991643670485138860832357660, 69768236619183466076110136290750715548, 32383134960394164339076842474280712870, 147747232748027508904245311745435517130, 25327826075608705748116808975774398964, 65295332681674581261444632606267440749, 236756211690281667988216748814564193312, 106435149910135092172124474857722935730, 270727089812520941022075406571244846193, 206881193220261276126028739930244917728, 131961838897694897398340205404861333362, 219211823942216355573832791993673934321, 150960424777134558142309786444952807101, 51112048255939343109218372373173385772, 182065623911902509203036774197184164110, 168420344895532090057957641972492853410, 301808673225362418769168353084541667053, 132272458662433671393247350648662880688, 495672626901999558635736361346563007, 182444159345379042372018248514964944782, 144584137563407779776361378564517880036, 338518705859818740467225748906995999694, 205885429741815676881969528495365151019, 233897982464483450790005953366237992668, 279307677123402840425362992920185630901, 133493426228159673166382443820069696429, 316624110847744871475435405969944304329, 187931604382397525131117897387179435812, 220019728924915067987393012581921164417]
# enc = b'cTmkMb\xfc\x05|\x1d\xc7\x13\xbaSe\xe0\xbd\xc0\xd9\xa3\x8cwo\x82yN[B&\x80\xd7KPwQ`\x9c\xbf<y\x8e\x8a\x97e\xa074\xb2'

这个题目弄的心情有点烦躁，因为求解key1很容易，难度主要在求解key2。但是出题人失误了，最后AES用的仍然是key1，而不是key1和key2异或得到的key，这样难度就一点都没有了。

不过我还是会把两个部分都讲一下。

首先，第一部分很显然是个AGCD问题，不清楚的指路la佬博客：

格密码 | Lazzaro (lazzzaro.github.io)

那么就可以求解出ms数组和p以及key1。

其实这道题问题到这里就已经结束了，由于A数组已经给定，并且A和ms生成的方式都是：

getrandbits()

那么又可以利用MT19937，只是这一次我们是向后预测iv。预测完iv后直接解AES就得到flag。

然后接下来就说一下我做出来了发现没用的第二部分，第二部分难度我觉得相对来说大很多。

第二部分里，我们有多组如下式子：

$$b_i = a_ix \quad(mod\;p)$$

但是bi只泄漏了中间一些位，高位和低位是没有的，因此我们需要构造HNP，构造思路如下：

首先，x是一个512比特的数，肯定不能出现在我们要规约的短向量中，因此要消元，消元方式就是两两作差，在这里我们选择将所有项与第0项作差，如下：

由于：

$$b_0 = a_0x \quad(mod\;p)$$ $$b_i = a_ix \quad(mod\;p)$$

所以有：

$$b_0a_i = a_ia_0x \quad(mod\;p)$$ $$b_ia_0 = a_ia_0x \quad(mod\;p)$$

作差即可得到：

$$b_ia_0 = b_0a_i \quad(mod\;p)$$

然后把a0乘过去：

$$b_i = a_0^{-1}a_ib_0 \quad(mod\;p)$$

由于已知bi的中间128位，所以我们可以把bi和b0拆为三部分：

$$2^{528}b_{hi} + 2^{400}b_{leaki} + b_{li} = a_0^{-1}a_i(2^{528}b_{h0} + 2^{400}b_{leak0} + b_{l0}) \quad(mod\;p)$$

两边均出现了已知的bleak项，提取到一边去：

$$2^{528}b_{hi} + b_{li} = a_0^{-1}a_i(2^{528}b_{h0} + 2^{400}b_{leak0} + b_{l0}) - 2^{400}b_{leaki}\quad(mod\;p)$$

把常数项凑起来：

$$2^{528}b_{hi} + b_{li} = a_0^{-1}a_i(2^{528}b_{h0} + b_{l0}) - 2^{400}b_{leaki} + a_0^{-1}a_i2^{400}b_{leak0}\quad(mod\;p)$$

然后，令：

$$A_i = a_0^{-1}a_i$$ $$B_i = - 2^{400}b_{leaki} + a_0^{-1}a_i2^{400}b_{leak0}$$

就有形式：

$$2^{528}b_{hi} + b_{li} = A_i(2^{528}b_{h0} + b_{l0})+B_i \quad(mod\;p)$$

然后把模p去掉化成等式：

$$2^{528}b_{hi} + b_{li} = A_i(2^{528}b_{h0} + b_{l0})+B_i +t_ip$$

就是个HNP问题了，只不过是二元的。而这个形式正好前段时间有师傅问过我，是这篇的SSSMMM一题：

Crypto趣题-Lattice | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

构造形式完全一样，不明白的师傅可以去看看。

然后这题目里，LLL后的第一行就是目标向量，因此我们就可以求解出所有完整的b，从中随便选一组等式也就有key2。但是求完了key2惊奇地发现，居然没用！最后也没上这题的revenge，心痛。

exp(完整的两部分，包含两个key的求解)：

from Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib

#part1 AGCD
kbits = 256

Q = [38630062416586710341458654419912504176237737247477839749085033080367529539859992076587411537805430366799412095876782912512744262957062106155418341531142309858429218208463637096843365217114990765965110566415965985105403996944993619708417839598461935470469097206342256014086162845948208599334925650727933097059538199199685364793545286980392966271769914201657672004082101110775504946586957241075964270454872257405872181588544468173017149763827540561921126826597515171761064800381983526515300315517818122598179574900255685121991744205071544970, 41522753602903133841910260331594875922287719226997542592715810409935551768308104573333760854332533376702631593490915962706512143045107096658851885513727202513616813054397657610854303071682604806070009002234312854968365250748142324994926715544722158698813288131533399544263105858513134170084625526223987620550110255872688155827773099232631041345207194483609514502522566888883736218471849075697433311580004701384847571029783514418685068903758509270527252444771313048094566344002411364378658592832008194309873599342916391769027015343562030852, 41542983120532762175372001624404625565366126179958909731196555044290633581761361918706298428954501507557598076910710787422049443564800530253137695341299743714514361560156305534490483794181933110893966453220306980682146624294992100948497284459992930850081254114996830645068636306625330524465991656430799359422407117440063911943625477783216502523414967017151717597372146324488526509879620785458016456593044828784565522423332830549325397893426472247197776412026158371655860380929692662547882654137064941217130915364306358205055760044763651406, 42853015443318352230776688785915441259875645365236808434164117288657978345098324019250085686482568413223085548506789311679316323466083886556772338612177680666217592255234589446979456714341877135596118517098603502394776049958587301113539552072352462301070489369653155854389890761241450743607560719433910573462283304103064437843063566946231984094581307498714742271881862348689297267558023093643893310002803310596286441071314219020032740336515363830250477649030557311461077069407775907176409762823453607196260454965048316567154365877848652918, 31152961872836435078296602982779340735140569916125711058616435902653202922218293684857125091648631460215120167354825278469413413558325850576700866199515219603448136082693185200558425103833947831228064760642508443585470729998592994719564254894176473779555436230174300038353978808432410463449170865897259181312953584408177790825688497584119467820716449210429423337019604137134889051973100340798405991782200038835066294194815913887924272593864934325496116821854183293510325217934617021428710898873475027666892706022106386340733691632884942848]

L = Matrix(ZZ,5,5)
L[0,0] = 2^(kbits)
for i in range(1,5):
    L[0,i] = Q[i]
    L[i,i] = -Q[0]
res = L.LLL()[0]
q0 = int(abs(res[0]) // L[0,0])
p = int(abs(Q[0]) // q0)

key1 = long_to_bytes(p)[:32]

#recover ms
q1 = int((q0*Q[1]+res[1]) // Q[0])
q2 = int((q0*Q[2]+res[2]) // Q[0])
q3 = int((q0*Q[3]+res[3]) // Q[0])
q4 = int((q0*Q[4]+res[4]) // Q[0])
m0 = Q[0] - p*q0
m1 = Q[1] - p*q1
m2 = Q[2] - p*q2
m3 = Q[3] - p*q3
m4 = Q[4] - p*q4
ms = [m0,m1,m2,m3,m4]

#part2 HNP
length = 36
a = [12789809461864875489953273982997537541385904671489556544122095227619591140533414669794423644619127980362623481580128258914287474542792728686579090501397390, 10463950513938701625808784986819665844287315724639315128677227520960105897990256530542006653611594269012930935073966767351788182657861624733138283749460454, 5253244650607533810967862436125419800679723144526973463211784033045021824966560017919956773745212139142517766154626849426827164032731516615725539069585525, 5644589184984504085855423002268477365020278981591337230721358313393863912025011466727192648804002734561676112555123877764178690726130713927642577324443238, 4231732567865883627242742552738439372803539125622706171540910152922080004603138662537022248675968288205781990968838888633816697065257733344028576518431020, 2483388920404524165854675814798022834892112957478917588986471421083048888193527751575039626887367465858751417977246719312923814782809309525841102293919541, 3252353812256192711411255830105475125944842449239880454539397067913664088094160819193268643401968970009466652179043139341471403913410402646923633696154454, 11575010486066232687430367040977113580882826853104996856464797182632266635060724100357205810604915010810884387573114266349621457564659060272935537811111850, 116107444921917032985259963199427176510900273385517435613848456370557161312731449337837406563733552524777525870560544042690403987311424820755256727586807, 5859050133610438843641532306693688255014116940390205022708310454673159702673207152462501010791971695002865650407033762568636006764435795015869726867643634, 5954075553161305677556950650395792531753502207483036473422070018485916621872566706504374038792527687442272405589975343003802956899043321092006127828986114, 4571747544457157571652286537158051402285727327066029382085461714597609990601683125994983291866807816649968826930652068427193317966970789937746419206862747, 7166507561570980603812241332170524724051295937096000768984168029904561160020043035660087151672164814332446644696618077835020463308343415953131944864257266, 4852042788460566411381271873349329096978244586097817622748766708426751073559942708861852208085367014057217116211249133109246735634468823924185525972777655, 11962941918999276757181090570698839032103646409734781047194175833198626142790676141060052011581957980660140931408560130449153056874213033784715711461403345, 10324508881746579337486319574059121005227580732153432145860775835052420139026016902518605634385512021513380467928195663920843022679549517463264144660593354, 13276257094435850052122403884510025189232513948002582716865201271569293297601525601586036713056700716929820641888489806178376555435219630186396004003438962, 6525051273399089095687950615197786094425890004112675057642687348101531212837185750558500720306108976630502328600886080197626115513445112562084719104488315, 12922888505610354933000354792496863801007995464403098763485264334670452387681468617068312646367483171083114539083453125614861357751571161533921864394641576, 9489726784141062031514945333087338495823600723655465328127755755022980083351477888038160719541864899912899592065620071698977397662002448273876711116012763, 10630316198843195148937849513165933809121991192035364160395429088101265852052098101114542104327663563661384303617672183366879116750889320604308038959012109, 12675564142993964272844760955973914547747654087592111324261755301551267959231076883765863344473167582531968290671984039948163579495803204811731286282708940, 11847724105274460405216443356582445218232627275228120716891711887600046501095390733716854871561352002320819466803698088448952127166615410820121973485089326, 5131676593756685549522564504727003861447389891839469018437277330988047271086971907217360711863971849879439418231726349935396008040776952541710218842744018, 8049060452950901277510497437779182190254362319091882684392717180429468875432078713802857488901441344429723298843967365750616860588029426099852763482179470, 2365060249260571713545479629411006471094806409182638354076861269679377537605360223984548798658469783472746989448405310909017645138161178501458084966625559, 7467521246204465304438401242342633361751371318557249418344587207503257890765643838557008735305668588521988487342275527781708126255070883848829062790678347, 5841608816993144092409175658260479687582056537041472535819914412630519543198558564258699185557903902095773598614097026740427138629173672250387442834578787, 3935779917509948624841228665498558015416911059417306651751360048412619176423173794541812556512582747588138532941031730797102738268660078594473168666677171, 1459083415233950534805962555425717865938763752937036513111696179351002303817986848490146888626704327653287774806488952733813718461674376764427084478395399, 6426876689549337938550615491086475536072547585103523407263007393570982327518298678278232288342601754164640081474537962710401178482959474762541185760732929, 5241364650650467046722868257809607948071188801137204831449976666385482519613365369974704486723941517654753205012497273820309153659423928739972270634209996, 6387483223002092292686097811446217867743566298067033295601210265979889577756648605354064672061975949925472022416479935990178719227937307079186916383092053, 170562164015232424518655058158727202269056868720093972639058422975773575660534168774299548952867348396798580779605954510297102765330549642318362861226163, 10004133230245713370426176448219282796530473722412487408402635996842671302539458739305597027107498342509248085998067976408732789438099488867425813748783724, 12325342879747412722323355648741345730921040452129462974449188258885453690169624888480720109964630270938743431623479816739889661554987977051169401841580388, 641543989928732942291347866597230552820621633110802944556141221591498546555080480758772801043509130524233886009444044150447511986129019395067102094826363]
b = [108715652691370707411987210267535348806, 131676833696101475747102644851662113271, 122436706338521558335484593966234623745, 255864866572301552398412638474857375629, 81098761191414480003681301866161112100, 322322463176364397336266169283851913620, 198167679309202772183020662350938553923, 326360662842236388778385468938922853242, 241812832858991643670485138860832357660, 69768236619183466076110136290750715548, 32383134960394164339076842474280712870, 147747232748027508904245311745435517130, 25327826075608705748116808975774398964, 65295332681674581261444632606267440749, 236756211690281667988216748814564193312, 106435149910135092172124474857722935730, 270727089812520941022075406571244846193, 206881193220261276126028739930244917728, 131961838897694897398340205404861333362, 219211823942216355573832791993673934321, 150960424777134558142309786444952807101, 51112048255939343109218372373173385772, 182065623911902509203036774197184164110, 168420344895532090057957641972492853410, 301808673225362418769168353084541667053, 132272458662433671393247350648662880688, 495672626901999558635736361346563007, 182444159345379042372018248514964944782, 144584137563407779776361378564517880036, 338518705859818740467225748906995999694, 205885429741815676881969528495365151019, 233897982464483450790005953366237992668, 279307677123402840425362992920185630901, 133493426228159673166382443820069696429, 316624110847744871475435405969944304329, 187931604382397525131117897387179435812, 220019728924915067987393012581921164417]

A = []
B = []
for i in range(1,length):
    temp = inverse(a[0],p)*a[i] % p
    A.append(temp)
for i in range(1,length):
    temp = inverse(a[0],p)*a[i] % p
    temp = temp * b[0]*(2^400) - b[i]*(2^400)
    temp = temp % p
    B.append(temp)

O = matrix(ZZ,(length-1),(length-1)+3)
E = diagonal_matrix([2^160]*((length-1)+3))
T1 = diagonal_matrix([p]*((length-1)))
T2 = matrix(ZZ,(length-1)+3,length-1)
for i in range(length-1):
    T2[i,i] = 2^528
    T2[-1,i] = -B[i]
    T2[-2,i] = -A[i]
    T2[-3,i] = -A[i] * 2^528

L = block_matrix(ZZ,[[T1,O],[T2,E]])

K = 2^400
L[-1,-1] = K
L[-2,-2] = 1
L[-3,-3] = 2^160

temp = L.LLL()[0]

bh0 = abs(temp[-3] // (2^160))
bl0 = abs(temp[-2])
b0 = bh0*2^528 + b[0]*2^400 + bl0
x = inverse(a[0],p) * b0 % p
key2 = long_to_bytes(int(x))[:32]


#part3 decrypt
enc = b'cTmkMb\xfc\x05|\x1d\xc7\x13\xbaSe\xe0\xbd\xc0\xd9\xa3\x8cwo\x82yN[B&\x80\xd7KPwQ`\x9c\xbf<y\x8e\x8a\x97e\xa074\xb2'

iv = b'\xe9\x19\xbcU?\xd5\x1a>\xaa\x9c\xb2\xe6@\xbd\xbd9'
aes = AES.new(key1,AES.MODE_CBC,iv)

flag = aes.decrypt(enc)
print(flag)

#flag{86baa4ed-5ec7-11ee-ae14-ac1203ab14da}