2020招新Crypto补充题 WP

听说Crypto快被ak了,就捞了三道以前出的水题给肖桑,虽然招新结束也没人做出来……

禁止套娃#

题目描述:

9csK+#V;cV<,pg4(Gb^^{}/j5EbNnB[LBT9o[13yP>=AqLe5GOwtYK[Gl|W4AxIP]I]L[gW;[9ndOUIl_PK’+d.eV:?.9:I1l(G5&;-TwR=m5;HGe!Wb;%SLk|?=E;#[y#/w53{qU;1F4Dk2]P-P4@D)0!}B.;TR56lP.vzp&d6?yGe^s/{0!uR>q{9>t:/4dZ.#=PRU{b/;d/xd)j3_V3A.9(@F$Q8h0/hIQ@;PM$E5SefoUUJFFs)yP)1RsWWxcX,9H=Sm45i1./:XV.g?]j.zg7TTLo51r@(t5@lb2AI]Zs]2xW;^gY@U{0w’<%+.b3[a(RD6iC+=^0-<h3gIUB(SAdHLeY6z#v^&A^UZI,EZ)H]NtCHuW\RS3eR?7Y[%:*rg>*t6.Pm_-\ix3Ye}MF4@.t>OUW?)LOR+(O0qRGy/hQQy,m(J4Hw6o<^3[dw^S9u54l0U?dZoxzoq<x;}8x&Kn8/I#1V}Z%?;/(v7b]+4kVxq!%V@BjN(0Yl\c9Sn+9$CR^S!S+t<o(?m++JwHUCy):#b<mq:.L?X$IHQ’nPkq7U4Il<S1NR2,wE=Yq@j?1>Yuy]f4r[AEE<xp58r2

工具:python或在线工具。python可以参考这篇博客https://www.cnblogs.com/pcat/p/11625834.html ,在线工具太多了这里就不一一列举。

解法及思路:
0.疯狂套娃就完事了,题目考察的是大家对于Base编码的了解。

1.目前Base系列有Base16、Base32、Base36、Base58、Base62、Base64、Base85、Base91、Base92、Base128等。其中每种编码的字符集也不同:

Base16:0123456789ABCDEF

Base32:ABCDEFGHIJKLMNOPQRSTUVWXYZ234567

Base36:0123456789abcdefghijklmnopqrstuvwxyz

Base58:123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz

Base62:0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz

Base64:ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/

Base85:Base85有三种,这里就不写了感兴趣可以去了解下。

Base91:ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!#$%&()*+,./:;<=>?@[]^_`{|}~”

Base92:!#$%&’()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[]^_abcdefghijklmnopqrstuvwxyz{|}

Base128:0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz\xb5\xb6\xb7\xbc\xbd\xbe\xc1\xc2\xc3\xc4\xc5\xc6\xc7\xc8\xc9\xca\xcb\xcc\xcd\xce\xcf\xd1\xd2\xd3\xd4\xd5\xd6\xd7\xd8\xd9\xda\xdb\xdc\xdd\xde\xdf\xe1\xe2\xe3\xe4\xe5\xe6\xe7\xe8\xe9\xea\xeb\xec\xed\xee\xef\xf1\xf2\xf3\xf4\xf5\xf6\xf7\xf8\xf9\xfa\xfb\xfc\xfd\xfe\xff

2.因为提示了从小往大套的套娃,所以解密的时候就要从大往小解,从题目来看可以猜出是Base92(因为懒就没套Base128),然后从Base91开始依次往下解就可以了:

Base91:
Co&Fi)[z%#tflk5d?DNcrZGY4KxtwvzVo(=jo06KU<[;j4i2]+Zp]H*GHyxQk]P2q5w]07BCJQKhEof~ZuJ$wHj%zaHKZ@j1tsFW>*jdP%=&O3i~ZGEy4Fj*NAsP+0QZ[bEbFvX3wclw/U+ZkHOr}uYH__R%MO?@;B*O6rI!=.E_c$J5b(3Vp9P.P|WCM”/Kd$kp;%G.4pZpa,/)fYojT!M9Z`89XIo6bD+)?1=L|6.ZEXsy^vuYeLyVYxVbury*pxB4H3"XB&Gb^"uJh@<LaNH"SZ3k/Zw0WUah2Yo;*EGR^v7Rb1A2lKO]DdHqeF#)9D)+uNO$O<fOm4!%TC%e+<n#"O*DM}4NHrzpdBJ4g|6=VZBxb0]95yKU!COGmI2i=A8eu~L5KZ}jh%/bOmP#WKGwAEVVZDa=jo!{VH/]a@b8Ayl)S#<tcmX”)PM&#zDnT(7[b!(Qo>Fn&Ky`b@>&FOm^*^Q_*xkZ12Q2{rA

Base85:
:.A8a9ijeV<CT!@9$Gd<``9T=_^to9ijr.:/sb\=%=uG<(:#7;-$/):KKP3<GchY<)l@E<&&/E;f4p>@o[&W@7Oib<I.hP;FNH_<&/8I=u&]H:ITM,;))T\=YX)<&.$#<_#bV:0:7m@RsC:AOT’Y:K2”M:K14i=&(C:K::iA9r#H@RjUC@n:)b9l2mH=]I1H>"D[t@RO7B=u0>b;FP+j@9@&8;-$^T;))c:/tJ4@RijB9il”$;JUM5@W#(cASP+5;__0(<(:%jA6!+p:.@Nq=%>"@TQ0I<E30W=%>t@9iu@<<,?Al:3pSU<(D0i;Jf<W<A6:K:,"[<*!oo9h/)J<dJO<@VS5C;DM!C<EN-Q@7<U==`$W!:/ttO<A@6m<``<l<HgSh~>

Base64:
NFVUMWFJUFNkaUY3VWU0YjV4MWJsNUFQWG1VTFYwQVFoOW92UmtVTUE5T1k3SnBncUdnaGd4UzZZRE5qT2l5Z2JPOExSQ1dTY1ZZT2I2VGJMNXNWbHRqeEFGOThuOTRRWTRyOURQdzk2bGZscHc2Mm93YU1GZHVZbDVyZ3ZYREdMaXdNQVV5Q1hWNUZjbGE2MWhKRkx3bnRtejRGS1R0TFZTdUc2NFAzYmZ5bWJyUUY2WGM3MXpZTllsNzhXTGx4RmRyU05oN092TVo4MGRBVzk4bjBhR2NOUXR0aEE0YmFHNUhwU1NwVWVGUw==

Base62:
4UT1aIPSdiF7Ue4b5x1bl5APXmULV0AQh9ovRkUMA9OY7JpgqGghgxS6YDNjOiygbO8LRCWScVYOb6TbL5sVltjxAF98n94QY4r9DPw96lflpw62owaMFduYl5rgvXDGLiwMAUyCXV5Fcla61hJFLwntmz4FKTtLVSuG64P3bfymbrQF6Xc71zYNYl78WLlxFdrSNh7OvMZ80dAW98n0aGcNQtthA4baG5HpSSpUeFS

Base58:
4Pzo8BpCWJkoDjHCyFqeWMnoreXAGC7fUBgNEsVVLPLcn72Va5bpndReKrjLuAeuwReD7zKEkYrwG1bxFjraMz5CDS3cR2DJzKgoPSMVF4nkkUGq1xsBtBpv3LKneWtGL3cxwMuycB3qUuHUV7EaFUCyfcZJQcA9uWnvzRvCoun

Base36:
15061929375867113824841966869787948457757906197916407858560049868496672562120390798001482101892391044953117327200758517883135

Base32:
GZCDMMJXGQ3TENZZGZDDOMZWHA3EENRRGY2DMRRWIM3EGNSEGYYTMQRWGU3EINRVGY4DMMJXGA3TANZZ

Base16:
6D617472796F73686B61646F6C6C6D616B656D656861707079

得到原文:matryoshkadollmakemehappy再套上flag就行了,so easy!
3.flag{matryoshkadollmakemehappy}

LCG#

题目描述:
工具:python
解法及思路:
0.这道题的考点为 LCG (线性同余发生器(Linear congruential generator)),灵感来自Soreat_u师傅在2019 NCTF中出的 LCG 题目和 Z3R0YU师傅的一篇博客
具体的攻击思路以及推导在Z3R0YU师傅的博客里以及写得非常清楚了,这里就不再赘述。
1.由此简单说一下这道题解题思路,首先根据根据输出的几个值依次确定模数、乘数、增量。故此可以推算出该随机数序列往后值,因为加密方式采取了异或运算,故逆着再异或一遍即可得到明文。
2.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
# -*- coding: utf-8 -*-
import gmpy2

def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, x, y = egcd(b % a, a)
return (g, y - (b // a) * x, x)

def modinv(b, n):
g, x, _ = egcd(b, n)
if g == 1:
return x % n

def crack_unknown_increment(states, modulus, multiplier):
increment = (states[1] - states[0]*multiplier) % modulus
return modulus, multiplier, increment

def crack_unknown_multiplier(states, modulus):
multiplier = (states[2] - states[1]) * modinv(states[1] - states[0], modulus) % modulus
return crack_unknown_increment(states, modulus, multiplier)

def crack_unknown_modulus(states):
diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
zeroes = [t2*t0 - t1*t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
modulus = abs(reduce(gmpy2.gcd, zeroes))
return crack_unknown_multiplier(states, modulus)

print crack_unknown_modulus([7544171032306805964,7718972702969096199,6292365728341114862,7372286589453751584,7903720898235007348,7336209243121042116])

恢复出 乘数 m = 672257317069504226 ,增量 c = 7382843889499547368 ,模数 n = 9223372216854775783

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
m = 672257317069504226  # "乘数"
c = 7382843889499547368 # "增量"
n = 9223372216854775783 # "模数"

def decrypt(c, key):
m=''
m=c^key[6]
for i in range(7,15):
m=m^key[i]
return m

s=[]
s.append(7544171032306805964)
for i in range(1,16):
s.append((s[i-1] * m + c) % n)

cipher = 17256520551932211059
flag = decrypt(cipher, s)
print flag

3.flag{9261754567465340477}

听说你会RSA#

题目描述:
工具:python
解法及思路:

0.不难发现是RSA加密算法,已知条件为:

n = 26061686048002154630453426526835067700023746912021991684138331030171624329551027949458262323274893963582445971458394769916795892271029901531421776961634319100681703941873670544279357885695562279064839142902374941253369640958380513575525690828876953116434323256961676982064656740067919348735774557673468065418330446254071423698564792591912030249547900282718209439183449459005322301530549960029496669021341648787282853880830590729491527999383661401855536616116529352701871823081442737448707990142506617306341108498712575167478886917448241346613732553646409787061458997883508224778536174266923800282110345668737280244741
s = x + y + z = 280513550109578771087736997761823252895
a = (741251 * x - 589635 * y + 543219 * z) (mod n)
c0 = x^19 (mod n)
c1 = y^19 (mod n)
c2 = z^19 (mod n)

故此符合Related Message Attack攻击条件
5
具体的攻击思路以及推导参见 ctf-wikiA New Related Message Attack on RSA

1.exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = 26061686048002154630453426526835067700023746912021991684138331030171624329551027949458262323274893963582445971458394769916795892271029901531421776961634319100681703941873670544279357885695562279064839142902374941253369640958380513575525690828876953116434323256961676982064656740067919348735774557673468065418330446254071423698564792591912030249547900282718209439183449459005322301530549960029496669021341648787282853880830590729491527999383661401855536616116529352701871823081442737448707990142506617306341108498712575167478886917448241346613732553646409787061458997883508224778536174266923800282110345668737280244741
s = 280513550109578771087736997761823252895
c1 = 2842866273228119855423150901343083724336085916664562161984104906391458605624616440756064723739342966597630989488134890684705426125814191168359821021266342464782794096018915209771352199879853868083755152528900324616642529684077759892188174226925807021540817099132779735196865421822545035100660026050722692252216979066807706481094080662013913527211197788538594492098474842913746597136803451955777263364832993176179610566332333737946808257930041708869824543244045917218863814095082218838866324017560942783806849897095830642694521712610507217388893072617313966136258797031544440526479233350282017417527903966363941240053
c2 = 22463687625108712775167179290411094487454718167041556301175426340849975375634628585614881230964001050742731248110732703633830203590648930747399989103655087291442350194689341993920842662638729966980832891623221823320707990094237257124573480820811749026966826336482885636191139077233028373544828377351049847875868609801415440899405034024529704860022711043675116070216987913726925884191720910175492891559030833867208429938430492662292716136039663002639017655248630830924817294515004163596481472836718352118898383554973744061626143270729352047305625288378756632908629337740362838801297544597099692055501698013078120590982
c3 = 18432002613568266691185373601826072494084636743765308918927635340721617236187319721600539130733513549332195882554662119570931876842509745779663516520500279239138698139063460904823268849248415932071863595015696371995764407751114571842827593527071565407336401365576951975697732247417538400495356014440045797877218282974279554615002892817079562159168051103763147186282281710447110009157536070507455948491490527769618046289511219162940289111274457525920131792771383970590155667308115076969116947877466497165584007004647681947224852682863201984908784407785800190763088437665142562855777350070677964426006231754037983086034

R.<x, y, z> = Zmod(n)[]
I = ideal(x + y + z - s, x^19 - c1, y^19 -c2, z^19 - c3)
res = I.groebner_basis()

m1 = n - int(res[0] - x)
m2 = n - int(res[1] - y)
m3 = n - int(res[2] - z)
m = (int(m3<<256) + int(m2<<128) + int(m1))
print (hex(m)[2:].strip('L'))

得到
666c61677b62663636346662372d353439382d346266322d616335662d6466653364633531613230327d060606060606

再hex转str就完事了,偷懒直接用在线工具

2.flag{bf664fb7-5498-4bf2-ac5f-dfe3dc51a202}