第7章纠错码与通信系统的保密课件.ppt

《第7章纠错码与通信系统的保密课件.ppt》由会员分享，可在线阅读，更多相关《第7章纠错码与通信系统的保密课件.ppt（116页珍藏版）》请在三一办公上搜索。

1、第7章 纠错码与通信系统的保密,7.1 基于纠错码的公钥密码体制 7.2 基于纠错码的私钥密码体制 7.3 基于纠错码的身份认证 7.4 基于纠错码的数字签名,第7章 纠错码与通信系统的保密 7.1 基于纠错码的公钥,7.1 基于纠错码的公钥密码体制,7.1.1 M公钥密码体制 M公钥密码体制是1978年McEliece利用一般线性码的译码问题是一个难解的数学问题和Goppa码有快速译码算法的特点，最早提出的一个基于纠错码的公钥密码体制，简称为M公钥体制。该体制的公钥是随机产生的一个线性分组码的生成阵，公钥隐藏了线性分组码的快速译码算法，它是一种局部随机的密码体制。下面介绍M公钥密码体制的加、

2、解密原理。,7.1 基于纠错码的公钥密码体制 7.1.1 M公钥密,设G是二元（n，k，d)Goppa码的生成矩阵，其中n2m，d2t1，kn-mt。随机地选取两个二元矩阵S和P，则公钥G为 GSGP（71）式中：Skk阶可逆矩阵；Gkn阶Goppa码生成矩阵；Pnn阶置换矩阵。,设G是二元（n，k，d)Gopp,私钥：S，G，P。加密过程：对于任意一个明文mGF(2)k，密文加密算法如下：cmGe(72)式中：eGF(2n）上重量为t随机矢量。,私钥：S，G，P。加密过程：,解密过程：收方收到一个密文c以后，计算 cP1mSGPP1ePlmSGe，因为P是置换距阵，所以W(z)W(z)t，然

3、后利用Goppa的快速译码算法将其译成mmS，密文c对应的明文为mmS-1。则用户收到密文c后，用自己的秘密钥进行解密的步骤为（1）计算cP-1mGP-1+eP-1(mS)GeP-1；（2）对cP-1用有效的Goppa码译码算法进行译码译得mS；（3）计算(mS)S-1得明文m。,解密过程：,McEliece系统的缺点是密钥长度较大，数据扩展率太大，优点是对同一公钥，一个明文可以对应许多个密文，从而增加了从密文破译的困难。对McEliece系统的破译一方面是求出密钥S-1，P-1，G；另一方面是由具体密文c来求对应的明文m。由现有的系统安全性分析可知，这两种破译方法都未发现有有效的算法。此系统

4、还可纠正密文在传送中发生的错误，这种系统称为既加密又纠错的系统。,McEliece系统的缺点是密钥长,7.1.2 N公钥密码体制 N公钥密码体制是1986年Niederreiter提出的另一个基于纠错码的公钥密码体制，该体制是一个背包型公钥密码体制，简称N公钥密码体制。N公钥密码体制的公钥为随机产生的线性分组码的监督阵，与M公钥不同的是N公钥隐藏了具有快速译码算法的线性分组码的监督阵。下面介绍这个公钥密码体制的加、解密原理。,7.1.2 N公钥密码体制,设C是有q元线性（n，k，2t1)Goppa码，取两个q元矩阵 M、P，则公钥H为 HMHP（73）式中：H码C的(nk)n监督矩阵；Mq元(

5、nk)(nk)非奇异矩阵；Pq元nn阶置换矩阵。私钥：H，M，P。,设C是有q元线性（n，k，2t1,加密算法：zy(H)T(74)式中：znk维密文；(H)TH的转置矩阵；y重量为t的q元n维明文。解密运算：由zy(MHP)T知：z(MT)1y(PT)HT，由码的快速译码算法得到yPT，因此可以求出y。,加密算法：,7.1.3 M公钥密码体制与N公钥密码体制的关系 李元兴、王新梅等于1994年在IEEE信息论汇刊上发表论文,证明了M公钥和N公钥密码体制是等价的。假定M公钥密码体制和N公钥密码体制采用的是相同的（n，2t+1）线性码C，则M密码体制的公钥为 GS1GP（75）式中：S1价可逆矩

6、阵；Pnn阶置换矩阵；G码C的生成矩阵。,7.1.3 M公钥密码体制与N公钥密码体制的关系,M公钥密码体制的私钥：S1，G，P。N密码体制的公钥为 S2HP（76）式中：S(n-)(n-)阶可逆矩阵；Pnn阶可逆矩阵；码C监督矩阵。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能被发现，也就是说若N体制被打破，则M体制被打破，即密文m可以在多项式时间内被获得。因此，破译M体制不会比破译N体制难。N密码体制中的加密方程：zy(H)T（

7、78）则在多项式时间里可以求得一个长为n的码字c，使得：zc(H)T（79）又因为c可以表示成为 cmGy（710）式中：m一个维明文。,给定z和，若e能被发现，也就是说,7.1.4 Ms公钥密码体制 在M公钥密码体制中，密文通过信道时不能有干扰。若密文通过信道时有干扰，则收端收到的密文为 ccz（711）式中：mGe；z信道产生的错误图样。,7.1.4 Ms公钥密码体制,这时，在解密过程中错误图样ze的汉明重量很可能大于码的纠错能力，若进行译码，就得到错误的码字，这样势必得到与原明文不同的错误明文。事实上没有纠错能力的所有密码体制都存在这个问题。接收端得到错误明文后，由于看不懂明文，知道在传

8、输过程中产生了错误，可以要求对方重发，这样就降低了通信效率，而重发又增加了通信的不安全性。王新梅给出克服上述缺点的另一个方法，对M公钥进行了修正，使其具有一定的纠错能力或检错能力。下面介绍这种修正的M公钥体制，即Ms公钥体制。设明文为m，则对应的密文为 csmGses（712）,这时，在解密过程中错误图样ze的,式中：GsSGP；es是一个长为n的二进制随机序列,且它的重量为 W(es)=tst 显然，当tst时，Ms公钥就是M公钥，因此M公钥可以看成Ms公钥的特殊情况，Ms公钥体制可以看成是M公钥的推广。,式中：GsSGP；es是一个长为,Ms公钥体制解密算法与M公钥密码体制的基本相同。所不

9、同的是，当密文在有扰信道中传输时，若信道产生的错误图样e的重量(e)t-ts，则Ms公钥体制能保证解密后所得明文的正确性，而M公钥体制不具有这个性能。攻击M公钥的有关算法都可用来攻击Ms公钥体制，由于tst，所以Ms公钥体制的安全性要比M公钥体制弱，但也有足够的强度。表71列出用（2048，1388，121）Goppa码，取ts55时构造的Ms公钥体制复杂度与错误个数的关系，采用的攻击是LeeBrickell攻击。,Ms公钥体制解密算法与M公钥密码体制,表71 复杂度与错误的关系,表71 复杂度与错误的关系,7.1.5 M公钥的安全性 M密码体制使用的是二元既约Goppa码，Goppa码的数量

10、随参数的增加而快速增加。对M公钥密码体制的攻击可以归结为下列问题：对于一个加密矩阵G，若存在一个kk阶可逆矩阵S，nn阶可逆矩阵P，密码分析者知道其快速译码算法的C的生成阵G，且 GSGP。若这种情况发生，M公钥密码体制就可被攻破。但这种情况发生的概率是很小的。下面给出M公钥的几种攻击方法。,7.1.5 M公钥的安全性,1.已知码字的攻击 密码分析者随机地选n比特密文中的k比特，k比特没有错误的概率为 与kn阶矩阵G相对应的kk阶矩阵可逆的概率为qk，因此，任意取密文c的k比特，它既没有错误且对应的kk阶子矩阵可逆的概率为qkpk，求一个kk阶可逆矩阵逆的时间复杂度为(k3)，因此，这种攻击的

11、工作因子为(k3qkpk)。这是1978年McEliece给出的一种攻击方法。,1.已知码字的攻击,2.错误图样攻击 随机地选取kn阶矩阵G的k列j1，j2，jk，且使其构成kk阶可逆矩阵Gk，令yk，zk分别表示由n维矢量y和z的第j1，j2，jk个分量构成的k维矢量，因此ykzkmGk,(ykzk)(Gk)-1mG。取k比特码字zk,zk的汉明重量小于等于j(jc)，若y(yk+zk)(Gk)-1 G的重量为t，则zk=zk,因此密文m(ykzk)(Gk)-1，否则选另一个k维矢量zk重复上面的步骤。若重量小于等于j的k比特矢量被用完，但消息还未恢复出来，取kn阶矩阵G的另一个kk阶子矩阵

12、，重复上面的步骤，直到明文m被发现为至。,2.错误图样攻击,3.最小汉明重量的码字攻击 设yxGz是一个接收码字，这里G是(n，k，d)线性码的生成矩阵，z是重量为t的错误矢量;(k1)n阶矩阵G/z是(n,k1，t)线性码的生成阵。因此，发现一个码的最小重量的码字对应于发现错误矢量z。若有算法能发现一个码的最小重量的码字，就可被用来攻击M体制。但发现一个码的最小重量的码字是一个NP完全问题，因此，通过这种方法攻击，似乎也是很困难的。,3.最小汉明重量的码字攻击,4.消息重发攻击 1997年，Berson提出两种对McEliece体制的攻击方法，即消息重发攻击(messaGeresendatt

13、ack)和相关消息攻击(relatedmessaGeattack)。考查具有如下参数的McEliece体制，n1024，k524，t50，下面先介绍消息重发攻击。,4.消息重发攻击,5.相关消息攻击 若两个消息m1，m2被加密，假定密码分析者知道m1m2，那么密码分析者知道：c1m1e1，c2m2Ge2 这里m1m2，e2e1。因此，c1c2m1e1m2Ge2(m1m2)e1+e2由于预先知道m1m2，可计算(m1m2)G，因此，c1c2(m1m2)e1e2,5.相关消息攻击,类似于消息重发攻击，仅需要次数比较少的猜测就能攻击成功。消息重发攻击可看成相关消息攻击的特例。虽说Berson的分析不

14、够严密，但他给出的攻击方法从一定程度上也指出了M公钥存在的弱点。,类似于消息重发攻击，仅需要次数比较,7.1.6 M公钥的变型 下面给出为了抗击Berson的两种攻击，HunGMinSun提出的如下变型的M公钥方案。1.变型1 1)加密 c(m+h(e)Ge(713)式中：e重量为t的n比特随机矢量；h输入为n比特、输出为k比特的单向Hash函数。,7.1.6 M公钥的变型,2)解密 由M公钥的解密算法可得mh(e)，然后计算m(m+h(e)h(e)。3)安全性 设m1和m2是两个消息。假定m1m2，则c1c2(h(e1)h(e2)Ge1e2,(h(e1)h(e2)G。由于不知道h(e1)，h

15、(e2)，因此也不知道(h(e1)h(e2)G，密码分析者很难确定出错误位置，消息重发攻击不会成功。,2)解密,假定密码分析者知道m1m2的值，那么 c1c2(m1m2h(e1)+h(e2)Ge1e2 虽然密码分析者知道m1m2的值，但不知道h(e1)，h(e2)，因此也不知道(m1m2h(e1)h(e2)G，密码分析者很难确定出错误位置，相关消息攻击也不能成功。对M公钥进行以下变型，也能够防止erson的两种攻击方法。,假定密码分析者知道m1m2的值，那么,2.变型2 1)加密 cf(m，e)Ge(714)式中：e重量为t的n比特随机矢量；f单向函数。单向函数f满足给定f(m，e)而确定m，

16、e在计算上是不可行的，但在知道f(m,e)，e时，很容易计算m。2)解密 首先利用M公钥的解密算法求得f(m,e)，e，然后利用f(m,e)，e求得m。,2.变型2,7.1.7 增加M公钥的传信率 M公钥的传信率比较低，大约为0.5，因此有些学者提出了改进M公钥传信率的方法。1)加密 设消息m(ma，mb)。密文cmaGe，这里eG(mb)，G是一个将mb映射到重量为t的n比特错误矢量的可逆映射。2)解密 ma可以通过M公钥的解密算法得到，同时也就得到了G(mb)，那么mbg1g(mb)。,7.1.7 增加M公钥的传信率,3)信息率 通过这种方法可以改变M公钥的信息率。例如若k524，n102

17、4，t50时，M公钥的信息率为0.51，变型后的M公钥的信息率为0.79；若k654，n1024，t37时，M公钥的信息率为0.63，变型后的M公钥的信息率为0.87。,3)信息率,4)安全性 变型后的M公钥体制的基本思想与原M公钥的基本相同，其主要差别是错误矢量的随机性问题。变型后的M公钥的错误矢量不是真正随机的，它由mb确定，这是一种确定性加密。,4)安全性,设m(m1a，m1b)，m2(m2a，m2b)是两个要加密的消息，变型后的M公钥将消息分成两部分，因此它也暴露出如下可能的弱点。（1)若知道m1a，那么，G(m1b)c1m1aG，m1bG1(G(mb)。（2)若知道m1b，那么m1a

18、GcG(m1b)，通过解方程，能很快算出m1a。（3)若知道m1am2a，m1bm2b，那么e1e2，c1c2（m1am2a)Ge1e2，因此可以获得有关错误位置的一些信息。,设m(m1a，m1b)，m2(,（4)若知道m1am2a，m1bm2b，那么(m1am2a)Gc1c2，因此通过解方程能很快地算出m1am2a。（5)若知道m1am2a的值和m1bm2b，那么c1c2（m1am2a)Ge1e2，e1e2c1c2（m1a G，因此可以获得有关错误位置的一些信息。,（4)若知道m1am2a，m1bm,7.2 基于纠错码的私钥密码体制,7.2.1 Rao私钥密码体制 Rao私钥密码体制是由T.

19、R.Rao于1984年提出的一个私钥密码体制，其基本思想是将McEliece公钥用于私钥密码体制。1)加密 令Zz|zGF(2)n，z的汉明重量为，m是k比特的明文，其对应的n比特密文c为 cmSGPz(715),7.2 基于纠错码的私钥密码体制 7.2.1 Rao,式中：G二进制线性Goppa码(n，k,2t1)的生成矩阵；Skk阶二元可逆矩阵；Pnn阶置换矩阵；z从Z中随机选取的n比特矢量。私钥：G，S，P，SGP。2)解密 计算cPT，通过译码得到mS，计算mSS1得明文m。,式中：G二进制线性Goppa码(,7.2.2 RaoNam私钥密码体制 从密码分析的角度看，当错误矢量的汉明重量

20、约等于n2时，大数表决攻击方法不能成功。在此情况下，码字的每个码元被正确猜测的概率为12，这是最佳的。因此，RaoNam提出使用预先定义取自码C不同剩余类，其汉明重量约等于n2错误码字。同时他们还提出利用简单的纠错码(汉明重量小于等于6，码长最多为250比特)来获得私钥密码系统。设G是(n，k)Goppa码的生成矩阵，z是一个特指的错误图样，它的平均汉明重量大约为n2。,7.2.2 RaoNam私钥密码体制,1)加密方法令m是k比特的明文，则密文c为 c(mGz)P(716)式中：Gn阶加密矩阵（GSG）；S阶可逆矩阵；G汉明重量小于等于6的(n，)线性码的生成矩阵；Pnn阶置换矩阵；z随机选

21、取的一个错误矢量。密钥：S，P，G，H，伴随错误表。,1)加密方法,2)解密方法 由加密运算公式（716）得：c(mGz)PmSGPzPmGPzP（717）令ccPT，则 cmGz（718）由（718）得：cHTmGHTzHTzHT（719）,2)解密方法,具体解密步骤如下：(1)利用公式（718）计算c；(2)根据公式（719）计算m；(3)通过伴随错误表，可以找到z，同时可以算出mS。(4)根据mSS-1计算明文m。由于这个私钥密码体制安全性在很大程度上依靠于z的选取，所以，1989年RaoNam给出了下列选取z的方法：,具体解密步骤如下：,有限域GF(2)上的n维矢量空间GF(2)n关于

22、(n，)线性码C有2n个陪集，每一个陪集对应于惟一一个伴随式，在每一个陪集中选定一个重量大约等于n2的码字，这样就形成2n-个重量大约等于n2的n重矢量。,有限域GF(2)上的n维矢量空间GF,7.2.3 LW私钥密码体制 根据RaoNam方案，李元兴和王新梅提出了一个可用作加密和认证的私钥密码体制。这一方案被称为LW私钥密码体制。1.基本原理 假定码率R0.5，即kn-k，则L-W体制的加、解密方法如下所述。1)加密（1)将消息m分成k比特的组。（2)通信双方秘密地商定一种算法，从m中选定nk比特，构成nk比特的组m1。,7.2.3 LW私钥密码体制,（3)将m1作为伴随式，通过查伴随错误表

23、找出与其对应的n比特矢量z，zHTm1。（4)根据公式（716）计算密文c。2)解密（1）利用公式（718）计算。（2）根据公式（719）计算m1（m1zHT）。（3)利用伴随错误表，找出错误矢量z，并恢复mS。（4)根据mSS1恢复明文m。,（3)将m1作为伴随式，通过查伴随错误表找出与其对应的n比,（5)收方利用他与发方商定的选取方法，从m中选取n比特，并与第二步算出的m1进行比较。若传输中没有错误，选取的nk比特与m1相等，则消息m是明文，且m被认证。若传输中有错误，或密文被敌手篡扰过，这时收方收到的密文是：c*cze（720）即 c*mSGPzemSGP(zz*e)P（721）式中:z

24、*ezePT。,（5)收方利用他与发方商定的选取方法，从,2.一个等价方案 下面介绍的加密和解密算法等价于LW方案。先给出一个定义：令GB是(2k-n)n阶二元矩阵，其右逆为G-1B，HB为GB生成的线性码的监督矩阵。定义集合：H(xA，y)|yxGfA(x)，xB0，xAGF（2）nk 为了便于叙述，令yH（xA），xA H1（sB）。,2.一个等价方案,1)加密 k比特明文x对应的n比特密文：yB(x)GBH（A(x)（722）2)解密 计算 sByHTB，xAH1(sB)xB(yH（xA）G-RB 则明文为 x1(xA)1(xB)（723）密钥：GB，HB，H，H1，集合A，B。,1)加

25、密,3.安全性分析 LW私钥密码体制与RaoNam密码体制的基本思想相同，其惟一的差别是此私钥密码体制的错误矢量被用作认证和加密两个目的。为了便于密码分析，1994年J.vanTilberG给出下述一个与LW方案等价的定义。设nkk，A是在集合1，2，k中随机的选取一个子集a1，a2，,ank，这里a1a2an-k，k比特矢量x的一个子矢量定义为（724）,3.安全性分析,定义函数fA：fA(x)z，zZ，zHTA(x)（725）式中：xk比特明文；Z错误矢量集；fA(x)错误选择函数。设C是一个二元(n，k)线性码，G是码C的生成阵，其右逆是GR。H是码C的监督阵。fA是错误选择函数，T是伴

26、随错误表，T(zHT,z)|zZ。,定义函数fA：,密钥:矩阵G，H，错误选择函数fA(x)加密:k比特明文x被加密成n比特密文y：yxGfA(x)（726）解密:计算yHTA(x)，查伴随错误表，得到fA(x)，明文x(xG)GR(或通过译码得到明文x)。,密钥:矩阵G，H，错误选择函数fA(,定理71 在LW密码系统中，设y i，yj，yij分别是明文xi，xj,xi xj对应的密文，则 yiyjyijC（727）证明 因为A是线性函数，则(yiyjyij)HT(fA(xi)fA(xj)fA(xixj)HT A(xi)A(xj)A(xixj)0 所以 yiyjyijC,定理71 在LW密码

27、系统中，设y,4.计算E的方法 在LW密码方案中，可以找到和G等价的矩阵E。由于任意k个线性无关的码字都能被用作构造码的生成阵，因此下面的算法计算出一个矩阵E，它生成的码与加密矩阵G生成的码相同。（1)随机地选取两个不同的明文xi，xj,分别加密获得不同的密文yi，yj，yij。（2)计算码字cyiyjyij。（3)重复（1)，（2)步，直到找到k个线性无关的码字(c1，c2,ck)。（4)令E(cT1,cT2,cTk)T。,4.计算E的方法,5.获得A的方法 在LW方案中，下面两步可以获得集合A和私钥矩阵G的2k-n行。（1)定义A，随机选取一个明文x，加密成yxGfA(x)，计算伴随式sy

28、DT。（2)对于任意的i（1ik），将明文xuj加密，获得其对应的密文：yi(xui)GfA(xui)（728）计算伴随式：siyiDT。,5.获得A的方法,在获得G的2k-n行后，通过下列方法能找到一个与LW方案等价的私钥矩阵。令B1，2，k-A，x是k比特矢量，xAA(x)，xBB(x)，码字(xAxB)是码字x的坐标置换形式。定义集合 H(xA，y)：yxGfA(x)，xB0，xAGF(2n-k)。,在获得G的2k-n行后，通过下列方,给定xB0，矢量xA决定了fA(x)和y。令集合H中的yH(xA)，将矩阵G分列成GA，GB两个子矩阵，使得：yxGfA（x）A(x)GAB(x)GBfA

29、（x）（729）式中：GBG的子矩阵。yB(x)GBH(A(x)通过解方程GBHTB O2k-n，2(n-k)得到校验矩阵HB。,给定xB0，矢量xA决定了fA(x,7.2.4 MC分组加密纠错体制 私钥密码体制用于实际信道时也存在纠错问题。RaoNam私钥体制没有纠错能力。王新梅教授在1986年提出了具有纠错能力的私钥密码体制。这一方案的思想是建立在M公钥密码体制基础上的，基本思想是对明文先进行纠错编码，再采用分组密码加密。,7.2.4 MC分组加密纠错体制,1.MC体制的基本原理 收方和发方随机的选取有限域GF(2)上(n，k，2n1)Goppa码的生成矩阵G，nn阶置换阵P，n比特的随机

30、序列z，并将其作为它们的私钥。发方将要传送的密文分成k比特的组，假定其中一组为m。密钥：码C的生成矩阵G，置换矩阵P，伪随机序列z。加密：k比特的源文m对应的密文为 c(mGz)P(730),1.MC体制的基本原理,密文c经过有扰信道传送给收方，收方收到的便是ce，其中e为错误图样。解密步骤：（1)计算(c+e)PTmGzePT;（2)计算(ce)PTzmGePT;（3)将mGePT译码得到密文m。,密文c经过有扰信道传送给收方，收方,2.MC体制的安全性分析 因为MC密码体制的密钥由三部分组成:(n，k，2t1)Goppa码的生成矩阵G、置换矩阵P和随机序列z。如果密码分析者知道随机序列z，

31、则密码分析者能通过“选择明、密文对攻击”获得码的生成阵G，和置换阵P，因此它的安全性很大程度上由随机序列z提供。若选择的随机序列是安全的，那么MC密码体制是安全的。,2.MC体制的安全性分析,对于一般未加纠错码的密码体制，特别是分组密码体制的密文，在传输过程中的每一个错误，必将产生不正确解密。但是MC加密纠错体制具有纠错能力，因此它的正确解密的概率远比其他的体制高。MC密码体制中，纠错码使用的是Goppa码，事实上，也可以用其他的码，如级连码、乘积码、RS码等，从而使这些码构造的密码能在强干扰信道中应用，且译码的设备不太复杂。,对于一般未加纠错码的密码体制，特别,7.2.5 基于级连码的私钥密

32、码体制 因为M公钥体制存在以下问题，所以A.Kh.AlJabri，F.A1Thukair和A.Mirza提出基于级连码的私钥密码体制，将其简称为KAM私钥密码体制，也叫基于级连码的私钥密码体制。下面先叙述M公钥体制存在的问题，然后叙述KAM私钥密码体制的基本思想。（1)McEliece公钥体制的非线性是靠错误图样提供的，若码的最小距离小，则McEliece体制的非线性也就小，在这种情况下，M体制的安全性也就低。,7.2.5 基于级连码的私钥密码体制,（2)全零码字能被正确的猜测，因为全零码字对应密文的汉明重量小于等于t，而非全零码字对应的密文的汉明重量大于等于t1。这里，t是码的纠错能力。（3

33、)对于M体制，由SGP生成的码和由G生成的码具有相同的重量分布。,（2)全零码字能被正确的猜测，因为全零码字,1.加、解密原理 加、解密过程由以下两步构成：外码加密和内码加密。外码加密和内码加密的思想和M密码体制的基本相同，但使用的纠错码都是低维码，添加的错误矢量都不能超过码的纠错能力。外码是有限域GF(2m0)上的(n0，k0，d0)码，随机地选取生成矩阵G0。送给外码编码器的是有限域GF(2m0)上的k0维码字，由外编码器送出的是n0维码字，添加的错误矢量是重量小于等于(d0-1)2的n0维码字。内码加密层由L个内码加密者构成。其中第i个加密(i1，2，L)是有限域GF(2)上的（ni，k

34、i，di）线性码，随机地选取其生成矩阵Gi。,1.加、解密原理,加密过程可简要表述如下。,（731),式中：c0(uSG0z0)P1；Ti(c0)是经过多路复用器后的字符；Zi(zi1,zi2,ziL)是对应于内 编码器(i1，i2，iL)的错误图样。,加密过程可简要表述如下。（731)式中：c0(uSG,2.解密 解密过程是加密过程的逆过程，其过程可以叙述如下：（1)对接收到的密文左乘-12。（2)将得到的结果送给多路复用器，多路复用器按照复用规则将它们送给内码译码器。（3)将第（2）步得到的结果送给解多路复用器，然后将解多路复用器得到的结果左乘P-11。（4)将第（3）步得到的结果送给外码

35、译码器，对译码后的结果左乘S1，得到明文。,2.解密,7.3 基于纠错码的身份认证,7.3.1 方案的基本原理 加密能提高消息的安全，也能提供认证功能。例如,当A想向B证明他的身份时，A可以采用身份认证协议使B确信他是A。1994年Stern提出了基于纠错码的一个交互式零知识身份认证协议。协议的安全性依赖于发现一个码字具有给定的汉明重量和给定的伴随式的困难性。,7.3 基于纠错码的身份认证 7.3.1 方案的基,下面介绍这个身份认证方案。随机选取有限域GF(2)上（n，k，d）线性码的生成矩阵G，并将G公开。每一个用户随机地选一个n比特、汉明重量为p的码字s。这里p是一个预先给定的整数。他的公

36、开身份是 iGs(732)Stern身份认证方案还依赖于比特委托技术(Commitment)。若u是一个比特序列，u的一个委托是指u在密码Hash函数下的像。为了便于叙述，假定任一个用户A想给另一用户B证明他自己的身份。这个协议包括下面r轮，每一轮的运作过程如下：,下面介绍这个身份认证方案。随机选取有,(1)A随机地选取n比特码字y，随机选取集合 1，2，n的一个置换。设c1，c2，c3分别是对序列,H(y),y,(ys),的委托。这里,可以把看作为一个二元比特序列，y是n元矢量在置换下的像。将c1，c2，c3送给B。(2）B随机选取集合0，1，2中的一个元素b，并将b送给A。（）若b0，A公

37、布y，。若b1，A公布ys，。若b2，A公布y，；s，。,(1)A随机地选取n比特码字y，随,(4)若b0，B验证委托c1，c2是否正确。若b1，B验证委托c1，c3是否正确。注意到A已经公布了ys，因此 H(y)H(ys)i 这里,i是A的公钥。若b2，B验证委托c2，c3是否正确，以及s的重量是否为p。循环的次数r依赖于需要的安全水平。,(4)若b0，B验证委托c1，c2,7.3.2 方案的安全性分析 Stern身份认证方案的安全性依赖于由G(s)计算出s的困难性。由前面的讨论可知，给定一个k比特码字x，求重量为p的n比特码字s，使G(s)x是一个NPC问题。设以G为监督阵的(n，n-k)

38、码的最小矩离为2t1，若p小于t，寻找满足G(s)x(s的汉明重量为p)的码字s，对应于伴随式译码问题。对于一个一般的线性纠错码，译码问题是一个NPC问题。在不知道密钥的情况下，要伪造一个签名，有下面几种攻击方式：,7.3.2 方案的安全性分析,(1)攻击者在不知道A密钥s的情况下，随机选取一个汉明重量为p的n比特码字t，在这种情况下，若b0，2，攻击者就能假冒A向B成功地证明自己的身份，b1时，攻击者不能假冒A向B证明自己的身份，攻击者攻击成功的概率为(23)r，这里r是循环的轮数。,(1)攻击者在不知道A密钥s的情况下,(2)攻击者选一个n比特的码字C，满足G(C)i，t的汉明重量不等于p

39、，在这种情况下，若b0，1，攻击者就能假冒A向B成功地证明自己的身份，b2时A不能向B成功地证明自己的身份，因此，攻击者攻击成功的概率为(23)r，这里r是循环的轮数。(3)攻击者还可以通过攻击密码Hash函数来攻击Stern身份认证方案，但在假定密码Hash函数存在的情况下，这种攻击成功的概率也是很小的。综上所述，在假定单向函数存在的情况下，Stern身份认证方案是安全的。,(2)攻击者选一个n比特的码字C，满,7.3.3 方案的一个变型 设G是有限域GF(2)上的(n，k)线性码的生成阵，n2m。用户A在(2m-1，m，2m-1)单纯码(汉明的对偶码)中，随机选取m个线性无关的码字s1，s

40、2，sm作为自己的秘密密钥。m维单纯码的非零码字的汉明重量为2m1。与其对应的公钥为G(s1)，G(s2)，G(sm)。,7.3.3 方案的一个变型,(1)用户A随机选取n比特码字y，并随机选取集合1，2，n的个置换，设c1，c2分别是对二元序列，G(y)，y，s1，s2，sm的一个委托。A将c1，c2送给B。(2)B随机选取二元序列b1，b2，bm，并将其送给A。(3)A计算,（733）,并将其送给B。,(1)用户A随机选取n比特码字y，并随,(4)B随机取b0或1，并将b送给A。(5)若b0，A公布，若b1，A公布y，以及s1，s2，s3,sm。(6)若b0，B验证委托c1是否正确。因为,

41、是A的公钥。,若b1，B验证委托c2是否正确，验证z是否一致，si的重量是否为2m1，i1，2，m。,(4)B随机取b0或1，并将b送给A,7.4 基于纠错码的数字签名,7.4.1 基于纠错码的Xinmei数字签名方案 用户A选择一个纠tA个错误的二元(n，k，dA2tA1)既约Goppa码A，或者有大码类的其他码。公钥：JA=P-1AG*AS-1A WA=G*AS-1A TA=P-1AHTA HA,tA 私钥：SA、GA和PA。,7.4 基于纠错码的数字签名 7.4.1 基于纠错码,式中：GAkn阶A码的生成矩阵；HA(nk)n阶A码监督矩阵；PA二元的nn阶随机矩阵；SAkk阶满秩的随机矩

42、阵；P-1APA的右逆阵；S-1ASA的右逆阵。,式中：GAkn阶A码的生成矩阵；,G*A与GA满足以下关系：GAG*A=Ik(734)式中：Ikkk阶单位方阵；G*Ank阶矩阵；JA、WAnk阶矩阵。,G*A与GA满足以下关系：,1.签名方法 设被签的消息M是一个长为k的二进制序列，用户A进行如下签名运算：E(M)(EjMSA GA)PACj(735)式中：Cj用户A对M的签名；Ej汉明重量W(Ej)tA的长为n的二元随机序列。用户A将Cj或(M，Cj)通过信道送给用户B。由(735)式知，由于Ej的不同，对同一消息M可以产生各种不同的签名，因而是一类概率型的签名算法.,1.签名方法,由于信

43、道中可能有干扰，因此用户B收到的是 Cj=Cj+E=(EjMSAGA)PA+E（7-36)2.验签运算 用户B收到Cj后，首先在公钥本中查到A的公钥后，进行以下验证：(1)右乘TA，计算伴随式。D1(Cj)=CjTA(EjMSAGA)PA+EP-1AHTA=EjHTA（737）式中：EjEjEP-1A。,由于信道中可能有干扰，因此用户B收到的是,(2)译码。用户B得到伴随式D1(Cj)后，并知道tA和HA就可用已知的译码算法，如BerlekampMassy(BM)算法进行译码。如果W(Ej)tA且能被译码器发现，则译码器发出一指令表示收到的Cj有误，要求用户重发签名，若E0，则译码器正确译码，

44、得到Cj和Ej。(3)右乘JA。D3(Cj)CjJA(EjMSAGA)PAP-1AG*AS-1A EjG*AS-1AM（738）,(2)译码。,(4)计算。D4(Cj)D3(Cj)EjWA EjG*AS-1A+MEjG*AS-1AM（739）若此时得到的M与收到的M相同，则签名正确，否则签名有误。由以上讨论可知，若PA是一个nn阶置换矩阵，则W(E)W(EP-1A)，因而如果W(Ej)etA，且W(E)tA-e，则该方案具有纠正信道产生的tA-e个错误的能力。,(4)计算。,7.4.2 Xinmei签名方案的安全性 1992年Harn等首先给出了对该方案的攻击与修正。如果攻击者已知用户A对某些

45、消息如M1和M2的签名：C1E（M1）（Ej1MSAGA）PA C2E（M2）（Ej2M2SAGA）PA则攻击者可以组合M1和M2的签名C1C2，冒充用户A的签名，若W(Ej3)WW(Ej1Ej2)tA，则C1C2能够通过验签运算:C1C2(Ej1Ej2(M1M2)SAGA)PA(Ej3M3SAGA)PA（740）,7.4.2 Xinmei签名方案的安全性,为了防止这种利用已知的签名组合进行攻击，Harn等建议在对消息 M进行签名前，用非线性的Hash函数h(x)，对消息M进行处理，得到h(M)，然后再对h(M)进行签名运算：E(h(M)(Ej+h(M)SAGA)PA（7-41）由于Hash函

46、数的非线性，故能防止这种攻击。,为了防止这种利用已知的签名组合进行攻,假设攻击者能设法使用户A对同一消息M进行n+1次签名：C1,C2,Cn，Cn+1，且它们之中n个签名如C1,C2,Cn线性无关,则计算：CCn（EMSAGA)PA(En1MSAGA)PA(EEn）PA CCn（EEn）PA CnCn（EnEn）PA,假设攻击者能设法使用户A对同一消息,表示成以下形式：,（742）,即,式中X和Y分别是nn阶矩阵。,表示成以下形式：（742）即 式中X和Y分别是nn阶,因为C，C，,Cn线性无关，因而X矩阵是满秩矩阵，所以Y也必是nn阶满秩矩阵，故只要经过(n)次计算就可得到Y，因而,PAY-

47、1 X（743）得到了PA后，用以下方法就可得到SAGA。,因为C，C，,Cn线性无关，因,若有k个不同消息M，M，Mk的签名 C1，C，,Ck。这里Cj(EMSAGA)PA,j1,2,k由此得到：CjP-1AEj+MSAGA（744）并通过译码计算得到Ej，从而可得：CjP-1AEMSAGA 由式(744)可以得到以下k个n重的集合：CjP-1AEMSAGA|，,k,若有k个不同消息M，M，M,由该集合可组成以下方程：DMSAGA（745）式中D为kn阶矩阵，即,由该集合可组成以下方程：,式中D为kn阶矩阵，即,若消息集合M|1，2，k中的k个消息线性无关，则M有逆阵M，由式(745)式得：

48、MDMMSAGASAGA(746)求M或完成式(746)的计算，其工作因子仅为O(n)。,式中D为kn阶矩阵，即 若消息集合M|,7.4.3 修正Xinmei方案 1.AW方案 为了抗击AW攻击，Alabhadi和Wieker于1993年提出了一个改进方案，称为AW方案。首先用户A选择一个非线性函数f(x，y)，并把它公开，这里x是二元k重矢量，y是二元n重矢量，其输出值是二元k重矢量。,7.4.3 修正Xinmei方案,用户A选择一个（n，k，d2tA1）二元即约Goppa码A，及生成矩阵GA和监督矩阵HA，并由GAG*AIk式找到相应的右逆矩阵G*A，以及确定一个GF(2)上的nn阶满秩随

49、机矩阵PA。公钥为 GA=P-1AG*A,HA=P-1AHTA,W*A,HA,tA,tAtA（749）私钥为GA，PA，GA,WA。,用户A选择一个（n，k，d2t,式中:WA秩为n的nl阶矩阵，ln且W*A满足以下关系：AW*AIn（750）签名方法如下：用户A随机地选择一个汉明重量W(E)tA的二元n重E，以及长为ln的二元随机矢量Z，且W(Z)l2，则用户A对消息M的签名是长为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年，王新梅应用类似

50、于AW方案，对原来的Xinmei方案进行修正，得到比AW方案更为简单的修正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函数；t签名时间；M长为k的消息序列；E长为n的重量W(E)tA的二元随机序列；h(M，E)、h(M，E，t)和h（M，t）长为k的二元序列。,式中：h(x，y)和h(x，y，t),因此修正Xinmei方案的公钥、私钥及签名算法与原Xinmei方案的相同，仅仅多了一次Hash函数h(