置换魔群.md

置换魔群

吃了不会 Sage 的亏，全都在手撸 Python。

置换群上的 RSA

懂 RSA 和“阶”是个什么意思就行了，并不需要置换群的特殊性质。意外收获是了解到 Python 的 pow 函数现已直接支持求模逆元 ：

secret = cipher ** pow(e, -1, cipher.order())

完整自动化代码请见：置换魔群/autorun1.py

置换群上的 DH

置换群的“标准化”记法提示了一个置换可以被“分解”成若干低阶的“子置换”（非专业术语），整个置换的阶就是这些子置换的阶的最小公倍数。

破 DH 的思路是：把 g 拆成子置换 g_i，然后 y = g ** secret 也可以按 g 的子置换拆成 y_i（显然多次重复置换 g 后，g 中每个子置换的元素不会被换到其他子置换中），这样就考虑在每个子置换 y_i = g_i ** secret_i 上解 secret_i。假定子置换的阶不高（我尝试了几个，最多的也就上千），直接穷举就行了。

最后 secret 就是用中国剩余定理求同余方程组 secret = secret_i mod g_i.order() 的解。

完整自动化代码请见：置换魔群/autorun2.py

置换群上的超大离散对数（没做出来）

第三题思路是有的，要想办法构造两个 g，使得 g_1 * g_2 的阶非常大，大到能唯一确定 secret，然后就跟第二题一样了。但不知道怎么构造 g。

最后一天做这个题，没时间了，写了个粗糙的贪心，从 2 开始挨个取质数划分子置换。但得到的 g_1 * g_2 的阶离 upper bound 还差好几个数量级。

并不能做出来的代码在：置换魔群/autorun3.py