ElGamal 数字签名 修改版

ElGamal 数字签名技术综述数字签名技术综述 摘摘 要要 当今社会是一个信息化的社会 计算机以及互联网的普及 让人们的生活越来越方便 但是 信息安全的问题却日益突出 尤 其表现在计算机网络的安全问题上 现在网络安全的形式已不容乐 观 不仅严重威胁到人们正常的生活 甚至威胁到国家的安全 因 此 信息安全的重要性愈发突出 而信息安全技术的核心之一就是 数字签名技术 如何在信息传输过程中保证信息的安全性和真实性 这是数字签名技术所要研究的重要问题 数字签名可以解决否认 伪造 篡改 冒充问题 使用数字签名技术使得发送者发送的时候 不能否认发送的报文签名 接受者不能伪造发送者的报文签名 ElGamal 数字签名方案作为目前最为重要的数字签名方案之一 极大地促进了现代密码学的发展 ElGamal 数字签名与一般公钥密 码体制签名的不同之处 是具有高安全性和实用性 本文介绍 ElGamal 的基础知识以及改进后的 ElGamal 数字签名 阐述了基于 ElGamal 体制盲签名和多重数字签名 关键词关键词 信息安全 数字签名技术 ElGamal 密码学 ABSTRACT Today is an information society the popularity of computers and the Internet make lives of people more and more convenient However the issue of information security has become increasingly prominent espcially in the issues of the computer network security At present the form of the network security is not optimistic not only a serious thread to people s normal lives but also even a thread to national security Therefore the importance of information security become more prominent and one of the core password of information security technology is the digital signature technology How in the process of information transmission to ensure information security and authenticy which is a important issues the digatal signature technology to study The digital signature can be resolved to the problem of deny forgery tampering posing Using digital signature technology makes the sender can not deny that send message when recipients can not forged signatures and the sender s message signatures As currently one of the most important digital signature scheme ElGamal digital signature scheme greatly stimulates the development of modern cryptography The difference of ElGamal digital signature and the general public key cryptosystem signature is high safety and practicality In this paper we introduced the basic knowledge of ElGamal digital signature technology and improved ElGamal digital signature list the ElGamal signature technique based on other signature scheme Keywords Infomation security Digatal signature technology ElGamal Cryptography 第一章 绪论 1 1 研究背景及意义 信息在社会中的地位越来越重要 已成为社会发展的重要战略 资源 信息安全的重要性也日益突出 而信息安全技术的核心之一 就是数字签名技术 同时现代数字签名技术是解决信息安全的比较 有效的方法 因此 数字签名的研究成为当前国际上的一个研究热 点 而怎样利用数字签名来保证信息在传输过程中的安全性和真实 性是当前研究的一个重要课题 1 2 信息安全的重要性 信息系统安全的中心内容是保证信息在系统中的保密性 认证 性和完整性 传统的密码体制 其主要功能是信息保密 而现代密 码体制还应保证信息在系统的可认证性和完整性 这样可以保证在 公开信道上安全地传递信息 为了防止消息被窜改 删除 重放和 伪造 一种有效的方法是使发送的消息具有被验证的能力 使接收 者能够识别和确认消息的真伪 实现这类功能的密码系统称为认证 系统 消息的认证性和消息的保密性不同 保密性是使截获者在不 知密钥的情况下不能解读密文的内容 而认证性是使任何不知密钥 的人不可以构造出一个密文 使意定的接收者脱密成一个可理解的 消息 合法的消息 认证理论和技术是最近 20 年来随着计算机通信 的普遍应用而迅速发展起来 它成为保密学的一个重要的领域 认证系统主要有以下几个方面的内容 1 消息认证 2 身份认 证 3 数字签名 前两者的目的是解决在通信双方利害一致条件下 如何防止第三方伪装和破坏的问题 而数字签名则解决了当通信双 方是竟争对象时 如何远距离迅速地用电子签名代替传统的手写签 名和印签的问题 自从 1949 年 Shannon 发表了题为 保密系统的通信理论 以来 随着信息时代的来临和数字通信技术的飞速发展 特别是当今的通 信与计算机网络的结合 将会逐步使用电子邮件来代替传统的书面 邮件 这些要求使用这种系统的收方对发方的身份进行确证 这可 用数字签名来完成 数字签名是现代通信中实现消息认证的一种重 要手段 1 3 数字签名的基本概念 数字签名 就是只有信息的发送者才能产生的别人无法伪造的一 段数字串 这段数字串同时也是对信息的发送者发送信息真实性的 一个有效证明 其是非对称密钥加密技术与数字摘要技术的应用 数字签名了的文件的完整性是很容易验证的 而且数字签名具有不 可抵赖性 数字签名的流程如下所示 数字签名的目的是 1 使收方能够确证发方的签名 但不能 伪造 2 发方发出签了名的消息给收方后 就不能否认它所签发 的消息 3 一旦收发双方就消息的内容和来源发生争执时 应能 给仲裁者提供发方对所发消息签了名的数据 1 4 数字签名的功能和应用 数字签名其功能有以下几个方面 1 完整性 数字签名与原始的文件或其摘要一起发送给接收 方 一旦信息被篡改 接受者可以通过计算机摘要和验证签名来判 断该文件无效 2 机密性 将报文信息用接收方的公钥进行解密 以保证信 息的机密性 3 防伪造 签名密钥即私钥只有签名者自己拥有 别人不能 伪造出正确的签名数据 这就是防伪造特性 4 身份认证 数字签名中 公钥是其身份的标志 使用公钥 签名 如果接受方或验证方用其公钥进行验证并获通过 那么可以 肯定签名人就是拥有私钥的那个人 5 防抵赖 数字签名可作为签名者签名操作的依据 防止抵 赖 6 防重放攻击 通常采用对签名报文的加盖时间戳或添加处 理流水号等技术 可以防止重放技术 数字签名的应用如下 数字签名技术最早应用于用户登录过程 PKI 作为电子商务 电子政务的技术平台 使得技术应用 商业价值 生产力提高成为 有机的整体 得到了长足的发展 到目前为止 全国省市几乎都建 立了自己的 CA 认证中心 这些 CA 中心的数字证书及相关应用方案 被广泛应用于网上报关 网上报税 网上报检 网上办公 网上招 投标 网上采购 数字工商等大型电子政务和电子商务工程中 数字签名技术还广泛应用于电子邮件 数据交换 电子交易和 电子货币等领域 安全电子交易 SET 是 MasterCard 两大信用卡公司 和多家科技公司于 1977 年制定的一个在 Internet 上进行的在线交 易的安全标准 SET 提供了消费者 商家和银行间的认证 确保了 交易数据的安全 完整可靠和交易的不可否认 特别是保证了消费 者的隐私 SET 已经成为了目前最流行通用的安全电子商务标准 他的核心技术主要有公开密钥加密 数字签名 数字证书 数字信 封等 SET 协议中的数字签名技术之一是双重签名 双重签名的特 性就是把发给两个不同通信实体的两个不同消息联系在一起 两个 通信实体都可以验证该双重签名 第二章 ElGamal 数字签名 2 1 引言 2 1 1 研究进展 1985 年 ELGamal 基于离散对数难题提出一种数字签名方案 称为 ELGamal 数字签名方案 1994 年 Harn 等人对 ELGamal 及其 类似方案进行了总结 得出了 18 个安全可行的方案 即广义 ELGamal 签名方案 同时 Horster 也独立地提出了 Mata ELGamal 签名方案 它是 Harn 的 18 个方案的进一步推广 因为 ELGamal 型签名方案是在环或域上进行的二元运算 容易受到同态 攻击和代换攻击 因此 在实际应用 ELGamal 型签名方案时 需要 将明文 m 进行处理 即利用 hash m 来代替 m 1994 年 Nyberg 和 Rueppel 对 ELGamal 签名方案进行了攻击 提出具有消息恢复的签 名方案 称为 N R 数字签名方案 Hoster Michels 和 Petress 利用 N S 数字签名方案具有较小的签名长度和消息恢复特性设计了一种 低通信消耗的签名方案 称为 HMP 方案 随后相继提出很多种具 有消息恢复特性的签名方案 在签密方案中 信息签发者可以对信 息进行加密和签名 信息接收者可以对接收到的信息进行解密和验 证 当消息量很大时 还可以采用消息链接的方式进行处理 2 2 ElGamal 数字签名方案 本节给出 ELGamal 签名方案原形及其它的几种变形方案 并分 析了这些方案在计算上的优缺点以及对方案的安全性进行了比较 2 2 1 ElGamal 密码体制 1 ElGamal 密码体制的原理 密钥产生过程 首先选择一素数 p 以及两个小于 p 的随机数 g 和 x 计算 mod x ygp 以 y g p 作为公开密钥 x 作为秘密 密钥 加密过程 设欲加密明文消息 M 随机选一与 p 1 互素的整数 k 计算 1 mod k Cgp 2 mod k Cy Mp 密文为 12 CC C 解密过程 2 1 mod x C Mp C 这是因为 2 1 modmodmodmod kk xkxk Cy My M pppMp Cgy 2 利用椭圆曲线实现 ElGamal 密码体制 首先选取一条椭圆曲线 并得 p Ea b 将明文消息 m 嵌入到 曲线上得到点 m p 再对点 m p 做加密变换 取 p Ea b 得一个生成元 G p Ea b 和 G 作为公开参数 用户 A 选 A n 作为秘密钥 并以 AA Pn G 作为公开钥 任一用户 B 若想向 A 发送消息 m p 可选取一随机正整数 k 产生以下点作为密 文 mmA CkG PkP A 解密时 以密文点对中的第 2 个点减去用自己的秘密钥与第 1 个点的倍乘 即 mAAmAAm PkPn kGPk n Gn kGP 攻击者若想由 m C 得到 m P 就必须知道 k 而要得到 k 只有通 过椭圆曲线上的两个已知点 G 和 kG 这意味着必须求椭圆曲线上 的离散对数 因此不可行 关于椭圆曲线内容 笔者就不在此赘述 请读者阅读文献 1 中椭圆曲线密码体制一章 2 2 2 基于离散对数问题的 ElGamal 签名体制 1 体制参数 p 大素数 g p Z 的一个生成元 x 用户 A 的秘密钥 Rp xZ y 用户 A 的公开钥 mod x ygp 由于 k 不能相等 2 签字的产生过程 对于待签字的杂凑值 m A 执行以下步骤 计算 m 的杂凑值 H m 选择随机数 k 1p kZ 计算 mod k rgp 由于 gcd 1 1k p 计算 1 mod1 sH mxr kp 以 r s 作为产生的数字签字 3 签字的验证过程 接收方在收到消息 m 和数字签字 r s 后 先计算 H m 并按下 式验证 mod rsH m Ver y r s H mTurey rgp 正确性可由下式证明 mod rsrxksrx H mrxH m y rg rggp 由于 mod 1 ksH mxrp 2 2 3 基于身份的 ElGamal 签名体制 1 体制参数 设 q 是大素数 1 G 与 2 G 分别是阶为 q 的加法群和乘法群 122 e GGG 是一个双线性映射 11 0 1HG 和 22 0 1HG 是两 个杂凑函数 q sZ 是系统的主密钥 P 是 1 G 的一个生成元 用户 ID 的公开钥和秘密要分别是 11 ID QH IDG 和 IDID dsQ 2 签字产生过程 对于待签字的消息 m A 执行以下步骤 选择随机数 k p kZ 计算 x y RR RkP 计算 1 2 S H m P x k RID d 以 R S 作为产生的数字签字 3 签字的验证过程 接收方在收到消息 m 和数字签字 R S 后 先计算 2 H m 并按 下式验证 2 2 R Hmx IDpubID Ver QR SHmTuree R Se P Pe Pd 正确性可由下式证明 2 2 1 2 H m P x k s R R x Hm RIDID Hmx pubID e R Se kPde P Pe P d e P Pe Pd 2 2 4 安全性分析 1 整体性攻击 如果一个攻击者试图伪造用户 A 对消息 m 的签名 他随机大素数地选取一个整数 攻击成功的概率为 1p s Z 这对于大素数来讲几乎是不可能的 如果要从 r 中求出消息 1 1 p 密钥 k 将面临求解离散对数的难题 2 重复性攻击 如果对不同的消息使用相同的密钥 则面临消 息密钥被暴漏的危险 设 则 1 11 mod 1 xrp smk 1 22 mod 1 xrp smk 1212 mod 1 s kp sm m 若 则 一旦得 12 0mod 1 p s s 1 122 1 mod 1 kp s m ms 到 k 就很容易求得 x 第三章 基于 ElGamal 数字签名体制的其它签名方案 3 1 基于 ElGamal 体制的盲签名方案 盲签名是一种特殊的数字签名 当用户 A 发送消息 m 给签名者 B 时 一方面要求 B 对消息签名 另一方面又有不想让 B 知道消息 内容 也就是签名者 B 所签的消息是经过盲化处理的 签名除具有 一般数字签名的特征外 还有下面两个特征 1 签名者无法知道所签消息的具体内容 虽然他为这个消息 签了名 匿名性 2 即使后来签名者见到这个签名时 也不能将之与盲消息对 应起来 不可跟踪性 其中引入了有向因子 有向盲签名方案构造为 设 A A g p y x Alice Bob 各自的私钥和公钥 现在 Alice 需 Bob 为 B B g p y x 消息 m 进行盲签名 3 1 1 盲签名过程 步骤如下 步骤 1 Alice 随机选择盲因子 满足计算 p t Z gcd 1 1t p mod 1 Ax Mmp t 将 M 送给 Bob 步骤 2 Bob 1 接受到 M 后 随机选择 k 计算 pZ mod k rp g mod B A x p y 1 mod 1 B p k x 2 求出 11 mod 1 B skMrp x 3 将作为签名送给 Alice r s 步骤 3 Alice 首先 求出 验证mod B A x p y mod mr s B p gyr 如果不等式成立 则拒绝接受 Bob 对盲消息的签名 然后由对盲消 息 M 的签名 S 恢复出对原消息 m 的签名 s 1 1 mod 1 AA r xx Ssp tt 验证等式是否成立 决定恢复的 s 是否正确 mr s B gyr 方案中各种符号的具体含义分别为 p 为一个大素数 可使 中求解离散对数为困难问题 m 为原消息 M 为盲化后的消息 pZ s 为原消息的签名 S 为盲消息的签名 g k r 参数的意义和 ElGamal 签名体制中一致 3 1 2 性能分析 1 安全性分析 1 有向因子的引入使得只有验签双方具mod AB BA xx p yy 有签名和验证签名的权利 其他参与者和用户或攻击者将不具备验 证消息签名的权利 攻击者欲求出 须知道私钥或 这将面 xA yA 临求解离散对数问题 2 攻击者如获取盲消息 M 欲从 M 中求得私钥 将面临离 xA 散对数问题 而如果想求出原消息 m 因为 t 是一大的随机数 将 面对大整整因子分解的困难 3 攻击者想要从中求得签名者私钥 因 1 mod 1 B p k x xB 为 k 为签名者随机选取的大素数 所以必然面临大整数因子分解的 困难 而欲从中求出 k 也会同样面临求解离散对数问mod k rp g 题 2 方案特点 1 将发送方的私钥引入对消息的盲化 即 mod 1 Ax Mmp t 相比于原有的盲化方法 提高了盲消息的抗攻击性能 2 在本方案中 引入有向因子 使得只有特定收发方才具 有对消息进行签名的能力 攻击者无法通过对消息进行签名而对签 名进行跟踪 在 ElGamal 签名体制基础上 设计了一种新的盲签名技术 在 签名过程中通过有向因子的引入 实现了定向用户验签的功能 并 且将私钥引入对消息的盲化过程 提高了算法的安全性能 该方案 将加密和盲签名融为一体 具有较高的安全性和实用性就 必将有 利于推动电子商务的发展并使盲签名技术在选举投票 数字货币协 议 电子支付系统等中得以广泛的应用 3 2 基于 ElGamal 体制的多重数字签名方案 在数字签名应用中 有时需要多个用户对同一文件进行签名和 认证 比如 一个公司发表的声明涉及到财务部 开发部 销售部 售后服务部等部门 需要这些部门签名认可 那么 需要这些部门 对这个声明文件进行签名 能够实现多个用户对同一文件进行签名 的数字签名方案称为多重数字签名方案 根据不同的签名过程 多重数字签名方案可分两类 广播多重 数字签名和有序多重签名方案 以下就基于 ElGamal 体制的广播多 重数字签名展开具体阐述 基于 ElGamal 体制的广播多重数字签名是指在签名过程中 签 名组成员之间没有签名的先后顺序 但要求必须有一个签名收集者 最终完成整个签名 在广播多重数字签名方案中 文件发送者同时 将文件发送给每一位签名者进签名 然后签名者将签名文件发送到 签名收集者 由收集者对签名文件进行整理并发送给签名验证者 签名验证者验证多重签名的有效性 下图描述了广播多重数字签名 方案 过程如图 4 2 所示 签名发送 者 文件签名 者 签名收 集者 签名收集 者 图 4 2 广播多重签名过程 方案描述 方案包含系统初始化 签名和验证过程 方案的参与者有消息 发送者 若干签名者 签名收集者和 1U 1 2 n i i U cUvU 1 系统初始化 每一位签名者任意选取作为的私钥 并计算 iU 1 1 i xp iU 作为公钥 公开参数有 p g i 1 2 n 和 h mod i i x p yg yi 2 签名过程 将 m 发送给每一位签名者 随机选取 计算 1UiUiU 1 1 i kp 发送给其他每一位签名者 mod i i k p g r j j i U 收到后计算 jUir 1 mod n r i i Rp r 然后再计算 将签名 m mod 1 iiii Rh mp sxkr siri 发送到 收到后 其中 首先按 cUcU iiim s r 1 2 ni 照上式计算 R 然后验证方程是否成立 若成立 i mod i i R h m i s r p yg r 说明的签名是对的 否则 不接受 要求重新签名或放弃本次签 iU 名 计算 则多重签名是 cU12n s s ss m s R 3 验证过程 当收消息后 验证等式为 vU m s R 1 s R h m n Rg y y 如果等式成立 认为签名有效 否则 签名无效 vU 基于 ElGamal 体制的多重签名方案有以下特点 1 多重签名是每个签名成员生成部分签名 以合作的方式生 成多重签名 2 部分签名的方式固定 不随签名人员的改变而变化 3 部分签名算法和验证算法