数论及其应用序列密码流五章.pptx

2025/2/211第5章：

密码函数其它安全性设计一、差分分布二、特殊的差分分布：雪崩与扩散三、高阶差分分布四、正形置换

2025/2/212一、差分分布回顾对分组密码的已知明文攻击。设明文是n维布尔向量x=(x1,x2,…,xn)；密文是n维布尔向量y=(y1,y2,…,yn)；密钥是l维布尔向量z=(z1,z2,…,zl)；加密变换是y=F(x,z)；解密变换是x=F-1(y,z)。其中函数F：GF(2)n+l→GF(2)n。当密钥z固定时，加密变换F是GF(2)n上的可逆函数（置换函数）。（分组密码总是多次一密的，即密钥z被反复使用）。设攻击者知道加密变换F，但不知道通信伙伴正在使用的密钥z。

2025/2/213一、差分分布设攻击者获得了大量的明文/密文对。这些明文/密文对给出了关于未知密钥z的信息。从理论上说，获得的明文/密文对越多，所得到的关于未知密钥z的信息越多。问题是怎样根据这些信息来确定密钥z。换一个角度，通信伙伴怎样设计加密变换F，使得：即使攻击者获得了大量的明文/密文对，因此得到了关于未知密钥z的很多信息，但攻击者无法将这些信息转化为对密钥z的有效求解。这样的性质总称为伪随机性。伪随机性包含太多的内容，非线性性就是其中之一。伪随机性还包含差分分布均匀性等。

2025/2/214一、差分分布定义5-1设有函数f：GF(2)n→GF(2)m。对固定点a∈GF(2)n，定义f在a点的差分函数为△f(x,a)=f(x+a)+f(x)。当x变动时，△f(x,a)的值的分布称为f在固定点a处的差分分布。当x和a都变动时，△f(x,a)的值的分布称为f的差分分布。（差分分布的均匀性是密码函数的一个重要的安全性指标，著名的差分密码分析正是利用了差分分布的不均匀性。最理想的情形：差分分布是均匀的。即对任意固定点a∈GF(2)n，f在a点的差分函数△f(x,a)是均衡函数。）

2025/2/215一、差分分布例一种攻击。设密码函数f：GF(2)n→GF(2)m。设有一个固定点a∈GF(2)n，使得f在a点的差分函数△f(x,a)=f(x+a)+f(x)的分布极为不均匀。当x变动时，△f(x,a)的值几乎是定值b。现在攻击者知道了f(u)的值等于v，但不知道u的值。则攻击者推断出f(u+a)的值几乎是定值v+b。例另一种攻击：简化计算部件。

2025/2/216一、差分分布例设函数f：GF(2)n→GF(2)，是n维布尔函数。则f在任意固定点a点的差分函数△f(x,a)是均衡函数；当且仅当：f是Bent函数。此时n必须是偶数。例设函数f：GF(2)n→GF(2)m。则f在任意固定点a点的差分函数△f(x,a)是均衡函数；当且仅当：f是多输出Bent函数。此时n必须是偶数，且n≥2m。（因此，理想的差分分布等价于理想的非线性性）

2025/2/217一、差分分布例设函数f：GF(2)n→GF(2)n。则f在固定点a点的差分函数△f(x,a)不可能是均衡函数。如果△f(x,a)竟然是均衡函数，则当x跑遍GF(2)n，△f(x,a)也应该跑遍GF(2)n。如果当x跑遍GF(2)n时△f(x,a)也跑遍GF(2)n，则△f(x,a)的每个值只出现一次。然而，△f(u,a)=f(u+a)+f(u)；△f(u+a,a)=f(u+a+a)+f(u+a)=f(u)+f(u+a)。当x=u以及x=u+a时，△f(x,a)相等。因此，△f(x,a)的每个值出现偶数次。最理想的情形是：△f(x,a)的每个值出现0次或2次。

2025/2/218二、特殊的差分分布：

雪崩与扩散差分分布的均匀性是一个过于强的性质，以至于常常难以满足。以下稍弱化这一概念，考虑一类特殊差分分布的均匀性，称为雪崩与扩散。总设函数为f：GF(2)n→GF(2)m。定义5-2如果对任意固定的a∈GF(2)n，WH(a)=1，（1）f(x+a)+f(x)是均衡函数，则称f满足严格雪崩准则；（2）f(x+a)+f(x)是k阶弹性函数，则称f满足k阶严格雪崩准则。定义5-3如果对任意固定的a∈GF(2)n，1≤WH(a)≤k，f(x+a)+f(x)是均衡函数，则称f满足k次扩散准则。

2025/2/219二、特殊的差分分布：

雪崩与扩散对于函数y=f(x)，不妨称x和y分别为明文和密文。严格雪崩准则可以理解为一种不连续性：当明文改变一个比特时，相应密文的改变是完全随机的，且密文平均改变m/2个比特。由定义显然有：严格雪崩准则弱于差分分布均匀性（差分分布均匀性等价于完全非线性性）；严格雪崩准则就是1次扩散准则；满足k+1次扩散准则就一定满足k次扩散准则；满足n次扩