发信人: courieryboo (小凡·每天灌水多一些...), 信区: DC
标 题: 数字签名方案的软件开发
发信站: BBS 水木清华站 (Wed May 24 17:00:08 2000)
摘 要：以数字签名标准DSS改进方案为基础，进行了改进数字签名方案的软件开发，构
造了数字签名软件的数据结构，并设计和实现了数字签名软件的各种算法，同时就加快
算法实现速度进行了改进。
关键词：软件开发；数字签名；DSS
中图分类号：TP311.56 文献标识码：A
Software Developing for Digital Signature Scheme
ZHANG Yu-qing, XIAO Guo-zhen
（Institute of Information Security, Xidian University, Xi′an 710071, China
）
Abstract: An improved digital signature algorithm is introduced, then the so
ftware is developed with emphasis on its algorithms and data structure. The
improvement and discussion of speeding the software are presented.
Key words: software developing; digital signature; DSS
在Internet/Intranet广泛普及和电子商务飞速发展的今天，数字签名已成为计算机
通信网上取代传统的印鉴和手书签名确保网络安全的关键和核心技术之一。在众多已提
出的数字签名方案中，美国国家数字签名标准DSS是1个较为典型的实用的签名方案，为
此有关DSS及其改进方案的软件开发，成为我们的研究课题。
1 数字签名方案
1991年8月美国国家标准局NIST公布了数字签名标准DSS［1］。该标准采用了DSA算
法。DSA为ElGamal方案的变型，它采用了Schnorr方案中g为非原根的做法，以降低签名
的长度。DSS发布后，许多学者提出了DSS改进方案，这当中我们选取YEN S M和LAIH C
S于1995年在文献［2］提出的改进方案为软件开发的原型，记为YL方案。YL方案中，验
证者无需作逆元素计算，由于求逆元素几乎相当于指数运算，相当费时，因此适合验证
者计算能力较小者使用。YL方案安全性与DSA完全一样，都是基于求离散对数的困难问题
。对于其它DSS改进方案的软件开发，可参照本文进行。
1.1 系统参数
p 512-1024比特长的素数，且长度为64的倍数
q 160比特长的素数，且q|p-1
g h(p-1)/q(mod p), 0<h<p,且h(p-1)/q(mod p)>1
x 0<x<q，秘密钥
y gx(mod p)，公开钥
其中：p、q和g公开，也可以为用户公用。秘密密钥是x，公开密钥是y。
另外，算法使用了1个单向Hash函数H(m)，对DSS来说是SHA。但Hash函数可根据具体
情况选取，不一定采用SHA，故本文不讨论Hash函数的软件开发。
1.2 签名过程
设m是待签名的消息
(1)随机生成1个k,0<k<q；
(2)计算
r=(gk mod p)mod q，
及s=k(H(m)+xr)－1（mod q），
若H(m)=0或s=0或r=0，返回步骤(1)。
计算出的(r,s)为消息m的签名。
1.3 验证过程
(1)首先检查r和s是否属于(0,q)，若不是，则(r,s)不是签名。
(2)计算
t=sH(m)mod q,
r′=(gtysrmod p)mod q。
若r′=r成立，则(r,s)是消息m的合法签名；否则为非法签名。
2 数字签名方案的软件开发
2.1 软件步骤
依照YL方案，我们开发的数字签名软件分为3个步骤：
2.1.1 系统参数产生过程
按方案要求，产生系统参数—p、q、g、x和y.p、q和g存放在文件common.dss中，y
存放在文件public.dss中，x存放在文件private.dss中。common.dss和public.dss文件
公开，private.dss文件为签名方的私有文件。
2.1.2 签名过程
签名方读取文件common.dss和private.dss中的系统参数p、q、g和x，产生随机数k
，并对消息文件m计算签名(r,s)，然后将签名存入指定签名文件中。
2.1.3 验证过程
验证方读取系统参数文件common.dss和private.dss中的参数p、q、g和y，并读取指
定签名文件中的签名(r,s)，计算t和r′，验证(r,s)是否是消息m的合法签名。
2.2 数据结构
程序语言PASCAL设计者WIRTH N有1本成名著作《算法+数据结构=程序》。数字签名
软件正是符合这种定义的程序。我们开发数字签名软件的主要工作是对位数较大的二进
制和十进制整数进行处理。这种大整数，是数字签名软件的主要数据结构，它构成了软
件的基础。
我们构造的数据结构如下：
2.2.1 常量
QBITS=160 素数q(注：二进制数)的长度
PBITS素数p(注：二进制数)的长度，如512
BITSLENGTH=2*PBITS 存放大数(注：二
进制数)数组的长度，此长度应为PBITS的2倍，以便可容纳模运算的任何中间结
果
DATALENGTH=BITSLENGTH/log210
存放大数(注：十进制数)数组的长度
2.2.2 数组
binint用于存放大数(注：二进制数)的一维整型数组，长度BITSLENGTH
byteint用于存放大数(注：十进制数)的一维整型数组，长度DATALENGTH
2.3 算法
整个数字签名软件采用模块化设计方法，各模块以函数方式实现。下面将就主要模
块及算法进行阐述，同时考虑到数字签名与公钥算法在软件实现上的类似性，而公钥算
法比分组密码算法大约慢1000倍，故此除了软件实现外，我们还必须进行优化，以加
快软件运行的速度。
2.3.1 基本运算及模块
数字签名方案中的运算主要是模运算，模运算满足交换律、结合律和分配律，并遵
循按模计算原理。
按模计算原理：令a、b、n为整数，OP代表+、-、*运算符，则有
(a OP b)mod n=((a mod n) OP (b mod n)) mod n
按模计算有效地限制了模运算中间结果的范围。对于2个k比特长的数进行模n运算，
任何加、减、乘的中间结果至多为2k比特长。这样将不会产生很大的中间结果，便于存
储和处理2.2节中的数据结构就能满足软件的要求。
故我们开发的数字签名软件的基本模块主要是模运算、素数产生与测试、不同类型
数据的转换等。
基本函数模块：
(1)Plus 功能：求2个数的和；
(2)Substract功能：求2个数的差；
(3)Multiply功能：求2个数的乘积；
(4)Mod 功能：求2个数的商及余数；
(5)IntRandom功能：产生随机数；
(6)ExpMod功能：指数求余，如求gk mod p;
(7)Prime功能：判断1个数是否素数；
(8)Inverse功能：计算某数的乘法逆元，如求a关于mod n的乘法逆元a－1；
(9)类型转换模块 功能：byteint类型变量和binint类型变量的相互转换。
2.3.2 素数生成算法
素数生成算法较多，我们取如下简明的算法：
设｜p｜,｜q｜为所要产生的素数p,q的长度(注：二进制)，运行下述算法以产生签
名方案所需素数：
(1)取｜q｜-1长的n；
(2)计算q=2*n+1；
(3)测试q是否素数，不是则q+2→q，继续测试，直至q为素数；
(4)如果q的长度>｜q｜，则返回步骤(1)重做；
(5)产生了符合要求的素数q；
(6)计算：
s=(2｜p｜-1-1)/(2*q)
t=(2｜p｜-1-1)/(2*q)
(7)产生1个随机数n, s<n<t；
(8)p=2*n*q+1；
(9)如果p不是素数，则返回步骤(7)；
(10)产生了符合要求的素数p。
2.3.3 素数测试算法
素数测试我们采用Lehman概率测试算法，见参考文献［3］。
Lehman定义：e(a,n)=a(n-1)/2mod n, G={e(a,n):a∈Z*n}
如果n是奇数，G={1,n-1}当且仅当n是素数时成立。如果从Z*n中挑选100个a去验证
上式成立，则n不是素数的概率是2－100。
2.3.4 快速指数运算
指数运算是数字签名软件中运算量大的计算。对于求gk mod p最简单而直接的方法
，就是将g连续乘(k-1)次，但这种方法太慢，为此我们以二元法来加快指数运算，即先
将指数表示成二进制数，再进行运算。
例如求g23，23表示成二进制为10111，计算方法为：
(1)令A=g,并去掉10111最左边的1；
(2)由左向右扫描二进制数，遇到“0”，就将A平方；遇到“1”，就将A平方后再乘
以g。
计算过程为：
g→g2→g4*g→g10*g→g22*g→g23
以上计算，共需7次乘法(注：将平方视为乘法运算)，这样大大加快了指数运算。
2.3.5 求逆元运算
求a关于mod n的乘法逆元a－1，可采用欧拉(Euler)定理或欧几里德(Euclid)算法，
后者见参考文献［4］。
欧拉定理：若(a,n)=1，则aΦ(n)=1 mod n，故此有aaΦ(n)-1=1 mod n，进而有aΦ
(n)-1=a－1mod n。对于素数n,Φ(n)=n-1，则逆元a－1＝an-2mod n。
求逆后进行验证，进而可排除所选的n不是素数的情况。
3 结 语
我们基于本文中的数据结构和算法，顺利地实现了DSS及改进方案一类的数字签名软
件开发，同时该软件也可作为参照来实现类似的公开密钥算法。考虑到数字签名的实现
效率，我们将在以下问题上继续研究，以求获得更快更有效的软件实现：①基于不同字
长的计算机的优化处理；②找出程序中费时较多的模块，进行代码优化，或运用汇编语
言加以实现；③运用硬件方法。
感谢：信息保密研究所GDS数字签名方案开发小组成员的有益讨论和帮助。
基金项目：国家自然科学基金资助项目(69673025)
作者简介：张玉清(1966-)，男，河南荥阳人，西安电子科技大学博士生文章编号：100
7-4112(1999)04-0117-03
作者单位：西安电子科技大学 信息保密研究所，陕西 西安 710071
参考文献：
［1］ NIST. The Digital Signature Standard Proposed by NIST［J］. Commun. A
CM, 1992,35(7):36—40.
［2］ YEN S M, LAIH C S. Improved Digital Signature Algorithm［J］. IEEE Tr
ans. On Computers, 1995,44(5):729—730.
［3］ LEHMAN D J. On Primality Tests［J］. SIAM J. Comput., 1982,11(2):374—
375.
［4］ SCHNEIER B. Applied Cryptography: Protocols, Algorithms, and Source C
ode in C［M］.USA:John Wiley & Sons, Inc., 1994.
［责任编辑 郭庆健］
收稿日期：1999-02-01
--
梧桐身旁的浮云里 飘出一弯朦胧的月亮 * *
清清淡淡的月光 静静地飘落在我身旁 ●
ahuang
在寂寞的晚上 我就是一只音乐虫子 ^^ *
飞呀飞呀找不到爱发源的地方... ...
●
※ 来源:·BBS 水木清华站 smth.org·[FROM: 166.111.5.39]