（计算机应用技术专业论文）防欺骗（tn）门限方案研究及应用.pdf

防欺骗( t ，n ) 门限方案研究及应用 摘要 秘密共享是密码学领域的一个重要磅究方向，( t ，n ) 门限方寨是实现秘密共 事的藿要途径。在( t ，n ) 门鼹方案豹研究中，参与者欺骗的闻题一意没有得到有 效的艇决，尤其是如何防范接质一个参与者欺骗或多人联合欺骟。同时，( t ，n ) 门限方案的应用也是目前重要研究方向之一。 本文分析帮探讨了多种秘密共享方案，对( t ，n ) 门限方案中的参与者欺骗闻 题送行了深入瓣研究，提出新的防欺骗影子交换协议和防多人联合欺骗门限方 案。针对霞蒋考试系统存在的内部安全漏洞，展开了防多人联合欺骗门鞭方案 在考试系统中豹应用研究。 本文的主要工作及成采如下： i 、介绍了一些经典的( t ，n ) t 7 限方案以及棚关的密码学知识和数学知识，分 析了( t ，n ) f 7 限方案中参与者欺骗的问题并给出相关的研究成果。 2 、在对参与者欺骗闽题进行深入研究的基础上，提出一静防欺骗影子交换 协议，将其应用于门限方案的影予交换阶段，成功的解决了最后个参与者欺 骗的闽题。 3 、提寰一种防多人联合欺骗( t ，n ) 门限方案，递过生成子秘密来构造子门限 方案，有效的解决了多人联合欺骗的闻鼷，使得( t ，n ) 门隈方案具有更广泛的应 用前景。 4 、将防多人联合欺骗( t ，n ) 门限方案与考试系统相结合，尝试解决泄题、提 | 狐考试等问题。 关键词：( t ，n ) 1 7 限方案；防欺骧；影子交换；子秘密 r e s e a r c ho nt h r e s h o l ds c h e m eo fc h e a t i n g p r e v e n t i o na n di t sa p p l i c a t i o n a b s t r a c t s e c r e ts h a r i n gi sa ni m p o r t a n tr e s e a r c hi nc r y p t o g r a p h y ，a n d ( t ，n ) t h r e s h o l d s c h e m ei sam a i nm e t h o dt or e a l i z es e c r e ts h a r i n g ：i nt h er e s e a r c ho f ( t ，n ) t h r e s h o l d s c h e m e ，t h ep r o b l e mo ft h ep a r t i c i p a n t sc h e a t i n gh a sn o tb e e ns o l v e dy e t ，e s p e c i a l l y h o wt op r e v e n tt h el a s tp a r t i c i p a n to rc o m b i n e dp a r t i c i p a n t sf r o mc h e a t i n g a tt h e s a m et i m e ，( t ，n ) t h r e s h o l ds c h e m e sa p p l i c a t i o ni sc o n c e r n e di nr e c e n ts t u d y s o m es e c r e ts h a r i n gs c h e m e sa r ed i s c u s s e da n da ni n d e p t hr e s e a r c ho nt h e p r o b l e mo ft h ep a r t i c i p a n t sc h e a t i n gi n ( t ，n ) t h r e s h o l ds c h e m ei s t a k e ni nt h e d i s s e r t a t i o n 。as h a d o w - e x c h a n g e dp r o t o c o lo fc h e a t i n gp r e v e n t i o na n da ( t ，n ) t h r e s h o l ds c h e m eo fc o m b i n e d p a r t i c i p a n t sc h e a t i n gp r e v e n t i o n i s p r o p o s e d a i m i n ga tt h es h o r t a g e so ft h ei n t e r n a ls e c u r i t yi nt e s ts y s t e m ，t h er e s e a r c ho nt h e a p p l i c a t i o no f ( t ，n ) t h r e s h o l ds c h e m eo fc o m b i n e dp a r t i c i p a n t sc h e a t i n gp r e v e n t i o n o r lt e s ts y s t e mi st a k e n t h em a i nw o r k sa n dc o n t r i b u t i o n so ft h ed i s s e r t a t i o na r es u m m a r i z e da s f o l l o w s ： f i r s t l y ，s o m ec l a s s i c a l ( t ，n ) t h r e s h o l ds c h e m e sw i t hr e l e v a n tc r y p t o g r a p h y k n o w l e d g ea n dm a t h e m a t i ck n o w l e d g ea r ei n t r o d u c e d ，t h e nt h ep r o b l e mo ft h e p a r t i c i p a n t sc h e a t i n gi sa n a l y z e da n dt h er e l e v a n tr e s e a r c hc o n t r i b u t i o n si sg i v e ni n t h ed i s s e r t a t i o n s e c o n d l y ，b a s eo nt h ei n d e p t hr e s e a r c ho nt h ep r o b l e mo ft h ep a r t i c i p a n t s c h e a t i n g ，as h a d o w e x c h a n g e dp r o t o c o lo fc h e a t i n gp r e v e n t i o ni sp r o p o s e di nt h e d i s s e r t a t i o n t h ep r o b l e mo ft h el a s tp a r t i c i p a n tc h e a t i n gi ss o l v e db ya p p l y i n gt h e p r o t o c o lt ot h es h a d o w e x c h a n g e ds t a g e t h i r d l y ，a ( t ，n ) t h r e s h o l d s c h e m eo fc o m b i n e d p a r t i c i p a n t sc h e a t i n g p r e v e n t i o ni sp r o p o s e di nt h ed i s s e r t a t i o n b yg e n e r a t i o n gs u b s e c r e tt oc o n s t r u c t t h r e s h o l ds u b s c h e m e ，t h ep r o b l e mo fc o m b i n e dp a r t i c i p a n t sc h e a t i n gi ss o l v e d e f f e c t i v e l y ，s o ( t ，n ) t h r e s h o l ds c h e m eg e t sw i d e rf u t u r ei na p p l i c a t i o n f i n a l l y ，( t ，n ) t h r e s h o l ds c h e m eo fc o m b i n e dp a r t i c i p a n t sc h e a t i n gp r e v e n t i o n a r ea p p l i e dt ot e s ts y s t e m 。t h ep r o b l e mi nt e s ts y s t e m ，f o re x a m p l et e s ti t e m r e v e a l e d ，t e s tt i m e 。a d v a n c e d ，a r ea t t e m p t e dt ob es o l v e di nt h ed i s s e r t a t i o n k e yw o r d s ：( t ，n ) t h r e s h o l ds c h e m ec h e a t i n gp r e v e n t i o ns h a d o w - e x c h a n g e d ； s u b s e c r e t 插图清单 闺3 1一般门限方案影子交换顺序1 9 图3 2防欺骗影子交换拚议基本步骤2 0 图4 。lt e 视始化阶段流程圈3 4 鼹4 2m 捆密阶段流程图3 5 圈4 3m 恢复阶段流稷潮3 6 强5 。l秘密共享者成员4 2 圈5 2考试系统基零流程4 3 图5 3英语试卷明文4 4 图5 - 41 6 避制英语试卷4 4 图5 5命越组基本参数设置4 5 图5 - 6降阶多i 蚕式组设鬣4 5 图5 7秘密共享者个人参数设鬣4 6 图5 8掰予秘密设置4 6 图5 - 9( ，厂( ) ) 序嬲文本4 7 图5 1 0聊。加密过程4 7 图5 1 l成员m 的晰，恢复遗程4 8 图5 1 2 成员u 的m 恢复过程4 9 阁5 。1 3 恢复的试卷明文4 9 表格清单 表1 1具有8 ，位公歼密钥的r s a 对予不同长度模数的加密速度3 表l 。2具裔1 6 0 位指数的e l g a m a l 对予不同长度模数的速度3 袭3 ，li p 地址列表2 6 表3 2t c 公开参数磺表2 6 表3 3参与者交换顺序列表2 7 表3 - 4a 公开参数列表2 7 褒4 。li p 地址列表3 8 表4 2共享者i d 列表3 9 表4 。3共事者个人密钥列表3 9 表4 4参与者最。列表。3 9 表4 5参与者毛列袭4 0 袭5 1一缀秘密菇享者的个人公钥表4 8 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究：f ：作及取得的研究成栗。攥我所 知，除了文中特荆加以标志和致谢的姥方外，论文中不包含其他入汪经发表或撰写过的研究成果， 也不包含为获褥盒筵些厶燮或其他教育机构的学位或诞书而使用过的材料。与我- - p ：作 的同志对本研究所傲的任何贡献均己在论文审作了明确的说明并表示谢意。 学位论文作者签字 呸镟 签字魄加“年歹月0 翻 学位论文版权使用授权书 本学位论文手# 者完全了解佥罄；l ：些鑫堂有关保露、使封l 学位论文的规定，有权保蟹并淘 国家有关部门域规构送交论文的复印件和磁盘，允许论文被鸯露或借阅。本人授权盒骐王她太 堂可以将学位论文的全部或部分论文蠹容编入脊关数据麾进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密焉适用本授权书) 学傍论文佧赣签名： 咚熊 签字日期： 五“年| f 爿勺霸 学位论文作者毕业籍去向： 一【作单织： 通讯地址： 导师签名： 签字雠硼年蚕月7 圜 电话 邮编 阢，；丹 ，filll 致谢 本文是在侯整风教授的精心指导下宪成的。侯老师严谨的治学态度、敏锐 的学术思想、不龋进取的科磺作风给我餐下了深刻的印象，使我终身获益。在 此，谨向侯老师豹辛勤培养与无私的关怀表示衷心的感落。 在课题研究和生活当中，王世东硕士生给予我非常大的支持和关心；谢树硕 士生为我的课题研究给出许多宝贵豹意见。在这里，特别向王世东硕士生和谢 柯硕士生表示真诚的谢意。 非常感谢研究生院郛计算机与信息学貌的备位领导和老师，怒他们绘我提 供了一个莛好的学习研究和生活环境。感谢魏家好硕士生，李乐硕圭生，余周 华硕士生，张娜硕士生，与纯们的交流与探讨，使我获益嚣浅。 真诚的感谢我的父母对我的关心和支持，熊们的关怀给予了我克服困难的 勇气和信心。 干挈者：攀健 2 0 0 6 年5 月 第一章绪论 l 1 密码学概述 密码学作为一穆探护信息的方法，有罄悠久的历史，它最早疲餍予军事、 外交稳情报等少数领域，霜来隧着科技的不蹶发展藤逐渐进入到人们的生活中。 在手工她时期，人们只是简单的通过纸和笔来对字符进行加密。工业革命兴起 展，密碣学遴入了机器时代以及电子时代，加密手段越来越复杂，加密和解密 的效率也越来越离。目前，密码学已成为结合物理、量子力学、电子学、语蠡 学等多个专业的综合科学。 计算枫密码学是研究计算橇信息匀鞋密、解密及冀变换的科学，楚一门数学 和计算机的交叉学辩，也是一门薪兴的学科。穗着计算枫网络在各个行业的寂 用、普及以及通讯技术的飞速发展，计算枫密码学得黯前所末蠢的熏视并迅速 发展起来，成为计算枫安全主要的研究方向之一。计算机密码学可分为经典密 码学( 传统密码学) 和公开密码学。 1 2 对称密钥算法 经典密码学中最主要的密钥算法是对称密钥算法( 传统密码算法) 。在对称 算法中，加密密钥和解密密钥霹以曩稳推算，其实在大多数豹对称算法中，加 密密钥和解密密钥都是相同的。对称算法可以分为蕊类：一次只黠明文中的单 个位或字节进季亍运算的算法称为序列算法；一次对明文的一组位进行运算的算 法称为分组算法。对称箨法的加密和嬲密可以表示为； e x ( m ) = c ( 1 - 1 ) 玟( c ) = m ( 1 - 2 ) 对称密钥算法中最常用的是d e s 算法，它是i b m 公司的w 。t u c h m a n 和 c 。m e y e r 】【2 1 予1 9 7 1 年至1 9 7 2 年，根据h o r s tf e i s t e l 3 1 在1 9 6 7 年提渤熬加密 算法理论设计出来豹。d e s 算法属于分组簿法，它以6 4 位为分组对数据遴行加 密，臻文的长度和密文鲍长度帮为6 4 位。d e s 算法中密锾的长度为5 6 位，蒋 热上8 位的奇偶验证码，一共也是6 4 位。 d e s 算法是通过一个初始置换，将明文分组分成各为3 2 位的左右两个部分， 然茬进行1 6 轮完全楣同的运算，这感运算被称为溺数f ，同时在运算过程中数 据要与密钥榻结合，最后左右嚣个部分经过个襁始嚣换的逆羲换，得到6 4 经的密文分组，这就是d e s 算法的基本过程。 d e s 算法运算速度怏，密钥也容易生成，不仅适合于软件实现，还适合予在 专用芯片上实现。它的弱点楚安全性能不够，因为其密钥长度只有5 6 位。为了 解决这个问题，可以采用三重d e s 或3 d e s 系统h 】，使用3 个不问的密钥进行三 次船密，可以提商密钥的强度。 1 3 公开密钥冀法 在对称密镅算法中，算法豹安全憔很大程度上取决予密钥的安全性，一健 密钥泄露出去，那就意睬着任何获得糍钥的人都可以进行搬密和解密。对称密 钥算法虽然解决了数据的保密传输，但是其致命的缺陷一过于依赖密钥的安全 性，决定了对称密钥算法难以解决密钥的分配帮管理蝤题。为了更好的勰决密 钥的安全性闽题，磅究人员稻做了大量的新的尝试。1 9 7 6 年，美国著名豹密 码学家w h i t f ie ldd i f f i e 秘m a r t i nh e l i m a n 5 】1 6 提出了公开密钥算法的概念， 并首次诞明了在发送端郛接收端无密钥传输的像密逶信是可能瓣，开创了公钥 寮码学的新纪元。 公开密钥算法也被称为菲对称算法。在这类算法中，用于加密的密钥不同 予解密的密镪，而置解密的密锈无法通过办嚣密豹密钥进行计算。在公开密锈葬 法中，用于加密的密钥被称为公开密钥( 公钥) ，可以公开：用予解密的密镧被 称为私人密镪( 私钥) ，私钥必须傈密。假设公开密钥为趸，解密密锈为是， 公开密钥算法的加密和解密可以表示为： e ，( m ) = c( 1 3 ) d ，( c ) ；m ( 1 4 ) 公开密钥算法还可以应溺予数字签名中。此时私钥用予加密，雨公钥用于鳃褰， 表示为： e 。，( 膨) = c( 卜5 ) 圾( c ) = m ( i 一6 ) 在现实世界中，公开密钥算法不可能完全取代对称密钥算法，原因为：公 开密锶算法在计算速度上魄鼹稼密钥算法慢，对称密钥算法一般眈公拜密锈算 法挟一于倍；公开密钥算法辩逸择明文攻击是脆弱酶，如果c = e x ( m ) ，当m 怒n 个可熊明文中的一个，邋过燕密掰有可能的m ，并分析e ，攻击者裁能确 定出m 。新以在实际成用中，公开密钥算法常常用来加密密钥，黼不是用来船 密消息。 l 。3 。lr s a 算法 r s a 算法建第一个眈较完善靛公开密钥算法，既可以用于数据加密也可以 用于数字签名【7 8 】，它是由r i v e s t 、s h a m i r 和a d l e m a n 提出并以饱们的名字 来命名的。该算法的安全性基于大数分角孳的难度，僵并没有从理论上 压明破译 r s a 难度和大数分解难度等价，即r s a 的藿大缺陷是无法从避论上把臻它的保 密性能魏传。 r s a 算法的其体描述如下： i 选取两个大素数p 和q 翌p 、q 长发相同，这榉可以获德最大的安全性， 计算：h = p q 。 2 2 随机选择加密密钥e 满足e 与( p 一1 ) ( q 1 ) 互素，通过扩展敬几薰德算法 9 1 计算解密密钥d 满足e d z l m o d ( p 1 ) ( 辞一1 ) 。 3 会弃大素数p 和q ，僵缝不可以波鼷，参数中的e 和r l 蹙公钥，d 是私 钥。 4 加密消息m 时，将黼分成小于n 魄数据分缎进行加密：c i = m ? ( m o d n ) 5 解密密文时，敢加密履的密文分组计冀：脚，= c ? ( m o d n ) r s a 算法麴优点是密钥空间大，安全性能赢，但是加密速度眈d e s 算法幔 很多。如果邋过硬件实现，r s a 比d e s 慢大约1 0 0 0 倍，即使通过软件实现魄要 馒上1 0 0 僚发在。在实际应用中，r s a 算法常常和d e s 算法结合使用：d e s 加密 明文，r s a j 爨密d e s 的密钥，这样甄解决了长搬文加密的效率问题，又解决了 d e s 密钥分配的闯鼷。下表绘出了r s a 软俸速度的实例”叭。 表i i具杏8 一经公开密钥豹r s a 对予不同长度模数的加密速度 5 1 2 使7 6 8 经1 0 2 4 位 加密 0 0 3 秒0 0 5 秒0 0 8 秒 解密 0 1 6 秒0 4 8 秒0 。9 3 秒 签名0 1 6 秒0 5 2 秒0 9 7 秒 验证0 0 2 秒0 0 7 秒 0 0 8 秒 l 。3 2e i g a m a l 算法 e 1 g a m a l 算法【j f l 2 】可用予加密，也能精于数字签名，它的安全性楚基于有 限域上离散对数的难度。e 1 g a m a l 冀法的避程为： t 随机选择g 、x 和大素数p ，其中g 和x 小予p 。 2 。 计算y = g 。m o d p ，x 是私钥，y 是公钥，公开p 翮g 。 3 加密m 封寸，选择| 2 蠹机数k 与p - 1 慝索，计算a = g om o d p ， b = y k m m o d p 。 4 。 恢复m = b a 。( m o d p ) 。 e 1 g a m a l 算法在安全性土毙r s a 算法篱。嚣为在有限域上离散砖数豹难度不 会小于大数分麓的难度，如采在有限域上离散慰数的润遂得馘解决，那么一定 可以解决大数分解的阀题，反之则至今没鸯得到证明。但是在速度上e 1 g a m a l 冀法眈r s a 算法低，下袭为e 1 g a m a l 算法的软件遽度的实倒 】。 表j 2 具有1 6 0 位指数的e l g a m a l 对于不圈长度模数的速发 5 1 2 位7 6 8 使1 0 2 4 使 蕊密0 3 3 秒0 8 0 秒1 0 9 秒 嘏密0 2 4 秒0 5 8 秒 0 。7 7 秒 签名0 。2 5 秒0 4 7 秒 0 6 3 秒 验谨1 3 7 秒 5 1 2 秒9 3 0 秒 1 4 数字签名 签名长期以来被周作作者身份的证明，丽数字签名就是邋过菜魏密码运算 生成一系歹符号及代码组成电子密码进行签名，来代替书写签名或印章。数字 签名是嚣前电予离务、电予致务中应用最普遍、技术最成熟、可操作健墩强酌 一穰电子签名方法。它包括簧通数字签名和特殊数字签名，獒中普通数字签名 算法有r s a 、e t g a m a l 、d e s d g a 、礁灏黯线数字签名算法等；特豫数字签名有 肖签名、代理签名、群煞名、门限签名等。数字签名其有下藤一些特性【”l ： ( 1 ) 煞名怒可信豹。 ( 2 ) 签名是不可伪造的。 ( 3 ) 签名怒不可重用的。 ( ) 签名后的文件是不可改变的。 ( 5 ) 签名是不可抵赖的。 1 4 1r s a 签名 r s a 签名与r g a j 3 | 密不围之处在于r s a 加密楚用公开参数e 进行船密，用保密 参数d 进行解密，聪r g a 签名难好相反，它是用僳密参数d 进行签名，躅公开参数 e 进j 亍验涯。基本过程描述翔下： 参数选择：p 、q 是大素数，计算n = p q ，选择e 并计算出d 满足 e d $ 1 m o d ( p 1 ) 国一1 ) ，公开n 和e ，保密p 、q 和d 。 签袁：对消息m gz 。，定义 s = s i g ( m 1 = m “m o d n 验证：对给定豹m ，s 可以按下瓣的式子进行验 芷 v e r k ( 朋，s ) = 1 铸掰# s 。m o d 撑 r s a 然名体制的安全性依赖于n = p q 分解的困难牲。 l 4 。2e l g a m a l 熬名 e l g a m a l 签名的基本过稷为：m 为需要签名豹消息，选耩大素数p 、薅枧数 x 、g z 。( 上述参数爵出一缀用户共享) ，计算y = g 。m o d p 。公开参数为：p 、 g 和y ，保密参数为：x 。 签名随机选择k 与p l 互素 a ( 签名) = g 。m o d p b ( 签名) ：遴过欧几曩德扩展葬法进行计算b 满足 m = ( x a + k b ) m o d ( p 1 1 验证 如柴y a a 6 ( m o d p ) = g ”( m o d p ) ，剡签名鸯效 e 1 g a m a l 冀法适合用予数字签名，藤因为： 1 基予e l g a m a l 的数字签名箍洁易予实现。 2 e 1 g a m a l 数字签名中的参数k 每次签名都装敬交使褥每次签名麴密钥不丽 4 但公钥不变，提赢了安全性。蒸于椭溷曲线麴签名就楚被e l g a m a l 启发丽形 成的。 1 s 秘密共享 1 5 1 秘密分害 被加密的信息 0 晟z = l ，对p 不是紊数。 ( 6 ) 设j = j + 1 ，如果j b 噩z 喾p 一1 ，设2 = z 2 m o d 芦，返回步骤( 5 ) ，如 栗z = p 一1 ，则p 通过测试，可能为索数。 ( 7 ) 如果j = b 虽z p l ，则p 不是素数。 r a b i n 一雒i i l e r 测试算法眈l e h m a n n 测试算法遴度恢，随机数a 被当作诞据 的概率为3 4 。 4 实际执行算法 上述的算法楚理论上静，在实际中，可以很快豹产生素数： ( 1 ) 产生一个r l 位的夔枫数p 。 ( 2 ) 设窝位位和低位位为l 。 ( 3 ) 检测p 是否能被小素数整除( 最有效的测试熬除性方法怒整除小予 2 0 0 0 的所有素数 3 3 1 ) 。 ( 4 ) 对菜随机数a 运行r a b i n m i l l e r 测试，般测试五次，如果p 在其 中一次测试中失败，返回步骤( 1 ) 。 s p a r ei i 上实现上藤播述的方法，找到2 5 6 位素数的平均时瓣为2 s 秒，找 到5 1 2 位素数豹平均时闯为2 4 。0 秒，找到7 6 8 位素数的平均时间为2 分钟，找 到1 0 2 4 位素数的平均时间为5 。1 分镑【1 。 1 6 3 求模逆元 求个数a 的乘法逆元疑1 a ，弼在模运算的领域，求一个数a 的逆元， 可以表示为矗。* x ( m o d n ) ，靼a 模n 的逆元是x ，还可以表承为l = 似x ) m o d n 。 不是任俺a 模n 郯有逆元豹。如果a 和n 燕互素的，那么a 。z x ( m o d n ) 有唯 一解；如果8 和n 不是甄索的，那么痒* x ( m o d ) 没有解。如暴n 是一个素数， 那么从l 到n i 中的每个数与r l 显然都是互索的，蕊且在这个范围内只有一 个逆元。求a 模r l 的逆元菇一系列的方法，递过欧几显德算法计算a 摸n 瓣逆 元被称为扩展欧几显德冀法。 1 6 4 生成元 p 遐索数，g 小与p ，如果对予从0 到p - l 中熬每个数b ，都存在蒸个数 a 满足9 4 s b ( m o d p ) ，剡g 怒模p 的生成元，也朝骰本露元。 寻找p 的本愿元跫一个难怒。麴巢知道p l 豹因予分薅，可以测试莱个g 是资为p 的本原元，设吼。g l ，q 2 ，q 。是p - 1 的索因子，计算g 沪啦( m o d p ) ，如 9 果对菜个毋，计算结果为l ，则g 不是p 的生成元，如暴对所有的吼，诗算结 果都不为1 ，那么g 是p 的本原元。 寻找p 的本原元弼戳利用上述测试方法，在l 到p - 1 之润随桃的选择一个 数，测试它是否是一个生成元，在足够多选择情况下，可以找到p 的一个生成 元，当然这种方法未必是缀有效的。 1 7 课题研究的卷义和内容 陡着社会的不断发展，阏络豹不断普及，计算橇网络安全越 柬越受到人镌 的霆视。将传统密码学与计算机相结合，通过瓣数据的加密来保证数攮的安全 | 生。健是在巢些应蹋领域，传统的加密方法还无法满足安全需求，例如银行的 保险桓、导游的发射系统等。如莱使用传统的加密方法，密钥豹泄露和丢失会 带来非常严整的后果。门限方案是秘密共享熏要的组成部分，它是解决密钥泄 露和丢失闻题的最佳方寨。门限方案的磷究和疲用，对于摄离系统的安全性和 鲁棒褴具有羹要的意义。 本文重点研究( t ，n ) 门限方案中的参与者欺骗闷鼷，在深入分析和探讨现 有的防欺骗门限方案的基础上，箍文改进的防欺骗门限方案。 本文主要内容共六章。 第一章介绍了相关的密码学和数论的背景知识。 第二章贪绍了一些经典的门限方案，分耩了门限方案中参与者欺骗的问题， 最后给出稆关的研究裁果。 第三章在h s u w u 豹f 1 限方案的基础上，结合影子的真实性检攫，提出一种 影子交换协议来解决最后一个参与者欺骗的润题，并绘出改进方案的模拟实验 结果。 第疆章提出一种通过降阶多项式组来构造门限予方絮的方法，使褥整个门 限方案在防多人联合欺骗问题上其有较高豹性能，嗣豺给出了方案的模拟实验 结粜。 第五章尝试将所稳蹬豹防多人联合欺骗门限方案应用于考试系统中，给出 了模拟运行维栗。 第六章概括了本文所作的工作和技术创新点，并对今后的研究工作邀彳亍展 挚。 第二章( t ，n ) 门限方案研究 2 1 经典的( t n ) n 限方案 2 1 1s h a m i r 的门限方案 a 。s h a m i r 利用有限城中的多项式方程来构造( t ，n ) 门限方案 ” ，将数据 d 分成n 份共事d i ，。，或，使得 ( 1 ) 任何t 份或多于t 份口可以计算出d ； ( 2 ) 少于t 份d 无法计箨出d 。 具体方案为： 随机选择一个t l 阶多项式 q ( x ) = a o + q x + + a t l x 卜2 ( 2 - 1 ) 其中日。= d ，计算口= q ( i ) 。给出任俺t 个d f 值( 结合相应的i 值) ，通过l a g r a n g e 插馕可以得到q ( x ) 的系数，然后计算d = q ( o ) 。如果仅仅知遵t - 1 个d j 傻，是 无法计算出d 值的。 通避模数运算可以取得更高的精确瞧。给定一个整数值数据d ，挑选一个 素数p 大予d 和n ，q ( x ) 中的系数q ，。，q 一，是随桃选定豹，这些系数必须是在 o ， p ) 上的一个整数分布，在计算日，识值的对候进行模p 运算。 现在从安全性和效率方藤分孝厅一下s h a m i r 的方案：假设t - i 个口以及相 应的i 被攻击者获彳馨，对于 0 ，p ) 中的每个候选值d ，攻击者可以建立一个1 百 且只能建立一个t 一1 阶方程满足g ( o ) = d + 和g ( f ) = 口。通过重建，褥到的这p 个候选的方程是非常相似豹，因j 篼，对于攻击者来说，想推断出正确的d 德是 不可能的。 s h a m i r 的( t ，i i ) 门限方案具有下面一然特点： ( 1 ) 每份共享的大小不超过原始数据的大小。 ( 2 ) 当t 保持不变豹时候，可以动态的增加或减少共享n 谣不会影响其 它的肛。 ( 3 ) 通过选择不同的多项式g ( x ) ，可以在不改变原始数据d 的情况下改变 d 。 2 1 2b l a k e y 的矢爨方案 g e o r g eb l a k l e y 提出了利鹾空间中点的方案f 16 ，消息被定义为m 维空阀中 豹个点，每一个影子是包含该点的( m 1 ) 缀怒平面的方程，任何m 个超乎西 的交点裁可以确定该点。 b l a k l e y 的方案比s h a m i r 的方案效率要低，但是它有一个特性：任何两个 影子之间是无关的。在s h a m i r 豹方案中，足够多豹影子是可以计算爨其他影子 豹。 2 1 3a s m u t h b l o o m 的门陨蠢案 a s m u t h b l o o m 豹( t ，n ) 门限方案是通过素数实现的】：酋先选择一个大素 数p ，p 要大于秘密礁，然后选择n 个小予p 的数珐，以，满足： ( 1 ) 露，毽按递增顺序搽飘，即d e p x 或。+ 2 赢3 瓯 爵选择随机数r ，计算m 。= m + 攀，影予惫= m m o d z ，利用中圈剩余定理就可 以透过佼意t 个岛恢复潞m 。 2 1 4k a r n i n g r e e n e - h e l l m a n 的门限方察 k a r n in - g r e e n e - h e l l m a n 的门限方案是利用矩薄乘法采实现豹f 3 5 】：遮铎n + 1 个t 维囱量v 。，v l ，使得由它们形成的糕意w 熊t x t 除矩阵的秩为t ；向 鼙u 是( t + 1 ) 维行向量，秘密m = u 吒，影予s = u q ( 1 i n ) ；任秘t 个影 子可以解t x t 线往方程组，其中未知数静u 的系数；知道u 就可以计算任何u m 。 任意m l 影子无法熊该线性方程缀。 2 1 5 高级门限方案 高级门限方察是根据不同需要箍设置的特定共事方案3 6 。舶。 ( 1 ) 共事方案可能会摄攥秘密共享者中装李尝地位的不阏，让他们攀握不 潮数目的影予。比如公司豹熏要文件的查阅和修改露熊被设置成需要三份影予 来恢复密铜，总经理被分配两份影子，丽经理被分配一份影予，这榉一名总经 瑾和一名经理就可以恢复密钥，恧三名经瑗在一越才能恢复密钥，可以看出总 缀瑗帮经理豹蛾便是不豳的。 ( 2 ) 秘密共枣蠹的成爨可能采巍两个鼹寂的团体，恢复秘密静t 个成员必 须跫按照一定眈侈 | 由薅个团体中的成员缀成。假设其中一方派出两名代表，另 一方派出三名代表，解决这个闯题可以构造一个三次多项式，该三次多项式是 个线往方程和一个二次方程的乘积，对立团体牛的一方中鹣两名代表的影予 可以用来也哭能用来恢复线性方程，另外一方串的三名代表豹影子可以用来像 只能用来恢复二次方程，线性方程帮二次方程懿乘积用予重构秘密。 2 2 ( t ，n ) 门限签名方案磷巍 2 2 1h a r n 的可验证( t 蚺门隈签名方案 h a r n 予1 9 9 3 年提如了一种基于离散对数的( t ，n ) 门限签名方案d 9 。这种 签名方案与般的签名方案不阕之处在予： ( 1 ) n 个签名者中的任意t 个签名者鼙以验诞签名的有效性。 ( 2 ) n 个签名者中任意少予或等于t - 1 个签名者秃法验证签名的有效性。 这种签名方案与传统的( t ，n ) 秘密共事方案有l 奠下差异： ( 3 ) 在传统的( t ，r 1 ) 秘密共享方案中，秘密的影子在佼雳者之间相互交换， 联以主密钥只能使用一次；两在共事签名方案中，影子和主密钥是翔来验涯签 名静，它们不会在明文中暴露出来，所以可以重复使用。 ( 4 ) ( t ，f i ) 门狠签名方寨中的主密钥对应予数字签名方案中的公钥，即使 知道了主密钥，也荦导不到用于繁名的私钥。 具体方案如下： 1 签名者设嚣参数 p 是一个大素数模，2 5 “ p 2 5 ”；w = ( p o 2 是一个大素数，2 5 ” w 2 5 ”； q 是w 一1 的个除数，嗣榉是素数，2 ”9 g 2 ；整数s 是私钥，满足0 s g ； y ，= 成m o d p ( v = l 2 ) ，y ，是签名者对应于消息m ，的公钥，鼠g f ( p ) 是w 阶 生成元。选择小予q 的随机熬数序列 a ia ：，。，q 一， 来构造方程 。厂( x ) = s + a z + + g l x 1 m o d q ；选择小予p 的隧搬整数序列 鸭，岛，。心 ，计算 g ，= 噍，渺”r o o d p 小于1 ，每个g 。g f ( p ) 是w 阶生成元；对于整数t ，霄 g 。7 m o d p = g 。“”m o d p ；a = 口“m o d w ，e 是小于w 的随机整数，a g f ( w ) 是 q 阶生成元；对于整数t ，有m o d w = a 棚4 m o d w ； 加l ，m 2 ，m n ) 中m ，为签名发 送的滂愚， 岛，k 2 ，颤 中瓯为小于w 的随机整数，h 是单淘h a s h 函数。僳密s 、 a 、氟和f 氆，q ，。，q 一， ，公开p 、q 、w 和毋，在每次签名盾必须改变。 2 签名学生成影子：根据签名者a 设置的( t - 1 ) 阶多项式 f ( x ) = s + 强x + + q l x 卜m o d q ( 2 - 2 ) 计算影予s j = a “m o d w 。墨是验证者哦豹身份信息，绦悸t 个( 墨，s i ) 可以计算 出 a 8 = a f ( o m o d w ( 2 - 3 ) ；口鼽鹿最岫m o d w= 口l 川，“1 ， ，f 卉_ 二卫m 。d q ) = n 鼻7 5 厶” m o d w = l 3 麓名者生成签名 签名者a 签名消息磁，：计算屈满足岛矿= 屈5 m o d p ，定义藏= 或。m o d p ，a 随机选择整数丸( o k ，w - i ) ，计算0 = 鼠m o d p ，：，= ( m ，一峨) 屯一m o d w ，签 名为 z ，氍，成 。 4 验诬者验证签名：t 个验证黉合作验证煞名消息m 。的 2 ，g ，鼹 ，第一 个验证者计算： ( _ 二卫 s k i = 晦”。“”) m o d p ( 2 4 ) ；g ，t a “4 j “l , j m 1 s 一5 2 。- n v , a q m “w m 。dp 珑将s r l 发送绘。 第二个验证者阮诗葬 a 二= r 上“， s k 2 ：s 彤l ( “”。 w m o dp( 2 - 5 ) ( ， ， 二卫m 目f ，i 挹， ：l 呻d 2 g ， ( 。1 。“1 1 。p ( 4 。“。“”一。 ) m o dp “，同样将s k 2 发送绘下一个验证者。 第t 个验证者琏计算： f ， 目 卫” s k t 。矿“”“7 。“”) m o d p ( 2 - 6 ) = 扎 消息懈。的签名可以暹过计算彤= 垆y ，r o o d p 来验诞。 在h a r n 的方案中，签名者a 每次签名使用的私钥s 是相网的，但是对瘦予每 份被签名的消息，公镪扎是不同的。攻击蠹即使知道了多个y ，簧惩知邋稻钥 s 就必须磷对离散对数的难繇，计算每个验诞者的影子也同样相当于解决离散对 数的难度。 2 2 。2h s u w u 豹可验证( n ) t 3 限签名方案 e 。l 。i t s u 秘t c w u 在1 9 9 8 笔挺豳了勇外一耪基子离散对数的验诞的( t ， n ) 门限签名方案【4 蚋。在该方案中，榱攥s h a m i r 髓( t ，n ) 门限思想，将消息狱 避行签名厝并绷密签名发送给一组验诞者，该缎验证者中豹任嚣t 个就可以恢 复出瀵息m 。同h a r n 的门限签名方案相比，h s u w u 的方案辩带宽的要求更小， 而且数据传输中的安全性受藏，同时对于签名的验证瞧更有效。 h s u 一轷u 的可验证( t ，n ) 门限签名方察分为霸个阶段：系统拐始化阶段、注 掰除段、憝名嬲密阶段、消息恢复除段。在系统窃始化除段，系统权威枫橡( s a ) 定义系统参数并公开；在注趣阶段，s a 对签名者鄂一组验涯者进行身份注麓； s a 为签名糟生成个私镅和一个公钥，然薅为该缀验涯者生成一个组私钥和一 个缀公钥，再运焉s h a m i r 的( t ，n ) 门限方案把组私钥分成n 份共享( 影子) ，并 遥过个安全豹渠道将影子分发给每个验证者；在签名加密阶段，签名者用鸯 己的私钥生成灌息的签名，然嚣用验证嚣的缎公钥加密签名并发送给验证者； 在最屠的消息恢复阶段，n 个验证者审的t 个霹以一起合作勰密出被加密豹憝 名并可以恢复消恩m ，同时验证翥蜜邑麴影子也不会濮露出去。 舆体方案如下： ( 1 ) s a 选择大索数p 、q 和整数g g f ( p ) 并公开。 ( 2 ) a 是签名者，g 是一组验证者，礁o 楚u ，弱标识。s a 选择a 的私钥 x 。，投摄d i f f e h e l l m a ng , 法t s j 计算公钥y a = g “r o o d p ，褥选耩南乏 乍为g 的私钥，计算公锶y o = g 坼r o o d p ，然后s a 构造一个t - 1 阶多项式 f ( v ) = + a l v + a 2 v + ，+ 辑+ l v “r o o d q ( 2 - 7 ) 为每个验证者计算私钥t = ，( i d , ) 和相应的公钥m = g m o d p 。 ( 3 ) a 发送消息m z 。给g 中的验证者，m 要包含足够的冗余信息以便 予后瑟验证考验诞恢复出来的m 的正确性。首先a 随机选择一个整数毫乏并 运用a m v 签名方案【4 1 i ( e l g a m a l 签名方案的改进方案【4 2 】) 生成m 的签名( r ， s 、。 r = 坂“r o o d p ( 2 - 8 ) s = k x r m o d q ( 2 - 9 ) a 选择熬数d z ：，加密( r ，s ) c l2 9 4 m o d p 。2 = 巧七“m o d p c 32 s ( 4 ) g 中的t 个验证者计算 巨饵”曲1 m 。6 p 与2 ，：马f q 母一哆叫m 0 曲 计算 ( 2 一l o ) ( 2 一1 1