HASH GAME - Online Skill Game GET 300

　　上讲主要内容回顾 公钥密码体制的简介 背包问题 RSA算法 ElGamal算法 ECC算法 IBE算法 1 第九十讲Hash 函数及其应用 主讲人：谷利泽 Email ：Tel: 010 本讲主要内容 哈希函数的简介 哈希函数算法举例(SHA-1) 哈希函数的安全性 口令的安全性 消息认证 数字签名 3 引言 在一个开放通信网络的环境中，信息面临的攻击包括窃 听、伪造、修改、插入、删除、 否认等。因此，需要提供用 来验证消息完整性的一种机制或服务 消息认证。这种服务 的主要功能包括： 确保收到的消息确实和发送的一样； 确保消息的来源真实有效； 注：对称密码体制和公钥密码体制都可提供这种服务，但用于 消息认证的最常见的密码技术是基于哈希函数的消息认证码。 4 认证码和检错码 现代密码学中的消息认证码与通信学的消息检错 码有密切的联系，并由其演变而来，但其根源和 目的 是不同的。 检错码是检测由于通信的缺陷而导致消息发生错误的 方法； 认证码是用来检查由于恶意或有目的等方式修改消息 的技术。 5 哈希（Hash）函数的简介 也称散列函数、杂凑函数等，是一种单向密码体制 ，即 它是一个从明文到密文的不可逆映射，即只有“加密”过程， 不存在“解密”过程。同时，Hash 函数可以将“任意”长度 的输入经过变换以后得到固定长度的输出。 Hash 函数的这种 单向特征和输出数据长度固定的特征使得它可以生成消息或数 据块的“数据指纹”（也称消息摘要或散列值），因此在数据 完整性和数字签名等领域有广泛的应用的，哈希函数在现代密 码学中非常起着重要作用。 6 哈希函数的表示 对不同长度的输入消息，产生固定长度的输出。这个固 定长度的输出称为原输入消息的“散列”或“消息摘要” （Message Digest ）。 公式表示形式： h=H(M) M ：任意 长度的消息 H ：哈希（Hash）函数或杂凑函数或散列函数 h：固定长度的哈希值 7 哈希算法的性质(特点) 输入：消息是任意有限 长度。 输出：哈希值是 固定长度。 容易计算：对于任意给定的消息，容易计算其哈希值。 单向性：对于给定的哈希值h ，要找到M使得H(M) ＝h在计 算上是不可行的。 8 哈希算法的性质(安全性) 抗弱碰撞性：对于给定的消息M ，要发现另一个消息M ， 1 2 满足H(M ) ＝H(M )在计算上是不可行的。 1 2 抗强碰撞性 ：找任意一对不同的消息M M ，使H(M ) ＝ 1 ， 2 1 H(M )在计算上是不可行的。 2 随机性： 当一个输入位发生变化时，输出位将发生很大变 化。(雪崩效应) 9 哈希函数的一般结构 输入分组 输入分组的长度 分组数 M0 M1 ML-1 b b b n n f n f n … n f IV =CV0 CV1 CVL- 1 初始值 链接变量 压缩函数 散列值的长度 10 哈希函数的核心技术 设计无碰撞的压缩函数f ，而攻击者对算法的攻击重点是 压缩函数f 的内部结构，由于压缩函数f 和分组密码一样是由 若干轮处理过程组成，所以对压缩函数f 的攻击需通过对各轮 之间的位模式分析来进行，分析过程常常需要先找出压缩函 数f 的碰撞。由于是压缩函数 ，其碰撞是不可避免的。因此， 在设计压缩函数f 时就应保证找出其碰撞在计算上是不可行的。 常用的散列函数： MD5； SHA系列； 11 哈希函数的历史 Hash 的概念起源于1956年，Dumey 用它来解决symbol table question(符号表问题) ，使得数据表的插入、删除、查询操作可 以在平均常数时间内完成。 散列算法MD族是在上个世纪90年代初由mit laboratory for computer science和RSA data security inc 的Ron ・Rivest设计的， MD代表消息摘要(message-digest ) ，MD2(1989) 、MD4(1990)和 MD5(1991)都产生一个128位的信息摘要. SHA 系列算法是NIST 根据Rivest 设计的MD4和MD5 开发的 算法，国家安全当局发布SHA作为美国政府标准，SHA(Secure Hash Algorithm)表示安全散列算法。 12 SHA系列简介 SHA 系列包括多个散列算法标准，其中，SHA-1是数字 签名标准中要求使用的算法。 SHA-0 ：正式地称作SHA ，这个版本在发行后不久被指出存 在弱点。 SHA-1 ：NIST 于1994年发布的，它与MD4和MD5散列算法非 常相似，被认为是MD4和 MD5 的后继者。 SHA-2 ：实际上分为SHA-224、SHA-256、SHA-384和SHA- 512算法。 13 SHA-1的简介 SHA-1接受任何有限长度的输入消息，并产生长度为 160 比特的Hash值（MD5仅仅生成128位的摘要），因此抗穷 举性更好。SHA-1 设计时基于和MD4相同原理，它有5个参 与运算的32位寄存器字，消息分组和填充方式与MD5相同， 主循环也同样是4轮，但每轮进行20 次操作，非线性运算、 移位和加法运算也与MD5 类似，但非线性函数、加法常数 和循环左移操作的设计有一些区别。 14 SHA-1哈希值的生成过程 L512 bits N bits 填充(0 to 511 bits) 消 息 100…0 消息长度L (mod 264) 512 bits 512 bits 512 bits 512 bits M0 M1 … Mi … ML-1 512 512 512 512 160 160 160 160 160 IV HSHA-1 HSHA-1 … HSHA-1 … HSHA-1 CV1 CVi CVL-1 哈希值 15 SHA-1对单个512位分组的处理过程 M 512比特 hi-1(160比特) i 初始值： A=0 A B C D E B=0xefcdab89 f , K , W[0…19] 20步 C=0x98badcfe 1 1 D=0 A B C D E E=0xc3d2e1f0 f , K , W[20…39] 20步 2 2 A B C D E f , K , W[40…59] 20步 3 3 A B C D E f , K , W[60…79] 20步 4 4 + + + + + 模232加 h (160比特) i 16 SHA-1生成字W 的方法 t 1 W =S (W +W +W +W ) (t=16,17,…,79) t t-16 t-14 t-8 t-3 M (512bit) w ,w ,w ,w … w ,w ,w ,w … w ,w ,w ,w i 0 2 8 13 t-16 t-14 t-8 t-3 63 65 71 76 + 循环左 + + 移一位 S1 S1 S1 W W0 … W15 W16 … Wt … 79 17 SHA-1的基本操作 5 A=E+f(t,B,C,D)+S (A)+W +K ; t t f (X, Y, Z) = (X∧Y) ∨(～X ∧Z) (t=0 ,…, 19) 1 B=A; f (X, Y, Z) = X⊕Y⊕Z (t=20,…,39) 2 C=S30(B); f (X, Y, Z) =(X∧Y) ∨(X∧Z) ∨(Y∧Z) (t=40,…,59) 3 D=C; f (X, Y, Z) = X⊕Y⊕Z (t=60,…,79) 4 E=D; A B C D E K 的4个取值2、3、5、10的 t 30 平方根，然后再乘以2 ，最 后取结果的整数部分。 f + S5 + S30 + Wt + Kt K =0x5a827999 (t=0,…,19) 1 K =0x6ed9ebal (t=20,…,39) 2 K =0x8f1bbcdc (t=40,…,59) A B C D E 3 K =0xca62c1d6 (t=60,…,79) 4 18 哈希函数的攻击 攻击者的主要目标不是恢复原始的明文，而是用非 法消息替代合法消息进行伪造和欺骗，对哈希函数 的攻击也是寻找碰撞 的过程。 生日攻击 19 生日问题 问题：假定每个人的生日是等概率的，每年有365天（不考虑 闰年）。在k个人中至少有两个人的生日相同的概率大于0.5 ， 问k 的最小值是多少？ 把每个人的生日看作在[1，365] 中的随机变量。由组合数学基 本知识得知k个人的生日不重复的概率为 k k p (k ) 1p 365 / 365 ; k 23,p (k ) 0.5073; k 100,p (k ) 0.9999997; 20 安全问题的思考 目前安全的哈希值位数是多少? 假设哈希值位数为m， 其信息集合大小为2m ，那 有意义的攻击：发生 么，这集合中多少个消息时 碰撞的消息对攻击者 使得出现碰撞的概率大于 有利。 50% 。 21 哈希函数的攻击过程 签名者对消息x 的签名其实就是使用私钥对H(x)加密得到的签 名值Sig (h(x))。 k k 对手对消息x产生2 个变形的消息(即表达同样的意思消息) ， 再拟定一个准备替换消息x 的假消息x’( 它表示另外一个意思， k 但对攻击者有利 ) ，产生x’ 的2 个变形消息。计算所有这些 消息的哈希函数值。 比较这两个哈希函数值集合，以便发现具有相同哈希函数值 ( 匹配) 的消息。如果没发现，则再产生其他一对有效消息和 假消息，直到出现一个匹配为止。 用找到匹配的假消息x’代替消息x ，后面仍然附加签名值 Sig (h(x))一起送给验证者。 k 22 两个集合相交问题 已知两个k元集合X {x , x ,, x },Y {y , y ,, y },其中x , y ( 1 2 k 1 2 k i j 1 i, j  k )是{1,2,, n}上均匀分布的随机变量。取定x , 若y  x , i i i 则称y 与x 匹配。固定i, j, y 与x 匹配的概率为1/ n, y  x 的概率 i i i i i i k 为11/ n。Y中所有k个随机变量都不等于x 的概率为(11/ n) 。 i 假设X ,Y中的k个随机变量两两互不相同,则X与Y中不存在任何 匹配的概率为(11/ n)k 2 。从而Y与X至少有一个匹配的概率为 k 2 于 1(11/ n) 。我们希望知道多大的k能使这个概率大 0.5。 x k 2 1/ n k 2 式  x)  e , x  0, 有1(11/ n) 1(e ) 。 为此, 利用不等 (1 出  (ln 2)n  0.83 n  n。 令不等式右边等于0.5，求 k 23 结论 假设哈希函数H输出长度为m ，全部可能的输出有 n=2m 个。哈希函数H接受k个随机输入产生集合X ，接 受另外k个随机输出产生集合Y 。根据前面的讨论知， 当k=2m/2 时，X 与Y 至少存在一对匹配(即哈希函数产 生碰撞) 的概率大于0.5 。由此看出，2m/2 将决定输出长 度为m 的哈希函数h 强碰撞的强度。 24 哈希函数的应用 譬如可信计算、文件病毒 口令的安全性 的检验、网页防篡改、黑 白名单等许多应用。 文件的完整性 譬如零知识证明、比特承 诺、不经意传送、电子商 密码协议的应用 务的安全协议等许多应用。 消息认证 数字签名 譬如随机数的生成、密钥更 新等许多应用。 其它应用 25 基于口令的身份认证 由于口令易实现、成本低、使用方便等特点，成为当 前最常用的认证方式，尤其在安全性要求不是很高的应用 场合。 对于大部分系统而言，初始化时，系统管理员给每个 用户指定一个缺省(临时) 口令，认证数据库中保存缺省口 令及其哈希值。然后，管理员通过某些方式，如邮件或者 电话，告诉用户他的缺省口令。 缺省口令的更新 哈希函数的好处： 远程口令的认证  口令信息实现安全传输 管理员不知道用户的口令 26 新口令设置 输入终端 认证系统 缺省口令 使用哈希值2作 或旧口令 为密钥加密哈希 新口令 值1产生密文 哈希值 哈希函数 使用数据库中的哈希值2 哈希函数 作为密钥解密得用户新 口令的哈希值1 使用哈希 值1替换数 哈希值2 据库中的 哈希值1 公 哈希值2 开 加密 信 哈希值1 解密 道 密文 密文 27 远程口令认证 输入终端 认证系统 口令 明文口令 随机数 哈希值 哈希函数 挑战 哈希函数 哈希值 挑战 公 开 应答1 哈希函数 信 道 匹配吗？ Y 通过 应答 N 应答 拒绝 28 消息认证的概述 网络系统安全一般要考虑两个方面：一方面，加密保护 传送的信息，使其可以抵抗被动攻击；另一方面，就是要能 防止对手对系统进行主动攻击，如伪造、篡改信息等。认证 是对抗主动攻击的主要手段，它对于开放的网络中的各种信 息系统的安全性有重要作用。认证分为实体认证和消息认证。 消息认证的目的： 验证信息的来源是真实的，而不是冒充的，此为消息源认证。 验证消息的完整性，即验证信息在传送或存储过程中是否被 修改。 29 哈希函数的分类 改动检测码MDC(Manipulation Detection Code) 不带密钥的哈希函数 主要用于消息完整性 消息认证码MAC(Message Authentication Code) 带密钥的哈希函数 主要用于消息源认证和消息完整性 30 MAC的生成过程 秘密密钥 MAC 消息 算法 MAC 不安全信道 31 消息认证码 消息认证码(MAC，Messages Authentication Codes)，是与密钥相关的的单向散列函数，也称为消息鉴别 码或是消息校验和。此时需要通信双方A和B共享一密钥K 。 设A欲发送给B 的消息是M ，A 首先计算MAC=CK(M) ，其中 CK(·)是密钥控制的公开函数(如哈希函数) ，然后向B发送 M ‖MAC ，B 收到后做与A相同的计算，求得一新MAC ，并与 收到的MAC做比较。 32 消息认证码的功能 接收方相信发送方发来的消息未被篡改，这是因为攻击者 不知道密钥，所以不能够在篡改消息后相应地篡改MAC ，而 如果仅篡改消息，则接收方计算的新MAC 将与收到的MAC 不同。 接收方相信发送方不是冒充的，这是因为除收发双方外再无 其他人知道密钥，因此其他人不可能对自己发送的消息计算 出正确的MAC 。 33 消息认证的常用实现过程 密钥K 消息 密钥K Hash函数 Hash函数 消息 哈希值 消息 公开信道 哈希值 认证码 相等 N 认证 认证码 无效 Y 认证 有效 34 HMAC的简介 利用对称分组密码体制（如DES 、AES ）的密码分组链 接模式（CBC）一直是构造MAC 的最常见的方法。近几年， 人们越来越感兴趣于利用哈希函数来设计MAC ，这是因为像 MD5 、SHA-1这样的哈希函数，其软件执行速度比诸如DES 、 AES 这样的对称分组密码要快。 然而，诸如SHA-1这样的哈希函数并不是专门为MAC 而 设计的，由于哈希函数不依赖于密钥 ，所以它不能直接用于 计算MAC 。目前，已经提出了许多方案将密钥加到现有的哈 希函数中。HMAC是最受支持的方案，并且在Internet协议中 (如SSL) 中有应用。 35 HMAC的结构 左边经填充0后的K， + + b/8 K 的长度为b比特. K ipad b位 b位 b位 b/8 S1 M0 M1 … ML-1 消息M的分组. K+ opad n位 哈希 IV 函数 n位 b位 一个分组的比特数. 填充至b位 哈希函数所产生 哈希值的长度. S0 n位 哈希 n位 哈希函数输 IV 函数 HMAC(K,M) 入的初始值. 36 HMAC算法描述 ① K 的左边填充0 以产生一个b 比特长的K+ （例如K 的长为160 比特，b=512 ，则需填充44个零字节0x00）。 ② K+ 与ipad 逐比特异或以产生b 比特的分组S1 。 ③ 将M 附于S 后。 1 ④ 将哈希函数H作用于步骤③产生的数据流。 ⑤ K+ 与opad逐比特异或, 以产生b 比特长的分组S 。 0 ⑥ 将步骤④得到的杂凑值链接在S 后。 0 ⑦ 将H作用于步骤⑥产生的数据流并输出最终结果。 37 HMAC的有效实现方案 左边经填充0 b/8 + 后的K，K 的 长度为b比特 预计算 对每条消息计算 K+ ipad 一个分组的比特数 b位 b位 b位 M0 M1 …ML-1 消息M的分组 哈希函数输 入的初始值 S1 IV f n位 哈希 函数 K+ opad n位 哈希函数所产生 哈希值的长度 填充至b位 S0 b/8 n位 n位 IV f f HMAC(K,M) 38 数字签名的引言 手写签名是一种传统的确认方式，如写信、签订协议、 支付确认、批复文件等。在数字系统中同样有签名应用的需 求，如假定A发送一个认证的信息给B ，如果没有签名确认的 措施，B 可能伪造一个不同的消息，但声称是从A 收到的；或 者为了某种目的，A 也可能否认发送过该消息。很显然，数字 系统的特点决定了不可能沿用原先的手写签名方法来实现防 伪造或抵赖，这就是提出了如何实现数字签名的问题。 数字签名是电子信息技术发展的产物，是针对电子文档 的一种签名确认方法，所要达到的目的是：对数字对象的合 法化、真实性进行标记 ，并提供签名者的承诺。随着信息技 术的广泛使用，特别是电子商务、电子政务等快速发展，数 字签名的应用需求越来越大。 39 数字签名的简介 数字签名体制是以电子签名形式存储消息的方法，所 签名的消息能够在通信网络中传输。 在当今数字化的信息世界里，数字化文档的认证性、 完整性和不可否认性是实现信息化的基本要求，也决定信息 化的普及和推广。数字签名是满足上述要求的主要手段之一， 也是现代密码学的主要研究内容之一。 数字签名是日常生活中手写签名的电子对应物。 40 数字签名与手写签名的不同 签名：手写签名是被签文件的物理组成部分；数字签名是 连接到被签消息上的数字串。 传输方式：数字签名和所签名的消息能够在通信网络中传 输。手写签名使用传统的安全方式传输。 验证：手写签名是通过将它与真实的签名进行比较来验证； 而数字签名是利用已经公开的验证算法来验证。 数字签名的复制是有效的；而手写签名的复制品是无效的。 手书签字是模拟的，且因人而异。数字签字是0和1的数字 串，因消息而异。 41 数字签名的概念 所谓数字签名(Digital Signature) ，也称电子签名，是指附 加在某一电子文档中的一组特定的符号或代码 ，它是利用数 学方法和密码算法对该电子文档进行关键信息提取并进行加 密而形成的，用于标识签发者的身份以及签发者对电子文档 的认可，并能被接收者用来验证该电子文档在传输过程中是 否被篡改或伪造。 42 数字签名的理解 数字签名由公钥密码发展而来，作为密码学基本元语，它在网 络安全，包括身份认证、数据完整性、不可否认性等方面有着 重要应用。 数字签名的目的是提供一种手段，使得一个实体把他的身份与 某个信息捆绑在一起。一个消息的数字签名实际上是一个数， 它仅仅依赖于签名者知道的某个秘密，也依赖于被签名信息的 本身。 数字签名基于两条基本的假设：一是私钥是安全的，只有其拥 有者才能获得；二是产生数字签名的惟一途径是使用私钥。 43 数字签名的对比 与消息加密不同：消息加密和解密可能是一次性的，它要求 在解密之前是安全的；而一个签字的消息可能作为一个法律 上的文件，如合同等，很可能在对消息签署多年之后才验证 其签字，且可能需要多次验证此签字。 与消息认证不同：数字签名也是一种消息认证技术，它属于 非对称密码体制，消息认证码属于对称密码体制，所以消息 认证码的 处理速度比数字签名快得多。但是，消息认证码无 法实现不可否认性。 44 数字签名的安全要求 签名是可以被验证的 接受者 能够核实签名者对消息的签名。 签名是不可伪造的 除了签名者，任何人( 包括接受者) 不能伪造消息的签名。 签名是不可重用的 同一消息不同时刻其签名是有区别的。 签名是不可抵赖的 签名者事后不能抵赖对消息的签名，出现争议时，第三方 可解决争端。 45 数字签名算法的实现要求  签名的产生必须使用签名者独有的一些信息 以防伪造和否 认，同时，要求保证独有的一些信息的安全性。 签名的产生应较为容易。 签名的识别和验证应较为容易。 对已知的数字签名构造一新的消息或对已知的消息构造一 假冒的数字签名在计算上都是不可行的。 46 数字签名方案的组成 数字签名方案是由五元组组成的， 即{P,S,K,Sign,Ver} 。 P:明文空间； S:签名空间； K:密钥空间； Sign:签名算法； Ver:验证算法； 47 数字签名的组成 系统初始化 生成数字签名方案用到的所有参数。 签名生成算法 用户利用给定的算法对消息产生签名s=Sign(m)。 签名验证算法 验证者利用公开的验证方法对给定消息的签名进行 验证，得出签名的有效性。Ver (s,m)=0或1。 48 数字签名描述 签名者A 验证者B 消息 Hash函数 哈希值 Hash函数 消息 签名有效 消息 公开信道 验证算法 哈希值 签名 签名 签名无效 签名算法 A的公钥 A的私钥 49 数字签名常见的实现算法 基于RSA 的签名算法 基于离散对数的签名算法 基于ECC 的签名算法 50 数字签名算法思考的主要问题 如何实现签名算法(私钥加密) ； 如何实现验证算法(公钥解密) ； 证明算法的正确性 ； 分析算法的效率； 目前针对这种签名/验证算法的安全分析。 51 RSA数字签名算法(初始化) 1. 选取两个大素数p和q，两个数长度接近，1024位 2. 计算n=p*q,

　　(n)=(p-1)(q-1) 3. 随机选取整数e(1e

　　(n))，满足gcd(e,

　　(n))=1 4. 计算d，满足d*e=1 （mod

　　(n)）。 注：n公开，p和q保密。 e为公钥，d为私钥。 52 RSA数字签名算法(签名和验证) 签名算法 1.利用一个安全的Hash 函数h 来产生消息摘要h(m) 。 2. 用签名算法计算签名s=Sign (m)=h(m)d mod n 。 k 验证算法 1.首先利用一个安全的Hash 函数h计算消息摘要h(m) 。 2. 用检验等式h(m) mod n=se mod n 是否成立，若相等签名有 效，否则，签名无效。 53 RSA数字签名算法(正确性) 由于 s=h(m)d mod n d*e=1 （mod

　　(n)） 所以 se mod n=h(m)ed mod n =h(m) k

　　(n)+1 mod n = h(m) *h(m) k

　　(n) mod n

　　(n) k =h(m)* (h(m) ) mod n = h(m) 54 RSA数字签名算法(举例) 初始化： 假设A选取p = 13，q = 11，e = 13，则有n = pq = 143，φ(n) = (p- 1)(q-1) = 12×10 = 120。求解ed = 13d ≡ 1(mod 120) 得d = 37 。因此 A 的公钥为 （n = 143, e = 13）；私钥为d = 37 。 签名过程： 假定消息m的Hash值h(m) = 16，则计算m签名s = h(m)d mod n = 1637 mod 143 = 3。 验证过程： 接受者B收到签名后，计算se mod n = 313 mod 143 = 16，h(m) mod n = 16 mod 143 = 16，等式h(m) mod n = se mod n成立，因此，B验 证此签名有效。 55 RSA数字签名方案(安全性) 如果不使用Hash 函数，则对消息m ,m 的签名分别为s = m d 1 2 1 1 mod n ，s = m d mod n ，假设攻击者获得了这两个签名， 2 2 就可以伪造消息m *m 的有效签名s *s 。（同态性） 1 2 1 2 使用Hash 函数可以避免这样的攻击。 对于大消息而言，对其Hash值的签名不仅不失数字签名特 征 ，而且大大提高其签名和验证的效率。 RSA 签名方案还存在签名可重用的问题，即对同一消息在 不同时刻签名是相同的。 通过引入随机数来解决这个问题。 56 基于离散对数的签名算法 ElGamal数字签名 Schnorr数字签名 DSA数字签名 57 Elgamal签名算法(初始化和签名) 初始化： 首先选择一个大素数p ，使在Zp 中求解离散对数困难。 * x 然后选择一个生成元g∈Zp ，计算y≡g mod p ，则公开密 钥y,g,p ，私钥x 。 签名过程： 设待签消息为m ，签名者选择随机数k∈ Zp* ，计算： R r≡(gk mod p) s≡(h(m)-xr)k-1 mod (p-1) 则数字签名为(s,r) ，其中h 为Hash 函数。 58 Elgamal签名算法(验证) 验证过程： 签名接受者在收到消息m和签名值(r,s)后，首先计算 h(m) ，然后验证等式： r s h(m) y r ≡ g mod p 如等式成立，则数字签名有效；否则签名无效 。 59 Elgamal签名算法(正确性) 因为： k r≡ (g mod p) -1 s≡ (h(m)-xr)k mod (p-1) 所以： ks ≡h(m)-xr mod (p-1) gks ≡gh (m)-xr mod p gks gxr ≡gh (m) mod p r s h (m) y r ≡g mod p 60 Elgamal签名算法(举例) 初始化： 假设A选取素数p = 19 ，Zp* 的生成元g = 2 。选取私钥x = 15 ，计算y = gx mod p = 215mod 19 ≡12，则A 的公钥是(p = 19, g = 2, y = 12)。 签名过程： 设消息m的Hash值h(m) = 16，则A选取随机数k = 11，计算r = gk mod p = 211 mod 19 ≡15，k-1 mod (p-1) ≡5 。最后计算签名s = [h(m)-xr]k-1 mod (p-1) = 5(16-15×15 )mod 18 ≡17。得到A对m的签名为(15, 17)。 验证过程： r s 15 17 接受者B得到签名(15 , 17)后计算y r mod p = 12 15 mod 19 ≡ 5 ， h(m) 16 r s h(m) g mod p = 2 mod 19 ≡5 。验证等式y r ≡g (mod p)相等，因此B 接受签名。 61 Elgamal签名算法(安全性) 如果k值泄露，则容易计算： 不能泄露随机数k。 x ≡ [ h(m)-sk] r-1 mod (p-1)， 签名者的私钥泄露。 不能使用相同的k对两个不同消息进行签名。 假设k用来对两个不同的消息签名，则r相同， 即(r，s )是m 的签名， 1 1 (r，s )是m 的签名， 2 2 有s ≡ [ h(m )-xr ] k-1 mod (p-1) (1) 1 1 s ≡ [ h(m )-xr ] k-1 mod (p-1) (2) 2 2 那么有(s -s ) k ≡ [ h(m )-h(m ) ] mod (p-1)， 1 2 1 2 由于消息m 和m 不同，有s -s ≠ 0 mod (p-1)， 1 2 1 2 则k ≡ [ h(m )-h(m ) ] (s -s )-1 mod (p-1)， 1 2 1 2 一旦得到k，就很容易计算签名者的私钥x 。 签名者多次签名时所选取多个k之间无关联。 62 随机数的作用 保证私钥的安全性。 实现数字签名的不可重用性，即不同时刻对同 一消息进行签名，产生不同的签名值。 63 Schnorr签名算法(初始化和签名) 初始化： 首先选择一个大素数p ，使在Zp 中求解离散对数困难。然 * q 后选择一个生成元g∈Zp ，g ≡1 mod p ，最后选取随机数 1xq ，计算y≡gx mod p ，则公钥为(p,q,g,y) ，私钥为x 。 签名： 用户选择随机数k ，对消息进行如下计算得签名值(e,s)。 k r≡g mod p e=H(r,m) s≡xe+k mod q 64 Schnorr签名算法(验证) 验证： 接受方在收到消息m和签名值(e,s) 后，进行以下步骤： s -e 计算r ≡g y mod p 1 计算H(r ,m) 1 验证等式：H(r ,m)=e 1 如果等式成立，接受签名，否则签名无效。 65 Schnorr签名算法(正确性) 签名体制的正确性证明： s -e r ≡g y mod p 1 s -xe ≡g g mod p ≡gs-xe mod p ≡gxe+k-xe mod p ≡gk mod p ≡r H(r ,m)=e