2024-DKCTF-wp-crypto

很有意思。

Crypto_签到

简单lcg，换元解即可

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
'''

只需要注意generate变换了两次，直接贴官方解吧。

import gmpy2

output = [5944442525761903973219225838876172353829065175803203250803344015146870499,
          141002272698398325287408425994092371191022957387708398440724215884974524650,
          42216026849704835847606250691811468183437263898865832489347515649912153042,
          67696624031762373831757634064133996220332196053248058707361437259689848885,
          19724224939085795542564952999993739673429585489399516522926780014664745253]
t = []
for i in range(1, len(output)):
    t.append(output[i] - output[i - 1])

T = []
for i in range(1, len(t) - 1):
    T.append(t[i + 1] * t[i - 1] - t[i] ** 2)

m = []
for i in range(len(T) - 1):
    mm = gmpy2.gcd(T[i], T[i + 1])
    if isPrime(mm):
        m.append(int(mm))
    else:
        for i in range(1, 100):
            if isPrime(mm // i):
                mm = mm // i
                m.append(int(mm))
                break

for i in m:
    a = gmpy2.invert(t[0], i) * t[1] % i
    b = output[1] - a * output[0] % i
    a_ = gmpy2.invert(a, i)

    seed = a_ * (output[0] - b) % i
    for _ in range(2 ** 16):
        seed = a_ * (seed - b) % i
        flag = long_to_bytes(seed)
        if b'flag' in flag:
            print(flag)

Matrix_revenge

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)]
"""

有限域下矩阵是否有类似欧拉定理的性质呢？

论文 https://www.gcsu.edu/sites/files/page-assets/node-808/attachments/pangia.pdf

我们发现当二阶方阵行列式不整除n时，在一般线性群下有阶

$$g=(p^2-1)(p^2-p)(q^2-1)(q^2-q)$$

其更一般的形式为

$$g=\prod_{k=0}^{s-1}(p^s-p^k)\cdot\prod_{k=0}^{s-1}(q^s-q^k).$$

简单推导

第一列向量可以是 $\mathbb{F}_q^n$中的任何非零向量，所以，第一列有$q^{n}-1$种选择。

第二列向量与第一列向量线性无关，第一列向量生成子空间中包含$q$个向量，所以第二列向量有$q^{n}-q$种选择。

同理，第三列向量有$q^{n}-q^{2}$种选择，第四列为$q^{n}-q^{3}$.

推广可得$$g=\prod_{k=0}^{s-1}(p^s-p^k)\cdot\prod_{k=0}^{s-1}(q^s-q^k).$$

这说明g为群中元素的数量，也就是群的阶

由拉格朗日定理我们知道子群的阶一定是群的阶的约数，所以元素阶整除群的阶，所以群中任意元素的g次幂必定为e。

（费马小定理就是拉格朗日定理在模p群下的表现）

所以同理于RSA我们同样可以在阶下找一个e的逆元d，用与RSA一样的方法来做matrixRSA。

其实这题在hnctf出过了，但是我没做，我就奇怪这题算是最复杂的了怎么会有这么多解

（那么当方阵行列式整除n时，是否有类似于amm的算法呢？）

（如果e很大，是否有类似于维纳攻击的方法呢？）

（亟待研究）

from Crypto.Util.number import *
def decimal_to_base(n, base):
    if n == 0:
        return "0"
    digits = []
    while n:
        digits.append(int(n % base))
        n //= base
    digits = digits[::-1]
    return digits

def matrixproduce(A,digits,n):
    lena = len(digits)
    C = identity_matrix(4)
    for i in range(lena):
        B = Matrix(Zmod(n),A)
        m = lena-i
        for j in range(m-1):
            B = B**n
        B = B**digits[i]
        C = C*B
    return C
    
p = 724011645798721468405549293573288113   
q = 712853480230590736297703668944546433
n = p*q
g = (p**4-p**3)*(p**4-p**2)*(p**4-p**1)*(p**4-p**0)*(q**4-q**3)*(q**4-q**2)*(q**4-q**1)*(q**4-q**0)
e = 65537
C = matrix(Zmod(n),[(354904294318305224658454053059339790915904962123902870614765704810196137, 307912599668649689143528844269686459695648563337814923172488152872006235, 143644686443811064172873392982322248654471792394264352463341325181752577, 22995887787365556743279529792687264972121816670422146768160153217903088), (111349308911096779758451570594323566987628804920420784718347230085486245, 370237591900013263581099395076767089468466012835217658851568690263421449, 305451886364184428434479088589515273362629589399867618474106045683764897, 454103583344277343974714791669312753685583930212748198341578178464249150), (168497521640129742759262423369385500102664740971338844248603058993335309, 228941893018899960301839898935872289351667488000643221589230804176281482, 340080333594340128998141220817079770261711483018587969623825086357581002, 122922413789905368029659916865893297311475500951645918611759627764993518), (10332477229415731242316540110058798318207430965033579181240340751539101, 238172263316130590821973648893483382211906906298557131324791759298887701, 487586702165464601760230182019344052665496627253691596871783460314632260, 12238020921585443139790088280608644406695242899000592355653073240122626)])
d = inverse(e,g)
d = 15806680399060040009171608494332099667965006023942006329657487966102814020501150626456330792092735181642854019923412956550558461511110849070057544453882301197493754015490022851296284106084292204295419261456548149423971590556163580977467946513801615095458650037385920557261615384147910422121891906859461789777038575978079268706617458449842440351702697878312214115895493219789213974070133199990032711111946768810238677188046605517065798529773350946255574484638407509093796816629417602243665229729108700158716856339436735611298303663582457643176512488963323309766763370951413816945684392634117393908290319600488918482609717880323953515055614313785562108982443259294382253163129242583007424347870378389813783669881928124540182530004668864441308729592168389209532725647271795361596209794862867559523707635949566323319684562218806662628181503607385115688062392613583947989473289809411708203763210363893203891591740032480349022914040165941787704028766910936271163414231295023222145669843287241929127170124310248619150568501281544689249544922319657010702729267333417500949022807756995680723292213596492497010974558361252426023956242905073293531404889423873

assert(C.determinant()%n!=0)
X = ((matrixproduce(C,decimal_to_base(d,n),n)))
print(long_to_bytes(int(X[0][0]))+long_to_bytes(int(X[0][1]))+long_to_bytes(int(X[0][2])))

EzDES

懒得喷 做得最久的一题

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'
"""

from Crypto.Cipher import DES
from Crypto.Util.Padding import pad
keys = [
'0101010101010101',
'FEFEFEFEFEFEFEFE',
'E0E0E0E0F1F1F1F1',
'1F1F1F1F0E0E0E0E',
'0000000000000000',
'FFFFFFFFFFFFFFFF',
'E1E1E1E1F0F0F0F0',
'1E1E1E1E0F0F0F0F']
from Crypto.Cipher import DES
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'
for key in keys:
    key = bytes.fromhex(key)
    cipher = DES.new(key, DES.MODE_ECB)
    print(cipher.encrypt(enc))

MidRSA

非常简单的推导，新生赛题吧

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
"""

我们知道$c_i\equiv m^{e_i}\quad\mathrm{mod~}n$

取两个不同的$c_i^{e_j}\equiv c_j^{e_i}\mod n$

$c_i^{e_j}-c_j^{e_i}=kn$

所以取两个ij gcd完就是n

得到n之后右移300位就是flag

根据裴蜀定理，一定存在$xe_1+ye_2=gcd(e_1,e_2)$

所以$$c_{1}^{x}\times c_{2}^{y}\equiv m^{e_{1}x+e_{2}y}\equiv m^{gcd(e_1,e_2)}\mod n$$

但是gcd(e1,e2) != 1

所以理论上还要再来一次，但是不知道为什么这里直接通了

from Crypto.Cipher import DES
from Crypto.Util.Padding import pad
from Crypto.Util.number import *
e1 = [109, 71, 109, 73]
cipher1 = [36272047346364825234770733058042613197790911431212158822254782055957208837848605160852567043492625692783344073921185227328379941291979083011033, 13421582077901767047291741873622169312010984740586925881415103229648835151589774736786336965745532072099996467445790339749720696886313635920080, 36272047346364825234770733058042613197790911431212158822254782055957208837848605160852567043492625692783344073921185227328379941291979083011033, 41425183140413487232780768389488969603566343428250573532166425276868000949579663990819005141199597640625439816343697426958648927294289659127871]
e2 = [79572758141493570128961125255246129069540961757778793209698370333142346488381, 80555585862127636800866563977080055603517001358195529410497461746213789997225, 44651921320695090688745333790065512192118202496468714141526113242887125432380]
cipher2 = [58600444300331800249882073146233995912287198739549440714207984476331259754331716531491187240053630185776787152600165426285021284302994699108557023545574315706006132536588848833818758624067461985444940651823107522770906474037882323326792755635934081822967331031854184791299228513024491344725765476710816941057, 16511944800191885973496391252612222059697387587833308714567450121364756390806094606646424594583975159634952911600665271092389815248477961923357683297311169260578508157717777465241680062644118354471550223231057620392252324514411927096940875466794869671163453991620492008856178108060167556176019729800517994337, 80885008609388989196377721090246742575908473911131498982960117640742106565184297197238656375198284856442596226398287448931285735903463892735111244609358611618958293002176923706195402338331128766464276441210238388187625107435781170368017908610916585774514676482124401329575553658828115269495158818527164441546]
n = 93468142044831350317940409833603031534515663349871776634867176846669780024082517910566484997161088199091160371537367121403194814422867749777235397168852158723228851090445429617275680206703935781244466363279841409768649097588586494453125840436600639420286950914680651600232197982546122764845043227394567787283

import math
from gmpy2 import *
n1 = math.gcd((cipher1[3]**71-cipher1[1]**73),cipher1[0]**71-cipher1[1]**109)
print(n1>>300)
print(long_to_bytes(n1>>300))
#b'DRKCTF{5d0b96e8-e069-4'
def rsa_gong_N_def(e1,e2,c1,c2,n):
    e1, e2, c1, c2, n=int(e1),int(e2),int(c1),int(c2),int(n)
    s = gmpy2.gcdext(e1, e2)
    s1 = s[1]
    s2 = s[2]
    m = (pow(c1,s1,n) * pow(c2 ,s2 ,n)) % n
    return int(m)

x = (math.gcd(rsa_gong_N_def(e2[0],e2[1],cipher2[0],cipher2[1],n),rsa_gong_N_def(e2[1],e2[2],cipher2[1],cipher2[2],n)))
print(long_to_bytes(rsa_gong_N_def(e2[0],e2[1],cipher2[0],cipher2[1],n)))
#b'378-82e7-120e4b761a0b}'

Myencrypt

简单格密码 hgameweek4的水平

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]
"""

我们发现n可以直接写成r的式子

$$n=r^{13}-r^{12}-6r^{11}-r^{10}-12r^9+4r^8-27r^7+4634r^6-13970r^5-4670r^4-6r^3+4610r^2-4659r-27918$$

直接用sagemath的解方程得r

得P

然后这个格

已知低位

$$H_{n+1}*2^{16}+L_{n+1}\equiv a(H_{n}*2^{16}+L_{n})+b\mod p$$

$$H = 2^{16}$$

$$H_{n+1}*H+L_{n+1}\equiv a(H_{n}*H+L_{n})+b\mod p$$

$$H_{n+1}\equiv aH_n+(aL_n+b-L_{n+1})*H^{-1}\mod p$$

$$H_{2}\equiv aH_1+(aL_1+b-L_2)*H^{-1}\mod p$$

$$H_{3}\equiv aH_2+(aL_2+b-L_3)*H^{-1}\mod p$$

可以化简

$$A_{n} = a^{n}$$

$$B_{n} = a*B_{n-1}+(aL_{n-1}+b-L_n)*H^{-1}$$

直接构造 （其实跟那个HNP完全是一个思路 只是多了一个高位而已 由此看来 DKRCTF<Hgameweek3（确信
$$
\begin{pmatrix}
P &0 &\ldots &0 &0 &0\\
0 &P &\ldots &0 &0 &0\\
\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\
0&0&\ldots&P&0&0\\
A_1&A_2&\ldots&A_n&1&0\\
B_1&B_2&\ldots&B_n&0&\frac{P}{2^{n}}\\
\end{pmatrix}
$$
也就轻松拿下H1

也就拿下seed了

from Crypto.Util.number import *
PR.<r> = PolynomialRing(RealField(1000))
n = 17959692613208124553115435318871530105762927141420294800783695207170608966804977782615874404539156257549097962410144332053383210075663138848832474791712256427111304125146378883542387121684653496644116081809328796925343393644118376497507
f = (r**6 -3*r**5 - r**4 + r**2 - r - 6)*(r**7 + 2*r**6 + r**5 + 4*r**4 + 7*r**2 + r + 4653)-n
r = (int(f.roots()[0][0]))
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
enc_P = 17215745298239635988196009014709535403293865406390546681749129213899045156482782458937447412919331336842808052179915132663427715069134196783415529688715962754860563850858056507148936427379551986735103284388996678146580229028006898491552
phi = (p-1)*(q-1)
e = 65537
d = inverse(e,phi)
P = pow(enc_P,d,n)
a = 2759277675743644814124420138047586760905070650864591936190199977578763421196999718749092450720072564786874114432179104175692800471519816376692104515142375
b = 8111240578821759579875175166986910195923820191652867334412871591814076020421468033017946066268237980082938735686222173713853299600396887041341974719819186
out = [0,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]
H = 2**16
A = [1]
B = [0]
Hfu = inverse(H,P)
for i in range(1, len(out)-1):
    A.append(pow(a*A[i-1] ,1,P))
    B.append(pow((a*B[i-1]+Hfu*(a*out[i]+b-out[i+1])),1 , P))
print(A[1:])
print(B[1:])
M = matrix(ZZ,41,41)
for i in range(39):
    M[i, i] = P
    M[39, i] = A[i]
    M[40, i] = B[i]
    M[i, 39] = M[i, 40] = 0
M[39, 39] =  1
M[40, 40] = 2^500
M[39, 40]= 0
vl = M.LLL()
for l in vl:
        if l[-1] == 2^500:
               vl = l
print(vl)
h1 = vl[-2]
l1 = out[1]
s1 = h1*2**16+l1
seed = ((s1 - b)*inverse(a,P))%P
print(long_to_bytes(int(seed)))