2024 数字中国积分争夺赛 线下

WriteUp 5个月前 admin
71 0 0

        上周去福州参与了 2024 数字中国积分争夺赛的线下赛,可以说是非常坐牢了,虽然线下有密码题,但相当于被零封了。半决赛是两道论文题,但不给外网,狗看摇头,直接放弃了;决赛的密码题也是在拿到提示后才秒的,还是太菜了。

半决赛

babysign

from Crypto.Util.number import *
from Crypto.Cipher import AES
from random import randint, getrandbits
from hashlib import sha256, md5
from secret import flag

def pad(x):
    return x + b"x00" * (16 - len(x) % 16)

def sign(message, sk):
    global state
    new_state = sum([state[i] * c[i] for i in range(t+1)]) % N
    state = [1] + state[2:] + [new_state]
    nonce = new_state
    r = pow(g, nonce, p) % q
    s = inverse(nonce, q) * (sk * r + int(sha256(message).hexdigest(), 16)) % q
    return r, s

p = getPrime(1024)
q = getPrime(200)
g = 3
N = getPrime(320)
sk = getrandbits(200)
n = 6
t = 3
state = [1] + [randint(0, N) for i in range(t)]
c = [getrandbits(320for i in range(t+1)]
messages = [b"114514" * (i+1for i in range(n)]

aes = AES.new(key = md5(long_to_bytes(sk)).digest(), mode = AES.MODE_ECB)
enc = bytes_to_long(aes.encrypt(pad(flag)))

R = []
S = []
for i in range(n):
    ri, si = sign(messages[i], sk)
    R.append(ri)
    S.append(si)

print(f"p = {p}")
print(f"q = {q}")
print(f"N = {N}")
print(f"c = {c}")
print(f"R = {R}")
print(f"S = {S}")
print(f"enc = {enc}")


'''
p = 109801600052935929456365619739090774744018564228266126895298370854583060266152566067050910664413174595254180168342854113664140621754039391358371714725945351244081609881596272127403394004476347628323577078665504222963051771234357235913552519631706169904604428523480875092201229951886321708322476191646278287459
q = 1534010635171832255493592219851988768205332262446560841823627
N = 1671811495531661330812416738621010063593181424673793819263629597437659960591290123919247440467161
c = [106776416449285738716536637012371007606517912489324067631030211869497087921567995484278464094531, 1715837348292346685726028809561895741872591211209467247755566110983055604970675950006417471270831, 1443377864705196276190981923608406365095804241719516313156828832409063105295874994697583367744683, 124895503161559483300377049815891880940590946520634177588086135558746292956861164538005362039493]
R = [1036453797023528666642364160281802950096909436763545285308908, 326371814110787606259271831742179072992357254456037768751664, 1437243598089031382422432333623847779257497388264397577671271, 440515561264248565323690318966702644727161426338099283113942, 221245316768170693597429105627937425200238033771394941075094, 529581137481411636812547590854398500676430693974634023457833]
S = [1111142152550639579984883926946293370005210267192481871482655, 32497371165697871198056313936692832832674660727524072345292, 1336105468180489723126352552624331076455931680897754471797531, 89722925057469245019281719776680657046140458511161695318273, 424403247604436453990397153926641348093826082342902295667702, 901688545427576163296143946245459273962270838353199393550879]
enc = 37704615820585836453727418413787636506971406940247588901450985146152853279614027174463887437859465678117864533232085
'''


相关论文:《“Pseudo-Random” Number Generation within Cryptographic Algorithms: the DSS Case》

我们先来看一下论文中的实例,用了一个 DSA 签名,给出了两条消息以及其对应的签名。其中用于生成临时密钥 的 PRNG 是 LCG,所以可以拿到的关系式是

2024 数字中国积分争夺赛 线下

于是构造格子

则存在向量 ,能够使得

于是我们用 LLL 算法对 进行格基规约,

不过直接规约可能得不到我们期望的这个向量,因此这里我们可以设

其中 gamma1 是和 相同数量级的一个数,gamma2 是和 x 相同数量级的一个数,这样就能够让 都趋向于 1,然后我们就再在这个规约后的格子上找一个 的 CVP 就行了。

以上大概就是这篇论文的核心思想了,然后我们回到这道题目。

题目仍然是一个 DSA 的签名,但是其中用于生成临时密钥 r 的伪随机数 state (这里设为 k)是由 LCG 的变体生成而来,可以表示为

其中 已知,

然后题目给出了六条消息和对应的签名,根据 DSA 签名算法,于是我们有同余式组

再加上

沿用上面的思想,我们构造格子

则存在向量 ,能够使得

对应的调一下

然后我们就再在这个规约后的格子上找一个 的 CVP 就行了。

代码实现

from Crypto.Util.number import *
from Crypto.Cipher import AES
from random import randint, getrandbits
from hashlib import sha256, md5

p = 
q = 
N = 
c = 
R = 
S = 
enc = 

r0,r1,r2,r3,r4,r5 = R
s0,s1,s2,s3,s4,s5 = S
c0,c1,c2,c3 = c
E1=2^320
E2=2^200

L = Matrix(QQ,
[   [ s0,  0,  0,  0,  0,  0,-c1,  0,  0,1/E1,0,0,0,0,0,0],  
    [  0, s1,  0,  0,  0,  0,-c2,-c1,  0,0,1/E1,0,0,0,0,0], 
    [  0,  0, s2,  0,  0,  0,-c3,-c2,-c1,0,0,1/E1,0,0,0,0], 
    [  0,  0,  0, s3,  0,  0,  1,-c3,-c2,0,0,0,1/E1,0,0,0], 
    [  0,  0,  0,  0, s4,  0,  0,  1,-c3,0,0,0,0,1/E1,0,0], 
    [  0,  0,  0,  0,  0, s5,  0,  0,  1,0,0,0,0,0,1/E1,0], 
    [-r0,-r1,-r2,-r3,-r4,-r5,  0,  0,  0,0,0,0,0,0,0,1/E2], 
    [  q,  0,  0,  0,  0,  0,  0,  0,  0,0,0,0,0,0,0,0], 
    [  0,  q,  0,  0,  0,  0,  0,  0,  0,0,0,0,0,0,0,0], 
    [  0,  0,  q,  0,  0,  0,  0,  0,  0,0,0,0,0,0,0,0], 
    [  0,  0,  0,  q,  0,  0,  0,  0,  0,0,0,0,0,0,0,0], 
    [  0,  0,  0,  0,  q,  0,  0,  0,  0,0,0,0,0,0,0,0], 
    [  0,  0,  0,  0,  0,  q,  0,  0,  0,0,0,0,0,0,0,0], 
    [  0,  0,  0,  0,  0,  0,  N,  0,  0,0,0,0,0,0,0,0], 
    [  0,  0,  0,  0,  0,  0,  0,  N,  0,0,0,0,0,0,0,0], 
    [  0,  0,  0,  0,  0,  0,  0,  0,  N,0,0,0,0,0,0,0]]
)



L_lll = L.LLL()

def BabaisClosestPlaneAlgorithm(L, w):
    G, _ = L.gram_schmidt()
    t = w
    i = L.nrows() - 1
    while i >= 0:
        w -= round( (w*G[i]) / G[i].norm()**2 ) * L[i]
        i -= 1
    return t - w

messages = [b"114514" * (i+1for i in range(6)]


m0,m1,m2,m3,m4,m5 = [int(sha256(i).hexdigest(),16)  for i in messages]
Y = vector([m0, m1, m2, m3 , m4, m5, c0, c0, c0, 1111111]) # target vector
X = BabaisClosestPlaneAlgorithm(L_lll, Y)
sk = X[-1]*E2##

aes = AES.new(key = md5(long_to_bytes(int(sk))).digest(), mode = AES.MODE_ECB)
flag = aes.decrypt(long_to_bytes(enc))
print(flag)

# b'flag{e0f287c8-2476-7726-e674-e45eb01cf9e7}x00x00x00x00x00x00'

badpq

from Crypto.Util.number import *
from gmpy2 import next_prime
from random import randint

flag = b'xxx'
m = bytes_to_long(flag)

low_bits = 360
def gen_keys1():
    while True:
        try:
            p = getPrime(512)
            q = next_prime((p + randint(02 ** 360))//2*3)
            n = p * q
            phi = (p - 1) * (q - 1)
            d = randint(n ** 0.314, n ** 0.324)
            e = inverse(d, phi)
            break
        except:
            continue
    return e,n

def gen_keys2():
    while True:
        try:
            p = getPrime(510)
            q = next_prime(p + randint(02 ** (low_bits-104)))
            n = p * q
            phi = (p - 1) * (q - 1)
            d = randint(n ** 0.39, n ** 0.40)
            e = inverse(d, phi)
            break
        except:
            continue
    return e,n

e1,n1 = gen_keys1()
e2,n2 = gen_keys2()
c1 = pow(m,e1,n1)
c2 = pow(c1,e2,n2)

print("e1 = %d" % e1)
print("n1 = %d" % n1)
print("e2 = %d" % e2)
print("n2 = %d" % n2)
print("c2 = %d" % c2)

'''
e1 = 18001900173273719697391359353065232588449445170500945278647026949882355462724616069496074220555205054223521563993535173526672654477052637135073850629368359760892593105580894657781145338498708910046867860809612182650396938314935515110746278735104321963474519329060780012648139288786428974872599159200799968861
n1 = 114983128977868545043878741490990841725001781170870943692742872722435872925766900876518759545501224415903088891960418988764246950692178608854128364602590133628277645700350621807181459512884527559415209940334803723409668501800865947233583791696682819330636722731719996740051062092325218479716111580978978318717
e2 = 7718828321409063503456557148130451825245011305255137327301507428857264066773401748265681469527691164751198083878974951925773362451876651796344869784288867599731617157598751909356640691448463717904387806712890699566812299441439984665934303863456033156384479932954935465004485243369594662503112519106793007089
n2 = 7856751739787337705195346372852751551833071857633944397270882313800491497819451307982952136444042851493492063223934118957076561459007841813630454948516315244049818693762878799490675183046955565559919856007445544097406228995279812965467063255407439731312449987300708909474124666222312642817168217594393330587
c2 = 6132778539680603017599783781880068343895992089783012900815347527161556022759968558421014660962178507812074236445227262121292798560258918858857031931943379326675974691584836091977353020621002518061553154449283246151894445570248461279275100980500478880169957064927543488924186623613499698653636069914257536538
'''

相关论文:《Generalization of Some Attacks on RSA with Small Prime Combination and Small Private Exponent》

结论在这里

2024 数字中国积分争夺赛 线下

具体的推导过程这里就不再赘述了,感兴趣的读者可以直接去翻论文。

代码也不难实现

from Crypto.Util.number import *


def attack_rsa_with_small_prime_comb_and_small_pri(i,j,e,n):
    # << Generalization of Some Attacks on RSA with Small Prime Combination and Small Private Exponent >>
    for kd in continued_fraction(e/(n-isqrt(i/j*n)-isqrt(j/i*n)+1)).convergents():
        tk = kd.numerator()
        td = kd.denominator()
        if int(pow(2,e*td,n)) == 2:
            print("[+] Success !")
            print("d =",td)
            return td

e1 = 18001900173273719697391359353065232588449445170500945278647026949882355462724616069496074220555205054223521563993535173526672654477052637135073850629368359760892593105580894657781145338498708910046867860809612182650396938314935515110746278735104321963474519329060780012648139288786428974872599159200799968861
n1 = 114983128977868545043878741490990841725001781170870943692742872722435872925766900876518759545501224415903088891960418988764246950692178608854128364602590133628277645700350621807181459512884527559415209940334803723409668501800865947233583791696682819330636722731719996740051062092325218479716111580978978318717
e2 = 7718828321409063503456557148130451825245011305255137327301507428857264066773401748265681469527691164751198083878974951925773362451876651796344869784288867599731617157598751909356640691448463717904387806712890699566812299441439984665934303863456033156384479932954935465004485243369594662503112519106793007089
n2 = 7856751739787337705195346372852751551833071857633944397270882313800491497819451307982952136444042851493492063223934118957076561459007841813630454948516315244049818693762878799490675183046955565559919856007445544097406228995279812965467063255407439731312449987300708909474124666222312642817168217594393330587
c2 = 6132778539680603017599783781880068343895992089783012900815347527161556022759968558421014660962178507812074236445227262121292798560258918858857031931943379326675974691584836091977353020621002518061553154449283246151894445570248461279275100980500478880169957064927543488924186623613499698653636069914257536538

d2 = attack_rsa_with_small_prime_comb_and_small_pri(1,1,e2,n2)
d1 = attack_rsa_with_small_prime_comb_and_small_pri(2,3,e1,n1)

c1 = pow(c2,d2,n2)

# c1 may bigger than n2
for k in range(100):
    m = pow(int(c1)+k*n2,d1,n1)
    flag = long_to_bytes(int(m))
    if b"flag" in flag:
        print(flag)

# b'flag{e8d4abc6c676f92e2f4874973d25c420}'

(PS:希望春秋以后的线下赛选题能不能稍微那啥一点,既不给上网,也不给资料,还选了这种论文题,着实多少大概也许有那么一些为难人。当然,也怪自己技不如人,毕竟人”国家队“还是能做得出来)

决赛

方程解密

这道题目是在所谓“共同防御”的赛制下,就是第一个解出的队伍会简单分享一下解题思路。所以当我还在台下想着怎么构造格子的时候,突然就听到这题被解出来了,大概就猜到这题应该不麻烦。当听着一血队伍磕磕巴巴地说着什么“维也纳攻击”的时候,就晓得这题的 v 大概率在 e/n 的连分数的收敛分数上了。于是立马掏出板子梭了一下,摸了一个三血。

n = 73327580327096363941184067076642123092520041405188442426515332851631548126961330943581818271126533401554180409968250088293241154125851089420726951106005516975653246248683570268351209255797480904614659468070562106048405454014895560596358058182901059878034793142208932022564549017033260867300211774028771035453
e = 57151226308943374680142794982010176222497765364529380268548935165758040222145627036162260994342075324103526381857344279597704799540499130349950141943084507238275546451525219742274348170961951271067509868049500661139141637437970076445350150361548157732135685521193407513224070010354999388515169624741885677283306163909232161839

for yx in continued_fraction(e/n).convergents():
        y = yx.numerator()
        x = yx.denominator()
        if int(y).bit_length()==100 and int(x).bit_length()==40:
         print(y)
         break

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


def pad(key):
    return key+(16-len(key))*b'x00'
    
c = b'xfaxf5g6xeerxb1x8cxefzxf2U~xe8x7fpx10xdcxafxf6xc6;x11#xd4xf6xf0xd2x89xe4]xe0xefRpxfex05.xb9xfbx8exa3jxeb+xf9x03xaa'
key1 = y
cipher=AES.new(pad(long_to_bytes(key1)),AES.MODE_ECB)
enc=cipher.decrypt(c)
print(enc)

b'flag{6bd49be8-aae3-11ee-b55f-701ab8f179b6}x00x00x00x00x00x00'

解了归解了,简单分析一下为啥叭。

根据题目有等式

其中 是 512 比特; 是 1083 比特; 是 100 比特, 是 50 比特, 是 40 比特

整理一下式子我们有

我们手里有 ,那就两边同除一个 ,有

移项一下

根据 Legendre’s theorem

只要证明   就可以证明  v/u 会在  e/n 的连分数的收敛分数上了。

两边都乘一个 ,那么只需要证明

简单观察一下各个元素的比特长度就知道这个不等式是成立的,所以我们能够在  e/n  的连分数的收敛分数上找到   v/u ,后面根据找到数据的比特长度判断一下就行。

原文始发于微信公众号(Van1sh):2024 数字中国积分争夺赛 线下

版权声明:admin 发表于 2024年5月29日 下午6:01。
转载请注明:2024 数字中国积分争夺赛 线下 | CTF导航

相关文章