想起了之前在BRICS+2023里发现一道很简短的题目，没想到里面大有学问。

信安数学基础简单了解了一下置换群，不过应试学的比较粗糙，继续深入了解一下。

前置知识

置换和置换群

对于某个组$(1,2,3)$，可以进行置换，使用itertools库的permutations()函数可以进行置换排列：

1
2
3
4
import itertools  
print(list(itertools.permutations([1, 2, 3])))    

# [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

可以发现使用这个函数返回的是一个带有所有排列组合的集合，对于组成元素集合$X=(1,2,3)$，将$X$排列后得到的六种置换构成一个对称群$S_X$，这个对称群的某个子群就叫做一个置换群。

这里我们组成元素有$3$个，所以是$3$阶对称群。

置换群中的元素是一些置换，例如上面例子中存在某个置换：

满足：

置换群的复合

下面是对置换群的操作：

对于复合操作，先进行$\tau$再进行$\sigma$，可以直接写作$\sigma\tau$。

置换群的元素也可以自己和自己进行复合，例如：

sage里可以进行排列操作：

1
2
3
4
5
6
G = Permutations(3)
g = G.random_element()	# [3, 1, 2]
h = G.random_element()	# [3, 2, 1]
print(g * h)	# [1, 3, 2]
print(g^2)	# [2, 3, 1]
print(g^3)	# [1, 2, 3]

这里得到的元素其实是省略写法：

对于[3, 1, 2]得到的其实是一个置换：

对于[3, 2, 1]得到的其实是一个置换：

两个置换进行复合，得到新的置换：

对于对称群$S_n$（$n$元对称群），阶为$n!$，置换群的阶应该是对称群阶的一个因子。

回圈

回圈是置换群元素的另一种表示方法：对于某个置换，存在：

那么存在一个长度为$k$的回圈，记作$(a_0,a_1,…,a_{k-1})$，将所有的回圈写在一起就可以表示一个置换了。

对于某个置换：

得到回圈表示：

单个元素可以认为自己构成一个圈。

在sage中使用PermutationGroupElement可以得到一个回圈表述的置换元。

置换群开方

群平方

之前提到了置换群元素可以进行自己和自己复合，也就是做平方运算。

对于某个置换：

进行平方计算得到：

注意到在回圈中，对置换进行平方也就是对其中所有的回圈分别进行了平方置换，可以将大的置换拆分为每个回圈构成的小置换，得到：

还注意到平方运算的一个性质：

对于长度为偶数的回圈，进行平方后会被拆分为两个长度相等的圈：

对于长度为奇数的圈，进行平方后还是一个长度不变的回圈，只改变了其中的顺序：

群开方

群开方操作需要进行几种讨论，可以先设定$\tau=\sigma^2$，圈的奇偶是一个很好的切入点。

奇数圈开方

对于一个奇数圈，在$\tau$中发现存在奇数圈$\tau_i$，如果这个奇数圈的长度在整个平方置换是唯一的，那么就可以断定这个圈是$\sigma$中某个相同长度的奇数圈$\sigma_i$平方得到。

根据我们知道的奇数圈平方后的元素顺序，就可以轻易还原出原来的开方置换：

得到转换关系：

也就是按照这关系重新排列一下就能得到开方后的元素。

偶数圈开方

如果在$\tau$的回圈中找到两个回圈拥有相同的长度$\frac k2$，如果这个长度是偶数，那么就可以确定是为$\sigma$中一个长度为$k$的回圈平方分裂产生。

但是如果$\frac k2$为奇数，那么会出现两种情况，不确定是为一个偶数$k$圈分裂产生还是两个长度$\frac k2$的奇数圈平方产生。

奇数圈的情况按照上面直接转化即可，这里注意一下$\frac k2$为偶数的情况，奇数圈平方只产生奇数圈，记：

根据转换关系就能得到：

但是这里会有一个问题，对于某个回圈$(a,b,c)$，有：

它们都认为是同一个回圈，所以当这多种组合和另一个回圈进行开方整合为一个回圈之后，由于顺序出现问题就会产生多解，解的个数可以发现和整合前圈内元素数量是相同的，即为有$\frac k2$个解。

BRICS+ sqrt

非常简短的题目：

1
2
3
4
5
6
from sage.all import *
import hashlib

P = Permutations(256).random_element()
print(P**2)
print([x^y for x,y in zip(hashlib.sha512(str(P).encode()).digest(), open('flag.txt', 'rb').read())])
1
2
[41, 124, 256, 27, 201, 93, 40, 133, 47, 10, 69, 253, 13, 245, 165, 166, 118, 230, 197, 249, 115, 18, 71, 24, 100, 14, 160, 28, 251, 96, 106, 5, 244, 58, 67, 44, 150, 42, 255, 74, 168, 182, 153, 209, 227, 232, 159, 128, 125, 11, 135, 90, 76, 30, 84, 31, 1, 149, 48, 95, 216, 94, 157, 131, 196, 172, 105, 169, 202, 203, 121, 210, 53, 9, 147, 89, 39, 68, 59, 141, 87, 207, 51, 180, 19, 81, 57, 103, 228, 77, 12, 129, 185, 85, 45, 123, 50, 116, 65, 213, 104, 64, 54, 155, 222, 112, 3, 252, 21, 33, 138, 151, 211, 233, 204, 97, 239, 113, 82, 200, 23, 231, 177, 26, 72, 4, 78, 183, 199, 6, 49, 29, 250, 119, 32, 56, 110, 187, 35, 143, 83, 25, 70, 2, 66, 101, 217, 120, 224, 142, 191, 136, 189, 127, 132, 36, 174, 146, 152, 140, 193, 62, 178, 17, 148, 248, 167, 88, 73, 229, 134, 156, 158, 60, 63, 242, 221, 34, 214, 20, 171, 139, 226, 186, 164, 181, 236, 107, 111, 61, 99, 108, 179, 223, 137, 212, 237, 102, 161, 145, 184, 173, 247, 162, 205, 154, 55, 117, 254, 38, 75, 234, 7, 46, 109, 22, 175, 144, 219, 220, 195, 190, 98, 79, 15, 170, 80, 235, 52, 8, 37, 243, 198, 86, 43, 192, 241, 240, 208, 130, 188, 114, 218, 215, 206, 176, 238, 16, 246, 126, 122, 163, 225, 92, 91, 194]
[18, 188, 48, 47, 100, 234, 225, 8, 187, 34, 124, 113, 118, 252, 137, 196, 125, 20, 251, 168, 167, 5, 225, 134, 66, 203, 26, 148, 63, 181, 213, 124, 170, 234, 35, 120, 47, 69, 157, 69, 194]

题目给了一个$S_{256}$的一个置换的平方，需求开方。

根据之前对回圈的知识了解，首先先通过PermutationGroupElement来获得这个平方群元的回圈结果：

1
2
3
4
5
6
P2 = [41, 124, 256, 27, 201, 93, 40, 133, 47, 10, 69, 253, 13, 245, 165, 166, 118, 230, 197, 249, 115, 18, 71, 24, 100, 14, 160, 28, 251, 96, 106, 5, 244, 58, 67, 44, 150, 42, 255, 74, 168, 182, 153, 209, 227, 232, 159, 128, 125, 11, 135, 90, 76, 30, 84, 31, 1, 149, 48, 95, 216, 94, 157, 131, 196, 172, 105, 169, 202, 203, 121, 210, 53, 9, 147, 89, 39, 68, 59, 141, 87, 207, 51, 180, 19, 81, 57, 103, 228, 77, 12, 129, 185, 85, 45, 123, 50, 116, 65, 213, 104, 64, 54, 155, 222, 112, 3, 252, 21, 33, 138, 151, 211, 233, 204, 97, 239, 113, 82, 200, 23, 231, 177, 26, 72, 4, 78, 183, 199, 6, 49, 29, 250, 119, 32, 56, 110, 187, 35, 143, 83, 25, 70, 2, 66, 101, 217, 120, 224, 142, 191, 136, 189, 127, 132, 36, 174, 146, 152, 140, 193, 62, 178, 17, 148, 248, 167, 88, 73, 229, 134, 156, 158, 60, 63, 242, 221, 34, 214, 20, 171, 139, 226, 186, 164, 181, 236, 107, 111, 61, 99, 108, 179, 223, 137, 212, 237, 102, 161, 145, 184, 173, 247, 162, 205, 154, 55, 117, 254, 38, 75, 234, 7, 46, 109, 22, 175, 144, 219, 220, 195, 190, 98, 79, 15, 170, 80, 235, 52, 8, 37, 243, 198, 86, 43, 192, 241, 240, 208, 130, 188, 114, 218, 215, 206, 176, 238, 16, 246, 126, 122, 163, 225, 92, 91, 194]

P2C = PermutationGroupElement(P2)
print(P2C)

# (1,41,168,88,103,54,30,96,123,177,221,195,137,110,33,244,215,109,21,115,204,162,62,94,85,19,197,237,241,188,107,3,256,194,223,98,116,97,50,11,69,202,173,158,146,101,104,155,132,29,251,122,231,37,150,142,25,100,213,7,40,74,9,47,159,152,136,56,31,106,112,151,191,99,65,196,212,234,86,81,87,57)(2,124,26,14,245,206,154,127,78,68,169,73,53,76,89,228,235,43,153,189,111,138,187,236,192,108,252,163,178,34,58,149,224,79,59,48,128,183,226,170,229,52,90,77,39,255,91,12,253,225,15,165,148,120,200,145,66,172,156,36,44,209,254,92,129,199,161,193,179,214,46,232,243,218,144)(4,27,160,140,143,70,203,247,238,240,130,6,93,185,164,17,118,113,211,75,147,217,175,63,157,174,60,95,45,227,80,141,83,51,135,32,5,201,184,186,181,171,134,119,82,207,55,84,180,20,249,246,176,242,114,233,198,102,64,131,49,125,72,210,38,42,182,139,35,67,105,222,190,61,216,22,18,230,8,133,250,126)(16,166,248)(23,71,121)(117,239,208)

得到了一个$75$长度的回圈、两个长度$82$的回圈，三个长度$3$的回圈，$8$个长度$1$的回圈。

注意到这里的长度$1$的内圈这个函数是不给的，需要我们自己去补。

可以确定长度为$75$的圈就是长度为$75$的回圈进行了平方得到的；两个长度为$82$的回圈一定是一个长度为$164$的回圈平方得到的；三个长度$3$的回圈需要分情况，可能是三个奇数圈平方，也可能是一个奇数圈平方，另外两个是一个长度$6$的偶数圈平方分裂得到；$8$个长度为$1$的内圈讨论起来就更复杂了。

可以通过爆破将$8$个$1$的求出所有可能，还有$3$个$3$的排列组合，剩下两个圈是确定的，不需要这么复杂。

这里的回圈表示用的都是string型，将数组转为string然后拼接一下得到即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
# sage
import hashlib
import itertools
from tqdm import tqdm

P2 = [41, 124, 256, 27, 201, 93, 40, 133, 47, 10, 69, 253, 13, 245, 165, 166, 118, 230, 197, 249, 115, 18, 71, 24, 100, 14, 160, 28, 251, 96, 106, 5, 244, 58, 67, 44, 150, 42, 255, 74, 168, 182, 153, 209, 227, 232, 159, 128, 125, 11, 135, 90, 76, 30, 84, 31, 1, 149, 48, 95, 216, 94, 157, 131, 196, 172, 105, 169, 202, 203, 121, 210, 53, 9, 147, 89, 39, 68, 59, 141, 87, 207, 51, 180, 19, 81, 57, 103, 228, 77, 12, 129, 185, 85, 45, 123, 50, 116, 65, 213, 104, 64, 54, 155, 222, 112, 3, 252, 21, 33, 138, 151, 211, 233, 204, 97, 239, 113, 82, 200, 23, 231, 177, 26, 72, 4, 78, 183, 199, 6, 49, 29, 250, 119, 32, 56, 110, 187, 35, 143, 83, 25, 70, 2, 66, 101, 217, 120, 224, 142, 191, 136, 189, 127, 132, 36, 174, 146, 152, 140, 193, 62, 178, 17, 148, 248, 167, 88, 73, 229, 134, 156, 158, 60, 63, 242, 221, 34, 214, 20, 171, 139, 226, 186, 164, 181, 236, 107, 111, 61, 99, 108, 179, 223, 137, 212, 237, 102, 161, 145, 184, 173, 247, 162, 205, 154, 55, 117, 254, 38, 75, 234, 7, 46, 109, 22, 175, 144, 219, 220, 195, 190, 98, 79, 15, 170, 80, 235, 52, 8, 37, 243, 198, 86, 43, 192, 241, 240, 208, 130, 188, 114, 218, 215, 206, 176, 238, 16, 246, 126, 122, 163, 225, 92, 91, 194]
c = [18, 188, 48, 47, 100, 234, 225, 8, 187, 34, 124, 113, 118, 252, 137, 196, 125, 20, 251, 168, 167, 5, 225, 134, 66, 203, 26, 148, 63, 181, 213, 124, 170, 234, 35, 120, 47, 69, 157, 69, 194]

P2G = PermutationGroupElement(P2)

s = [10, 13, 24, 28, 167, 205, 219, 220]
o2Circles = set()
o2Circles.add('')
for si in tqdm(itertools.permutations(s)):
  tmp = []
  for i in range(0, len(si), 2):
    for t in tmp:
      if si[i] in t or si[i+1] in t:
        break
    else:
      tmp += [tuple(sorted([si[i], si[i+1]]))]
      o2Circles.add(''.join(str(x) for x in sorted(tmp)))
o2Circles = sorted(list(o2Circles))
print(len(o2Circles))

def sqrtOdd(oddCircles):
  Ptmp = ''
  for oc in oddCircles:
    k = len(oc)
    assert k % 2 == 1
    k = (k - 1) // 2
    tmp = []
    for i in range(k):
      tmp += [oc[i]]
      tmp += [oc[k+i+1]]
    tmp += [oc[k]]
    Ptmp += str(tuple(tmp))
  return Ptmp
  
def sqrtEven(evenCircles):
  Ptmp = []
  if evenCircles == []:
    return []
  assert len(evenCircles) == 2
  assert len(evenCircles[0]) == len(evenCircles[1])
  k = len(evenCircles[0])
  if k % 2 == 1:
    Ptmp += [sqrtOdd([evenCircles[0]]) + sqrtOdd([evenCircles[1]])]
  for i in range(k):
    tmp = []
    for j in range(k):
      tmp += [evenCircles[0][j]]
      tmp += [evenCircles[1][(i+j)%k]]
    Ptmp += [str(tuple(tmp))]
  return Ptmp

circles3 = [
  (16,166,248),
  (23,71,121),
  (117,239,208)
]
evenCircles0 = [
  (1,41,168,88,103,54,30,96,123,177,221,195,137,110,33,244,215,109,21,115,204,162,62,94,85,19,197,237,241,188,107,3,256,194,223,98,116,97,50,11,69,202,173,158,146,101,104,155,132,29,251,122,231,37,150,142,25,100,213,7,40,74,9,47,159,152,136,56,31,106,112,151,191,99,65,196,212,234,86,81,87,57),
  (4,27,160,140,143,70,203,247,238,240,130,6,93,185,164,17,118,113,211,75,147,217,175,63,157,174,60,95,45,227,80,141,83,51,135,32,5,201,184,186,181,171,134,119,82,207,55,84,180,20,249,246,176,242,114,233,198,102,64,131,49,125,72,210,38,42,182,139,35,67,105,222,190,61,216,22,18,230,8,133,250,126)
]
oddCircles0 = [
  (2,124,26,14,245,206,154,127,78,68,169,73,53,76,89,228,235,43,153,189,111,138,187,236,192,108,252,163,178,34,58,149,224,79,59,48,128,183,226,170,229,52,90,77,39,255,91,12,253,225,15,165,148,120,200,145,66,172,156,36,44,209,254,92,129,199,161,193,179,214,46,232,243,218,144),
]

P0 = sqrtOdd(oddCircles0) 
for o2i in tqdm(o2Circles):
  for ec0 in sqrtEven(evenCircles0):
    P1 = P0 + ec0
    for c3 in itertools.permutations(circles3):
      evenCircles1 = [c3[0], c3[1]]
      oddCircles1 = [c3[2]]
      P2 = P1 + sqrtOdd(oddCircles1) 
      for ec1 in sqrtEven(evenCircles1):
        P3 = P2 + ec1
        P4 = P3 + o2i
        PG = PermutationGroupElement(P4) 
        assert PG^2 == P2G

        P = list(PG.dict().values())
        Ph = hashlib.sha512(str(P).encode()).digest()
        flag = ''.join([chr(x^^y) for x, y in zip(Ph, c)])
        if 'brics' in flag or 'BRICS' in flag:
          print(P)
          print(flag)
          exit(0)

'''
[190, 226, 217, 195, 155, 62, 20, 96, 176, 24, 227, 169, 220, 52, 76, 248, 197, 54, 17, 40, 238, 103, 239, 10, 55, 229, 137, 28, 186, 8, 64, 104, 143, 193, 81, 187, 119, 196, 127, 249, 61, 212, 145, 236, 11, 79, 242, 218, 151, 45, 146, 245, 15, 230, 100, 102, 222, 179, 243, 97, 168, 93, 223, 106, 38, 189, 87, 12, 80, 215, 208, 99, 225, 246, 107, 165, 154, 91, 232, 202, 67, 142, 158, 213, 164, 35, 105, 22, 148, 206, 68, 252, 94, 185, 50, 133, 95, 174, 210, 84, 32, 31, 18, 5, 57, 131, 147, 92, 247, 140, 156, 49, 241, 152, 240, 60, 23, 237, 150, 235, 117, 171, 250, 170, 191, 221, 255, 144, 163, 162, 112, 184, 123, 37, 101, 198, 160, 36, 86, 33, 173, 207, 244, 183, 153, 135, 3, 228, 214, 82, 125, 233, 66, 39, 201, 138, 98, 51, 114, 110, 34, 6, 199, 19, 89, 16, 205, 216, 253, 26, 231, 111, 83, 116, 194, 47, 126, 161, 149, 7, 122, 234, 2, 29, 85, 251, 44, 75, 172, 41, 72, 254, 58, 63, 27, 42, 118, 56, 178, 43, 132, 141, 109, 130, 167, 77, 25, 121, 192, 65, 188, 182, 180, 224, 203, 88, 256, 128, 219, 13, 4, 1, 157, 46, 53, 124, 69, 120, 14, 30, 134, 59, 136, 139, 200, 209, 113, 115, 71, 204, 211, 159, 48, 70, 90, 9, 21, 166, 74, 177, 181, 129, 73, 108, 78, 175]
brics+{ab99943f6dae4f20595c8645fcf8289e}

 54%|██████████████████████████████████                             | 413/764 [24:42<20:59,  3.59s/it]
'''