JLU校赛

badmonkey 2020年10月12日 1,131次浏览

2020 Spirit CTF

凯撒密码

签到题，google一下，遍地都是在线工具原理嘛，就是rot一下就行了。

小猪佩奇

签到题，比赛中间临时出的用于送(bu)分(shi)，同样的google一下就会发现其实是猪圈密码，，不过需要注意下{和}无法被加密，本质就是单表替换。

baby_reverse

源码如下:

# python3
from badmonkey import flag

message = bytes_to_long(flag)

enc = message ^ message>>23

print("enc = ",enc)
# enc = 696190889020604856890193198853561201348825165171326836202150445122902404137656377702109518236445

引导向的题目，主要是考察一下分析能力，不难发现其实，enc的前23位其实是明文的前23位，而enc的23-46位则是明文的前23位和23-46位的异或，由于我们知道明文的前23位，因此很容易恢复明文的23-46位以此类推，可以恢复所有明文的比特位。学弟有用cpp写的exp(很强了)，我这里就贴出python版本的exp：

# python3
enc = 696190889020604856890193198853561201348825165171326836202150445122902404137656377702109518236445
shift = 23
def inverse_right(res, shift, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp >> shift
    return tmp
flag = inverse_right(enc,shift,enc.bit_length())
print(bytes.fromhex(hex(flag)[2:].strip("0xL")))

easy_reverse

这题有三个用z3解的队伍(全是18级的,均在前十)，有亿点离谱嗷，三支队伍同时非预期，其中两只队伍代码高度重复，虽然爷锤不动你，但是爷看不起你。恶心到爷了，爷惹不起，爷爪巴。

源码信息如下：

from Crypto.Util.number import *
from badmonkey import flag
m = bytes_to_long(flag)

BITS = m.bit_length()

a,b,c,d = 15,27,19,23
mask1 =  3698415493855604199601451107484163420720646551661606649093806737041154400431942060340531696401
mask2 =  3460949362284136053271491912952156811286686375965162899233783178191434976143378804364416056910


def encrypt(y):
    y = y ^ y >> a
    y = y ^ y << b & mask1
    y = y ^ y << c & mask2
    y = y ^ y >> d
    return y&((2<<BITS)-1)

enc = encrypt(m)
print("enc = ",enc)
# enc = 1050202800288756594888207862919284086044293654918425636192291797436341243157293011540594049798

比baby_reverse复杂一点，其实也没复杂多少。我们可以发现，return的值最后与了一下2<<BITS -1其实就是mod 2^BITS，而这里的&mask1是在左移，或者右移运算后与上去的(注意表达式的符号的优先级，y ^ y << b &mask1 ==> y ^ ((y<<b) & mask1))，这次我们仍然知道LSB或者MSB的部分位，利用这些部分位，根据baby_reverse的思想我们可以恢复每一步的中间结果，然后逆推回去就可以得到初始的信息。exp如下：

a,b,c,d = 15,27,19,23
mask1 =  3698415493855604199601451107484163420720646551661606649093806737041154400431942060340531696401
mask2 =  3460949362284136053271491912952156811286686375965162899233783178191434976143378804364416056910

BITS = mask1.bit_length()

enc = 1050202800288756594888207862919284086044293654918425636192291797436341243157293011540594049798

# right shift inverse
def inverse_right(res, shift, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp >> shift
    return tmp


# right shift with mask inverse
def inverse_right_mask(res, shift, mask, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp >> shift & mask
    return tmp

# left shift inverse
def inverse_left(res, shift, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp << shift
    return tmp


# left shift with mask inverse
def inverse_left_mask(res, shift, mask, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp << shift & mask
    return tmp

def encrypt(y):
    y = y ^ y >> a
    y = y ^ y << b & mask1
    y = y ^ y << c & mask2
    y = y ^ y >> d
    return y&((2<<BITS)-1)


def recover(y):
    y = inverse_right(y,d,BITS)
    y = inverse_left_mask(y,c,mask2,BITS)
    y = inverse_left_mask(y,b,mask1,BITS)
    y = inverse_right(y,a,BITS)
    return y&((2<<BITS)-1)

flag = recover(enc)
print(bytes.fromhex(hex(flag)[2:].strip("0xL")))

lcg-5

其实也是白给题，之前在热身赛的时候已经把lcg系列的wp发过了，懒得写了，直接借用学弟的解题思路

根据数论的一条性质 如果有几个随机数分别乘以n，那么这几个数的欧几里德算法(gcd)就很可能等于n。

定义a为乘数,c为增量,n为模数

$$
s_{n} = a \times s_{n-1} + c\mod n
$$
$$
t_{n-1} = s_n - s_{n-1} = (s_{n-1}\times a + c)-(s_{n-2}\times a + c)=t_{n-2}\times m \mod n
$$

据此可推出
$$
t_{n+1}\times t_{n-1} - t_{n}\times t_{n} = (m\times m \times t_{n-1}\times t_{n-1}-m\times t_{n-1}\times m\times t_{n-1} ) = 0 \mod n
$$

据此计算 n

from Crypto.Util.number import *

s = [9997297986272510947766344959498975323136012075787120721424325775003840341552673589487134830298427997676238039214108, 4943092972488023184271739094993470430272327679424224016751930100362045115374960494124801675393555642497051610643836, 6774612894247319645272578624765063875876643849415903973872536662648051668240882405640569448229188596797636795502471, 9334780454901460926052785252362305555845335155501888087843525321238695716687151256717815518958670595053951084051571, 2615136943375677027346821049033296095071476608523371102901038444464314877549948107134114941301290458464611872942706, 11755491858586722647182265446253701221615594136571038555321378377363341368427070357031882725576677912630050307145062, 7752070270905673490804344757589080653234375679657568428025599872155387643476306575613147681330227562712490805492345, 8402957532602451691327737154745340793606649602871190615837661809359377788072256203797817090151599031273142680590748, 2802440081918604590502596146113670094262600952020687184659605307695151120589816943051322503094363578916773414004662, 5627226318035765837286789021891141596394835871645925685252241680021740265826179768429792645576780380635014113687982]
t = []
for i in range(9):
    t.append(s[i]-s[i-1])
n = []
for i in range(7):
    n.append(GCD((t[i+1]*t[i-1]-t[i]*t[i]), (t[i+2]*t[i]-t[i+1]*t[i+1])))
print(n)

可得

[2, 1, 393916182865583204167593579626567099983463054572651446294350689155749034982777402793379583263905054399035065243497725, 393916182865583204167593579626567099983463054572651446294350689155749034982777402793379583263905054399035065243497725, 15756647314623328166703743185062683999338522182906057851774027566229961399311096111735183330556202175961402609739909, 47269941943869984500111229555188051998015566548718173555322082698689884197933288335205549991668606527884207829219727, 47269941943869984500111229555188051998015566548718173555322082698689884197933288335205549991668606527884207829219727]

抛去2,1 取最大公约数

n=15756647314623328166703743185062683999338522182906057851774027566229961399311096111735183330556202175961402609739909

根据模数计算乘数a

from Crypto.Util.number import *

s = [9997297986272510947766344959498975323136012075787120721424325775003840341552673589487134830298427997676238039214108, 4943092972488023184271739094993470430272327679424224016751930100362045115374960494124801675393555642497051610643836, 6774612894247319645272578624765063875876643849415903973872536662648051668240882405640569448229188596797636795502471, 9334780454901460926052785252362305555845335155501888087843525321238695716687151256717815518958670595053951084051571, 2615136943375677027346821049033296095071476608523371102901038444464314877549948107134114941301290458464611872942706, 11755491858586722647182265446253701221615594136571038555321378377363341368427070357031882725576677912630050307145062, 7752070270905673490804344757589080653234375679657568428025599872155387643476306575613147681330227562712490805492345, 8402957532602451691327737154745340793606649602871190615837661809359377788072256203797817090151599031273142680590748, 2802440081918604590502596146113670094262600952020687184659605307695151120589816943051322503094363578916773414004662, 5627226318035765837286789021891141596394835871645925685252241680021740265826179768429792645576780380635014113687982]
n = 15756647314623328166703743185062683999338522182906057851774027566229961399311096111735183330556202175961402609739909
a = []
for i in range(9):
    a.append((s[i+1]-s[i])*inverse(s[i]-s[i-1], n)%n)
print(a)

运行结果

[12579699113017418775336283330563701152016249260578453762156527994444775120651738985953338704360108899145113848406752, 1421031764968400527762460898092137083742564633301039280991459091107942075801014756436528426924261706134389048251788, 1421031764968400527762460898092137083742564633301039280991459091107942075801014756436528426924261706134389048251788, 1421031764968400527762460898092137083742564633301039280991459091107942075801014756436528426924261706134389048251788, 1421031764968400527762460898092137083742564633301039280991459091107942075801014756436528426924261706134389048251788, 1421031764968400527762460898092137083742564633301039280991459091107942075801014756436528426924261706134389048251788, 1421031764968400527762460898092137083742564633301039280991459091107942075801014756436528426924261706134389048251788, 1421031764968400527762460898092137083742564633301039280991459091107942075801014756436528426924261706134389048251788, 1421031764968400527762460898092137083742564633301039280991459091107942075801014756436528426924261706134389048251788]

可取a=1421031764968400527762460898092137083742564633301039280991459091107942075801014756436528426924261706134389048251788

据此计算c

s = [9997297986272510947766344959498975323136012075787120721424325775003840341552673589487134830298427997676238039214108, 4943092972488023184271739094993470430272327679424224016751930100362045115374960494124801675393555642497051610643836, 6774612894247319645272578624765063875876643849415903973872536662648051668240882405640569448229188596797636795502471, 9334780454901460926052785252362305555845335155501888087843525321238695716687151256717815518958670595053951084051571, 2615136943375677027346821049033296095071476608523371102901038444464314877549948107134114941301290458464611872942706, 11755491858586722647182265446253701221615594136571038555321378377363341368427070357031882725576677912630050307145062, 7752070270905673490804344757589080653234375679657568428025599872155387643476306575613147681330227562712490805492345, 8402957532602451691327737154745340793606649602871190615837661809359377788072256203797817090151599031273142680590748, 2802440081918604590502596146113670094262600952020687184659605307695151120589816943051322503094363578916773414004662, 5627226318035765837286789021891141596394835871645925685252241680021740265826179768429792645576780380635014113687982]
n = 15756647314623328166703743185062683999338522182906057851774027566229961399311096111735183330556202175961402609739909
a = 1421031764968400527762460898092137083742564633301039280991459091107942075801014756436528426924261706134389048251788
c = []
for i in range(9):
    c.append((s[i] - a*s[i-1])%n)
print(c)

运行结果

[4733695552606335950008399086439710463503482083237959789567398282795949881522148352994723475908507826081987110658922, 11545938748867242620537115092757411052463250917387015436216035440161952627398745850382131607456750667325541719714933, 11545938748867242620537115092757411052463250917387015436216035440161952627398745850382131607456750667325541719714933, 11545938748867242620537115092757411052463250917387015436216035440161952627398745850382131607456750667325541719714933, 11545938748867242620537115092757411052463250917387015436216035440161952627398745850382131607456750667325541719714933, 11545938748867242620537115092757411052463250917387015436216035440161952627398745850382131607456750667325541719714933, 11545938748867242620537115092757411052463250917387015436216035440161952627398745850382131607456750667325541719714933, 11545938748867242620537115092757411052463250917387015436216035440161952627398745850382131607456750667325541719714933, 11545938748867242620537115092757411052463250917387015436216035440161952627398745850382131607456750667325541719714933]

可取c=11545938748867242620537115092757411052463250917387015436216035440161952627398745850382131607456750667325541719714933

至此已获得lcg全部参数

from Crypto.Util.number import *

s = 9997297986272510947766344959498975323136012075787120721424325775003840341552673589487134830298427997676238039214108
n = 15756647314623328166703743185062683999338522182906057851774027566229961399311096111735183330556202175961402609739909
a = 1421031764968400527762460898092137083742564633301039280991459091107942075801014756436528426924261706134389048251788
c = 11545938748867242620537115092757411052463250917387015436216035440161952627398745850382131607456750667325541719714933

flag = long_to_bytes((s-c)*inverse(a,n)%n)
print(flag)

结果为

b'Spirit{final__lcg__is__co0m1ing__are_you_ready?}'

baby_math

同样的热身赛，已经出过了类似的题，不过数比较小，可以直接计算。源码如下：

# baby math
from math import factorial
from badmonkey import flag

p =  6754809195983416889371518438404230464318771258362527973287334033265667200119099459184180646680169474847824019197256829826149222241090098845978570412659797

def my_wilson(x,p):
    return factorial(x)%p

res = my_wilson(p-2333,p)
mid = md5(str(res).encode()).hexdigest()
assert  mid == "a3fe2bd4fb7c2f3642d57d67967c649b"

print("Spirit{{{}}}".format(res%(2**100)))

不难发现my_wilson其实是想用于威尔逊定理的计算，不过并不是计算$(p-1)! \mod p$ 而是要计算$(p-2333)! \mod p$，我们只需要稍微变化一下。由于$(p-1)! \mod p$ $(p-1)! \equiv -1 \mod p$所以有$(p-2)!(p-1) \equiv -1 \mod p $，即$(p-2) \equiv 1 \mod p$，由于(p-2333)!(p-2332)(p-2331)...(p-2) = 1 mod p，所以算$(p-2333)! \mod p$其实就相当于求(p-2332)(p-2331)...(p-2) mod p的逆元就行了。于是可以写出如下exp:

from Crypto.Util.number import *
from hashlib import md5
p =  6754809195983416889371518438404230464318771258362527973287334033265667200119099459184180646680169474847824019197256829826149222241090098845978570412659797

res = 1
for i in range(2,2333):
    res = res*inverse(p-i,p)
    res %= p
mid = md5(str(res).encode()).hexdigest()
assert  mid == "a3fe2bd4fb7c2f3642d57d67967c649b"
print("Spirit{{{}}}".format(res%(2**100)))

结语

又摸了一篇，爬了爬了，赶紧学pwn。

上一篇： PWN:从零开始的学习之路