应用密码学：4－分组密码（续）

1、密 码 学分组密码(续1)本讲内容 IDEA分组密码算法典型分组密码介绍IDEA国际数据加密算法（the International Data Encryption Algorithm）是中国学者莱学嘉在瑞士攻读博士期间与其导师著名的密码学家J.L.Massey一起研究、最后于1991年定形的一个著名的分组密码体制。该密码是NESSIE工程的候选算法之一。今天看来，虽然其64比特的明文分组长度对于应付计算机和计算技术的发展来说可能稍嫌不够，但尚未发现明显弱点，是为数不多的经过较多理论分析和时间检验的好算法之一。IDEA使用一个长为128的比特串作为密钥，每次对一个长为64比特的明文组进行加密，

2、得到的密文组长仍为64比特。即M= ，C= ，K= 。典型分组密码介绍IDEAIDEA的描述加密算法.+X1(16bit)X2(16bit)X3(16bit)X4(16bit)+Y1(16bit)Y2(16bit)Y3(16bit)Y4(16bit)第i轮迭代输出变换在前面图示的IDEA算法中，多次对两个16比特数据块使用了下列三种运算：逐比特模2加， 模216加法，模216+1乘法（须将16比特全零数据看成为216）。+IDEA的描述密钥扩展. 各轮迭代以及输出变换一共使用52个加密子密钥它们依据所给128bit主密钥K按下述方法产生：IDEA的描述IDEA的描述脱密过程. 采用与加密过程一

3、样的算法，只不过须将52个加密子密钥对应换成以下的脱密子密钥：在上式中，K-1K的模216+1乘法逆，即：K-1K=1；-KK的模216加法逆，即：-K K=0。+正确性. 只需对下面图示的变换 ：证明 即可。注意到有: 。对固定的K5和K6，当S1,S2,S3,S4分别用T1,T2,T3,T4代替时，运算结构的输入U1,U2不变，从而输出V1,V2也不变。T1= S1V2T2= S2V1 T1T3=S1S3T3= S3V2 T2T4=S2S4T4= S4V1IDEA的描述+S1S2S3S4T1T2T3T4U1V1V2U2IDEA的软件实现求模216加法“ ”的逆元与模216+1乘法“”的逆元

4、.对于0K216，-K其实就是K求反码之后+1的结果；对于0K216，K-1就是K模(216+1)的逆（因216+1是素数，故K模(216+1)可逆）。下面给出模逆的概念及其求法：对dZn=0,1,2,n-1，若eZn，de1(mod n)，则称d模n可逆，并称e为d模n的逆，记为d-1(mod n)=e。+IDEA的软件实现一个有关的重要结果是：dZn模n可逆，当且仅当(d,n)=1。对给定的dZn，如何判定d与n互素并且求出d-1(mod n)呢？我们有所谓的辗转相除法如下：设a0=n,a1=d，辗转做带余除法得ai-1=qiai+ai+1，i=1,k其中k使0=ak+1aka1。表成矩阵

5、形式：IDEA的软件实现不难看出于是，可设ai=uin+vid，i=1,k。由辗转相除过程可知，ak=(d,n)。如果(d,n)=1，则ukn+vkd=1，由此即得vkd 1(mod n)因此，d-1(mod n)=vk(mod n)。现在得到求d-1(mod n)的方法如下：由n与d开始辗转做带余除法，直至最后除尽为止；若最后除尽时的除式不为1，则d与n不互素而d模n不可逆，结束；根据辗转相除法的矩阵表示可求出那么，d-1(mod n)=vk(mod n)。IDEA的软件实现或者，可以推导出求vi的递推关系：注意到ai+1= ui+1n+vi+1d，又ai+1=ai-1-qiai=(ui-1

6、-qiui)n+(vi-1-qivi)d可见 vi+1=vi-1-qivi，且必要的初值是：v0=0,v1=1。根据上述递推关系可给出求d-1(mod n)的算法框图如下页：IDEA的软件实现输入：n,d初始化an,bd,t0,v1用带余除法计算：a=qb+r（0rb)r=0 ?v0 ?vn+v输出：v=d-1(mod n)修改ab,brwv,vt-qv,twYNYNb=1 ?YN回答：d-1(mod n)不存在，结束。可以证明，上述算法的输出v必然满足：0vn 。IDEA的软件实现模216+1乘法的低高算法.对于0a,b2n(n为自然数)，必有注意： 对应ab的n个最低有效位，刚好是ab右移n位的结果。证明. 存在唯一的整数q和r，使得ab=q(2n+1)+r，0r2n+1,0q2n从而ab=q2n+q+r，0q+r2n+1ID