编码理论 第二版 教学课件 作者 田丽华 第12-16章第14章.ppt

《编码理论 第二版 教学课件 作者 田丽华 第12-16章第14章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第14章　纠错码与保密编码14.1基于纠错码的公钥密码体制14.2基于纠错码的私钥密码体制14.3基于纠错码的身份认证及数字签名14.4签名、加密和纠错相结合的公钥体制14.1基于纠错码的公钥密码体制14.1.1M公钥密码体制M公钥密码体制是1978年McEliece利用一般线性码的译码问题是一个难解的数学问题和Goppa码有快速译码算法的特点，最早提出的一个基于纠错码的公钥密码体制，简称为M公钥体制。该体制的公钥是随机产生的一个线性分组码的生成阵，公钥隐藏了线性分组码的快速译码算法，它是一种局部随机的密码体制。下面介绍M公钥密码体制的加解密原理。　　

2、设G是二元（n，k，d)Goppa码的生成矩阵，其中n＝2m，d＝2t＋1，k＝n-mt。随机地选取两个二元矩阵S和P，则公钥G′为G′＝SGP式中：S—kk阶可逆矩阵；G—kn阶Goppa码生成矩阵；P—nn阶置换矩阵。私钥：S，G，P。加密过程：对于任意一个明文m∈GF(2)k，密文加密算法如下：c＝mG′＋z(14-2)式中：z——GF(2n）上重量为t的随机矢量。解密过程：收方收到一个密文c以后，计算cP－1＝mSGPP－1＋zP－l＝mSG＋z＇，因为P是置换距阵，所以w(z)＝w(z＇)＝t，然后利用Goppa的快速译码算法将其译码成m

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

4、效的算法。此系统还可纠正密文在传送中发生的错误，这种系统称为既加密又纠错的系统。14.1.2N公钥密码体制N钥密码体制是1986年Niederreiter提出的另一个基于纠错码的公钥密码体制，该体制是一个背包型公钥密码体制，简称N公钥密码体制。N公钥密码体制的公钥为随机产生的线性分组码的校验阵，与M公钥不同的是N公钥隐藏了具有快速译码算法的线性分组码的校验阵。下面介绍这个公钥密码体制加、解密原理。设C是有q元线性（n，k，2t＋1)Goppa码，取两个q元矩阵M、P，则公钥H′为H＇＝MHP，t（14-3）式中：H—码C的(n－k)×n校验矩阵；M—q元

5、(n－k)×(n－k)非奇异矩阵；P—q元n×n阶置换矩阵。私钥：H，M，P加密算法：(14-4)14.1.3M公钥密码体制与N公钥密码体制的关系李元兴、王新梅等于1994年在IEEE信息论汇刊上发表论文,证明了M公钥和N公钥密码体制是等价的。　　假定M公钥密码体制和N公钥密码体制采用的是相同的（n，ｋ，2t+1）线性码C，则M密码体制的公钥为G＇＝SlGP（14-5）式中：S１—ｋｋ价可逆阵；P—nn阶置换阵；G—码C的生成矩阵。M公钥密码体制的私钥：Sl，G，P；N密码体制的公钥为:Ｈ＇＝S2HP（14-6）式中：S２—(n—ｋ)(n—ｋ)阶可逆矩

6、阵；P—n×n阶可逆矩阵；Ｈ—码C校验矩阵。M公钥密码体制中的加密方程：c＝mG＇＋e（14－7）将方程（14－7）两端乘(H′)Ｔ得：N密码体制中的加密方程：z＝y(H′)T（14－8）则在多项式时间里可以求得一个n长码字c，使得：z＝c(H′)T（14－9）又因为c可以表示成为c＝mG′＋y（14－10）式中：m——一个ｋ维明文。因此，若M体制被打破，即由c能解密得到m，也就可得到y，那么，N体制被打破。因此，从这个角度看，M公钥密码体制与N公钥密码体制是等价的。14.2基于纠错码的私钥密码体制14.2.1Rao私钥密码体制Rao私钥密码体制是19

7、84年由T.R.Rao提出的一个私钥密码体制，其基本思想是将McEliece公钥用于私钥密码体制。1)加密　　令Z＝{z

8、z∈GF(2)n，z的汉明重量为t}，m是k比特的明文，其对应的n比特密文c为c＝mSGP＋z(14－11)式中：G——二进制线性Goppa码(n，k，2t＋1)生成矩阵；S——k×k阶二元可逆阵；P——n×n阶置换阵；z——从Z中随机选取的n比特向量。私钥：G，S，P，SGP。2)解密　　计算cPT，通过译码得到mS，计算mSS－1得明文m。14.2.2Rao-Nam私钥密码体制从密码分析的角度看，当错误向量的汉明重量约等

9、于n／2时，大数表决攻击方法不能成功。在此情况下，码字的每一个坐标被正确猜测的概