题解作者：tl2cents
出题人、验题人、文案设计等：见 Hackergame 2022 幕后工作人员。
-
题目分类：math
-
题目分值：置换群上的 RSA（200）+ 置换群上的 DH（200）+ 置换群上的超大离散对数（300）
小 A 最近在鏖战密码学和代数学基础，密码学上有置乱和置乱阶，代数学基础老师又恰好讲了交错群（置换群）
小 A 首先把置换群的基本概念都烂熟于心，置换群的每一个元素都是一次置乱操作，比如
上述置换代表着，位置 1 的元素经过置换后到位置 2，位置 2 的元素经过置换后到位置 4，位置 3 元素不变，位置 4 元素经过置换后到位置 1。其实上述置换由两个小置换构成：
简单排列组合一下，小 A 发现
可是，小 A 发现，虽然可以找到置换魔群，但要表示这上面的一个元素，自己的磁盘空间远远不够，这可让他郁闷了好一阵，宇宙大概是个无限阶群吧，才会存在这么复杂的魔群。既然置换群这么神奇，小 A 决定在置换群上面做做公钥密码。
小 A 首先想到了著名的 RSA 算法，RSA 算法依赖的是给定 Zmod(n) 群，求该乘法群的阶的困难性，可是置换群
既然 RSA 不行，小 A 决定研究一下置换群上的离散对数（DLP），置换群的阶可是随着 n 超指数级别增长，那么在这上面求解离散对数肯定是很困难的！小 A 于是仿照 DH 密钥交换协议，生成了自己的公私钥。你能破解他的私钥吗？
小 A 的私钥被破解了，他百思不得其解，怎么阶这么大的一个群，离散对数求解这么容易呢？肯定是自己实现有问题，于是决定把自己私钥弄得比
置换群太光滑了，在这上面做传统的公钥密码，全是后门，毫无机密性可言，除非你能做到高阶的置换群，但是在此之前，你的内存肯定会炸掉。
- 如果你对群论与魔群有兴趣，并且没有相关基础，这或许是一个很有用的视频：群论与魔群
- 第三题：怎么得到置乱群
$A_n$ 上的最大阶元素，也就是怎么找到密码学意义上的最大置乱阶，并且构造最乱的置换。
附件下载：置换魔群附件
你可以通过 nc 202.38.93.111 10114 来连接，或者点击下面的 "打开/下载题目" 按钮通过网页终端与远程交互。
如果你不知道
nc是什么，或者在使用上面的命令时遇到了困难，可以参考我们编写的 萌新入门手册：如何使用 nc/ncat？
置换群是结构很有趣的一个群， Pohlig Hellman 离散对数求解算法就特别直观。所以这题前面两问有 CTF 经验的大手子们理解理解题意都能秒了，甚至熟悉 sage 接口的话，可以直接用 SageMath 上的 SymmetricGroup/PermutationGroup 类和 discrete_log 之类的轮子直接求离散对数，因为我自己用 Python 写的 permutation_group 类是直接仿照 SymmetricGroup 来写的，所以要改的地方几乎没有。写代码的时候把元素的 order 函数都写了，这样的话，第一题就完全是送分的题。
第三问算是开放式的一题，这一问的思路很清晰：找到两个
附注：经过企鹅拼盘（这题用的就是 由于出题人没有全文替换之前写的置乱、交错等，导致部分叙述出现了交错群/置乱群，
第一题的 RSA，只要你对群的阶有一个基本的了解，这题就很简单了，我们加密了一个置换 g：
$$ c^d = g^{ed} =g^{kg.order()+1} = 1^k *g =g $$
第二题就是求解离散对数了，本来想糊一个 DH 密钥的标准交换过程，最后还是直接搞 dlp。由于置换群的光滑性质，就可以直接用 sage 的 Pohlig Hellman 光滑阶离散对数算法在置换群上特别直观，怎么自己写轮子参考第三节、代码参考纯 Python 写的 exp。
第三题其实是开放式的一题（因为出题人能力有限，找不到最大的上界orz），最后一节详细介绍了题目里最大阶的贪心构造方法，出题人写 writeup 的时候又想到了更直观的想法，求解两个元素联合起来的最大阶，只需要在不改变物品的情况下把原来背包问题的容量扩展到 approximate subset sum，目标和为
纯 Python 解法（完善了 permutation group 类）参考 python-exp，SageMath 脚本参考 sage-exp。
我们首先来看
我们单独观察单个的小置换可以发现，(1,3) 的周期为 2，(2,4,5) 的周期为 3，所以 A 的阶是 6：
- 对于初始的 (1,3)，1 置换到 3，
$A^2$ 置换就变成 1 置换 3 再置换到 1，也即是 1 置换到 1，周而复始； - 对于初始的 (2,4,5)，2 置换到 4，
$A^2$ 置换就变成 2 置换 4 再置换到 5，也就是 2 置换到 5，$A^3$ 就变成 2 置换到 2，周而复始。
因此，一般性的结论就是，我们考虑
上面的方法也就是 Pohlig Hellman 算法的核心思想，不过在一般有限域
当然，由于题目里面的每个小子群的阶不超过 2000，因此直接对每一个小子群进行打表，计算下面的式子:
[(e, sub_element**e) for sub_element in g.standard_tuple for e in range(len(sub_element))]这样把结果里面的y对应的小置换直接查表得到对应的 e 即可，也就得到了
考虑
最优解有下面两种性质几种情况：
- 小置换长度
$l_i$ 不是素数的次幂之外的合数，否则$l_i = a*b$ （非平凡分解），由于$b^a,a^b\ge a*b,a,b>=2$ 恒成立，并且在于其他数做 LCM 时，$a^b,b^a$ 之一的结果肯定不小于$a*b$ 的结果，因此最优解里面一定不存在上述合数。 -
$Landu(n)$ 一定可以表示为$Landu(n)= MAX_{p^k \lt n} lcm(p^k,Landu(n-p^k))$ （最优子结构）
有了上面的结论就可以类似 01 背包问题愉快地动态规划了，背包的容量是 n，里面可以塞的东西就是小于 n 的所有素数次幂，
def aupton(N): # compute terms a(0)..a(N)
V = [1 for j in range(N+1)]
for i in primerange(2, N+1):
for j in range(N, i-1, -1):
hi = V[j]
pp = i
while pp <= j:
hi = max((pp if j==pp else V[j-pp]*pp), hi)
pp *= i
V[j] = hi
return V题目中上界的的生成方法，思路就是不管三七二十一，先产生
$\forall\ i\le k：Value(p^i) = 1$ $\forall\ i\gt k：Value(p^i) = p^{i-k}$
更新物品价值后，再求解一次背包问题，得到第二个元素的最大阶 bound = lcm(O1,O2) + randint(1, lcm(O1,O2)//100)。连续通过 15 轮的概率是
代码如下（之前用 C 写的，抄过来有点丑）
# sage 9.5
# For python you can use the `factorint` from sympy instead of `factor`
# from sympy import factorint
# factor = lambda x: list(factorint(x).items())
from math import sqrt,gcd
from Crypto.Util.number import *
from sympy import nextprime
def PrimeN(n):
a = [0]*(n+1)
a[0] = a[1] = 0
for i in range(2,n+1):
a[i] = 1
for i in range(2,int(sqrt(n)+1)):
mul = 2
if (a[i] == 0):
continue
while (i * mul <= n):
a[i * mul] = 0
mul+=1
return a
def max_order_element_combine(n,nums=1):
#MX = [1]*(n+1)
prime = PrimeN(n)
prime_pows = {}
# init item values
for i in range(n,-1,-1):
if not prime[i]:continue
k = i*i
prime_pows.setdefault(i,i)
while (k <= n):
prime[i]+=1
prime_pows.setdefault(k,k)
k *= i
res = [] # store the results
for _ in range(nums):
MX = [1]*(n+1)
for i in range(2,n+1):
if not prime[i]:continue
for j in range(n,1,-1):
temp = i
for k in range(1,prime[i]+1):
if (j - temp >= 0 and MX[j] < MX[j - temp] * prime_pows[temp]):
MX[j] = MX[j - temp] * prime_pows[temp]
temp *= i
res.append(MX[-1])
res_facts = factor(res[-1])
# renew the item weights
for f in res_facts:
p_f =f[0]**f[1]
j = f[0]
while j < n:
if j <= p_f:
prime_pows[j] = 1
else:
prime_pows[j] = min(j//p_f,prime_pows[j])
j*=f[0]
return res思路就是扩容背包，不扩大物品（素数幂）的选择范围；我们把背包容量扩大两倍，由此得到的最大阶 O 以及其标准素因子分解
# sage 9.5
# python version in python exp
def aupton_2(N): # compute terms a(0)..a(N)
V = [1 for j in range(2*N+1)]
for i in primerange(2, N+1):
for j in range(2*N, i-1, -1):
hi = V[j]
pp = i
while pp <= j:
hi = max((pp if j==pp else V[j-pp]*pp), hi)
pp *= i
V[j] = hi
return V
'''
Wikipedia subset sum approximation algorithm
http://en.wikipedia.org/wiki/Subset_sum_problem#Polynomial_time_approximate_algorithm
from https://github.com/saltycrane/subset-sum/blob/master/subsetsum/wikipedia.py
'''
import operator
def approx_with_accounting_and_duplicates(x_list,s):
c = .01 # fraction error (constant)
N = len(x_list) # number of values
S = [(0, [])]
for x in sorted(x_list):
T = []
for y, y_list in S:
T.append((x + y, y_list + [x]))
U = T + S
U = sorted(U, key=operator.itemgetter(0))
y, y_list = U[0]
S = [(y, y_list)]
for z, z_list in U:
lower_bound = (float(y) + c * float(s) / float(N))
if lower_bound < z <= s:
y = z
S.append((z, z_list))
return sort_by_col(S, 0)[-1]
def split_2n(n,order):
num_set = set([p^e for p,e in factor(order)])
target_sum = n
sum1,prime_list1 = approx_with_accounting_and_duplicates(num_set,target_sum)
prime_list2 = num_set - set(prime_list1)
sum2 = sum(prime_list2)
if sum1 <= target_sum and sum2 <= target_sum:
return prod(prime_list1),prod(prime_list2)
def Landu_expand(n):
order = aupton_2(n)[-1]
return split_2n(n,order)