（计算机应用技术专业论文）秘密共享体制方案的研究与实现.pdf

硕士论文秘密共享体制方案的研究与实现 摘要 秘密共享是实现信息安全和数据保密的重要手段，它在防止重要信息和秘 密数据的丢失、毁坏、被恶意修改或被不法分子利用中起着非常关键的作用， 已经成为现代密码学领域中一个重要的分支，同时它也是信息安全方向一个重 要的研究内容。 本文利用加权门限和m i g n o t t e 列，结合中国剩余定理提出了一个新的秘密 共享方案，该方案解决了目前大部分秘密共享方案需要参与者掌握多个子秘密、 管理和传递这些子秘密不安全等缺点问题。本方案只需每个参与者保存一个私 钥，简化了密钥的管理和使用，并且利用公告牌避免了秘密信息的传递，同时 秘密分发者可以很轻易地改变方案的秘密信息和门限值，使方案的管理具有很 大的灵活性。 本文利用一维可逆细胞自动机的特点，结合中国剩余定理提出了一个新的 秘密共享方案。该方案将一个秘密信息分解成若干个子秘密，以二进制文本形 式将这些子秘密分别作为可逆细胞自动机的初始配置，演化出秘密共享份额， 最后通过其反向迭代功能恢复出这些子秘密，进而重构秘密信息。 本文在最后对这两个方案都进行了模型实现，计算机仿真表明，以上方案 易于实现，且具有较好的安全性。 关键词：秘密共享，可逆细胞自动机，密钥管理 a b s t r a c t 硕上论文 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 tt o o lf o rt h ei n f o r m a t i o ns e c u r i t ya n dt h ed a t a p r i v a c y ，a n di tp l a y sa ni m p o r t a n tr o l ei np r o t e c t i n gi m p o r t a n ti n f o r m a t i o na n d s e c r e t d a t af r o mb e i n gl o s t ，d e s t r o y e d ，v i c i o u s l ym o d i f i e d ，o ri n t ow r o n gh a n d s s e c r e t s h a r i n gh a sb e e no n ei 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 ya n da l s o o n e i m p o r t a n tr e s e a r c hf i e l do fi n f o r m a t i o ns e c u r i t y i nt h i sp a p e rp r o p o s e dan e ws e c r e ts h a r i n gs c h e m ew i t hu s i n gt h et h e o r e mo f w e i g h t e dt h r e s h o l da n dm i g n o t t er o wc o m b i n a t i o nw i t hc h i n e s er e m a i n d e rt h e o r e m t h i sp r o g r a mr e s o l v et h es h o r t c o m i n g sq u e s t i o n sw h i c ht h em a j o r i t yo fc u r r e n t s e c r e ts h a r i n gs c h e m en e e dt h ep a r t i c i p a n t sh o l dan u m b e ro fs u b m a s t e rs e c r e t sa n d t h em a n a g e m e n ta n dd e l i v e r ya rei n s e c u r i t y i nt h i sp a p e rt h ep r o p o s e ds c h e m eo n l y r e q u i r e se a c hp a r t i c i p a n tt oh o l do n es i n g l ep r i v a c yk e y ，w h i c hs i m p l i f i e st h e m a n a g e m e n ta n du s a g eo f t h ep r i v a c yk e y ，a n du s et h eb u l l e t i nb o a r d st oa v o i dt h e t r a n s m i s s i o no fs e c r e ti n f o r m a t i o n ，s e c r e td i s t r i b u t o rc a l l e a s i l yc h a n g et h e p r o g r a m ss e c r e t i n f o r m a t i o na n dt h et h r e s h o l d ，m a k et h em a n a g e m e n to ft h e p r o g r a mw i t hag r e a td e a lo ff l e x i b i l i t y b a s e do n ao n e d i m e n s i o n a lr e v e r s i b l ec e l l u l a ra u t o m a t aa n dc h i n e s e r e m a i n d e rt h e o r e m ，an e ws e c r e ts h a r i n gs c h e m ew a sp r o p o s e di nt h i sp a p e r t h i s p r o g r a mb r e a k sd o w ns e c r e tm e s s a g ei n t o an u m b e ro fs u b - s e c r e t s m u l t i p l e s u b s e c r e t sw i t ht h ef o r m so fb i n a r yt e x ta lec o n s i d e r e da so n eo ft h ei n i t i a l c o n f i g u r a t i o n so ft h er e v e r s i b l ec e l l u l a ra u t o m a t a , e v o l v e dt h es e c r e ts h a r e ds h a r i n g a tl a s t ，t h eb a c k w a r di t e r a t i o no ft h er e v e r s i b l ec e l l u l a ra u t o m a t ai su s e dt or e c o v e r t h es u b - s e c r e t s ，t h e nr e c o n s t r u c t i o nt h es e c r e tm e s s a g e a tt h ee n do ft h ep a p e r ，i m p l e m e n t i n gt h em o d e l so ft h et w on e wp r o g r a m s ， c o m p u t e rs i m u l a t i o ns h o w st h et w op r o g r a m sa r ec o r r e c ta n df e a s i b l ew i t hg o o d s e c u r i t y k e y w o r d s ：s e c r e ts h a r i n g ，r e v e r s i b l ec e l l u l a ra u t o m a t a ，k e ym a n a g e m e n t i i 图表目录硕上论文 图表目录 图2 1 3 1 二维细胞自动机及其邻居7 图2 1 4 1 采用反射型的一维细胞自动机8 表2 2 17 6 号映射规则9 图4 1 1 可逆细胞自动机的状态转换示意图2 0 图4 1 2 11 7 0 号和2 4 0 号作用后的结果2 2 图5 1 1 模型系统的运行流程图2 6 图5 1 2 系统主界面2 6 图5 2 1 初始化的结果2 7 图5 2 2 关于模n 的大数幂乘的算法框图2 7 图5 3 1 方案转换算法框图2 8 图5 3 2 方案转换后的结果2 9 图5 4 1 公告牌上的信息3 0 图5 5 1 求逆元算法运行框图3 0 图5 5 2 恢复后的结果3 l 图6 1 1 模型工作流程图3 2 图6 2 11 7 0 号细胞自动机加密算法框图3 3 图6 4 1 产生5 个子秘密3 4 图6 4 2 将子秘密转换为二进制3 5 图6 4 3 1 7 0 号细胞自动机加密后的结果3 6 图6 5 1 份额不够时恢复的结果3 7 图6 5 2 2 4 0 号细胞自动机转换的结果3 8 图6 5 3 利用中国剩余定理恢复的结果3 9 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本学 位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或公布 过的研究成果，也不包含我为获得任何教育机构的学位或学历而使用过的 材料。与我一同工作的同事对本学位论文做出的贡献均已在论文中作了明 确的说明。 研究生签名： 缀孵 科晰 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或上 网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并授权 其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密论文， 按保密的有关规定和程序处理。 研究生签名：韭 1 舢溺 硕士论文秘密共享体制方案的研究与实现 1 绪论 密码技术是- i 1 历史悠久的学科，早在三千年以前，古埃及人为了记载历代法老王 朝的业绩，利用一些奇特象形符号来代替一般的象形文字，从而达到保存秘密信息的目 的。当今随着计算机网络技术的不断发展，特别是i n t e r n e t 的广泛应用，在金融、商 业、文化教育、工农业生产、军政等社会的各个部门中己大量使用各种基于网络的系统， 如电子商务、电子政务、电子货币自动转账支付等等。伴随着计算机网络的广泛应用， 一方面给人们的生活提供了方便，另一方面也提出了很多需要解决的问题。其中信息的 安全性就是一个突出的问题。因此在保密通信中，人们主要采用加密的手段来保密信息， 而核心是密钥的保密问题，密钥的管理直接影响着加密系统的安全，从而如何有效地管 理密钥就成为密码学中十分重要的课题。 1 1 研究背景与意义 当今社会，随着互联网技术发展的速度加快，它在日常生活中发挥着越来越重要的 作用，人们可以利用互联网进行网上购物、远程教育、发送电子邮件等操作。但是，互 联网有利有弊，首先它是一个开放的网络，所以存在着比如黑客攻击、网络犯罪以及信 息传输时存在的不安全因素等等。因此当利用互联网进行商业和通信时，保证信息的保 密性、完整性已经成为了一个非常紧迫的问题。信息安全技术由此应运而生，信息安全 技术是结合数学、计算数学、信息科学等多学科的交叉学科。 在通信中，为了较好实现信息的安全保密，主要采用加密的手段来保密信息，而加 密的核心是密钥的保密问题，密钥的管理直接影响着通信系统的安全，从而如何有效地 管理密钥就成为密码学中十分重要的课题。在k e r c h h o f f 假设下，一个秘密系统的安全 性并不是由所采取的算法决定，而是取决于密钥的是否安全。因此需要确保攻击者不能 访问密钥，但是在实际应用中，这一点是很难保证的。 如何降低密钥泄漏的可能性和降低密钥泄漏的危害性是一项十分重要的研究工作。 以前对密钥的保护主要是通过硬件存储的方法实现的，对密钥的操作都在硬件中进行 的，但是这种方法的缺点就是需要大量昂贵的硬件设备。 秘密共享体制就是针对这种情况而产生的。现在介绍一下什么是秘密共享体制，假 设一个组织共同拥有的秘密信息为s ，参与保管此秘密信息的参与者人数为刀，秘密信 息的分配者使用一定的算法将秘密信息s 分为玎个子秘密分别分配给这n 个参与者来保 管。当符合人数的参与者合作时，利用保管的子秘密采用一定的算法可以恢复原始的秘 密信息s ，而不符合要求数目的参与者合作则恢复不了s ，这种体制称为秘密共享体制。 其中如果甩个参与者中任意，个或者，以上合作即可恢复秘密信息s ，任意少于t 个参与 1 绪论硕上论文 者合作时不能恢复秘密信息s ，称这种秘密共享体制为( f ，2 ) 门限秘密共享体制【l 】。 b l a k l e y 2 和s h a m i r l 3 1 分别于1 9 7 9 年独立地提出了秘密共享的概念，并分别设计了具 体的体制。秘密共享体制为密钥管理提供了一个非常有效的途径，在政治、经济、军事、 外交中得到了广泛应用。例如，在一个公司里，每天都需要打开保险柜，公司有4 个保 管员，但是公司并不将密码委托给单个保管员。利用秘密共享体制就可以设计这样一个 系统，在这个系统中，任何2 个保管员或2 个以上合作都能打个保险柜，但任何单独一个 人就不能打开。同样秘密共享在军事上也有重要的用途，例如，在控制导弹发射时必须 由3 人或多人同时参加才能生效。 目前，秘密共享中主要有以下几个问题： ( 1 ) 没有分配者的秘密共享 这种秘密共享体制中，有厅个参与者，但是没有分配者将秘密分为以个子秘密，而 是采取了一种门个参与者就可以产生秘密信息的协议，通过协议，每个参与者可以得到 一个有效的子秘密，在恢复秘密信息之前，没有任何人知道共享的秘密是什么东西【1 】。 ( 2 ) 有欺诈者的秘密共享 有许多方法可以欺骟秘密共享体制，下面是其中的几种： 情景1 ：上校a l i c e ，b o b 和c a r d 在某个隔离区很深的地下掩体中。一天他们从总 统那得到密码消息：“发射那些导弹，我们要跟根除这个国家的神经网络研究残余 。 a l i c e ，b o b ，c a r d 出示他们的子片段，但c a r d 却输入一串随机数。她实际上是和平主 义者，不想发射导弹。由于c a r d 没有输入正确的子片段，因此他们恢复的信息是错误 的，导弹没有发射成功。即使a 1 i c e 和b o b 一起工作，他们也不能证明c a r d 的子片段 是无效的i 。 情景2 ：上校a l i c e ，b o b 和c a r d u 与m a l l o r y 一起坐在掩体里，m a l l o r y 是伪装的。 同样消息从总统那来了，并且每个人都出示了他们知道的子片段，m a l l o r y 只有在看到 他们三人的子片段之后才出示他的子片段。由于重构这个秘密只要三个子片段，因此他 能够很快地产生一个有效的秘密并显示出来。现在，他不仅知道了秘密，而且没有人知 道他不是这个方案的一部分i l j 。 如今，随着计算机网络和数字通信的迅速发展，秘密共享体制的应用日益广泛。近 年来在密码学会议及有关的杂志上，如j o u r n a lo fc r y p t o l o g y ，n e t w o r ks e c u r i t y 等， 研究关于秘密共享体制的文章层出不穷。 1 2 国内外研究现状 1 9 8 3 年，a s m u t h n b l o o m 4 1 对基于中国剩余定理的门限秘密共享体制进行了研究，同 年，k a r n i n 、g r e e n e 和h e l l m a 5 1 将信息论引入秘密共享体制的研究。1 9 8 6 圭g ，b e n a l o h l 6 】 提出了同态秘密共享体制的概念。f r a n k e l 7 1 等人推进了同态秘密共享体制的研究。1 9 8 9 2 硕上论文秘密共享体制方案的研究与实现 年，b r i c k e l l 【8 1 给出了矢量空间访问结构的定义，并且提出了基于矢量空间访问结构上 的完备秘密共享方案。1 9 9 1 年，b r i c k e l l 和d a v e n p o r t 瞵j 揭示了理想秘密共享体制和拟阵 之间的关系。1 9 9 2 年，曹珍富【9 】提出了秘密共享的2 次密钥方案。1 9 9 4 年，h e 矛i d a w s o n 1 0 】 利用单向函数提出了多级秘密共享体制。 如何抵抗欺诈是秘密共享体制的另一个重要研究方向。t o m p a 和w o l l 1 1 】提出的预防 欺诈的( f ，z ) 门限秘密共享算法将密钥集s 分为和l e g a l 且= s - - s i ，l e g a l 。该方案中 的缺点是没法确定谁是真正的欺诈者。同年b r i c k e l l 乘l s t i s o n 5 4 1 修改t b l a k e y f 3 限方案 从而使诚实的参与者能够识别欺诈者。在该方案中，当一个诚实参与者重构共享的秘密 时，他要对所收到的每一个子秘密进行检查，用来检查出伪造的子秘密。该方案的优点 是可以确保n - 1 个参与者联合起来时只能欺骗一个诚实者，其成功的概率为 ( 刀一r + 1 ) ( 1si - 1 ) ，其中s 为密钥集合。为了使秘密共享方案具有识别欺诈者的功能， 分配给每个参与者的子秘密的长度也随之增加，但是这给保护秘密增加了难度。 b r i c k e l l 和s t i n s o n 方案分配给每个参与者的子秘密多达 + 2 t 一3 个元素，其中每一个 都是有限域的元素。但是当t 和，z 很大时，b r i c k e l l 和s t i s o n 方案不是完备的且不能有 效的实施计算，该方案只适用于，和刀较小的情况。1 9 8 9 年，r a b i n 和b e n - o r 1 2 】构造的秘 密共享体制能使诚实的参与者以一定概率发现欺诈者，但该体制的缺陷是信息率较低， 因此并不常用。 鉴于以上的秘密共享方案都是建立在门限方案的基础上，1 9 9 9 年，p a d r o 等人【l3 j 提 出来基于矢量空间的防欺诈秘密共享方案。该方案主要是针对当参与者授权子集中的若 干参与者联合起来出示伪子秘密欺骗授权子集中的另外一些参与者就能成功非法获得 共享的子秘密这种隐患而提出的。 ( ，疗) f - j 限秘密共享体制也可以应用于等级系统的访问控制。1 9 8 3 年，a k l 和t a y l o r 【1 4 j 首次将密钥和等级系统的访问控制相结合，但他们的方案实现起来较为困难。目前等级 系统中，具有代表性的方案是c h a n g 1 5 】方案。1 9 9 2 年，h a r n 和l i n 1 6 】提出了针对一般访问 结构卜重构秘密共享方案，本方案中每个参与者的子秘密可以重复使用1 次，分别恢复1 个共享秘密。而h a r n 在1 9 9 5 年提出的方案是建立在门限方案的基础上，客服了这个缺点， 参与者可以用同一个子秘密共享任意多个秘密，子秘密可以使用任意多次，此方案的安 全性是基于离散对数的难解性。 另外，( ，玎) f - j 限秘密共享体制还可以应用于数字签名，构成门限数字签名体制。2 0 0 0 年，徐秋亮和郑志华【1 7 】提出了可抵抗恶意参与者进行假“部分签名的门5 艮r s a 签名体 制。 1 3 本文所做的工作 本文的主要工作和创新点如下： 1 绪论硕上论文 ( 1 ) 利用加权门限和m i g n o t t e 列，结合中国剩余定理提出了一个新的秘密共享方案， 该方案解决了目前大部分的加权门限秘密共享方案需要参与者掌握多个子秘密、管理和 传递这些子秘密不安全等缺点。本方案每个参与者只需保存一个私钥，私钥可以重复使 用，简化了密钥的管理和使用，并且利用公告牌避免了秘密信息的传递。秘密分发者可 以很轻易地改变方案秘密信息和门限值，使得方案的管理具有很大的灵活性。由于本方 案的密钥可以重复使用，使得整个方案产生的信息量大大减少，计算复杂度明显降低。 ( 2 ) 对一维可逆细胞自动机做了详细的分析，并且利用其可逆性结合中国剩余定理 提出了一个新的秘密共享方案，该方案将一个秘密信息分解成若干个子秘密，以二进制 文本形式将这些子秘密分别作为可逆细胞自动机的初始配置，演化出秘密共享份额，通 过其反向迭代功能恢复出这些子秘密后进而利用中国剩余定理重构秘密信息。分析结果 表明，该方案构建方法简单，易于实现，且在计算上是安全的。 ( 3 ) 对提出的两个新方案进行了模型实现，运行结果表明，这个两个模型都是正确 可行的，具有较好的安全性，可以根据实际情况加以修改和扩展，可以应用到密码控制 中，具有较好的应用前景。 1 4 论文的结构及内容 本文的组织结构和内容如下： 第一章，介绍了秘密共享体制的研究背景和意义，国内外的研究情况，同时介绍本 文所作的工作以及本文的结构及内容。 第二章，介绍了细胞自动机的定义、表示、分类以及应用。 第三章，介绍了数论的几个知识点以及秘密共享体制几个经典的研究方案。并且利 用加权门限和m i g n o t t e 列，结合中国剩余定理提出了一个新的秘密共享方案，通过计 算证明了该方案是安全的。 第四章，介绍了可逆细胞自动机的基本内容，并给出了实验分析。利用可逆细胞自 动机的特点，结合中国剩余定理，提出一个新的秘密共享方案，通过计算，证明了提出 的方案的安全性是可靠的。 第五章对第三章提出的新方案进行了模型实现，介绍了系统的工作流程，对一些重 要算法给出了运行框图，并且对模型系统的每一个部分都作了较为详细的介绍。 第六章对第四章提出的新方案进行了模型实现，通过例子表明：本方案模型简单， 具有良好的可行性和安全性。 第七章对论文所做的工作进行了总结，明确需要进一步研究的内容，同时对秘密共 享体制的应用前景进行了展望。 硕士论文 秘密共享体制方案的研究与实现 1 5 小结 本章主要介绍了秘密共享方案的一些基本知识，为后面的内容做铺垫。在第2 章中， 将主要详细介绍细胞自动机理论的知识，这是本论文一个重要的知识点，是本文提出新 方案的一个重要理论依据。 2 细胞自动机的基本理论硕上论文 2 细胞自动机的基本理论 细胞自动机( c e ll u l a ra u t o m a t a ，简称c a ) 是最近一个比较热门的研究课题，它是 物理、数学、计算机和生物等学科的交叉产物。在计算机领域中，细胞自动机在人工智 能和加密等多个领域中有着较大的用途。 2 1 细胞自动机的定义 2 1 1 数学定义 下面首先从数学的角度介绍一下细胞自动机，然后给出细胞自动机的概念【1 8 】。 定义1 ：细胞自动机是一个四元组，用数学公式表达就是：c a 2 ( 如，乙，z ( ，) ，b ) ，其 中包括： d l ( 1 ) 空间结构如：如= 兀z j = f = ( 机，f d 一。) if o z o ，f d 一。z n 。- ) i = o d l d 表示维数，其中兀毛= z o x z t 一。为集合z o ，z d 一。的笛卡尔积( c a r t e s i a n t = o p r o d u c t ) ，z n , = o ，l ，j l 为模j 的整数集，f - i o , f i ，i d 1 ) 为细胞单元的结构。 ( 2 ) 状态空间乙：细胞自动机中细胞单元f 的状态取值范围。状态空间一般都是取 z ，因为这样最容易在v l s i 实现。 ( 3 ) 邻域规则函数z ( ，) ：在细胞自动机的邻域半径，= t o , 吒，一。) 里，用来确定第f 个 细胞单元状态。 ( 5 ) 边界条件b ：确定了某个细胞单元f _ f 0 ，f d 一。) 邻域半径之内的邻域单元在超 出细胞自动机空间结构时的处理办法，包括映射边界条件、固定边界条件和循环边界条 件。 在上面的定义的细胞自动机中，最简单的一种是d = 1 ，q = 2 ，= l 的初等细胞自动 机，简称e c a ，是最经常用到的一种。 现在给出有关细胞自动机的两个定义： 定义2 ：所有细胞单元使用相同转换规则为单一细胞自动机或规则细胞自动机。 定义3 ：由两种或两种以上的领域函数规则组成的细胞自动机为混合细胞自动机2 0 1 。 下面按各个知识点更为详细的介绍细胞自动机的基本概念。 2 1 2 细胞与状态 细胞又可称为基元或单元，是细胞自动机的最基本的组成部分。目前研究最多的是 6 t 论文 秘密共享体制方粜的日究b 实现 以0 ，1 为状态集的细胞自动机因为这种细胞自动机比较简单，只有两种状志，可以 很方便的用计算机来模拟。 2 1 3 细胞邻居 细胞自动机中的细胞是分布在细胞空间里的，细胞空间是按几何划分的，理论上， 它可以是任意维数的欧几里德空间规则划分。不过目前为了便于研究主要针对一维和 二维细胞自动机。对于一维细胞自动机，细胞空间的划分就只有一种。而最为常见的二 维细胞自动机，细胞空间可分为三角、四边和六边形三种网格排列。 在一维细胞自动机中，通常是用半径来确定邻居的，距离半径内的所有细胞均被认 为是该细胞的邻居。 二维细胞自动机比较复杂，但通常有以下三种方式，如图21 31 所示： 匪圈髑 ( a ) v o nn e u m a n n 型( b ) m o o r e 型( c ) 扩展的m o o r e 型 图213 1 二维细胞自动机及其邻居( 黑色为细胞，灰色为邻居) ( 1 ) 冯一诺依曼( y o nn e u m a n n ) 型 一个细胞的上、下、左、右相邻的四个细胞为该细胞的邻居。这里邻居半径为l 。 ( 2 ) 摩尔( m o o r e ) 型 一个细胞的上、下、左、右、左上、右上、右下、左下相邻八个元胞为该细胞的邻 居。邻居半径r 同样为1 相当于图像处理中的八邻域、八方向。 ( 3 ) 扩展的摩尔( m o o r e ) 型 将上面所说的邻居半径r 扩展为2 或者更大，即得到扩展的摩尔型邻居。 2 1 4 边界条件 在理论上，细胞空间通常是在并维向l 足无限扩展的，这样会有利于在理论上的推 理和研究。不过在实际应用中，无法在计算机上实现这一理想条件，因此，需要定义不 同的边界条件。一般使用的边界条件主要有三种类型：阁期型、反射型和定值型2 “。 周期型( p e h o d i cb o u n d a r y ) 是指相对边界连接起束的细胞空m 。对于一维空间，细 胞空间表现的形状是一个首尾相接的”圈”。 反射型( b e i l e c t iv eb o u n d a r y ) 指在边界外邻居的细胞状态足以边界为轴的镜面反 射。下图是当r = 1 时的边界情形( 如图21 41 ，黑色表示1 ，白色表示0 ) ： 2 细胞白动机的摹奉理论 硕i ：论文 _ 图2 1 4 。1 采用反射型的一维细胞自动机 定值型( c o n s t a n tb o u n d a r y ) 指所有边界外细胞均取某一固定常量，如o ，1 等。 2 1 5 转换规则 根据细胞当前状态及其邻居状态确定下一时刻该细胞状态的函数，称其为状态转移 函数。一般来说，对于一个系统来说，细胞自动机的演化规则是确定的，细胞自动机会 沿着给定的初始条件沿着相同的路径演化，从而得到相同的演化结果。但是有的时候， 为了更好的模拟自然现象，规则也会发生变化，这种细胞自动机称为混合细胞自动机。 2 1 6 时间 细胞自动机是一个动态系统，它在时间上的变化是离散的，即时间是一个整数值， 而且连续间距。假设时间间距西= l ，若t = 0 为初始时刻，那么，t = 1 为其下一时刻。 在转换函数中，一个细胞的t + l 时刻状态只取决于，时刻的该细胞及其邻居的状态。 2 2 细胞自动机的表示 初等细胞自动机是状态集s 只有两个元素 s l ，s 2 ，即状态个数七= 2 ，邻居半径，= l 的一维细胞自动机，它是最简单的细胞自动机模型。这里最重要的是s 所含的符号个数， 通常将其记为 o ，1 ) 。为了方便起见，将初等细胞自动机的邻域状态配置 s - ，t t ，j 川t ) 的映 射 石= f ( 1 1 1 ) 9 - - - ，彳= f ( o o o ，f o = 厂( 0 0 0 ) ) 的组合a f = - 。z 幸2 称为初等细胞自动机的 规则号。如 石五六五六五石石= 0 1 0 0 11 0 0 ) 对应的规则号为7 6 ，表2 2 1 便是7 6 号初等 细胞自动机的规则映射： 8 硕卜论文秘密共享体制方案的研究与实现 2 3 细胞自动机的分类 表2 2 17 6 号映射规则 tt + l 1 1 1o 1 1 01 1 0 1o 1 0 00 0 111 0 1 0 1 0 0 1o 0 0 00 细胞自动机主要是按动力学和维数分类的，下面分别进行介绍： 2 3 1 动力学分类 8 0 年代初，s w o l f r a m 在基于动力学的行为上，对细胞自动机做出了分类，将所有 的细胞自动机的动力学行为归纳为四大类【2 0 】： ( 1 ) 平稳型：从任何初始状态开始，经过一定时间运行后，细胞空间就会趋于一个平 稳的构形，结构不会随着时间而变化。 ( 2 ) 周期型：经过一定时间运行后，细胞空间趋于一系列简单的固定结构或周期结 构。 ( 3 ) 混沌型： 的非周期行为。 ( 4 ) 复杂型： 2 3 2 维数分类 从任何初始状态开始，经过一定时间运行后，细胞自动机表现出混沌 出现复杂的局部结构，或者说是局部的混沌，其中有些会不断地传播。 理论上来说，细胞自动机可以是任意维数的，细胞自动机可以分为以下几类1 2 l 】： ( 1 ) 一维细胞自动机：细胞按等间隔方式分布在一条向两侧无限延伸的直线上，每个 细胞具有有限个状态s ，s s = “，是9o ，s k ) ，定义邻居半径，细胞的左右两侧共有2 ， 个细胞作为其邻居集合n ，转换函数f ：s 2 h 1 专s 可以记为： 譬”= 厂( s 2 ，s 2 l ，s 2 ，殴，) s ! 为第f 个细胞在，时刻的状态。称上述a = s ，n ，f ) 三元组( 维数d = 1 ) 为一维细胞自动 9 2 细胞自动机的基奉理论硕十论文 机。 ( 2 ) 二维细胞自动机：细胞分布在二维欧几里德平面上规则划分的网格点上，通常为 方格划分。 ( 3 ) 高维细胞自动机：只是在理论上进行少量的探讨，实际的系统模型较少。 2 4 细胞自动机的研究现状 利用细胞自动机实现数据加密最早始于w o l f r a m 2 4 j ，在1 9 8 5 年美洲密码学年会上， 他首次提出了将细胞自动机的初始状态作为密钥，使用规则3 0 细胞自动机前向迭代产 生的伪随机序列作为密钥流，从而开创了细胞自动机在密码学中的应用研究，但是，该 方法的缺陷是不能保证产生伪随机序列的周期特性。 1 9 8 9 年，h o r t e n s i u s 等人使用非一致细胞自动机做随机数生成器，他的思想是在 细胞自动演化的不同时刻，不同的演化规则可以作用在同一细胞上【2 引。同一年，p e t e r d h o r t e n s i u s 提出了用规则3 0 和规则4 5 组成的可编程细胞自动机构造具有i l l 序列特性 的伪随机序列【2 6 1 ，该方法产生的伪随机序列具有很强的相关性。1 9 9 4 年，s n a n d i 提出 使用g f ( 2 ) 上的可编程细胞自动机和存储单元来产生伪随机序列口”。1 9 9 7 年，d o l o r e s 等提出了一种使用线性移位寄存器来控制每个时刻细胞自动机迭代次数的伪随机序列 产生方法，以提高产生伪随机序列的线性复杂度和周期1 2 引。m d a s c a l u 等在w 0 1 f r a m 方 法的基础上加入存储单元来减少细胞自动机过早地进入配置循环【2 9 1 ，但是该方案同样不 能保证产生伪随机序列的周期特性。1 9 9 8 年，m i o d r a gm i h a l j e v i c 等提出在g f ( q ) 上使 用线性可编程细胞自动机的前向迭代产生伪随机序列的方法【3 0 1 ，并于1 9 9 9 年提出了在 g f ( q ) 上使用线性可编程细胞自动机的前向迭代产生伪随机序列的方法【3 1 1 。 1 9 9 5 年，b s r i s u c h i n w o n g 等人提出将非线性细胞自动机应用于f e i s t e l 型密码中 的非线性函数，并将另一个线性细胞自动机作为每一分组数据的加密密钥的方法【3 3 1 。 1 9 9 6 年，0 l a f e 首次提出基于细胞自动机变换的概念p 4 儿3 5 j 。2 0 0 2 年，张传武提出了一 种基于具有多项式的9 0 1 5 0 加性细胞自动机的输入边乔可逆细胞自动机对称密码模型 1 3 6 0 虽然基于细胞自动机的密码算法的安全性还有待于检验，同时期作为一个完整的密 码算法实现还处于探索阶段，但是细胞自动机作为密码系统中的一个构件模块是具有很 好的前途的。 本文利用细胞自动机的局部相互作用的规则的特点，如具有离散性、同质性、局部 性和并行性等特点，提出了一个新的秘密共享方案，该方案主要利用了细胞自动机中的 一类特殊的细胞自动机一可逆细胞自动机。 l o 硕士论文秘密共享体制方案的研究与实现 2 5 小结 细胞自动机是由一些简单的局部相互作用的规则来驱动整个系统的进行演化的，具 有离散性、同质性、局部性和并行性等基本属性。目前，细胞自动机的理论得到了快速 地发展，其应用前景日趋成熟。本文在研究细胞自动机的理论的基础上，提出了一种基 于可逆细胞自动机的秘密共享方案，该方案结合可逆细胞自动机的一些特点和优点，具 有一定的发展前景。方案的具体内容在第4 章中详细叙述。 3 基于加权门限和m i g n o t t e 列的秘密共享方案硕十论文 3 基于加权门限和m i g n o t t e 列的秘密共享方案 在本章里，利用加权门限和m i g n o t t e 歹0 ，结合中国剩余定理提出了一个新的秘密共 享方案。 3 1 数论基础知识 在本节中，将对在秘密共享体制中所需要的必要的数学基础进行简单的整理和介 绍，以便能清楚地了解秘密共享体制中的工作原理及如何分析与证明其安全性。 3 1 1 同余及模的运算 定义3 1 同余令三个整数口，b 及m 0 ，称口在模m 时与b 同余，当且仅当a 与b 的 差为m 的整数倍，即口一b = o n ，其中k 为任意整数若口与b 同余，记做口三bm o d m ， m 被称为这个同余式的模。 定理3 1 模m 的同余关系满足 ( 1 ) 自反性：即口兰a m o d m 。 ( 2 ) 对称性：即若口兰b m o d m ，则b 暑a m o d m 。 ( 3 ) 传递性：即若口三b m o d m ，b 兰c m o dm ，则口兰c m o dm 。 定理3 2 若a c 三b c r o o d m ，且c 和m 互素，则窃三b m o d m 。 定义3 2 若a b 暑1m o d m ，则称b 为口在模m 下的乘法逆元，b 可表示为口。 3 1 2 乘法逆元的求法 已知口及m 且( 6 , m ) = 1 ，需要求出口一满足锻。主1 m o d m 是经常出现的问题。 方法：若缈( 聊) 已知，则由欧拉定理可知绷妒”兰1 m o d m 。因此有口伊”一1 三口一m o d m 。 3 1 3 中国剩余定理 中国剩余定理( c h i n e s er e m a i n d e rt h e o r e m ，c r t ) 是约公元前1 0 0 年时有中国数学 家孙子发现的，故也称为孙子定理，它是数论中最有用的定理之一。 k 定理l ：( 中国剩余定理) 设嘲，m ：，m k 是两两互素的正整数，m = 兀m l ，则一次同 l = l 余方程组 q ( m o d 码) 兰s 6 2 ( m o d m 2 ) 兰j 吼( m o d m k ) 三s 硕- 上论文秘密共享体制方案的研究与实现 对模肘有唯一解： j 兰( 丝巳q + 丝吃呸+ + 丝吼d m ) a k ) ( m o dj 兰( 一巳q + 吃呸+ + 吼 、i i hi k 其中q 满足丝q 兰l ( m o d m t ) ( f _ 1 ，2 ，后) 。 h i l 3 2 门限秘密共享典型方案研究 3 2 1 传统秘密共享 传统秘密共享主要分为以下两种： ( 1 ) l a g r a n g e 插值多项式方案【1 】： s h a m i r 币u 用有限域中的多项式方程来构造门限方案，选择一个大素数p ，使之比可 能的最大子秘密数目和可能的最大秘密都大。共享秘密时，随机产生一个次数为m 一1 的 多项式。例如：要形成一个( 3 ，门) f - j 限方案( 恢复m 需要3 个子秘密) ，则产生一个二次多 项式f ( x ) ： f ( x ) = ( a x 2 + b x + m ) m o d p ( 3 1 ) 其中p 是一个比所有系数都大的随机素数，且p 公开，系数a 和b 为秘密随机整数， 在分发完子秘密后就丢掉，m 是消息。其中秘密份额缸是可以通过计算多项式( 3 1 ) 在 几个不同点上的值得到： 毛= 厂( ) 第一个份额取多项式( 3 1 ) 在x = 1 处的值，第二个份额取多项式( 3 1 ) 在x = 2 处的值，以 此类推。由于多项式( 3 1 ) 有3 个未知系数口，b ，m ，因此任意3 个或3 个以上的份额就能够 求解出未知系数，即恢复消息m 。若份额数少于3 个则不能恢复。 ( 2 ) a s m u t h - b l o o m 方案 对一个( f ，刀) 门限秘密共享方案方案，选择大素数p ，使得p 大于消息m 。选择刀个 小于p 的数m l ，m 2 ，m n 满足以下条件： ( 1 ) m ，的值按递增顺序排列，即鸭 p x ，一册+ 2 m n m + 3 m h ； 当分配秘密份额时，选择一个随机数r ，计算： m = f + 印 然会计算份额惫： t = mm o d m , 3 基于加权门限和m i g n o t t e 列的秘密共享方案 硕十论文 由中国剩余定理可知，由任意f 个或f 个以上的份额能够恢复m ，少于，个份额则不 能恢复l i j 。 3 2 2 多秘密共享 下面介绍两个比较具有代表性的方案： ( 1 ) c h a n g 等人提出的多秘密共享方案1 3 7 】 2 0 0 5 年，c h a n g 等人针对文献【3 8 1 和【3 9 1 两种多秘密共享方案的不足之处，提出来一个 新的改进方案，方案具体内容如下： 定义f ( x ) 为任意单向函数，其中厂o ( x ) = x ，f ( x ) = f ( f 扣1 ( x ) ) 。 分发者d 选择不同的数x ，其中f - 1 ，2 ，n ，分别作为n 个成员的公开信息，然后d 执行以下步骤分发秘密： 1 随机选择m ，儿，此作为秘密份额。 2 构造t - 1 次多项式最( x ) ，其中e ( o ) = 。 3 计算z 白= p 。( x j ) 和九= z 旬o f ( y ，) ，其中j = 1 ，2 ，行。 4 对扛k 一1 ，k 一2 ，1 ，执行以下步骤： ( a ) 构建一个t 一1 次多项式p ( x ) ，其中? ( o ) = 量。 ( b ) 计算z j ，= ( x ，) 和吒= 乙o 。( y j ) o s i + 1 ，其中j = 1 ，2 ，刀。 5 通过安全信道分发只给成员并且公布z ，其中f = 1 ，2 ，k ，j = 1 ，2 ，刀。 秘密恢复阶段，每个成员首先提交厂。( y ，) 并按照以下公式恢复秘密： = 最( o ) = 主( 广( 儿) 。叱) 血兰 ( 3 6 ) a = l b = l ，6 口 口 6 然后各个成员按顺序提交厂扣1 ( 少，) ，f 卜2 ( j ，) ，f 1 ( y ，) ，按顺序依次恢复秘密s i ： i 州0 ) _ 善t ( 八此州挑+ 。瓢t 。i 0 - ( 3 7 ) 该方案利用单向函数来实现多个信息的共享。该改进方案可以重复使用子密钥。 ( 2 ) s h a o 等人的可验证多秘密共享方案【4 0 】 方案具体内容女n - f ：f ( r ，s ) 是一个单向函数，鼻，尸：，只是需要共享的秘密信息。 p 是一个安全素数，q 是大素数hq i ( p - 1 ) ，g 是g f ( q ) 上的q 阶本原元。d 选择甩个