密碼學(xué)原理與實踐答案

密碼學(xué)原理與實踐答案1.1幾個簡單的密碼體制注：小寫代表明文，大寫代表密文分組密碼：單表代換密碼：移位密碼，代換密碼，仿射密碼?多表代換密碼：維吉尼亞密碼，希爾密碼?非代換密碼：置換密碼流密碼：同步流密碼，異步流密碼1.1.1移位密碼密碼體制：令P=C=K=Z26P=C=K=Z_{26}P=C=K=Z26?有eK(x)=(x+K)mod26dK(y)=(x?K)mod26e_{K}(x)=(x+K)mod26\quadd_K(y)=(x-K)mod26eK?(x)=(x+K)mod26dK?(y)=(x?K)mod26并且當(dāng)K=3時叫凱撒密碼。密鑰空間為261.1.2代換密碼密碼體制：令P=C=Z26P=C=Z_{26}P=C=Z26?對任意的置換π∈K\pi\inKπ∈K，有eπ(x)=π(x)dπ(y)=π?1(y)e_{\pi}(x)=\pi(x)\quadd_{\pi}(y)=\pi^{-1}(y)eπ?(x)=π(x)dπ?(y)=π?1(y)。密鑰空間為26!26!26!1.1.3仿射密碼加密函數(shù)形式：e(x)=(ax+b)mod26e(x)=(ax+b)mod26e(x)=(ax+b)mod26，要求仿射函數(shù)必須是單射，也就是同余方程ax≡y(mod26)ax\equivy(mod26)ax≡y(mod26)有唯一解。上述同余方程有唯一解?gcd(a,26)=1\Leftrightarrowgcd(a,26)=1?gcd(a,26)=1，證明略。此時a的取值為0~25之間與26互素的數(shù)，共12個，b的取值為0~25。這時密鑰空間為312。將m推進到一般值，（記?(m)\phi(m)?(m)為ZmZ_{m}Zm?中與m互素的個數(shù)），此時密鑰空間大小為m??(m)m*\phi(m)m??(m)，由數(shù)論可知?(m)\phi(m)?(m)的計算公式如下：對?m，一定存在m=∏i=1npiei,則?(m)=∏i=1n(piei?piei?1)對\forallm，一定存在m=\prod_{i=1}^{n}{p_i^{e_i}},則\phi(m)=\prod_{i=1}^n({p_i^{e_i}-p_i^{e_i-1}})對?m，一定存在m=∏i=1n?piei??,則?(m)=∏i=1n?(piei???piei??1?)下面討論解密函數(shù)。易知當(dāng)且僅當(dāng)gcd(a,m)=1gcd(a,m)=1gcd(a,m)=1，a在ZmZ_mZm?上存在唯一的乘法逆。記aaa的乘法逆為a?1a^{-1}a?1。則有d(y)=a?1(y?b)mod26d(y)=a^{-1}(y-b)mod26d(y)=a?1(y?b)mod26綜上，仿射密碼體制：令P=C=Z26，且K={(a,b)∈Z26×Z26;gcd(a,26)=1}eK(x)=(ax+b)mod26;dK(y)=a?1(y?b)mod26令P=C=Z_{26}，且K=\{(a,b)\inZ_{26}\timesZ_{26};gcd(a,26)=1\}\\e_{K}(x)=(ax+b)mod26;\quadd_{K}(y)=a^{-1}(y-b)mod26令P=C=Z26?，且K={(a,b)∈Z26?×Z26?;gcd(a,26)=1}eK?(x)=(ax+b)mod26;dK?(y)=a?1(y?b)mod261.1.4維吉尼亞密碼密碼體制：令P=C=K=(Z26)m，對任意的密鑰K=(k1,k2,...,km)，有ek(x1,x2,...,xm)=(x1+k1,x2+k2,...,xm+km)dk(y1,y2,...,ym)=(y1?k1,y2?k2,...,ym?km)令P=C=K=(Z_{26})^m，對任意的密鑰K=(k_1,k_2,...,k_m)，\\有e_k(x_1,x_2,...,x_m)=(x_1+k_1,x_2+k_2,...,x_m+k_m)\\d_k(y_1,y_2,...,y_m)=(y_1-k_1,y_2-k_2,...,y_m-k_m)令P=C=K=(Z26?)m，對任意的密鑰K=(k1?,k2?,...,km?)，有ek?(x1?,x2?,...,xm?)=(x1?+k1?,x2?+k2?,...,xm?+km?)dk?(y1?,y2?,...,ym?)=(y1??k1?,y2??k2?,...,ym??km?)一次加密m個字母。密鑰空間大小為26m26^m26m1.1.5希爾密碼在對明文采用線型加密的同時采用一次加密m個字母的方式。將全部m個明文分別用m組不同的權(quán)重線型加權(quán)得到密文。因此密鑰空間大小為m?mm*mm?m，一般采用矩陣的形式，記為K=(ki,j)，加密過程為y=xK，解密過程為x=yK?1K=(k_{i,j})，加密過程為y=xK，解密過程為x=yK^{-1}K=(ki,j?)，加密過程為y=xK，解密過程為x=yK?1。要求矩陣KKK可逆，矩陣K在模26的情形下可逆?gcd(detK,26)=1矩陣K在模26的情形下可逆\Leftrightarrowgcd(detK,26)=1矩陣K在模26的情形下可逆?gcd(detK,26)=1，證明略。密碼體制：令P=C=(Z26)m,(m?2)，K={定義在Z26上的m×m可逆矩陣}有eK(x)=xKdK(y)=yK?1令P=C=(Z_{26})^m,(m\geqslant2)，K=\{定義在Z_{26}上的m\timesm可逆矩陣\}\\有e_K(x)=xK\\d_K(y)=yK^{-1}令P=C=(Z26?)m,(m?2)，K={定義在Z26?上的m×m可逆矩陣}有eK?(x)=xKdK?(y)=yK?11.1.6置換密碼只改變明文中字母的位置，加密函數(shù)是雙射。密碼體制：令P=C=(Z26)m，K由所有定義在集合{1,2,...,m}上的置換組成，有ek(x1,x2,...,xm)=(xπ(1),xπ(2),...,xπ(m))dk(y1,y2,...,ym)=(yπ?1(1),yπ?1(2),...,yπ?1(m))令P=C=(Z_{26})^m，K由所有定義在集合\{1,2,...,m\}上的置換組成，\\有e_k(x_1,x_2,...,x_m)=(x_{\pi(1)},x_{\pi(2)},...,x_{\pi(m)})\\d_k(y_1,y_2,...,y_m)=(y_{\pi^{-1}(1)},y_{\pi^{-1}(2)},...,y_{\pi^{-1}(m)})令P=C=(Z26?)m，K由所有定義在集合{1,2,...,m}上的置換組成，有ek?(x1?,x2?,...,xm?)=(xπ(1)?,xπ(2)?,...,xπ(m)?)dk?(y1?,y2?,...,ym?)=(yπ?1(1)?,yπ?1(2)?,...,yπ?1(m)?)置換密碼是希爾密碼的特殊形式，很容易找到置換π\(zhòng)piπ的關(guān)聯(lián)置換矩陣KπK_{\pi}Kπ?，且Kπ?1=Kπ?1K_{\pi^{-1}}=K_{\pi}^{-1}Kπ?1?=Kπ?1?。1.1.7流密碼同步流密碼（密鑰流與明文無關(guān)）通過密鑰生成器流和初始密鑰KKK生成和明文長度一致的密鑰流z=z1z2...z=z_1z_2...z=z1?z2?...，密鑰流中的每個元素ziz_izi?都對應(yīng)一套加密和解密規(guī)則，然后用密鑰流中對應(yīng)位置的密鑰元素分別對明文進行加密得到密文。如果始終存在zi+d=ziz_{i+d}=z_izi+d?=zi?，那么稱該流密碼為周期為ddd的周期流密碼。流密碼通常以二元字符表示。一種產(chǎn)生密鑰流的方法：給定2m個值k1,k2,...,km,c0,c2,...cm?1∈Z2，令zi+m=∑j=0m?1cjzi+jmod2給定2m個值k_1,k_2,...,k_m,c_0,c_2,...c_{m-1}\inZ_2，令z_{i+m}=\sum_{j=0}^{m-1}c_jz_{i+j}mod2給定2m個值k1?,k2?,...,km?,c0?,c2?,...cm?1?∈Z2?，令zi+m?=∑j=0m?1?cj?zi+j?mod2。在這種方法下通過選擇合適的cic_ici?可以使任意非零初始向量(k1,k2,...km)(k_1,k_2,...k_m)(k1?,k2?,...km?)產(chǎn)生周期為2m?12^m-12m?1的密鑰流。這種密鑰流可以利用線性反饋移位器（LFSR）用硬件方式實現(xiàn)。異步流密碼（密鑰流與明文有關(guān)）根據(jù)明文生成密鑰流，可能出現(xiàn)密鑰空間較小不安全的問題。1.2密碼分析幾種攻擊模型：唯密文攻擊，已知明文攻擊，選擇明文攻擊，選擇密文攻擊在唯密文攻擊中，根據(jù)不同英文字母在大樣本下的出現(xiàn)頻率不同，可以結(jié)合這點進行攻擊。1.2.1仿射密碼分析通過計算密文中各個字母出現(xiàn)的頻率（數(shù)）推測明文字母與密文字母的映射關(guān)系，利用兩對推測的映射關(guān)系解二元一次方程組得到a,ba,ba,b，要注意對aaa進行是否滿足gcd(a,26)=1gcd(a,26)=1gcd(a,26)=1的驗證，不滿足的話說明映射關(guān)系推測錯誤，需要重新推測。1.2.2代換密碼分析代換密碼比仿射密碼復(fù)雜，但同樣是依據(jù)字母出現(xiàn)的頻率（數(shù)），同時結(jié)合兩個字母組合以及三個字母組合的頻率（數(shù)）來推斷所有字母的映射關(guān)系。1.2.3維吉尼亞密碼分析首先要確定密鑰長度m的值kasiski測試法：找到長度至少為3的相同密文段，記下每個密文段到起始點密文段的距離δi\delta_iδi?，則可以猜測m為δi\delta_iδi?最大公因子的因子。重合指數(shù)法：重合指數(shù)Ic(x)I_c(x)Ic?(x)定義：對于長度為n的串x=x1x2...xnx=x_1x_2...x_nx=x1?x2?...xn?，Ic(x)I_c(x)Ic?(x)是xxx中兩個隨機元素相同的概率。設(shè)f0,f1,...,f25f_0,f_1,...,f_{25}f0?,f1?,...,f25?分別為A,B,...,ZA,B,...,ZA,B,...,Z在xxx中出現(xiàn)的頻數(shù)，則$I_c(x)=\frac{\sum_{i=0}{25}C_{f_i}2}{C_n^2}$對于英文文本串xxx而言，設(shè)p0,p1,...,p25p_0,p_1,...,p_{25}p0?,p1?,...,p25?分別為字母A,B,...,ZA,B,...,ZA,B,...,Z出現(xiàn)的期望概率，則Ic(x)≈∑i=025pi2=0.065I_c(x)\approx\sum_{i=0}^{25}p_i^2=0.065Ic?(x)≈∑i=025?pi2?=0.065對維吉尼亞密文串y=y1y2...yny=y_1y_2...y_ny=y1?y2?...yn?而言，每隔m個字母取出一個字母，這樣將其分割成m個等長子串，即y1=y1ym+1y2m+1...y^1=y_1