-
题目分类：math
-
题目分值：解密消息（150）+ 攻破算法（300）
某同学在某不知名百科网站上看到一个神奇的密码学协议，叫做「不经意传输」（Oblivious transfer）。
于是他按照网站上描述的「1–2 oblivious transfer」自己实现了协议中一方的逻辑，你可以作为另一方与之进行交互。
完全按照百科网站上的算法来实现的协议应该不会有什么问题吧？
点击下载 源代码
除了网页终端，你也可以通过 nc 202.38.93.111 10031 来连接
我之前给 pwnhub 出过一道关于 oblivious transfer 的题目 BabyOT
0CTF/TCTF 2020 Finals 也有一道 Oblivious
再加上这道题，三道题每道题的解法都完全不同。它们都是按照维基百科上面的算法实现的，但问题都在于，m0 和 m1 并不是均匀随机选择的。
我出这道题是因为某同学（就是 114514 那道题的出题人）跟我说，BabyOT 那道题其实 RSA 的 key 每次重新生成也可以做，不过要求字符集不能超过 16 个字符。他很快写好了字符集为连续 16 个字母的简单 demo。但是当我问他能不能把这 16 个字符设定成十六进制的 16 个字符时，我们都没想出来怎么搞。
我最开始以为穷举量太大，无法解出，后来发现其实把 RSA 的 bit 数变小就可以了，RSA 2048 变成 1024，解题需要的穷举量直接开根号。
直接按照 oblivious transfer 的协议实现一下另一方就可以正常获取到两条消息中的一条了。
但是，这里有个坑，就是 m0 可能比 n 大。要么多试几次，要么把解出来的 m0 不断加上 n 尝试。
当然，你也可以直接去做第二问，这样第一问也包含在内了。
题目的缺陷在于，m0 和 m1 都是十六进制编码之后的字符串，每个字符都是在 09 af 这个特定的字符集内的，相比于随机的消息，非常不均匀。
以下的数学公式都是 mod n 意义下的。
仔细思考 1-2 oblivious transfer 的算法，我们可以发现解决这道题的重点：
精心构造 v，可以 k0 和 k1 成比例。如果我们让 k0 = -scale * k1，那么就有 m0' + m1' * scale = (m0 + k0) + (m1 + k1) * scale = m0 + m1 * scale。
如何让 k0 = -scale * k1 呢？我们知道 k0 ^ e = v - x0 和 k1 ^ e = v - x1，代进去把 v 解出来就行了：
v = (x0 + scale ^ e * x1) / (1 + scale ^ e)
只要我们发送这样计算得到的 v，然后拿到 m0' 和 m1' 时计算一下，就可以得到 m0 + m1 * scale 了。
首先我们考虑简单的情形，即，m0 和 m1 每个字符都是 0~15 的范围。
字符串编码成的大整数，可以看作是 256 进制的数，如果每一个字节都是 0~15，意味着高 4 个二进制位都是 0。如果我们取 scale = 16，那么 m0 + m1 * scale 就是把两个数交错拼起来，示意图如下：
m0: 01 02 03 04
m1: 0a 0b 0c 0d
这样的话
m0 : 01 02 03 04
m1 * 16 : a0 b0 c0 d0
m0 + m1 * 16: a1 b2 c3 d4
你看，什么信息都没丢，你可以轻松从中还原出 m0 和 m1。
再考虑复杂一点的情形，m0 和 m1 的字符集都是连续 16 个字符，或者说，更弱的条件，字符集的每个字符 mod 16 正好是 0~15。
此时，虽然 m0 和 m1 交织在了一起，但是我们从 m0 + m1 * scale 的低字节开始，通过 mod 16 就可以找到 m0 的低字节，然后减掉 m0 的低字节，继续 mod 16 找到 m1 的低字节，这样继续下去，就可以还原 m0 和 m1。
这道题中的情况是，m0 和 m1 的字符集 mod 16 并不恰好是 0~15。这样的话，当我们遇到重复的值，我们无法判定它是多种情况中的哪一个。所以，我们需要一些穷举。
其实，scale 也可以不是 16。我通过统计无法分辨的情况出现的概率，找到了题目字符集下比较好的一个 scale：19。
然后，我们拿到 m0 + m1 * scale 后，就可以开始从低字节开始寻找可能的 m0 和 m1 的低字节了，解题脚本需要记住所有的可能情况，然后不断向高字节搜索。
然而，对于我这种用 Python 这样运行速度很慢的语言解题的人来说，穷举量通常会是 2^30 以上的量级，在题目连接的短时间内无法穷举完成。当然，你可以选择不断重试，反正总有机会遇到穷举几分钟之内就找到解的情况。
穷举需要的数量级是一个二项分布（可以看成正态分布）。我的做法是，不断重新连接服务器，每次先计算一下穷举量，蹲到一个穷举量小于 2^24 的情况，分分钟就可以穷举出来。实测重连一些次就可以蹲到一次穷举量足够小的。