↓Skip to main content

d3ctf2022🧀🧀🧀

·488 words·3 mins Draft
Table of Contents

花了一下午看题,解数较多的三个题难度比较签到

尽一点绵薄之力

d3factor #

查论文搞出一个有限域多项式

构造好a后用sage自带的smallroot就能求出来，其中出现了一个灵异事件，自己的电脑求各种LLL会直接 暴毙，用官方在线sage搞到了数据

对结果处理，得到p的六次方

#! /usr/bin/sage
from hashlib import md5
import gmpy2 
from sage.all import *
from sage.groups.generic import bsgs
from Crypto.Util.number import *

# N = 1476751427633071977599571983301151063258376731102955975364111147037204614220376883752032253407881568290520059515340434632858734689439268479399482315506043425541162646523388437842149125178447800616137044219916586942207838674001004007237861470176454543718752182312318068466051713087927370670177514666860822341380494154077020472814706123209865769048722380888175401791873273850281384147394075054950169002165357490796510950852631287689747360436384163758289159710264469722036320819123313773301072777844457895388797742631541101152819089150281489897683508400098693808473542212963868834485233858128220055727804326451310080791
# e1 = 425735006018518321920113858371691046233291394270779139216531379266829453665704656868245884309574741300746121946724344532456337490492263690989727904837374279175606623404025598533405400677329916633307585813849635071097268989906426771864410852556381279117588496262787146588414873723983855041415476840445850171457530977221981125006107741100779529209163446405585696682186452013669643507275620439492021019544922913941472624874102604249376990616323884331293660116156782891935217575308895791623826306100692059131945495084654854521834016181452508329430102813663713333608459898915361745215871305547069325129687311358338082029
# e2 = 1004512650658647383814190582513307789549094672255033373245432814519573537648997991452158231923692387604945039180687417026069655569594454408690445879849410118502279459189421806132654131287284719070037134752526923855821229397612868419416851456578505341237256609343187666849045678291935806441844686439591365338539029504178066823886051731466788474438373839803448380498800384597878814991008672054436093542513518012957106825842251155935855375353004898840663429274565622024673235081082222394015174831078190299524112112571718817712276118850981261489528540025810396786605197437842655180663611669918785635193552649262904644919
# a = (e2-e1)*inverse_mod(e1*e2,N)
# PR.<x> = PolynomialRing(Zmod(N))
# f=x-a
# x0 = f.small_roots(X=2^1000, beta=0.4)

# x0 = 1476751427633071977599571983301151063258376731102955975364111147037204614220376883752032253407881568290520059515340434632858734689439268479399482315506043425541162646523388437842149125178447800616137044219916586942207838674001004007237861470176454543718752182312318068466051713087927370670177514666860822341380494148050832401609562069841131611670608508889564903156115171543356434938854665775998209034026454583918190592316542096833683522232732078346945883792128428219017665904611238598515356080299964332522186719141840239751107772675611703424971072329706974374008179321418610378586680426547416872428073384036373775613
# print(x0)
# ans = f(x0)
# p = gcd(ans,N)
# print(p)
# print(isPrime(p))
# p = 302041005420039804788837973713898327221537364540217123524277085489425015387406302827931741511110799839253993542589980437030294737549654496720894473925249726898113670841165053274897225331487693822448903890664321018179858685020471572484115220669783927170647297629616743131628132318835058700355916820746650505209238111625956099990183829787016000154371928717007922683297772484179270642107118214144502646097942422343431687478702790785714060858198343943546186776012201
# print(gmpy2.iroot(p,int(6)))

p = 81911394167511996830305370213894554209992159667974516868378702592733037962549
q = N//(p**7)
q = 59689394622751323780317475130818337618980301243859922297121750335804594909859
c = 2420624631315473673388732074340410215657378096737020976722603529598864338532404224879219059105950005655100728361198499550862405660043591919681568611707967
e = 0x10001
N = p*q
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,N)
msg = long_to_bytes(m)
print(msg)
flag = 'd3ctf{'+md5(msg).hexdigest()+'}'
print(flag)

flag d3ctf{42f79e777e622aef5344b04ad6233130}

d3bug #

线性代数问题，把$r0 …. r63$留在等号左边，已知量r64~r98移到等号右边

得到关于r0~r63的70组方程

构造矩阵发现矩阵的秩刚好为64，求最简矩阵去掉线性相关的向刚好得到r0~r63的值

求等号左边的代码：

mask = '1010010000001000000010001001010010100100000010000000100010010100'
mask = [int(i) for i in mask ]
r1 = '01111101111010111000010010111001101'
r2 = '00100110001000110001101010101001001'
r1 = [int(i) for i in r1]
r2 = [int(i) for i in r2]
x1 = [0 for i in range(35)]
for i in range(35):
    A = r1[i]
    B = 0
    # print('i',i)
    for j in range(1,i+1):
        B^=(r1[i-j]&mask[64-j])
    x = A^B
    x1[i]=x

# ============================================
print(r2)
x2 = [0 for i in range(35)]
for i in range(35):
    A = r2[i]
    B = 0
    print('i',i)
    for j in range(1,i+1):
        print(i-j)
        B^=r2[i-j]
    # print(A,B)
    x = A ^ B
    # print('x',x)
    # input()
    x2[i]=x

print('x1=',x1)
print('x2=',x2)

# x1= [1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0]
# x2= [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

构造矩阵以及求最简矩阵的代码

#! /usr/bin/sage
from sage.all import *
from sage.groups.generic import bsgs
from Crypto.Util.number import *

mask = '1010010000001000000010001001010010100100000010000000100010010100'
mask = [int(i) for i in mask ]
# mask = [i for i in range(len( mask) )]
# M=0
# for i in mask:
#     M^=i
    
# print(M) m=0

x1= [0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1]
x2= [0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0]
r1=x1
r2=x2
print(len(r1),len(r2))

matrix1 = [[0 for i in range(65)] for i in range(70)]
for i in range(35):
    for j in range(i,64):
        matrix1[i][j]=mask[j-i]
    matrix1[i][64]=r1[i]
    
for i in range(35,70):
    for j in range(i-35,64):
        matrix1[i][j]=1
    matrix1[i][64]=r2[i-35]
# print(matrix1)
M = matrix1
F = GF(2)
M1 = Matrix(F,M)

M1 = M1.rref()
print(M1.rank())
M2 = M1[:64,:-1]
ans =  M1[:64,64:]
print(M2)
print(ans)
flag=''
for i in ans:
    print(i[0])
    flag += str(i[0])
print(flag)

l2b得到flag

flag D3CTF{LF5Rsuk!}