ZK Hack Puzzle 2 题解：如何用小子群攻击求解离散对数
1背景
Pohlig-Hellman 算法
当群的阶具有小的素因子时，可以使用Pohlig-Helman算法高效计算该群中元素的离散对数。
具体来说，给出两个群元素 和 ，其中 的阶为 使得 （ 是 的素因子）。希望计算出 。
如果可以对所有 找到，则可由中国剩余定理高效得到。又由，则。
计算 ，由拉格朗日定理，为阶子群的生成元。
假设足够小，则可遍历，找到满足的。则
椭圆曲线协因子
BLS12-381 曲线由，两条曲线组成：
其中 且为的根。
注意到两个椭圆曲线群的阶都具有小的素因子，直接使用这两个群会遭受上述Pohlig-Hellman算法的攻击，故在生产实践中实际使用的群是上述两群的素数阶子群（素数阶子群的阶为上述分解中最大的素因子）。这是通过给曲线上的每个点乘以协因子实现的。协因子为群阶的所有小素数因子之乘积。
factor(E1.order())
> 3 * 11^2 * 10177^2 * 859267^2 * 52437899^2 * r
cofactor = 3 * 11^2 * 10177^2 * 859267^2 * 52437899^2
hex(cofactor)
> 0x396c8c005555e1568c00aaab0000aaab
2挑战内容
见：https://github.com/kobigurk/zkhack-trusted-setup
给出椭圆曲线点，， 求解（)
注意：原题目背景为Groth'16 zk-SNARKs的Trusted Setup阶段，上述为抽象后的挑战内容。
3题解
G1生成子群
G1 = E(/*coordinates of ts1_0 in rust code*/)
factor(G1.order())
> 3 * 11 * 10177 * 859267 * 52437899 * r
对比该点的阶与上述的阶，发现由生成的子群的阶确实具有小的素因子3,11,10177,859267,52437899。
大素数也为生成的子群的阶的因子中，如果能想办法去除掉 ，则可以使用Pohlig-Hellman算法得到题解。
可以使用和上述乘以协因子同样的方法将椭圆曲线点投影到一个“不安全”的子群中：如果给乘以，那么由生成的子群的阶恰为，即小素数因子的乘积。于是也在该子群之中且。这意味着可以运行Pohlig-Hellman算法得到
s_times_g1 = E(/*coordinates of ts1_1 in rust code*/)
discrete_log(s_times_g1,G1,operation='+')
> 2335387132884273659
G2生成子群
已知的阶为，且cofactor=0x5d543a95414e7f1091d50792876a202cd91de4547085abaa68a205b2e5a7ddfa628f1cb4d9e82ef21537e293a6691ae1616ec6e786f0c70cf1c38e31c7238e5，分解为：
factor(E2_cofactor)
> 13^2 * 23^2 * 2713 * 11953 * 262069 * 402096035359507321594726366720466575392706800671181159425656785868777272553337714697862511267018014931937703598282857976535744623203249
故记，最后的大素数为
和 确实在 阶的子群中，但是不能确定生成了阶的子群（它可能生成更小的子群）。所以需要确定的阶，即需要找到最小的数使得，其中是无穷远点。
通过一次去掉一个的素因子再乘以的方法，可以得到阶为。
因此定义基点为，指数点为
计算如下：
discrete_log(exp, base, 2713 * 11953 * 262069, operation='+')
> 6942769366567
合并
已有 和 且。使用中国剩余定理得到
crt([s_mod_n1, s_mod_nt2], [n1, nt2])
> 62308043734996521086909071585406
得到的有105比特，还不是最终的128比特的。由于，故可在的空间中暴力搜索从而得到。
let (_ts1, _ts2) = puzzle_data();
let n1_times_nt2 = Fr::from_str("128602524809671824928355010578973").unwrap();
let s_tag = Fr::from_str("62308043734996521086909071585406").unwrap();
for k in 0..4000000 {
let s = n1_times_nt2*Fr::from(k) + s_tag;
if _ts1[0].mul(s) == _ts1[1] && _ts2[0].mul(s) == _ts2[1] {
println!("{}", s);
return;
}
}
输出:114939083266787167213538091034071020048，通过测试。