坊间传言 Jeff Dean 在面试 Google 的时候，曾根据公钥心算出 Google 私钥。当然大多数人都把这事当作笑话对待，但只有 Z 同学知道，这是真的。
根据国家计生委未公开的大数据统计，平均每 66666666 位少年少女中就有一位这样的天才，心算能力极为恐怖，可以在线性复杂度内分解任意长度的大整数，因为时间瓶颈主要在于把结果用笔写出来。中国科学技术大学少年班学院成立的主要目的，其实就是为了网罗这样的神童。每当这样的一位天才出现，国家就会将其秘密保护起来，送到国家高性能计算中心作为 ALU，而其同学却只是被告知出国。实际上，曾排 TOP500 榜单第一名的超算“神威-太湖之光”的主要算力其实是由两位这样的天才少年提供，剩余的 10649600 个核心则负责将通用的计算程序规约到大整数分解，以及处理输入输出等等外围工作。
后来，少年班学院的“冰球”，Z 同学的一个好朋友，在离开科大去北大做相关秘密研究之际，告诉了 Z 同学这个消息。Z 同学马上意识到 RSA 实际上并不安全，惊慌失措，立刻删掉了自己所有服务器上面的 RSA 公钥，大喊：“不能再公开 RSA 中的 n 了！我们必须立即以一种新的方式使用 RSA！”。在连续几个通宵的苦思冥想后，Z 同学写了一段 python 代码，用他改进过的 RSA 算法加密了一段消息。新的算法并没有透露 n，只给定了两个大整数：(p*q)^(p+q) 和 (p*q)^(p-q)，其中 ^ 是按位异或运算。
“终于能睡个安稳觉了”，Z 同学如是想。在上床之前，Z 同学告诉你，除非这个新的算法有漏洞，否则不要打扰他的休眠。而喜欢恶作剧的你，能找到正当理由叫醒正在熟睡的 Z 同学吗？
我出这道题的灵感来自于某个国际比赛的一道 RSA 题目，那道题目的解法也是逐位爆破，具体的题目找不到了，欢迎知道的同学告诉我是哪题。
题目代码很简单，除去空行，连 10 行都不到
import sympy
p = sympy.randprime(2 ** 1023, 2 ** 1024)
q = sympy.randprime(2 ** 1023, 2 ** 1024)
a = (p * q) ^ (p + q)
b = (p * q) ^ (p - q)
flag = open('flag.txt', 'rb').read()
m = int.from_bytes(flag, 'big')
print(a, b, pow(m, 65537, p * q))代码中随机生成两个大素数 p 和 q，然后计算出 a = (p * q) ^ (p + q) 和 b = (p * q) ^ (p - q)，其中 ^ 是按位异或运算。然后，读取 flag 文件的内容并且转换成一个大整数 m，再输出 a、b 和用参数 n = p * q, e = 65537 的 RSA 加密后的 flag。
要解密 flag，我们只能求出 p 和 q，然后算出 RSA 的私钥。可是，因为异或运算的存在，我们从 a 和 b 很难用数学推导的方法来解出 p 和 q。
根据题目描述
根据国家计生委未公开的大数据统计，平均每 66666666 位少年少女中就有一位这样的天才，心算能力极为恐怖，可以在线性复杂度内分解任意长度的大整数，因为时间瓶颈主要在于把结果用笔写出来。中国科学技术大学少年班学院成立的主要目的，其实就是为了网罗这样的神童。
我们去少年班学院找出一位这样的天才，然后让他/她心算求解即可得到 flag。
我们定义 f1(x, y) = (x * y) ^ (x + y) 和 f2(x, y) = (x * y) ^ (x - y)，我们发现这两个函数都有一个共同的性质，就是函数值的最低 n 个二进制位只和 x、y 的最低 n 个二进制位有关。也就是说，我们可以用 a 和 b 的最低 n 位来判断 p 和 q 的最低 n 位是否可能正确。如果它们的最低 n 位满足 f1 和 f2 函数，那么它们就是 p 和 q 低位的候选答案；如果不满足，它们就根本不可能是真正 p 和 q 的低位。
所以我们可以从一个二进制位（n=1）开始，每次增加一位。每增加一位时，我们把原来满足条件的 p 和 q 低位的每种可能情况分别在前面加上 0 或 1，这样每种情况就变成了 4 种新的情况，然后对所有新的情况用 f1 和 f2 函数提供的约束条件进行过滤，只保留满足条件的情况。当跑到 1024 位的时候，就只会剩下真正满足条件的 p 和 q 了。
然后，我们根据 RSA 的原理，在 mod (p-1)*(q-1) 的意义下对 e 求逆元，得到私钥 d，计算 pow(c, d, p * q) 即可得到 flag 的大整数表示。
这个问题的巧妙之处在于，每增加一位，候选答案的数量会变成 4 倍，但同时根据数学期望，正好会有 1/4 的候选答案被过滤后保留下来，所以程序的运行时间不会指数爆炸。
求解脚本如下：
#!/usr/bin/env python3
import gmpy
a, b, c = [int(s) for s in open('output.txt').read().split()]
f1 = lambda p, q: (p * q) ^ (p + q)
f2 = lambda p, q: (p * q) ^ (p - q)
candidates = {(0, 0)}
for m in range(1025):
print(m, len(candidates))
candidates_ = set()
mask = (2 << m) - 1
for x, y in candidates:
if f1(x, y) == a and f2(x, y) == b:
p, q = x, y
d = gmpy.invert(65537, (p - 1) * (q - 1))
m = pow(c, d, p * q)
print(bytes.fromhex(hex(m)[2:]))
exit()
for bx in range(2):
for by in range(2):
xx = x + (bx << m)
yy = y + (by << m)
if f1(xx, yy) & mask != a & mask:
continue
if f2(xx, yy) & mask != b & mask:
continue
candidates_.add((xx, yy))
candidates = candidates_最后吐槽一下 github 的 markdown 不能加 latex 数学公式。
题目中的 p 和 q 真的是用随机数生成出来的吗？Z 同学会不会在里面隐藏了什么信息？不要问我，我不知道