多重门限密钥共享机制与应用
- 格式：pdf
- 大小：314.54 KB
- 文档页数：4
第２９卷
ＶＯ１．２９ 第１９期
ＮＯ．１９ 计算机工程与设计
Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｄｅｓｉｇｎ ２００８年１０月
Ｏｃｔ．２００８
多重门限密钥共享机制与应用
贺忠华， 周永权
（广西民族大学数学与计算机科学学院，广西南宁５３０００６）
摘要：针对密钥管理机制的需求，将共享密钥ｋ，采用Ｓｈａｍｉｒ（ｔ，ｎ）门限分解为ｎ个密钥份额，对所产生的＂个密钥份额，再次
使用（１，ｒｔ）门限进行分解，分别形成下一级的密钥份额，以此类推，形成经过多重门限所分解的密钥份额，由此推广了Ｓｈａｍｉｒ （ｔ，ｒｔ）门限密钥共享机制，提出了更一般的多重门限密钥共享机制，并给出了多重门限机制针对招投标系统在各种不同需求
下的应用解决方案。 关键词：秘密共享；多重门限；子秘密；密钥；招投标系统 中图法分类号：ＴＰ３９３．０８ 文献标识码：Ａ 文章编号：１０００—７０２４（２００８）１９—４９２９—０３
Ｒｅｓｅａｒｃｈ ａｎｄ ａｐｐｌｉｃａｔｉｏｎ ｏｆ ｍｕｌｔｉｐｌｅ—ｔｈｒｅｓｈｏｌｄ ｋｅｙ ｓｈａｒｉｎｇ
ＨＥ Ｚｈｏｎｇ—ｈｕａ， ＺＨＯＵ Ｙｏｎｇ—ｑｕａｎ
（Ｓｃｈｏｏｌ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｇｕａｎｇｘｉ Ｕｎｉｖｅｒｓｉｔｙ ｆｏｒ Ｎａｔｉｏｎａｌｉｔｙ，Ｎａｎｎｉｎｇ ５３０００６，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ａｃｃｏｒｄｉｎｇ ｔｏ ｋｅｙ ｍａｎａｇｅｍｅｎｔ ｍｅｃｈａｎｉｓｍ，ｔｈｅ ｓｅｃｒｅｔ ｋｅｙ ｋ ｉｓ ｄｉｖｉｄｅｄ ｉｎｔｏ”ｓｅｃｒｅｔ ｓｈａｒｅｓ，ｔｈｅｎ ｅａｃｈ ｏｆ ｓｅｃｒｅｔ ｓｈａｒｅ ｍａｙ ｂｅ ｄｉｖｉｄｅｄ ｉｎｔｏ ｔｈｅ ｏｔｈｅｒ ｎ ｓｅｃｒｅｔ ｓｈａｒｅｓ ｂｙ ｕｓｉｎｇ（ｔ， ）ｔｈｒｅｓｈｏｌｄ ｔｅｃｈｎｉｑｕｅ ａｇａｉｎ ａｎｄ ＳＯ ｏｎ．Ｓｏ ａ ｍｏｒｅ ｇｅｎｅｒａｌ ｍｕｌｔｉｐｌｅ—ｔｈｒｅｓｈｏｌｄ ｓｈａｒｉｎｇ ｍｅｃｈａｎｉｓｍ ｉｓ ｐｒｏｐｏｓｅｄ．Ｓｈａｍｉｒ（ｆ， ）ｔｈｒｅｓｈｏｌｄ ｓｈａｒｉｎｇ ｍｅｃｈａｎｉｓｍ ｉｓ ｅｘｔｅｎｄｅｄ．Ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｐｒｏｐｏｓｅｄ ｍｅｃｈａｎｉｓｍ ａ ａｐｐｌｉｃａｔｉｏｎ
ｔｏ ａ ｂｉｄｄｉｎｇ ｓｙｓｔｅｍ ｕｎｄｅｒ ｖａｒｉｏｕｓ ｅｎｖｉｒｏｎｍｅｎｔｓ ｉｓ ｄｅｔａｉｌｅｄ．
Ｋｅｙ ｗｏｒｄｓ：ｓｅｃｒｅｔ ｓｈａｒｉｎｇ；ｍｕｌｔｉｐｌｅ－・ｔｈｒｅｓｈｏｌｄ；ｓｕｂ・－ｓｅｃｒｅｔ；ｋｅｙ；ｂｉｄｄｉｎｇ ｓｙｓｔｅｍ
０ 引 言
在保密通信中，通常人们采用密钥来加密所需保密的信
息，即不拥有密钥的非法用户无法窃扶信息，这使得信息的安
全保密主要维系于密钥的安全，因此，如何有效地管理密钥已 成为密码学中重要的研究课题之一。１９７９年，Ｓｈａｍｉｒ提出了
（ｆ，ｒｔ）一门限密钥分散管理的概念“’，该方案解决了一组参与者
各成员对同一个密钥Ｋｅｙ的共享问题。后来出现了不少有关 门限密钥共享与签名的研究文献［２－６】。然而，在实际应用中，
因为参与密钥管理的人在系统中所处的地位不尽相同，有许 多活动必须要求某些特定的人参与才能进行，如在开电视会
议时，主讲人必须到场，因此在恢复会议密钥时，必须有主讲 人参与：义如在招投标系统中，当对标书评标时，要求招标方、
投标方、公证处等每一方都必须有代表参加，这样才能打开标
书。显然，这些实际需求通过Ｓｈａｍｉｒ（１，ｎ）门限机制是无法实 现的，这就要求人们另寻途径来构建密钥共享体制。本文根 据实际应用问题的特定要求，将（，，Ｆ／）门限加以推， ‘，提出了…
种更为一般的多重门限密钥共享机制，并给出这种机制的实
现方案。同时，基于‘个具体应用——网上招投标系统，根据
该系统的特定需求，包括指定若干人必须参加评标、分组参加 评标、指定若干组必须参加评标、权重不同的成员评标等，详 细阐述多重门限机制在这些需求中的实现方法。
１ Ｓｈａｍｉｒ（，，，ｚ）门限密钥共享机制
Ｓｈａｍｉｒ提出的（ｆ， ）门限密钥分散管理的概念，简记为ｆ，，？） 门限方案，该方案将一个密钥分成ｒ／个部分（称为 个予密钥），
分别交给ｎ个人保管，使得对确定的整数 ＜Ｈ）满足： （１）在这ｎ个人中，任意ｒ（，≥ｆ）个人协作都能恢复出原密钥。
（２）任意ｒ（ｒ 个人协作对恢复原密钥没有任何帮助。
为实现（ｆ，ｒｔ）门限机制，Ｓｈａｍｉｒ提出使用Ｌａｇｒａｎｇｅ插值多项
式方案来共享秘密Ｋｅｙ。该方案是用有限域ＯＦ（ｐ）上的一个卜１ 次多项式：， ）＝ａ ＋ Ｉ２＋…＋口．ｘ＋ａｏｍｏｄｐ来构造（ｆ， ）门限 体制。其中所选的随机素数ｐ要大于最大可能的密钥Ｋｅｙ和参
与者总数 ，并且公开。 ａ。＝厂（０）…ａ，，口卜 ，…，ａ，为所选用的
随机系数，在生成ｎ个秘密份额后即可丢弃。已知共享秘密
Ｋｅｙ，以及所选用的随机系数ａ ，口卜 ，…，ａ，，通过计算多项式 ） 对 个不同置的取值就可将密钥Ｋｅｙ分解为 份秘密份额 ，，
Ｋ２，…， ，且 ＝ ｊｍｏｄＰ，ｉ＝１，２，…， 。每一（ｘｉ，Ｋ）可以看作曲
线 ）上的一点，并可作为一个成员的标识符。 由于任意ｔ个点都可惟一地确定相应的ｆ—１次多项式，所
收稿日期：２００８—０４．１ ５ Ｅ—ｍａｉｌ：ｈｚｈ＠ｇｘｕｎ．ｃｎ 基金项目：国家自然科学基金项目（６０４６１００１）；， 一西自然科学基金项目（０５４２０４８）。 作者简介：贺忠华，女，硕士，讲师，研究方向为数据库与Ｗｅｂ服务、网络与信息安全； 周永权，男，博士，教授，研究方向为计算智能及其 应用。
——
４９２９—— 以，秘密Ｋｅｙ可以从ｔ个秘密份额重构。给定任意ｔ个秘密份额
，ｊ ，… ，由Ｌａｇｒａｎｇｅ插值公式可重构多项式厂
， ）＝∑ ｎ —ｘｊ）／（ｘ 一与）ｍｏｄｐ １ ｊ＊ｉｄ一１ ｍｆ￣ｘ）得Ｎｔ个秘密份额所重构的密钥Ｋｅｙ＝ｆ＇（Ｏ）。
２多重门限密钥共享机制
Ｓｈａｍｉｒ（ｒ＇ｎ）门限密钥共享机制能解决一组成员共享一个
秘密的问题，但未能满足现实中的特定需求。因此，本文将
Ｓｈａｍｉｒ（ｔ，ｎ）门限密钥共享机制加以推广，提出多重门限密钥共 享体制，以解决实际应用的多种需求。
２．１算法思想 多重门限机制以Ｓｈａｍｉｒ（ｆ， ）门限机制为基础，首先将共 享密钥Ｋｅｙ，采用（ｆ’，１）门限分解为 个密钥份额；其次，对所产生
的，１个密钥份额，可再次使用（厶 ）门限进行分解，形成下一级的
密钥份额，依此类推，可以形成经过多重门限所分解的密钥份 额。即多重门限密钥共享机制的算法思想。
经多重（ｆ，，ｔ）门限之后，共享密钥Ｋｅｙ分解为多个密钥份额，
并且分级分配给多个用户保管，而只有这些用户经过逐级的 （ｆ’，１）密钥重构，才能重新重构共享密钥Ｋｅｙ。因此，多重门限机
制解决了分级，分组的用户秘密共享问题。 ２．２算法详细描述 多重门限密钥共享机制的密钥分配原理图如图１所示，
Ｋｅｙ为共享密钥，（ 。，ｎ 。）为Ｓｈａｍｉｒ门限机制， ”等为通过 门限机制所分解的密钥份额，如果密钥Ｋｅｙ经过ｋ重分解，则经
过ｋ重门限所形成的叶子节点的密钥份额为最终用户所拥有
的密钥份额。 多重门限密钥共享机制用于解决多种需求下的秘密共享
问题。因此，需要解决密钥分解和密钥重构问题。以下基于
图１的原理图，详细描述密钥分解和密钥重构过程。 （１）密钥分解：对共享密钥Ｋｅｙ进行分解的过程如下：①对 共享密钥Ｋｅｙ，采用Ｓｈａｍｉｒ（ｆ＇ ）门限分解为，ｚ个密钥份额。②对
任意分解的 个密钥份额，可以再次使用Ｓｈａｍｉｒ（，， ）门限分解
为ｒ１个下一级密钥份额。③重复②，多次运用Ｓｈａｍｉｒ（ｆ＇ 门限 之后，就形成了多重门限下的多个密钥份额。
（２）密钥重构：采用多重门限密钥共享机制，对密钥Ｋｅｙ重
构的过程实际是分解过程的逆过程，即从第ｋ级开始，采用 Ｓｈａｍｉｒ的重构机制进行重构，产生第ｋ一１级的密钥，然后再次
重构第ｋ一２级的密钥，直到重构为最终的共享密钥Ｋｅｙ。
二重
‘
…‘‘
－——４９３０－—— 图１多重门限密钥共享体制 ３应用实例
我们知道招投标是一种非常重要的商业活动，在招投标过 程中，投标方（各家厂商）向招标方投一份加密的标书，在等待开
标这段时间内不允许其他人（包括招标方）看到标书里的任何信
息，直到评标。在评标的时候为了保证评标的公证性，避免黑 箱操作，要有公证人、投标方、招标方同时在场才可以开标评
标。同时要求公证方必须至少有一人在场才可以进行开标。
当通过信息化方式即通过网络实现招投标系统时，为了 避免招标方和公证人进行联合欺骗，或避免某人因故缺席而
无法开标的尴尬局面的产生，可通过采用Ｓｈａｍｉｒ门限机制来 实现，即在投标时，投标方将加密标书的密钥Ｋｅｙ通过（ｆ’ ）门限
机制分解为ｎ个秘密份额，并分配给给指定的ｎ个合法开标人 （来自投标方、招标方和公证方），当开标时，要求这，１个人中只
要ｔ（１≤ｆ≤ｎ）个人同时在场就可以成功打开标书进行评标。如
果合法的开标人达不到指定的人数ｔ，则无法成功解密标书。 显然，使用Ｓｈａｍｉｒ门限机制可以实现招投标系统中的基本
需求。但是在实际应用过程中，由于评标人所处的地位和重要 性不尽相同，招投标双方可能会提出特定的要求，这些要求包括
指定某个可信的人（如公证处人员）必须参加才能评标；将开标人
员分组，其中的任意几组参加就可以评标，并且每组中的若干成 员参加就可代表该组评标；将开标人员分组，并且某些组必须参
加才能评标；为突出某些成员的地位和重要性，要求给予其权值
不同的密钥份额，如给定经理两个密钥份额，即经理可以代表 两个人等；这些需求不能通过Ｓｈａｍｉｒ门限来实现，但是通过多 重门限密钥共享机制可以实现这些要求。因此以下详细讨论
多重门限密钥共享机制在招投标系统中的应用和实现。 ３．１指定若干人必须参加的招投标系统 在招投标系统中，为保证公平性和公正性，招投标双方希
望能有双方都可信任的人（如公证处人员）参加评标才能打开
标书；即这些所信任的人必须参加招投标，才能顺利打开标 书，否则不能完成评标。这就是在招投标系统中，指定若干人
必须参加的特殊需求。 假定加密标书的密钥为Ｋｅｙ，开标总人数为月个，要求开标
所需人数为ｆ个，指定必须参加开标的人数为 个，则通过多重
门限密钥共享体制进行密钥分解的过程如图２所示。 由图２，将主密钥Ｋｅｙ分配给ｎ个开标人共享的步骤为：
（１）将主密钥Ｋｅｙ通过 ＋ｌ，什１）门限机制分解为 １个密钥 份额，其中的Ｓ个密钥份额 。， ，…， 分配给Ｓ个指定必须参加
的成员，另一个密钥Ｋｒ再作为剩余 一 ）个成员共享的主密钥； （２）将密钥份额Ｋｒ再次通过（ｆ—Ｓ，ｒｌ－ｓ）门限机制分解为，ｌ—
图２
指定 个人必须参加的招投标系统
