ComSec作业十一：数字签名

13.2 数字签名应该具有哪些性质？

数字签名一般旨在解决两种情形的问题，一是接收方伪造消息并声称该消息是来自发送方的，二是发送方拒绝承认已发送过的消息，在收发双方不能完全信任的情况下，就需要数字签名来解决这个问题。

数字签名有下列特征：

• 它必须能验证签名者，签名日期和时间。
• 它必须能认证被签的消息内容。
• 签名应由第三方仲裁，以解决争执。
• 数字签名具有认证功能。

13.3 数字签名应满足哪些要求？

• 签名必须是与消息相关的二进制位串。

• 签名必须使用发送方某些独有的消息(secret)，以防伪造和否认。

• 产生数字签名比较容易。

• 识别和验证签名比较容易。

• 伪造数字签名在计算上是不可行的。无论是从给定的数字签名伪造消息，还是从给定的消息伪造数字签名，在计算机上都是不可行的。

• 保存数字签名的副本是可行的。

13.6 直接数字签名方法中会遇到哪些威胁？

直接数字签名方法有这样一个弱点: 方法的有效性依赖于发送方私钥的安全性。发送方可以声称他的私钥已经丢失或被盗用，其他人伪造了他的签名，以此否认自己以前曾发送过某条消息。

另一种可能的威胁是：X的私钥可能在时刻T被盗用，但攻击者可用X的签名发一条并加盖一个在T或T之前的时间戳。

13.6

(a)

由算法一知道，返回g时，$g^{q} = 1 \ mod \ p$ 。此时有两种情况，要么q为阶，要么q为阶的整数倍,由DSA的定义，q为(p-1)的一个素因子，所以q只可能是1和q的整数倍，当q为1时，只有g=1时才满足(g=1与题设矛盾) $g^{q} = 1 \ mod \ p$，所以q一定为阶。

(b)

由DSA定义，$g=h^{(p-1)/q} \ mod \ p$,得 $g^{q} = h^{p-1} \ mod \ p$

p为素数，由费尔马小定理,$h^{p-1} = 1 \ mod \ p$

所以始终有$g^{q} = 1 \ mod \ p$ ，又g不等于1，证明过程与上题基本相同，q一定为阶。

©

由拉格朗日定理，求生成元的个数，好像就是求左陪集的个数，不知道这样理解正不正确…

子群的阶为$\phi(q)=q-1$，$Z_{p}$的阶为$\phi(p)$=p-1,由拉格朗日定理8.1，(左陪集)生成元的个数为(p-1)/(q-1)

q=157为素数，有$\phi{(q)}=156$。所以算法1需要经过 40193-1/157-1 ≈ 258 轮循环，才可以找到一个生成元。

(4) 不愿意。由c: 如果p为1024位长，q为160位长，算法一大概需要$2^{1024}/2^{160}=2^{864}$轮循环，才可以得到一个生成元。

(5) 算法2第一次找不到生成元的条件是第一次就找到g=1，此时$1 = h^{(p-1)/q} \ mod \ p$

此时(p-1)/q要整除以h的阶r。相当于是要找阶为r的生成元的个数。

又有公式

$\sum_{r\ | (p-1)/q}\phi(r)$=(p-1)/q。

所以首次找不到生成元的概率为$\frac{(p-1)/q}{(p-1)}$=1/q=1/157。

所以，首次找到生成元的概率为156/157 (这么大?~…)