DragonKnight CTF
前言
打了一会就去鸣潮战斗爽了，所以没写几题，趁着有时间复现一下。
注：附件在我的github中
题目
Crypto_签到
task
from Crypto.Util.number import *
m = b'flag{********}'
a = getPrime(247)
b = getPrime(247)
n = getPrime(247)
seed = bytes_to_long(m)
class LCG:
def __init__(self, seed, a, b, m):
self.seed = seed
self.a = a
self.b = b
self.m = m
def generate(self):
self.seed = (self.a * self.seed + self.b) % self.m
self.seed = (self.a * self.seed + self.b) % self.m
return self.seed
seed = bytes_to_long(m)
output = LCG(seed,a,b,n)
for i in range(getPrime(16)):
output.generate()
print(output.generate())
print(output.generate())
print(output.generate())
print(output.generate())
print(output.generate())
'''
5944442525761903973219225838876172353829065175803203250803344015146870499
141002272698398325287408425994092371191022957387708398440724215884974524650
42216026849704835847606250691811468183437263898865832489347515649912153042
67696624031762373831757634064133996220332196053248058707361437259689848885
19724224939085795542564952999993739673429585489399516522926780014664745253
'''
思路：额，就是lcg进行了两次，是一个比较基础的题，网上有很多脚本，我前面的一个博客里面也有，直接套就好了。
exp
c = []
import gmpy2
from Crypto.Util.number import GCD, isPrime, long_to_bytes
t=[]
for i in range(1,len(c)):
t.append(c[i]-c[i-1])
m = 0
for i in range(1,len(t)-1):
m = GCD(t[i+1]*t[i-1]-t[i]**2, m)
a = (c[3]-c[2])*gmpy2.invert(c[2]-c[1],m) % m
b = (c[2]-a*c[1]) % m
a_1=gmpy2.invert(a,m)
for i in range(2**16):
c[1] = (c[1]-b) * a_1 % m
flag = long_to_bytes(c[1])
if b'flag{' in flag:
print(flag)
break
#flag{Hello_CTF}
EzDES
task
from Crypto.Cipher import DES from Crypto.Util.Padding import pad from secret import flag,key key = bytes.fromhex(key) des = DES.new(key, DES.MODE_ECB) enc = des.encrypt(pad(flag,64)) print(enc) """ b't\xe4f\x19\xc6\xef\xaaL\xc3R}\x08;K\xc9\x88\xa6|\nF\xc3\x12h\xcd\xd3x\xc3(\x91\x08\x841\xca\x8b\xc1\x94\xb5\x9f[\xcd\xc6\x9f\xf9\xf6\xca\xf5\x1a\xda\x16\xcf\x89\x154\xa1\xfe\xc5\x16\xcf\x89\x154\xa1\xfe\xc5' """
思路：当时比赛时题目框里面的hint是想想des中key的特点，说实话，当时我真的不知道，后面在群里交流的时候才知道是弱密钥。
分别是这八个
0x0101010101010101 0xFEFEFEFEFEFEFEFE 0xE0E0E0E0F1F1F1F1 0x1F1F1F1F0E0E0E0E 0x0000000000000000 0xFFFFFFFFFFFFFFFF 0xE1E1E1E1F0F0F0F0 0x1E1E1E1E0F0F0F0F
随便拿一个当key就出来了。
exp
c=
from Crypto.Cipher import DES
key='0000000000000000'
key = bytes.fromhex(key)
des = DES.new(key, DES.MODE_ECB)
flag=des.decrypt(c)
print(flag)
#DRKCTF{We4k_K3y_1s_V3ry_D4nger0us_In_DES}
MatrixRSA_Revenge
task
from Crypto.Util.number import *
import os
flag = b"DRKCTF{??????????????}" + os.urandom(212)
p = getPrime(120)
q = getPrime(120)
print(f"p = {p}")
print(f"q = {q}")
part = [bytes_to_long(flag[16*i:16*(i+1)]) for i in range(16)]
M = Matrix(Zmod(n),[
[part[4*i+j] for j in range(4)] for i in range(4)
])
e = 65537
C = M ** e
print(f"C = {list(C)}")
"""
p = 724011645798721468405549293573288113
q = 712853480230590736297703668944546433
C = [(354904294318305224658454053059339790915904962123902870614765704810196137, 307912599668649689143528844269686459695648563337814923172488152872006235, 143644686443811064172873392982322248654471792394264352463341325181752577, 22995887787365556743279529792687264972121816670422146768160153217903088), (111349308911096779758451570594323566987628804920420784718347230085486245, 370237591900013263581099395076767089468466012835217658851568690263421449, 305451886364184428434479088589515273362629589399867618474106045683764897, 454103583344277343974714791669312753685583930212748198341578178464249150), (168497521640129742759262423369385500102664740971338844248603058993335309, 228941893018899960301839898935872289351667488000643221589230804176281482, 340080333594340128998141220817079770261711483018587969623825086357581002, 122922413789905368029659916865893297311475500951645918611759627764993518), (10332477229415731242316540110058798318207430965033579181240340751539101, 238172263316130590821973648893483382211906906298557131324791759298887701, 487586702165464601760230182019344052665496627253691596871783460314632260, 12238020921585443139790088280608644406695242899000592355653073240122626)]
"""
思路：这个题目主要考察了一般线性群的阶，这个题就是四阶模p矩阵的阶，然后就是rsa了。
exp
p=
q=
C=[]
from Crypto.Util.number import *
phi1=(p-1)*(p+1)*(p^2+p+1)*p*(p^2+1)
phi2=(q-1)*(q+1)*(q^2+q+1)*q*(q^2+1)
d=inverse(65537,phi1*phi2)
C=Matrix(Zmod(p*q),C)
M=C**d
flag=b""
for i in range(4):
for j in range(4):
flag+=long_to_bytes(int(M[i,j]))
print(flag)
#DRKCTF{a58986e7-33e5-4f65-8c22-b8a5e620752d}
MidRSA
task
from Crypto.Util.number import *
from secret import flag
import random
import gmpy2
def generate_Key1(ebits):
e = [getPrime(ebits) for _ in range(4)]
return e
def encrypt1(message,e):
n = gmpy2.next_prime(bytes_to_long(message) << 300)
m = getPrime(256)
c = [int(pow(m,e[i],n)) for i in range(len(e))]
return c
def generate_Key2(nbits):
p = getPrime(nbits // 2)
q = getPrime(nbits // 2)
n = p*q
e = [random.getrandbits(nbits // 4) for _ in range(3)]
return n,e
def encrypt2(message,e,n):
m = bytes_to_long(message)
c = [int(pow(m,e[i],n)) for i in range(len(e))]
return c
assert flag.startswith(b"DRKCTF{")
flag1 = flag[:len(flag)//2]
flag2 = flag[len(flag)//2:]
ebits = 7
e1 = generate_Key1(ebits)
cipher1 = encrypt1(flag1,e1)
print("e1 =",e1)
print("cipher1 =",cipher1)
nbits = 1024
n,e2 = generate_Key2(nbits)
cipher2 = encrypt2(flag2,e2,n)
print("e2 =",e2)
print("cipher2 =",cipher2)
print("n =",n)
"""
e1 = [109, 71, 109, 73]
cipher1 = [36272047346364825234770733058042613197790911431212158822254782055957208837848605160852567043492625692783344073921185227328379941291979083011033, 13421582077901767047291741873622169312010984740586925881415103229648835151589774736786336965745532072099996467445790339749720696886313635920080, 36272047346364825234770733058042613197790911431212158822254782055957208837848605160852567043492625692783344073921185227328379941291979083011033, 41425183140413487232780768389488969603566343428250573532166425276868000949579663990819005141199597640625439816343697426958648927294289659127871]
e2 = [79572758141493570128961125255246129069540961757778793209698370333142346488381, 80555585862127636800866563977080055603517001358195529410497461746213789997225, 44651921320695090688745333790065512192118202496468714141526113242887125432380]
cipher2 = [58600444300331800249882073146233995912287198739549440714207984476331259754331716531491187240053630185776787152600165426285021284302994699108557023545574315706006132536588848833818758624067461985444940651823107522770906474037882323326792755635934081822967331031854184791299228513024491344725765476710816941057, 16511944800191885973496391252612222059697387587833308714567450121364756390806094606646424594583975159634952911600665271092389815248477961923357683297311169260578508157717777465241680062644118354471550223231057620392252324514411927096940875466794869671163453991620492008856178108060167556176019729800517994337, 80885008609388989196377721090246742575908473911131498982960117640742106565184297197238656375198284856442596226398287448931285735903463892735111244609358611618958293002176923706195402338331128766464276441210238388187625107435781170368017908610916585774514676482124401329575553658828115269495158818527164441546]
n = 93468142044831350317940409833603031534515663349871776634867176846669780024082517910566484997161088199091160371537367121403194814422867749777235397168852158723228851090445429617275680206703935781244466363279841409768649097588586494453125840436600639420286950914680651600232197982546122764845043227394567787283
"""
第一部分
在官方wp中是类似爆破的方法去写的，在这里用格的方法去写，看鸡块师傅的博客可能会更加清楚一点
exp
e= [109, 71, 73]
c= [36272047346364825234770733058042613197790911431212158822254782055957208837848605160852567043492625692783344073921185227328379941291979083011033, 13421582077901767047291741873622169312010984740586925881415103229648835151589774736786336965745532072099996467445790339749720696886313635920080, 41425183140413487232780768389488969603566343428250573532166425276868000949579663990819005141199597640625439816343697426958648927294289659127871]
L = Matrix(ZZ, 3, 4)
for i in range(3):
L[i,0] = e[i]*1000
L[i,i+1] = 1
L = L.LLL()
alist1 = L[0][1:]
k1nl = 1
k1nr = 1
for i in range(3):
if(alist1[i]<0):
k1nr *= c[i]**(-alist1[i])
else:
k1nl *= c[i]**alist1[i]
k1n = k1nl-k1nr
alist2 = L[1][1:]
k2nl = 1
k2nr = 1
for i in range(3):
if(alist2[i]<0):
k2nr *= c[i]**(-alist2[i])
else:
k2nl *= c[i]**alist2[i]
k2n = k2nl-k2nr
n = gcd(k1n,k2n)
for i in range(2,10000):
while(n % i == 0):
n //= i
print(long_to_bytes(n>>300))
#DRKCTF{5d0b96e8-e069-4
第二部分
就是简单的共模了
e = [79572758141493570128961125255246129069540961757778793209698370333142346488381, 80555585862127636800866563977080055603517001358195529410497461746213789997225, 44651921320695090688745333790065512192118202496468714141526113242887125432380] c = [58600444300331800249882073146233995912287198739549440714207984476331259754331716531491187240053630185776787152600165426285021284302994699108557023545574315706006132536588848833818758624067461985444940651823107522770906474037882323326792755635934081822967331031854184791299228513024491344725765476710816941057, 16511944800191885973496391252612222059697387587833308714567450121364756390806094606646424594583975159634952911600665271092389815248477961923357683297311169260578508157717777465241680062644118354471550223231057620392252324514411927096940875466794869671163453991620492008856178108060167556176019729800517994337, 80885008609388989196377721090246742575908473911131498982960117640742106565184297197238656375198284856442596226398287448931285735903463892735111244609358611618958293002176923706195402338331128766464276441210238388187625107435781170368017908610916585774514676482124401329575553658828115269495158818527164441546] n = 93468142044831350317940409833603031534515663349871776634867176846669780024082517910566484997161088199091160371537367121403194814422867749777235397168852158723228851090445429617275680206703935781244466363279841409768649097588586494453125840436600639420286950914680651600232197982546122764845043227394567787283 from Crypto.Util.number import long_to_bytes from gmpy2 import gmpy2 r,s1,s2 = gmpy2.gcdext(e[0], e[1]) m = (pow(c[0],s1,n)*pow(c[1],s2,n)) % n print(long_to_bytes(m)) #378-82e7-120e4b761a0b}
MyEncrypto
task
from Crypto.Util.number import *
from secret import flag
import random
def getMyPrime():
while True:
r = random.getrandbits(64)
_p = r**6 -3*r**5 - r**4 + r**2 - r - 6
_q = r**7 + 2*r**6 + r**5 + 4*r**4 + 7*r**2 + r + 4653
if isPrime(_p) and isPrime(_q):
return _p, _q
def enc(m, n):
return pow(m, 65537, n)
def LCG(s,a,b,n):
return (a*s + b) % n
seed = bytes_to_long(flag)
P = getPrime(512)
a = random.randrange(0,P)
b = random.randrange(0,P)
def Roll():
global seed
seed = LCG(seed,a,b,P)
return seed % 2**16
p, q = getMyPrime()
n = p * q
enc_P = enc(P, n)
print(f"n = {n}")
print(f"enc_P = {enc_P}")
out = []
for _ in range(40):
out.append(Roll())
print(f"a = {a}")
print(f"b = {b}")
print(f"out = {out}")
"""
n = 17959692613208124553115435318871530105762927141420294800783695207170608966804977782615874404539156257549097962410144332053383210075663138848832474791712256427111304125146378883542387121684653496644116081809328796925343393644118376497507
enc_P = 17215745298239635988196009014709535403293865406390546681749129213899045156482782458937447412919331336842808052179915132663427715069134196783415529688715962754860563850858056507148936427379551986735103284388996678146580229028006898491552
a = 2759277675743644814124420138047586760905070650864591936190199977578763421196999718749092450720072564786874114432179104175692800471519816376692104515142375
b = 8111240578821759579875175166986910195923820191652867334412871591814076020421468033017946066268237980082938735686222173713853299600396887041341974719819186
out = [39566, 15295, 19818, 55685, 49100, 6517, 2675, 9567, 37243, 40312, 42906, 35874, 44178, 1256, 40298, 29149, 35721, 19886, 63020, 50116, 6844, 39897, 16134, 50218, 44609, 46188, 52712, 49903, 20933, 5441, 19411, 8330, 6904, 39350, 60853, 43446, 35910, 43728, 61533, 13757]
"""
第一部分
按着题目的节奏走，先求出r，然后就知道了_p和_q，也就找到了P
代码
n = 17959692613208124553115435318871530105762927141420294800783695207170608966804977782615874404539156257549097962410144332053383210075663138848832474791712256427111304125146378883542387121684653496644116081809328796925343393644118376497507
from Crypto.Util.number import *
from sympy import *
r=Symbol('r')
_p = r**6 -3*r**5 - r**4 + r**2 - r - 6
_q = r**7 + 2*r**6 + r**5 + 4*r**4 + 7*r**2 + r + 4653
z=solve([_p*_q-n],[r])
print(z)
#z=1248775963213848425
enc_P = 17215745298239635988196009014709535403293865406390546681749129213899045156482782458937447412919331336842808052179915132663427715069134196783415529688715962754860563850858056507148936427379551986735103284388996678146580229028006898491552
z=1248775963213848425
_p = z**6 -3*z**5 - z**4 + z**2 - z - 6
_q = z**7 + 2*z**6 + z**5 + 4*z**4 + 7*z**2 + z + 4653
d=inverse(65537,(_p-1)*(_q-1))
P=pow(enc_P,d,_p*_q)
print('P=', P)
#P=10679387699123200522776360035184725927822172255453595568464894884736102462568579313264894449779104030120028056158023524486966766295648236135714849745610937
第二部分
一种是论文做法，参考RECONTRUNC.pdf (cmu.edu)，大概意思是根据lcg去写出方程，再利用cvp去恢复lcg
代码，参考了Kicky_Mu师傅的代码
def gen_matrix(a:int, modulus:int, size:int) -> list:
matrix = [[0]*size for _ in range(size)]
for i in range(size):
matrix[0][i] = pow(a, i, modulus)
for i,j in zip(range(1,size), range(1,size)):
if i==j:
matrix[i][j] = modulus
return matrix
def attack(a:int, modulus:int, output_length:int, Ys:list):
I = inverse_mod(2**output_length, modulus)
y = [(el*I) % modulus for el in Ys]
L = IntegerMatrix.from_matrix(gen_matrix(a, modulus, len(Ys)))
reduced = LLL.reduction(L)
Xi_I = CVP.closest_vector(reduced, y, method="fast")
Xi = [xi_i*2**output_length % modulus for xi_i in Xi_I]
return Xi
diffs = []
for i in range(len(out) - 1):
diffs += [out[i + 1] - out[i]]
Xi = attack(a, P, 16, diffs)
seed = ((((Xi[0] - b) * inverse_mod(a - 1, P)) % P) - b) * inverse_mod(a, P) % P
flag = long_to_bytes(seed)
print(flag)
第二种就是直接去手算这个表达式
然后就出来了
代码
P=10679387699123200522776360035184725927822172255453595568464894884736102462568579313264894449779104030120028056158023524486966766295648236135714849745610937
a = 2759277675743644814124420138047586760905070650864591936190199977578763421196999718749092450720072564786874114432179104175692800471519816376692104515142375
b = 8111240578821759579875175166986910195923820191652867334412871591814076020421468033017946066268237980082938735686222173713853299600396887041341974719819186
out = [39566, 15295, 19818, 55685, 49100, 6517, 2675, 9567, 37243, 40312, 42906, 35874, 44178, 1256, 40298, 29149, 35721, 19886, 63020, 50116, 6844, 39897, 16134, 50218, 44609, 46188, 52712, 49903, 20933, 5441, 19411, 8330, 6904, 39350, 60853, 43446, 35910, 43728, 61533, 13757]from Crypto.Util.number import *
import gmpy2
from Crypto.Util.number import *
L = [0] + out
n = len(out)
A = [1]
B = [0]
for i in range(1,n):
A.append(a*A[i-1] % P)
B.append((a*B[i-1] + (a*L[i]+b-L[i+1])*gmpy2.invert(2^16,P))%P)
A = A[1:]
B = B[1:]
Ge = Matrix(ZZ,n+1,n+1)
for i in range(len(A)):
Ge[i,i] = P
Ge[-2,i] = A[i]
Ge[-1,i] = B[i]
Ge[-2,-2] = 1
Ge[-1,-1] = P // 2^16
M = Ge.LLL()[0]
H1 = M[-2]
L1 = out[0]
seed1 = H1 * 2^16 + L1
seed = ((seed1 - b)*gmpy2.invert(a,P))%P
print(long_to_bytes(int(seed)))
#DRKCTF{a57b63a6-ecf5-46d3-a501-2d359a4fd168}