Winnermakesithappenloserletithappen数字签名.ppt

《Winnermakesithappenloserletithappen数字签名.ppt》由会员分享，可在线阅读，更多相关《Winnermakesithappenloserletithappen数字签名.ppt（79页珍藏版）》请在装配图网上搜索。

1、1 数字签名 现代密码学 第 8章 2 本章主要内容 1、 数字签名的基本概念 2、数字签名标准 3、其他签名方案 习题 3 数字签名由公钥密码发展而来，它在网 络安全，包括身份认证、数据完整性、不可 否认性以及匿名性等方面有着重要应用。本 章首先介绍数字签名的基本概念和一些常用 的数字签名算法，然后介绍身份认证协议、 身份证明技术以及其他一些常用的密码协议。 1. 数字签名的基本概念 4 上一章介绍的消息认证其作用是保护通 信双方以防第三方的攻击，然而却不能保护 通信双方中的一方防止另一方的欺骗或伪造。 通信双方之间也可能有多种形式的欺骗，例 如通信双方 A和 B（设 A为发方， B为收方）

2、使 用消息认证码的基本方式通信，则可能发生 以下欺骗： 1.1 数字签名应满足的要求 5 B伪造一个消息并使用与 A共享的密 钥产生该消息的认证码，然后声称该消息来 自于 A。 由于 B有可能伪造 A发来的消息，所以 A就可以对自己发过的消息予以否认。 这两种欺骗在实际的网络安全应用中都 有可能发生，例如在电子资金传输中，收方 增加收到的资金数，并声称这一数目来自发 方。又如用户通过电子邮件向其证券经纪人 发送对某笔业务的指令，以后这笔业务赔钱 了，用户就可否认曾发送过相应的指令。 数字签名应满足的要求 6 因此在收发双方未建立起完全的信任关 系且存在利害冲突的情况下，单纯的消息认 证就显得不

3、够。数字签名技术则可有效解决 这一问题。类似于手书签名，数字签名应具 有以下性质： 能够验证签名产生者的身份，以及产生签 名的日期和时间。 能用于证实被签消息的内容。 数字签名可由第三方验证，从而能够解决 通信双方的争议。 数字签名应满足的要求 7 由此可见，数字签名具有认证功能。 为实现上述 3条性质，数字签名应满足以下 要求： 签名的产生必须使用发方独有的一些信息 以防伪造和否认。 签名的产生应较为容易。 签名的识别和验证应较为容易。 对已知的数字签名构造一新的消息或对已 知的消息构造一假冒的数字签名在计算上都 是不可行的。 数字签名应满足的要求 8 数字签名的产生可用加密算法或特定的 签

4、名算法。 1. 由加密算法产生数字签名 利用加密算法产生数字签名是指将消息或消 息的摘要加密后的密文作为对该消息的数字 签名，其用法又根据是单钥加密还是公钥加 密而有所不同。 1.2 数字签名的产生方式 9 (1) 单钥加密 如图 1(a)所示，发送方 A根据单钥加密 算法以与接收方 B共享的密钥 K对消息 M加密 后的密文作为对 M的数字签名发往 B。该系统 能向 B保证所收到的消息的确来自 A，因为只 有 A知道密钥 K。再者 B恢复出 M后，可相信 M 未被篡改，因为敌手不知道 K就不知如何通 过修改密文而修改明文。具体来说，就是 B 执行解密运算 Y=DK(X)，如果 X是合法消息 M

5、 加密后的密文，则 B得到的 Y就是明文消息 M， 否则 Y将是无意义的比特序列。 1. 由加密算法产生数字签名 10 消息加密产生数字签名的基本方式 11 (2) 公钥加密 如图 1(b)所示，发送方 A使用自己的秘 密钥 SKA对消息 M加密后的密文作为对 M的数 字签名， B使用 A的公开钥 PKA对消息解密， 由于只有 A才拥有加密密钥 SKA，因此可使 B 相信自己收到的消息的确来自 A。然而由于 任何人都可使用 A的公开钥解密密文，所以 这种方案不提供保密性。为提供保密性， A 可用 B的公开钥再一次加密，如图 1(c)所示。 1. 由加密算法产生数字签名 12 下面以 RSA签名

6、体制为例说明数字签名的产生 过程。 体制参数。 选两个保密的大素数 p和 q，计算 n=p q， (n)=(p-1)(q-1)；选一整数 e，满足 1e(n)， 且 gcd(n),e)=1；计算 d，满足 de1 mod (n)； 以 e,n为公开钥 ,d,n为秘密钥。 签名过程。 设消息为 M，对其签名为 SMd mod n 1. 由加密算法产生数字签名 13 验证过程。 接收方在收到消息 M和签名 S后，验证 是否成立，若成立，则发送方的签名有效。 实际应用时，数字签名是对消息摘要加密产 生，而不是直接对消息加密产生，如图 6.3(a)图 6.3(d)所示。 ? m odeM S n 1.

7、 由加密算法产生数字签名 14 由加密算法产生数字签名又分为 外部保密方式 和 内部保密方式 ，外部保密方式是指数字签名是直 接对需要签名的消息生成而不是对已加密的消息生 成，否则称为内部保密方式。 外部保密方式便于解决争议，因为第 3方在处 理争议时，需得到明文消息及其签名。但如果采用 内部保密方式，第 3方必须得到消息的解密密钥后 才能得到明文消息。如果采用外部保密方式，接收 方就可将明文消息及其数字签名存储下来以备以后 万一出现争议时使用。 1. 由加密算法产生数字签名 15 2. 由签名算法产生数字签名 签名算法的输入是明文消息 M和密钥 x， 输出是对 M的数字签名，表示为 S=Si

8、gx(M)。 相应于签名算法，有一验证算法，表示为 Verx(S,M)，其取值为 算法的安全性在于从 M和 S难以推出密 钥 x或伪造一个消息 M使 M和 S可被验证为真。 , xx x Tr u e S S ig M V e r S M F a ls e S S ig M 2. 由签名算法产生数字签名 16 公钥签名方案 公钥签名方案： 利用私钥生成签名，利用公钥验证签名，只有 私钥的拥有者才能生成签名，所以能够用于证 明谁生成的消息。 任何知道公钥的人可以验证消息，（他们要确 认公钥拥有者的身份，这是公钥的密钥分配问 题），通常不对整个消息签名，因为这将会使 交换信息长度增加一倍，使用消息

9、的 hash 值， 数字签名可以提供消息的不可否认性 , 17 数字签名的执行方式有两类： 直接方式 和具有仲裁的方式。 1. 直接方式 直接方式是指数字签名的执行过程只有 通信双方参与，并假定双方有共享的秘密钥 或接收一方知道发方的公开钥。 1.3 数字签名的执行方式 18 直接方式的数字签名有一公共弱点，即方案的 有效性取决于发方秘密钥的安全性。如果发方想对 已发出的消息予以否认，就可声称自己的秘密钥已 丢失或被窃，因此自己的签名是他人伪造的。可采 取某些行政手段，虽然不能完全避免但可在某种程 度上减弱这种威胁。例如，要求每一被签名的消息 都包含有一个时戳（日期和时间）并要求密钥丢失 后立

10、即向管理机构报告。这种方式的数字签名还存 在发方的秘密钥真的被偷的危险，例如敌手在时刻 T偷得发方的秘密钥，然后可伪造一消息，用偷得 的秘密钥为其签名并加上 T以前的时刻作为时戳。 1. 直接方式 19 上述直接方式的数字签名所具有的缺陷都可通 过使用仲裁者得以解决。和直接方式的数字签名一 样，具有仲裁方式的数字签名也有很多实现方案， 这些方案都按以下方式运行： 发方 X对发往收方 Y 的消息签名后，将消息及其签名先发给仲裁者 A， A 对消息及其签名验证完后，再连同一个表示已通过 验证的指令一起发往收方 Y。此时由于 A的存在， X 无法对自己发出的消息予以否认。在这种方式中， 仲裁者起着重

11、要的作用并应取得所有用户的信任。 2. 具有仲裁方式的数字签名 20 以下是具有仲裁方式数字签名的几个实 例，其中 X表示发方， Y表示收方， A是仲裁 者， M是消息， X Y： M表示 X给 Y发送一消 息 M。 2. 具有仲裁方式的数字签名 21 例 1 签名过程如下： X A： MEKXAIDXH(M)。 A Y： EKAYIDXMEKXAIDXH(M)T。 其中 E是单钥加密算法， KXA和 KAY分别 是 X与 A共享的密钥和 A与 Y共享的密钥， H(M) 是 M的杂凑值， T是时戳， IDX是 X的身份。 2. 具有仲裁方式的数字签名 22 在中， X以 EKXAIDXH(M)

12、作为自己 对 M的签名，将 M及签名发往 A。在中 A将 从 X收到的内容和 IDX、 T一起加密后发往 Y， 其中的 T用于向 Y表示所发的消息不是旧消息 的重放。 Y对收到的内容解密后 ,将解密结果 存储起来以备出现争议时使用。 2. 具有仲裁方式的数字签名 23 如果出现争议， Y可声称自己收到的 M的确 来自 X，并将 EKAYIDXMEKXAIDXH(M) 发给 A，由 A仲裁， A由 KAY解密后，再用 KXA对 EKXAIDXH(M)解密，并对 H(M)加以 验证，从而验证了 X的签名。 2. 具有仲裁方式的数字签名 24 以上过程中，由于 Y不知 KXA，因此不能直接检查 X的

13、 签名，但 Y认为消息来自于 A因而是可信的。 所以在整个过程中， A必须取得 X和 Y的高度信任： X相信 A不会泄露 KXA，并且不会伪造 X的签名 ; Y相信 A只有在对 EKAYIDXMEKXAIDXH(M)T中的杂 凑值及 X的签名验证无误后才将之发给 Y; X， Y都相信 A可公正地解决争议。 如果 A已取得各方的信任，则 X就能相信没有人能伪造 自己的签名， Y就可相信 X不能对自己的签名予以否认。 2. 具有仲裁方式的数字签名 25 本例中消息 M是以明文形式发送的，因 此未提供保密性，下面两个例子可提供保密 性。 例 2 签名过程如下： X A: IDXEKXYMEKXAID

14、XH(EKXYM)。 A Y: EKAYIDXEKXYMEKXAIDXH(EKXYM)T。 2. 具有仲裁方式的数字签名 26 其中 KXY是 X， Y共享的密钥，其他符号 与例 1相同。 X以 EKXAIDXH(EKXYM)作为对 M的签名，与由 KXY加密的消息 M一起发给 A。 A对 EKXAIDXH(EKXYM)解密后通过验证杂 凑值以验证 X的签名，但始终未能读取明文 M。 A验证完 X的签名后，对 X发来的消息加 一时戳，再用 KAY加密后发往 Y。解决争议的 方法与例 1一样。 2. 具有仲裁方式的数字签名 27 本例虽然提供了保密性，但还存在与上 例相同的一个问题，即仲裁者可和

15、发方共谋 以否认发方曾发过的消息，也可和收方共谋 以伪造发方的签名。这一问题可通过下例所 示的采用公钥加密技术的方法得以解决。 例 3 签名过程如下： X A： IDXESKXIDXEPKYESKXM。 A Y： ESKAIDXEPKYESKXMT。 2. 具有仲裁方式的数字签名 28 其中 SKA和 SKX分别是 A和 X的秘密钥， PKY是 Y的公开钥，其他符号与前两例相同。 第步中， X用自己的秘密钥 SKX和 Y的公开 钥 PKY对消息加密后作为对 M的签名，以这种方式 使得任何第 3方（包括 A）都不能得到 M的明文消息。 A收到 X发来的内容后，用 X的公开钥可对 ESKXIDXE

16、PKYESKXM解密，并将解密得到的 IDX 与收到的 IDX加以比较，从而可确信这一消息是来 自于 X的（因只有 X有 SKX）。 第步， A将 X的身份 IDX和 X对 M的签名加上 一时戳后，再用自己的秘密钥加密发往 Y。 2. 具有仲裁方式的数字签名 29 与前两种方案相比，第 3种方案有很多优 点。 首先，在协议执行以前，各方都不必有 共享的信息，从而可防止共谋。 第二，只要仲裁者的秘密钥不被泄露， 任何人包括发方就不能发送重放的消息。 最后，对任何第三方（包括 A）来说， X 发往 Y的消息都是保密的。 2. 具有仲裁方式的数字签名 30 数字签名标准 DSS(Digital Si

17、gnature Standard)是由美国 NIST公布的联邦信息处 理标准 FIPS PUB 186，其中采用了上一章介 绍的 SHA和一新的签名技术，称为 DSA(Digital Signature Algorithm)。 DSS最初 于 1991年公布，在考虑了公众对其安全性的 反馈意见后，于 1993年公布了其修改版。 2. 数字签名标准 31 首先将 DSS与 RSA的签名方式做一比较。 RSA算法既能用于加密和签名，又能用于密 钥交换。与此不同， DSS使用的算法只能提 供数字签名功能。图 2用于比较 RSA签名和 DSS签名的不同方式。 2.1 DSS的基本方式 32 RSA 签

18、名 RSA 加密解密是可交换的 可以用于数字签名方案 给定 RSA 方案 (e,R), (d,p,q) 要签名消息 M：计算 : S = Md(mod R) 要验证签名 ,计算 : M = Se(mod R) = Me.d(mod R) = M(mod R) 33 使用 RSA加密、认证： 使用发送者的私钥签名一个消息，使用接收者 的公钥加密消息 看起来，一个消息可用 RSA加密、签名而不改 变大小，但是，加密使用的是消息接收者的模， 签名是消息发送者的模，后着可能比前者小 交换两者顺序？ 签名常使用 HASH函数值。 RSA 签名的使用 34 RSA签名与 DSS签名的不同方式 35 采用

19、RSA签名时，将消息输入到一个杂 凑函数以产生一个固定长度的安全杂凑值， 再用发方的秘密钥加密杂凑值就形成了对消 息的签名。消息及其签名被一起发给收方， 收方得到消息后再产生出消息的杂凑值，且 使用发方的公开钥对收到的签名解密。 这样收方就得了两个杂凑值，如果两个 杂凑值是一样的，则认为收到的签名是有效 的。 RSA签名与 DSS签名的不同 36 DSS签名也利用一杂凑函数产生消息的 一个杂凑值，杂凑值连同一随机数 k一起作 为签名函数的输入，签名函数还需使用发送 方的秘密钥 SKA和供所有用户使用的一族参 数，称这一族参数为 全局公开钥 PKG。 RSA签名与 DSS签名的不同 37 签名函

20、数的两个输出 s和 r就构成了消息 的签名 (s， r)。接收方收到消息后再产生出 消息的杂凑值，将杂凑值与收到的签名一起 输入验证函数，验证函数还需输入全局公开 钥 PKG和发送方的公开钥 PKA。验证函数的 输出如果与收到的签名成分 r相等，则验证 了签名是有效的。 RSA签名与 DSS签名的不同 38 US Federal Govt approved signature scheme (FIPS PUB 186) ，使用 SHA hash alg， NIST 即求 S = k-1(M - x.K) mod (p-1) 签名是 (K,S) ， k 应该被销毁 同 ElGamal 加密方案，

21、 签名信息也是消息的 2倍 验证 (K,S) 是 对 M的签名 : yK.KSmod p = aMmod p 53 (2) 签名的产生过程 对于待签名的消息 m， A执行以下步骤： 计算 m的杂凑值 H(m)。 选择随机数 k： k Z*p，计算 rgk(mod p)。 计算 s(H(m)-xr)k-1(mod p-1)。 以 (r,s)作为产生的数字签名。 ElGamal签名体制 54 (3) 签名验证过程 接收方在收到消息 m和数字签名 (r, s)后， 先计算 H(m)，并按下式验证： 正确性可由下式证明： ()( , ( , ) , ( ) ) ( m o d )r s H mV e

22、r y r s H m T r u e y r g p ( ) ( ) ( m o d )r s r x k s r x H m r x H my r g g g g p ElGamal签名体制 55 ElGamal 签名方案举例 取 p=11, g=2；选择私钥 x=8 ； 计算 : y = ax mod p = 28 mod 11 = 3 公钥是 : y=3,g=2,p=11；对 M=5 签名： 选择随机数 k=9，确定 gcd(10,9)=1， 计算 : K = ak mod p = 29 mod 11 = 6 解 : 5 = 8.6+9.S mod 10; nb 9-1 = 9 mod

23、 10; 因此 S = 9.(5-8.6) = 3 mod 10 签名是 (K=6,S=3)。 要验证签名 , 确认 : 36.63 = 25 mod 11； 3.7 = 32 = 10 mod 11 56 3. Schnorr签名体制 (1) 体制参数 p：大素数， p2512； q：大素数， q|(p-1)， q2160； g： g RZ*p,且 gq1(mod p)； x：用户 A的秘密钥， 1xq； y：用户 A的公开钥， ygx(mod p)。 3. Schnorr签名体制 57 (2) 签名的产生过程 对于待签名的消息 m， A执行以下步骤： 选择随机数 k： 1kq，计算 rgk

24、(mod p)。 计算 e=H(r, m)。 计算 sxe+k(mod q)。 以 (e, s)作为产生的数字签名。 3. Schnorr签名体制 58 (3) 签名验证过程 接收方在收到消息 m和数字签名 (e, s)后， 先计算 rgsy-e(mod p)，然后计算 H(r,m)， 并按下式验证 其正确性可由下式证明： ( , ( , ) , ) ( , )V e r y e s m Tru e H r m e ( m o d )s e x e k x e kr g y g g r p 3. Schnorr签名体制 59 4. Neberg-Rueppel签名体制 该体制是一个消息恢复式签

25、名体制，即 验证人可从签名中恢复出原始消息，因此签 名人不需要将被签消息发送给验证人。 (1) 体制参数 p：大素数； q：大素数， q|(p-1)； g： g RZ*p，且 gq1(mod p)； x：用户 A的秘密钥， x RZ*p； y：用户 A的公开钥， ygx(mod p)。 4. Neberg-Rueppel签名体制 60 (2) 签名的产生过程 对于待签名的消息 m， A执行以下步骤： 计算出 ，其中 R是一个单一映 射，并且容易求逆，称为冗余函数。 选择一个随机数 k(0kq)，计算 rg-k mod p。 计算 。 计算 sxe+k(mod q)。 以 (e, s)作为对 m

26、的数字签名。 ()m R m ( m od )e mr p 4. Neberg-Rueppel签名体制 61 (3) 签名的验证过程 接收方收到数字签名 (e, s)后，通过以 下步骤来验证签名的有效性： 验证是否 0ep。 验证是否 0sq。 计算 vgsy-e(mod p)。 4. Neberg-Rueppel签名体制 62 计算 mve(mod p)。 验证是否 m R(m)，其中 R(m)表示 R的值域。 恢复出 m=R-1(m)。 这个签名体制的正确性可以由以下等式证明： ( m o d ) ( m o d ) ( m o d ) ( m o d )s e x e k x e km

27、v e p g y e p g e p g e p m 4. Neberg-Rueppel签名体制 63 5. Okamoto签名体制 (1) 体制参数 p：大素数，且 p2512; q：大素数， q|(p-1)，且 q2140； g1, g2：两个与 q同长的随机数； x1, x2：用户 A的秘密钥，两个小于 q的随机 数； y：用户 A的公开钥， yg-x11g-x22(mod p)。 5. Okamoto签名体制 64 (2) 签名的产生过程 对于待签名的消息 m， A执行以下步骤： 选择两个小于 q的随机数 k1,k2 RZ*q。 计算杂凑值： eH(gk11gk22(mod p),m

28、)。 计算： s1(k1+ex1)(mod q)。 计算： s2(k2+ex2)(mod q)。 以 (e, s1, s2)作为对 m的数字签名。 5. Okamoto签名体制 65 (3) 签名的验证过程 接收方在收到消息 m和数字签名 (e, s1, s2) 后，通过以下步骤来验证签名的有效性： 计算 vgs11gs22ye(mod p)。 计算 e=H(v,m)。 验证： 其正确性可通过下式证明： 12( , ( , , ) , )V e r y e s s m T r u e e e 1 2 1 1 2 2 1 2 1 21 2 1 2 1 2 1 2( m o d ) ( m o d

29、 ) ( m o d )s s k e x k e x x e x e k kev g g y p g g g g p g g p 5. Okamoto签名体制 66 设 n是一个大合数，找出 n的所有素因子 是一个困难问题，称之为大数分解问题。下 面介绍的两个数字签名体制都基于这个问题 的困难性。 3.2 基于大数分解问题的数字签名体制 67 1. Fiat-Shamir签名体制 (1) 体制参数 n： n=pq，其中 p和 q是两个保密的大素数； k：固定的正整数； y1,y2, ,yk：用户 A的公开钥，对任何 i(1ik)， yi都是模 n的平方剩余； x1,x2, ,xk：用户 A的

30、秘密钥，对任何 i(1ik)， 。 1 ( m o d ) iix y n 1. Fiat-Shamir签名体制 68 (2) 签名的产生过程 对于待签名的消息 m， A执行以下步骤： 随机选取一个正整数 t。 随机选取 t个介于 1和 n之间的数 r1,r2, ,rt， 并对任何 j(1jt)，计算 Rjr2j(mod n)。 1. Fiat-Shamir签名体制 69 计算杂凑值 H(m,R1,R2, ,Rt)，并依次取出 H(m,R1,R2, ,Rt)的前 kt个比特值 b11, ,b1t,b21, ,b2t, ,bk1, ,bkt。 对任何 j(1jt)，计算 。 以 (b11, ,b

31、1t,b21, ,b2t, ,bk1, ,bkt),(s1, ,st) 作为对 m的数字签名。 1 ( m od )ijk bj j i i s r x n 1. Fiat-Shamir签名体制 70 (3) 签名的验证过程 收方在收到消息 m和签名 (b11, ,b1t,b21， ,b2t, ,bk1, ,bkt),(s1, ,st)后， 用以下步骤来验证： 对任何 j(1jt)，计算 。 计算 H(m,R1,R2, ,Rt)。 2 1 ( m od )ijk bj j i i R s y n 1. Fiat-Shamir签名体制 71 验证 b11, ,b1t,b21, ,b2t, ,bk

32、1, ,bkt是 否依次是 H(m,R1,R2, ,Rt)的前 kt个比特。 如果是，则以上数字签名是有效的。 正确性可以由以下算式证明： 22 1 1 1 2 2 2 1 (m o d ) ( ) ( ) (m o d ) i j i j i j ij k k k b b b j j i j i i i i i k b j i i j i R s y n r x y r x y r R n 1. Fiat-Shamir签名体制 72 2. Guillou-Quisquater签名体制 (1) 体制参数 n： n=pq， p和 q是两个保密的大素数； v： gcd(v,(p-1)(q-1)=1

33、； x：用户 A的秘密钥， x RZ*n； y：用户 A的公开钥， y Z*n， 且 xvy1(mod n)。 2. Guillou-Quisquater签名体制 73 (2) 签名的产生过程 对于待签消息 m， A进行以下步骤： 随机选择一个数 k Z*n，计算 Tkv(mod n)。 计算杂凑值： e=H(m,T)，且使 1ev； 否则，返回步骤。 计算 skxe mod n。 以 (e, s)作为对 m的签名。 2. Guillou-Quisquater签名体制 74 (3) 签名的验证过程 接收方在收到消息 m和数字签名 (e, s)后， 用以下步骤来验证： 计算出 Tsvye(mod

34、 n)。 计算出 e=H(m,T)。 验证： 正确性可由以下算式证明： ( , ( , ) , )V e r y e s m T ru e e e ( m o d ) ( ) ( m o d ) ( ) ( m o d ) ( m o d ) v e e v e v v e v T s y n k x y n k x y n k n T 2. Guillou-Quisquater签名体制 75 带密钥的 HASH 以上的签名方法都是公钥技术，计算与数据量较 大 ，需要私钥的认证方案。 好的方法是使用快速的 hash 函数： 密钥与消息同时参加运算 : KeyedHash = Hash(Key|

35、Message) 有一些弱点 ，随后建议 : KeyedHash = Hash(Key1|Hash(Key2|Message) 76 HMAC HMAC 是使用带密钥的 HASH函数的结果，成 为 internet标准 (RFC2104)。 结构： HMACK = Hash(K+ XOR opad)|Hash(K+ XOR ipad)|M) K+ 是经过填充的密钥 ， opad, ipad 特殊的填 充值， Opad=01011010重复 b/8次； ipad=00110110重复 b/8次 安全性是基于原来的 HASH函数的安全性。任 何 MD5, SHA-1, RIPEMD-160 都可以

36、这样使用。 77 1. 在 DSS数字签名标准中，取 p=83=2 41+1， q=41， h=2，于是 g224 mod 83，若取 x=57，则 ygx457=77 mod 83。在对消息 M=56签名 时，选择 k=23，计算签名并进行验证。 2. 在 DSA签名算法中，参数 k泄露会产生 什么后果？ 习题 78 3. Illustrate the operation of El Gamal signatures, given the following parameters: prime p=31； prim root a=3 Determine a suitable private and public key, and then show the signing and verification of a message M=7. 习题 79 THE END！