ezDHKE
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
from random import randbytes, getrandbits
from flag import flag
def diffie_hellman(g, p, flag):
alice = getrandbits(1024)#私有密钥a
bob = getrandbits(1024)#私有密钥b
alice_c = pow(g, alice, p)#公钥A
bob_c = pow(g, bob, p)#公钥B
print(alice_c , bob_c)
key = sha256(long_to_bytes(pow(bob_c, alice, p))).digest()
iv = b"dasctfdasctfdasc"
aes = AES.new(key, AES.MODE_CBC, iv)
enc = aes.encrypt(flag)
print(enc)
def getp():
p = int(input("P = "))
assert isPrime(p)
assert p.bit_length() >= 1024 and p.bit_length() <= 2048
g = 2
diffie_hellman(g, p, flag)
getp()
Diffie-Hellman密钥交换问题，之前有做过类似的，但印象不深，一时没反应过来。
分析：
输入合适的p后，生成密钥，计算key并进行AES加密。可以知道只需要得到alice即私钥便可得到key，而私钥的获取涉及到离散对数问题，我们可以构造光滑数p来加快离散对数的求解。
生成光滑数p后，解离散对数得到私钥alice就ok了：
#生成p
import random
def init():
primes = []
p = 1
while len(primes) < 100:
p = next_prime(p)
primes.append(int(p))
return primes
def genMyPrime(bits):
while True:
g = 2
while g < 2 ** bits:
g *= random.choice(primes)
g += 1
if isPrime(g):
return g
primes = init()
p = genMyPrime(1024)
print(p)
g = 2
p = 11756781807369612568987946406116708206085796102104764370311211526129098969124132772485005472491601993647757712097892527606473674439580305334918428562672593410208130532152246109676304724083387637126229487238384816904854886474986809133953118441512847896818133054734855878261565007941944916923998347895163011420291
A = 100447359246949348381867879033659162186716190965156445467791956545782555036826256166345730437509009563652725624306280245993070519138454021746438791765254833502167527081906839407055364598768133602548346013805689415071667166625549580860279112795907460502972339544073504002919518792611294563149020034775342240140
B = 4247287287245724508382917583144074045696957472538918310401561723526170385929933056036081998581612703755233148777840904666643631066663388991313366579055098044398761886560525804928535027896287055517660010490420927936393289382752281731334844970406256807917777833328038494036774262372592299841830013393704286587284
iv = b"dasctfdasctfdasc"
enc = b'!\xf66:\xc8I\xa4\xa1\xc0\xff\x96"\xbbV\x05\xd9\x94S^\xb9\xa9IcBD\x7f\x85\xc2\xf4\xdf0\xe5\x88\x14b\xc1\xb0r\xcc\x81\xf1\xe9\xf8Mi\xf8\x86\xd3'
import sympy
alice = sympy.discrete_log(p, A, g)
print(alice)
alice = 3875366393484613574150768240935118185275848588096652363687457216841997708270865635136392149070869993078676753875041547438514367813659607838567750939174170795966804223187123410648065664477838330244241571829007823990351920291325744246570838904467234895777088947513707466123675829868672543642693499176019888137
from Crypto.Cipher import AES
key = sha256(long_to_bytes(pow(B,alice,p))).digest()
iv = b'dasctfdasctfdasc'
aes = AES.new(key,AES.MODE_CBC,iv)
flag = aes.decrypt(enc)
print(flag)
这道题在生成合适的p上多花了点时间，下次有经验了。
ezRSA
from Crypto.Util.number import *
from secret import secret, flag
def encrypt(m):
return pow(m, e, n)
assert flag == b"dasctf{" + secret + b"}"
e = 11
p = getPrime(512)
q = getPrime(512)
n = p * q
P = getPrime(512)
Q = getPrime(512)
N = P * Q
gift = P ^ (Q >> 16)
print(N, gift, pow(n, e, N))
print(encrypt(bytes_to_long(secret)),
encrypt(bytes_to_long(flag)))
# 75000029602085996700582008490482326525611947919932949726582734167668021800854674616074297109962078048435714672088452939300776268788888016125632084529419230038436738761550906906671010312930801751000022200360857089338231002088730471277277319253053479367509575754258003761447489654232217266317081318035524086377 8006730615575401350470175601463518481685396114003290299131469001242636369747855817476589805833427855228149768949773065563676033514362512835553274555294034 14183763184495367653522884147951054630177015952745593358354098952173965560488104213517563098676028516541915855754066719475487503348914181674929072472238449853082118064823835322313680705889432313419976738694317594843046001448855575986413338142129464525633835911168202553914150009081557835620953018542067857943
# 69307306970629523181683439240748426263979206546157895088924929426911355406769672385984829784804673821643976780928024209092360092670457978154309402591145689825571209515868435608753923870043647892816574684663993415796465074027369407799009929334083395577490711236614662941070610575313972839165233651342137645009 46997465834324781573963709865566777091686340553483507705539161842460528999282057880362259416654012854237739527277448599755805614622531827257136959664035098209206110290879482726083191005164961200125296999449598766201435057091624225218351537278712880859703730566080874333989361396420522357001928540408351500991
gift = P ^ (Q >> 16)
可通过这一行恢复P、Q来。已知P的高16位，那么可求Q的高x位，x稍比16小，为了更准确。再通过异或又可求P接下来的高x位，那么就知道了P的高16+x位，依次类推，可以逐步求出P、Q。
N = ...
gift = ...
pp = bin(gift)[2:][:16]
b = 512-16
gift = bin(gift)[2:][16:]
x = 5#大致算了下x最大应该为9
for i in range((512-16)//x):#类似分组
PP = int(pp+'0'*b,2)#已知的高位，填充0到512位
Qb = bin(N//PP)[2:][i*x:x*i+x]#算出Q的高位部分,即x位，5位
#print(Qb)
gb = gift[i*x:i*x+x]
pb = bin(int(gb,2)^int(Qb,2))[2:].zfill(x)#异或后前面的0会省略掉，进行填充
pp += pb
b -= x
for i in range(3):#还差1位或者两位
px = int(pp+bin(i)[2:],2)
if N%px == 0:
p = N//px
print(p)
break
搬的佬的wp，真不一定能顺利敲出来。
接着解RSA求n：
phi = (P-1)*(Q-1)
d = inverse(e,phi)
n = pow(c0,d,N)
输出了下位数1020位，少了点，n应该比N大，在原有基础上再加个N，得到1023位。
n = 83410392685813224685786027640778560521035854332627839979281105731457044069408118952629284089869335506983096270269822559619624906180108256504440296527471536363057103101146262613593336072556587341466840510200003498265457285439149541137127199088938421905041387224795918868443175561632999479925818053898100117419
最后一部分，
print(encrypt(bytes_to_long(secret)),
encrypt(bytes_to_long(flag)))
两个加密的明文是有重复的部分的，不知道是啥攻击，看了两个老佬的wp，说是相关明文攻击或关联信息攻击，也没找到相关的内容，暂时先记着。
def attack(c1, c2, a, b, e, n):
PR.< x >= PolynomialRing(Zmod(n))
g1 = x ^ e - c1
g2 = (a * x + b) ^ e - c2
def gcd(g1, g2):
while g2:
g1, g2 = g2, g1 % g2
return g1.monic()
return -gcd(g1, g2)[0]
for i in range(100):#secret长度未知，爆破
b = bytes_to_long(b"dasctf{"+b'\x00'*i+b"}")
flag = (attack(c2, c3, 256, b, 11, n))
if flag != n-1:
print(b'dasctf{'+long_to_bytes(flag)+b'}')
ezAlgebra
from Crypto.Util.number import getPrime, bytes_to_long
def YiJiuJiuQiNian(Wo, Xue, Hui, Le, Kai):
Qi = 1997
Che = Wo+Hui if Le==1 else Wo*Hui
while(Xue):
Qi += (pow(Che, Xue, Kai)) % Kai
Xue -= 1
return Qi
l = 512
m = bytes_to_long(flag)
p = getPrime(l)
q = getPrime(l//2)
r = getPrime(l//2)
n = p * q * r
t = getrandbits(32)
c1 = YiJiuJiuQiNian(t, 4, p, 1, n)
#(t+p)^4 mod n
c2 = YiJiuJiuQiNian(m, 19, t, 0, q)
#(m*t)^19 mod q
c3 = YiJiuJiuQiNian(m, 19, t, 1, q)
#(m+t)^19 mod q
print(f"n = {n}")
print(f"c1 = {c1}")
print(f"c2 = {c2}")
print(f"c3 = {c3}")
output:
n = 119156144845956004769507478085325079414190248780654060840257869477965140304727088685316579445017214576182010373548273474121727778923582544853293534996805340795355149795694121455249972628980952137874014208209750135683003125079012121116063371902985706907482988687895813788980275896804461285403779036508897592103
c1 = 185012145382155564763088060801282407144264652101028110644849089283749320447842262397065972319766119386744305208284231153853897076876529326779092899879401876069911627013491974285327376378421323298147156687497709488102574369005495618201253946225697404932436143348932178069698091761601958275626264379615139864425
c2 = 722022978284031841958768129010024257235769706227005483829360633993196299360813
c3 = 999691052172645326792013409327337026208773437618455136594949462410165608463231
首先根据**c1 = YiJiuJiuQiNian(t, 4, p, 1, n)**解出p和t来。
因为Le == 1，所以$Qi = 1997 + \sum_{i=1}^4 (t+p)^i (mod n)$
二项式展开并模上p，得到：
$Qi = 1997 +t^4+t^3+t^2+t = c1(mod p)$
在环p上求解多项式
PR.<x> = PolynomialRing(Zmod(n))
f = x^4+x^3+x^2+x-c1+1997
print(f.small_roots(X=2^32, beta=0.4)[0])
#t = 2915836867
t出来后带回$Qi = 1997 +t^4+t^3+t^2+t = c1(mod p)$与n求gcd得到p：
p = gcd((1997+t**4+t**3+t**2+t - c1), n)
print(p)
#12674045065380963936369006640913707206092165254372327547575287589116533343005456615635388048683828685030860153531390706945709086518510926980644275915726413
然后是两个最高19次的方程：
$Qi = 1997 + \sum_{i=1}^{19} (m\cdot t)^i (mod q)$
$Qi = 1997 + \sum_{i=1}^{19} (m+t)^i (mod q)$
用groebner_basis求q，相关的知识网上很少，只能问gpt了。
groebner_basis是一个数学计算库中的函数名，用于计算多项式环的 Groebner 基。在代数几何学中，一个多项式环是由多个变量和它们的系数组成的代数结构。Groebner 基是一个多项式环中的一组基础元素，可以用于多项式方程组求解、代数曲线的描述等问题。
Groebner 基可以理解为一种基础元素，类似于向量空间中的基向量。不同的 Groebner 基可以描述不同的几何对象，例如代数曲线、代数曲面等。在计算 Groebner 基时，通常需要使用一些算法，例如 Buchberger 算法、F4 算法等。
举例：
假设有方程组：
x^2 + y^2 - 1 = 0
x + y - 1 = 0
将这个方程组转化为一个多项式方程组，即：
f1 = x^2 + y^2 - 1
f2 = x + y - 1
我们可以使用 groebner_basis 函数来计算这个方程组的 Groebner 基：
from sympy import groebner
x, y = symbols('x y')
f1 = x**2 + y**2 - 1
f2 = x + y - 1
GB = groebner([f1, f2], x, y)
'''
GB = [y - sqrt(2)/2 - 1/2, x - sqrt(2)/2 - 1/2]
'''
而通过这个基我们可以知道方程组的解。
对于原题：
P.<x,y> = PolynomialRing(Zmod(n))
#求Groebner基需两个参数，可以将 y 视为一个常数（0）
f1 = 1997-c2
f2 = 1997-c3
for i in range(1,20):
f1 += (x*t)^i
f2 += (x+t)^i
G = [f1,f2]
B = Ideal(G).groebner_basis()
print(B)
'''
[x + 21158731716376226090392498841915660119151249151578293634082749989659307225047065454562556490794720241251831294269248252992828782428316834166828404876181491874871787144664849984606114249820338190252050491223066273953777506705536480844475141933848618113343415375867066617512805575869013694523034573111259114274, 87038069032840052005520908272237788908169043580221040711149494083975743478969]
'''
q=87038069032840052005520908272237788908169043580221040711149494083975743478969
其中Ideal(G) 可以用于创建一个多项式环的理想
一个多项式环的理想：
在代数学中，一个多项式环的理想（ideal）是一个多项式集合，它包含了所有可以被这个集合中的多项式整除的多项式。例如，在一个二元多项式环中，理想可以表示为：
I = <f1, f2, ..., fn>
f1, f2, ..., fn是多项式环中的多项式。这个理想表示了所有可以被f1, f2, ..., fn整除的多项式。
参数选择上如果不定义y，也可以用已知的t：
P.<x,t> = PolynomialRing(Zmod(n))
#求Groebner基需两个参数，可以将 y 视为一个常数（0）
f1 = 1997-c2
f2 = 1997-c3
f3 = t - 2915836867
for i in range(1,20):
f1 += (x*t)^i
f2 += (x+t)^i
G = [f1,f2,f3]
B = Ideal(G).groebner_basis()
print(B)
'''
[x + 21158731716376226090392498841915660119151249151578293634082749989659307225047065454562556490794720241251831294269248252992828782428316834166828404876181491874871787144664849984606114249820338190252050491223066273953777506705536480844475141933848618113343415375867066617512805575869013694523034573111259114274, t + 119156144845956004769507478085325079414190248780654060840257869477965140304727088685316579445017214576182010373548273474121727778923582544853293534996805340795355149795694121455249972628980952137874014208209750135683003125079012121116063371902985706907482988687895813788980275896804461285403779036505981755236, 87038069032840052005520908272237788908169043580221040711149494083975743478969]
'''
q = 87038069032840052005520908272237788908169043580221040711149494083975743478969
同样也能解出结果。
m = -21158731716376226090392498841915660119151249151578293634082749989659307225047065454562556490794720241251831294269248252992828782428316834166828404876181491874871787144664849984606114249820338190252050491223066273953777506705536480844475141933848618113343415375867066617512805575869013694523034573111259114274
#注意负号，当然这不是最终的m
m = m % q
print(m)
#56985796272753226120469211992443340429346162287195965942430959147227534853120
转字节串却不对，m应该是要比q大，可以爆破：
for i in range(10000000):
flag = long_to_bytes(m+i*q)
if b'dasctf{' in flag:
print(flag)
print(i)
break
#b'dasctf{ShangPoXiaPoYaSiLeYiQianDuo}'
#8751845
总结
做出来一道，wp也能看懂很多，收获颇多，挺好的。
参考：
2023DASCTF&0X401 WriteUp (qq.com)
[(25条消息) DASCTF 2023 & 0X401七月暑期挑战赛] crypto_石氏是时试的博客-CSDN博客
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com