SUSCTF-Crypto方向所有赛题

Special Curve3

思路

看到SpecialCurve3这个名字，不禁想起西湖论剑的SpecialCurve2，想这两个应该有什么关系，于是打开春乎找到他当时赛后写的复盘，了解到有.log这个能算自己定义的群的离散对数的逆天函数。审查题目，自己定义了一个曲线和它的群操作，一开始以为能用edwards曲线变换和Montgomery形式的变换映射到熟悉的椭圆曲线，然而失败了，报了些奇奇怪怪的错误，遂Google，以“圆锥曲线加密”为关键字找到了这篇文章，按照文章所述以及题目的信息，知道前两个curve是论文所提到的两种不安全的曲线，按照文章依葫芦画瓢，再借助春乎的.log函数，整出前两关，得到e1,e2。第三关选择了“安全”的参数，即勒让德符号为-1，怀疑p有问题（不然真就无解了），尝试分解p-1,p+1,p^ 2+1,p ^ 2-1等，发现p+1光滑，于是猜测群的阶为p+1，仿照安全客这篇讲Pohlig Hellman的文章，对p+1的因子求离散对数再CRT合并得到e3，由于勒让德符号为-1，不能构造映射用.log，因此爆破每一个因子求离散对数，获得flag。

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
import random
import hashlib
from Crypto.Util.number import *
class SpecialCurve:
    def __init__(self,p,a,b):
        self.p=p
        self.a=a
        self.b=b

    def __str__(self):
        return f'SpecialCurve({self.p},{self.a},{self.b})'

    def add(self,P1,P2):
        x1,y1=P1
        x2,y2=P2
        if x1==0:
            return P2
        elif x2==0:
            return P1
        elif x1==x2 and (y1+y2)%self.p==0:
            return (0,0)
        if P1==P2:
            t=(2*self.a*x1-self.b)*inverse_mod(2*y1,self.p)%self.p
        else:
            t=(y2-y1)*inverse_mod(x2-x1,self.p)%self.p
        x3=self.b*inverse_mod(self.a-t**2,self.p)%self.p
        y3=x3*t%self.p
        return (x3,y3)

    def mul(self,P,k):
        assert k>=0
        Q=(0,0)
        while k>0:
            if k%2:
                k-=1
                Q=self.add(P,Q)
            else:
                k//=2
                P=self.add(P,P)
        return Q
def Legendre(a,p):       #勒让德符号计算
    return (pow((a%p+p)%p,(p-1)//2,p))%p

def get_nonre(p):
    a=random.randint(1,p)
    while Legendre(a,p)==1:
        a=random.randint(1,p)
    return a

def get_ts(p):
    p=p-1
    count=0
    while p%2==0:
        count+=1
        p=p//2
    return count,p


def root_2(a,p):
    t,s=get_ts(p)
    ta=pow(get_nonre(p),s,p)
    tb=pow(a,s,p)
    h=1
    for i in range(1,t):
        d=pow(tb,2**t-1-i,p)
        if d==1:
            k=0
        else:
            k=1
        tb=(tb*pow(ta,2*k,p))%p
        h=(h*pow(ta,k,p))%p
        ta=pow(ta,2,p)
    print(h*pow(a,(s+1)//2,p)%p)
    return h*pow(a,(s+1)//2,p)%p


def trans1(a,p):
    return lambda t: (t+root_2(a,p))/(t-root_2(a,p))

def trans2(a,p):
    return lambda t: 1/t

#a为系数列表,b为模数列表
def myCRT(a,b):
    pro=1
    res=0
    for i in b:
        pro*=i
    for i in range(len(b)):
        r=pro//b[i]
        res+=a[i]*r*inverse_mod(r,b[i])
    return res%pro

curve1=SpecialCurve(233083587295210134948821000868826832947,73126617271517175643081276880688551524,88798574825442191055315385745016140538)
G1=(183831340067417420551177442269962013567, 99817328357051895244693615825466756115)
Q1=(166671516040968894138381957537903638362, 111895361471674668502480740000666908829)
curve2=SpecialCurve(191068609532021291665270648892101370598912795286064024735411416824693692132923,0,58972296113624136043935650439499285317465012097982529049067402580914449774185)
G2=(91006613905368145804676933482275735904909223655198185414549961004950981863863, 96989919722797171541882834089135074413922451043302800296198062675754293402989)
Q2=(13504049588679281286169164714588439287464466303764421302084687307396426249546, 110661224324697604640962229701359894201176516005657224773855350780007949687952)
curve3=SpecialCurve(52373730653143623993722188411805072409768054271090317191163373082830382186155222057388907031638565243831629283127812681929449631957644692314271061305360051,28655236915186704327844312279364325861102737672471191366040478446302230316126579253163690638394777612892597409996413924040027276002261574013341150279408716,42416029226399083779760024372262489355327595236815424404537477696856946194575702884812426801334149232783155054432357826688204061261064100317825443760789993)
G3=(15928930551986151950313548861530582114536854007449249930339281771205424453985946290830967245733880747219865184207937142979512907006835750179101295088805979, 29726385672383966862722624018664799344530038744596171136235079529609085682764414035677068447708040589338778102975312549905710028842378574272316925268724240)
Q3=(38121552296651560305666865284721153617113944344833289618523344614838728589487183141203437711082603199613749216407692351802119887009907921660398772094998382, 26933444836972639216676645467487306576059428042654421228626400416790420281717654664520663525738892984862698457685902674487454159311739553538883303065780163)
P1,P2,P3=curve1.p,curve2.p,curve3.p
F1,F2,F3=GF(P1),GF(P2),GF(P3)

'''
t_G=F1(G1[1])/F1(G1[0])       #算t
t_Q=F1(Q1[1])/F1(Q1[0])       #算t
reflectionG=trans1(curve1.a,P1)(t_G)
reflectionQ=trans1(curve1.a,P1)(t_Q)
e1=reflectionQ.log(reflectionG)
assert curve1.mul(G1,e1)==Q1
print(e1)
'''

e1=184572164865068633286768057743716588370

'''
t_G=F2(G2[1])/F2(G2[0])           #算t
t_Q=F2(Q2[1])/F2(Q2[0])           #算t
reflectionG=trans2(curve2.a,P2)(t_G)
reflectionQ=trans2(curve2.a,P2)(t_Q)
e2=ZZ(reflectionQ/reflectionG)
assert curve2.mul(G2,e2)==Q2
print(e2)
'''

e2=131789829046710687154053378348742202935151384644040019239219239301007568911745

#猜测群的阶，尝试分解p-1和p+1,以及p^2-1,p^2+1,p^3-1等，发现p+1光滑（实际上p^2-1和p^3-1都不需要，因为是因子,p^2+1和p^3-1搞不出来）,于是猜测群的阶为p+1
INF=(0,0)   #无穷远点
Factor=[4,
 2663,
 5039,
 14759,
 18803,
 21803,
 22271,
 22307,
 23879,
 26699,
 35923,
 42727,
 48989,
 52697,
 57773,
 58129,
 60527,
 66877,
 69739,
 74363,
 75869,
 79579,
 80489,
 81043,
 81049,
 82531,
 84509,
 85009,
 91571,
 96739,
 98711,
 102481,
 103357,
 103981]
dlogs=[]
for i in Factor:
    Now=INF
    tmpG=curve3.mul(G3,ZZ((P3+1))//ZZ(i))
    tmpQ=curve3.mul(Q3,ZZ((P3+1))//ZZ(i))
    for dlog in range(i):
        Now=curve3.add(Now,tmpG)
        if Now==tmpQ:
            dlogs.append(dlog)
            break

e3=myCRT(dlogs,Factor)+1 #这里我们crt求出来的并非就是e3,还需要加上1
print(e3)
e3=23331486889781766099145299968747599730779731613118514070077298627895623872695507249173953050022392729611030101946661150932813447054695843306184318795467216
assert(curve3.mul(G3,e3)==Q3)
enc=4161358072766336252252471282975567407131586510079023869994510082082055094259455767245295677764252219353961906640516887754903722158044643700643524839069337
flag=enc^^bytes_to_long(hashlib.sha512(b'%d-%d-%d'%(e1,e2,e3)).digest())
print(long_to_bytes(flag))
#b'SUSCTF{Y0u_kNow_c0n1c_curv3_anD_discrete_l0g_vEry_we11~}'

large case

思路

给了p,q,r，n为三者的乘积，e就是phi的因子，并且是p-1,q-1,r-1中三个素因子的乘积，由于e，phi不互素，我们考虑使用AMM开根算法。尝试分解p-1,q-1,r-1，p-1能完全分解，q-1用yafu分解1300s也能搞出来，r-1搞了两个小时没出来（事实上证明没啥用）。由于AMM只能解决小指数的情形，若指数很大，这题就基本上没戏了（不然可以发paper了），所以我们猜想，e取的是p-1,q-1,r-1的小因子。但是r-1最小的因子都有上百万。因此我们利用条件将pad(m)的3096位归约到1024位到2048位之间，而p,q也是1024位，这时m就会在pq的域下了，所以我们丢掉r-1的因子，直接用p-1,q-1的小因子去搞（太小的如2，3，7还是不大可能），r-1也取个小因子（后面在跑的时候思考既然我们都已经不考虑r-1的因子了，那这个因子大不大其实跟我们没什么关系，当时想如果这个跑不出就换大因子搞，还好出了），开根之后得到flag。

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#开r次方根
import random
import sympy
import math
from gmpy2 import *
from Crypto.Util.number import *

def Legendre(a,p):       #勒让德符号计算
    return (pow((a%p+p)%p,(p-1)//2,p))%p

def ex_Legendre(a,p,r):     #判断是否为r次剩余
    return (pow(a,(p-1)//r,p)==1)

def get_nonre(p):
    a=random.randint(1,p)
    while Legendre(a,p)==1:
        a=random.randint(1,p)
    return a

def get_ex_nonre(p,r):
    a=random.randint(1,p)
    while ex_Legendre(a,p,r)==1:
        a=random.randint(1,p)
    return a

def get_ts(p):
    p=p-1
    count=0
    while p%2==0:
        count+=1
        p=p//2
    return count,p

def get_ex_ts(p,r):
    p=p-1
    count=0
    while p%r==0:
        count+=1
        p=p//r
    return count,p

def get_alpha(r,s):
    k=1
    while (s*k+1)%r!=0:
        k+=1
    alpha=(s*k+1)//r
    return alpha

def amm2(a,p):
    t,s=get_ts(p)
    ta=pow(get_nonre(p),s,p)
    tb=pow(a,s,p)
    h=1
    for i in range(1,t):
        d=pow(tb,2**t-1-i,p)
        if d==1:
            k=0
        else:
            k=1
        tb=(tb*pow(ta,2*k,p))%p
        h=(h*pow(ta,k,p))%p
        ta=pow(ta,2,p)
    return h*pow(a,(s+1)//2,p)%p

def ammr(a,p,r):           #AMM获得一个根
    t,s=get_ex_ts(p,r)
    alpha=get_alpha(r,s)
    rho=get_ex_nonre(p,r)
    ta=pow(rho,(s*r**(t-1))%(p-1),p)
    tb=pow(a,r*alpha-1,p)
    tc=pow(rho,s,p)
    h=1
    if t==0:
        return pow(a,alpha*h,p),ta,p
    for i in range(1,t-1):
        d=pow(tb,r**(t-1-i),p)
        if d==1:
            j=0
        else:
            print("dddd")
            j=-sympy.discrete_log(p,d,ta)
            #j=-math.log(d,a)
            print(j)
        b=b*pow(pow(tc,j,p),a)%p
        h=h*pow(c,j,p)%p
        c=pow(c,r,p)
    return pow(a,alpha*h,p),ta,p

def extend(root,ta,p,r):
    res=set()
    for i in range(r):
        tmp=root*pow(ta,i,p)%p
        res.add(tmp)
    return list(res)

#a为系数列表,b为模数列表
def CRT(a,b):
    pro=1
    res=0
    for i in b:
        pro*=i
    for i in range(len(b)):
        R=pro//b[i]
        res+=a[i]*R*invert(R,b[i])
    return res%pro

def solve_n(a,p,q,r):        #解当n=pq时的情形
    res=[]
    RES1=ammr(a%p,p,r)
    RES2=ammr(a%q,q,r)
    L1=extend(RES1[0],RES1[1],RES1[2],r)
    L2=extend(RES2[0],RES2[1],RES2[2],r)
    for i in L1:
        for j in L2:
            temp=CRT([i,j],[p,q])
            res.append(temp)
    return res

p=127846753573603084140032502367311687577517286192893830888210505400863747960458410091624928485398237221748639465569360357083610343901195273740653100259873512668015324620239720302434418836556626441491996755736644886234427063508445212117628827393696641594389475794455769831224080974098671804484986257952189021223
q=145855456487495382044171198958191111759614682359121667762539436558951453420409098978730659224765186993202647878416602503196995715156477020462357271957894750950465766809623184979464111968346235929375202282811814079958258215558862385475337911665725569669510022344713444067774094112542265293776098223712339100693
r=165967627827619421909025667485886197280531070386062799707570138462960892786375448755168117226002965841166040777799690060003514218907279202146293715568618421507166624010447447835500614000601643150187327886055136468260391127675012777934049855029499330117864969171026445847229725440665179150874362143944727374907
a=2832775557487418816663494645849097066925967799754895979829784499040437385450603537732862576495758207240632734290947928291961063611897822688909447511260639429367768479378599532712621774918733304857247099714044615691877995534173849302353620399896455615474093581673774297730056975663792651743809514320379189748228186812362112753688073161375690508818356712739795492736743994105438575736577194329751372142329306630950863097761601196849158280502041616545429586870751042908365507050717385205371671658706357669408813112610215766159761927196639404951251535622349916877296956767883165696947955379829079278948514755758174884809479690995427980775293393456403529481055942899970158049070109142310832516606657100119207595631431023336544432679282722485978175459551109374822024850128128796213791820270973849303929674648894135672365776376696816104314090776423931007123128977218361110636927878232444348690591774581974226318856099862175526133892

PP=[ 7, 757, 1709, 85015583, 339028665499, 149105250954771885483776047, 1642463892686572578602085475101104723805585678675707586553009837707279291648160744722745420570786735582631019452016654157586623543454908938807521637550223579103317696104438456966780396624343550451096013730928292041667133825444056448136643704677066463120079]
QQ=[ 3, 66553, 84405986771, 81768440203, 38037107558208320033, 16137718604846030589135490851713, 14369576056311038198362075935199486201201115381094289671031774994452214307042971166730146897009438957078052300683916910041250723573953110349566216311685009675744215421971185909678546052934704709232060199286321405045769976194110037]
RR=[5156273,10012111,11607389,68872137169799749,9691125310820433463]
P=757
Q=66553
R=5156273
e=P*Q*R
a=a*invert(pow(2**1024,e,p*q*r),p*q*r)%(p*q*r)
print(a)
A1=pow(a,invert((Q*R)%(p-1),p-1),p)
A2=pow(a,invert((P*R)%(q-1),q-1),q)
RES1=ammr(A1%p,p,P)
RES2=ammr(A2%q,q,Q)
print(pow(RES1[0],P,p)==A1)
print(pow(RES2[0],Q,q)==A2)
print(RES1[0])
print(RES2[0])
tt1=7700134146413203335573871689895239649523826964798753951118907764374468701380230646668699151638088864326937164914647973580340523759806441772313411463030830977275574217572801250453207088891613732432934275970526137904863662059764692420784462894335565049743175545091375493307863291499149512027751479854369076486
tt2=97127769154391954478158333319253125848146734781401341100552749456749909131766132177841450244285412055004811036427963683364198744452408709852717758239537039794748062597759047284626577221916908271740791136898405499359224473811595744452970474069305546442180105085850003353278267681999778967972663810137184306114

L1=extend(RES1[0],RES1[1],RES1[2],P)
L2=extend(RES2[0],RES2[1],RES2[2],Q)
print(tt1 in L1)
print(tt2 in L2)
#逆序枚举更快
for i in L1[::-1]:     
    for j in L2:
        temp=CRT([i,j],[p,q])
        m=long_to_bytes(temp)
        if b'SUSCTF' in m:
            print(m)
            break
#b'For RSA, the wrong key generation method can also reveal information. You recover my secret message, and here is the flag:SUSCTF{N0n_c0prime_RSA_c1pher_cAn_a1s0_recover_me33age!!!}\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'

Inverse Problem

思路

刚开始看不知道是什么东西，后面突然想到有个东西叫LWE，learning with errors，好像跟误差这东西有点关系，然后就去lazzaro佬的博客偷学了一波，la佬博客。但是一般我们讨论的LWE，都是整数，在整数格子上，但是这里并不是，产生了小数（浮点数的累计误差让直接乘逆变得不太可行），我们自然就想到了将小数扩大为整数，就是在$Ax=b$两边同时扩大一个倍数，使其变为整数（感觉扩大为近似整数也可），然后由于浮点数运算的误差，这里就会存在一个误差向量s，精确表示为$Ax=b+s$，也就是$Ax-b=s$，这里利用矩阵性质，两边转置将形式化为我们熟悉的：$x^TA^T-b^T=s^T$,s为小向量，扩大一维，构造格子调整参数用LLL打再乘逆，以最后一个元素为-1为判定依据，即可得flag。

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#sage
import numpy as np
b=[365.70605003390546, 383.22392124225024, 400.640087842069, 417.84199007926037, 434.72288587570716, 451.1847676148434, 467.1407458110251, 482.51679479180746, 497.252809093278, 511.30296958172937, 524.6354631948004, 537.2316391653928, 549.0847173300799, 560.1981891814168, 570.5840667157972, 580.2611340293561, 589.2533389518161, 597.5884263745527, 605.2968650055386, 612.4110630374365, 618.9648165161183, 624.9928981118596, 630.5306816020914, 635.6137112146116, 640.2771610768812, 644.5551788138647, 648.4801562386791, 652.0820067831412, 655.3875449515116, 658.4200543535777, 661.199100692684, 663.740602612215, 666.0571276935108, 668.1583443270599, 670.0515409542965, 671.7421256877906, 673.2340393774058, 674.5300469406175, 675.6319058650935, 676.5404381911505, 677.2555468921495, 677.7762178159265, 678.10053722622, 678.2257385537031, 678.1482768722584, 677.8639205835502, 677.3678481496929, 676.6547414782242, 675.7188729438, 674.5541865153842, 673.1543734407334, 671.5129401333222, 669.6232624726493, 667.4786187460367, 665.072193640194, 662.3970470419692, 659.4460419709976, 656.211724164364, 652.6861416758932, 648.860588380176, 644.7252539940367, 640.268768791528, 635.4776457871529, 630.3356463148025, 624.823123103189, 618.9164222318631, 612.587445018727, 605.8034773416538, 598.5273843207025, 590.7182434535462, 582.3324532363482, 573.3253130130134, 563.6530294391988, 553.2750701442269, 542.1567579447033, 530.271978660415, 517.6058598538474, 504.1572643016257, 489.94093018578184, 474.98908242187497, 459.35234187882423, 443.09977878924127, 426.3179996640761, 409.1092256773656, 391.58841050253005]
b=[i*10**32 for i in b]
def gravity(n,d=0.25):
    A=np.zeros([n,n])
    for i in range(n):
        for j in range(n):
            A[i,j]=d/n*(d**2+((i-j)/n)**2)**(-1.5)
    return A

n=85

A=gravity(n)
A=A.transpose()
for i in range(n):
    for j in range(n):
        A[i,j]=int(A[i,j]*10**32)
M=matrix(ZZ,n+1,n+1)
for i in range(n):
    for j in range(n):
        M[i,j]=A[i,j]
for i in range(n):
    M[n,i]=b[i]
M[:-1,-1]=2^60
M[-1,-1]=1
s=M.LLL()
X=s*M**-1

s=''
for i in range(n+1):
    if X[i,-1]==-1 or X[i,-1]==1:
        for j in range(n):
            s+=chr(abs(X[i,j]))
        break
print(s)
#SUSCTF{Maybe_th3_1nverse_Pr0b1em_has_s0m3thing_1n_comm0n_w1th_th3_LWE_Search_Problem}

Ez_Pager_Tiper

思路

题目定义了一个lfsr类和一个基于lfsr的伪随机数生成器类，分析位运算可知伪随机数生成器的输出要么是c2，要么是c1 ^ c2，由magic的二进制下1的个数决定，奇数个为c2,偶数个为c1 ^ c2，对于problem1,magic由移位得到，个数肯定为奇数，所以就是c2产生随机数，对于problem1的c2，由于数据量比较小，可以采用爆破（逆序爆破），也可以使用BM算法，求得seed3和mask2后，解密得到一个小故事，然后进入problem2，此时magic1的位数为偶数，所以是c1 ^ c2，考虑到数据量，我们枚举seed3，用lfsr2生成的序列去推lfsr1生成的序列，得到128位输出，这里就只能用BM了，求出seed1和mask1之后解密筛选得到flag。

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#sage
from base64 import *
from Crypto.Util.number import *
n1=64
n2=12
name=b'Date: 1984-04-01'
with open('C:\\Users\\lenovo\\Desktop\\problem\\MTk4NC0wNC0wMQ==_6d30.enc','rb') as f:
    data=f.read()
class generator():
    def __init__(self, lfsr1, lfsr2, magic):
        self.lfsr1 = lfsr1
        self.lfsr2 = lfsr2
        self.magic = magic

    def infinit_power(self, magic):
        return int(magic)

    def malicious_magic(self, magic):
        now = (-magic & magic)
        magic ^^= now
        return int(now), int(magic)

    def confusion(self, c1, c2):
        magic = self.magic
        output, cnt = magic, 0
        output ^^= c1 ^^ c2
        while magic:
            now, magic = self.malicious_magic(magic)
            cnt ^^= now >> (now.bit_length() - 1)
            output ^^= now
        output ^^= cnt * c1
        return int(output)

    def getrandbit(self, nbit):
        output1 = self.lfsr1.getrandbit(nbit)
        output2 = self.lfsr2.getrandbit(nbit)
        return self.confusion(output1, output2)

class lfsr():
    def __init__(self, seed, mask, length):
        self.length_mask = 2 ** length - 1
        self.mask = mask & self.length_mask
        self.state = seed & self.length_mask

    def next(self):
        next_state = (self.state << 1) & self.length_mask
        i = self.state & self.mask & self.length_mask
        output = 0
        while i != 0:
            output ^^= (i & 1)
            i = i >> 1
        next_state ^^= output
        self.state = next_state
        return output

    def getrandbit(self, nbit):
        output = 0
        for _ in range(nbit):
            output = (output << 1) ^^ self.next()
        return output


def encrypt(cipher):
    flag=1
    for i in range(len(name)):
        if data[:len(name)][i]^^cipher.getrandbit(8)!=name[i]:
            flag=0
    return flag

def get_key(mask,key,degree):
    R = ""
    index = 0
    key = key[degree-1] + key[:degree]
    while index < degree:
        tmp = 0
        for i in range(degree):
            if mask >> i & 1:
                # tmp ^= int(key[255 - i])
                tmp = (tmp+int(key[degree-1-i]))%2
        R = str(tmp) + R
        index += 1
        key = key[degree-1] + str(tmp) + key[1:degree-1]
    return int(R,2)

def get_int(x,degree):
    m=''
    for i in range(degree):
        m += str(x[i])
    return (int(m,2))

def BM(r,degree):
    a=[]
    for i in range(len(r)):
        a.append(int(r[i]))       #将 r 转换成列表a = [0,0,1,...,]格式    
    res = []
    for i in range(degree):
        for j in range(degree):
            if a[i+j]==1:
                res.append(1)
            else:
                res.append(0)
    sn = []
    for i in range(degree):
        if a[degree+i]==1:
            sn.append(1)
        else:
            sn.append(0)
    MS = MatrixSpace(GF(2),degree,degree)        #构造 256 * 256 的矩阵空间
    MSS = MatrixSpace(GF(2),1,degree)         #构造 1 * 256 的矩阵空间
    A = MS(res)
    s = MSS(sn)                       #将 res 和 sn 的值导入矩阵空间中
    try:
        inv = A.inverse()            # 求A 的逆矩阵
    except ZeroDivisionError as e:
        return -1,-1
    mask = s*inv 
    return get_key(get_int(mask[0],degree),r[:degree],degree),get_int(mask[0],degree)

for seed2 in range(1<<n2,0,-1):
    print("now:",seed2)
    for mask2 in range(1<<n2):
        if(encrypt(lfsr(seed2,mask2,n2))):
            print("find seed2:",seed2)
            print("find mask2:",mask2)

seed2=2989
mask2=2053
'''
lfsr2=lfsr(seed2,mask2,n2)
story=b''
for i in data:
    temp=i^^lfsr2.getrandbit(8)
    story+=long_to_bytes(temp)
print(story)
'''

Name=b'Date: 1984-12-25'
with open ('C:\\Users\\lenovo\\Desktop\\problem\\MTk4NC0xMi0yNQ==_76ff.enc','rb') as f:
    Data=f.read()
bits=''
for i in range(len(Name)):
    tmp=bin(Data[:len(Name)][i]^^Name[i])[2:].zfill(8)
    bits+=tmp


for seed3 in range(1<<n2,0,-1):
    lfsr2=lfsr(seed3,mask2,n2)
    output2=''
    for j in range(len(Name)):
        tmp=lfsr2.getrandbit(8)
        output2+=bin(tmp)[2:].zfill(8)
    output1=int(bits,2)^^int(output2,2)
    output1=bin(output1)[2:].zfill(128)
    seed1,mask1=BM(output1,64)
    if seed1==-1 and mask1==-1:
        continue
    lfsr1=lfsr(seed1,mask1,n1)
    lfsr2=lfsr(seed3,mask2,n2)
    flag=b''
    for i in Data:
        temp=i^^lfsr1.getrandbit(8)^^lfsr2.getrandbit(8)
        flag+=long_to_bytes(temp)
    print(seed3)
    if b'SUSCTF' in flag or b'CTF' in flag or b'ctf' in flag:
        print(flag)
#b"Date: 1984-12-25\r\nThough the hunger pangs were no longer so exquisite, he realized that he was weak.  He was compelled to pause for frequent rests, when he attacked the muskeg berries and rush-grass patches.  His tongue felt dry and large, as though covered with a fine hairy growth, and it tasted bitter in his mouth.  His heart gave him a great deal of trouble.  When he had travelled a few minutes it would begin a remorseless thump, thump, thump, and then leap up and away in a painful flutter of beats that choked him and made him go faint and dizzy.\r\nIn the middle of the day he found two minnows in a large pool.  It was impossible to bale it, but he was calmer now and managed to catch them in his tin bucket.  They were no longer than his little finger, but he was not particularly hungry.  The dull ache in his stomach had been growing duller and fainter.  It seemed almost that his stomach was dozing.  He ate the fish raw, masticating with painstaking care, for the eating was an act of pure reason.  While he had no desire to eat, he knew that he must eat to live.\r\nIn the evening he caught three more minnows, eating two and saving the third for breakfast.  The sun had dried stray shreds of moss, and he was able to warm himself with hot water.  He had not covered more than ten miles that day; and the next day, travelling whenever his heart permitted him, he covered no more than five miles.  But his stomach did not give him the slightest uneasiness.  It had gone to sleep.  He was in a strange country, too, and the caribou were growing more plentiful, also the wolves.  Often their yelps drifted across the desolation, and once he saw three of them slinking away before his path.\r\nThe content is an excerpt from Love of Life, by Jack London. The problem is mainly about LFSR and I've tried not to make it hard (with the cost of some running time, actually). Your flag is SUSCTF{Thx_f0r_y0uR_P4ti3nce_:)_GoodLuck!_1bc9b80142c24fef610b8d770b500009} and I hope you will enjoy our game. You'll find this problem so ez while solving other problems, which is created by --."

CTF Crypto Writeup

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！