春秋杯春季赛2023

checkin

先连分数求解pell曲线的最小整数解，在二项式展开求指数part1和part2

pell曲线先求出x，y

# pell曲线  
# 求解 x^2 - N*y^2 = 1
def pell (N , numTry = 500):
    sols = []
    cf = continued_fraction ( sqrt ( N ))
    for i in range ( numTry ):
        denom = cf . denominator ( i )
        numer = cf . numerator ( i )
        if numer ^2 - N * denom ^2 == 1:
            sols.append((ZZ(numer) , ZZ(denom)))
    return sols
D = 1117
r = pell(D)[0]  # 默认取最小
print(r)

# 二项式展开
enc1 = pow(233 * n ** 2 + 1, part1, n ** 3)

$enc_1 = (233*n^{2} +1)^{part1} \pmod{n^3}$

$enc_1 = C_{part1}^{0}*(233*n^2)^{0}*1^{part1} + C_{part1}^{1} *(233*n^2)^{1}*1^{part1-1} + C_{part1}^{2} *(233*n^2)^{2}*1^{part1-2}.....$

后面都模$n^{3}$都是0

$enc_1 = 1 + part1 *(233*n^2)$

$part1 = (enc_1 - 1)/(233*n^2)$

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

n = 14381700422128582509148801752355744589949207890477326887251636389639477554903212313766087310581920423926674144511237847467160303159477932732842314969782540035709454603184976310835433114879043016737665256729350745769071186849072915716081380191025215059636548339167264601163525017898164466972776553148697204889820118261937316228241099344357088387154112255824092894798716597134811437852876763391697588672779069166285303075312833415574850549277205130215394422655325352478386576833373623679069271857652029364332047485797407322257853316210866532938722911480593571175419708834718860211036796987231227104370259051299799633809
enc1 = 7213976567554002619445032200800186986758840297933991288547009708561953107405266725278346810536664670987171549114913443730366439254199110599202411546254632702440251000149674899033994570393935743323319736976929843596350656674709510612789987746895513057821629144725499933366382123251520676386059405796801097683107223771674383940907066300331503757142088898427893069444164604408189686282018392714450005250018004986102062209998463347007934222341910941474212611569508001910685822097788669516018081617394144015000387497289693096617795809933540456797387940627782045397249431573540932386564021712811633992948508497879189416719996092292320828635490820907122756459412206735413770335545012892724496210585503157766011075566023635046144730429791359690237088629187946232458937292767085665897489251315749496284368726255508362410603108788759785472319449267909859926786774679533591222665476101832482161295321411313525830843915966136814748249906589458905410141906965538387896747375546846618213595165688661941876715858338407833641907024891922856719044736945863722003318526031957256722493189062624177017279248142024760515092698242159769372410662895078523142768353100643884341413944795392762315999109544070401451087596138520908569234305384182336436670714204963907240715652950621301644972412252424876159530992
enc2 = 15954854445966181136742750543358176358186230663706091821454832527034640100670779737656720251005109942306013877086451482243141488450122353285697850016200364912263403464109626937525725210545566742746628476797261121321515812788726862118315480354196115424526212965145342675007815411995594752584377871686965531829990461770047418586001518916553661158567047779694730702789677326905844275827365395845945286695577426050334364557405151339008293258932006267159313380746863008928500607405457044370494583863960981060999695448408234857505591647503423149271589648863473472196402149897680041851877198062464480400493467334040101779732999029043327947071232256187123316057998759518569161852646625701393295408789279678540894319137126821001853808931387200759810381958895695749251834840804088478214013923869059004663359509316215974475427057000629842098545503905230785431115754636129549758888267877395566717448365986552725726428222769339088308242580851434964429627168365161743834285778996916154182286570122208454025753108647581888781783757375011437394936853319184725324597963035778640646869326035848170752766298225095197226934969602554875402243303906613183431896300664684256018886119255870435413622515792072064528098344111446380223430819596310173312668368618931885819458529703118195242890075359424013033800260927722161030183373647798407301688760998313223874318513944409702828538509864933624724225689414495687466779277994989628367119101

part1 = (enc1 - 1) // (233*n^2)
flag1 = n2s(int(part1))
print(flag1)

# pell 方程
x,y = (87897747594260774254246835664214545379849, 2629972211566463612149241455626172190220)

x = var('x')
f = x*(x-1)*y^2*n^2 + 2*x*y*n + 2 - 2*enc2
part2 = f.roots()[0][0]
flag2 = n2s(int(part2))
print(flag2)

flag = flag1 + flag2
print(flag)

part2 一样的，也是二项式展开，不懂就问我

x = var('x') # 这个是声明 x 是变量

f = x(x-1)y^2n^2 + 2xyn + 2 - 2*enc2 # 一个关于x的方程

part2 = f.roots() # f.roots() 是方程的解

backdoor

除了RSA还有什么非对称加密呢，那么请了解一下ECC，和函数EllipticCurve

EllipticCurve(F, [A, B]) => y^2 = x^3 + A*x + B

E1 = EllipticCurve([A,B,C,D,E]) => y^2 + Axy + Cy = x^3 + Bx^2 + D*x + E

# 自己在sagemath构造一下
P = getPrime(512) 
F = GF(P)      # 有限域
E = EllipticCurve(F,[9,99,999,9999,99999])
print(E)       # y^2 + 9*x*y + 999*y = x^3 + 99*x^2 + 9999*x + 99999 
E = EllipticCurve([9,99])
print(E)       # y^2 = x^3 + 9*x + 99

那么开始解题

已知：

$M1 = k1 * G$

$Y = x * G$

$t = 1$

$z = (k1 - w * t) * G + (-a*k1 - b) * Y$

$shared\_key_2 = k2*B\_$

$\Rightarrow z = M1 - w*G - a*x*M1 - b*x*G$

from Crypto.Util.number import *
from gmpy2 import *
from libnum import *
from hashlib import *
from Crypto.Cipher import AES
(w,a,b,x) = (31889563, 31153, 28517, 763220531)
(A,B,P) = (1064988096, 802063264240, 12565302212045582769124388577074506881895777499095598016237085270545754804754108580101112266821575105979557524040668050927829331647411956215940656838233527)
F = GF(P)
E = EllipticCurve(F, [A, B])
G = E(359297413048687497387015267480858122712978942384458634636826020013871463646849523577260820163767471924019580831592309960165276513810592046624940283279131, 9290586933629395882565073588501573863992359052743649536992808088692463307334265060644810911389976524008568647496608901222631270760608733724291675910247770)

M1 = E(10930305358553250299911486296334290816447877698513318419802777123689138630792465404548228252534960885714060411282825155604339364568677765849414624286307139, 7974701243567912294657709972665114029771010872297725947444110914737157017082782484356147938296124777392629435915168481799494053881335678760116023075462921)
M2 = E(497353451039150377961380023736260648366248764299414896780530627602565037872686230259859191906258041016214805015473019277626331812412272940029276101709693, 8439756863534455395772111050047162924667310322829095861192323688205133726655589045018003963413676473738236408975953021037765999542116607686218566948766462)
B_ = E(5516900502352630982628557924432908395278078868116449817099410694627060720635892997830736032175084336697081211958825053352950153336574705799801251193930256, 10314456103976125214338213393161012551632498638755274752918126246399488480437083278584365543698685202192543021224052941574332651066234126608624976216302370)
z = M1 - w*G - a*x*M1 - b*x*G
print(z)

k2 = sha256(str(z[0]).encode()).digest()[:6]
k2 = bytes_to_long(k2)
key = k2*(B_)

# print(key[0])

def easy_enc(pt,key):       # 就是aes加密
    key = md5(str(int(key[0])).encode()).digest()
    cipher = AES.new(key, AES.MODE_ECB)
    ct = cipher.encrypt(pad(pt,16))
    print(ct)
def de_enc(ct,key):          # 写一个解密函数
    key = md5(str(int(key[0])).encode()).digest()
    cipher = AES.new(key,AES.MODE_ECB)
    pt = cipher.decrypt(ct)
    return pt
ct = b'\x1a\xfb\xa2\xe1\x86\x04\xfak\x9a\xa3\xd15\xb8\x16\x1d\xbc\xa9S\xf5;\xfa\xf1\x08dn~\xd4\x94\xa4;^*\xf6\xd7\xf10\xa3\xe1k`\x1f-\xef\x80\x16\x80\x80\xe2'
flag = de_enc(ct,key)
print(flag)

ecdsa

题目

import os
import ecdsa
import hashlib
from Crypto.Util.number import *
from Crypto.Util.strxor import strxor as xor
import secret

p = getPrime(256)                  # 256
gen = lambda: p + getPrime(16)     # p + 16bits
pad = lambda m: m + os.urandom(32 - len(m) % 32)   # 匿名函数

key = os.urandom(30)               # 随机数
sk = ecdsa.SigningKey.from_secret_exponent(     # 在签名?  
    secexp=bytes_to_long(key),
    curve=ecdsa.SECP256k1            
)

sig1 = sk.sign(data=b'This is the first message.', k=gen()).hex()   # 生成个key1 给他签名
sig2 = sk.sign(data=b'Here is another message.'  , k=gen()).hex()   # 生成个key2 给他签名
enc  = xor( hashlib.sha512(key).digest(), pad(secret.flag)).hex()   # secret 加密

print(f"{sig1 = }\n{sig2 = }\n{enc = }")
'''
sig1 = '3f4a6f288e35a4397201d246a98c1f9cfa463e67717fbbdcbd26d7fac75f875855455c2bfb355f7f593ffbe4c4bd1fc729cc129976b56905639100c8ac716b37'
sig2 = '9f563b21f0ee31b2f7a1a8c6edc8ff23b63e0a9d5dd4a699ecc3164871b4982df51bb2feb4bc06c578afd21d3e6227231dd5fe1d8440f3dcd025fd3ea68f5516'
enc  = 'cc66d251bfa54954890c81dc1c607bae716573949f327db18aa1f4c0f420b8d29dc7e7ff9edb17b90306bd2aa753fc3fd4dafb9cc4b771cbdd79000ef05a40c0'
'''

浅：下面的运算都是在$ecdsa.SECP256k1$的阶下的

print(ecdsa.SECP256k1.generator.order()) 
# 115792089237316195423570985008687907852837564279074904382605163141518161494337

已知：

$key_1 = key_0 + e_1$

$key_2 = key_0 + e_2$

$key_1*s_1 = sha256(m_1) + r_1 * key$

$key_2*s_2 = sha256(m_2) + r_2 * key$

$key_0 :(256bits) \\ e_1,e_2 : (16bits) \\ key:(240bits)$

$output:(s_1,r_1),(s_2,r_2),(m_1),(m_2)$

求key

$key1 = (m1 + r1 * key ) * s1^{-1}$

$key2 = (m2 + r2 * key ) * s2^{-1}$

$key_1 - key_2 = m_1*s_1^{-1} - m_2*s_2^{-1} + r_1 * key * s_1^{-1} - r_2 * key *s_2^{-1}$

$\Rightarrow key_1 - key_2 = m_1*s_1^{-1} - m_2*s_2^{-1} + key*(r_1 * s_1^{-1} - r_2 *s_2^{-1}) = e_1 - e_2$

$A = r_1 * s_1^{-1} - r_2 *s_2^{-1}$

$B = m_1*s_1^{-1} - m_2*s_2^{-1}$

$A*key + B = e_1 - e_2 $

$key:(240bits)$

Z为需要自己构造的数，在这里k为 $\Delta k$的$bits$

$Z =2^{16}/2^{240}$

\[ \left[ \begin{matrix} n & key & 1 \end{matrix} \right] * \left[ \begin{matrix} P & & \\ A & 2^{k}/2^{240} & \\ B & & 2^k \end{matrix} \right] = \left[ \begin{matrix} \Delta key & key*2^{16}/2^{240} & 2^{16} \end{matrix} \right] \]

from Crypto.Util.number import *
from gmpy2 import *
from libnum import *
from hashlib import *
from Crypto.Cipher import AES
import ecdsa
from Crypto.Util.strxor import *
from Crypto.Util.strxor import strxor as xor

sig1 = '3f4a6f288e35a4397201d246a98c1f9cfa463e67717fbbdcbd26d7fac75f875855455c2bfb355f7f593ffbe4c4bd1fc729cc129976b56905639100c8ac716b37'
sig2 = '9f563b21f0ee31b2f7a1a8c6edc8ff23b63e0a9d5dd4a699ecc3164871b4982df51bb2feb4bc06c578afd21d3e6227231dd5fe1d8440f3dcd025fd3ea68f5516'
enc  = 'cc66d251bfa54954890c81dc1c607bae716573949f327db18aa1f4c0f420b8d29dc7e7ff9edb17b90306bd2aa753fc3fd4dafb9cc4b771cbdd79000ef05a40c0'

m1 = 'This is the first message.'
m2 = 'Here is another message.'

p=ecdsa.SECP256k1.generator.order()
print(p)
r1 = bytes_to_long(bytes.fromhex(sig1[:len(sig1)//2]))
s1 = bytes_to_long(bytes.fromhex(sig1[len(sig1)//2:]))
r2 = bytes_to_long(bytes.fromhex(sig2[:len(sig2)//2]))
s2 = bytes_to_long(bytes.fromhex(sig2[len(sig2)//2:]))

# A = m_1*s_1 - m_2*s_2
# B = r_1 * s_1^{-1} - r_2 *s_2^{-1}
m1 = bytes_to_long(sha1(m1.encode()).digest())
m2 = bytes_to_long(sha1(m2.encode()).digest())

A = ZZ( r1 * invert(s1,p) - r2 * invert(s2,p) ) % p
B = ZZ( m1 * invert(s1,p) - m2 * invert(s2,p) ) % p 
p = ZZ(p)

RR=RationalField(256)
mat = [[p,0,0],[A,2^16/2^240,0],[B,0,2^16]]
M = Matrix(RR,mat)
L = M.LLL()[1][1]

d = L*2^240/2^16
d = n2s(int(d))
d = sha512(d).digest()
c = bytes.fromhex(enc)   # 等于long_to_bytes(int(enc,16))
m = strxor(d,c)
print(m)

hengxinyan

https://hengxinyan.github.io/2023/08/10/%E6%98%A5%E7%A7%8B%E6%9D%AF%E6%98%A5%E5%AD%A3%E8%B5%9B2023/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 hengxinyan !

无标签

巅峰极客2023

2023-08-10 hengxinyan

安洵杯2023

2023-08-10 hengxinyan