使用复杂的代换算法可以得到预期的混淆效果。简单的线性代换函数得到的混淆效果则不够理想,一般采用非线性代换。
扩散和混淆成功地实现分组密码本质属性,因而成为设计现代分组密码的基础。
分组密码的设计方法① 乘积密码 ② 迭代密码
① 乘积密码Shannon提出乘积密码的思想。乘积密码的基本思想是:通过将一个易于实现的具有一定混乱和扩散结构的较弱的密码函数进行多次迭代来产生一个强的密码函数。
主要思想:通过简单密码的乘积来组合密码体制。
(1)乘法密码
设M=C=Z26,K={a∈Z26;gcd(a,26)=1},对于a∈K,明文x,密文y,定义:
Ea(x)=ax (mod 26)
Da(y)=a-1y (mod 26)
(2)移位密码
对于k∈K,明文x,密文y,定义:
Ek(x)=(x+k) (mod 26)
Dk(y)=(y-k) (mod 26)
假设S1是乘法密码,S2是移位密码,很容易看出S1×S2是仿射密码。
对于S1×S2,其密钥形式为(a,k)
E(a,k)(x)=(ax+k) (mod 26)
对于S2×S1,其密钥形式为(k,a)
E(k,a)(x)=(ax+ak) (mod 26)
② 迭代密码
当今大多数分组密码都是乘积密码,乘积密码通常伴随一系列置换与代替操作,常见的乘积密码是迭代密码。
迭代密码通过讲一个弱的密码函数(称为圈函数、轮函数等)迭代若干次,产生一个强的密码函数,既能快速、有效地实现,又能使明文和密钥得到必要的混淆和扩散。
g称为圈变换、圈函数或轮函数。Nr称为迭代次数、圈数或轮数。(K1,K2,...,KNr)是r个圈子秘钥。
在设计圈函数时,要充分利用代换密码和置换密码各自的优点,抵消各自的缺点,保证通过多次迭代,形成一个强的分组密码算法。
典型的迭代密码:
明确定义一个轮函数和一个密钥编排方案,一个明文的加密将通过Nr轮类似过程。
K——确定长度的随机二元密钥
用K生成Nr个轮密钥(也称为子密钥)K1,K2,...,KNr,其列表(K1,K2,...,KNr)即为密钥编排方案,它是由K经过一个固定的、公开的算法生成的。
轮函数g
轮函数g以轮密钥Kr和当前状态Wr-1作为它的两个输入,下一个状态定义为Wr,初态W0被定义为明文x,密文y定义为经过Nr轮后的状态。有
Wr=g(Wr-1,Kr)
加密过程:
W0 <- x 初态
W1 <- g(W0,K1) 第1轮
W2 <- g(W1,K2) 第2轮
...
WNr-1 <- g(WNr-2,KNr-1) 第Nr-2轮
WNr <- g(WNr-1,KNr) 第Nr-1轮
y <- WNr 第Nr轮
为解密,g在第二个变量固定的情况下,必须是单射,即等价于存在g-1,g-1(g(w,k),k)=w.
解密过程:
WNr <- y
WNr-1 <- g-1(WNr,KNr)
...
W1 <- g-1(W2,K2)
W0 <- g-1(W1,K1)
x <- W0
迭代密码常见的模型有S-P网络(代替-置换网络),Feistel网络等。
代替-置换网络(S-PN)Substitution-Permutation一个S-PN就是一类特殊的迭代密码,设l和m都是正整数,明密文都是长为lm的二元向量。一个S-PN包含两个变换,分别记为∏s和∏p.
∏s:{0,1}l -> {0,1}l 实现l比特的代替,即S盒。
∏p:{1,2,...,lm} -> {1,2,...,lm},实现lm比特的置换,即P盒。
x=(x1,x2,...,xm)=x<1>||x<2>||...||x<m>.
x<i>=(x(i-1)l+1,x(i-1)l+2,...,xil),1≤i≤m.
S-PN特点: