（计算机系统结构专业论文）加权门限秘密共享研究.pdf

加权门限秘密共享研究 摘要 秘密共享是现代密码学的个重要分支，是保障信息安全和数据保密的重 要手段之一。利用秘密共享保存和管理秘密信息，一方面可以防止权力过于集 中而被滥用，分散了责任：另一方面可以保证数据的安全性和完整性。秘密共 享的研究不仅具有重要的理论意义，而且具有广泛的应用前景。 本文介绍了秘密共享的研究背景、现状及相关数学工具，探讨了门限秘密 共享研究的若干研究方向，分析了几种经典的门限秘密共享方案，重点研究了 加权门限秘密共享。针对已有的加权门限秘密共享方案存在的问题，提出了一 个新的加权门限秘密共享方案。该方案具有以下特点： ( 1 ) 允许参与者具有不同的权重值，只有当参与者集合的权重之和大于或 等于门限值时，才能恢复秘密；反之，则得不到关于秘密的任何信息。 ( 2 ) 方案中引入m i g n o t t e 列，并对其进行扩展，无论参与者的权重大小 如何，只需要保存一个秘密份额。从而减少了秘密信息的传输量，同时有助于 提高秘密信息的安全性。 ( 3 ) 无需设定额外的辅助数据( 如间接秘密等) ，从而简化了方案的结构， 降低了计算复杂度。 最后，本文介绍了大素数的生成和检测方法等算法及实现，利用v c + + 6 0 实现了该方案的原型系统，并分析了系统的各个模块及其功能。实验结果表明： 本文所提出的方案是正确和可行的，具备良好的安全性和应用性。 关键词：秘密共享；权值；m i g n o t t e 列；中国剩余定理 w e i g h t e dt h r e s h o l ds e c r e ts h a r i n gr e s e a r c h a b s t r a c t s e c r e ts h a r i n gi sa l li m p o r t a n tb r a n c ho fm o d e mc r y p t o g r a p h y i ti sas i g n i f i c a n tw a y t op r o t e c t i n gi n f o r m a t i o ns e c u r i t ya n dd a t ae n c r y p t i o n s e c r e ts h a r i n gi su s e df o rs a v i n g s e c r e ti n f o r m a t i o n i tp r e v e n t se x c e s s i v ec o n c e n t r a t i o no fp o w e rb e i n ga b u s e da n dc a n d i s p e r s er e s p o n s i b i l i t y o nt h eo t h e rh a n d ，i tg u a r a n t e e st h es e c u r i t ya n di n t e g r i t yo f d a t a t h e r e f o r e ，r e s e a r c ho fs e c r e ts h a r i n gh a si m p o r t a n tt h e o r e t i c a ls i g n i f i c a n c e a n db r o a d a p p l i c a t i o np r o s p e c t s f i r s t l y , t h eb a c k g r o u n d s ，s t a t u sa n dr e l a t e dm a t h e m a t i c a lt o o l so fs e c r e ts h a r i n g a l e p r e s e n t e di nt h ed i s s e r t a t i o n i ns u c c e s s i o n ，s e v e r a lc u r r e n tr e s e a r c ha r e a so ft h r e s h o l d s e c r e ts h a r i n ga r ed i s c u s s e d s o m ec l a s s i c a lt h r e s h o l ds e c r e ts h a r i n gs c h e m e s a r ea n a l y z e d t h e n ，t h ef e a t u r e so fc u r r e n tw e i g h t e dt h r e s h o l ds e c r e ts h a r i n ga r er e s e a r c h e d an e w w e i g h t e dt h r e s h o l ds e c r e ts h a r i n gs c h e m ei sp r o p o s e d t h e r e a r es o m ef e a t u r e si nt h e s c h e m ea sf o l l o w s ： ( 1 ) t h ep a r t i c i p a n t sa l ea l l o w e dt oo w l ld i f f e r e n tw e i g h tv a l u e o n l yw h e nt h et o t a l w e i g h tv a l u eo ft h ep a r t i c i p a n t si sg r e a t e r o re q u a lt ot h et h r e s h o l dv a l u e ，t h ep a r t i c i p a n t s c o u l dr e c o v e rt h es e c r e t ，o t h e r w i s et h e yc a l ld on o t h i n g ( 2 ) m i g n o t t es e q u e n c ei si n t r o d u c e da n d e x t e n d e di nt h es c h e m e n om a t t e rh o wm u c h t h ew e i g h tv a l u eo ft h ep a r t i c i p a n ti s ，e a c hp a r t i c i p a n to n l yn e e d st os a v eo n es h a r e i tc a n g r e a t l yr e d u c et h et r a n s m i s s i o nq u a n t i t yo fc o n f i d e n t i a li n f o r m a t i o n a n de n h a n c et h e s e c u r i t yo fi n f o r m a t i o n ( 3 ) n oa d d i t i o n a ld a t ai sr e q u i r e di nt h es c h e m e ，w h i c hs i m p l i f i e st h es t r u c t u r ea n d r e d u c e st h ec o m p u t a t i o n a ld i f f i c u l t y f i n a l l y , t h eg e n e r a t i o na n dr e a l i z a t i o na l g o r i t h m so ft h el a r g ep r i m en u m b e r a l e i n t r o d u c e di nt h ed i s s e r t a t i o n ap r o t o t y p es y s t e mi si m p l e m e n t e db yu s i n gv c + + 6 0 t h e f u n c t i o n so fc o m p o n e n to ft h ep r o t o t y p es y s t e ma r ed e t a i l e da n a l y z e d t h ee x p e r i m e n t a l r e s u i t ss h o wt h a tt h es c h e m ei sc o r r e c ta n df e a s i b l ea n dh a sg o o ds e c u r i t ya n da p p l i c a b i l i t y k e y w o r d s ：s e c r e ts h a r i n g ；w e i g h t e dt h r e s h o l d ；m i g n o t t e s e q u e n c e ；c h i n e s e r e m a i n d e rt h e o r e m 图表清单 4 1 本文方案与其他方案性能指标比较2 8 5 1 系统主界面3 1 5 2 产生秘密份额流程3 2 5 3 恢复秘密流程3 2 5 4 系统参数设置界面3 3 5 5 分配参与者权重值3 3 5 6 生成的m i g n o t e 列3 5 5 7 生成扩展的m ig n o t t e 列3 6 5 8 生成秘密份额3 7 5 9 参与者恢复秘密界面3 8 5 1 0 成功恢复出共享秘密3 8 5 1 l 参与者权重之和小于门限值提示3 9 5 1 2 恢复秘密失败界面3 9表图图图图图图图图图图图图 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得金g 里工些太堂 或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签字：杨寻 签字日期：2 v 。碑形。日 学位论文版权使用授权书 本学位论文作者完全了解合肥工业大学有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被 查阅或借阅。本人授权 金目巴王些太堂可以将学位论文的全部或部分论文内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇 编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：刁c 为亨 签字同期皂j ，年彳月知r 学位论文作者毕业后去向： 工作单位： 通汛地址： 翮签名：j l0 蝴导师签名：1 乞q 匆吨 签字日期：纠，年f 夥日 电话： 邮编： 致谢 在近三年的硕士研究生学习期间，得到了我的导师侯整风教授的悉心指导，无论 是课程学习、论文选题，还是收集资料、论文成稿，侯老师都给了我大量的帮助。无 论是从一开始的选题，还是最后完成毕业论文，侯老师都提出了具体的要求以及需要 改进的地方。侯老师广博的知识，严谨的学风，诲人不倦的精神都深深影响了我，激 励我不畏困难，永远向前。 在这里，也要感谢合肥工业大学计算机与信息学院的各位老师，他们在课堂上的 教诲为本文的研究提供了理论基础。 同时感谢网络和信息安全实验室的同学。在几年的学习生活中，我们互相帮助， 相处愉快。在本论文的研究和撰写中，他们给我提出了很多宝贵的意见，对我论文的 完成有很大的启发和帮助。 最后再次感谢所有关心、帮助过我的人。 作者：杨宇 2 0 1 0 年4 月 第一章绪论 1 1 研究背景和意义 当今社会，人类已经进入信息化时代，信息交换已经成为推动社会进步的 主要因素之一，利用网络进行信息的交换和资源的共享成为社会的一个重要特 征。人们利用计算机网络交换信息的同时，如何保证某些信息的秘密性、完整 性和不可否认性成为信息安全领域的一个重要的研究方向。信息安全领域提供 的许多实用技术( 如数据加密、数字签名和身份验证技术等) 都是建立在密钥 安全的基础上，一旦密钥被窃取、丢失或者破坏，将会导致秘密信息泄露或无 法恢复秘密信息。因此，密钥的管理是信息安全技术的关键。 秘密共享是现代密码学领域中的一个重要分支，它为解决密钥的管理提供 了一个新的思路；为密钥在保存、传输和利用过程中的安全性提供了有力的保 障。秘密共享将秘密信息分成若干个秘密份额( 也称子秘密、碎片) ，分别将其 发送给对应的参与者，只有参与者的人数大于或等于某值时才能恢复出秘密； 小于该值时得不到秘密的任何信息，这就是秘密共享的基本思想。首先，秘密 共享可以将个人权力分散防止集权；其次，增加了秘密信息的稳定性，即当有 参与者的秘密份额缺失时，其他参与者也能利用各自的秘密份额恢复秘密。因 此，秘密共享作为管理秘密信息的重要工具，在密钥管理、数据安全、电子商 务等领域有着非常广泛的作用，其不仅有重要的理论意义，而且具有广泛的应 用前景。 加权秘密共享允许不同的参与者拥有不同的权重值，只有当参与者的权重 之和大于或等于门限值时才能恢复秘密；小于门限值时得不到关于秘密的任何 信息。 加权秘密共享有着广阔的应用前景，适用于参与者地位不同的场合( 比如公 司中，普通职员和经理的地位不同；军队中，首长和士兵的地位不同) ，日益引 起人们的关注，成为秘密共享领域中一个重要的研究方向。 1 2 秘密共享国内外研究现状 1 9 7 9 年，s h a m i r 和b l a r k e y 比1 分别独立提出了秘密共享的概念，即把一 个秘密分成若干部分( 秘密份额) 分发给玎个参与者，只有，或f 个以上的参与 者合作才能恢复出秘密。s h a m i r 设计了一个基于l a g r a n g e 插值多项式的秘密 共享方案，将秘密作为多项式的常数，多项式在各个点的值作为方案的秘密份 额。根据l a g r a n g e 插值定理，任意f 个点和在这，个点上多项式的值可以重构 该多项式，常数项即为共享秘密；而小于f 个点无法确定多项式各个项的系数， 所以无法得到共享秘密。b l a r k e y 利用向量空间的性质提出了一个( t ，疗) 门限秘 密共享方案，通过解，个方程组成的方程组得到共享秘密，而小于，个方程组成 的方程组显然无法得到正确结果，从而无法得到秘密信息。 随后，许多学者对秘密共享进行了深入地研究，提出了多种的秘密共享方 案。1 9 8 3 年，a s m u t h 和b l o o m 1 将模运算用于秘密共享，提出了基于中国剩余 定理的门限秘密共享理论；k a r n i n h 3 等提出了矩阵乘法方案；i t o 口33 等提出的实 现一般访问结构的秘密共享方案。在上述研究的基础上，c h o r 哺3 等提出的方案 可以有效地验证秘密分发者的身份，但是在验证期间需要分发者和参与者相互 传递大量信息，而且参与者之间无法验证对方的身份，从而导致其可应用性较 差。针对c h o r 方案的不足，f e l d m a n 1 基于离散对数的难解性提出了一个非交 互可验证秘密共享方案。t o m p a 和w o l l 订1 提出的秘密共享方案只能判断在恢复 秘密的过程中是否由参与者有欺诈行为，但是无法定位到具体参与者。文献 8 详细分析了现有防欺诈秘密共享方案的优缺点。1 9 9 3 年b l u n d o 阳1 等提出了一个 多秘密共享方案，其特点是利用信息论来实现多秘密的共享；1 9 9 8 年，h w a n g r ，c h a n gc 训也提出了一个多秘密共享方案，其特点是利用利用公开信息来实 现秘密信息交换，从而减少了秘密信息的传递，增强了安全性，但是在秘密恢 复的过程中，多个秘密无法同时恢复。随后，c h i e nhy 和j a njk 【l 妇提出了 一个多秘密共享方案，在恢复秘密的过程中，能够同时恢复所有秘密，克服 1 0 的缺陷。y a n g 等在2 0 0 4 年提出了一个新的方案n 刳，其特点是将多个秘密设置 成多项式的系数，增加了信息的利用率。2 0 0 5 年p a n g n 3 3 等基于s h a m i r 方案提 出了一个新的门限多秘密共享方案，实现了一次共享多个秘密。更多的关于多 秘密共享研究成果可参考文献 4 0 。 1 9 9 9 年，pm o r i l l 0 和cp a d r 6 h 4 1 等提出了一个加权秘密共享方案，但是 该方案是基于分解结构的，并且只适用于每个最小授权子集的元素个数只能为 2 ，这使得应用范围过于狭窄。z h a n g n 钉等提出了一种参与者有特殊权限的门限 秘密共享方案，使得加权秘密共享应用到一般的场合，但是因为要求解同余多 项式方程组，故计算量比较大。随后，i f t e n e n d 引等提出了一种基于中国剩余 定理的参与者有权重的秘密共享方案，该方案虽然可以减小特权参与者的秘密 份额规模的大小，但是对系统参数的要求比较苛刻，系统过于复杂。 1 3 课题研究的主要内容，解决的问题 1 3 1 研究内容 本文介绍了门限秘密共享的思想以及基于这种思想的几种典型的秘密共享 方案，重点研究了参与者有权重的门限秘密共享方案。通过分析总结前人研究 经验和成果，提出了一种基于扩展m ig n o t t e 列n ”的加权门限秘密共享方案。 论文的主要工作如下： ( 1 ) 深入研究了门限秘密共享思想及几种典型方案； ( 2 ) 提出了一个加权门限秘密共享方案，该方案在保证可靠性和正确性的 2 同时明显地减少了特权参与者秘密份额的数量； ( 3 ) 实现了一个加权门限秘密共享方案的原型系统，验证了方案的正确性 和可行性。 1 3 2 解决的关键问题 ( 1 ) 如何减少特权参与者秘密份额 传统的有特殊权限参与者的门限秘密共享方案只是简单给予特殊权限参与 者更多的秘密份额。通过分析和研究前人已有的成果，本文提出了自己的方案。 本方案通过构造一个扩展的m i g n o t t e 列可以使特权参与者和普通参与者的秘 密份额数量大小相同，有效的降低了方案中的秘密信息，减小了秘密信息在传 输中泄露的可能性。 ( 2 ) 大数运算问题 由于本文提出的方案是建立在大数运算的基础上，但是当前普通p c 机无法 实现大数运算。因此，本文采用m i r a c l 库来实现大数的运算，它良好地支持了 多种涉及到秘密共享方面的大数运算。 ( 3 ) 验证方案的正确性和可行性 对本方案进行理论证明和分析，通过实验来验证方案的正确性和可行性。 1 4 本文的组织结构 本文组织结构如下： 第一章：绪论。主要讨论了本文的研究背景，意义和目的以及国内外的研 究现状和已有成果。 第二章：秘密共享研究。介绍了关于秘密共享的一些概念和研究工具，介 绍了门限秘密共享思想，并详细描述和分析了几个经典的门限秘密 共享方案。 第三章：加权门限秘密共享研究。对现有几个加权门限秘密共享方案进行 具体分析和讨论，指出其方案存在的优点和不足。 第四章：基于扩展m i g n o t t e 列的加权门限秘密共享方案。针对上一章提出 的加权门限秘密共享方案的不足之处，提出了一种新的加权门限秘 密共享方案，并对方案进行了分析，解决了原有方案的不足之处。 第五章：原型系统的实现。介绍了如何实现大数的运算，重点分析了该原 型系统各个组成部分，对方案的可行性和正确性进行了验证。 第六章：总结与展望。 第二章秘密共享研究 秘密共享是信息安全和信息保密的重要工具，有着广泛的使用价值。本章 将介绍秘密共享思想及相关概念，探讨几种经典的门限秘密共享方案，分析这 几种方案的特点。 2 1 秘密共享基本思想 数据加密系统的安全性主要取决于密钥的安全性，一旦密钥泄露将会导致 系统丧失其安全性。因此，如何保存和管理密钥成为系统必须解决的问题。一 种方法是将密钥交给单个成员保管，但是当密钥遗失或损坏时，会造成秘密被 非法窃取或无法恢复。另一种方法是将密钥复制多份交给多个成员保管，这样 做虽然降低了密钥丢失的可能性，但是随着密钥副本的增多，密钥泄漏的可能 性也增大了。 秘密共享为上述难题提供了有效的解决途径，它将秘密分解为多秘密份额 ( 或称碎片，影子) 并将这些秘密份额分发给不同的参与者保管。只有特定的 参与者集合可以通过他们的秘密份额来恢复出秘密，其他任意集合都无法得到 关于秘密的任何信息。 门限秘密共享可以将秘密分散，提高了系统的安全性和鲁棒性，因为当攻 击者试图获得秘密时，必须获得达到门限值个数的秘密份额。当一部分秘密份 额遭到破坏或丢失时，只要其他参与者有大于或等于门限值的秘密份额就可以 恢复秘密。 2 2 秘密共享研究的基本工具和相关概念 2 2 1 数论知识 在秘密共享研究中，大部分理论都是建立在数论基础上的，下面将介绍一 些在秘密共享研究中涉及到的数论知识。 ( 1 ) 有限域 在密码学领域中，密码学上的运算都是基于有限域上的算术运算，因此有 限域有着广泛的应用。 若集合f 是有限集合，则称其对应域为有限域或者伽罗瓦域；反之称为无 限域。有限域是由一个有限集合f 和两种运算( 分别为加法( 用”+ ”表示) 和乘 法( 用表示) ) 共同组成。 一个有限域( f ，+ ，十) 满足下列条件： 集合f 中全体元素构成加法交换群，记为( f ，+ ) ，单位元用0 表示。元 素日的逆元表示为一a ； 集合，中全体非零元素构成乘法交换群，记为( e 难) ，单位元用1 表示。 4 元素a 的逆元表示为a ； 集合f 中的元素满足分配律，即对于v a ，b ，c f ，有 ( 口+ 6 ) 嗥c = a 木c + 6 木c 。 在有限域( f ，+ ，书) 中，减法定义为：口一b = a + ( 一b ) ；除法定义为a b = a * b ， 其中b 一为b 的逆元。 有限域元素的个数称为有限域的阶。对于任意一个素数g ，只存在一个9 阶 的有限域，用c 或者g f ( q ) 表示。 ( 2 ) 整数有限域 若集合f 是整数集合，则在模p 下，集合f 和加法( 减法) ，乘法( 除法) 共同构成一个整数有限域，记为c 。 整数有限域加法：如果口，b 0 ，则a + b - - - r m o d p ，r ； 整数有限域乘法：如果口，b ，则a * b 言s m o d p ，s 。 ( 3 ) 多项式有限域 若集合。是多项式集合，并且。的元素是次数最高为m - 1 次的多项式 ( 多项式系数取自e ) ： ，2 a m l x ”- 1 + 一2 x m - 2 + + a l x + a o ，a j e ) 。 多项式有限域的加法：如果多项式a ，b l ，且 a = a m 1 z m 一1 + a m 一2 x 埘一2 + + q x + 口o ， b = b m 1 x 珊- 1 + 6 胛一2 x 所一2 + + 6 1 x + 6 b ， 则c = a + b2 一l x 肼q + c m 2 x 肌2 + + c l x + c o 。 其中q = 缉+ 包m o d p ，0 z m - 1 。 多项式有限域的乘法：如果多项式口，b l ，且 a = a m _ 1 2 c ”一1 + a m 一2 x ”一2 + + q x + a o ， b = b m q 戈胛- 1 + k 一2 x 卅一2 + + b , x + 6 0 ， 则d = 口幸b m o d f ( x ) = 叱一l x 肼1 + 厶。2 x 肼一2 + + 4 x + 成。 其中厂( x ) 为次数为m 的不可约多项式。 ( 4 ) 模及同余运算 若口，b 为整数，存在整数g 和，使得：口= q b + r ，其中0 ， f ，其中i 么i 为集合么中元素的个数。 在门限秘密共享中，秘密分发者把秘密s 分割为成多个子秘密( 秘密份额) ，再 把这些子秘密通过安全信道发送给各个参与者。在恢复秘密时，如果有，( f 表 示方案的门限值) 个或，个以上的参与者在场时，就可以恢复出秘密j ，反之， 则无法得到关于秘密s 的任何信息。 门限秘密共享方案有两个很重要的参数：门限值( t h r e s h o l dv a l u e ) ，和 参与者数目，z 。 个( f ，疗) 门限秘密共享方案基本步骤描述如下： ( 1 ) 秘密分发者将秘密s 分割为玎个子秘密( 秘密份额) ：记为墨，s ，s 。 ( 2 ) 秘密分发者将这些子秘密安全地发送给对应的参与者。 ( 3 ) 在恢复秘密时，只有当不小于f 个的参与者出示秘密份额时，才能得到 共享秘密；否则便无法得到。 7 例如，在一个公司里，公司把一份机密材料交给5 个职员共同管理。公司 设计了一个方案使得只有3 个以上的职员在场的时候才能恢复这份机密材料， 少于3 个职员无法得到材料的任何信息。这就是一个( 3 ，5 ) 门限秘密共享方案。 下面将介绍几种经典的门限秘密共享方案，这几种方案都是当前门限秘密共享 研究的基础。 2 3 1 基于l a g r a n g e 插值多项式方案 2 3 1 1l a g r a n g e 插值多项式简介 设函数向( x ) = a t l x 卜1 + q 一2 x 卜2 + + a i x + a o 在区间【口，b l - _ 有定义，在这个区间 上有刀个点：五，恐，薯，令 y t = 矗( 薯) ，l f ， 在g f ( q ) 下，线性方程组 + q + 口l + q 薯+ = m 屯+ a o2m ( 2 3 ) x t + a o 2 y t 该方程组的系数为范德蒙( v a n d e r m o n d e ) 矩阵： 么= 葺t - i ，誓，i ( 2 4 ) 对该范德蒙行列式有： d e t a = 兀( - x j ) ( 2 5 ) l j t 因为没有任何一个x t 一等于零，所以d e t a 0 。所以方程组有唯一解，即 通过f 各点( t ，m ) 可以得到唯一多项式h ( x ) 。 2 3 1 2s h a m i r 门限秘密共享方案 l a g r a n g e 插值多项式方案是由s h a m i r 首先提出的，他利用有限域中的多 项式来构造门限方案。具体描述如下： ( 1 ) 系统参数初始化：设，z 为方案中参与者的人数，p 是一个大素数，并且 要大于秘密值，方案门限值为，。要求所有的参数都在有限域舒( p ) 内。 秘密分发者d 从6 f ( p ) 中随机选取玎个不同的整数而，x 2 ，然后公布以 上所有值。 ( 2 ) 产生秘密份额：分发者d 随机生成一个上卜1 次的多项式( 如式2 6 所 示) ，其中该多项式的系数在g f ( p ) 上。 h ( x ) = 口f ，l x 卜1 + 口f 一2 x 卜2 + + q x + m o d p ( 2 6 ) 8 + + + 寸声 f 之 也 也 q q q + + + 彳声f q q q d j 而吃 2 2卜l 2 x x 彳声 分发者d 令a o = h ( o ) = j 为方案共享秘密，并且对该多项式保密。然后计算： s ，= h ( x j ) r o o d p ，= 1 ，2 ，力 ( 2 7 ) 最后d 将s ，通过秘密信道发送给对应的方案参与者。 ( 3 ) 恢复秘密：必须有，或者r 个以上的参与者才能完成。参与者基于 l a g r a n g e 插值法，利用式2 8 可以恢复出多项式。 恢复多项式如下： h ( x ) = o 兀乙鲁 ( 2 8 ) 一f j 则恢复的秘密为： s = a o = 办( o ) = “五) 兀o ，击 ( 2 9 ) ， 一 得到在有限域g f ( p ) 唯一解多项式h ( x ) 的同时也就得到了秘密j 。但是当只 有小于f 个秘密份额时，就无法确定多项式h ( x ) ，也就无法得到秘密s 。 可以证明，s h a m i r 的( f ，z ) 门限方案是一个完备的理想方案乜引。 例2 1 ： 设p = 1 3 7 ，构造( 3 ，5 ) 门限方案。选取多项式 h ( x ) = ( 3 x 2 + 5 x + 7 ) m o d l 3 7 ，其中系数3 和5 为随机选取，7 为秘密。5 个秘密份 额如下： s 1 = h ( 1 1 = 3 + 5 + 7 暑1 5 m o d l 3 7 s 2 = h ( 2 ) = 1 2 + 1 0 + 7 暑2 9 m o d l 3 7 邑= 办( 3 ) = 2 7 + 1 5 + 7 言4 9 m o d l 3 7 瓯= 办( 4 ) = 4 8 + 2 0 + 7 三7 5 m o d l 3 7 邑= 五( 5 ) = 7 5 + 2 5 + 7 暑1 0 7 m o d l 3 7 可以使用3 个秘密份额( 比如墨，岛，黾) 来恢复秘密，通过解下面线性方程组： 融豢 2 3 2 基于中国剩余定理的门限秘密共享方案 2 3 2 1 中国剩余定理简介 中国剩余定理是由我国古代数学家首先提出的，因为其最早记载于我国古 代数学名著孙子算经，故人们又称之为孙子定理。后来经过人们进一步发展 得到完善，这种算法传到国外就被称为中国剩余定理，并在密码学中有广泛的 用途。 定理2 1 设整数列，m 2 ，两两互素，记m = 玛鸭。另有有整数列 ，厶，l ，则同余方程组 9 在模m 同余的意义下有唯一解： x - m a 矿五+ 必 巧1 厶+ + m , , m ：1 i r r o d m 其中必= m l n ； f 1 t 奎l ( m o d m i ) ； 1 i ，z 。 证明参看文献 2 3 。 ( 2 1o ) ( 2 1 1 ) ( 2 12 ) 2 3 2 2a s m u t h - b l o o m 门限秘密共享方案 a s m u t h 和b l o o m 在1 9 8 0 年提出了一个基于中国剩余定理的门限秘密共享 方案1 。 ( 1 ) 系统参数初始化：设有一个( f ，门) 门限方案，选取一个大素数p ，使之大 于秘密的可能值s ，选取n 个整数坍。，聊：，使得： ，z l m 2 l l * 3 7 幸4 1 。秘 密分发者随机选取一个整数1 3 ，得到9 + 1 3 1 l = 1 5 2 。给每个参与者计算秘密份 额： 1 0 确肋 脾 删删 删 厶厶一厶 三 兰 誊 x x x 假设前三个人需要恢复秘密， 余方程组： 解得：x = 1 5 2 。 1 5 2 m o d l l = 9 即为共享秘密。 1 4 = 1 5 2 m o d 2 3 7 = 1 5 2 m o d 2 9 2 8 = 1 5 2 m o d 3 1 4 = 1 5 2 m o d 3 7 2 9 = 1 5 2 m o d 4 1 则他们提供各自的秘密份额1 4 ，7 ，2 8 解下列同 2 3 3 空间向量秘密共享方案 b l a r k e y 利用向量空间的性质提出了一个( f ，n ) 门限秘密共享方案，通过解t 个方程组成的方程组得到共享秘密，而小于f 个方程组成的方程组显然无法得 到正确结果，从而无法得到秘密信息。 2 4 门限秘密共享主要研究方向 以上是几个经典的门限秘密共享方案，它们都是利用数学上一些理论再结 合秘密共享思想完成的。但是这些早期的方案由于过于简单，或多或少的存在 一些缺陷，很难应用到实际系统中，所以现在的门限秘密共享方案着重对这几 个方案进行改进，使其符合人们应用的需求。目前主要的门限秘密共享研究都 是基于对这几个方案进行扩展来完成的。下面介绍当前门限秘密共享主要研究 的几个方向。 2 4 1 可验证门限秘密共享 传统的门限秘密共享方案是假定秘密的分发者和参与者都是诚实的，并且 没有攻击者进行破坏，但是在实际的应用中并不是这种情况。当秘密发送者不 诚实时，可能分发伪造的秘密份额，这样当参与者人数大于或等于门限值时无 法恢复出秘密：当参与者不诚实时，可能出示伪造的秘密份额，来阻止其他参 与者恢复秘密。可验证秘密共享( v e r i f i a b l es e c r e ts h a r i n g ，简称v s s ) 就是 为解决秘密分发者和参与者不诚实问题而设计的。c h o r ，m ic a li ， a w e r b u c h 和g o l d w a s s t e r 哺1 首先提出了可验证门限秘密共享思想。一个可验证门限秘密 共享方案应该包括：在秘密分发阶段，秘密分发者发送给参与者的秘密份额是 可验证的；在恢复秘密阶段，参与者给出的秘密份额也是可验证的。 通过在验证身份阶段是否需要交换信息，可以将可验证秘密共享方案分为 篡 暑 毫 一= x x x ，c，l 两种类型。参与者在验证身份的过程中需要计算和传递数据的方案被称为交互 式可验证秘密共享方案隋 2 7 3 ；利用公钥密码系统进行身份认证的被称为非交互 可验证秘密共享方案川“钊。h w a n g 和c h a n g 3 引入了公告牌的概念，使得在 以后的方案中，参与者可以公告牌上的信息来验证参与者的身份和参与者所给 出的秘密份额的正确性，减少了秘密信息传递的数量，减小了网络通信代价。 下面介绍一种典型的可验证门限秘密共享方案：f e l d m a n 的v s s 方案吲。 f e l d m a n 提出的方案对s h a m i r 的方案进行扩展并增加公开信：息，从而达到 对参与者秘密份额进行验证这个目的。 ( 1 ) 系统参数：设p 是一个大素数，其长度不小于5 1 2 比特，q 为p 一1 的大 素数因子，其长度不小于1 6 0 比特，g 是z ：中的一个g 阶元素，r 是门限值，甩 是方案中参与者的个数，s 是要共享的秘密，然后公开这些参数。 ( 2 ) 生成秘密份额：秘密分发者在z 中随机选取一个o 一1 ) 次多项式： 厂( x ) = s + a l x - t - a 2 x 2 + + q 一1 x 卜1m o d p ( 2 1 6 ) ( 3 ) 计算秘密份额s ，： 墨= f ( x _ f ) r o o d q ( 2 1 7 ) 将墨通过安全信道发送给各个参与者，并广播验证信息： 幺= g qm o d p 其中f = 1 ，2 ，t - 1 ( 2 1 8 ) ( 4 ) 验证秘密份额：各个参与者通过交换得到其他参与者的秘密份额后，通 过下式验证秘密份额的正确性： g 耳= 兀：( r o o d p ( 2 1 9 ) 如果2 1 9 式成立，则秘密份额正确；反之，秘密份额不正确。 ( 5 ) 秘密恢复：至少需要f 个参与者合作才能恢复秘密，每个参与者公布各 自的秘密份额丑，此时，各个参与者可以通过判断式2 1 9 是否成立来验证s 。的 正确性。如果f 个参与者的秘密份额全部通过验证，则可通过l a g r a n g e 插值法 来恢复出式2 16 ，即可得到秘密j 。 2 4 2 门限多秘密共享 在一般的门限秘密共享方案中，参与者共享一个秘密，并且参与者的秘密 份额只能使用一次。但是在某些应用中，参与者需要共享多个秘密。一种简单 的方法是对每个秘密构造一个秘密共享方案来实现多个秘密的共享。其缺陷是 每个参与者保管的秘密信息太多，方案的效率低下。 针对以上方案遇到的问题，1 9 9 3 年b l u n d o 等基于信息论提出了多秘密共 享理论呻1 。基于该理论，1 9 9 4 1 9 9 5 年有人将门限思想引入，提出了门限多秘 密共享方案心引乜引，1 9 9 5 年 a r n n 63 提出了一种新的门限多秘密共享方案，其特 点是运用了单向函数的数学性质，参与者只需保留一个秘密份额便能够同时恢 复多个秘密，同时允许这些秘密对应的门限值不相等。随后在h a r n 思想的基础 上，改进方案相继提出6 3 7 3 引。c h i e n 等提出了一个可验证多秘密共享方案n 1 1 ， 其特点是基于系统编码，并且克服了h a r n 的缺点。后来，c h a n 等提出可验证 多秘密门限共享方案心副，其特点是将多秘密共享和可验证秘密共享相结合，但 是在验证秘密份额阶段，参与者需要计算大量数据，效率不高。目前对门限多 秘密共享方案研究主要集中在效率上。 下面介绍一种通过扩展s h a m i r 方案的多秘密门限共享方案，该方案由 p a n g 3 1 等在2 0 0 5 年提出。 ( 1 ) 系统参数初始化：设有双变量单向函数f ( r ，s ) ，秘密分发者选取大素数 g ，并任意选取，2 个整数，s ：，s n ，参与者的秘密份额即为该船个整数，同时公 布方案参与者的身份信息，记为l g i 材，u n 。以上所有的参数都是有限域g f ( q ) 上 的元素。 ( 2 ) 产生秘密份额：假设需要共享m 个秘密，记为c 1 ，c 2 ，c 埘，则秘密份额 的产生的具体步骤为： 分发者首先随机选取任一整数，对所有的母，计算f ( r ，磊) 。 然后利用向量( o ，c 1 ) ，( 1 ，c 2 ) ，( m - 1 ，c m ) 以及( ，f ( r ，t ) ) ( 其中f _ 1 ，2 ，以) 构造 0 + m 一1 ) 次多项式： h ( x ) = a o + a l x + + 卅l x 斛俨1m o d q ( 2 2 0 ) 从集合 m ，q 一1 】一 i 扛1 ，2 ，以 中取出最小的( n + m - t ) 个整数 4 ，畋，丸伽，分别计算函数值办( 4 ) ( 其中f = 1 ，2 ，m + n - t ) 。 并且以认证的方式们拍5 1 公布( ，厅( 吐) ，h ( d 2 ) ，办( d r 一，) ) 。 ( 3 ) 秘密恢复：当需要重构这m 个秘密时，至少需要f 个参与者合作。不妨 设这f 个参与者为u l ，u ，l l t 。 首先每个参与者( ，= l ，2 ，) 通过计算得到函数厂驴，墨) 的值，继而可得到f 个向量( u if ( r ，q ) ) ，( 甜：，f ( r ，是) ) ，( 坼，f ( r ，墨) ) 。 然后从区间【m ，q l 卜 lf = 1 ，2 ，n ) 中选取最小的( n + m - t ) 个整数 d l ，吐，以一，并根据步骤( 2 ) 公布的信息厅( 吐) ，h ( d 2 ) 9e o ，办( 以一，) 得到( 玎+ m r ) 个 向量( z ，办( 以) ) 。此时，恢复秘密的参与者共得到t n + r t 个向量，按式2 2 1 就 可以将该+ m 一1 ) 次多项式重构如下： 办( x ) = ：”z 兀= 川軎等= a o + 口l 地+ a m + n _ l x m + n - i m o d q ( 2 21 ) “i n j 其中( 置，z ) 表示向量( z ，厅( z ) ) 。 分别将0 ，1 ，m 一1 带入式2 2 1 就可以得到m 个秘密c l ，g ，c 册。 2 4 3 动态门限秘密共享 通常在门限秘密共享中，门限值，和秘密份额是固定不变的，如果周期较 长，那么攻击者就有足够的时间去窃取足够多的秘密份额，从而可以恢复出共 享秘密。这种攻击被称为移动攻击( m o b il ea t t a c k ) 。 动态秘密共享是在保证共享秘密不变的情况下定期更新秘密份额和门限 值，从而使得攻击者以前所窃取的秘密份额就会失去作用。因此，动态门限秘 密共享方案可以提高系统安全性，有效地抵抗移动攻击。 目前动态门限秘密共享的研究重点集中在如何产生新的秘密份额。主要有 两种方法生成新的秘密份额，一种是更新的秘密份额由参与者生成，另一种更 新的秘密份额由秘密分发者生成。前者各个参与者交互的信息过多，但是不需 要秘密分发者参与；后者方法简便，但是需要秘密分发者参与。 2 4 4 加权门限秘密共享 在一般的门限秘密共享方案中，所有参与者的地位都是平等的。然而在某 些应用环境中，参与者之间存在着职位或者权力大小的区别。比如在一个部门 的不同