（计算机软件与理论专业论文）秘密共享及其在门限代理签名中的应用研究.pdf

捅要 随着现代通信技术和计算机技术的飞速发展，尤其是互联网的迅猛发展，各种网络 服务已经渗透到了人们生活的各个领域，一方面给人类生活带来巨大的便利和好处，另 一方面也带来了前所未有的威胁。密码学技术在保障信息安全方面起到了至关重要的作 用。 在现代密码学中，对称密码体制、公钥密码体制、数字签名等都起到了保障信息安 全的作用。但是这些算法中，密钥的安全性决定着系统的安全性，一旦密钥泄漏，整个 系统就可能会崩溃，所有被该密钥控制的文件都能被破解，攻击者还可以利用此密钥签 署文件，给密钥所有者带来严重的后果。因此，如何更好的保护和管理密钥，减小密钥 泄漏的可能性具有十分重要的意义。自从1 9 7 9 年s h a m i r 和b l a k l e y 分别提出了秘密共 享方案，这种技术就得到了迅速的发展和广泛的应用。 随着信息安全内涵的不断延伸，信息安全已经不只是物理上安全或者在通信的双方 之间的秘密信息传递，而扩展到了消息的认证性等方面。而且，认证已经成为信息安全 的一个重要方面。数字签名是认证过程所采用的主要手段之一，它作为一种保障信息安 全的技术，能够保证信息的完整性、不可伪造性、不可否认性。数字签名技术和秘密共 享技术结合就形成了门限数字签名技术。门限代理签名体制，因其具有门限和代理两种 特性成为近年来密码学的一个热点问题。 本文首先介绍了秘密共享以及它的产生背景、意义和发展现状，接着阐述了密码学 相关的一些基础知识，然后对秘密共享方案和门限代理签名方案做了一些尝试和探索。 具体工作和所取得的主要研究成果如下： 1 研究了一些经典的秘密共享方案，分析了这些方案在实际生活中应用的不足之 处。并重点分析了h e d a w s o n 的多步骤秘密共享方案，在此基础上，提出了一个安全的 可验证的多秘密共享方案。在该方案中，每个参与者的子秘密由参与者自己选取，所以 不存在秘密分发者的欺骗；并且每个参与者能够验证其他合作者的欺骗；每个参与者选 取的子秘密可以复用；并且组秘密可以以任意顺序重构；此方案还能够抵抗合谋攻击。 2 。本文在大量分析门限代理签名前人工作的基础上，总结了已有门限代理签名方案 中存在的安全性问题。提出了一个安全的门限代理签名方案。该方案中每个参与者的公 、私钥以及群公钥由参与者共同协商，无须可信中心参与；提出的新方案能抵抗合谋攻 击，任意t 个人合作仍然无法知道其他代理人的秘密参数，也就无法伪造其他代理签名 人签名。 关键词：秘密共享；多秘密共享；门限代理签名；无可信中心；合谋攻击 a b s l 卧c t w i t hr a p i dd e v e l o p m e n to ft h em o d e r nc o m m u n i c a ti o n st e c h n o l o g ya n dc o m p u t e r t e c h n o l o g y ，e s p e c i a ll y t h ed e v e l o p m e n to ft h ei n t e r n e t ， m o r ea n dm o r e a p p l i c a t i o n se x c h a n g ei n f o r m a t i o nt h r o u g hi n t e r n e t i n t e r n e tb r i n g sm u c hm o r e c o n v e n ie n c et ou sa n di tb r i n g st o om u c ht h r e a ta tt h es a m eti m e c r y p t o g r a p h y p l a y sa ni m p o r t a n tr o l ei np r o t e c ti n gi n f o r m a ti o ns e c u r i t y s y m m e t r i cc r y p t o s y s t e m ，p u b li c k e yc r y p t o s y s t e m ，d i g i t a ls i g n a t u r e o f m o d e r nc r y p t o g r a p h yg u a r a n t e et h ei n f o r m a t i o ns a f e t y b u ti nt h e s ea l g o r i t h m s ， t h es e c u r i t yo fs e c r e tk e yd e c i d e st h es e c u r i t yo ft h es y s t e m ，t h ee x p o s u r eo f s e c r e tk e yw o u l dl e tt h ew h o l es y s t e mc o l l a p s ea n dl e a dt ot h ee n c r y p t e df i l e s d e c r y p t e da n dm a l i c i o u s l ys i g ni l l e g a lf i l e sw i t h t h ek e yb yh a c k e r sw h i c h r e s u l t si ns e r i o u sc o n s e q u e n c e s s oh o wt op r o t e c ta n dm a n a g et h ek e yb e t t e r a n dh o wt or e d u c et h ep r o b a b ili t yo fe x p o s u r eo fs e c r e tk e yh a v ea ni m p o r t a n t s i g n i f i c a n c e s i n c e1 9 7 9 ，s h a m i ra n db l a k l e yr e s p e c t i v e l yp r e s e n tt h et h e o r y o fs e c r e ts h a r i n ga n dt h r e s h o l ds c h e m e ，w h i c hp r o m o t e st h ed e v e l o p m e n ta n d p r a c t i c a la p p l i c a t i o no ft h i st h e o r y t h em e a n i n go fi n f o r m a ti o ns e c u r i t yise n l a r g e d i tm e a n sn o to n l yt h e p h y s i c a l s e c u r i t y o rc o m m u n i c a t e si np r i v a c y ，b u ta ls ot h em e s s a g e s a u t h e n t i c a t i o na n ds oo n a m o n gt h e m ，t h ea u t h e n t i c a t i o ni st h ei m p o r t a n ta s p e c t t h ed i g i t a ls i g n a t u r ei st h ep r i m a r ym e t h o dt op r o v i d et h ea u t h e n t i c a t i o n d i g i t a ls i g n a t u r ea sa ni n f o r m a ti o ns a f e t yt e c h n o l o g yp l a y sa ni m p o r t a n tr o l e i np r o t e c t i n gt h ei n t e g r i t yo ft h ed a t a ，u n d e n i a b i l i t ya n dn o n r e p u d i a t i o no f i n f o r m a t i o n c o m b i n i n gt h ed i g i t a ls i g n a t u r ew i t ht h es e c r e ts h a r i n gt e c h n o l o g y l e a d st ot h eb i r t ho ft h et h r e s h o l ds i g n a t u r et e c h n o l o g y t h r e s h o l dp r o x y s i g n a t u r e ，w h i c ha r et w ok i n d so fp a r t i c u l a rd i g i t a ls i g n a t u r e s ，b e c a u s eo ft h e i r p e c u l i a rt h r e s h o l dc h a r a c t e r i s t i ca n dp r o x yc h a r a c t e r i s t i c ，h a v eb e c o m eo n eo f t h em a j o rs u b j e c t si nt h ec r y p t o g r a p h yf i e l d f i r s t l y ，t h i sd i s s e r t a t i o np r e s e n t st h ec o n c e p to fs e c r e ts h a r i n ga n di t s b a c k g r o u n da n db r o a d c a s t t h e ni td is c u s s e ss o m ek n o w l e d g et h a tr e f e r st ot h e c r y p t o g r a p h y a n dw ee x p l o r ea n dr e s e a r c ht h es e c r e ts h a r i n gs c h e m ea n dt h r e s h o l d p r o x ysig n a t u r es c h e m e m a i nc o n t r i b u t i o n so ft h i sp a p e ra sf o l l o w s ： 1 i td i s c u s s e ss o m et y p i c a ls c h e m e so nt h et h r e s h o l ds e c r e t ss h a r i n gs c h e m e ， a n da n a l y s e st h es h o r t c o m i n g so ft h e s es c h e m ei na p p l i c a t i o n s a n df o c a ll y a n a l y s e st h et h r e s h o l dm u l t i s e c r e ts h a r i n gs c h e m eo fh e - d a w s o n b a s e do nt h e m ， w ep r o p o s e das e c u r et h r e s h o l dm u l t i s e c r e ts h a r i n gs c h e m e i nt h i ss c h e m e ，e a c h p a r t i c i p a n t ss e c r e ts h a d o ww a ss e l e c t e db yt h ep a r t i c i p a n th i m s e l f ，s ot h e u dc h e a t i n gi sn o te x i s t e d a n de v e r yp a r t i c i p a n tc a nd e t e c tt h ec h e a t i n gb y a n yo t h e rp a r tici p a n ts e a c hp a r tici p a n tc a ns h a r em a n ys e c r e tsw it ho t h e r p a r t i c i p a n t sb yh o l d i n go n l yo n er e u s a b l es h a d o w a n dt h eg r o u ps e c r e tc a l lb e r e c o n s t r u c t e di nf r e eo r d e r f u r t h e r m o r e t h en e ws c h e m ec a nw it h s t a n dt h e c o n s p i r a c ya t t a c k 2 b a s e do nt h et h r e s h o l dp r o x ys i g n a t u r es c h e m e o ff o r e f a t h e r s w o r k s ， t h ep a p e rg e n e r a l i z e dt h es e c u r i t y p r o b l e m si ne x i s t i n gs c h e m e s as e c u r e t h r e s h o l dp r o x ys i g n a t u r es c h e m ei sp r o p o s e d i nt h es c h e m ee a c hp a r t i c i p a n t s p u b li ck e ya n dp r i v a t ek e ya n dt h eg r o u pp u b li ck e ya r en e g o ti a t e da m o n ga ll p a r t i c i p a n t sw i t hn ot r u s t e dp a r t yr e q u i r e d t h ep r o p o s e ds c h e m ec a nw i t h s t a n d t h ec o n s p i r a c ya t t a c k ，a r b i t r a r i l ys i g n e r so fts t i l lc a n tk n o wt h es e c u r e k e y so fo t h e rm e m b e r si nt h ep r o x yg r o u p ，s ot h e yc a n ti m p e r s o n a t es o m eo t h e r p r o x ys i g n e r st og e n e r a t eav a l i dt h r e s h o l dp r o x ys i g n a t u r e a tl a s t ，w es u m m a r i z eo u rd is s e r t a ti o na n de x p e c tt h ef u t u r eo fs e c r e t s h a r i n gs c h e m ea n di t sa p p l i c a t i o ni nt h r e s h o l dp r o x ys i g n a t u r e k e y w o r d s ：s e c r e ts h a r i n g ：m u l t i s e c r e ts h a r i n g ；t h r e s h o l dp r o x ys i g n a t u r e ： w i t h o u tat r u s t e dp a r t y ：c o n s p i r a c ya t t a c k 秘密共享及其在门限代理签名中的应用研究 学位论文独创性声明 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果。论文中除特 别加以标注和致谢的地方外，不包含他人和其他机构已经撰写或发表过的研究成果，其 他同志的研究成果对本人的启示和所提供的帮助，均已在论文中做了明确的声明并表示 谢意。 学位论文作者签名：丝丝丝 学位论文版权的使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校有 权保留并向国家有关部门或机构送交复印件或磁盘，允许论文被查阅和借阅。本文授权 辽宁师范大学，可以将学位论文的全部或部分内容编入有关数据库并进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质 论文的内容相一致。 保密的学位论文在解密后使用本授权书。 学位论文作者签名：二垒边、超指导教师签名： 期：伽尹如仃日 3 6 秘密共享及其在门限代理签名中的应用研究 1 绪论 计算机技术的迅猛发展促进了网络技术的发展，越来越多的信息由过去的人工和书 信传递转变为通过网络发布和传输。大到一个国家的政治、军事、外交等重要领域，小 到人们的日常生活，都离不开因特网。人们可以利用因特网进行远程教育、网络购物、 电子支付、发送e - m a i l 等。但是因特网是一个开放的网络，它在带给人们便利的同时 也带来了各种信息安全问题和安全隐患，如黑客攻击等。因而保障信息的安全性已经成 为十分现实和紧迫的问题，信息安全无疑也成为现代社会信息科学领域的一项重要技 术。密码学技术作为信息安全中的关键技术受到了极大的关注，目前已经证明它是保护 网络信息安全的一种行之有效的方法。 密码学是一门古老而又年轻的科学，其历史可以追溯到几千年前，古代人类创造的 象形文字就是一种原始的密写方式 1 ，如今密码学也已经从单纯的军事应用目的渗透 到了社会需要的各个领域。可以说，它是结合数学、计算机科学和信息科学等多门学科 为一身的交叉学科。密码学技术主要保障信息的保密性、认证性、可用性、可控性和不 可否认性。 1 限密码学的产生背景和研究意义 密码技术能够保障信息安全很大程度依赖于密钥的安全性。 在对称密钥密码体制中，拥有秘密密钥就能够对用此秘密密钥加密的所有文件进行 解密等操作。非法用户在窃取信息的同时还可能会对信息进行篡改，给秘密密钥所有者 带来严重的后果。 在公钥密码体制中，拥有私钥就能够对秘密信息进行解密或者签名，这就意味着私 钥拥有者具有所有的权力。一旦丢失或者出错，不但合法用户无法提取信息，而且非法 用户可能会窃取信息。 可见，密钥的安全性是信息系统安全的关键。门限密码体制很好的解决了这一问题。 它主要是研究把一个实体执行或者发起的密码操作，分散到多个实体组成的一个群体来 执行的问题。 1 1 1 秘密共享体制的产生和研究意义 秘密共享是门限密码体制的基础。它能够把秘密进行分割，并将秘密分发给多个成 员，每个成员都持有这样的一个秘密份额，也叫做子密钥或者影子，只有多于特定数量 的秘密份额合一起才能够重新构造这个秘密，而少于特定数量的秘密份额合一起也得不 到关于秘密的任何信息。这样，当少于特定数量的成员的秘密份额泄漏时，也不会对整 个系统的安全性造成威胁，减小了秘密泄漏的可能性。可见，秘密共享能够把责任分散， 在密钥的安全性、完整性以及合法使用中都起着非常关键的作用，进一步提高了系统的 安全性和健壮性。 秘密共享及其在门限代理签名中的应用研究 1 9 7 9 年，s h a m i r 2 0 和b l a k l e y 2 首先分别基于拉格朗日多项式和射影几何定理 提出了( t ，n ) 门限秘密共享方案。在他们的方案中，秘密分发者首先将秘密分成n 个不 同的部分，每部分都叫做子秘密，然后将子秘密通过安全信道分发给n 个参与者，其中 至少t 个参与者合作就能重构秘密，而任t - 1 个或更少个成员不能够获得任何秘密信息。 可见，( t ，n ) 门限秘密共享方案一方面将子密钥分给n 个成员，泄露少于t 个子密钥就 不会危及密钥，少于t 个成员合谋也不能得到密钥；另一方面如果密钥遭到破坏，只要 有t 个子密钥保留下来，就可以恢复密钥。因此使用秘密共享可以有效的解决密钥的遗 失、出错和攻击，同时降低了破译密钥成功的概率。 1 1 2 门限代理签名的产生和研究意义 传统意义上的签名如在外交活动中签署文件、在商业上签订合同和协议、在日常生 活中签字或印章，这些手写签名或印章曾一度起到了认证、核实和生效的重大作用。但 是随着计算机和网络通信技术的发展，这些容易被伪造、被篡改的签名已经不能满足需 求。数字签名这种用于保证信息完整性、不可否认性和不可伪造性的技术得到了广泛的 应用。 数字签名的概念首先由d i f f i e 和h e l l m a n 于1 9 7 6 年提出的。数字签名根据其不同 的应用可分为盲签名、多重签名、门限签名以及代理签名等。门限签名主要应用于将签 名权力通过门限的方式分配给群组的各成员的场合中。代理签名主要应用于将签名权力 委托给其他人，使其代表自己签名的场合中。但是，人们将签名权力委托给代理人时， 通常存在代理人是否可靠、是否会滥用代理签名权，以及代理人的代理密钥是否保存妥 当、是否会被其他人窃取并进行恶意签名等问题。为了解决这些问题，将门限签名引入 代理签名体制中，形成了门限代理签名。 门限代理签名体制，兼有门限和代理两种特性。可以满足这样的功能：一个原始签 名人所指派的代理签名人不止是一个，而可以是由很多个代理签名人所组成的一个代理 群，只有在群中特定数量的人合作下才能够产生一个合法的代理签名，而少于这个特定 数量的人合作也不能产生合法签名。 1 2 门限密码体制的国内外研究现状 1 2 1 门限秘密共享体制的国内外研究现状 自1 9 7 9 年以来，许多学者对门限秘密共享进行了深入的研究，提出了多种方案。 然而，在秘密共享方案中 2 - 2 0 有如下的不足： ( 1 ) 在一次秘密共享过程只能共享一个秘密 1 1 。 ( 2 ) 一旦秘密被重构，需要通过安全信道重新发布新的子秘密给每个成员 1 6 。 ( 3 ) 一个恶意的秘密分发者可能提供假的子秘密，这样成员就不能重构真正的秘密 8 。 ( 4 ) 一个恶意的参与者可能会提供假的子秘密给其他成员，这样这个恶意参与者就成为 2 秘密共享及其在门限代理签名中的应用研究 能够唯一重构秘密的人 2 3 。 为了解决第一个问题，提出了一些( t ，n ) 门限多秘密共享方案 7 ，1 0 ，1 1 。为了解决 第二个问题，j a k s o n 1 6 更进一步把秘密共享方案定义成两种类型：一次方案和多次方 案。两者的不同在于多次方案中的子秘密可以复用，而一次方案中的子秘密不能复用。 我们知道，重新发布子秘密既耗费时间又耗费资源。 为了解决第三个问题，c h o r 8 提出了一个可验证的秘密共享方案来检测秘密分发 者的欺骗。在c h o r 的方案中，每个参与者能够验证分发者分给他她的子秘密，这就要 求参与者必须诚实。可见，在c h o r 的方案中第四个问题仍然存在。很多年后，s t a d l e r 2 1 提出了一个方案同时解决了问题三和问题四，s t a d l e r 的方案既防止分发者 9 欺骗 又可验证任何成员 3 ，4 ，1 7 ，2 2 ，2 3 的欺骗。但是，这些可验证的秘密共享方案都是只能 在一次秘密共享过程中共享一个秘密。 1 9 9 4 年，h e - d a w s o n 2 4 提出了一个基于单向函数的多步骤秘密共享方案。他们使 用公开移动技术通过连续的单向函数来分步以特定顺序获得秘密。不久，h a m 2 5 在 1 9 9 5 年提出了可验证的多秘密共享方案。但是在他们的方案中，为了验证密钥是否有效， 每个参与者需要检测计算n ! ( ( n t ) ! t ! ) 等式。在1 9 9 7 年，c h e n 6 提出了另 外的可验证多秘密共享方案来改进h a m 的方案，但是这个方案的计算量仍然很大。2 0 0 5 年p a n g 2 6 等提出了一种新的门限多秘密共享方案，实现了一次共享过程共享多个秘 密。但是该方案的效率仍有待提高。 1 2 2 门限代理签名的国内外研究现状 门限代理签名是一个很重要的数字签名，近年来人们对门限代理签名进行了广泛的 研究。 目前，已经有许多门限代理签名方案 2 7 - 3 5 被提出。但这些方案都存在以下问题： ( 1 ) 合谋攻击等问题。文献 2 7 - 3 3 的方案中存在合谋攻击，即在不知道任何有效的门限 代理签名的情况下，恶意代理成员人数大于或等于门限值时，他们能合谋重新构造代 理群的秘密多项式函数，得到代理群的秘密参数，从而可以伪造其他代理成员的代理 签名。s u n 3 1 引入了代理人的个人密钥和代理群组的身份，实现了签名的不可否认性 和不可伪造性，未能实现可追查性。在h s u 等人提出的门限代理签名方案 3 2 中，产 生代理签名时需要代理签名人的私钥，因此恶意代理签名人因为没有其他代理签名人的 私钥不能伪造其他代理签名人的代理签名。但仍然存在着恶意代理签名人的人数大于或 等于门限值时，他们能合谋重新构造代理群的秘密多项式函数，从而得到代理群的秘密 参数的不安全因素。另外，在h s u 等人的方案中，原始签名人能根据代理签名辨认出 代理签名人的身份，这对原始签名人是非常有用的，因为原始签名人能对代理签名人的 代理签名进行监督，防止代理签名人滥用他们的代理签名权。但是，在有些实际情况下， 尽管代理签名人忠实地行使着原始签名人委托给自己的代理签名权力，代理签名人仍然 秘密共享及其在门限代理签名中的应用研究 不愿意原始签名人能根据代理签名确定代理签名人的身份。例如，电子选举、电子支付 世 守0 ( 2 ) 在文献 2 7 3 3 的方案中，一旦原始签名人将签名权委托给代理签名人，那么代理签 名人就具有对这个签名权的永久代理，这对原始签名人是很不利的。原始签名人希望代 理签名人在某一段时间内具有代理签名权，当这段有效期过后，就收回代理签名权。 ( 3 ) 到目前为止所提出的门限代理签名方案几乎都是需要可信中心的，王斌 3 6 等提出 了无可信中心的门限签名方案。然而其安全性被证明并不可行 3 7 。由可信中心来负责 参与者的密钥协商，会增加系统的实现代价和复杂度。而且在很多特定的应用环境下， 一个可被所有小组成员信任的可信中心是不存在的。 1 3 本文研究的主要内容及组织结构 1 3 1 研究内容 本文对门限秘密共享方案进行了深入研究，通过研究分析，总结前人的成果与不足， 提出了一个安全的多秘密共享方案，该方案是一个完备的可验证的门限多秘密共享方 案。 另外，研究了门限秘密共享体制在代理签名中的应用，提出了一个无可信中心的安 全的门限代理签名方案，验证了该方案的可行性、安全性。 论文的主要工作如下： ( 1 ) 深入研究了门限秘密共享理论和一些经典的秘密共享方案，分析了这些方案在实际 生活中应用的不足之处。并重点分析了h e d a w s o n 的多秘密共享方案，在此基础上，提 出了一个安全的可验证的多秘密共享方案。在该方案中，每个参与者的子秘密由参与者 自己选取，所以不存在秘密分发者的欺骗；并且每个参与者能够验证其他合作者的欺骗； 每个参与者选取的子秘密可以复用；并且组秘密可以以任意顺序重构；此方案还能够抵 抗合谋攻击。 ( 2 ) 本文在大量分析门限代理签名前人工作的基础上，总结了已有门限代理签名方案中 存在的安全性问题。提出了一个安全的门限代理签名方案。该方案中每个参与者的公、 私钥以及群公钥由参与者共同协商，无须可信中心参与；提出的新方案能抵抗合谋攻击， 任意t 个人合作仍然无法知道其他代理人的秘密参数，也就无法伪造其他代理签名人签 名。 1 3 2 组织结构 本论文的组织结构如下： 第一章绪论。阐述了门限密码学产生的背景和意义、研究的主要内容以及国内外的发 展现状。 第二章预备知识。介绍了本文方案所需要的预备知识。包括公钥密码体制、数字签名 4 秘密共享及其在门限代理签名中的应用研究 体制和相关的数论知识。 第三章门限秘密共享体制研究。概述了门限秘密共享，探讨了一些门限秘密共享的典 型方案。包括秘密共享方案( s s ) 、可验证秘密共享方案( v s s ) 。 第四章门限多秘密共享方案研究。对门限多秘密共享方案进行了深入研究，提出了一 个安全的多秘密共享方案，该方案是一个完备的可验证的门限多秘密共享方案。 第五章门限代理签名体制研究。回顾了门限代理签名方案的研究历史，提出了一个无 可信中心的安全的门限代理签名方案，验证了该方案的可行性、安全性。 第六章总结与展望。在总结全文工作的前提下，我们又对本研究领域提出了一些今后 研究的方向。 5 秘密共享及其在门限代理签名中的应用研究 2 预备知识 2 1 密码学基础 密码学( c r y p t o l o g y ) 是数学的一个分支，主要是研究通信安全保密的学科。它包括 密码分析学和密码编码学。密码分析学( c r y p t a n a l y s i s ) 是研究、分析、破译密码的科 学和技术；密码编码学( c r y p t o g r a p h y ) 是对信息进行编码实现信息保密的科学和技术。 加解密体制是密码学研究的核心问题，它的主要目的是解决如何在不安全的信道上 安全通信的问题。其中需要加密的信息( m e s s a g e ) 称为明文( p l a i nt e x t ) ，明文变换成 密文的过程称为加密( e n c r y p t i o n ) ，对明文进行加密时所采用的编码规则称为加密算法 ( e n c r y p t i o na l g o r i t h m ) ，利用加密算法加密后的信息称为密文( c i p h e rt e x t ) ，对密 文进行解密时所采用的编码规则称为解密算法( d e c r y p t i o na l g o r i t h m ) ，密文恢复出原 明文的过程称为解密( d e c r y p t i o n ) ，控制加密算法和解密算法的一对密钥( k e y ) 分别叫 做加密密钥( e n c r y p t i o nk e y ) 和解密密钥( d e c r y p t i o nk e y ) 。 下面给出加解密体制的形式化描述。 一个加解密体制是一个五元组( p ，c ，k ，e ，d ) ，需要满足以下条件： ( 1 ) p 是可能的明文构成的有限集合； ( 2 ) c 是可能的密文构成的有限集合； ( 3 ) k 是密钥空间，是可能的密钥构成的有限集合； ( 4 ) 对于每一个k k ，有一个加密算法e k e 和相应的解密算法巩d ，每一个 e k ：p - - - c 和以：cjp 都是一个函数，它满足对于每一个明文x p ，都有d k ( e k ( x ) ) = x 。 由性质( 4 ) 可以看出：对任意一个明文x 使用哝进行加密，加密后的密文使用相应 的以来解密，都能够恢复原来的明文。图2 1 提供了一个用加密进行通信的简单模型： 臣习 a 1 i c e - - l ，立 图2 1 6 秘密共享及其在门限代理签名中的应用研究 根据密钥的特点，密码体制分为对称加密体制和非对称加密体制两种。对称密码体 制( s y m m e t r i cc r y p t o s y s t e m ) 又称为单密钥( o n e - k e y ) 体制、私人密钥体制( p r i v a t e k e y c r y p t o s y s t e m ) 、传统( c l a s s i c a lc r y p t o s y s t e m ) 密码体制。之所以称之为单密钥体制， 是因为利用这种加密体制进行加解密的时候，发送方和接收方使用的是相同的密钥。其 加密过程如下图2 2 ： 截取入侵者篡改 加密密钥k 密文y = 最( x ) 安全信道 解密算法d 加密密钥k 明文x a 1 i c eb o b 图2 2 可见，在对称密钥密码体制中，在一个双方的通信中，密钥必须在两端都保密。那 么在一个大型网络中，需要管理许多密钥对。而且对于经常通信的双方a 和b ，良好的 密码使用习惯是规定密钥应该不时更换，也许每次会话都要更换。 非对称密码体制( a s y m m e t r i cc r y p t o s y s t e m ) 又称双密钥( t w o - k e y ) 体制、公开密钥 体制( p u b l i c - k e yc r y p t o s y s t e m ) ，公开密钥体制在加密和解密时使用两个不同的密钥， 发送方使用加密密钥对数据进行加密，接收方只能使用对应的解密密钥才能解密。其加 密过程如下图2 3 ： a 1 i c e 图2 3 7 b o b 秘密共享及其在门限代理签名中的应用研究 非对称密码技术的最大的优点就在于它对密钥管理方法的改进，它采用不同的加密 密钥和解密密钥，这样就不需要维护安全信道来传输，使密钥在处理和发送上更为方便 和安全。非对称密码技术的出现 3 8 3 9 ，使得现代密码学有了划时代的发展。很多密 码技术都是基于这种体制，如数字签名等。 2 i i 公钥密码算法 为了解决信息公开传送和密钥管理问题，美国著名密码学家d i f f i e 和h e l l m a n 4 0 于1 9 7 6 年发表了具有划时代意义的一篇论文：密码学的新方向，提出了公钥密码学 的概念。公钥密码的提出可以说是整个密码学发展史上的一次伟大革命。公钥密码体制 克服了对称密码体制的缺点，为近代密码学指明了方向。它的出现也是现代密码学诞生 的标志。 公钥密码体制的一个重要思路就是：可以找到一个密码体制，使得由给定的e k 来求 解以在计算上是不可行的。如果满足这一条件，加密算法e k 是一个公钥，可以公开发布。 显然，在公钥体制中，a ( 或者其他任何人) 可以利用公钥加密算法吼发出一条加密的消 息给b ，而不需要先在安全信道上为共享密钥通信。b 将是唯一能够利用解密算法反对 密文进行解密的人。 公钥加密算法使用两个独立的密钥：加密密钥又称公开密钥，简称公钥；解密密钥 又称私人密钥，简称私钥。就加密而言，发送者a 以接收者b 的公钥作为加密密钥，接 收者b 以自己的私钥作为解密密钥，则可以实现发给接收者的消息只能由接收者b 解密。 值得注意的一个事实就是公钥密码体制无法提供无条件安全性。这是因为一个敌手 至少可以通过观察密文y ，利用公钥加密算法e k 来加密每一条可能的明文，直到他发现 唯一的x 使得y = 哝( x ) 为止。可见，这个x 就是y 的解密。所以，我们仅研究公钥体制 的计算安全性。 公钥密码体制不象对称密码体制那样基于简单的替换和置换，而是基于单向 ( o n e - w a y ) 函数。单向函数是一个可逆函数厂：a - - ) b ，它需满足： ( 1 ) 对每一个x ea ，计算f ( x ) 是容易的； ( 2 ) 对于几乎所有的x ea ，由f ( x ) 求解x 在计算上是不可行的。 d i f f i e 和h e l l m a n 随后引入了陷门单向函数( t r a p d o o ro n e - w a yf u n c t i o n ) 的概念， 它对于研究公钥密码体制是很有帮助的。陷门单向函数：疋：彳。- - ) 召：，z ez ，z 是陷门信 息集。它需满足： ( 1 ) 对于每一个z ez ，在给定z 的条件下容易找到一对算法e 和d ，使得对所有x a ， 计算z 及其逆：l ( x ) = e ( x ) ，见( 正( x ) ) = x 是容易的。而且当给定z 后容易找到一种算 法f ( 消息集鉴别函数) ，对所有x a ，容易检查是否x e 么，彳，是可用明文集； ( 2 ) 对于几乎所有z z ，当只给定e 和e 的时候，对几乎所有的x 4 ，不能从y = e ( 工) r 秘密共享及其在门限代理签名中的应用研究 计算出x ； ( 3 ) 对于每一个z ，集合彳必须是保密系统中明文集合的一个方便集，即容易实现明 文到它的映射。 陷门单向函数是构造公钥密码体制的途径。 2 1 2 数字签名 传统意义上的签名如在外交活动中签署文件、在商业上签订合同和协议、在日常生 活中签字或印章，这些手写签名或印章曾一度起到了认证、核实和生效的重大作用。但 是随着计算机和网络通信技术的发展，这些容易被伪造、被篡改的签名已经不能满足需 求。数字签名这种用于保证信息完整性、不可否认性和不可伪造性的技术得到了广泛的 应用。 在公钥密码体制中，发送者a 以自己的私钥作为加密的密钥而以自己的公钥作为解 密密钥，则可实现对发送者a 身份的认证。显然，公钥体制适合于数字签名的构造。因 为，一个签名实体用自己独有的私钥对不同消息进行签名，从而产生不同信息签名，应 该不能被其他实体所伪造，而且也可以被不同的接收实体所验证，而这正是数字签名的 基本要求。 一个签名体制是一个五元组( p ，a ，k ，s ，v ) ，满足以下条件： ( 1 ) p 是可能的消息构成的有限集合； ( 2 ) a 是可能的签名构成的有限集合； ( 3 ) 密钥空间k 是可能的密钥构成的有限集合； ( 4 ) 对于每一个七k ，有一个签名算法s i g k s 和相应的验证算法v e t k v ，对每一个消 息x e 尸和每一个签名y a ，每一个s i g k ：pja 和v e t t ：p x aj t r u e ，f a l s e 都是满足下 列条件的函数： v e t k 加尼 = s i g k 器 由消息工尸和签名y a 构成的数据对( x ，y ) 为消息签名。 一个安全有效的数字签名方案应具有以下特性： ( 1 ) 签名的可信性。任何人都可以验证签名的有效性； ( 2 ) 签名的不可伪造性。除了合法的签名者之外，任何人都不能产生合法签名； ( 3 ) 签名的不可抵赖性。任何签名者在产生签名后，无法抵赖自己对消息的签名； ( 4 ) 签名的不可复制性。对一个消息的签名不能通过复制变为对其他消息的签名； ( 5 ) 签名消息的不可改变性。经过签名的消息不能被篡改，一旦签名的消息被篡改，则 任何人都可以发现消息和签名之间的不一致性，签名不再成立。 9 秘密共享及其在门限代理签名中的应用研究 2 2 数学基础 许多密码学体制依赖于解决某个数论问题的困难性，所谓困难性是指对给定的问 题，在合理有限的资源范围内找不到一个可行的算法来解决这个问题，即在计算上的不 可行性。下面给出在公钥密码体制中经常用到的一些困难性问题。 2 2 1 大整数因子分解问题 在数论中，整数的唯一分解定理指出：任何一个大于1 的整数，若不考虑因子的次 序，则它能唯一的表示成若干素数的乘积。 大整数分解问题 4 1 ：给定整数n ，找出它的素因子。即对n 进行因子分解 n = a 日p 2 2 p k 略，其中p ，是互不相同的素数，e i 是正整数。 如果已知两个数p 和q ，求其乘积n = p q 是非常容易的。但是如果已知的是乘积n ， 那么分解这个乘积解出两个因子p 和q 就不那么简单了，尤其当这个乘积是一个大素数 ( 如超过1 0 2 4 位) 的时候，而这也是现代密码学中公钥密码体制提出的数论理论基础。 现在广泛应用的基于大数分解问题提出的r s a 4 2 密码体制，仍被认为是安全性最好的 体制之一。 分解一个大整数很费时。尽管如此，在这方面现在还是有一些进展。二次筛选法 ( q s ) 4 3 ，4 4 对于低于1 1 0 位的十进制数来说，是目前已知的最快算法。目前最好的大 数分解算法是数域筛选法( n f s ) ，对于大于1 1 0 位左右的十进制数来说，一般的数域筛 选是目前己知的最快的大数分解算法。另外还有一些算法如连分数算法 4 5 、椭圆曲线 法( e c m ) i4 6 j 对较大数是没有用的。 2 2 2 离散对数问题 离散对数问题 4 7 是公钥密码体制中的一个基本问题，它的安全性决定了很多密码 方案和算法的安全性，如e l g a m a l 4 8 、d s a l - 4 9 7 等算法。 离散对数 5 0 ：设g 是一个有限循环群且g g 是g 的一个生成元。元素a ( a eg ) 的离散对数指的是有唯一的整数x ，( 0 x i g i ) ，使得a = g 。成立。记作x = l o g 。口。如 果g 不是生成元，a 基于g 的离散对数若存在指的是最小的正整数x ，使得口= g 。成立。 离散对数具有以下性质： 设g = ( g 是阶为n 的有限群，口，b ，c eg ( 1 ) l o g g ( a b ) 量l o g g ( a ) + l o g 窖( b ) m o d n ( 2 ) l o g 。( 口。) 堇x l o g 。( a ) m o d n ，v x ez ( 3 ) 如果h 是g 的另一个生成元，则1 0 9 9 ( 口) 三l o g ( a ) 1 0 9 ( g ) 】m o d n ，当a = h 时有 l o g 。( 办) 兰 1 0 9 ( g ) 】叫m o d n 离散对数问题( d l p ) r 5 1 j ：对于一个有限循环群g = 1 0 2 4 ) 来说，只要2 ”一l 至少有一个“大”的素因子，t 。上离散对数 问题目前被认为是计算上不可行的。 2 3 双变量单向函数 在相关的文献 7 5 2 中都使用到了