现代密码学数字签名习题与解答

1、第6章 数字签名 习题及参考答案 （注意：由于本章习题数字较大，所以需要调用大数库进行计算。但由于期末考试题中的数字都是较小的数，且要求手算，所以希望大家参考书中例题和习题的题型代入一些2、3位的数进行手算练习）1. 对于RSA数字签名体制，假设 p=839，q=983，N=p×q=824737。已知私钥d=132111，计算公钥e和对消息m=23547的签名。 解：由RSA签名体制可以得 e=d-1mod(N)=132111-1mod882916=26959， 对消息m的签名为 s= md modN=23547132111mod824737=266749。 2. 对于RSA数字签名

2、体制，假设模N=824737，公钥e=26959。 (1) 已知消息m的签名是 s=8798，求消息m。 (2) 数据对(m, s)=(167058, 366314 )是有效的消息签名对吗？ (3) 已知两个有效的消息签名对(m, s) = (629489, 445587)与(m, s) = (203821, 229149)，求m×m的签名。 解：(1) 由公式可得：m = semodN = 879826959mod824737 = 123456(2) 因为m= semodN = 36631426959mod824737 = 167058 = m，所以是有效的消息签名对。(3) m&

3、#215;m的签名为：y = (m×m)dmodN = s×smodN = 4455587×229149mod824737 = 75915。3. 在ElGamal数字签名体制中，假设p=19，g=13。如果签名者A选取的私钥为x=10，试计算公钥。设签名者A要对消息M=15进行签名，且选取随机数k=11，求签名者A对M=15的签名。并验证该数字签名的有效性。 解：计算公钥：y=gxmodp=1310mod19=6，计算签名：r=gkmodp=1311mod19=2，s=(m-xr)k-1mod(p-1)=(15-10*2)*11-1mod18=11，所以得签名为：

4、(r, s) = (2, 11)。 验证：因为yr*rsmodp= 62*211mod19= 8 = gmmodp=1315mod19=8，所以签名有效。 4. 假设签名者A利用ElGamal数字签名体制对两个消息M1和M2进行签名，得到的签名分别为（r, s1）和（r, s2），并假设gcd(s1s2, p1)=1。 (1) 说明如何利用已知的信息计算随机数 k； (2) 说明如何利用已知的信息计算私钥 k。 解：见教材139页。 5. 假设在ElGamal数字签名体制中，p=31847，g=5，公钥y=25703。已知（23972，31396）是对消息M=8990的签名，（23972，20

5、481）是对消息M=31415的签名，求随机数 k 和私钥 x。 解：由k(v-s)=(w-m)mod(p-1) => k(31396-20481)=(8990-31415)mod31846=> 10915k=9421mod31846因为 gcd(10915, 31846)=1，所以通过求解一次同余方程得：k=1165。再将k代入一次同余方程20481=k-1(31415-23972*x)mod31486得：23972x=23704mod31846，由于gcd(23972, 31846)=2|23704，所以该同余方程有2个解，分别是：7459和23382，再将 x 值代入公钥 y

6、=gxmodp=5xmod31847=25703 中验算得：x=7459。6. 对于Chaumvan Antwerpen不可否认数字签名协议，假设p=1019，q=509，a=475，私钥x=200。 (1) 求公钥y。 (2) 求消息m=555的签名。 (3) 选取随机数对(e1, e2)= (20, 411)，验证签名的有效性。 解：（1）。（2）签名。（3）对(e1, e2)= (20, 411)，计算，把发送给签名者，签名者计算，并且把发给验证者。验证者接收到以后计算，验证与是否相等，如果相等则接收，否则拒绝。这里相等，应该接收。7. 在数字签名标准DSS中，假设p=83，q=41，h

7、=2。求 (1) 参数g； (2) 取私钥x=57，求公钥y； (3) 设消息M=56，取随机数k=23，求M的签名； （注：为了简化，用M代替SHA(M)。）(4) 对M=56的上述签名进行验证。 解：(1) g = h(p-1)/qmodp = 4 (2) y=gxmodp=77(3) r=(gkmodp)modq=10，s=(k-1(M+xr)modq=29，所以签名为(10, 29)。(4) 计算：w=s-1modq=21 u1=(mw)modq=28 u2=(rw)modq=5 v=(gu1yu2)modp)modq=10。所以v=r，签名有效。8. 在数字签名算法DSA中，如果随机数 k 被泄露，将会发生什么问题？ 答：DSA中，参数k泄露后果：如果在DSA签名中使用的 k 值被泄露，因为s k-1(H(m)+xr) mod q，则除 x 外其余参数均为已知，上式由二元一次不定同余方程变为 x 的一元一次同余方程，私钥 x 即可求出，所以攻击者可以由此伪造任意消息的签名。 9. 在数字签名标准DSS中，要求 s0，试分析其原因。 答：s不等于0原因： 如果s0mo