о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 5 Vol.36 No.5 1999



ǩDSS/DSAļӦ÷
̷ġн
ժҪżͨżķչǩõ˹㷺Ӧ.ǩ׼DSS/DSAΪȺǩǩģt,n֤ԼԶ֤̿3Ӧ÷.Ⱥ˷ֱǩͬһļȻеĸǩͬһȺǩ.ǩģt,n֤n֤еκt֤ͬһǩ.Զ֤֤̿ǩDSAܽϣ֤µ˼·.
ؼʡǩȺǩ֤֤
ͼšTP393;TN918
SEVERAL APPLIED SCHEMES BASED ON DSS/DSA 
SIGNATURE SCHEME
TAN Kai-Jun, ZHU Hong-Wen, and GU Shang-Jie
(Department of Electronic Engineering, Shanghai Jiaotong University,Shanghai200030)
AbstractWith the development of the technology of computer and network communication, digital signature schemes have got extensive application. In the paper here, three applied schemes based on USA's digital signature standard DSS/DSA are presented. They include multisignature scheme, digital signature scheme with (t,n) shared verification and remote password authentication scheme. The multisignature scheme allows multiple signers to sign the same message separately and all individual signatures can be combined into a multisignature. The digital signature scheme with (t,n) shared verification lets any t verifiers in n collaborate to verify a signature. The remote password authentication scheme combines the password authentication with digital signature DSA closely, which provides a new way of thinking for password authentication.
Key wordsdigital signature, multisignature, shared verification,password authentication
1
ǩԴ1976Ӧýͼձעѧо߸ӦûҪȺ˶ǩ.1985꣬ELGAmalһϻɢELGAmalǩǩʷһҪ̱.˺Ľ13.Ϊǩ϶࣬ȱͳһı׼ʱ׼֯1984רΪ.ͬʱı׼֯Ϊǩı׼ҲؽйΪʢ.Ұȫұ׼ͨ1991ǩDSS㷨׼DSA.DSAҲǻELGAmalǩ.뵱Ƴݼܱ׼DESһDSAҲѧǿҷӦӦлģҲ.NIST˻ķӦΪ˽DSAΪFIPS׼ȡһϵеĴʩDSA.DSAĳ̨ؽѧ޴Ӱ.
żͨżķչӦĸӻǩҲϵĵǩ֤ģʽչΪ㷺.һЩ£һļҪͬʱǩôҪȺǩеһЩף3ݡף4.һһǩҪ˹֤ͬף5ݡף6.⣬C.C.Changˣ7ݽELGAmalǩӦõԶ̿.֮ǩӦǹ㷺.DSAǩ㷨ڵķӦΣNISTڽΪFIPS׼ӦǰпܽDESһΪʱ׼.ԱǻDSA㷨3Ӧ÷Ⱥǩǩģt,n֤Զ֤.
2DSA㷨
DSA㷨漰ҪУ
pΪһģ2511<p<2512qp-1һӣ2159<q<2160=h(p-1)/q mod ph0<h<pһh(p-1)/q mod p>1.Hһhashʹùһ֪hashֵϢڼǲܵ.ҳͬhashֵĲͬϢڼҲǲܵ.
xiûUi˽Կ0<xi<qyi=xi mod pUiĹԿ.ûUiΪ˷һǩϢ£
1. ѡһkiʹ0<ki<q
2. ri=(ki mod p) mod q,
si=(k-1i(H(m)+xiri))mod q,
k-1ikiģqĳ棬(k-1iki)mod q=10<k-1i<qmҪ͵Ϣ
3. Ϣmǩrisiһ͸Uj.
Ϊ֤ǩm,r,sֱUiյmrisiUjȿǷ0<r䣬s<qһǩ.Uj㣺
w=(s)-1 mod q (wsģqĳ)
U1=(H(m)w) mod q
U2=((r)w)mod q
V=((()U1(yi)U2)mod p) mod q
V=r䣬ǩ͵õ֤UjյϢUiа.Vr䣬ôϢܱ޸ģUiȷǩðǩϢΪЧ.
3Ⱥǩ
һЩ£һЩҪļҪ˵ǩһĿͬҪĶ෽ͬǩǾҪȺǩ.һֻDSAȺǩ.
nûǩͬһϢm.
3.1֤ǩ
ÿûѡki0<ki<q㣺
ri=(ki mod p) mod q
{ri,ki}ûһûri,kiãû

ôûUiԿxiǩϢm.
si=(k-1(H(m,T)+xir))mod q1siq-1
Tǩķÿûϵͳǩʱ־Ҫûڸʱǩ.ֹǩز.
Ui(i=1,2,n)ǩ(ռ֤ǩȺǩ.ǩûϢ)͸ǩ{ri,si}(i=1,2,,n)Ҫ֤ǩǷϷȿǷ1risiq-1ǵĻܾǩ㣺
wi=(si)-1 mod q(wisiģqĳ)
U1i=(H(m,T)wi) mod q
U2i=(rwi) mod q
V=((()U1i(yi)U2i) mod p) mod q
V=rôûUiõĶϢmĸǩ{ri,si}֤.
3.2ȺǩĲ
ǩĲȺǩ{rsT}s=s1+s2++sn mod q.
3.3֤Ⱥǩ
ڽյϢmȺǩ{rsT}󣬽ȼ㦤T=T-T(Tǽӵǩʱ)涨ֵܾǩ֤.ǩߵĹԿyi=xi mod p㣺

֤̣ȿǷ1rsq-1ǵĻܾǩ㣺
w=s-1 mod q(wsģqĳ)
U1=(nH(m,T)w) mod q
U2=(rw) mod q
V=((U1yU2) mod p) mod q
V=rôǩ֤.
V=r֤

3.4ȫԷ
ϵȺǩǻDSA.İȫDSAİȫ.ף8жйDSAİȫԽ˲.ṩDSAʵֵȺǩ˼·ǵİȫDSAͬҪܿ.
ȺǩÿûǩͬһļȻиǩϳȺǩûչ.κηǷûαװĳϷûǩļΪûдû˽Կ.⣬ף3δǩز.ķмʱ־Եֿ๥.ʹ߻ԭеһǩ{r,s,T}ԽTʱ䣬޷ĵsеH(m,T)Թɹ.
4ǩt,nĹ֤
֤˵ǩ֤ϵͳУ֤ϵͳİȫƿ.һɿΣȫϵͳʹ.Ϊˣɲö֤֤ǩԷɢΣһϵͳȫ.
1989꣬Soete˻ıε(t,n)ǩ֤5ݣHarnһֻ޸˵ELGamelǩ(t,n)ǩ֤.˻DSA㷨(t,n)֤.
4.1
pһģ(2511<p<2512).w=(p-1)/2һ(2510<w<2511qw-1һ(2159<q<2160).xϵͳԿ(0<x<q).yi=xi mod pûUiΪϢmiǩĹԿiGF(p)wԪ.жʽf(z)=x+a1z++at-1zt-1mod q(ai(i=1,2,,t-1)(0,q)ѡȡ).giGF(p)еwԪGF(w)еqԪmiΪҪǩϢHǵϣ.ki(0<ki<w).ai(i=1,2,,t-1)ܣpwqgi(i=1,2,).ǩߵ˽ԿxԿyi.ski뱣ܣkiڲͬǩҪ仯.
4.2ӰӵĲ
ǻShamir1ܹԼDSA㷨ҪLagrengeֵ.
AǩߣxǩԿAΪ֤߲ܵӰ.Aѡһt-1׵Ķʽf(z)=x+a1z++at-1zt-1 mod qÿ֤Vi(i=1,2,n)ӰΪxi=f(zi) mod w(ziViĹϢ).t(zi,xi)ôxʽȷ

4.3ǩĲ
AǩϢmi(0mip-1)ôAҵigxi=xi mod pǰѶyi=xi mod pyi=gxi mod p.Aѡһki(0<ki<w)㣺
ri=kii mod p
si=(k-1i(H(mi,T)+xri))mod w
ԣsi,ri,gi,i,T}miǩ.Tʱ־Եֿǩز.
4.4ǩ֤
Ϣmiǩ si,ri,gi,i,T,ȼ㦤T=T-T(Tǽӵǩʱ)涨ֵܾǩ֤.n֤Vi(i=1,2,,n)еtԽ֤(t).ף6֪t֤߿ǩߵĹԿyi=xi mod p.ż飺
H(mi,T)i=rsii(yrii)-1 mod p(1)
ʽômiǩ֤.
֤ʽ(1)
rsii(yrii)-1mod p=((kii mod p)si(xi mod p)-ri) mod p
=((kisi-xri)imod p) mod p
=((kisi-xri)mod wi mod p) mod p
=H(mi,T)i mod p
4.5ȫԷ
(t,n)ǩ֤İȫҲDSAİȫ.ǩ(t,n)֤ɢȫΣϵͳİȫ.ף6Ҳδǩز迼ǣķмʱ־Եֿ๥.ʹ߻ԭеһǩsi,ri,gi,i,TԽTʱ䣬޷ĵsiеH(mi,T)йɹ.
5Զ֤
ChangLiaoף7һELGamelǩĿ֤.÷֤ǩܽϣ֤ȫµ˼.ף9ָChang-LiaoĲ֮ϣһĸĽһHarnǩԶ֤.
һֻDSAǩԶ֤.
5.1ûע
ûUiϵͳύIDiϵͳûṩϣH;жּ㹦ܵܿ.xϵͳ˽Կ.y=x mod pϵͳԿ.
ϵͳûUiǩPWi=(ri,si)ri=(ki mod p) mod q(kiһ0<ki<q,kiϵͳ棬kiûĲͬͬ.)
si=(k-1i(H(IDi)+xri))mod q
PWi㣺
V=(H(IDi)s-1i)mod qy(ris-1i) mod q mod pmod q=r
5.2ûϵͳ
ûϵͳʱܿ
A=timod p
B=ti+siH(A,T) mod q
ti(1,q)Tʱӡ£Ȼ֤Ci=(H(IDi),ri,A,B,T)͸ϵͳ֤.
5.3ϵͳ֤
ϵͳյCiT=T-T涨ֵ(TǽӵCiʱ)ϵͳô洢ĶӦki㣺
L=(k-1i) mod q(Lkiģqĳ)

A=(H(IDi)yri)-H(A,T)L mod p
A=Aô֤ɹ.֤
A=(H(IDi)yri)-H(A,T)Lmod p
=(ti+siH(A,T))mod q(H(IDi)xri)-H(A,T)L mod p
=(ti+siH(A,T)) mod q(-sikiH(A,T)L)mod qmod p
=ti mod q mod p=ti mod p
A=rtii mod q
A=ri(H(IDi)yri)-H(A,T) mod q
ô洢ͷͱ˷Ǵ洢ͷ.
5.4ȫԷ
ף9ָChang-LiaoΪ洢ûκݣֻܿǼǵķֹֹͶʧʹãӶϵͳҪ洢.ֵǼǵķͨĿעķȣȫԲ.ڱУȡ˴洢ͷϵͳ洢ϵͳΪÿûkiûĿעֹ򽫶Ӧkiɾ.洢kiͨ洢ûǲͬ.ʹkiй©Ҳй©ri=(ki mod p)mod q޷õsi޷CiϵͳԴ洢kiһĴ洢ȫ.ڱмʹhashִ洢kiԿԷֹף7ָα.nûıͨsi=(k-1i(H(IDi)+xri))mod qϵͳԿxΪkiĲͬҲЧ.ӹԿyԿxԼAtiȼɢѶ.
6
DSS/DSAΪȺǩǩ(t,n)֤ԼԶ֤Ϊǩ֤ϵͳ˽һ.Ȼǩڿ֤ϵͳȻŵ㣬Ҳһľ.ΪߵĸƽϣҪһо.⣬ף9ף6е(t,n)ǩ֤˼룬(t,n)֤.ͬҲñлDSA(t,n)ǩ֤ƳɻDSA(t,n)֤.ĳЩ£Ҫһ˹ͬһȻ˶ϵͳ.ҲеȺǩ˼·һɷ.ȤĶ߿Լ̽.
߼飺̷Ů19726ʿоҪоΪѧ簲ȫϢ.ģУ193911ϺӹϵϯѧңʿʦҪоΪͨ硢ֵ֧Эͬȫ.нܣУ19406ʿʦҪоΪͨҵATMýͨŵ.
ߵλϺͨѧӹϵϺ200030
ο
1Agnew G B, Mullin R C, Vanstone S A. Improved digital signature scheme based on discrete exponentiation. Electro Lett, 1990,26(14):10241025
2Schnopr C P. Efficient identification and signature for smart cards. In: Advances in Cryptology-CRYPTO '89,Santa Barbara, 1985.239252
3Lein H.New digital signature scheme based on discrete logarithm.Electron Lett,1994,30(5):396398
4Wu T C,Chou S L, Wu T S. Two ID-based multisignature protocols for sequential and broadcasting architectures. Computer Communications, 1996,19:851856
5DE Soete M, Quisquater J J, Vedder K. A signature with shared verification scheme. In:Advances in Cryptology-CRYPTO'89,santa Barbara:Springer-Verlag,253262
6Harn L.Digital signature with (t,n) shared verification based on discrete logarithms. Electron Lett,1993,29(24):20942095
7Chang C C, Liao W Y. A remote password authentication scheme based upon ELGamal's signature scheme. Computers & Security,1994,13(2):137144
8The digital signature standard. Comm ACM, 1992, 35(7):3640
9Ф.HarnǩԶ֤ͨ.ͨѧ,1996,17(1):114119
(Qi Ming,Xiao Guozhen.A remote authentication scheme based on Harn digital signature scheme.Communication Journal(in Chinese),1996,17(1):114119)
ԭյڣ1997-10-21
޸ĸյڣ1998-08-10
