获取分组密码活跃S盒个数下界的方法

摘要

本发明公开了一种获取比特级置换线性扩散层分组密码活跃S盒个数下界的方法，包括：对使用比特级置换作为扩散层的分组密码中的每个S盒的每个输入比特和每个输出比特引入差分变量，并对所述每个S盒引入活跃变量；针对所述每个S盒，分析S盒操作和位置换操作对差分模式传播的限制，并以最小化所述分组密码中所有S盒的活跃变量之和为目标对所述每个S盒的每个输入比特和每个输出比特的差分变量以及每个S盒的活跃变量赋予所述限制，以建立一混合整数的线性规划问题；求解所述混合整数线性规划问题，以获得活跃S盒的下界。本发明大大降低了密码设计工作量和出错概率，填补了本领域空白，同样适用于采用非极大距离可分码构造的线性扩散层。

主权项

一种获取使用比特级置换作为线性扩散层的分组密码活跃S盒个数下界的方法，其特征在于，包括：对使用比特级置换作为扩散层的分组密码中的每一个S盒的每个输入比特和每个输出比特，引入差分变量，并对所述每一个S盒引入活跃变量；针对所述每一个S盒，分析S盒操作、轮密钥异或操作和比特级置换操作对差分模式传播的限制，并以最小化所述分组密码中所有S盒的活跃变量之和为目标对所述每一个S盒的每个输入比特和每个输出比特的差分变量以及每一个S盒的活跃变量赋予所述限制，以建立一混合整数的线性规划问题；求解所述混合整数线性规划问题，以获得活跃S盒个数的下界；其中，所述限制包括：对于A[r,t]变量所代表的S盒，对所述差分模式传播具有如下限制：限制一，保证当A[r,t]变量所代表的S盒为活跃S盒时，该S盒的输入差分中，至少有一个输入比特变量的值为1，即：x[r,t,1]+…+x[r,t,P]‑A[r,t]≥0限制二，保证当A[r,t]变量所表示的S盒的输入差分中有一个非零比特时，该S盒必须是活跃S盒，即：x[r,t,p]‑A[r,t]≤0限制三：非零输入差分一定导致非零输出差分，且非零输出差分一定导致非零输入差分，即：Py[r,t,1]+…+Py[r,t,P]‑x[r,t,1]‑…‑x[r,t,P]≥0且Px[r,t,1]+…+Px[r,t,P]‑y[r,t,1]‑…‑y[r,t,P]≥0限制四：保证当A[r,t]变量所代表的S盒的输入差分中有1比特非零时，输出差分中至少有B比特非零，即：x[r,t,1]+…+x[r,t,P]+y[r,t,1]+…+y[r,t,P]≥B×d其中，d≥x[r,t,1]、…、d≥x[r,t,P]、d≥y[r,t,1]、…、d≥y[r,t,P]，B为A[r,t]变量所代表的S盒的极大分支数；其中d为输入输出差分标记变量，当x[r,t,1]、…、x[r,t,P]、y[r,t,1]、…、y[r,t,P]中任意一个变量取1时，d取1，否则取0；其中，极大分支数的定义为：$Bs={\min }_{a\ne b}\{wt\left(\right(a\oplus b\left)\right|\left|\right(S\left(a\right)\oplus S\left(b\right)\left)\right):a,b\in F_2^{\omega }\}$其中，Bs为S盒的极大分支数，wt为一二进制数据串的汉明重量，即非零数据位的个数，a、b分别为S盒的输入变量，S(a)表示此S盒以a为输入时的输出值，S(b)表示此S盒以b为输入时的输出值；所述分组密码的每一轮中，轮密钥异或操作的输入输出差分限制为：所述轮密钥异或操作的两个输入比特和一个输出比特之和大于等于2倍的且大于等于所述轮密钥异或操作的两个输入比特和一个输出比特，即$z\left[1\right]+z\left[2\right]+z\left[3\right]\ge 2d_{\oplus }$$d_{\oplus }\ge z\left[1\right]$$d_{\oplus }\ge z\left[2\right]$$d_{\oplus }\ge z\left[3\right]$其中，z[1]、z[2]为所述异或操作的两个输入比特，z[3]为所述异或操作的输出比特，为差分标记变量，其值只取0和1，当z[1]，z[2]，z[3]中有任意一个变量取1时，取1，否则取0；限制使用比特级置换作为扩散层的分组密码的密码体制的输入差分不全为0。