周末打了一下鹏城杯，密码学方向的赛题都是一些“老东西”拼凑起来的。唯一一个不熟悉的 HNP 问题，还因为出题人的“宅心仁厚”，可以直接忽视。
[LeakyRSA]
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 比特。所以大致方向就是利用这个信息，以及 来恢复 的高位，然后再走一个 coppersmith 完成对 n 的分解。
那么我们首先需要根据条件，对 自高位进行剪枝爆破。约束的条件总共有四条：
其中比较“强”的是 ，每当我们选择一个 的比特，那么此时 的对应比特也能确定。 xor(pnew,qnew) == leak[:2+i]
另外一个我们这里稍微意会一下（就是不严格证明了），就是 高位相乘的结果，前面大约一半的数和 的高位是相同的。tmp>>(tmp.bit_length()-i//2)== n>>(n.bit_length()-i//2)
当我们定下了当前 的高位，那么 低位全补 0，然后它们相乘的结果要小于 。 (int(pnew.ljust(512,'0'),2)*int(qnew.ljust(512,'0'),2) < n)
当我们定下了当前 的高位，那么 低位全补 1，然后它们相乘的结果要大于 。(int(pnew.ljust(512,'1'),2)*int(qnew.ljust(512,'1'),2) > n)
from Crypto.Util.number import *
def xor(a,b):
tmp = ""
for i,j in zip(a,b):
tmp+=str(ord(i)^ord(j))
return tmp
nbits = 512
leakBits = 262
leak=2223117424030234543005449667053988296724455736030907136592525175314696509716321
leak = bin(leak)[2:].rjust(262,'0')
n=73822410148110759760164946405270228269255384237831275745269402590230495569279769799226813942899942423718229747478982630879557319063920515141217164980012063064986634632452289290326704640527699568662492105204165609614169349755365956569362139057327962393611139347462018186440108621311077722819578905265976612923
p='1'
q='1'
P=[p]
Q=[q]
for i in range(261):
PP=[]
QQ=[]
for a in '01':
for b in '01':
for pnew,qnew in zip(P,Q):
pnew = pnew+a
qnew = qnew+b
tmp = int(pnew,2)*int(qnew,2)
#print(tmp)
if xor(pnew,qnew) == leak[:2+i] and tmp>>(tmp.bit_length()-i//2)== n>>(n.bit_length()-i//2) and (int(pnew.ljust(512,'0'),2)*int(qnew.ljust(512,'0'),2) < n) and (int(pnew.ljust(512,'1'),2)*int(qnew.ljust(512,'1'),2) > n) :
PP.append(pnew)
QQ.append(qnew)
print(len(P))
P = PP.copy()
Q = QQ.copy()
print(P)
# P = ['1000001000011100010101010110000111101011000100111100000111111100011001101101101110100111101010111011001100111101001100010011110010100000001100010100110110000110000100101000111110110000101100100010111111001101001000001001111101111010000011111000101010100100000010', '1100111011010111101010100001110101111111100110111010101010011101100000101101010010101000010011001110110001011011011010000000100000111100111011101111100011110110111000000101100100101100100011111110011000101011011010100011001010101100111000100100110011001101000010', '1000001000011100010101010110000111101011000100111100000111111100011001101101101110100111101010111011001100111101001100010011110010100000001100010100110110000110000100101000111110110000101100100010111111001101001000001001111101111010000011111000101100010000100010', '1100111011010111101010100001110101111111100110111010101010011101100000101101010010101000010011001110110001011011011010000000100000111100111011101111100011110110111000000101100100101100100011111110011000101011011010100011001010101100111000100100110101111001100010', '1000001000011100010101010110000111101011000100111100000111111100011001101101101110100111101010111011001100111101001100010011110010100000001100010100110110000110000100101000111110110000101100100010111111001101001000001001111101111010000011111000101100010000001010', '1000001000011100010101010110000111101011000100111100000111111100011001101101101110100111101010111011001100111101001100010011110010100000001100010100110110000110000100101000111110110000101100100010111111001101001000001001111101111010000011111000101010100100000011', '1100111011010111101010100001110101111111100110111010101010011101100000101101010010101000010011001110110001011011011010000000100000111100111011101111100011110110111000000101100100101100100011111110011000101011011010100011001010101100111000100100110011001101000011', '1000001000011100010101010110000111101011000100111100000111111100011001101101101110100111101010111011001100111101001100010011110010100000001100010100110110000110000100101000111110110000101100100010111111001101001000001001111101111010000011111000101100010000100011', '1100111011010111101010100001110101111111100110111010101010011101100000101101010010101000010011001110110001011011011010000000100000111100111011101111100011110110111000000101100100101100100011111110011000101011011010100011001010101100111000100100110101111001100011', '1100111011010111101010100001110101111111100110111010101010011101100000101101010010101000010011001110110001011011011010000000100000111100111011101111100011110110111000000101100100101100100011111110011000101011011010100011001010101100111000100100110011001101101011']
这里我们能够得到十个可能的 ，不过根据我们的代码， 是等价的，也就意味着其中有两个值是正确的。我们遍历其中的数，走一个 coppersmith 。由于这里泄露的比特不多，经过测试，如果想恢复 250 比特的低位，那么需要设置 beta=0.47,epsilon=0.008，跑一次比较久。这里我选择再爆破 5 个比特，这样子可以设 epsilon=0.02，跑起来要稍微快些。
有结果了之后正常解一个 RSA 就可以了。
from tqdm import *
R.<x> = Zmod(n)[]
for pbar in tqdm(P[::-1]):
for i in range(32):
tmp = int(pbar,2)<<5
tmp+=i
f = tmp*2**245 + x
xx = f.monic().small_roots(X=2^245,beta=0.47,epsilon=0.02)
if xx:
p = f(xx[0])
print(p)
# 6814449132912466352143200200256605077873329465758477832056090562012411200107156482645933890997787435093806046493913273252717701817613907418845774345791241
c=71808322808599218331233291542779486534747913572475630198802984648982830332628443972652322590637382696027943799004331488098592525306523343649935216419522329722152742610560398216737030893090641493326477786720839849938277402743820773957184083430369443325368720115515840174745825798187125454448297155036065857691
n=73822410148110759760164946405270228269255384237831275745269402590230495569279769799226813942899942423718229747478982630879557319063920515141217164980012063064986634632452289290326704640527699568662492105204165609614169349755365956569362139057327962393611139347462018186440108621311077722819578905265976612923
p=6814449132912466352143200200256605077873329465758477832056090562012411200107156482645933890997787435093806046493913273252717701817613907418845774345791241
q=n//p
d = inverse(65537,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))
[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 = 'a3eae82b4c491e0e'
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))
# 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
这题目一眼看过去就知道要爆破了（烦人。）不过题目本身涉及的知识点并不难，稍微了解过 CTR 和 CBC 模式就能做了。
首先是 flag 的第一部分，看到 encrypt1 函数，使用的是 CTR 模式，并且每一次的计数器都是从同一个位置开始。我们知道 CTR 模式是有点类似于流密码的，因此遭受不住已知明文攻击。而题目使用同样的 key1 对 gift1 和 flag1 分别进行了一次加密，因此只要我们能够知道 gift1 的内容，就能利用 gift1 和其对应密文来恢复 flag1 了。
首先看到 flag1 = b"2023: "+flag[:13]+flag[14:18]+flag[19:23]，而根据前面解出的 flag，我们知道这个比赛的 flag 都是 flag{} 的格式。于是相当于我们已经知道了 flag1 的11个字节的明文，即 2023: flag{，对应的，我们也能够恢复 11 字节的 gift1
def xor(a,b):
tmp = ""
for i,j in zip(a,b):
tmp+=chr(i^j)
return tmp.encode('latin1')
enc_gift1 = 'bad7dbcff968d7cdbf51da011fe94e176fc8e7528e4dd85d2d5fc20ba69cefb7bfd03152a2874705bd2d857ea75b3216a830215db74772d9b9e9c218271d562694d3642d2917972fdb8c7363d8125730a50824cd8dc7e34cd4fa54be427cca'
enc_flag = 'c1c78891e30cd4c0aa5ed65c17e8550429c4e640881f9f1d6a56df'
enc_flag=bytes.fromhex(enc_flag)
enc_gift1=bytes.fromhex(enc_gift1)[:len(enc_flag)]
ans = (xor(b"2023: flag{",xor(enc_gift1,enc_flag)))
print(ans)
我们得到 b'I am Deathw'
拿着这个题目名字去百度搜，可以搜到一个暴雪的英雄，死亡之翼，因此这里应该是 Deathwing，再搜一下，就能够搜到原台词：I am Deathwing, the destroyer, the end of all things,inevitable,indomitable,I am the cataclysm
最后就可以用这个原台词恢复 flag1 了
def xor(a,b):
tmp = ""
for i,j in zip(a,b):
tmp+=chr(i^j)
return tmp.encode('latin1')
enc_gift1 = 'bad7dbcff968d7cdbf51da011fe94e176fc8e7528e4dd85d2d5fc20ba69cefb7bfd03152a2874705bd2d857ea75b3216a830215db74772d9b9e9c218271d562694d3642d2917972fdb8c7363d8125730a50824cd8dc7e34cd4fa54be427cca'
enc_flag = 'c1c78891e30cd4c0aa5ed65c17e8550429c4e640881f9f1d6a56df'
enc_flag=bytes.fromhex(enc_flag)
enc_gift1=bytes.fromhex(enc_gift1)[:len(enc_flag)]
ans = (xor(b"I am Deathwing, the destroyer, the end of all things,inevitable,indomitable,I am the cataclysm",xor(enc_gift1,enc_flag)))
print(ans)
得到 ：b'2023: flag{4ff732dd2b7445fd'
然后看到 encrypt2 函数，
使用的 CBC 模式，
填充符号用的是 &，
key2也给出了绝大部分 key2 = b'tn*-ix6L*tCa*}i*'，
gift2 为 gift2 = b'I tell you this, for when my days have come to an end , you, shall be King.'+h，其中 h 是 key2 的sha256 的前 11 个字节。因此我们知道 gift2 的绝大部分内容，以及其最终的字符串长度。测一下不难得到在加密时，gift2后面会填充10个 &，这是我们爆破 key2 的关键。
最后 gift2 的密文是 ********c********b**************4***5********3****6a*****a**2********c*8******7***********3***5***2********e*5*************a******5**c***74***********fee046b4d2918096cfa3b76d6622914395c7e28eef，只有最后一组是完整的，倒数第二组只有最后10个字符也就是5个字节。
爆破方案就是，根据 CBC 模式，最后一组密文使用 AES 解密后，还要和前一组密文异或才能得到明文。那么这里，我们首先爆破密钥 key2，然后对最后一组密文进行解密，解密后的最后 5 个字节，和倒数第二组还“幸存”的 5 个字节进行异或，如果结果是 5 个 & 字符的话，就说明爆破的密钥 key2 正确。
from string import printable
from tqdm import *
enc_gift2 = "fee046b4d2918096cfa3b76d6622914395c7e28eef"
from Crypto.Cipher import AES
def xor(a,b):
tmp = ""
for i,j in zip(a,b):
tmp+=chr(i^j)
return tmp.encode('latin1')
iv = bytes.fromhex(enc_gift2[:10])
cipher = bytes.fromhex(enc_gift2[-32:])
for i in tqdm(printable):
for j in printable:
for k in printable:
for l in printable:
key2 = 'tn%s-ix6L%stCa%s}i%s'%(i,j,k,l)
dec = AES.new(key2.encode(), AES.MODE_ECB)
m = dec.decrypt(cipher)
m = xor(iv,m[-5:])
if m == b"&"*5:
print(key2)
最后我们得到 key2 = b'tn5-ix6L#tCaG}i6'
不过由于这里 flag2 是用作于 AES 的 iv。想要恢复这个 iv 就要用 gift2 第一组明文的 AES 密文和通过 CBC 模式得到的密文进行异或（为了区分，我们分别叫它们 AES密文 和 CBC密文好了，其实就是差了一个异或的值）。由于我们已经知道 gift2 的第一组明文了，想要获取其 AES 密文 只需要用 key2 加密一下就好了。那么目前的问题就是如何获得其 CBC 密文，即获得 。而想要获得第一组的 CBC 密文，我们只需要获取第二组的 AES 密文和 CBC 密文，让他们异或一下就好了，而获取第二组的 CBC 密文……，因此问题就来到了最后一组。而最后一组的 CBC密文我们是知道的，由于 key2 爆出来了，其 sha256 我们也能算，只需要 6 个字节，因为还有 10 个字节的填充符号 &，于是 AES 密文也有了，这样就能有前一组的 CBC 密文，有了前一组的 CBC 密文，就能有前前一组的密文了……
from Crypto.Cipher import AES
import binascii
import hashlib
def xor(a,b):
tmp = ""
for i,j in zip(a,b):
tmp+=chr(i^j)
key2 = b'tn5-ix6L#tCaG}i6'
enc_gift2 = "918096cfa3b76d6622914395c7e28eef"
h = binascii.unhexlify(hashlib.sha256(key2).hexdigest())[:11]
gift2 = b'I tell you this, for when my days have come to an end , you, shall be King.'+h
gift2 += b'&'*10
M = []
for i in range(0,len(gift2),16):
M.append(gift2[i:i+16])
Minv = M[::-1]
nowcipher = bytes.fromhex(enc_gift2)
for i in range(6):
dec = AES.new(key2, AES.MODE_ECB)
m = dec.decrypt(nowcipher)
precipher = xor(Minv[i],m)
nowcipher = precipher
print(precipher)
得到 a3eae82b4c491e0e
结合 assert (flag[13] == 45 and flag[18] == 45 and flag[23] == 45 and flag[28] == 45)
显然 flag 是一个 uuid，于是最终的 flag 为 flag{4ff732dd-2b74-45fd-a3ea-e82b4c491e0e}
[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)
bh + bm + bl = a * x + kp
bh * 2^528 + bl = a * x - bm * 2^400 + kp
238 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'cTmkMbxfcx05|x1dxc7x13xbaSexe0xbdxc0xd9xa3x8cwox82yN[B&x80xd7KPwQ`x9cxbf<yx8ex8ax97exa074xb2'
#c7-11ee-ae14-ac1203ab14da}
首先看到
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)]
是一个典型的 AGCD 的攻击场景，这里暂时就不细说了，感兴趣的读者可以看这篇文章 https://martinralbrecht.wordpress.com/2020/03/21/the-approximate-gcd-problem/
用到的格子就是
ns = [38630062416586710341458654419912504176237737247477839749085033080367529539859992076587411537805430366799412095876782912512744262957062106155418341531142309858429218208463637096843365217114990765965110566415965985105403996944993619708417839598461935470469097206342256014086162845948208599334925650727933097059538199199685364793545286980392966271769914201657672004082101110775504946586957241075964270454872257405872181588544468173017149763827540561921126826597515171761064800381983526515300315517818122598179574900255685121991744205071544970, 41522753602903133841910260331594875922287719226997542592715810409935551768308104573333760854332533376702631593490915962706512143045107096658851885513727202513616813054397657610854303071682604806070009002234312854968365250748142324994926715544722158698813288131533399544263105858513134170084625526223987620550110255872688155827773099232631041345207194483609514502522566888883736218471849075697433311580004701384847571029783514418685068903758509270527252444771313048094566344002411364378658592832008194309873599342916391769027015343562030852, 41542983120532762175372001624404625565366126179958909731196555044290633581761361918706298428954501507557598076910710787422049443564800530253137695341299743714514361560156305534490483794181933110893966453220306980682146624294992100948497284459992930850081254114996830645068636306625330524465991656430799359422407117440063911943625477783216502523414967017151717597372146324488526509879620785458016456593044828784565522423332830549325397893426472247197776412026158371655860380929692662547882654137064941217130915364306358205055760044763651406, 42853015443318352230776688785915441259875645365236808434164117288657978345098324019250085686482568413223085548506789311679316323466083886556772338612177680666217592255234589446979456714341877135596118517098603502394776049958587301113539552072352462301070489369653155854389890761241450743607560719433910573462283304103064437843063566946231984094581307498714742271881862348689297267558023093643893310002803310596286441071314219020032740336515363830250477649030557311461077069407775907176409762823453607196260454965048316567154365877848652918, 31152961872836435078296602982779340735140569916125711058616435902653202922218293684857125091648631460215120167354825278469413413558325850576700866199515219603448136082693185200558425103833947831228064760642508443585470729998592994719564254894176473779555436230174300038353978808432410463449170865897259181312953584408177790825688497584119467820716449210429423337019604137134889051973100340798405991782200038835066294194815913887924272593864934325496116821854183293510325217934617021428710898873475027666892706022106386340733691632884942848]
x0,x1,x2,x3,x4 = ns
B = matrix(ZZ,[[2^256,x1,x2,x3,x4],[0,-x0,0,0,0],[0,0,-x0,0,0],[0,0,0,-x0,0],[0,0,0,0,-x0]])
L = B.LLL()
ans= L[0][0] // 2^256
p0 = abs(ans)
p = (x0 // p0)
# p = 293423658885957174953198318664231534672400520068303593221989900395768107225130267646792968959460384248015583618158947268381852534151783869878808621629530642974652628810907251607210136313789978156955302211733219987661815438401343683
key1 = long_to_bytes(int(p))[:32]
有了 p 之后，我们就能够获取到 ms，而 ms = [random.getrandbits(256) for _ in range(num1)]，
另外下面还有一个
for i in range(num2):
a = random.getrandbits(512)
因此根据 ms 和 a，典型的 mt19937 预测随机数，就能搞到iv，然后看到
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))
这里加密用的是 key1 而不是 key，（难崩）因此根本不需要管 key2，直接用 iv 和 key1 进行一个 AES 密文的解即可。
ns = [38630062416586710341458654419912504176237737247477839749085033080367529539859992076587411537805430366799412095876782912512744262957062106155418341531142309858429218208463637096843365217114990765965110566415965985105403996944993619708417839598461935470469097206342256014086162845948208599334925650727933097059538199199685364793545286980392966271769914201657672004082101110775504946586957241075964270454872257405872181588544468173017149763827540561921126826597515171761064800381983526515300315517818122598179574900255685121991744205071544970, 41522753602903133841910260331594875922287719226997542592715810409935551768308104573333760854332533376702631593490915962706512143045107096658851885513727202513616813054397657610854303071682604806070009002234312854968365250748142324994926715544722158698813288131533399544263105858513134170084625526223987620550110255872688155827773099232631041345207194483609514502522566888883736218471849075697433311580004701384847571029783514418685068903758509270527252444771313048094566344002411364378658592832008194309873599342916391769027015343562030852, 41542983120532762175372001624404625565366126179958909731196555044290633581761361918706298428954501507557598076910710787422049443564800530253137695341299743714514361560156305534490483794181933110893966453220306980682146624294992100948497284459992930850081254114996830645068636306625330524465991656430799359422407117440063911943625477783216502523414967017151717597372146324488526509879620785458016456593044828784565522423332830549325397893426472247197776412026158371655860380929692662547882654137064941217130915364306358205055760044763651406, 42853015443318352230776688785915441259875645365236808434164117288657978345098324019250085686482568413223085548506789311679316323466083886556772338612177680666217592255234589446979456714341877135596118517098603502394776049958587301113539552072352462301070489369653155854389890761241450743607560719433910573462283304103064437843063566946231984094581307498714742271881862348689297267558023093643893310002803310596286441071314219020032740336515363830250477649030557311461077069407775907176409762823453607196260454965048316567154365877848652918, 31152961872836435078296602982779340735140569916125711058616435902653202922218293684857125091648631460215120167354825278469413413558325850576700866199515219603448136082693185200558425103833947831228064760642508443585470729998592994719564254894176473779555436230174300038353978808432410463449170865897259181312953584408177790825688497584119467820716449210429423337019604137134889051973100340798405991782200038835066294194815913887924272593864934325496116821854183293510325217934617021428710898873475027666892706022106386340733691632884942848]
p = 293423658885957174953198318664231534672400520068303593221989900395768107225130267646792968959460384248015583618158947268381852534151783869878808621629530642974652628810907251607210136313789978156955302211733219987661815438401343683
ms = [i%p for i in ns]
x = []
for each in ms:
tmp = each
while tmp >0:
x.append(tmp%(2**32))
tmp >>= 32
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]
for each in A:
tmp = each
while tmp >0:
x.append(tmp%(2**32))
tmp >>= 32
print(len(x))
from MT19937_Crack import *
mtb = MT19937Recover()
result = mtb.go_on(x)
enc = b'cTmkMbxfcx05|x1dxc7x13xbaSexe0xbdxc0xd9xa3x8cwox82yN[B&x80xd7KPwQ`x9cxbf<yx8ex8ax97exa074xb2'
import random
from Crypto.Util.number import *
from Crypto.Cipher import AES
key1 = b'0b5e732a48fc8c6f5ac6366212d2bc59'
iv = long_to_bytes(result.getrandbits(128))
aes = AES.new(key1,AES.MODE_CBC,iv)
enc = aes.decrypt(enc)
print(enc)
得到 b’flag{86baa4ed-5ec7-11ee-ae14-ac1203ab14da}x06x06x06x06x06x06′
当然，如果还是想要解出 key2 ，其实这就是 2022 年全国高校密码数学挑战赛的一个赛题，可以去看一下 @tover 的博客 https://tover.xyz/p/HNP-note/#Level-3 ，写的挺详细了已经。
[SecretShare]
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
# res = a0+a1*x+a2*x^2+a3*x3+...+a20*x20
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
这道题就更简单了（可能又是出题失误，信息放出来多了），
其中 f(x) 函数可以记为
数组 A 和 X 都是由 21 个 1024 比特的数组成，其中 A 的后 20 个是 random.getrandbits(1024)， 21 个 X 都是 random.getrandbits(1024)
1024/32*21=672，足足的了。直接就能往前把 20 个 a 全部恢复。这里又把 x 全部给出来了，对应的 r 也给了，P 就是
那直接
再解一下 RSA 就完活了。
with open("output.txt") as f:
data = f.read().split("n")[:-1]
X=[]
R=[]
for each in data:
tm = each.split(" ")
X.append(int(tm[0]))
R.append(int(tm[1]))
print(len(X))
x = []
for each in X:
tmp = each
while tmp >0:
x.append(tmp%(2**32))
tmp >>= 32
print(len(x))
from MT19937_Crack import *
mtb = MT19937Recover()
result = mtb.go_back(x,608)
def factory(res):
ans=[]
for i in range(0,len(res)//32):
tmp = 0
for j in range(32):
tmp+=res[32*i+j]<<(j*32)
ans.append(tmp)
return ans
A = factory(result)
value = result+x
result = mtb.go_back(value,32)
A = factory(result)+A
print(len(A))
x = X[0]
res = R[0]
p = 667548632459029899397299221540978856425474915828934339291333387574324630349258515018972045406265448494845331262999241448002076917383740651362641947814545076390796789402373579283727117618532504865966299599663825771187433223531022829811594806917984414530614469374596457149431218829297339079019894262229453357029
for i in range(1,21):
res = (res-A[i-1]*x**i)%p
N = 11790604055677230214731474049594783873473779547159534481643303694816346271798870343160061559787963631020684982858033776446193418629055210874285696446209220404060653230407249409973790191858423402504530660556839353260629987853933304089439885784684686555554108157760445567974629355878575105480273451284714281430590737346099023372211403461861104391534461524711472734572409128196536805998116015230502045333769525693468193385557827209520108839913096017750428926467123493650506193757937746017474062985480713594474378324234033232933140389879312722642144536418253323908290256009510135710208223393009237664704631175216240376891
p=res
q=N//res
c = 9658009093151541277762773618550582280013680172161026781649630205505443184765264518709081169475689440555639354980432557616120809346519461077355134139495745998317849357705381020225760061125236265304057301286196004542729553944161451832173970613915423841610378207266606500956362098150141825329354727367056070349148059780287916811442861961254066733726576151134458892613951223277692935141880749737598416235307087782001086096114978527447987308876878393763055893556123029990282534497668077854186604106027698257663251502775547705641708624619340185646943640576690633662704397191379303254341343433077302686466850600522990402912
e = 65537
from Crypto.Util.number import *
d = inverse(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,p*q)))
原文始发于微信公众号（Van1sh）：2023 鹏程杯
