运行输出如下
以上输出表格与文献[1] 给出的完全一致
S盒的代数性质
主要是平衡性、代数次数、非线性度、Walsh谱、差分均分度、SAC、扩散准则PC(k)，具体计算根据它们的定义。代码如下
###########################################################
def sbox_balance(S):
for j in range(S_N):
cnt = sum((S[i]>>j)&1 for i in range(S_SIZE))
print(f"Output bit {j}: {cnt} ones")
sbox_balance(sm4_sbox_table); print()
###########################################################
def max_nonlinearity(n):
if n % 2 == 0:
return 2^(n-1) - 2^(n//2 - 1)
else:
return 2^(n-1) - 2^((n-1)//2)
def sbox_boolfun_property(S):
min_nl = infinity
for j in range(S_N):
bf = BooleanFunction([(S[i]>>j)&1 for i in range(S_SIZE)])
deg = bf.algebraic_degree()
nl = bf.nonlinearity()
min_nl = min(min_nl, nl)
walsh_max = max(abs(w) for w in bf.walsh_hadamard_transform())
print(f"Bit {j}: degree={deg}, nonlinearity={nl}, max|Walsh|={walsh_max}")
print(f"the minimum nonlinearity is {min_nl}, theory max nonlinearity is {max_nonlinearity(S_N)}")
sbox_boolfun_property(sm4_sbox_table); print("")
###########################################################
def sbox_differential_uniformity(S):
ddt = {}
for dx in range(1, S_SIZE):
for x in range(S_SIZE):
dy = S[x] ^^ S[x^^dx]
ddt[(dx, dy)] = ddt.get((dx, dy), 0) + 1
delta = max(ddt.values())
print("Differential Uniformity =", delta)
sbox_differential_uniformity(sm4_sbox_table); print()
###########################################################
def sbox_fixed_points(S):
fps = []
for x in range(S_SIZE):
if S[x] == x:
fps.append(hex(x))
return fps
fps = sbox_fixed_points(sm4_sbox_table)
print(f"has {len(fps)} fixed points: {fps}", end="\n\n")
###########################################################
def flip_bit(x, i):
return x ^^ (1 << i)
def sbox_sac(S):
sac_matrix = matrix(QQ, S_M, S_N, 0)
for x in range(S_SIZE):
for i in range(S_M):
xp = flip_bit(x, i)
dx = S[xp] ^^ S[x]
for j in range(S_N):
if (dx >> j) & 1:
sac_matrix[i, j] += 1
# Normalize to probability
sac_matrix = sac_matrix / S_SIZE
return sac_matrix
print(sbox_sac(sm4_sbox_table)); print()
def sbox_check_pck(S, k):
bool_funcs = []
bf_satisfy_pcks = []
for i in range(S_N):
bf = BooleanFunction([(S[x] >> i) & 1 for x in range(S_SIZE)])
bool_funcs.append(bf)
bf_satisfy_pcks.append(True)
for i, f in enumerate(bool_funcs):
w = f.walsh_hadamard_transform()
for a in range(1, S_SIZE):
if bin(a).count('1') <= k:
if w[a] != 0:
# D = f.derivative(a)
# if not D.is_balanced():
bf_satisfy_pcks[i] = False
break
r = bf_satisfy_pcks[i]
print(f"bf[{i}] satify PC({k}):{r}")
for k in range(1, 4):
sbox_check_pck(sm4_sbox_table, k); print()
###########################################################
sbox_check_pck函数内注释部分为用布尔函数导数的方法，结果与使用Walsh谱的方法一致。当k=1时等价于SAC。运行脚本，输出如下
可以看出S盒不严格满足PC(k)，SAC则是接近满足。其它指标良好
参考文献
[1] GB/T32907—2016 信息安全技术 SM4分组密码算法
[2] Algebraic Cryptanalysis of SMS4: Gr¨obner Basis Attack and SAT Attack Compared