2023 鹏程杯

密码学 7个月前 admin
118 0 0

周末打了一下鹏城杯,密码学方向的赛题都是一些“老东西”拼凑起来的。唯一一个不熟悉的 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 模式就能做了。

2023 鹏程杯

首先是 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个字节。

2023 鹏程杯

爆破方案就是,根据 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(256for _ in range(num1)]
qs = [getPrime(1024for _ 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(256for _ in range(num1)]
qs = [getPrime(1024for _ in range(num1)]
ns = [p * qs[_] + ms[_] for _ in range(num1)]

是一个典型的 AGCD 的攻击场景,这里暂时就不细说了,感兴趣的读者可以看这篇文章 https://martinralbrecht.wordpress.com/2020/03/21/the-approximate-gcd-problem/

用到的格子就是

2023 鹏程杯

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 鹏程杯

版权声明:admin 发表于 2023年11月7日 下午3:12。
转载请注明:2023 鹏程杯 | CTF导航

相关文章

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...