签名算法

数字签名的算法

签名算法是指数字签名的算法。数字签名，就是只有信息的发送者才能产生的别人无法伪造的一段数字串，这段数字串同时也是对信息的发送者发送信息真实性的一个有效证明。数字签名是通过一个单向函数，对要传送的信息进行处理得到的用以认证信息来源，并核实信息在传送过程中是否发生变化的一个字母数字串。应用最为广泛的三种签名算法是：Rabin签名、DSS签名、RSA签名。

基本概念

签名算法是指数字签名的算法。数字签名（又称公钥数字签名、电子签章）是一种类似写在纸上的普通的物理签名，但是使用了公钥加密领域的技术实现，用于鉴别数字信息的方法。一套数字签名通常定义两种互补的运算，一个用于签名，另一个用于验证。

数字签名是通过一个单向函数，对要传送的信息进行处理得到的用以认证信息来源，并核实信息在传送过程中是否发生变化的一个字母数字串。数字签名提供了对信息来源的确定并能检测信息是否被篡改。数字签名要实现的功能是我们平常的手写签名要实现功能的扩展。平常在书面文件上签名的主要作用有两点，一是因为对自己的签名本人难以否认，从而确定了文件已被自己签署这一事实；二是因为自己的签名不易被别人模仿，从而确定了文件是真的这一事实。采用数字签名，也能完成这些功能：

（1）确认信息是由签名者发送的；

（2）确认信息自签名后到收到为止，未被修改过。

数字签名算法有映象式和印记式两类。由于印记式的签名速度和验证速度比映象式快得多，因此印记式数字签名算法更为实用。

实现方法

实现数字签名有很多方法，数字签名采用较多的是公钥加密技术，同时应用最为广泛的三种是：Hash签名、DSA签名、RSA签名。

对称密钥密码算法进行数字签名

对称密钥密码算法所用的加密密钥和解密密钥通常是相同的，即使不同也可以很容易地由其中的任意一个推导出另一个。在此算法中，加、解密双方所用的密钥都要保守秘密。

Lamport发明了称为Lamport.Difle的对称算法：利用一组长度是报文的比特数(n)两倍的密钥A，来产生对签名的验证信息，即随机选择2n个数B，由签名密钥对这2n个数B进行一次加密交换，得到另一组2n个数C。

发送和接收的方式如下：

（1）发送

发送方从报文分组M的第一位开始，检查M的第i位：

M的第i位为0时，取密钥A的第i位；M的第i位为1时，取密钥A的第i+1位。

直至报文全部检查完毕，所选取的n个密钥位形成了最后的签名。

（2）接收

接受方对签名进行验证，从第一位开始依次检查报文M：

M的第i位为0时，签名中的第i组信息是密钥A的第i位；M的第i位为1时，签名中的第i组信息为密钥A的第i+1位。

直至报文全部验证完毕后，就得到了n个密钥，由于接受方发送验证信息c，所以可以利用得到的n个密钥检验验证信息，从而确认报文是否是由发送方所发送。

Hash签名

单向函数的概念是计算起来相对容易，但求逆却非常困难。也就是说，已知X，我们很容易计算f(X)。但已知f(X)，却难于计算出X。

单向Hash函数有很多名字：压缩函数、缩短函数、消息摘要、指纹等。单向Hash函数H(M)对一则任意长度的消息进行处理，返回一个具有固定长度m的散列值h：

h=H(M)，其中h的长度为m=H(M)具有以下属性：

（1）给定M，很容易计算出h，这表现了函数的快速性；

（2）给定h，很难计算出满足H(M)=h的M，这表现了函数的单向性；

（3）给定M1，很难找到一则消息M2，使得H(M1)=H(M2)；

（4）h=H(M)，h的每一比特都与M 的每一比特有关，并有高度敏感性。即每改变M的一比特，都将对h产生明显影响；

（5）Hash函数除了信息M 自身之外，应该基于发信方的秘密信息对信息M进行确认；

（6）输入数据M没有长度限制；

（7）对输入任何长度的M数据能够生成该输入报文固定长度的输出。

相关步骤

RSA数字签名算法

产生签名与验证参数：

Step1，签名人A选择两个大素数p、q，计算n=pq及中Φ(n) = (P-1)(q-1)；

Step2，寻找e 、d 使满足(eΦ(n)) 1及ed l(mod Φ(n))；

Step3，公开验证参数{n,e}，A 保存{ p, q,d , Φ(n)}作为秘密的签名参数；

Step4，选用一通用的散列函数h(.)。

签名算法：

Step1，A将需签名的文件m(含接收人、内容、签名人、日期等)编码后映射成h(m) ；

Step2，计算

Step3，将{m, }发送至文件接收人B或仲裁人T(A、B、T的含义下同)。

验证算法：

B(或T)检验

是否成立，若成立则接收此文件及签名，否则拒绝接收或宣布无效。

Rabin数字签名算法

产生签名与验证参数：

Step1，签名人A选择两个大素数p、q，计算n=pq；

Step2，公开验证参数n，A 保存{ p, q}作为秘密的签名参数；

Step3，选用一通用的散列函数h(.)。

签名算法：

Step1，A 将需签名的文件m编码后映射成h(m)；

Step2，计算 mod p， mod q及印记

Step3，将{m, ， }发送至文件接收人B或T。

验证算法：

B或T检验

是否成立，若成立则接收此文件及签名，否则拒绝接收或宣布无效。

DSS数字签名算法

产生签名与验证参数：

Step1，A 选择一个大素数p，p-1应具有大素数因子q，选择一个g使g的次数为q，再选择一个计算 mod p；

Step2，公开验证参数{p,q,g,y}，A 保存{ p, q}作为秘密的签名参数；

Step3，选用一通用的散列函数h(.)。

签名算法：

Step1，A 将需签名的文件m编码后映射成h(m)，计算使

Step2，计算

及s (h(m)+xr) mod q；

Step3，将{m,r,s}发送至文件接收人B或T。

验证算法：

Step1，B(或T)先计算u h(m) mod q及v r mod q；

Step2，检验

是否成立，若成立则接收此文件及签名, 否则拒绝接收或宣布无效。

算法比较

下面是对三种签名算法RSA、Rabin、DSS算法的比较。

安全性

由于求解mod n(n=np)的平方根问题以高概率等价于n的整数分解问题（Rabin定理），所以Rabin算法的安全性与RSA大体相当。DSS的安全性是建立在求离散对数问题上，至今虽未证明破解DS与求解q阶乘法群的离散对数等价，但也未找到其他可绕开求离散对数的解法。整数分解与求离散对数的计算复杂度是近似的，因而上述三种签名算法的安全性大体相当。

参数选择

DSS算法参数的选择比前两种算法要容易。RSA算法出于安全性考虑，对参数p、q的选择有一些较严格的要求，如（k为较小自然数）应足够大、gcd(p-1,q-1)应比较小、p 1和q 1都应至少含有一个充分大的素数因子等；Rabin算法对参数p、q的要求与RSA算法大体相同，但为了达到与RSA相当的安全性，其参数p、q应比RSA算法中稍大；DSS算法安全性的关键参数是q，可比前两种算法中的n值略小，但应远大于单独的p和q。

参数共享性

RSA 算法和Rabin算法都无法共享参数；因为DSS算法可以对k有不同选择，所以可以共享参数p、q、g，参数共享时至今尚未发现用户之间可以互相伤害的途径。

签名速度

DSS算法签名速度较慢。RSA算法和Rabin算法签名时耗费时间的主要部分都是mod p、mod q的指数运算，这两种算法签名速度大体相同；DSS 算法签名时mod p(p>q)的指数运算所耗费的时间要比前两种算法长。

验证速度

DSS算法验证速度较慢。Rabin算法验证时需进行一次mod n的平方运算，而RSA算法验证时需进行一次mod n的e次指数运算，因此RSA算法比Rabin算法要稍慢；DSS算法验证时需要进行2次mod p的指数运算，因此DSS算法验证速度较前两种算法慢,，而Rabin算法验证速度最快。

印记长度

DSS算法签名印记较长。RSA算法和Rabin算法的签名印记都是一个mod n 数，只是Rabin算法多了1个很小的数；DSS算法的签名印记是两个mod q数r 、s，比起前两种算法的印记要长一些。

印记的重复性

DSS算法签名印记具有不重复特性。文件m和h(m)完全相同，用DSS算法签名时因每次可以选择不同的k产生签名印记，故DSS算法的签名印记每次可以不同；RSA算法和Rabin算法无此特性，但可以对算法作适当改进，以增加1个随机数加长传送的数据为代价，使算法具有签名印记不重复的特性。

全国各地天气预报查询

上海市