基于LDPC码的数字签名模拟系统调研报告.pdf

中 南 大 学 中 南 大 学 CENTRAL SOUTH UNIVERSITY 本科生毕业设计 调研报告 本科生毕业设计 调研报告 题 目 基于 LDPC 码的数字签名模拟系统 题 目 基于 LDPC 码的数字签名模拟系统 学生姓名 文 明 学生姓名 文 明 指导教师 黄大足 指导教师 黄大足 学 院 信息科学与工程学院 学 院 信息科学与工程学院 专业班级 计算机科学与技术 0404 班 专业班级 计算机科学与技术 0404 班 完成时间 2008 年 3 月 完成时间 2008 年 3 月 基于 LDPC 码的数字签名模拟系统 摘要 I 摘 要 在信息化的今天 人们倍加重视信息的安全问题 数字签名技术作为信息安全 领域的一项重要技术 应用日益广泛 数字签名已成为信息社会中人们保障网络身 份安全的重要手段之一 通过在数据中加入数字签名 能够保证网络通信过程中信 息传输的完整性 确认发送者的身份认证 以及防止交易中的抵赖发生 本文介绍了数字签名的国内外发展现状 数字签名的基本原理 LDPC 码发展概 况 LDPC 码的基本原理 以及基于纠错码的 XinMei 数字签名方案 最后对基于 LDPC 码的数字签名做了初步构思 关键字 数字签名 LDPC 码 纠错码 XinMei 基于 LDPC 码的数字签名模拟系统 目录 II 目 录 前 言 1 第一章 数字签名 2 1 1 国内外发展状况 2 1 2 数字签名基本原理 3 1 3 LDPC 码 5 1 3 1 LDPC 码基本原理 6 第二章 基于 LDPC 码的数字签名 9 2 1 基于纠错码的 XinMei 数字签名方案 9 2 1 1 基本原理 9 2 1 2 安全性分析 10 2 2 基于 LDPC 码的数字签名方案 11 总 结 13 参考文献 14 基于 LDPC 码的数字签名模拟系统 前言 1 前 言 在全球信息化高速发展的今天 依靠公共网络所从事的政治 经济 文化活动 呈快速上升的趋势 Internet 所具有的开放性 国际性和自由性增加了用户应用自 由度 提高了办事效率 极大的方便了信息的交换与资源共享 这种迅捷的信息传 播与简单的操作正改变着人们的工作与生活方式 网络与数字技术的发展在促进社会发展的同时也带来了许多负面影响 诸如侵 犯版权 信息篡改 数据保密等问题 网络技术的开放性也给知识产权保护及敏感 信息的保密工作带来了极大的苦难与挑战 人们越来越多的使用计算机网络来传送 安全敏感的信息 对攻击者来说 可以得到的技术越来越先进 并且这些技术的成 本在不断的下降 从而使密码分析技术的工程实现变得越来越容易 在这个网络世界中 如何保证你收到的信息没有被破坏 以及如何确定发信人 的身份 信息的安全问题 信息完整性 保密性 可用性以及可控性 已经成为迫切需 要解决的问题 对此国内外许多学者提出了系列信息安全保护思想 其中数字签名 技术就是一种被广泛应用于保证信息完整性和安全性的技术 是在网络系统虚拟环 境中确认身份的重要技术 LDPC 码即低密度奇偶校验码 Low Density Parity Check Code LDPC 它是 由 Robert G Gallager 博士于 1963 年提出的一类具有稀疏校验矩阵的线性分组码 不仅有逼近 Shannon 限的良好性能 而且译码复杂度较低 结构灵活 是近年信道编 码领域的研究热点 目前已广泛应用于深空通信 光纤通信 卫星数字视频和音频 广播等领域 LDPC 码已成为第四代通信系统 4G 强有力的竞争者 而基于 LDPC 码的 编码方案已经被下一代卫星数字视频广播标准 DVB S2 采纳 自 1996 年低密度奇偶校验码 Low Density Parity check Codes LDPC 被重 新引起关注以来 围绕 LDPC 码的研究和开发就没有停止过 其中一方面就是研究 LDPC 码的在数字签名领域的应用 本文在第二章最后一节中中讨论了将LDPC码应用于数字签名构造一种安全的数 字签名方案的可行性 基于 LDPC 码的数字签名模拟系统 数字签名 2 第一章 数字签名 1 1 国内外发展现状 随着 Internet 的普及 网络通信在日常生活中扮演着越来越重要的角色 网络 通信的安全性也越来越受到关注 需要发送方在发送信息同时发送证明身份的信息 类似于手写签名 用于接收方确认信息真伪 由于计算机只能处理数字信息 数字 签名技术应运而生 数字签名 1 是指附加在数据单元上的一些数据 或是对数据所作的密码变换 这种数据变换能使数据接收者确认数据的来源 完整性并保护数据 数字签名是非 对称加密技术中一种 主要通过单向 Hash 函数和公钥算法共同实现 数字签名技术 的基本思想是签名只能由一个人 个体 创建 但可以被任何人校验 每一个数字签 名方案都有一个密钥对生成函数 即给定随机输入 R 将输出两个密钥 SR 私人签名 密钥 和 VR 公共签名密钥 签名方案可以是确定的 也可以是随机的 并可通过 签名验证算法进行验证操作 数字签名与加密解密密切相关 基于公钥密码体制和私钥密码体制都可以获得 数字签名 目前主要是基于公钥密码体制的数字签名 包括普通数字签名和特殊数 字签名 普通数字签名算法有 RSA ElGamal Fiat Shamir Guillou Quisquarter Schnorr Ong Schnorr Shamir 数字签名算法 Des DSA 椭圆曲线数字签名算法 ECDSA 和有限自动机数字签名算法等 特殊数字签名有盲签名 代理签名 群签 名 不可否认签名 公平盲签名 门限签名 具有消息恢复功能的签名等 它与具 体应用环境密切相关 基于公钥密码体制的非对称密钥系统 PKI 的电子签名技术的应用可以基本 解决信息传递的有效性 安全性和不可抵赖性等问题 这一技术在电子认证机 CA 的支持下得到快速应用和发展 其安全可靠性已经过大量实践的检验 数字签名技术目前在安全电子邮件 电子商务中应用较广泛 1 数字签名其它研究方向 数字签名是互联网上不可缺少的安全处理技术 除了前面提到的 RSA 等算法实 现外 还有许多新的算法 实现途径以适应特定领域 主要研究方向如下 1 XML 数字签名 XML 数字签名 定义一种与 XML 语法兼容的数字签名语法描述 规范 描述数字签名本身和签名的生成验证过程 XML 数字签名的核心是如何采用 XML 的语法规则来对数字签名作出恰当而充分的描述 且对签名的生成和验证过程 作出准确的描述 2 高效可验证的安全数字签名 通过高效可严整的安全数字签名方案能够防 基于 LDPC 码的数字签名模拟系统 数字签名 3 止通过猜测 RSA 算法的某些变量来选择信息进行攻击 其安全性实现不是基于树型 结构的信任关系 而是基于一种 Hash 和标记 范式并假设加密所用的 Hash 函数 是经过详细定义且合理的 随机构造一个预测模型且能描述并证明模型是安全可靠 的 证明所构造的模型可以用一个满足特定计算特性的 Hash 函数来代替 通过证明 满足特定计算性质的 Hash 函数的存在性来证明假设的合理性 3 数字签名硬件实现 随着算法复杂度的增加 加密性能下降 硬件实现是 解决此类问题的有效途径 如采用数字信号处理器 DSP 有报道用 DSP 加密的性 能比用软件加密要高 300 倍 通过硬件使得 RSA 快速实现对 RSA 公钥密码体制应用 很有意义 2 电子签名的立法 联合国贸易法委员会 2001 年 7 月通过的 电子签名示范法 对电子签名加以规 范 从法律的角度给予电子签名以传统签名 盖章同等的法律地位 是电子类签名 得以广泛应用和发挥功效的前提 从 1995 年至今 已有三十多个国家 地区和国际 组织先后制订了电子签名法或以确立电子签名法律地位为主要内容的电子商务法 从根本上为电子商务的发展奠定了基础 确立电子签名的法律地位已成为国际立法 和电子商务发展的大势所趋 2005 年 4 月 1 日 我国正式颁布实施 电子签名法 它的出台为我国电子 商务发展提供了基本的法律保障 它解决了电子签名的法律效力这一基本问题 并 对电子商务认证机构 电子签名的安全性 签名人的行为规范 电子交易中的纠纷 认定等一系列问题做出了明确的规定 技术的发展离不开国家的支持 相信在国家有关法律的支持下 数字签名技术 会越来越优秀 1 2 数字签名基本原理 1 公钥密码原理 公钥密码算法是使用一对互相匹配的密钥进行加密 解密 每个用户拥有一把 仅为本人所掌握的私有密钥 SK 私钥 用它进行解密和签名 同时拥有一把公开密 钥 PK 公钥 并可以对外公开 用于加密和验证签名 因此 这种体制又称为双钥或 非对称密钥密码体制 当发送一份保密文件时 发送方使用接收方的公钥对数据加 密 而接收方则使用自己的私钥解密 这样 信息就可以安全无误地到达目的地了 即使被第三方截获 由于没有相应的私钥 也无法进行解密 或者用户也可以采用 自己的私钥对信息加以处理 由于密钥仅为本人所有 这样就产生了别人无法生成 的文件 也就形成了数字签名 2 密钥的维护与管理 基于 LDPC 码的数字签名模拟系统 数字签名 4 公钥密码体制存在一个问题就是如何保证你得到的公钥没有被替换或遭到其他 破坏 确实是你将要与之进行通信的实体的公钥 数字证书正是基于这个思想提出 的 数字证书证明了公钥与公钥持有者真实身份之间的确定关系 是使用公钥的基 础 一般采用的策略是提供一个可信任的第三方机构专门制造和发放证书 每个人 在网络上的身份由他对应的数字证书来确定 用户自己产生密钥 并通过 CA Certificate Authority 认证中心获得数字证书 数字证书有计算机生成的记录 包含有 CA 验证通过的该证书持有者的个人信息以及对应的公钥 由于数字证书是由 CA 经过签名的 如果它被篡改与冒充 你可以在认证阶段检查出来 这样就以保证 你得到的公钥确实是真实可信的 3 数字签名算法 一个签名算法一般包括两个部分 签名算法和验证算法 发送方使用一个私有 的签名算法 签字算法使用的密钥是秘密的 即是签字者的私钥 接收方可以使用 一个公开的验证算法进行验证 该算法根据签名是否有效而返回签名为 真 或 假 的答案 认证算法使用的密钥是发送方 即签名者 的公钥 在签名时由于报文的长 短不同可以有不同的处理方式 如果签名的报文长度较短 签名者可以直接用私钥 对报文全文进行签名操作 但一般建议不采用这种方式 如果报文较长 需要对报 文的数据摘要用私钥进行签名操作 有时为了完成保密性的要求 数字签名和加密 技术一起使用 对签名结果加密或者对消息原文加密 在实际签名中 按照不同的 要求通常采用以下三种不同的签名方案 直接签名 对于较短的消息 直接用发送者的私钥对该短消息签名即可 也就 是对整个消息进行了签名 使用数据摘要的数字签名 对于较长的消息 如果直接对消息签名速度是很慢 的 此时签名算法通常和一个公开密码的散列函数结合使用 这样可以大大提高运 算速度 加强型数字签名 在特殊的应用中需要发送签名的加密消息给接收方 因此提 出了加强型的数字签名方案 为了叙述方便使用直接签名方式来讲述 以下是签名 与公钥加密结合的签名过程 上述方案是先进行签名然后进行加密的一个处理过程 这是一种经常使用的方案 在签名与加密结合的过程中存在另外一种处理方案 即 先加密后签名 由于这种方案存在签名被接收方伪造来发送给第三方 充当接收方 给第三方发送的消息的签名的可能性 所以现实中不使用此方案 4 常用的数字签名算法 自从 1979 年 G J Simmons 将数字签名讨论应用于美苏两国的禁止核试验 条约的验证工作中以来 数字签名技术引起了学术界尤其是密码学界和计算机界的 广泛重视 特别是随着网络的飞速发展 出现了许多签名算法 最常见的数字签名 算法为 RSA DSA ECDSA 三种 基于 LDPC 码的数字签名模拟系统 数字签名 5 RSA 是公钥密码体制中最久负盛名的算法 它既可以用于加密也可以用于数字 签名 RSA 算法已经经过各界多年的深入分析 到目前为止仍然认为是安全的 且 是最为广泛采用的一种密码体制 RSA 既可以用于加密解密也可以用于数字签名 当用于数字签名时 签名者使用私钥参数来完成签名 验证者使用签名者的公钥参 数来完成认证 DSA 是是 EL Gamal Schanorr 等数字签名算法的变体 被美国 NIST 作为 DSS 数字签名标准 基于离散对数问题的数字签名算法 它是由美国国家标准化研究院 和国家安全局共同开发的 由于它是由美国政府颁布实施的 主要用于与美国政府 做生意的公司 其他公司则较少使用 它只是一个签名系统 而且美国政府不 提倡使用任何削弱政府窃听能力的加密软件认为这才符合美国的国家利益 相对于 RSA 等密码体制来说 椭圆曲线加密体制是比较新的技术 椭圆曲线数 字签名算法和 RSA 与 DSA 的功能相同 并且数字签名的产生和认证的速度比 RSA 和 DSA 快 椭圆曲线签名算法也是密码系统在椭圆曲线密码体制 EL Gamal 上的平移 其安全性是基于有限域上椭圆曲线加法群的离散对数问题 ECDL P 与前两种相 比它的安全性更高 5 特殊用途的数字签名方案 除了一些普通的数字签名之外 研究者们还提出了一些特殊用途的数字签名方 案 有不可否认数字签名 盲签名 Blind Signature 群签名 Group Signature 批量签名 环签名 代理签名 Proxy Signature 等 它们都是一些带有特殊附加功 能的数字签名体制 1 3 LDPC 码 LDPC Low Density Parity Check Code 低密度奇偶校验 码是由 Gallager 在 1963 年就提出的一种具有稀疏校验矩阵的线性分组码 2 然而在接下来的 30 年来一 直被人们忽视了 1993 年瑞士日内瓦召开的国际会议上 Berrou 3 提出了 turbo 码 由于他们很 好的应用了 Shannon 的信道编码定理中的随机性编 译码条件 从而获得了几乎接 近 Shannon 理论极限的译码性能 然而 虽然 Turbo 码标志着人们构造其性能接近 Shannon限的好码的开始 但Turbo码仍未将随机化思想真正贯穿于其编译码的始终 而且它有许多缺点 在深入研究 Turbo 码原理的过程中 发现了 LDPC 码具有比 Turbo 更低的线性译 码复杂度 至此 LDPC 码才重新吸引了研究者的兴趣 几乎同时 D MacKay M Neal 等人 4 对它重新进行了研究 发现 LDPC 码同样具有逼近香农限的优异性能 最近的 研究结果显示 一定条件下其性能距 Shannon 限只差 0 04dB 对严格的理论分析具 基于 LDPC 码的数字签名模拟系统 数字签名 6 有可验证性 其译码算法本质上是并行算法 有利于硬件的实现及减少译码时延 由于 LDPC 码本身具有译码较简单 结构灵活 抗突发差错特性好等优点 目前 已广泛应用于深空通信 光纤通信 卫星数字视频和音频广播等领域 LDPC 码已成 为第四代通信系统 4G 强有力的竞争者 而基于 LDPC 码的编码方案已经被下一代卫 星数字视频广播标准 DVB S2 采纳 目前国内外许多也已经将纠错码应用于数字签名中 试图将纠错码的优点融入 到数字签名中去 提出更安全的数字签名解决方案 如 AW 方案和 Xinmei 方案 1 3 1 LDPC 码基本原理 1 LDPC 码构造 LDPC码即低密度奇偶校验码 所谓的 低密度 是来源于矩阵的稀疏性 图1 1 所 示为一 LDPC 码的校验矩阵 图 1 1 LDPC 码一例 Tanner 提出 二分图 Bipartite Graph 模型对 LDPC 码进行分析 二分图由 比特节点 Bit Nodes 效验节点 Check Nodes 及连接他们的边组成 图 1 1 中的 效验矩阵对应图 1 2 a 中的二分图 基于 LDPC 码的数字签名模拟系统 数字签名 7 a 正则 LDPC 码 b 非正则 LDPC 码 图 1 2 LDPC 码的二分图 LDPC 码分为正则码 所有比特节点的次数一样 所有效验节点的次数也一样 和 非正则码 比特节点的次数各不相同 效验节点的次数也有相应的变动 图 1 2 b 为非正则码图 2 LDPC 编码 LDPC 码的编码的研究包括 如何增加二分图中的 grith 即图中的最小环长 如何构造恰当的校验矩阵使得由校验矩阵得到编码生成矩阵的计算简单 如何提高 校验矩阵的秩等 Mackay 等人建议使奇偶校验矩阵强制为下三角阵的形式 5 码集 ensemble 的校 验矩阵满足下三角形式的约束 但是由于它保证了编码具有线性的编码时间复杂度 但是这种约束太强 必然破坏校验矩阵的 grith 约束和变量节点及校验节点的次数 约束 从而导致性能明显下降 所以在满足 grith 约束和次数约束的条件下实现线 性时间编码是 LDPC 码走向实用的关键 Siper 等人提出级联图的方法来取代二分图以减小编码复杂度 6 仔细地选择级 联的层数以及每层的大小 构造线性时间内可编码和译码的码是可以实现的 但它 的缺点在于实际上每层的长度通常都是远小于整个编码码长的 这会导致在同样码 长的情况下和标准的 LDPC 码相比有性能上的损失 T J Richardson 等人 7 提出了对稀疏校验矩阵的行或者列进行重排 从而得到 具有准下三角结构的校验矩阵 利用下三角系数线性方程可以线性时间求解 适当 基于 LDPC 码的数字签名模拟系统 数字签名 8 处理后我们就可以实现线性时间编码 但是如何得到这个下三角矩阵仍然没有令人 满意的方法 T J Richardson 等人通过贪心算法重排校验矩阵过于复杂 并且这样 的预处理需要很多的时间 如果用 matlab 来实现上万码长校验矩阵重排 普通计算 机是办不到 寻找更为有效的方法来获得准下三角矩阵是这个问题的关键 3 LDPC 译码 译码算法的好坏决定了能否最大程度地发挥码本身具备的这种纠错潜力 译码 算法的复杂度决定了工程实现的可行性 LDPC 码的各种译码算法 主要有基于编码 二分图结构的 Message Passing 算法 8 Sipser 和 Spielman 提出的基于扩张图观点 的并行译码算法 9 M P C Fossorier 给出的一种基于迭代可靠性的算法 10 Jinghu Chen 和 M Fossorier 在此基础上提出的两种改进的 BP Based 算法 11 Message Passing 算法在算法的运行过程中 可靠性信息在二分图的变量节点和 校验节点之间来回地更新和传送 因此得名 该算法的前提假设是码对应的二分图 中没有环 BP 算法是一种并行算法 在硬件中的并行实现能够极大地提高译码速度 BP 算 法的迭代过程中 如果试验译码得到成功 译码过程立即结束而不是进行固定次数 的迭代 有效地减少了算法的迭代次数 如果算法在预先限定的最大迭代次数到达 后仍未找到有效的译码结果 译码器将报错 这时的译码错误为 可检测的 若算 法找到一个与 x 不相等的 X 满足方程 H X O mod 2 时将产生 不可检测 的错误 实际使用中不可检测错误的出现概率基本可忽略不计 基于LDPC码的数字签名模拟系统 基于LDPC码的数字签名 9 第二章 基于 LDPC 码的数字签名 基于 LDPC 码的数字签名 本章通过对 XinMei 方案的分析的基础上构造基于 LDPC 码的数字签名方案 2 1 基于纠错码的 XinMei 数字签名方案 12 2 1 1 基本原理 虽然基于纠错码的公钥密码体制早已实现 如 McEliece 公钥密码体制 Niederreiter 公钥密码体制 但与 RSA 公钥密码体制不同 无论是 McEliece 公钥还 是 Niederreiter 公钥都只能用于加密 而没有数字签名功能 能否用纠错码构造 类具有签名能力的密码体制 或者既有加密又具有签名能力的密码体制 这是一个 值得研究的课题 1990 年王新梅教授提出了一类基于纠错码的数字签名方案 XinMei 方案 并在此基础上构造了一类既具加密又具签名能力的方案 具体如下 发送端用户 A 选择一个二进制的 n k d 纠错码 C A 一般为 Goppa 码或有很 多码的其它码类 C A 码的生成矩阵和校验矩阵分别为 G 和 H 最小距离为 d 能 纠正 t d 1 2 个随机错误 用户 A 在公开密钥本中公布以下公钥 ATTT ttSGWHPQTSGPQJ 1 111 11 保留私人密钥 S G P和Q H 这里S和Q分别是k k阶和n n阶的满秩二进制随机矩阵 P是n n 阶的置换阵 Q 1 S 1 和P 1 分别是它们的右逆阵 G T 与G 满足以下关系 KT IGG 2 1 这里Ik 是k k阶单位方阵 可知G T 是一个n k 阶矩阵 因为G是一k n 阶矩 阵 因而 J和W都是n k阶矩阵 求满足 1 式的G T 相应于解有K 2 个线性方程 但却有nk k n 个未知数的方程组 因此G T 有很多解 也即G T 必定存在 称G T 为 G的右拟逆阵 HT 是校验矩阵H 的转置 是一个n n k 矩阵 故T是一个n n k 阶矩阵 1 签名算法 设被签的消息M是一个长为k的二进制序列 发送端A进行如下签名运算 CQMSGPEME i 2 2 基于LDPC码的数字签名模拟系统 基于LDPC码的数字签名 10 C是n长的二进制序列 它就是用户A对消息M的签名 这里Ei 是重量w Ei t A t的n长二进制随机序列 用户A 将C 有时也同时将M 传给用户B 由于Ei 的不同 对同一消息M可以产生各种不同的签名 因而是一类概率型的签名算法 2 验签运算 用户B得到C后 在公开密码本中查到A的公钥 J T W 及t t A 并进行如下 验签运算 1 右乘T 计算伴随式 TiTi HPEHPQQMSGPECTCD 111 1 2 译码 用户B得到伴随式 并知道t n和H 对某些码不一定非知道H 就可用已知的译 码方法译码 如可应用mBerlekamp的迭代译码算法译码 得到 E i Ei P 1 若2 t A t w E i t 或t次迭代后 迭代差值d不为0 则说明接收的签名消息中所产生的 错误超过了t t A 或签名是被篡改过 或是伪造的 此时B停止验证 并通知A重 发签名消息 否则进行下一步 3 右乘J矩阵 MSGPESGPQQMSGPECJCD TiTi 1 11 11 3 2 3 4 计算 MSGPEMSGPESGPECDCD TiTiTi 1 11 11 1 34 得到了消息M 若P 是一个n n 阶置换矩阵 则w E w EP 因而如果w Ei e t A 且w E t A e 则方案具有纠正信道产生的tA e 个错误的能力 但是 此时可以由 公钥 T Q 1 P 1 HT 和H 很容易得到P 1 和P 其计算复杂度为O n 3 因而该签名 方案并不安全 因此 该签名方案中的P 不能是一个置换矩阵 必须是一个满秩的 随机矩阵 且每行和每列的Hamming 重量在n 2 左右 此时E i的重量几乎均大于t 因而 该签名方案不具有纠错能力 2 1 2 安全性分析 13 1 Harn 提出的攻击 1992年Harn等首先给出了对该方案的攻击和修正 指出可能组合两个消息的签 名而得到另一个有意义的消息的签名 究其原因 在于签名生成式 2 2 中呈现的 线性 特征 即 2 1 jPSGMEMEC jjjj 则 基于LDPC码的数字签名模拟系统 基于LDPC码的数字签名 11 PSGMMEECC 212121 而使得W E 1 E 2 t仍可能满足 此外 由于H 的公开使验签过程中E公开 从而使攻击者通过恰当的信息组台 要求签名者 用户A 对各个部分签名 而后上述 关系得到完整消息的有效签名 2 AW攻击 Alabhadi 和 Wieker 于1992 年对Xinmei 方案提出了选择性明文攻击方法 利 用这种攻击 仅需O n 3 就能破译Xinmei方案 对于Harn 提出的修正方案 也可以 用该AW攻击破译 3 修正 Xinmei 方案 修正Xinmei方案的签名算法如下 PSGtEMhEC jjjj 这里h x y t 是非线性单向hash函数 它是公开的 t j是签名的时间 h M E j t j 是长为k 的二进制序列 M是长为k的消息序列 E j是长为n的重量为w E j t A 的二进制随机序列 修正Xinmei方案的公钥 私钥及签名算法与原Xinmei 方案相同 仅仅是多了一次hash 函数计算 用户A 把 M C j t j 作为对消息M 的签名 送给用户B 用户B的验签 过程如同原来的Xinmei方案 用户B 在验签过程中得到h M E j t j 和E j后 再由收到的M t j 计算h M E j t j 若h M E j t j h M E j tj 则说明 签名有效 否则签名无效 要求用户A 重发签名 2 2 基于 LDPC 码数字签名方案 根据上述对Xinmei 方案和其修正方案的分析 我们可以看出 这些方案实际上 是建立在大矩阵分解困难性的基础上的 仅对于签名用户的公钥求广义逆矩阵我们 就可以有效地构造等价的签名私钥 从而成功地伪造签名 虽然利用纠错码可以构 造出一类数字签名方案 但有以下一些弱点 一是由于所用的码是线性码 因此攻 击者往往可以利用这种线性性 进行各种组合伪造签名 或从公钥中解出私钥 所 以必须利用非线性码或非可换的码如秩距离码构造 二是为了阻止错误图样E 被攻 击者所利用 在验签或译码过程中 最好不要泄露错误图样E 但这一点似乎很难做 到 此外 在修正Xinmei方案中引入了单向hash 函数和时戳 看来 在用纠错码构 造的各类密码体制 如McEliece 公钥体制 中这是必须的 否则 这类密码体制的安 全性很难得到充分保证 特别 如果所用的码是线性码 则更是必不可少的 基于此前的分析和研究 构造一种基于LDPC码的数字签名方案是可行的 大体 上可以仿照Xinmei方案 把Goppa码用LDPC码来代替 将LDPC码的优点融入设计方案 基于LDPC码的数字签名模拟系统 基于LDPC码的数字签名 12 中 注意设计中克服以上提到的各种弱点 然后用JAVA语言来模拟实现 基于 LDPC 码的数字签名模拟系统 总结 13 总 结 本文所做的工作如下 1 明确选题意义以及背景 2 查阅文献 总结了数字签名的历史 国内外发展现状 以及最新的技术 3 查阅文献 总结了 LDPC 码的基本原理 4 详细分析基于纠错码 Goppa 码 的 XinMei 数字签名方案 了解数字签名方案 的具体设计流程和安全问题 为下一步的需求分析和总体设计做准备 基于 LDPC 码的数字签名模拟系统 参考文献 14 参考文献 1 赵祥 数字签名综述 J 计算机工程与设计 2006 27 2 195 197 2 文红 符初生 LDPC 码原理和应用 西安 电子科技大学出版社 2006 135 253 3 C Berrou A Glavieux P Thitimajshima Near Shannon Limit Error Corre Cting Coding an Decoding Turbo Codes C Proc IEEE ICC 93 Geneva Switzerland May 1993 4 R Michael Tanner A Recursive Approach to Low Coplexity Codes IEEE Trans On InformationTheory September 1981 1T 27 5 533 547 5 M Siper D A Spielman