上周去福州参与了 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(320) for i in range(t+1)]
messages = [b"114514" * (i+1) for 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，所以可以拿到的关系式是
于是构造格子
则存在向量 ，能够使得
于是我们用 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+1) for 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, 1, 1, 1, 1, 1, 1, 1]) # 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(0, 2 ** 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(0, 2 ** (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》
结论在这里
具体的推导过程这里就不再赘述了，感兴趣的读者可以直接去翻论文。
代码也不难实现
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 数字中国积分争夺赛 线下
