翻译:中国科学技术大学信息安全专业老师 也是成立的。这种方案的安全与离散对数问题紧密相关,但是并不等价于离散对数问题。许 多更安全和更有效的签名方案都是从 EI Gamal签名方案派生而来的。一个这样的签名算法 是数字签名算法(DSA, digital signature algorithm)1。在这个方案中,用户A的私有密 钥和公开密钥通过下述步骤生成 1)选择一个素数q,2139<q<216。 2)选择一个整数t,0≤t≤8,和一个素数p,21164<p<2312+,所以q整除p-1。 3)选择a,1<a<p-1,并计算g= a(p-l)q mod p。如果g=1,用一个新的a再 试。(这一步计算以p为模的阶q的生成元g。) 4)选择一个a,使其满足1≤a≤q-1。 5)计算y=g"mdp。 6)A的私有密钥就是数值a,公开密钥是(p,q1,g,y)。 A为了对文档m进行签名,使用SHA-1计算散列值h(m),并且转换成一个整数,然 后 7)随机地选择一个整数k,1≤k≤q-1。 8)计算r=( g mod p)modq 9)计算 k-mod q 10)计算s=k-(h(m)+ar)modq。 A对m的签名就是整数对(r,S)。这个签名将用A的公开密钥(P,q,g,y)进行检测: 验证1≤r≤q和1≤s≤q 计算= s-mod q 计算41=W,h(m)mdq和l2=rwmd 计算v=(g“y“modp)modq 当且仅当ν=r,则通过验证 RSA签名 在文献[127]中描述的RSA算法是用它的发明者 Rivest、 Shamir和 Adleman的第一个 字母命名的,它同样可以用于签名和加密。RSA的这种特定的性质必须对许多关于数字签 名和公开密钥密码的流行的误解负责。在RSA签名方案中,用户A选择两个素数p和q, 第9页共19页 创建时间:2003/7/91446:00翻译：中国科学技术大学信息安全专业老师 第 9 页 共 19 页 创建时间：2003/7/19 14:46:00 也是成立的。这种方案的安全与离散对数问题紧密相关，但是并不等价于离散对数问题。许 多更安全和更有效的签名方案都是从 EI Gamal 签名方案派生而来的。一个这样的签名算法 是数字签名算法（DSA，digital signature algorithm）[116]。在这个方案中，用户 A 的私有密 钥和公开密钥通过下述步骤生成。 1）选择一个素数 q ， 159 160 2  q  2 。 2）选择一个整数 t ，0  t  8 ，和一个素数 p ， t t p 511 64 512 64 2 2 − +   ，所以 q 整除 p −1。 3）选择  ，1   p −1 ，并计算 g p p q mod ( −1)/ = 。如果 g = 1 ，用一个新的  再 试。（这一步计算以 p 为模的阶 q 的生成元 g 。） 4）选择一个 a ，使其满足 1  a  q −1。 5）计算 y g p a = mod 。 6）A 的私有密钥就是数值 a ，公开密钥是 ( p,q, g, y)。 A 为了对文档 m 进行签名，使用 SHA-1 计算散列值 h(m) ，并且转换成一个整数，然 后： 7）随机地选择一个整数 k ，1  k  q −1。 8）计算 r g p q k = ( mod )mod 。 9）计算 k mod q −1 。 10）计算 s k (h(m) ar)mod q 1 = + − 。 A 对 m 的签名就是整数对 (r,s) 。这个签名将用 A 的公开密钥 ( p,q, g, y) 进行检测： ·验证 1 r  q 和 1 s  q ·计算 w s mod q −1 = ·计算 u1 = wh(m)mod q 和 u2 = rwmod q ·计算 v g y p q u u ( mod )mod 1 2 = ·当且仅当 v = r ，则通过验证。 RSA 签名 在文献[127]中描述的 RSA 算法是用它的发明者 Rivest、Shamir 和 Adleman 的第一个 字母命名的，它同样可以用于签名和加密。RSA 的这种特定的性质必须对许多关于数字签 名和公开密钥密码的流行的误解负责。在 RSA 签名方案中，用户 A 选择两个素数 p 和 q