0xGame2021PartCrypto

0xGame部分Crypto题目出题手记

Week 1

1: MyFunction

题目加密代码：

1
2
3
4
5
6
7
8
from math import log
from secret import flag
def f(x):
    return x*log(x) #log(x) is "y=ln(x)" used in maths

for i in flag:
    print(f(ord(i)))
#输出部分略去

这个题目出的目的是让新生熟悉一下Python的代码，顺便通过一个简单的python代码，了解一下python的基本语法，是模仿的西电的新生赛出的。西电的新生赛出的用的函数是$y=e^x$，也给出了很多数字。因为$y=e^x$有很明显的反函数，所以那个题可以直接对所有的输出取对数，就可以获得明文。但这个题目不行，因为$y=x\ln x$没有可以写出来的反函数形式别问，因为我数学不行，我求不出来。因此这个题目的正确做法是枚举可能的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
from math import log
def f(x):
    return x*log(x)

arr=open("output.txt","r").readlines()
s=""
for y in arr:
    for i in range(1,128):
        if abs(f(i)-float(y))<0.0003:
            s+=chr(i)
            continue
print(s)
#0xGame{YouH4veKn0wedPy7honL081s<y=ln(x)>InM47hs}

不过实际的解题中，真正写脚本的新生并不多，有的是通过excel打表，然后一个一个解的。把所有的$x$求出来之后，然后查ASCII码表一个一个手动对照的。

之前验题的时候，我考虑到了浮点误差，因此这边用的是abs(f(i)-float(y))<0.0003判断的。实际上在$x>40$的时候，$(x+1)\ln(x+1)-x\ln x$的差值已经超过了$2$。因此直接取整也是可以的。不过最后我发现不考虑浮点误差的问题照样也是可以做的。

2.Class 8

一个争议性挺大的题目。因为当时出题的时候，我并不想出古典密码题——属实没意思。但既然要求出一个古典密码，那就只能出一个。。

最后出题的时候确实是出难了，虽然To1in那个ManyCode那个题也出难了，但他最后简化了，然后我看到当时已经有2、3个人解出来了，就没有简化。八种古典密码放在一起。有的还有歧义。。。（不过虽然还是有学弟没有跟我交流，也做出来了。

Class8

1
2
3
4
5
6
7
8
第1、6位是盲文
第2、7位是跳舞的小人
第3位是猪圈密码
第4、11、16位是手机九键键盘
第5、9、14位是莫尔斯电码
第8、12位是银河字母
第10、15位是培根密码
第13位是电脑键盘，cfgb之间围着的是V

这道题一开始打算出规则的单词的，但后面就出得不规则了。主要是第13位、第15位出问题出得非常多。第15位确实有两种解法，因此第15位是 O 最后也算对了。

flag: 0xGame{CLASSLNRDDLDVTNB} 或 0xGame{CLASSLNRDDLDVTOB}

以后再也不出这种无聊的古典密码题了。。。。

3.ABC Of RSA

这个题主要是用于给新生入门一下RSA相关知识。。

1
2
3
4
5
在RSA加密中，已知：
p=9677
q=9241
e=10009
求解密指数d，包上0xGame{}提交。

这个如果下载Python的密码学专用包，写起来会非常快。

1
2
3
4
5
6
from Crypto.Util.number import *
p=9677
q=9241
e=10009
print(inverse(e,(p-1)*(q-1)))
#39982249

不过发现很多学弟学妹没有装包的情况下，利用$ed=k\phi+1$，暴力枚举$k$的。这个虽然这道题是可行的。但下一个题，当数字大起来的时候，就显得不可行了。。

4.BlackGiveRSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
from secret import flag,p,q
assert q>p 
n=p*q
e=10007
assert len(flag)==42
for i in range(6):
    m=bytes_to_long(flag[i*7:i*7+7])
    print(pow(m,e,n))
print("Encryption using modulus n=",n)
"""
OutPut:
1150947306854980854
243703926267532432
1069319314811079682
688582941857504686
670683629344243145
1195068175327355214
Encryption using modulus n= 1687126110378632809
"""

RSA入门题，直接放到yafu/factordb上分解出$p=1175078221,q=1435756429$，分别是Am4的QQ和自己的QQ号。。

然后直接按照RSA的解密方法分解就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
p,q=1175078221,1435756429
n,phi=p*q,(p-1)*(q-1)
d=inverse(10007,phi)
cipher=[
    1150947306854980854,
    243703926267532432,
    1069319314811079682,
    688582941857504686,
    670683629344243145,
    1195068175327355214
    ]
m=b""
for c in cipher:
    m+=long_to_bytes(pow(c,d,n))
print(m)
#0xGame{ChuTiRenDeQQShiJiShangJiuShiQDeZhi}

Week 2

Equation

1
2
3
4
5
解方程题，RSA加密，没有附件，远程连接一次过去就可以接收加密数据。解出来的明文结果要long_to_bytes
p,q∈(2**1407,2**1408) 
nc 47.101.38.213 60718
Author:huangx607087
QQ:1435756429

linux虚拟机中，直接在终端输入nc 47.101.38.213 60718 ，可以获得$n,e,c,f$，其中$f=ap+bq$。

（当然，本题为防作弊，每次连接后发出的$a,b$内容都不一样，但$f=ap+bq$的格式是肯定的，你获取的 系数可能与此不同，但不影响解题）。

随机连接上去，获取一组数据：

1
2
3
4
5
6
n =
32366272889292879088882195998253721958216118427319043123590736165426820884306499725050727749537295796623781690886255268016096819542474814457437532341958464848643200659916387692563367270923362263462485626863278634698636219570995613163637857962196938268241034329466928075048970301826587646917598116612437415879221437295531628513384414258368369916946742389703355179727112580592683439416261547865491725025586248605272291584028774967553627942724579632389254496409849216841409604686980557654983994405692268823696566554514932549687234389560838939048535333918846662927374585386766723838290671937789073306966759191649325746073717288252462817952734597692830994622255635546908058581524477518532518924112976563197010192251929746445312969880127879576958492529042343256141675368594461418257288354657105617752796615735654975200326101463143024542800708390095145361
e = 906371
c =
15326438748659000169738486078886997781541935909035823368289334280968233481809714574428064879237827914760740438396085818400100752918474657858554388771724064383701395897618045276281398824434274848557653909089994244435972710632336639335300023667869547648881808002952139588112935030846125601449819192271492110196773991802015580978532663199706950910343070008368979693052990985227852719668245569238857908655227385682414319846321429428810022909530050444105837210601614933221417662986725539709495237298445020038006845869543594704774018595363714269915863872404761678621066244387220449270355482924374014811790125751689511923646410269665459941400645007655696532244986604521949477159649748754760874919743902307824198126893002486445262315126416725774433901321311453440889692050265638750239216391568288836776466397695369910655394827082589725264284100323144743368
f = 4071 * p + 7840 * q = 70609572383507708646716591625555712379946460153989879089689539734922903656784859764618771054881882855097217363252911229485210947514270593649999198018427595733868497208821457315913778178532267217419587556519640009047854707649751663514017094626487619210733938544175505589938842947647526503757953723232894419183885106501307587792888770406913619606926851412157084401688469130571174114717305950501097282446764439401475500746719477183

方法一：

有Sagemath的，录入4个已知数据后，可以直接利用以下的代码求解：

1
2
var('p q')
solve([p * q == n, 4071 * p + 7840 * q == f],(p, q))

然后就可以解出：

1
2
p == 5083858928708691100777959116505887333680880438073587959441589817260857392095426280573595409516065652457557087257582498766032467943842309357363106558257787135298633883829312431320375735688577512605869266440855676882837431188700856046398782182742328211552394159944490832515415689088811946496781884336421281783780403089383634369539994631626195420357561861396522278697114564263369128050977173067291911354418900362132140587209993
q == 6366477383256967751970602048757684316904540292167385523826891274088514440505660634745365324329334130604911028192256744516414894198327621461246682553540834732916805952519429388776598030426539306581772164902923029140028510877621234508817302597008112380293895652938964720761299193541705748669586055114709614928841209888319746463583093400709614547276940953368857424121494354522321223778287994763284682566699629595310657706146377

方法二：

没有Sagemath的，可以编程求解。

由于$pq=n,4071p+7840q=f$，因此$4071p=f-7840q$，然后有$4071n=4071pq=(f-7840q)q$。

因此，我们可以构造方程$7840x^2-fx+4071n=0$，根据二次函数对称轴的位置，发现我们需要的值位于对称轴右侧。因此我们直接二分求解即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
def y(x):
	return 7840*x*x-f*x+4071*n
L, R = 2**1407, 2**1408
while L <= R:
	M = (L+R)//2
	if y(M) < 0:
		L = M+1
	if y(M) > 0:
		R = M-1
	if y(M) == 0:
		print(M)
		break
#6366477383256967751970602048757684316904540292167385523826891274088514440505660634745365324329334130604911028192256744516414894198327621461246682553540834732916805952519429388776598030426539306581772164902923029140028510877621234508817302597008112380293895652938964720761299193541705748669586055114709614928841209888319746463583093400709614547276940953368857424121494354522321223778287994763284682566699629595310657706146377

这个题目还可以用z3做。不过很多人的思路是根据二次方程求根公式，想要求$\sqrt{b^2-4ac}$的值。而这个值也可以通过函数的单调性，二分求解。。

Week 3

CryptoSignin3

题目是给出了RSA加密中的$e,n,c$，让你求出$5m$的加密结果（默认$c$是$m$的加密结果）。

这道题主要考察RSA的乘法同态性，由于$m^e \equiv c \pmod n$，因此我们有
$$
(5m)^e\equiv 5^em^e\equiv 5^ec \pmod n
$$
因此，我们只需要计算$5^{e}c \mod n$的值即可。然后转一下str类型，取最后25位即可。

1
2
3
4
n=2422711508900009723470102727278184898228579351729629175495904760516536114771819178772843940622693480942295987032442940867670858858530606887743557817380121361626756206355705110299827107648704348792184242506797212331641569408152865458082131811787893384573565771304686373397987779236692592582009393836324438173880350455958049987506807351970912049246353746635267159741115761548052126938491673479606393396100458729618059852813438444299361468512008386975558106274324688665963516424534366163011821633197140729560513838981241752422348968312410911097523311183305812013220724215584901550592570168096761576532621840320623463208702401829189862290303098674021012353400081288819532365151476738751064469957971192132666136590103567843662591585345483671185892760751481722342403025068374371716176981888876927119331602694699049322860285991375002326127401769287658952682585275891296760732815680898653162425658904911584903825163141576325803464119867837508173795728753701563149748508464162635777787788266240105654089919642728171076155284842273517797069725130328742992830894075552022372717019366081516680737
e=10007
c=1285901843278876234855607310979623200548989981628646673003523113580651626686523566799395153922258813222744927018205882436414589516795415393990321785993777190284046937462277341231780571523062023964463963139910673601962881978696384360480028132774373962893042697866284303407898274683337284548529324550392212212259945699167254341062208031468355814520907121576009140399280898693924706067921614961798886587174234822238887374399666546113213239071736098162263227821798099750616137755055435397986788792824117529508255014392344357337010003489080209442530630893119917536518243474797351694663533728052713570044084663268350004738561234330890283895430742958255842196396542672482459665354739161276178850775803757753274712331067038077233072381051447436014423088822190073982228377699578821863871042501139434131053044240618505423456248872825597521393564957261041606004454706987978944644129728005540587982321571481413548381251589071459468890948819121023006292105804319208332473499823959882524985324120811768843639294924500467781666073366713198751960913508720530656411097981933156605831180926219778514434
print(str(pow(5,e,n)*c%n)[-25:])

输出结果为：8489769636593649908538102，因此flag为0xGame{8489769636593649908538102}

RSA的同态性是一个很重要的知识点，在可以获得解密服务的服务器上，可以利用RSA的同态性，发送$2^ec,3^ec,…$等结果，获取解密服务，进而获取明文的一些性质，比如$2m$的情况、$3m$的情况等等。比如第四周的ParityOracleBase5就是用到了这个的算法

出这个题的原因，是因为去年的0xGame就是因为先出了ParityOracle，然后出了个SigninRSA，直接导致自己根本就没意识到$2^ec$的解密结果是$2m$。。。

虽然这个题解出来的人挺多，但这个题是为了给下周的ParityOracleBase5做准备用的。。

Predict 1

一个求LCG参数的题目。

根据题目的方法，我们有19次机会可以获得里面的state，然后再进行预测。但实际上，一般获取8组数据，就可以获取$a,b,p$的值（此处保证了$a,p$是素数）。当然为了保险，15组数据也是足够的。

首先，我们假设我们获取的数字为$x_1,x_2,…,x_8$。那么我们可以有：
$$
x_i\equiv ax_{i-1}+b \pmod p
$$
那么化简一下，就是：
$$
x_2\equiv ax_1+b\pmod p \tag1
$$

$$
x_3\equiv ax_2+b\pmod p\tag 2
$$

$$
x_4\equiv ax_3+b \pmod p \tag 3
$$

然后，由$(2)-(1),(3)-(2)$，消去$b$，可以得到：
$$
x_3-x_2\equiv a(x_2-x_1)\pmod p \tag{S1}
$$

$$
x_4-x_3\equiv a(x_3-x_2)\pmod p \tag{S2}
$$

由于在$\mod p$的条件下，除号表示乘上某个数的逆元，因此，我们把$a$提出来，就是
$$
a\equiv \dfrac{x_3-x_2}{x_2-x_1}\equiv \dfrac{x_4-x_3}{x_3-x_2} \pmod p \tag{T}
$$
${(T)}$中消去$a$，去分母，得：
$$
(x_3-x_2)^2\equiv(x_4-x_3)(x_2-x_1) \pmod p \tag{R1’}
$$
去掉同余号也就是
$$
(x_3-x_2)^2-(x_4-x_3)(x_2-x_1) =D_1p \tag{R1}
$$
然后，由此可知：
$$
(x_4-x_3)^2-(x_5-x_4)(x_3-x_2) =D_2p \tag{R2}
$$
因此，我们可以得到多个数据$\text{(R1)(R2)(R3)(R4)(R5)}$，然后计算所有结果得最大公因数就可以得到$p$。(一般7个值求出来的准确度就比较高了)

$p$得到之后，我们根据消去$b$的式子，就可以计算出$a\equiv \dfrac{x_3-x_2}{x_2-x_1} \pmod p$了。求出$a$以后，就可以根据$x_1,x_2$很快地求出$b$。

在整个做题的过程中，可能有人查看了百度的方法，结果到最后预测错了。原因很简单：因为这边只是有$\gcd(D_1p,D_2p)$，虽然$p$是一定的，但$\gcd(D_1,D_2)$的值却不为$1$。有两种办法解决：一是多选取几组数据，求公约数更保险，二是我测了一下，$\gcd(D_1,D_2)$的值实际上并不大（很大概率小于$1000$），因此可以写个$2$到$999$的循环，将$\gcd(D_1p,D_2p)$里面多余的因数除掉即可。

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
from Crypto.Util.number import *
from pwn import *
sh=remote("47.101.38.213",60709)
u,detla=[],[]
for i in range(16):
    sh.recvuntil(b">")
    sh.sendline(b"1")
    sh.recvuntil(b">")
    sh.sendline(b"1")
    numb=sh.recvline(keepends=False)
    numb=numb.split(b"is")[1]
    u.append(int(numb))
for i in range(12):
    detla.append(abs((u[i+2]-u[i+1])*(u[i+2]-u[i+1])-(u[i+3]-u[i+2])*(u[i+1]-u[i])))
p=detla[0]
for i in detla:
    p=GCD(p,i)
print(p)
assert isPrime(p)
a=(u[3]-u[2])*inverse(u[2]-u[1],p)%p
b=(u[1]-a*u[0])%p
print(a,b,p)
x=u[-1]
for i in range(205):
    if i%15==0:
        print(i)
    x=(a*x+b)%p
    sh.recvuntil(b">")
    sh.sendline(b"1")
    sh.recvuntil(b">")
    sh.sendline(str(x).encode())
sh.recvuntil(b"0xGame{")
flag=sh.recvline(keepends=False)
print("0xGame{"+flag.decode())
sh.close()

0xGame{86767788-6000-7608-6777-5454a581d836}

不过最后看了一下做出来的人的WP，有的人问过我，多获取了几组数据，多求了几次最大公约数把题目做出来了。也有人没有意识到这个问题，通过多次连接服务器，最终获取了一组$\gcd(D_1,D_2)=1$的情况，很顺利地解出了$p$。

实际上这里可以给大家扩展一下：任意两个正整数互素的概率是$\dfrac{6}{\pi^2}$，这个数字的倒数也是一个很著名的级数和：
$$
\sum_{i=1}^{+∞}\dfrac{1}{i^2}=\dfrac{\pi^2}{6}
$$

Week 4[Update 11.4]

ParityOracleBase5

RSA的PariyOracle攻击，是在获得了解密服务的情况下，你可以 对服务器发送任意密文，服务器会告诉你解密后明文的最后一位。

由于多数情况下都是二进制位，因此最后一位二进制位就是$0$或$1$。若明文$m$的密文是$c$，这个时候我们发送$2^e c$，解密就可以得到$2m$。很显然，由于$2m$是偶数，$n$是奇数。因此如果服务器返回$0$，说明$2m$没有超过$n$，而如果服务器返回$1$，说明$2m$超过了$n$，由于$2m$是偶数，$n$是奇数，因此这里模$n$使得$2m$减去了一个$n$.。

在获取$2m$的结果后，我们可以发送$4m$的密文 给服务器。那么我们可以根据这个表来判断$m$的取值范围：

$m$范围 第一次返回值 第二次返回值
$4m<n$ $0$ $0$
$n<4m<2n$ $0$ $1$
$2n<4m<3n$ $1$ $0$
$3n<4m<4n$ $1$ $1$

因此，我们发现：我们可以通过二分法逼出$m$的值，如果服务器返回$0$取前半段，返回$1$取后半段。

此时，如果我们把二进制扩展到五进制，很显然，我们就从讨论$2m$变成讨论$5m$，也就是$5^km$模$5$的值。但这里有一个问题：如果我们已知$m$位于$[L,R]$中，$b=\dfrac {R-L} 5$，那对于返回的可能值$0,1,2,3,4$一定是按顺序对应的吗？显然不是。

如果5𝑚在$[0,\frac n 5]$的范围内，那么很显然，服务器会返回0 但如果$5𝑚$在 $[\frac n 5,\frac{2n} 5]$ 中，很显然，真正的明文是$5𝑚 − 𝑛$。因此，这里的返 回值是 $−𝑛 \mod 5$ 的值。因此，1-4对应的区间顺序，与$n \mod 5$的值有关。

$n \mod 5$ $[0,\frac n 5]$ $[\frac n 5,\frac{2n} 5]$ $[\frac {2n} 5,\frac{3n} 5]$ $[\frac {3n} 5,\frac{4n} 5]$ $[\frac {4n} 5,n]$
$1$ $0$ $4$ $3$ $2$ $1$
$2$ $0$ $3$ $1$ $4$ $2$
$3$ $0$ $2$ $4$ $1$ $3$
$4$ $0$ $1$ $2$ $3$ $4$

因此，$n\equiv 4 \pmod 5$的情况是很容易被想到的。可以根据这个表进行讨论， 也可以就认定$n\equiv 4 \pmod 5$的情况，多连几次服务器，也可以拿到flag。 这个是高强度的交互，从题目中n的规模来看，一共要交互1750- 2100次，耗时12分钟左右。

有学弟看到了网上base2的题目，发现最后flag会出现误差。但这道题我们不需要考虑误差。因为flag在文本的中间，这边的误差不会影响到flag。并且，这个题目考虑到万一影响到了的情况，flag没有设置成md5的那种格式，而是在最后做了些手脚。因此flag即使出现3位有问题，也基本上都能猜出来是啥。

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
from Crypto.Util.number import *
from pwn import *
sh = remote("47.101.38.213", 60713)
sh.recvuntil(b"> ")
sh.sendline(b"1")
n, e, c = [sh.recvline(keepends=False) for _ in range(3)]
n, e, c = int(n[2:]), int(e[2:]), int(c[2:])
print(n)
print(e)
print(c)
L, R, Clk = 0, n, 1
judge = n % 5
Table = [[0, 0, 0, 0, 0], [0, 4, 3, 2, 1], [
    0, 3, 1, 4, 2], [0, 2, 4, 1, 3], [0, 1, 2, 3, 4]]
j0, j1, j2, j3, j4 = Table[judge]
print(f"judge={judge}")
while L < R:
    # for i in range(1):
    D = (R-L)//5
    if Clk % 35 == 0:
        print(Clk)
        print(R-L)
    P20, P40, P60, P80 = L+D, L+2*D, L+3*D, L+4*D
    a = c*(pow(5, e*Clk, n)) % n
    sh.recvuntil(b">")
    sh.sendline(b"3")
    sh.recvuntil(b">")
    sh.sendline(str(a).encode())
    Rem = sh.recvline(keepends=False)[-1]-48
    if Rem == j0:
        L, R = L, P20
    elif Rem == j1:
        L, R = P20, P40
    elif Rem == j2:
        L, R = P40, P60
    elif Rem == j3:
        L, R = P60, P80
    elif Rem == j4:
        L, R = P80, R
    else:
        print(b"Error")
        break
    Clk += 1
L = long_to_bytes(L)
L = L.split(b"          ")
print(L[1])
sh.close()

flag:0xGame{31b52022-6076-8067-8848-taijinshouji}

这个题一共有7位新生做出来，tql。

Predict 2

既然上周出了个Predict 1，那就会出个Predict 2。

LFSR，又称线性反馈移位寄存器。它是通过 $𝑦 ≡ \sum_{i=1}^ 𝑛 𝑎_𝑖𝑥_𝑖 \pmod p$ 的形式，获得输出$𝑦$。输出后，将$𝑥_0$去掉，把$y$接在$x$数组的最后，组成新的$x$数组，长度与原来$x$数组一致。整个过程中，$a$数组始终不变。

题目初始有97次获得state的机会，LFSR的长度为45。当你预测到后面600 个state后，就可以获得flag。 根据迭代式，我们可以得到这个规律：
$$
x_{45}\equiv \sum_{i=0}^{44} a_ix_i \pmod p
$$

$$
x_{46}\equiv \sum_{i=0}^{44} a_ix_{i+1} \pmod p
$$

很显然，如果我们把$a$看作未知数，那么就是要解含有$45$个未知数的方程。需要构造$45$个等式。

而在线性代数中，解线性方程组实际上都可以化为矩阵的运算，因此，我们可以构造下面的矩阵：

Predict2

这个矩阵有形如$\vec aM=\vec b$的格式。根据题目来看，很显然方程有唯一解。 所以运用线性代数知识，有$\vec a = \vec bM^{−𝟏}$ 。不过这里的逆矩阵是在模$p$意义 下的逆矩阵。

求逆矩阵可以用Sagemath，也可以根据线性代数 课上讲过的利用增广矩阵法求解逆矩阵，将 $(𝑀| 𝐸)$ 化为$( 𝐸 |𝑀^{-1})$ ，除法变成乘上对应数字的逆元。具体的做法见题目给出的附件2。

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
#Sagemath
from Crypto.Util.number import *
from sage.all import *
from pwn import *
sh = remote("47.101.38.213", 60710)
states = []
for i in range(90):
    sh.recvuntil(b">")
    sh.sendline(b"1")
    sh.recvuntil(b">")
    sh.sendline(b"1500000000")
    sh.recvuntil(b"is")
    states.append(int(sh.recvline(keepends=False)))
M = []
for i in range(45):
    M.append(states[i:i+45])
v = states[45:90]
M = matrix(Zmod(1435756429), M)
v = vector(Zmod(1435756429), v)
mask = v*(M**(-1))
v, mask = list(v), list(mask)
print(mask)
for i in range(601):
    s = 0
    for j in range(45):
        s += v[j]*mask[j]
    s %= 1435756429
    print(i, s)
    v = v[1:]+[s]
    sh.recvuntil(b">")
    sh.sendline(b"1")
    sh.recvuntil(b">")
    sh.sendline(str(s).encode())
sh.interactive()

附件2：求模意义下的逆矩阵代码，用的是增广矩阵法求逆矩阵，时间复杂度$O(n^3)$。

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
from Crypto.Util.number import *


def InvMatrixWithModulus(_matrix, p):
    if (not isPrime(p)) or (len(_matrix) != len(_matrix[0])):
        raise ValueError("matrix must be a square and p must be a prime")
    l = len(_matrix)
    matrix = [[] for _ in range(l)]
    for i in range(l):
        for j in range(l):
            matrix[i].append(_matrix[i][j])
    for i in range(l):
        matrix[i] = matrix[i]+[0 for _ in range(l)]
        matrix[i][l+i] = 1
    for i in range(l):
        inv = inverse(matrix[i][i], p)
        for j in range(i, 2*l):
            matrix[i][j] = matrix[i][j]*inv % p
        for j in range(i+1, l):
            timz = matrix[j][i]
            for k in range(0, 2*l):
                matrix[j][k] = (matrix[j][k]-timz*matrix[i][k]) % p
    for i in range(l):
        assert matrix[i][i] == 1
    for i in range(l-1, -1, -1):
        for j in range(i-1, -1, -1):
            timz = matrix[j][i]
            for k in range(i, 2*l):
                matrix[j][k] = (matrix[j][k]-timz*matrix[i][k]) % p
    J = []
    for i in matrix:
        J.append(i[l:])
    return J

flag:0xGame{87087788-7777-baa5-340d-512844320391}。

这个题目使用了动态flag（上个题目也是），一共有3个学弟做出来了，这个题也算是决定AK的题目吧。在这边放一下他们解出来的flag，作为纪念。

Schen 0xGame{87087788-7777-5b55-3ef6-512844325201}
Louis Youssef 0xGame{87087788-7777-1035-3e02-512844326801}
叶星 0xGame{87087788-7777-1fb5-3aad-512844329565}

Week 5(出题后记)

这次0xGame自己出了11个题目，总体来说还是从易到难的。个人认为与去年相比，第4周可能要比去年难一点，其他3周还是比去年偏简单的。

一共有3人AK了密码学的全部题目，也希望他们能在后面CTF的学习中，无论是否会走密码学方向，能够收获更多的知识吧。

10月12-14日自己迎来了第一个线下赛，在郑州。虽然没有密码学题目，是去白给的，但还是收获了很多，涨了见识，恰了380烂钱。。。 不过自己10月份还是非常忙的一个月，每周都出现了一堆事情，希望自己11月的事情稍微少一点，然后复习复习我的离散、概率论、信安数基和大物，希望自己期末考试这4门课都能考到60分。

还好自己去年6级过了，要是不过的话，今年的事情绝对会忙到我破防。10月第一周迎新，第二周线下，第三周为SAST和SACC招新批卷，第四周安全组授课，11月第一周写任选课论文和大物期中考，还有星盟分享又做了个ppt。。。。

希望自己2年后能够考南邮的研究生吧，以后再社会上混口饭吃不错了。

CTFSeason3
#WriteUp
0xGame2021PartCrypto
http://example.com/2021/10/25/0xGame2021PartCryptoDiv1/
作者
huangx607087
发布于
2021年10月25日
许可协议