應(yīng)用密碼學(xué)：4－分組密碼（續(xù)）

1、密 碼 學(xué)分組密碼(續(xù)1)本講內(nèi)容 IDEA分組密碼算法典型分組密碼介紹IDEA國際數(shù)據(jù)加密算法（the International Data Encryption Algorithm）是中國學(xué)者萊學(xué)嘉在瑞士攻讀博士期間與其導(dǎo)師著名的密碼學(xué)家J.L.Massey一起研究、最后于1991年定形的一個(gè)著名的分組密碼體制。該密碼是NESSIE工程的候選算法之一。今天看來，雖然其64比特的明文分組長度對(duì)于應(yīng)付計(jì)算機(jī)和計(jì)算技術(shù)的發(fā)展來說可能稍嫌不夠，但尚未發(fā)現(xiàn)明顯弱點(diǎn)，是為數(shù)不多的經(jīng)過較多理論分析和時(shí)間檢驗(yàn)的好算法之一。IDEA使用一個(gè)長為128的比特串作為密鑰，每次對(duì)一個(gè)長為64比特的明文組進(jìn)行加密，

2、得到的密文組長仍為64比特。即M= ，C= ，K= 。典型分組密碼介紹IDEAIDEA的描述加密算法.+X1(16bit)X2(16bit)X3(16bit)X4(16bit)+Y1(16bit)Y2(16bit)Y3(16bit)Y4(16bit)第i輪迭代輸出變換在前面圖示的IDEA算法中，多次對(duì)兩個(gè)16比特?cái)?shù)據(jù)塊使用了下列三種運(yùn)算：逐比特模2加， 模216加法，模216+1乘法（須將16比特全零數(shù)據(jù)看成為216）。+IDEA的描述密鑰擴(kuò)展. 各輪迭代以及輸出變換一共使用52個(gè)加密子密鑰它們依據(jù)所給128bit主密鑰K按下述方法產(chǎn)生：IDEA的描述IDEA的描述脫密過程. 采用與加密過程一

3、樣的算法，只不過須將52個(gè)加密子密鑰對(duì)應(yīng)換成以下的脫密子密鑰：在上式中，K-1K的模216+1乘法逆，即：K-1K=1；-KK的模216加法逆，即：-K K=0。+正確性. 只需對(duì)下面圖示的變換 ：證明 即可。注意到有: 。對(duì)固定的K5和K6，當(dāng)S1,S2,S3,S4分別用T1,T2,T3,T4代替時(shí)，運(yùn)算結(jié)構(gòu)的輸入U(xiǎn)1,U2不變，從而輸出V1,V2也不變。T1= S1V2T2= S2V1 T1T3=S1S3T3= S3V2 T2T4=S2S4T4= S4V1IDEA的描述+S1S2S3S4T1T2T3T4U1V1V2U2IDEA的軟件實(shí)現(xiàn)求模216加法“ ”的逆元與模216+1乘法“”的逆元

4、.對(duì)于0K216，-K其實(shí)就是K求反碼之后+1的結(jié)果；對(duì)于0K216，K-1就是K模(216+1)的逆（因216+1是素?cái)?shù)，故K模(216+1)可逆）。下面給出模逆的概念及其求法：對(duì)dZn=0,1,2,n-1，若eZn，de1(mod n)，則稱d模n可逆，并稱e為d模n的逆，記為d-1(mod n)=e。+IDEA的軟件實(shí)現(xiàn)一個(gè)有關(guān)的重要結(jié)果是：dZn模n可逆，當(dāng)且僅當(dāng)(d,n)=1。對(duì)給定的dZn，如何判定d與n互素并且求出d-1(mod n)呢？我們有所謂的輾轉(zhuǎn)相除法如下：設(shè)a0=n,a1=d，輾轉(zhuǎn)做帶余除法得ai-1=qiai+ai+1，i=1,k其中k使0=ak+1aka1。表成矩陣

5、形式：IDEA的軟件實(shí)現(xiàn)不難看出于是，可設(shè)ai=uin+vid，i=1,k。由輾轉(zhuǎn)相除過程可知，ak=(d,n)。如果(d,n)=1，則ukn+vkd=1，由此即得vkd 1(mod n)因此，d-1(mod n)=vk(mod n)?，F(xiàn)在得到求d-1(mod n)的方法如下：由n與d開始輾轉(zhuǎn)做帶余除法，直至最后除盡為止；若最后除盡時(shí)的除式不為1，則d與n不互素而d模n不可逆，結(jié)束；根據(jù)輾轉(zhuǎn)相除法的矩陣表示可求出那么，d-1(mod n)=vk(mod n)。IDEA的軟件實(shí)現(xiàn)或者，可以推導(dǎo)出求vi的遞推關(guān)系：注意到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。根據(jù)上述遞推關(guān)系可給出求d-1(mod n)的算法框圖如下頁：IDEA的軟件實(shí)現(xiàn)輸入：n,d初始化an,bd,t0,v1用帶余除法計(jì)算：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)不存在，結(jié)束。可以證明，上述算法的輸出v必然滿足：0vn 。IDEA的軟件實(shí)現(xiàn)模216+1乘法的低高算法.對(duì)于0a,b2n(n為自然數(shù))，必有注意： 對(duì)應(yīng)ab的n個(gè)最低有效位，剛好是ab右移n位的結(jié)果。證明. 存在唯一的整數(shù)q和r，使得ab=q(2n+1)+r，0r2n+1,0q2n從而ab=q2n+q+r，0q+r2n+1ID