春勃

这次 medium 分类题量是最多的，内容方面是最丰富的，两极分化比较严重。 有脑筋急转弯的，有考察 SageMath API 使用的，有 MISC 题目混进来的…… 总之 medium 分类最难的比 tough 还要更难…… Roldy题目描述题目的加密基于 ECB 模式的分组加密，以及基于 pyope 包中的 OPE 加密算法。 与远程终端交互，可以知道 flag 的密文，也能进行任意次输入明文，得到加密结果的操作。 试求 flag。 我的解答首先搜一波 OPE 是什么： https://crypto.stackexchange.com/questions/37375/order-preserving-encryption-ope-and-leakage 简单来说，OPE 就是 Order-Preserving Encryption（保序加密）的缩写。 接着具体看到 pyope 包的页面： https://pypi.org/project/pyope/ 其中有： 1assert cipher.encrypt(1000) < cipher.encrypt(2000) < ...

这次 medium 分类题量是最多的，内容方面是最丰富的，两极分化比较严重。 有脑筋急转弯的，有考察 SageMath API 使用的，有 MISC 题目混进来的…… 总之 medium 分类最难的比 tough 还要更难…… Derik题目描述已知 $O_0, O_1, O_2, O_3$ 的值，以及 $C_0, C_1, C_2, C_3, C_4, C_5, C_6, C_7$ 的值，未知 $e, d, p, q, r$ 的值。 有如下条件： $e, d, p, q, r$ 均为素数 $C_0 p - C_1 q \ge 0$ $C_2 p - C_3 r \ge 0$ $C_4 r - C_5 p \ge 0$ $(C_0 p - C_1 q) ^ e + (C_2 q - C_3 r) ^ e + (C_4 r - C_5 p) ^ e = d (C_0 p - C_1 q) (C_2 q - C_3 r) (C_4 r - C_5 p)$ $C_6 e - C_7 d = O_3$ RSA 中，$N = edpqr$，加密指数为 65537，对 flag 加密得到 $c ...

这次 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$ 构成的集合，就得到 ...

一九九七年 我学会了开汽车 上坡 下坡 轧死了一千多 警察来抓我 我跑到女厕所 女厕所的灯 没 有 开 一脚掉到茅屎坑 和粑粑交朋友 点此欣赏芜湖童谣 这周末，一年一度的 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：设计掉血扣分、耗 ...

回到概览 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 ...

回到概览 跟 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 进行张量计算，所以也没有到很慢。 但是，采样毕竟不是个精确的方法。可能存在没抽到的更优的动作。 解法二用梯度上升法来解这个最优化问题。 最小化就用梯度下降 ...

回到概览 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 是基于值的方法。我们并不学习策略（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: 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 ...