CryptoCTF 2023 easy分类 团队解题writeup
这次 easy 分类偏简单,
不过由于配合得不是很好,所以在实战中会有部分题目卡壳的情况
不过还好能有其他人也帮忙看一看,所以马上就能够解围
Did it!题目描述记 $n = 127$,$N=\{0, 1, 2, \ldots, n-1\}$,有随机的未知 $K \subseteq N$,且 $|K| \le 20$。
有至多 12 次的机会,输入一个集合 $A \subseteq N$,且 $|A| \le 20$,返回结果
\{x_0^2 \bmod n + r_0, x_1^2 \bmod n + r_1, \ldots\}对于所有 ${x_i \in A - K}$
其中 $r_i \in \{0, 1\}$ 为一个关于 $x_i$ 的随机数。
如果输入的 $A = K$,则得到 flag。
我的解答也就是说,有至多 11 次的机会去得到结果,然后就要猜出 $K$ 来。
因为 $n$ 是素数,所以对于结果中的每一组 $x_i^2 \bmod n + r_i$,都可以枚举 $r_i$,通过开平方求得可能的 $x_i$。然后再用 $A$ 减去这些 $x_i$ 构成的集合,就得到 ...
CryptoCTF 2023 战果速报
一九九七年
我学会了开汽车
上坡 下坡
轧死了一千多
警察来抓我
我跑到女厕所
女厕所的灯
没 有 开
一脚掉到茅屎坑
和粑粑交朋友
点此欣赏芜湖童谣
这周末,一年一度的 Crypto CTF 如期举行。在炎炎夏季,穿上发病棉袄,和队友们一起参加周五晚 22: 00 开始的 Crypto CTF,并 AK 了此次比赛。老规矩,先鸣谢下队友:
沛公 @peigong
石卡库 @sh1kaku
苏氨酸 @苏氨酸
To1in @To1in
V @Vanish
等风 @等风
Xenny @Xenny
Tover @Tover.
这波配合得不错
然后放个总榜
这次的题目总体来说都偏简(luan)单(gao),最难搞的反而是偏 misc 的几道题。所以说手速,或者是出 idea 的速度是最关键的。因为我们队伍还是贯彻一个养生 CTF,所以说基本上没搞得很晚就先歇逼了一阵,痛失前五。
之后更 writeup,下方为 writeup 传送门:
easy 分类
medium 分类之一
medium 分类之二
medium 分类之三
medium 分类之四
hard 分类之一
har ...
李宏毅强化学习个人笔记 - 其他姿势
回到概览
Sparse Reward实际上,用强化学习的算法去学 agent 的时候,多数情况下,agent 都是没办法得到奖励的。经常不获得奖励对 agent 的训练来说非常困难。
不管 actor 做了什么事情,得到的奖励都是 0,所以到最后什么都不会学到。
(譬如训练一个机械臂去开门,因为绝大多数情况下机械臂都在去伸手,在最后把门打开了才能获得一个正的奖励)
Reward Shaping环境有一个固定的奖励。为了让 agent 学的东西是我们想要的样子,我们去刻意设计一些奖励去引导 agent。
如上图所示,在小鹏与的 Q 函数中
对于玩的认知是,当前可以获得一个正的奖励,长时间后获得一个负的奖励
相反地,对于学习的认知是,当前可以获得一个负的奖励,长时间后获得一个正的奖励
假设小鹏与的衰减系数设得比较小的话,那么就总会关注短期奖励,从而会去玩,而不是学习
这个时候,就人为地“给一个棒棒糖”:在采取学习这个动作的时候,将短期奖励也“改”为正的奖励,虽然这个奖励不是环境真正的奖励
Facebook 训练去玩 FPS 游戏 VizDoom 的 agent:设计掉血扣分、耗 ...
李宏毅强化学习个人笔记 - Actor-Critic
回到概览
A3C: Asynchronous Advantage Actor-Critic
A2C: Advantage Actor-Critic
复习 policy gradient之前用 policy gradient 去学习 actor 的时候,都是看奖励函数的输出,来决定 actor 要怎么更新,才能得到最大的奖励。
但是因为互动的过程中有非常大的随机性,所以直接根据互动的过程学可能没有办法学得很好。
\nabla \bar{R}_{\theta} \approx \frac{1}{N} \sum_{n=1}^{N} \sum_{t=1}^{T_n} \left( \sum_{t'=t}^{T_n} \gamma^{t'-t} r_{t'}^n - b \right) \nabla \log p_{\theta} (a_t^n | s_t^n)从 $t$ 到 $T_n$ 的奖励加起来,乘上一个随时间减少的衰减因子,再减去一个 bias(baseline)。
可以记 $G_{t}^n = \sum_{t’=t}^{T_n} \gamma^{t’-t} r_{t’}^n$,$G ...
李宏毅强化学习个人笔记 - 对于连续动作的 Q-learning
回到概览
跟 policy gradient 比较起来,Q-learning 比较稳定(policy gradient 玩不起来什么游戏)
Q-learning 一个比较好训练的理由是:只要你找得到一个比较好的 Q 函数,那么你就有一个比较好的策略;也就是说如果你能恰当估计 Q 函数(其实比较容易,就是一个回归问题,只需要看到 loss 有无下降就能看出模型学得好不好),你就能更新你的策略。
Q-learning 最大的一个问题就是:比较难处理连续动作的情形。
a = \arg \max_{a} Q(s, a)假设现在动作 $a$ 是一个 连续向量,首先就不能通过枚举所有的 $a$ 去求 argmax。
解法一对于连续的动作 $a$,对其抽样:抽样出一个动作的集合 $\{a_1, a_2, \ldots, a_N\}$,看看哪个动作能得到最大的 Q 值。
在实际的操作上,可以抽样完后都丢到 Q 函数里面算。因为实际都在用 GPU 进行张量计算,所以也没有到很慢。
但是,采样毕竟不是个精确的方法。可能存在没抽到的更优的动作。
解法二用梯度上升法来解这个最优化问题。
最小化就用梯度下降 ...
李宏毅强化学习个人笔记 - Q-learning 在训练时的一些技巧
回到概览
Double DQNDouble DQN 提出的动机:在实际的 Q-learning 中,Q 值是经常被高估的。
总体来说,DQN 的 Q 值随着训练的进行逐步上升。Q 函数依赖于策略,在学习的过程中,策略会变得越来越强,Q 值就会越来越大。
实际值:训练结束后,再和环境互动,得到的真实奖励。(互动多次取期望)
Double DQN 能让估测值跟实际值更接近,且实际值(真正的累计期望)比原来的 DQN 要更大(模型更强)。
为什么 DQN 中的 Q 值老是被高估? 注意到学习时回归问题的形式:
Q(s_t, a_t) \longleftrightarrow r_t + \max_{a}{Q(s_{t+1}, a)}目标值很容易一不小心就被设太高:在算目标值的时候,看哪一个 $a$ 能得到最大的 $Q$ 值,就把它加上去。假设现在有某个动作 $a$,它得到的 $Q$ 值是被高估的。那么,在回归的时候,总是会选这个被高估的值来作为目标。如下图,本来大家的真实 Q 值都是差不多的,绿色部分表示被高估,那么总会采取被高估的动作对应的 Q 值作为回归目标。
这样,回归训练出的的 ...
李宏毅强化学习个人笔记 - Q-learning 简介
回到概览
Q-learning 是基于值的方法。我们并不学习策略(Actor),而是学习 Critic。Critic 不直接采取行为,而是评价现在的行为有多好。
假设现在有一个 actor $\pi$,critic 的工作就是评价这个 actor $\pi$ 做得有多好。
譬如这个 critic 可以做成是跟状态有关的函数:$V^{\pi}(s)$。它的含义为使用 actor $\pi$ 时,到了状态 $s$ 之后,可获得的 期望累积奖励。
例如上图,剩下的怪不多了的时候,$V^{\pi}(s)$ 就会比较小;反之,剩下的怪多的时候,$V^{\pi}(s)$ 就会比较大。
这里注意:critic 是必须要绑定一个 actor 的。critic 没办法凭空去评估一个状态的好坏;它评估的东西是给定一个状态,假设接下来跟环境互动的 actor 是 $\pi$,那么会得到多少奖励。因为就算给同一个状态,给定不同的 $\pi$,得到的奖励也会不一样的。(譬如很叼的玩家会在绝境秀操作,很捞的玩家就只会是个呆头鹅)
所以 critic 的取值跟状态和 actor 都有关。critic 是用来衡 ...
李宏毅强化学习个人笔记 - PPO
回到概览
PPO: Proximal Policy Optimization,该算法为 OpenAI 的默认强化学习算法。
复习:将神经网络作为 actor
神经网络擅长拟合函数
网络输入:机器的观测表示成向量或矩阵;
网络输出:每个动作对应输出层的一个神经元;
$p(s_{t+1}|s_t, a_t)$ 不能控制,由环境来决定,我们只能控制 $p_{\theta}(a_t|s_t)$。
任务是要最大化期望累积奖励 $\bar{R}_{\theta}$
\bar{R}_{\theta}=\sum_{\tau}R(\tau) p_{\theta}(\tau)=E_{\tau \sim p_{\theta}(\tau)}[R(\tau)](注意到 $R_{\theta}$ 是一个随机变量)
也就是说,在 $p_{\theta}(\tau)$ 这个分布里面采样轨迹 $\tau$,计算 $R(\tau)$ 的期望值。
然后 $R(\tau)$ 这一项不需要可微。上一次讲到策略梯度(Policy Gradient)可以推出:
\begin{align*}\nabla \bar{R}_{\t ...
李宏毅强化学习个人笔记 - 基于值的方法(学习critic)
回到概览
这里我们不学习 actor,也就是不学习怎么做事,而是学习一个 critic。
critic 的性质
critic 本身不决定动作;
给定 actor,critic 可以评估 actor 的好坏;
实际上,可以从 critic 里面得到一个 actor,这就是 Q-learning。
critic 实际上就是一个评估 actor $\pi$ 的函数 $V^\pi$
这个函数可以是一个神经网络
critic 的形式关于状态 $V^\pi(s)$ 当 actor 使用 $\pi$ 的时候,在观测到状态 $s$ 后获得的期望累积奖励。
如上图:
左边的状态,还剩很多飞机可以打,所以 $V^\pi(s)$ 较大;
右边的状态,较少飞机可以打,而且飞机渐渐靠下了,所以 $V^\pi(s)$ 较小。
对于不同的 actor $\pi$,给出一样的状态,可能给出的 critic $V^\pi(s)$ 也会不同。
譬如棋魂中的例子,之前藤原佐为建议进藤光下小飞,因为之前进藤光比较弱,后续变化较简单,更易驾驭;
之后变强了,就能够下变化更复杂的大飞;
也就是说,critic ...
李宏毅强化学习个人笔记 - 基于策略的方法(学习actor)
回到概览
基于策略的方法,也就是学习 actor。换言之,也就是学习一个策略函数 $\pi$:该函数输入观测,输出动作。
将神经网络作为 actor
神经网络擅长拟合函数
网络输入:机器的观测表示成向量或矩阵;
网络输出:每个动作对应输出层的一个神经元;
神经网络相较于查表的作为 actor 的好处
有“采样”的步骤,可以带来更多变的决策。譬如猜拳,会随机出锤子剪刀布。
譬如上面的打飞机,无法穷举所有的像素值,这种情况下建立表不现实。
神经网络泛化性好,可以举一反三。就算有些画面机器完全没有看过,也能够得到较好的结果(动作)。
决定 actor 的好坏回顾监督学习:用 loss 来刻画所学到函数的质量。
求网络参数 $\theta’$ 使得能够最小化总误差 $L$
或者说,使得预测分布与目标(target)越近越好
给定具有网络参数 $\theta$ 的 actor:$\pi_{\theta}(s)$,用该 actor 来玩游戏:
每一步可以记为三元组:(观测, 动作, 奖励)
$(s_1, a_1, r_1) \to (s_2, a_2, r_2) \to \ ...