第7章糾錯(cuò)碼與通信系統(tǒng)的保密課件

1、第7章 糾錯(cuò)碼與通信系統(tǒng)的保密 7.1 基于糾錯(cuò)碼的公鑰密碼體制 7.2 基于糾錯(cuò)碼的私鑰密碼體制 7.3 基于糾錯(cuò)碼的身份認(rèn)證 7.4 基于糾錯(cuò)碼的數(shù)字簽名 第7章 糾錯(cuò)碼與通信系統(tǒng)的保密 7.1 基于糾錯(cuò)碼的公鑰7.1 基于糾錯(cuò)碼的公鑰密碼體制 7.1.1 M公鑰密碼體制 M公鑰密碼體制是1978年McEliece利用一般線性碼的譯碼問(wèn)題是一個(gè)難解的數(shù)學(xué)問(wèn)題和Goppa碼有快速譯碼算法的特點(diǎn)，最早提出的一個(gè)基于糾錯(cuò)碼的公鑰密碼體制，簡(jiǎn)稱為M公鑰體制。該體制的公鑰是隨機(jī)產(chǎn)生的一個(gè)線性分組碼的生成陣，公鑰隱藏了線性分組碼的快速譯碼算法，它是一種局部隨機(jī)的密碼體制。下面介紹M公鑰密碼體制的加、解

2、密原理。7.1 基于糾錯(cuò)碼的公鑰密碼體制 7.1.1 M公鑰密 設(shè)G是二元（n，k，d)Goppa碼的生成矩陣，其中n2m，d2t1，kn-mt。 隨機(jī)地選取兩個(gè)二元矩陣S和P，則公鑰G為 GSGP （71） 式中：Skk階可逆矩陣； Gkn階Goppa碼生成矩陣； Pnn階置換矩陣。 設(shè)G是二元（n，k，d)Gopp 私鑰：S，G，P。加密過(guò)程： 對(duì)于任意一個(gè)明文mGF(2)k，密文加密算法如下： cmGe (72)式中：eGF(2n）上重量為t隨機(jī)矢量。 私鑰：S，G，P。加密過(guò)程： 解密過(guò)程： 收方收到一個(gè)密文c以后，計(jì)算 cP1mSGPP1ePlmSGe，因?yàn)镻是置換距陣，所以W(z)

3、W(z)t，然后利用Goppa的快速譯碼算法將其譯成mmS，密文c對(duì)應(yīng)的明文為mmS-1。則用戶收到密文c后，用自己的秘密鑰進(jìn)行解密的步驟為 （1）計(jì)算cP-1mGP-1+eP-1(mS)GeP-1； （2）對(duì)cP-1用有效的Goppa碼譯碼算法進(jìn)行譯碼譯得mS； （3）計(jì)算(mS)S-1得明文m。 解密過(guò)程： McEliece系統(tǒng)的缺點(diǎn)是密鑰長(zhǎng)度較大，數(shù)據(jù)擴(kuò)展率太大，優(yōu)點(diǎn)是對(duì)同一公鑰，一個(gè)明文可以對(duì)應(yīng)許多個(gè)密文，從而增加了從密文破譯的困難。對(duì)McEliece系統(tǒng)的破譯一方面是求出密鑰S-1，P-1，G；另一方面是由具體密文c來(lái)求對(duì)應(yīng)的明文m。由現(xiàn)有的系統(tǒng)安全性分析可知，這兩種破譯方法都未發(fā)現(xiàn)

4、有有效的算法。此系統(tǒng)還可糾正密文在傳送中發(fā)生的錯(cuò)誤，這種系統(tǒng)稱為既加密又糾錯(cuò)的系統(tǒng)。 McEliece系統(tǒng)的缺點(diǎn)是密鑰長(zhǎng) 7.1.2 N公鑰密碼體制 N公鑰密碼體制是1986年Niederreiter提出的另一個(gè)基于糾錯(cuò)碼的公鑰密碼體制，該體制是一個(gè)背包型公鑰密碼體制，簡(jiǎn)稱N公鑰密碼體制。N公鑰密碼體制的公鑰為隨機(jī)產(chǎn)生的線性分組碼的監(jiān)督陣，與M公鑰不同的是N公鑰隱藏了具有快速譯碼算法的線性分組碼的監(jiān)督陣。下面介紹這個(gè)公鑰密碼體制的加、解密原理。 7.1.2 N公鑰密碼體制 設(shè)C是有q元線性（n，k，2t1)Goppa碼，取兩個(gè)q元矩陣 M、P，則公鑰H為 HMHP （73） 式中：H碼C的(n

5、k)n監(jiān)督矩陣； Mq元(nk)(nk)非奇異矩陣； Pq元nn階置換矩陣。 私鑰：H，M，P。 設(shè)C是有q元線性（n，k，2t1 加密算法： zy(H)T (74) 式中：znk維密文；(H)TH的轉(zhuǎn)置矩陣；y重量為t的q元n維明文。 解密運(yùn)算： 由zy(MHP)T知：z(MT)1y(PT)HT，由碼的快速譯碼算法得到y(tǒng)PT，因此可以求出y。 加密算法： 7.1.3 M公鑰密碼體制與N公鑰密碼體制的關(guān)系 李元興、王新梅等于1994年在IEEE信息論匯刊上發(fā)表論文,證明了M公鑰和N公鑰密碼體制是等價(jià)的。假定M公鑰密碼體制和N公鑰密碼體制采用的是相同的（n，2t+1）線性碼C，則M密碼體制的公鑰

6、為 GS1GP （75） 式中：S1價(jià)可逆矩陣； Pnn階置換矩陣； G碼C的生成矩陣。 7.1.3 M公鑰密碼體制與N公鑰密碼體制的關(guān)系 M公鑰密碼體制的私鑰：S1，G，P。N密碼體制的公鑰為 S2HP （76） 式中：S(n-)(n-)階可逆矩陣；Pnn階可逆矩陣；碼C監(jiān)督矩陣。N公鑰密碼體制的私鑰：S2，H，P。M公鑰密碼體制中的加密方程： cmGe （77） 將方程（77）兩端乘(H)T得： zc(H)TmG(H)T e(H)Te(H)T M公鑰密碼體制的私鑰：S1，G，P 給定z和，若e能被發(fā)現(xiàn)，也就是說(shuō)若N體制被打破，則M體制被打破，即密文m可以在多項(xiàng)式時(shí)間內(nèi)被獲得。因此，破譯M體

7、制不會(huì)比破譯N體制難。N密碼體制中的加密方程： zy(H)T （78） 則在多項(xiàng)式時(shí)間里可以求得一個(gè)長(zhǎng)為n的碼字c，使得： zc(H)T （79） 又因?yàn)閏可以表示成為 cmGy （710） 式中：m一個(gè)維明文。 給定z和，若e能被發(fā)現(xiàn)，也就是說(shuō) 7.1.4 Ms公鑰密碼體制 在M公鑰密碼體制中，密文通過(guò)信道時(shí)不能有干擾。若密文通過(guò)信道時(shí)有干擾，則收端收到的密文為 ccz （711） 式中：mGe； z信道產(chǎn)生的錯(cuò)誤圖樣。 7.1.4 Ms公鑰密碼體制 這時(shí)，在解密過(guò)程中錯(cuò)誤圖樣ze的漢明重量很可能大于碼的糾錯(cuò)能力，若進(jìn)行譯碼，就得到錯(cuò)誤的碼字，這樣勢(shì)必得到與原明文不同的錯(cuò)誤明文。事實(shí)上沒(méi)有糾

8、錯(cuò)能力的所有密碼體制都存在這個(gè)問(wèn)題。接收端得到錯(cuò)誤明文后，由于看不懂明文，知道在傳輸過(guò)程中產(chǎn)生了錯(cuò)誤，可以要求對(duì)方重發(fā)，這樣就降低了通信效率，而重發(fā)又增加了通信的不安全性。王新梅給出克服上述缺點(diǎn)的另一個(gè)方法，對(duì)M公鑰進(jìn)行了修正，使其具有一定的糾錯(cuò)能力或檢錯(cuò)能力。下面介紹這種修正的M公鑰體制，即Ms公鑰體制。設(shè)明文為m，則對(duì)應(yīng)的密文為 csmGses （712） 這時(shí)，在解密過(guò)程中錯(cuò)誤圖樣ze的 式中：GsSGP；es是一個(gè)長(zhǎng)為n的二進(jìn)制隨機(jī)序列,且它的重量為 W(es)=tst 顯然，當(dāng)tst時(shí)，Ms公鑰就是M公鑰，因此M公鑰可以看成Ms公鑰的特殊情況，Ms公鑰體制可以看成是M公鑰的推廣。 式

9、中：GsSGP；es是一個(gè)長(zhǎng)為 Ms公鑰體制解密算法與M公鑰密碼體制的基本相同。所不同的是，當(dāng)密文在有擾信道中傳輸時(shí)，若信道產(chǎn)生的錯(cuò)誤圖樣e的重量(e)t-ts，則Ms公鑰體制能保證解密后所得明文的正確性，而M公鑰體制不具有這個(gè)性能。 攻擊M公鑰的有關(guān)算法都可用來(lái)攻擊Ms公鑰體制，由于tst，所以Ms公鑰體制的安全性要比M公鑰體制弱，但也有足夠的強(qiáng)度。 表71列出用（2048，1388，121）Goppa碼，取ts55時(shí)構(gòu)造的Ms公鑰體制復(fù)雜度與錯(cuò)誤個(gè)數(shù)的關(guān)系，采用的攻擊是LeeBrickell攻擊。 Ms公鑰體制解密算法與M公鑰密碼體制表71 復(fù)雜度與錯(cuò)誤的關(guān)系 表71 復(fù)雜度與錯(cuò)誤的關(guān)系

10、7.1.5 M公鑰的安全性 M密碼體制使用的是二元既約Goppa碼，Goppa碼的數(shù)量隨參數(shù)的增加而快速增加。對(duì)M公鑰密碼體制的攻擊可以歸結(jié)為下列問(wèn)題：對(duì)于一個(gè)加密矩陣G，若存在一個(gè)kk階可逆矩陣S，nn階可逆矩陣P，密碼分析者知道其快速譯碼算法的C的生成陣G，且 GSGP。若這種情況發(fā)生，M公鑰密碼體制就可被攻破。但這種情況發(fā)生的概率是很小的。下面給出M公鑰的幾種攻擊方法。 7.1.5 M公鑰的安全性 1.已知碼字的攻擊 密碼分析者隨機(jī)地選n比特密文中的k比特，k比特沒(méi)有錯(cuò)誤的概率為 與kn階矩陣G相對(duì)應(yīng)的kk階矩陣可逆的概率為qk，因此，任意取密文c的k比特，它既沒(méi)有錯(cuò)誤且對(duì)應(yīng)的kk階子矩

11、陣可逆的概率為qkpk，求一個(gè)kk階可逆矩陣逆的時(shí)間復(fù)雜度為(k3)，因此，這種攻擊的工作因子為(k3qkpk)。這是1978年McEliece給出的一種攻擊方法。 1.已知碼字的攻擊 2.錯(cuò)誤圖樣攻擊 隨機(jī)地選取kn階矩陣G的k列j1，j2，jk，且使其構(gòu)成kk階可逆矩陣Gk，令yk，zk分別表示由n維矢量y和z的第j1，j2，jk個(gè)分量構(gòu)成的k維矢量，因此ykzkmGk,(ykzk)(Gk)-1mG。取k比特碼字zk,zk的漢明重量小于等于j(jc)，若y(yk+zk)(Gk)-1 G的重量為t，則zk=zk,因此密文m(ykzk)(Gk)-1，否則選另一個(gè)k維矢量zk重復(fù)上面的步驟。若重

12、量小于等于j的k比特矢量被用完，但消息還未恢復(fù)出來(lái)，取kn階矩陣G的另一個(gè)kk階子矩陣，重復(fù)上面的步驟，直到明文m被發(fā)現(xiàn)為至。 2.錯(cuò)誤圖樣攻擊 3.最小漢明重量的碼字攻擊 設(shè)yxGz是一個(gè)接收碼字，這里G是(n，k，d)線性碼的生成矩陣，z是重量為t的錯(cuò)誤矢量;(k1)n階矩陣G/z是(n,k1，t)線性碼的生成陣。因此，發(fā)現(xiàn)一個(gè)碼的最小重量的碼字對(duì)應(yīng)于發(fā)現(xiàn)錯(cuò)誤矢量z。若有算法能發(fā)現(xiàn)一個(gè)碼的最小重量的碼字，就可被用來(lái)攻擊M體制。但發(fā)現(xiàn)一個(gè)碼的最小重量的碼字是一個(gè)NP完全問(wèn)題，因此，通過(guò)這種方法攻擊，似乎也是很困難的。 3.最小漢明重量的碼字攻擊 4.消息重發(fā)攻擊 1997年，Berson提出

13、兩種對(duì)McEliece體制的攻擊方法，即消息重發(fā)攻擊(messaGeresendattack)和相關(guān)消息攻擊(relatedmessaGeattack)?？疾榫哂腥缦聟?shù)的McEliece體制，n1024，k524，t50，下面先介紹消息重發(fā)攻擊。 4.消息重發(fā)攻擊 5.相關(guān)消息攻擊 若兩個(gè)消息m1，m2被加密，假定密碼分析者知道m(xù)1m2，那么密碼分析者知道： c1m1e1，c2m2Ge2 這里m1m2，e2e1。因此， c1c2m1e1m2Ge2 (m1m2)e1+e2由于預(yù)先知道m(xù)1m2，可計(jì)算(m1m2)G，因此， c1c2(m1m2)e1e2 5.相關(guān)消息攻擊 類似于消息重發(fā)攻擊，僅需

14、要次數(shù)比較少的猜測(cè)就能攻擊成功。消息重發(fā)攻擊可看成相關(guān)消息攻擊的特例。雖說(shuō)Berson的分析不夠嚴(yán)密，但他給出的攻擊方法從一定程度上也指出了M公鑰存在的弱點(diǎn)。 類似于消息重發(fā)攻擊，僅需要次數(shù)比較 7.1.6 M公鑰的變型 下面給出為了抗擊Berson的兩種攻擊，HunGMinSun提出的如下變型的M公鑰方案。 1.變型1 1)加密 c(m+h(e)Ge (713) 式中：e重量為t的n比特隨機(jī)矢量；h輸入為n比特、輸出為k比特的單向Hash函數(shù)。 7.1.6 M公鑰的變型 2)解密 由M公鑰的解密算法可得mh(e)，然后計(jì)算m(m+h(e)h(e)。 3)安全性 設(shè)m1和m2是兩個(gè)消息。假定m

15、1m2，則c1c2(h(e1)h(e2)Ge1e2,(h(e1)h(e2)G。由于不知道h (e1)，h(e2)，因此也不知道(h(e1)h(e2)G，密碼分析者很難確定出錯(cuò)誤位置，消息重發(fā)攻擊不會(huì)成功。 2)解密 假定密碼分析者知道m(xù)1m2的值，那么 c1c2(m1m2h(e1)+h(e2)Ge1e2 雖然密碼分析者知道m(xù)1m2的值，但不知道h(e1)，h(e2)，因此也不知道(m1m2h(e1)h(e2)G，密碼分析者很難確定出錯(cuò)誤位置，相關(guān)消息攻擊也不能成功。對(duì)M公鑰進(jìn)行以下變型，也能夠防止erson的兩種攻擊方法。 假定密碼分析者知道m(xù)1m2的值，那么 2. 變型2 1)加密 cf(m

16、，e)Ge (714) 式中：e重量為t的n比特隨機(jī)矢量；f單向函數(shù)。單向函數(shù)f滿足給定f(m，e)而確定m，e在計(jì)算上是不可行的，但在知道f(m,e)，e時(shí)，很容易計(jì)算m。 2) 解密 首先利用M公鑰的解密算法求得f(m,e)，e，然后利用f(m,e)，e求得m。 2. 變型2 7.1.7 增加M公鑰的傳信率 M公鑰的傳信率比較低，大約為0.5，因此有些學(xué)者提出了改進(jìn)M公鑰傳信率的方法。 1)加密 設(shè)消息m(ma，mb)。密文cmaGe，這里eG(mb)，G是一個(gè)將mb映射到重量為t的n比特錯(cuò)誤矢量的可逆映射。 2)解密 ma可以通過(guò)M公鑰的解密算法得到，同時(shí)也就得到了G(mb)，那么mbg

17、1g(mb)。 7.1.7 增加M公鑰的傳信率 3)信息率 通過(guò)這種方法可以改變M公鑰的信息率。例如若k524，n1024，t50時(shí)，M公鑰的信息率為0.51，變型后的M公鑰的信息率為0.79；若k654，n1024，t37時(shí)，M公鑰的信息率為0.63，變型后的M公鑰的信息率為0.87。 3)信息率 4) 安全性 變型后的M公鑰體制的基本思想與原M公鑰的基本相同，其主要差別是錯(cuò)誤矢量的隨機(jī)性問(wèn)題。變型后的M公鑰的錯(cuò)誤矢量不是真正隨機(jī)的，它由mb確定，這是一種確定性加密。 4) 安全性 設(shè)m(m1a，m1b)， m2(m2a，m2b)是兩個(gè)要加密的消息，變型后的M公鑰將消息分成兩部分，因此它也暴

18、露出如下可能的弱點(diǎn)。 （1)若知道m(xù)1a，那么，G(m1b)c1m1aG， m1bG1(G(mb)。 （2)若知道m(xù)1b，那么m1aGcG(m1b)，通過(guò)解方程，能很快算出m1a。 （3)若知道m(xù)1am2a，m1bm2b，那么e1e2， c1c2（m1am2a)Ge1e2，因此可以獲得有關(guān)錯(cuò)誤位置的一些信息。 設(shè)m(m1a，m1b)， m2( （4)若知道m(xù)1am2a，m1bm2b，那么(m1am2a)Gc1c2，因此通過(guò)解方程能很快地算出m1am2a。 （5)若知道m(xù)1am2a的值和m1bm2b，那么c1c2（m1am2a)Ge1e2，e1e2c1c2（m1a G，因此可以獲得有關(guān)錯(cuò)誤位置的

19、一些信息。 （4)若知道m(xù)1am2a，m1bm7.2 基于糾錯(cuò)碼的私鑰密碼體制 7.2.1 Rao私鑰密碼體制 Rao私鑰密碼體制是由T.R.Rao于1984年提出的一個(gè)私鑰密碼體制，其基本思想是將McEliece公鑰用于私鑰密碼體制。 1)加密 令Zz|zGF(2)n，z的漢明重量為 ，m是k比特的明文，其對(duì)應(yīng)的n比特密文c為 cmSGPz (715)7.2 基于糾錯(cuò)碼的私鑰密碼體制 7.2.1 Rao 式中：G二進(jìn)制線性Goppa碼(n，k,2t1)的生成矩陣； Skk階二元可逆矩陣； Pnn階置換矩陣； z從Z中隨機(jī)選取的n比特矢量。 私鑰：G，S，P，SGP。 2)解密 計(jì)算cPT，通

20、過(guò)譯碼得到mS，計(jì)算mSS1得明文m。 式中：G二進(jìn)制線性Goppa碼( 7.2.2 RaoNam私鑰密碼體制 從密碼分析的角度看，當(dāng)錯(cuò)誤矢量的漢明重量約等于n2時(shí)，大數(shù)表決攻擊方法不能成功。在此情況下，碼字的每個(gè)碼元被正確猜測(cè)的概率為12，這是最佳的。因此，RaoNam提出使用預(yù)先定義取自碼C不同剩余類，其漢明重量約等于n2錯(cuò)誤碼字。同時(shí)他們還提出利用簡(jiǎn)單的糾錯(cuò)碼(漢明重量小于等于6，碼長(zhǎng)最多為250比特)來(lái)獲得私鑰密碼系統(tǒng)。 設(shè)G是(n，k)Goppa碼的生成矩陣，z是一個(gè)特指的錯(cuò)誤圖樣，它的平均漢明重量大約為n2。 7.2.2 RaoNam私鑰密碼體制1)加密方法令m是k比特的明文，則密

21、文c為 c(mGz)P (716)式中：Gn階加密矩陣（GSG）；S階可逆矩陣；G漢明重量小于等于6的(n，)線性碼的生成矩陣；Pnn階置換矩陣；z隨機(jī)選取的一個(gè)錯(cuò)誤矢量。密鑰：S，P，G，H，伴隨錯(cuò)誤表。1)加密方法 2)解密方法 由加密運(yùn)算公式（716）得： c(mGz)PmSGPzPmGPzP （717）令ccPT，則 cmGz （718）由（718）得： cHTmGHTzHTzHT （719） 2)解密方法 具體解密步驟如下： (1)利用公式（718）計(jì)算c； (2)根據(jù)公式（719）計(jì)算m； (3)通過(guò)伴隨錯(cuò)誤表，可以找到z，同時(shí)可以算出mS。 (4)根據(jù)mSS-1計(jì)算明文m。 由于

22、這個(gè)私鑰密碼體制安全性在很大程度上依靠于z的選取，所以，1989年RaoNam給出了下列選取z的方法： 具體解密步驟如下： 有限域GF(2)上的n維矢量空間GF(2)n關(guān)于(n，)線性碼C有2n個(gè)陪集，每一個(gè)陪集對(duì)應(yīng)于惟一一個(gè)伴隨式，在每一個(gè)陪集中選定一個(gè)重量大約等于n2的碼字，這樣就形成2n-個(gè)重量大約等于n2的n重矢量。 有限域GF(2)上的n維矢量空間GF 7.2.3 LW私鑰密碼體制 根據(jù)RaoNam方案，李元興和王新梅提出了一個(gè)可用作加密和認(rèn)證的私鑰密碼體制。這一方案被稱為L(zhǎng)W私鑰密碼體制。 1.基本原理 假定碼率R0.5，即kn-k，則L-W體制的加、解密方法如下所述。 1)加密

23、（1)將消息m分成k比特的組。 （2)通信雙方秘密地商定一種算法，從m中選定nk比特，構(gòu)成nk比特的組m1。 7.2.3 LW私鑰密碼體制（3)將m1作為伴隨式，通過(guò)查伴隨錯(cuò)誤表找出與其對(duì)應(yīng)的n比特矢量z，zHTm1。（4)根據(jù)公式（716）計(jì)算密文c。 2)解密（1）利用公式（718）計(jì)算。（2）根據(jù)公式（719）計(jì)算m1（m1zHT）。（3)利用伴隨錯(cuò)誤表，找出錯(cuò)誤矢量z，并恢復(fù)mS。（4)根據(jù)mSS1恢復(fù)明文m。（3)將m1作為伴隨式，通過(guò)查伴隨錯(cuò)誤表找出與其對(duì)應(yīng)的n比 （5)收方利用他與發(fā)方商定的選取方法，從m中選取n比特，并與第二步算出的m1進(jìn)行比較。若傳輸中沒(méi)有錯(cuò)誤，選取的nk比特

24、與m1相等，則消息m是明文，且m被認(rèn)證。若傳輸中有錯(cuò)誤，或密文被敵手篡擾過(guò)，這時(shí)收方收到的密文是： c*cze （720） 即 c*mSGPzemSGP(zz*e)P （721） 式中:z*ezePT。 （5)收方利用他與發(fā)方商定的選取方法，從 2.一個(gè)等價(jià)方案 下面介紹的加密和解密算法等價(jià)于LW方案。先給出一個(gè)定義：令GB是(2k-n)n階二元矩陣，其右逆為G-1B，HB為GB生成的線性碼的監(jiān)督矩陣。定義集合：H(xA，y)|yxGfA(x)，xB0，xAGF（2）nk 為了便于敘述，令yH（xA）， xA H1（sB）。 2.一個(gè)等價(jià)方案 1)加密 k比特明文x對(duì)應(yīng)的n比特密文： yB(x

25、)GBH（A(x) （722） 2)解密 計(jì)算 sByHTB，xAH1(sB) xB(yH（xA）G-RB 則明文為 x1(xA)1(xB) （723） 密鑰：GB，HB，H，H1，集合A，B。 1)加密 3.安全性分析 LW私鑰密碼體制與RaoNam密碼體制的基本思想相同，其惟一的差別是此私鑰密碼體制的錯(cuò)誤矢量被用作認(rèn)證和加密兩個(gè)目的。為了便于密碼分析，1994年J.vanTilberG給出下述一個(gè)與LW方案等價(jià)的定義。 設(shè)nkk，A是在集合1，2，k中隨機(jī)的選取一個(gè)子集a1，a2，,ank，這里a1a2tA且能被譯碼器發(fā)現(xiàn)，則譯碼器發(fā)出一指令表示收到的Cj有誤，要求用戶重發(fā)簽名，若E0，則

26、譯碼器正確譯碼，得到Cj和Ej。 (3)右乘JA。 D3(Cj)CjJA (EjMSAGA)PAP-1AG*AS-1A EjG*AS-1AM （738） (2)譯碼。 (4)計(jì)算。 D4(Cj)D3(Cj)EjWA EjG*AS-1A+MEjG*AS-1AM （739） 若此時(shí)得到的M與收到的M相同，則簽名正確，否則簽名有誤。由以上討論可知，若PA是一個(gè)nn階置換矩陣，則W(E)W(EP-1A)，因而如果W(Ej)en且W*A滿足以下關(guān)系： AW*AIn （750） 簽名方法如下： 用戶A隨機(jī)地選擇一個(gè)漢明重量W(E)tA的二元n重E，以及長(zhǎng)為ln的二元隨機(jī)矢量Z，且W(Z)l2，則用戶A對(duì)消

27、息M的簽名是長(zhǎng)為l的序列 C（Ef（M，E）EG*A GA）PA ZW*AAZ (751) A把M，C，f（M，E）送給用戶B。 式中:WA秩為n的nl階矩陣 2. Xinmei修正方案 Xinmei修正方案是2000年，王新梅應(yīng)用類似于AW方案，對(duì)原來(lái)的Xinmei方案進(jìn)行修正，得到比AW方案更為簡(jiǎn)單的修正Xinmei方案。其簽名算法如下： C（Eh（M，E）SAGA）PA (753) 或 C （Eh（M，E，t）SAGA）PA，C （Eh（M，t）SAGA）PA （754） 2. Xinmei修正方案式中：h(x，y)和h(x，y，t)非線性單向Hash函數(shù)；t簽名時(shí)間；M長(zhǎng)為k的消息序列

28、；E長(zhǎng)為n的重量W(E)tA的二元隨機(jī)序列； h(M，E)、h(M，E，t)和h（M，t）長(zhǎng)為k的二元序列。式中：h(x，y)和h(x，y，t) 因此修正Xinmei方案的公鑰、私鑰及簽名算法與原Xinmei方案的相同，僅僅多了一次Hash函數(shù)h(M，Ej)或h(M，Ej，tj)的計(jì)算。 用戶A把(M，Cj)或(M，Cj，tj)送給用戶B。用戶B的驗(yàn)簽過(guò)程與原Xinmei方案的相同，這里不再重復(fù)。用戶B在驗(yàn)簽過(guò)程中得到h(M，E)或h(M，Ej，tj)和Ej后，再由收到的M和Ej計(jì)算h(M,Ej)，若 h(M,E)h(M,E j) （755） 則說(shuō)明簽名有效，否則簽名無(wú)效，要求用戶A重發(fā)簽名。

29、 因此修正Xinmei方案的公鑰、私 7.4.4 對(duì)AW方案和Xinmei方案的通用偽造攻擊 AW方案和Xinmei修正方案對(duì)AW攻擊是安全的。1994年AlabbadiM等提出了兩種對(duì)AW方案和Xinmei方案的通用偽造攻擊方法。 由Xinmei方案可知，用戶A對(duì)消息M的簽名是： C（EM SAGA）PA EPAMSAGAPA EjMQA （756） 式中：EjEPA；QASAGAPA。 7.4.4 對(duì)AW方案和Xinmei方案的通用偽造攻 若攻擊者已知QA以及至少知道任一個(gè)E j，則可用以下方法偽造簽名。設(shè)攻擊者需對(duì)消息M1偽造簽名，則僅需計(jì)算： C1EjM1QA （757） 顯然C1能通

30、過(guò)驗(yàn)簽運(yùn)算。這種偽造簽名方法對(duì)AW方案是有效的。 若攻擊者已知QA以及至少知道任一個(gè)E 可用以下方法找到QA。令Cj和Cj分別是消息Mj和Mj的簽名，Ej是這兩個(gè)簽名過(guò)程中所用的相同的錯(cuò)誤圖樣，則對(duì)于Xinmei方案有： CjCj（MjMj）Q （758） 對(duì)修正Xinmei方案有： CjCj （h（M，E）h（M，E）Q （759） 可用以下方法找到QA。令Cj和Cj分別 如果能得到k對(duì)消息的簽名：Cj，Cj(1，2，k)且每對(duì)所用的E相同，則可得： C1C1（M1 M1）QAC2C2 （M2 M2）QA CkCk（Mk Mk）QA 由此可得： CMQA （760） 如果能得到k對(duì)消息的簽名

31、：Cj，C式中： 若M矩陣為滿秩，則可以找到QAMC，其工作因子僅為(k)。因此只要找到k對(duì)線性無(wú)關(guān)的消息，且每對(duì)消息使用相同的E，就可找到QA。式中： 若M矩陣為滿秩，則可以找到QAM 由此可知，這種攻擊方法成功的關(guān)鍵是找到使用相同E的簽名C和Cj。假定用戶A在簽名過(guò)程中，E是在所有可能的錯(cuò)誤圖樣數(shù)目（761） 由此可知，這種攻擊方法成功的關(guān)鍵是找到 中等概地選取，則由生日攻擊可知，預(yù)期所需的簽名數(shù)目約為 ，就能以大于12的概率得到一對(duì)有相同E的簽名。因此這種攻擊方法成功的概率約為(762) 中等概地選取，則由生日攻擊可知，預(yù)期 7.4.5 簽名、加密和糾錯(cuò)相結(jié)合的公鑰體制 1.體制的構(gòu)造

32、用戶A和B各從GF(2)上選擇不同的 （n，k，d2t1)既約Goppa碼 A和 B。并分別公布以下公鑰： HAAPA HBP 式中:HA和HB分別是A和的監(jiān)督矩陣，PA和 P是nn階的GF(2)上不同的滿秩隨機(jī)矩陣。 7.4.5 簽名、加密和糾錯(cuò)相結(jié)合的公鑰體制 用戶A和B保留各自的私鑰:HA，PA和H，P。設(shè)A選取的消息集合SM是GF(2)上(n-k)維線性空間中的一個(gè)子集，且對(duì)任一個(gè)消息MASM，通過(guò)等式(譯碼) MAEAHTA （763） 總能很快找到一個(gè)EA，且其漢明重量W(EA)t，SM中的元素?cái)?shù)目為N。 用戶A和B保留各自的私鑰:HA，PA 用戶A和B正式通信前，A先要把SM中的

33、N個(gè)消息矢量依次按圖71，或通過(guò)安全信道送給B，B按圖72接收，則可恢復(fù)出這個(gè)矢量。A和B都秘密存儲(chǔ)SM，并約定A和B的消息空間是SM。 用戶A和B正式通信前，A先要把SM中圖71 簽名、加密和糾錯(cuò)編碼的實(shí)現(xiàn) 圖71 簽名、加密和糾錯(cuò)編碼的實(shí)現(xiàn) 圖72 糾錯(cuò)譯碼、解密和驗(yàn)簽的實(shí)現(xiàn)圖72 糾錯(cuò)譯碼、解密和驗(yàn)簽的實(shí)現(xiàn) 2.簽名、加密和糾錯(cuò)編碼的實(shí)現(xiàn) 1)簽名 用戶A將消息MASM送入A碼的譯碼器，由SM的性質(zhì)可知，MA經(jīng)過(guò)譯碼后必然惟一地得到EA，且W(EA)t，即 MAEAHTA (764) 對(duì)EA右乘(PTA)PA，便得到了對(duì)MA的簽名EA： EAEAPA (765) 2.簽名、加密和糾錯(cuò)編碼的實(shí)現(xiàn) 2) 加密 A利用HB的轉(zhuǎn)置矩陣(HB)T，對(duì)EA右乘運(yùn)算，得到(n-k)維矢量： SAEA(HB)T (766) 2) 加密 3) 糾錯(cuò)編碼 A把HB看作是A碼的對(duì)偶碼B的生成矩陣。由對(duì)偶碼