编码理论(第二版)2图文 (7)

G′＝SGP
第14章 纠错码与保密编码
式中：S—kk阶可逆矩阵； G—kn阶Goppa码生成矩阵； P—nn阶置换矩阵。 私钥：S，G，P。 加密过程： 对于任意一个明文m∈GF(2)k，密文加密算法如下：
c＝mG′＋z
(14-2)
式中：z——GF(2n）上重量为t的随机矢量。
第14章 纠错码与保密编码
式中：z*e=zePT。
第14章 纠错码与保密编码
若
z
e
是
一
个
码
字
，
由
解
密
算
法
，
收
方
可
以
获
得
m1，，同时 也能得 到
一 个明文 m ， m m。因 此从 m 抽 取 n— k 比 特，一 般不 会与 m1
相 等，其相等 的概率 为 2－( n－ k) ；若不 相等 ，m 被认 为得 到改动 ，收
H 'T
第14章 纠错码与保密编码
设C是有q元线性（n，k，2t＋1)Goppa码，取两个q元矩 阵M、P，则公钥H′为
H＇＝MHP，t
式中：H—码C的(n－k)×n校验矩阵；
M—q元(n－k)×(n－k)非奇异矩阵；
P—q元n×n阶置换矩阵。
私钥：H，M，P
加密算法：
z y(H ' )T
（14-3） (14-4)
14.2.2 Rao-Nam私钥密码体制 从密码分析的角度看，当错误向量的汉明重量约等于n
／2时，大数表决攻击方法不能成功。在此情况下，码字的 每一个坐标被正确猜测的概率为1／2，这是最佳的。因此， Rao-Nam提出使用预先定义取自码C不同的剩余类的汉明重 量约等于n／2错误码字。同时他们还提出利用简单的纠错码 (汉明重量小于等于6，码长最多为250比特)来获得私钥密码
第14章 纠错码与保密编码
第14章 纠错码与保密编码
14.1 基于纠错码的公钥密码体制 14.2 基于纠错码的私钥密码体制 14.3 基于纠错码的身份认证及数字签名 14.4 签名、 加密和纠错相结合的公钥体制
第14章 纠错码与保密编码
14.1 基于纠错码的公钥密码体制
14.1.1 M公钥密码体制 M公钥密码体制是1978年McEliece利用一般线性码的译码问题是一
方
将
拒
绝
接
收
这
个明
文
。
若
z
e
不
是
一
个
码
字
，
则由
解
密
算
法
得到
m1 m1 (当 且仅当 z＋ ze 是 另一个 错误 向量时 ，m1 ＝m1 )。因此从 m
抽 取 n—k 比 特，一 般不会 与 m1 相 等，其 相等的 概率也为 2 ； －（ n－ k）
若不相等， m 被认为得到改动，收方将拒绝接收这个明文。
论文,证明了M公钥和N公钥密码体制是等价的。 假定M公钥密码体制和N公钥密码体制采用的是相同的
（n，ｋ，2t+1）线性码C，则M密码体制的公钥为
G＇＝SlGP
（14-5）
式中：S１—ｋｋ价可逆阵； P—nn阶置换阵； G—码C的生成矩阵。 M公钥密码体制的私钥：Sl，G，P；
第14章 纠错码与保密编码
（ 1） A随 机 地 选取 n比 特码 字y ，随 机 选 取集
合 {1，2，… ，n}的 一个置 换 。设c1，c2 ，c3 分别 是 对 序 列 < ，H (y)>， <y, >,<(y ＋s), )， 的 委托。这 里 可以 被看作 一个二 元比特 序列，y 是 n元 向量在 置换 下 的像。 将cl，c2 ，c3送给 B。
设G是(n，k)Goppa码的生成矩阵，z是一个特指的错误 图样，它的平均汉明重量大约为n／2。
第14章 纠错码与保密编码
1)加密方法 令m是k比特的密文，则明文c为
c＝(mG＇＋z)P
(14－12)
式中：G′——ｋ×n阶加密矩阵（G′＝SG
S——
ｋ×ｋ
G——汉明重量小于等于6的(n，ｋ)
P——n×n
第14章 纠错码与保密编码
McEliece系统的缺点是密钥长度较大，数据扩展率太大， 它的优点是对同一公钥，一个明文可以对应许多个密文，从 而增加了从密文破译的困难。对McEliece系统的破译一方面
是求出秘密钥S-1，P -1，G；另一方面是对具体密文c来求对 应的明文m。由现有的系统安全性分析可知，这两种破译方
个难解的数学问题和Goppa码有快速译码算法的特点，最早提出的一个 基于纠错码的公钥密码体制，简称为M公钥体制。该体制的公钥是随机 产生的一个线性分组码的生成阵，公钥隐藏了线性分组码的快速译码算 法，它是一种局部随机的密码体制。下面介绍M公钥密码体制的加解密 原理。
设G是二元（n，k，d)Goppa码的生成矩阵，其中n＝2m，d＝2t＋1， k＝n-mt。随机地选取两个二元矩阵S和P，则公钥G′为
有限域GF(2)上的n维向量空间GF(2)n关于(n，ｋ)线性码C
有2n－ｋ个陪集，每一个陪集对应于惟一一个伴随式，在每一 个陪集中选定一个重量大约等于n／2的码字，这样就形成2n-ｋ 个重量大约等于n／2的n重矢量。
第14章 纠错码与保密编码
14.2.3 Li-Wang私钥密码体制 根据Rao-Nam方案，李元兴和王新梅提出了一个可用作加
H(y)＝H(y＋s)＋i
这里i是A的公钥。 若b＝2，B验证委托c2，c3是否证确，以及s．的重量是
否为p。循环的次数r依赖于需要的安全水平。
第14章 纠错码与保密编码
14．3．2 基于纠错码的Xinmei数字签名方案
用 户 A选 择一 个纠 tA 个错 误的 二进 制(n， k，dA 2tA
密和认证的私钥密码体制。这一方案被称为L-W私钥密码体制。 假定码率R≥0.5，即k≥n-k，则L-W体制的加、解密方法如
下所述。 1) 加密 （1) 将消息m分成k比特的组； （2) 通信双方秘密地商定一种算法，从m中选定n－k比特，
构成n－k比特的组m1; （3) 将m1作为伴随式，通过查伴随-错误表找出与其对应
N密码体制的公钥为:
Ｈ＇＝S2HP
式中：S２—(n—ｋ) (n—ｋ)阶可逆矩阵； P—n×n阶可逆矩阵； Ｈ—码C校验矩阵。
M公钥密码体制中的加密方程：
c＝mG＇＋e
将方程（14－7）两端乘(H′)Ｔ得：
（14-6） （14－7）
z＝c H 'T ＝mG＇ H 'T ＋e H 'T ＝e H 'T
第14章 纠错码与保密编码 N密码体制中的加密方程：
法都未发现有有效的算法。此系统还可纠正密文在传送中发 生的错误，这种系统称为既加密又纠错的系统。
第14章 纠错码与保密编码
14.1.2 N公钥密码体制 N钥密码体制是1986年Niederreiter提出的另一个基于纠
错码的公钥密码体制，该体制是一个背包型公钥密码体制， 简称N公钥密码体制。N公钥密码体制的公钥为随机产生的 线性分组码的校验阵，与M公钥不同的是N公钥隐藏了具有 快速译码算法的线性分组码的校验阵。下面介绍这个公钥密 码体制加、解密原理。
解密过程：
收方收到一个密文c以后，计算cP－1＝mSGPP－1＋zP－l ＝mSG＋z＇，因为P是置换距阵，所以w(z)＝w (z＇)＝t， 然后利用Goppa的快速译码算法将其译码成m＇＝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。
第14章 纠Leabharlann 码与保密编码14.3 基于纠错码的身份认证及数字签名
14.3.1 基于纠错码的身份认证 除加密消息以获得安全外，密码系统也能提供认证功能。
例如，当A想向B证明他的身份时，A可以采用身份认证协议 使B确信他是A。1994年Stern提出了基于纠错码一个交互式 零知识身份认证协议。协议的安全性依赖于发现一个码字具 有给定的汉明重量和给定的伴随式的困难性。下面介绍这个 身份认证方案。随机选取有限域GF(2)上（n，k，d）线性码 的生成阵G，并将G公开。每一个用户随机地选一个汉明重 量为p、n比特的一个码字s，这里p是一个预先给定的整数。 他的公开身份是：
（ 2）B随机 选取集 合{0，l，2}中的一 个元素b ， 并 将b送给 B。
（ 3）若 b＝0，A 公布 y， 。若 b＝1，A 公布 y＋s， 。 若 b＝2，A 公布 y， ； s， 。
第14章 纠错码与保密编码
（4）若b＝0，B验证委托c1，c2是否正确。若b＝1，B验 证委托c1，c3是否正确。注意到A已经公布了y＋s，，因此
第14章 纠错码与保密编码
式中：z —是 n－k维向 量；
H 'T —H＇的转置矩阵；
y—重量为t的 q元 n维向量。
解密运算：
由 z＝y(MHP)T 知：z(MT)－1＝y(PT)HT，由码的快 速译 码算法得到 yPT，因此可以求出 y。
第14章 纠错码与保密编码
14.1.3 M公钥密码体制与N公钥密码体制的关系 李元兴、王新梅等于1994年在IEEE信息论汇刊上发表
z——随
机选取的一个错误向量。
密钥：S，P，G，H，伴随－错误表(Syndrome-
errorTable)。
第14章 纠错码与保密编码
2)解密方法 由加密运算公式（14－12）得：
c＝(mG＇＋z)P＝mSGP＋zP＝m＇GP＋zP
令c′＝cPT，则
（14－13）