0xGameDiv4

WriteUp
CTFSeason1
发布日期:   2020-10-29

0xGame Div 4 题解

About

4周过去，7172分。还没第一周的某些人高，我果然是个fw。不过自己的CTF学习进入了第二阶段，很快就要进入数论了。 然而最近又在参加学校ACM菜鸟赛（（作为一个当年距离1=只差15分的2=蒟蒻，我该怎么办）

Crypto

1. littleTrick

一道并不算很难得题目，但我这个fw还是用了4个小时才做出来，wtcl

首先先看一下题目的主要代码：

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
def handle(self):
       self.send(BANNER)
       if not self.proof_of_work():
           return
       assert len(flag) == 44
       p, q = getPrime(1024), getPrime(1024)
       self.m = flag.encode()
       self.n = p*q
       self.e = 65537
       self.d = inverse(self.e,(p-1)*(q-1))

       self.send(b"n : " + hex(self.n)[2:].encode())
       while True:
           self.send(MENU, newline=False)
           choice = self.recv()
           if choice == b"1":
               mask = self.recvhex(prompt=b"Your mask (in hex): ")
               mask = long_to_bytes(pow(mask,self.d,self.n))
               if len(mask) >= 44:
                   break
               gift = self.m[:-len(mask)] + mask
               gift = pow(bytes_to_long(gift),self.e,self.n)
               self.send(hex(gift)[2:].encode())
               continue
           self.request.close()
           break

题目一开始，会给出$n$的值(此处相关的题目代码省略了)，$e=65537$为固定值

从代码中我们可以知道：这是一个很明显的RSA题目，flag的长度是$44$位，每当我们输入一个$16$进制数，系统会用解密函数对这个数字进行解密，如果超过flag的长度$44$位直接推出交互。否则将答案的最后替换为解密结果之后加密计算$c’$

很显然，对于每次交互的内容，我们必须慎重考虑。 根据通识可知：flag的最后一位一定是},，其ASCII码为$125$。所以我们可以先对服务器发送数值$125$通过加密后的数字（以$16$进制格式）发送给服务器，这样我们就得到了正确的$c$值了

得到正确的$c$值之后，我们可以每次枚举字符串的前一位，加密后发送给服务器，如果服务器返回的值与刚才得到的正确的$c$值完全一致，那么我们就认为这一位是正确的（因为这样相当于原密文没有被替换）。枚举结束我们就得到了flag

下面附上低清有码的脚本代码，别看因为我可菜了

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
from pwn import *
import time
from hashlib import sha256
from Crypto.Util.number import *
def getyanzhengma(s16len,s64len):
	LTSNMS="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOP\mathrm{QR}STUVWXYZ0123456789"
	assert len(s16len)==16 and len(s64len)==64
	for i1 in LTSNMS:
		for i2 in LTSNMS:
			for i3 in LTSNMS:
				for i4 in LTSNMS:
					if sha256((i1+i2+i3+i4+s16len).encode()).hexdigest()==s64len:
						return i1+i2+i3+i4
def incode(m,p):
	return hex(pow(m,65537,p))[2:]
##------main below------#
sh=remote("49.235.239.97",10004)
while(True):
	str1=sh.recvline(keepends=False)
	if(str1[0:6]=="sha256"):
		break
flag="}"
yanzhengma=(getyanzhengma(str1[12:28],str1[33:97]))
sh.send(yanzhengma)
print("[NOTE]SENT YANZHENGMA")
str1=sh.recvline(keepends=False)
n=int(str1[18:],16) 
for i in range(3):
	str1=sh.recvline(keepends=False)
str1=sh.recv(numb=4,timeout=20000)
sh.send(b"1")
str1=sh.recv(numb=40,timeout=20000)
sh.send(incode(ord('}'),n))
print("sent numbers")
str1=sh.recvline(keepends=False)
C=int(str1,16)
cnt=42
while cnt!=-1:
	#print(cnt)
	konst=b"1234567890abcdefxGame{-}"
	for j in konst:
		tmp=str(j)
		for i in range(3):
			str1=sh.recvline(keepends=False)
		str1=sh.recv(numb=4,timeout=20000)
		sh.send(b"1")
		str1=sh.recv(numb=44,timeout=20000)
		sh.send(incode(bytes_to_long(tmp+flag),n))
		str1=sh.recvline(keepends=False)
		C1=int(str1,16)
		if C1==C:
			flag=tmp+flag
			print(flag)
			cnt=cnt-1
			break
print(flag)

2.ElGamal

密码学压轴题= =，虽然不是远程题目但是最难的。代码量不大但思维量很大，因为这道题与数论联系极其紧密。虽然我以前打过OI，但学得不深，更别谈既有OI基础又有数学竞赛基础的Hermesdalao相比了。所以我在得到1..hint之后，才做了出来。由于这题很难所以WP(自己的学习笔记)要认真地写一下。
我们约定一下:以下凡无特殊说明，所有的数字均为整数，所有的除法均为整除

Note 1:ElGamal基本加密方法

step1：选择一个大质数$p$，和集合$Z_p^*$上的一个生成元$g$

step2：选择一个数字$k$在$[0,p-2]$内，计算$y=g^k \mod p$，也就是$g^k\equiv y \mod p$

step3：随机选取$r∈Z_{p-1}$，加密函数为$E(k,x,r)=(y_1,y_2)$ 其中$y_1\equiv g^r \mod p$，$y_2\equiv my^r \mod p$

其中：$k$是私钥，$p,g,y$是公钥

Note 2:ElGamal基本解密方法

解密函数：$D(y_1,y_2)=y_2(y_1^k) \mod p \equiv m(g^k)^r(g^{kr})^{-1}\equiv m \mod p$

很显然，ElGamal是一个基于离散对数的加密算法，想求出私钥$k$基本上是不可能的，目前最有效爆破离散对数的算法的复杂度为$O(\sqrt{p})$，但对于高达$512$位二进制数的大质数$p$，这个算法复杂度是非常高的。

根据西电大佬shallow在MOECTF的《Crypto入门指北》中所说：CTF中所有的密码学题目都是通过有漏洞的加密方式实现的。重点就是要从中找出漏洞，并且在没有密钥的情况下恢复明文。

所以，我们回归一下题目实现算法的源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *
from Crypto.PublicKey import ElGamal
from random import randint
from secret import flag
def notSquare(p):
    r = randint(2, p-2)
    while pow(r, (p-1)//2, p) == 1:
        r = randint(2, p-2)
    return r
def Square(p):
    return pow(randint(2, p-2), 2, p)
flag = bin(bytes_to_long(flag.encode()))[2:]
key = ElGamal.generate(512, Random.new().read)
f = open("data", "w")
for i in flag:
    plaintexts = {"0": Square(int(key.p)), "1": notSquare(int(key.p))}
    c = key._encrypt(plaintexts[i], randint(1, int(key.p)-2))
    f.writelines(hex(c[0])[2:]+", "+hex(c[1])[2:]+"\n")
f.close()
print("y =", key.y)
print("g =", key.g)
print("p =", key.p)

密文先被转化成了二进制，然后根据每一位是$0$还是$1$，用一个数字加密了，其中当这一位为$0$时选取的数字是个平方数对$p$取模的值，这一位是$1$时选取的数字不是一个平方数对$p$取模的值。然后将这个数字记为中间密文$x$，再产生一个随机数$r$作为指数将其加密。

既然这里涉及到了平方，而一个完全平方数对某个数取模一定会有某些特殊的性质，在hint的指引下，我们来看看什么叫做模$p$平方剩余和二次互反律：注:本题解/博客只讲解归纳法得到的性质，不讲解证明是因为我也不会，实际上是因为懒

Note 3:模$p$平方剩余

我们都知道：$3^2 \equiv 2 \mod 7$，所以$∃ x\in Z_7^*$，使得$x^2\equiv 2 \mod 7$有解，此时我们称$2$是模$7$的二次剩余

性质1：很显然在普通的一元二次方程中，$x^2=a^2$有两解$a$和$-a$，所以解方程$x^2\equiv 2 \mod 7$也有两解为$3$和$-3$（也就是$4$，因为$-3 \equiv 4 \mod7$）。由此可见$x^2\equiv (p-x)^2 \mod p$(直接展开即可证明其正确性)

我们可以继续看：在$Z_7^*$里面的$6$个数的平方分别为$1,4,2,2,4,1$。所以$1,2,4$是模$7$意义下的二次剩余，$3,5,6$不是模$7$的二次剩余

*性质2：可以证明，对于任何质数$p$，在$Z_p^$中，总是有一半的数是模$p$的二次剩余，也总有一半的数为模$p$的二次非剩余**

我们记$\mathrm{\mathrm{QR}}$为二次剩余，$\mathrm{\mathrm{NR}}$为二次非剩余，在模$7$意义下，$\mathrm{QR}={1,2,4},\mathrm{NR}={3,5,6}$。观察下列等式，我们可以得到性质3

（1）$2×4\equiv 1 \mod 7$ (2)$3×4\equiv 5 \mod 7$ (3)$3×5\equiv 1 \mod 7$

性质3：$\mathrm{QR}×\mathrm{QR}=\mathrm{QR}$,$\mathrm{QR}×\mathrm{NR}=\mathrm{NR}$,$\mathrm{NR}×\mathrm{NR}=\mathrm{QR}$

所以，我们可以类比$1$和$-1$两个数，将$\mathrm{\mathrm{QR}}$理解成$1$，$\mathrm{\mathrm{NR}}$理解成$-1$，

所以我们引入勒让德符号$(\frac{a}{b})$，意义为$a$是否为模$b$意义下的二次剩余，如果是，该值为$1$，如果不是，该值为$-1$

例如：$(\frac{4}{7})=1,(\frac{3}{7})=-1$

性质4：根据性质2，3中的结论，我们可以推出以下公式$(\frac{ab}{p})=(\frac{a}{p})(\frac{b}{p})$

由于任何一个数都可以写成几个质数乘方的乘积，而多数情况下我们只研究$a,b$均为奇数的情况，所以我们需要进一步研究几个性质

Note 4:两个特殊的数：$-1$和$2$

观察以下式子，我们可以得出性质5和性质6

$(\frac{-1}{3})=-1$ ，$(\frac{-1}{5})=1$，$(\frac{-1}{7})=-1$，$(\frac{-1}{11})=-1$ $(\frac{-1}{13})=1$ $(\frac{-1}{17})=1$，$(\frac{-1}{19})=-1$

$(\frac{2}{3})=-1$，$(\frac{2}{5})=-1$，$(\frac{2}{7})=1$，$(\frac{2}{11})=-1$，$(\frac{2}{13})=-1$，$(\frac{2}{17})=1$，$(\frac{2}{19})=-1$

性质5：对于质数$p$，若$p\equiv 1 \mod 4$,则$(\frac{-1}{p})=1$。若$p\equiv 3\mod 4$,则$(\frac{-1}{p})=-1$ (在模$4$意义下，$3$可以理解成$-1$)

性质6：对于质数$p$，若$p\equiv 1 \mod 8$,或者$p\equiv 7 \mod 8$，有$(\frac{-1}{p})=1$。若$p\equiv 3\mod 8$或者$p\equiv 5 \mod 8$,则$(\frac{-1}{p})=-1$

Note 5：二次互反律

性质4可以进行推广到多个整数相乘，可以验证$(\frac{70}{41})=(\frac{2}{41})(\frac{5}{41})(\frac{7}{41})$。所以我们在面对较大整数的时候，可以使用因式分解。然而面对特别大的整数的时候，你想想这真的可行?RSA怎么解释？

类比欧几里得算法，由于$\gcd(a,b)=\gcd(b,a)$，所以我们能不能尝试交换一下符号中的分子和分母(姑且这么说吧，实际上是很不规范的说法)，看看里面的性质呢？

此处不多介绍，自己找几个数字归纳归纳吧，直接放上结果,$m,k\in Z$

**性质7：$(\frac{4k+1}{4m+1})=(\frac{4m+1}{4k+1})$ ， $(\frac{4k+3}{4m+1})=(\frac{4m+1}{4k+3})$ ， $(\frac{4k+3}{4m+3})=-(\frac{4m+3}{4k+3})$ **

也就是说，两个数字如果都模$4$等于$3$时，交换分子分母要变号，否则可以直接交换,此处这里的两个奇数可以无所谓是质数还是合数，只要是奇数就行了,如果为偶数，分解出所有的$2$因子

举个例子，假如我们要计算$(\frac{37603}{48611})$，我们可以这样做：

$(\frac{37603}{48611})=-(\frac{48611}{37603})=-(\frac{11008}{37603})=-(\frac{2^8×43}{37603})=-(\frac{43}{37603})=(\frac{37603}{43})=(\frac{21}{43})=(\frac{43}{21})=(\frac{1}{21})=1$

约定$(\frac{1}{p})\equiv 1$

讲了这么多性质，我们可以得到这样的判断代码：很短，但是技术含量非常高

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def isqr(x,p):
    if p==1 or x==1:
        return 1
    sgn=1
    while x%2==0:
        x=x//2
        if p%8==3 or p%8==5:
            sgn=-sgn
    if x<p:
        _tmp=p
        p=x
        x=_tmp
        if x%4==3 and p%4==3 :
            sgn=-sgn
    return sgn*isqr(x%p,p)

我们发现：这道题的$y$和$g$都是$p$的二次剩余！根据$y_1\equiv g^r \mod p$，$y_2\equiv my^r \mod p$，$D(y_1,y_2)=y_2(y_1^k)$和性质 3 可知：这里的$m$就是明文，所以我们只要判断一下isqr(y1,p)*isqr(y2,p)的值是$1$还是$-1$，就可以知道明文是否为二次剩余值，然后就可以判断那一位是$0$还是$1$了。

下面放上所有的代码，我们发现给出来了$350$组数字，可以判断最前面缺了$2$位$00$,flag一共是$44$位。

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
from given import g,p,y
from c0s import c0
from c1s import c1
def isqr(x,p):
    if p==1 or x==1:
        return 1
    sgn=1
    while x%2==0:
        x=x//2
        if p%8==3 or p%8==5:
            sgn=-sgn
    if x<p:
        _tmp=p
        p=x
        x=_tmp
        if x%4==3 and p%4==3 :
            sgn=-sgn
    return sgn*isqr(x%p,p)
s=""
for i in range(350):
    a=isqr(c0[i],p)*isqr(c1[i],p)
    if a==1:
        s+="0"
    elif a==-1:
        s+="1"
s="00"+s
t=""
for i in range(44):
    t+=chr(int(s[8*i:8*i+8],2))
print(t)

Note 6：解出题目之后的一些思考：

这道题$y$是$p$二次剩余,$g$也是二次剩余，所以这道题有很多性质可以利用。试想一下，假如$y$不是$p$的二次剩余又会是怎样一种情况呢？

在Am473ur师傅的启发下，我得出了这样的结论：

当$y$不是$p$的二次剩余时，说明$g$必定不是$p$的二次剩余，根据$g^k\equiv y \mod p$可知，这里的$k$必定是一个奇数。

所以，根据之前的加密函数$D(y_1,y_2)=y_2(y_1^k) \mod p \equiv m(g^k)^r(g^{kr})^{-1}\equiv m \mod p$，简单思考，我可以得到这样的结果：

$y=\mathrm{NR}$时：

若$y_1=\mathrm{NR},y_2=\mathrm{NR}\Rightarrow m=\mathrm{QR}$

若$y_1=\mathrm{NR},y_2=\mathrm{QR}\Rightarrow m=\mathrm{NR}$

若$y_1=\mathrm{QR},y_2=\mathrm{NR}\Rightarrow m=\mathrm{NR}$

若$y_1=\mathrm{QR},y_2=\mathrm{QR}\Rightarrow m=\mathrm{QR}$

所以，无论$y$是何值，只要求出$(\frac{y_1}{p})(\frac{y_2}{p})$的值，这就是$(\frac m p)$的勒让德符号了。

目前，自己的《深入浅出密码学》还剩下第5、10、11、12、13五章没来得及看，这五章可以快速地浏览一遍各种新的加密算法，CTFWIKI上也有很多有用的资源值得被我利用，预计11月10日大概能够把这本书结束（11月的SET4和CET4压力还是有点大的，虽然学长们告诉我SET4和CET4很简单，不过我还是希望SET4能够拿到B，CET4考到470分以上），并且后面还要去ACM那边玩玩。

当《深入浅出密码学》看完之后，就得开始学习数学知识了，前者告诉你一些基本加密算法，后面就要找各类算法给出的性质，这样才能找到漏洞~解决问题

huangx607087学习CTF第1阶段，结束。第2阶段，开始

文章作者: huangx607087
文章链接: http://example.com/2020/10/29/0xGameDiv4/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 huangx607087 !
WriteUp
赏
  目录