（基础数学专业论文）基于代数几何的可公开验证的多密钥共享方案.pdf

m a s t e rd i s s e n a t i o no f2 01 1s c h o o lc o d e ：1 0 2 6 9 a c a d e i i l i cn u i n b e r ：510 8 0 6 010 2 2 e a s tc h i n an o r m a lu n i v e r s i t y a na l g e b r a i c g e o m e t r i cp u b i - c i yv e r i f i a b l e m u l t i s e c r e ts h a r i n gs c h e m e d e p a r 佃舭 m 句o c s u b j e c t ： s u p e r v i s o r ： m a l e n l a t i c s f i l r em a m e m a d c s a s s o c i a t ep r o f e s s o r l gs i m 弛 m a s 衙c 锄m d a t e ：j ij u i d i 2 0 1 1 4 华东师范大学学位论文原创性声明 郑重声明：本人呈交的 案，是在华东师范大学攻 基于代数几何的可公开验证的多密钥共享方 士( 请勾选) 学位期间，在导师的指导下进行 的研究工作及取得的研究成果。除文中已经注明引用的内容外，本论文不包含其他 个人已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均 已在文中作了明确说明并表示谢意。 作者签名：毒雾砀 日期：加，r 华东师范大学学位论文著作权使用声明 7 基于代数几何的可公开验j 芷的多密钥共享方案系本人在华东师范大学攻读学 位期间在导师指导下完成的硕幻博士( 请勾选) 学位论文，本论文的研究成果归华 东师范大学所有。本人同意华东师范大学根据相关规定保留和使用此学位论文，并 向主管部门和相关机构如国家图书馆、中信所和“知网 送交学位论文的印刷版和 电子版：允许学位论文进入华东师范大学图书馆及数据库被查阅、借阅；同意学校 将学位论文加入全国博士、硕士学位论文共建单位数据库进行检索，将学位论文的 标题和摘要汇编出版，采用影印、缩印或者其它方式合理复制学位论文。 定的“内部”或“涉密”学位论文，于 权。 导师签名：般本人鼢杰蟊西 期：印f ，谭 ”涉密”学位论文应是已经华东师范大学学位评定委员会办公室或保密委员会审定过的学位 论文( 需附获批的华东师范大学研究生申请学位论文”涉密”审批表方为有效) ，未经上 述部门审定的学位论文均为公开学位论文此声明栏不填写的，默认为公开学位论文，均适 用上述授权) 。 专磊陶硕士学位论文答辩委员会成员名单 姓名职称单位备注 寺凝叭讪锄梭锋奇、- 1 仰和欠垮 主席 璺郫位猛袭强辟昏1 l 帝轮夫学 刻移圉勃嘏缉7 i 、 1 阳乳天荡 华东师范大学基于代数几何的可公开验证的多密钥共享方案 摘要 1 9 7 9 年，s h 锄1 i r 和b l a l d 盯各自独立地提出了密钥共享的概念在已知的密钥共享 方案中，绝大多数方案假定密钥分发者和参与者集都是诚实的然而，在实际共享过程 中，密钥分发者和参与者集中的部分人可能作假针对防欺骗性问题，c 抽r g o l d w 雒s m i c a l i 和a w e r l m c h 于1 9 8 5 年提出了可验证密钥共享的概念值得注意的是，陈豪和 q 锄e r 在2 6 美密会议上首次提出了基于代数几何的密钥共享方案 本文利用代数曲线上的有理点构造了一种新的公开可验证多密钥门限方案利用 椭圆曲线上修正w 醯对性质，新方案可以有效检测出来自密钥分发者或参与者的欺 诈方案的安全性基于解椭圆曲线离散对数问题的困难性相比基于离散对数问题的 密钥共享方案，对于大致相同的安全强度，新方案使用较小的椭圆曲线群，好处是密钥 更短，减少了存储空间和传输量 关键词：多密钥共享：公开可验证；门限方案；代数曲线；修正肌订对 i 华东师范大学 基于代数几何的可公开验证的多密钥共享方案 a b s t r a c t s c c f c ts h 曲gw 弱r s tp r o p o s c d i n d c p c n d c n 廿yb ys l l a m i r 卸db l a l 【l c yi i l1 9 7 9 h im o s t l m a 舳s c h e m e s b o t h 血c d c a l 盱柚d t t l ep l a ) 懈a 坞s u p p o s e d t 0b e h o n e s lh 鲫e v 瓯i n 砌 w 0 订d i t i sc a 嘣：c i ：、，j l b l e t h 砒s 黜o f t l l 锄m i g h ta t 咖p t t o c h e a t t 0 a c h i ms e c 咖a g a i n s t c h 谢n gp l a y e 璐d e a l l cc c c 耻0 fv c 衲a b l es c 硎s h a 血g ( v s s ) w 丛i 眦e di n 1 9 8 5 b y q 峨g m d w 硒s 糊蠲d a w e r t m c h h a 疆p 1 0 2 0 0 6 ，o a n d c 瑚m 盯p 胁 p o s c d 吐l cf 汹t 础s n gs c h e m cb 嬲c d a l 誉j 嘲cg m 唧 ht h i st 1 1 c s i s ，w cc o n s 协k tan e wp i l _ b l i c l yv c 时a b l c 删t i - s c c r e tm 陀s h o l ds c h 黜璐i i l g a l g e _ b r a i cc 断髑w i 血m a n y 础a lp o i n t s t h c 卸蛐a 6 i sp e ：晌衄硝b y 锄p ：l o y i n g 圮m o d i 靠c dw - c i lp a i r i n go nc m 砸ca l n ，c st 0p r e v c n tp o s s i b l cc h c a t i i l g0 fb 0 山d c a l c 璐a n d p a r t i c i p 趾协t h es 仪咖0 f 饥s c h 黜i sb 雒e d t h ed i 伍c l i 时t 0s o l v et h ec i h p 血c i 阶，e d i s 删el o g 缸i n 皿p 惦b l e 札。咖叩a r i n gw i t h 也cs 曲岫c sb 勰e d d i s 眦1 0 9 龇p r o b - l c 甄f 研t h es 锄ek ，c l0 fs 黜r i 劬o s c h 黜锄p 1 0 y sa 咖l c h 皿i a l ：蛔雌湖e 哪 ma 埘撕v cs m a l l 盯蛔l 即班w h i c h d u c c st h es t c 腿g c 锄d 昀璐m i s s i r e q l l i 】舶e n t s k e y 啊r 盯凼： m u l m s r e ts h a 血g ； p u b h c l yv e r i f f c 撕；t h i s h o l d h 曲；a i g c _ b r a i c 华东师范大学 基于代数几何的可公开验证的多密钥共享方案 目录 第一章概述1 1 1 引言1 1 2 本文的主要研究内容2 1 3 论文的组织结构3 第二章基本概念和基础理论4 2 1 密钥共享基本理论4 2 2 代数函数域基本理论6 2 3 代数曲线与代数函数域1 l 2 4 代数几何码基本理论1 1 2 5 有限域上椭圆曲线基本理论1 4 第三章密钥共享方案的相关研究1 9 3 1 s h 跚】i r 的他帕门限密钥共享方案1 9 3 2 t 0 m p a 和w b u 攻击方案2 0 3 3 代数几何密钥共享方案2 l 3 4h 锄可验证多密钥共享方案2 4 第四章一种新的线性门限多密钥共享方案2 8 4 1 初始化阶段2 8 4 2 子密钥的分配阶段2 8 4 3 主密钥的重构阶段3 1 4 4 代数曲线上点的存在性证明3 3 第五章总结3 5 参考文献3 7 致谢4 l 1 1 引言 第一章前言 1 9 7 9 年，s h 锄】i r 【2 3 】和b l a l d e y 【2 】各自独立提出了密钥共享的概念由于密钥共 享可以大大地增加主密钥j 的安全性及可靠性，密钥共享引起了人们广泛关注这是因 为如果主密钥占仅存入一个个体( 人或计算机等) s 有可能失窃且易被记错或抹去密 钥共享有效克服了上述缺点，为密钥管理提供了一个崭新的思路 s h 锄i r 的( 七 力门限密钥共享方案基于i a g 明n g c 插值多项式。而b l a l d 昭的方案 基于摄影几何从那以后，基于代数或几何结构的各种密钥共享方案被逐一提出他们 大多是s h 锄1 i r 和b l a l d 呵方案的变形 大多数已提出的密钥共享方案是线性的他们有一个共同的特点是主密钥的 重构是通过求解线性方程组实现但线性密钥共享方案( l s s s ) 的一般化概念 由眦h 嘲和w i g d e 璐饥【1 7 】以单调张成方案( m o n 锄cs p 缸p r o g r 扰塔( m s p ) ) 的 等价语言第一次提出1 9 9 6 年，b c i l n c l 【1 】给出一般的线性密钥共享方案的数学模型并 建立了l s s s 与m s p 的对应关系 2 0 世纪如年代起，人们发现代数曲线上的代数结构可用于构造某些精美结果在 密钥共享领域，陈豪和c r 锄盯【7 】将代数几何技术用于构造了定义在有限域玛上缺 口( g a p ) 为2 9 的呻密钥共享方案( 代数几何密钥共享方案) 当g = 0 时，此方案便 退化成门限密钥共享方案对于大致同样多的参与者，代数几何密钥共享方案可以定义 在一个相对远远小的有限域上，使得参与者人数不受密钥共享方案的定义域的大小限 制( 远超过定义域的大小) 另一方面，s 蛐【2 3 】和b l a l d 呵【2 】提出密钥共享后不久，m c e l i e 和s 野 w 眦【2 1 】于1 9 8 1 年提出了密钥共享的防欺骗问题因为在共享中，受信道噪音干 扰或部分参与者不良企图影响，合成人可能接收到部分伪子密钥，导致重构出的主密 钥是一个伪主密钥为此，他们利用纠错码理论构造了一种陬帕门限密钥共享方案， 使得最多含有p 个欺骗者的艿( _ 七+ 幻) 个参与者能够正确地恢复出主密钥此后。 1 华东师范大学 基于代数几何的可公开验证的多密钥共享方案 i 0 m p a 和w b u 【2 8 】于1 9 8 8 年基于s h 锄l i r 的限n ) 方案给出了一种潜在的攻击情形 他们指出重构时七个有效参与者中即便只有一个不诚实的参与者，这个不诚实参与者 也能以很大的几率成功地欺骗其余七一1 个参与者 针对防欺骗性问题，c h o r 等人【1 1 】于1 9 8 5 年提出了可验证密钥共享的概念可验 证密钥共享通过验证解决防欺骗问题，具有良好的安全性质，它在安全多方计算中具有 重要应用可验证密钥共享保证即便出现密钥分发者欺骗，参与者也能恢复出真实的 主密钥值得注意的是，在c h o r 等人的方案中，不仅密钥持有人可以验证密钥分发者 分配子密钥的有效性，其他任何人都可以验证密钥分发者分配子密钥的一致性、有效 性以及有效参与者出示的子密钥的真实性 针对同一组人要共享多个主密钥，而且不同的主密钥对应不同的密钥共享要求的 问题，产生了多密钥共享的概念多密钥共享研究的主要内容是密钥分发者如何安全 且有效地共享多个密钥在几乎所有已知的密钥共享方案中，参与者拥有的子密钥仅 能使用一次故这些方案都是一次性方案但对多密钥共享方案来讲，子密钥应能多次 使用虽然已有一些多密钥共享方案的研究【1 6 】，【3 】。【3 l 】【4 】然而，这些方案不能消除 密钥分发者和参与者的欺骗1 9 9 5 年，h 锄【1 4 】基于离散对数问题成功地提出了一种 计算上安全的( 七 万) 门限可验证多密钥共享方案能同时防止密钥分发者与参与者的欺 诈在h 锄的方案中，密钥分发者给每一个参与者分配一个子密钥，参与者再利用这个 子密钥计算其副子密钥作为私钥发送给合成人这样即使泄露了副子密钥，敌手也不 能获知真正的子密钥，进而保障了子密钥的安全性 1 2 本文的主要研究内容 本文受h 锄的方案的启发，构造了一种新的线性门限多密钥共享方案在文 献【1 4 】中，h 锄基于b g r a n g c 差值多项式提出的多密钥分享方案在子密钥生成、分 配和主密钥合成方面具有极高的安全性和有效性他将每个主密钥的重构问题转化为 重构有限域中的一个值( 密钥分发者选定的h 舯n g c 差值多项式的常数项) 的问题在 新方案中，我用r i 锄衄r ( ，c h 空间的有理多项式取代ia g r a n g e 差值多项式构造多密 钥共享方案，将每个主密钥的重构问题转化为重构r i 舢r 0 c h 空间中一个点的问 题，旨在构造安全且高效的新多密钥代数几何共享方案新方案是一个可验证门限方 案方案的安全性基于解椭圆曲线离散对数问题的困难性相比方案【1 4 】，【1 3 】，对于大 致相同的安全强度，新方案使用的密钥较短，带来的好处是减少了计算量和存储空间、 加快了运算速度、提高了处理能力此外，通过利用修正的w 日对的部分性质和结论， 2 华东师范大学 基于代数几何的可公开验证的多密钥共享方案 新方案可以有效检测出来自密钥分发者或参与者的欺诈 1 3 论文的组织结构 本文各章内容和结构安排如下： 第一章：介绍密钥共享的部分研究进展，在此基础上，提出本文的研究内容和组织 安排 第二章：介绍本文需要用到的一些密码学、数学基础知识 第三张：具体介绍密钥共享方案的部分研究成果 第四章：提出一种新的基于代数几何的可公开验证的多密钥共享方案 第五章：对本文提出的新方案进行总结 3 第二章基本概念和基础理论 本章分四个部分。主要介绍论文用到的基础知识第一节介绍密钥共享基本理论， 第二节介绍代数函数域基本理论，第三节介绍代数曲线与代数函数域的关系，第四节介 绍代数几何码基本理论，第五节介绍椭圆曲线基本理论 2 1密钥共享基本理论 本节介绍密钥共享的基本概念和理论详细知识参见【3 2 】，【2 5 】 令p = p i ，p 2 ，r l 是n 个密钥共享参与者的集合称参与者的集合p 中实际 参与密钥共享的参与者毋l 一，p l l 伽帕为有效参与者设有限集s 是主密钥空间， s l ，s 矗分别为参与者p l 一， 的子密钥空间 定义2 1 ( 存取结构) r 2 ，是2 ，的一个非空子集，其中，2 p 表示p 的全部子集构成 的集合称r 是p 上的存取结构，如果集合r 满足单调性：若集合aer 则对任意集 合a ，2 ，且a a ，有r 定义2 2 ( 授权集和非授权集) 若r 是p 上的存取结构，则r 中的任何集合称为p 上的 授权集；对于2 ，r 中任何集合，即不属于r 的p 的任何子集，称为p 上的非授权集 只有授权集才能恢复主密钥，任何非授权集不能重构主密钥 在密钥共享方案中，密钥分发者p o 薯p 拥有一个主密钥j s 为了使参与者 p l ，p 2 ，只共享主密钥文密钥分发者首先利用子密钥分配算法：s j l 口陀( 力= ( j l ，而) 计算参与者p i 的子密钥毋，然后秘密地将子密钥& 分配给参与者p i ( f = l ，n ) ( 这 可通过一个秘密安全信道传输完成，只不得向任何人泄露子密钥毋) 若一组有效参 与者b l 一，吒伽s 刀) 希望重构主密钥，他们分别向密钥合成人( 即主密钥重构算 4 华东师范大学 基于代数几何的可公开验证的多密钥共享方案 法) 递交各自的子密钥记a = p l l 一，p i _ ( m n ) ) 主密钥重构算法具有以下性质： 1 对于任何aer ：砒c d w “ 毋lfea d = j ； 2 对于任何曰岳r 由 毋if 两无法计算出主密钥& 以下给出一般密钥共享方案的数学定义： 定义2 3 ( 一般密钥共享方案) 只r ，s ，s l ，s 。同上只是随机输入有限集合映 射万：s r _ s i s 。将任意给定的主密钥墨s 和随机输入r 灭映射 为瓜sr ) = ( 墨l ，而) ，其中毋s “1 i 玑通常称丌为分配函数或分配算法，若分配 函数万满足： 1 重构要求：对于任何aer ，郴i s ) = 0 这里日( - ) 是熵函数s 表示a 中成员的 子密钥 2 安全性要求：对于任何丑2 ，r o 0 称p 为工的极点当且仅当y p o ，则p 为了的m 阶零点如果y ，= 一m 0 ，则p 为工的m 阶极点 定义2 1 4 ( 主除子) 设o 工，定义j 的零点除子。极点除子和主除子如下： 11 ( 确：= 芝_ ：y 户只。：= 芝：( 一y ，) 只曲：= o 毗一。 只，倒l 咖o 只印o 瑚 显然( 】c ) o 0 ，( 】0 。0 且d = y p ( 习p ， 可以证明咖) = 0 ( 即石的零点与极点个数相同) 定义2 1 5 ( 除子间的等价) 任意d l ，d ied ，除子问的等价表示为d l 。d 2 d l 。d 2 当 且仅当存在某个工p 使得d l d 2 = 挑 定义2 1 6 ( 线性系) 除子d 的线性系，就是指和除子d 线性等价的所有有效除子构成 的集合，记作idi 定义2 1 7 ( 基点) 点p p ，称为线性系idi 的基点，若z ( d 一乃= z ( d ) 8 华东师范大学 基于代数几何的可公开验证的多密钥共享方案 下面介绍函数域理论中的重要定义 定义2 1 8 ( m 锄删咂r ) c h 空间) 对任意a 所，定义a 的m 渊- r o c h 空间为 z ( a ) = ，：西如+ a o lui o ) 命题2 1 对黜舢r ( c h 空间，有以下结论： 1 石z 似) 当且仅当对所有的p p ，有印( 力一y p ( a ) 2 任意a d ，z ) 为k 上的向量空间记z ( a ) 的维数为z ( a ) 3 对任意d l d 2 z ) ，若d lsd 2 ，则以d 1 ) z ( d 2 ) 从而z 1 ) 故d 2 ) 4 z ( 0 ) = 墨z ( 0 ) = 1 5 ae d ， 当c 跆g r a 幻一2 ，则咖( w a ) 0 所以“一a ) = o ，从而z 似) = 出弘+ l g 1 0 华东师范大学基于代数几何的可公开验证的多密钥共享方案 2 3代数曲线与代数函数域 定义2 1 9 ( 射影簇) 子集ycp i 称为射影代数集，如果存在其次多项式子集 m k 隅，墨，墨】使得y = p p i ：，( 竹= 0 ，对所有的fem 射影代数集 y p | i 称为不可约的，如果它不能表示成y = u 耽，其中n 和班为y 的真子代数 集射影簇是指不可约射影代数集y p 1 定义2 2 0 ( 代数曲线) 射影代数曲线y 是指一维射影簇即，y 的有理函数域取v ) 为一 元代数函数域 定义2 2 l ( 非奇异代数曲线) 点p y 称为非奇异点。如果局部环d p ( 功是离散赋值环 ( 即，0 p ( n 为具有唯一非零极大理想的主理想整环) 代数曲线y 称为非奇异的( 即光 滑的) ，如果所有点p y 都是非奇异点 设州足为一元代数函数域，则存在非奇异射影代数曲线e 它的有理函数域为e 设y 为非奇异射影代数曲线且，= 甄功为它的函数域则曲线上的点p y 与函数 域上的位存在一一对应关系p 卜肘- ( ，其中 知( 为局部环c i ，( v ) 的极大理想由 此，函数域上的定义和结论都可以转化到代数曲线上例如： 1 曲线y 的亏格即为函数域置( 功的亏格 2 曲线y 的除子为和式d = 万p p 其中却z 且几乎所有的万p = 0 d 的次数为 咖d = 万p 曲线y 上的除子形成加法群d ( ”，即y 的除子群 j ，e y 3 有理函数，在点p y 的阶定义为印( 其中印为函数域以功的离散赋值) 4 有理函数0 ，甄y ) 的主除子d 如= y ，p 主除子的次数为0 e y 2 4 代数几何码基本理论 陈豪和c 船m 盯【7 】基于代数几何码提出了代数几何密钥共享方案本节主要介绍 纠错码理论的基本概念和代数几何码的构造，详细知识参见【2 6 】，【2 9 】 华东师范大学 基于代数几何的可公开验证的多密钥共享方案 定义2 2 2 ( 码) 设n 为正整数，a 为非空有限集合码定义为a 的任意非空子集c 其中：= ( 口l ，口2 ，嘞) ：毋a ，l fs 以1 c 中的元素称为码字，再称为码长， 膨：= ici 称为码c 的个数 定义2 2 3 ( 线性码) 设喝为具有g 个元素的有限域当a = 玛且码c 巧为线性子空 间时，c 称为线性码此时称姗为码c 的维数 定义2 2 4 ( 码的最小距离) 任意口= ( 口l ，口2 ，锄) ，6 = ( 6 l ，如，巩) a ，定义 讹，：= l “ 1 ，2 ，万l ：嘞阢 l ， d 称为上的m 吼m i n g 距离元素口a 矗的重量定义为 w 如) ：= d ( 口，0 ) = i f 1 ，2 ，刀l ：q o li 非零码c 的最小距离政c ) 定义为 d ( c ) ：= m 拥 d ( 口，：口，6ec 巨口6 1 因为撒，功= m 一易，o ) = w l 如一功，所以当c 为线性码时，d ( o ：= 舢流 w f ( c ) ：0 c ec ) 定义2 2 5 ( ，m 回码和哳，毛d 】码) 伽，尬d ) 码是指具有码长为码字个数为眠最小 距离为d 的码作为线性码，陬，毛明码是指具有码长为维数为七，最小距离为d 的码 华东师范大学基于代数几何的可公开验证的多密钥共享方案 证明：考虑映射妒：z ( g ) _ 圪，厂卜抓p 1 ) ，( p 2 ) ，八r ) ) 则y p l 一( g ) = 0 所以只不是有理函数，的极点且八p 1 ) e 岛从而抓p 1 ) ，八p 2 ) ，八r ) ) 吃， 映射定义合理易知妒是向量空间的巴一线性映射而c 2 ( d ，g ) 是映射妒的像 加( 劝所以q ( d ，回为线性码c 2 ( d ，g ) 的维数七等于z ( g ) 的维数z ( g ) 减去核 妇删= 仃z ( g ) i 叭p 1 ) ，( p 2 ) ，( 一) ) = ( o 0 ，0 ) ) 的维数下面确定妇，( 劝 对于任意的，e 妇咖) 有厂( p i ) = 0 ( 1 f 刀) 即只( 1 f 哟都是，的零点所以 ，z ( g p l 一r ) = 以g d ) 从而妇，( d 以g d ) 另一方面，z ( g d ) 妇删 显然成立所以以g d ) = 妇“访，七= 故g ) 一姬一d ) 现在证明d 万一如g g 如果d 万一如g g l ，则存在非零码字u 妒1 ) ，( p 2 ) ，八r ) ) 使得州叭p 1 ) ，八p 2 ) ，八r ) ) ) = d 刀一咖g 一1 所以帆p 1 ) ，( p 2 ) ，八只) ) 至 少有如够+ 1 个分量) 为零不妨设，( p 1 ) = = 八p r ) = 0 ，r = 如g g + 1 则 ，ez ( g d ，) ，其中d ，= p l + + p r 但如g ( g d ，) = 如妒一，= 一1 0 ，颤g d ，) = 0 于是，= 0 ，这和抓p i ) ，八p 2 ) ，八 ) ) 是非零码字的假设矛盾因此d 之一一咖g 推论2 1 若出孵 2 9 一2 ， 则七= 西铝r g 一富+ 1 证明：若如妒 n ，则如g ( g d ) 2 9 一2 ，设w 为硒锄a 加一r 0 c h 定理中的典范除子，则咖( w g ) 0 ， z ( w g ) = o 于是七= 榔一g + 1 下面介绍另一种代数几何码( 几何g o p p a 码) 的定义 定义2 2 7 除子d ，g 的定义同上c 2 ( d ，g ) 的对偶码几何g o p p a 码c n ( d ，g ) 嵋定 义为 ( d ，g ) ：= 伪，正，五) e 巧：五妒( p i ) = o ，对于任意妒e 段d ) 1 i ；l 定理2 3c n ( d ，g ) 为【以，f ，们缌巨码且f = 忍一炳) + 郴一d ) ，如酊一( 2 9 一2 ) 证明：因为c n ，g ) 是q ( d ，g ) 的对偶码，所以d f m c q ( d ，g ) + 踟q ( d ，g ) = n 由 定理2 2 七= 幽峨( d ，g ) = z ( d 一媚一d ) 知= ( d ，g ) = n z ( g ) + 故g d ) 1 3 华东师范大学基于代数几何的可公开验证的多密钥共享方案 现在证明咖g 一( 2 9 一2 ) 如果 d 印一( 幻一2 ) 则存在非零码字 c ，= ( c l ，c 2 ，靠) ( d ，g ) 使得研) = 必g 一p i ) 所以存在 妒z ( g 一只+ 乃) z ( g 一p f ) z ( g ) 使得妒假) = 0 ( 对任意f d 且妒( 乃) 0 由 c n ( d ，g ) 定义，可得c l 认p 1 ) + + 岛驴( r ) = 0 若f c o 且f 工则烈只) = 0 ；若f 隹c o ， 则c l = o 所以前面的式子可化简为勺烈日) = 0 考虑到j c o 幻0 ) ，烈乃) = 0 这与 烈p ，) 0 矛盾所以矿如孵一( 2 9 一2 ) 推论2 2 若咖g 2 9 一2 ，则f n + g 一1 一出妒进一步，若n 如g g 2 9 一2 ，则 f = n + g l d e 孵 证明：f = 万一z ( g ) + 必g d ) 万一悯当抛g 2 9 一2 时，咖( 一g ) 咖g 2 9 一2 时， 衄( g d ) = 如孵一刀 3 是素数，g = 矿，r 为一正整数域上的椭圆曲线 e 叽) 由下述方程 于= p + 4 x + b 所确定的曲线加上一个无穷远点d 组成其中口，6 匕是满足材+ 2 7 垆o 的常量 点d 是曲线的惟一的一个无穷远点条件订+ 2 7 垆o 确保椭圆曲线是“光滑 的即非奇异的，即曲线的所有点都没有两个或两个以上不同的切线 椭圆曲线上的点按加法构成a b d 群点的加法定义如下： 1 4 华东师范大学基于代数几何的可公开验证的多密钥共享方案 定义2 2 9 ( 椭圆曲线上点的加法) d 是无穷远点，定义e 吼) 幻= 矿，p 是一个大于3 的 素数，为一正整数) 上的“+ ”运算如下： 1 对于所有的p e 叽) p + d = d + p = p ； 2 对于所有的p e 峨) 且p = 阮y ) d ，有一p = 瓴_ y ) ，p + ( 一竹= d 其中一p 表 示p 的负元 3 若p = o l ，) ，1 ) d ，q = ( 旎，沈) d ，则p + q = ，粥) 这里勋= 矛一工l 一旎，均= 砸l 一而) 一y l ，其中a 的选取分两种情况：一 i 当p q 时，五= 鸶碧； i i 当p = q 时，2 = 皆 对于任意的p e 暇) 满足，l p = d 的最小正整数n ，称为p 的阶，记作d 耐( 即= 忍 定义2 3 0 ( 椭圆曲线群的阶) 令 伍力ei 五ye 玛lu d l 为e 暇) 的f 覃一有理点全体 所有有理点的个数记为e 眠) ，称其为域f 孽上椭圆曲线e 吼) 的阶 由h 嬲s e 定理可知鼋+ 1 2 锕e ) 霉+ 1 + 2 倔 有限域上几种特殊的椭圆曲线定义如下： 定义2 3 l ( 奇异椭圆曲线、超奇异椭圆曲线和反常椭圆曲线) 1 若e 叽) = g 则称e 暇) 为奇异椭圆曲线； 2 若层暇) = g + 1 一f 而p i f ，则称e 皿) 为超奇异椭圆曲线； 3 若e 吼) 粤，且存在p e ) 使d 磁= p ，则称e 暇) 为反常椭圆曲线 离散对数公钥加密算法是目前最为热门的公钥加密算法。其安全性要远远高于基 于大数分解的r s a 算法离散对数问题可以定义为： 华东师范大学基于代数几何的可公开验证的多密钥共享方案 定义2 3 2 ( 离散对数问题) 设( g ，) 是乘法群，对于一个万阶元素口g 和卢 ，存 在唯一的整数口，0 口万一l ，满足：矿= 届称口为与口与口相关的离散对数，记为 如g 猡 在a b e l 群e 暇) 上关于七的方程q = 七p 中，由七和p 求q 容易，但由p 和q 求七是 困难的这就是有限域上椭圆曲线离散对数问题 椭圆曲线密码体制最早是由l 【 b u t z 【1 8 】和m m 盯【2 2 】于1 9 8 5 年提出，其安全性 就是建立在解有限域上椭圆曲线离散对数问题的困难性基础之上不过。并不是有限 域上所有的椭圆曲线都可以应用到公钥密码体制中为了确保安全性，需要选取安全 椭圆曲线对给定的椭圆曲线e ) ，若求解其上的离散对数问题需要指数时间，则称椭 圆曲线为安全椭圆曲线满足如下4 个条件的椭圆曲线e 叽) 称为安全椭圆曲线： 1 q 是大于3 的素数或口= 2 7 而r 为素数 2 e 0 巳) 不是奇异的、超奇异的或反常的椭圆曲线 3 e 叹) t 时一1 ) ，1 七2 0 4 当口= 2 ，且r 为素数时，e 吼) = z s ，其中s 是一个大素数，c 的值为1 或2 本文提出的新方案选用第一类椭圆曲线曲线新方案的可验证性基于修正w 酣对 的性质下面介绍w 醯对的定义和性质及修正的w 醯对的相关结论 定义2 3 3 蜘对) e 是一条定义在域置上的椭圆曲线假设域置的特征不整除正整 数鼋，则鼋阶w 醯对是一个映射 白：砌聊哪假q ) 一篇， 其中e m = p e 西l 矿= d ) ，= 协e 巧lf = 1 l ，a = ( 竹一( d ) ，曰= ( q ) 一( 仍。 ( 反) = 弘，( 届) = g 曰它满足如下性质： 1 双线性：对于所有的s l s 2 ，s ，乃，死，re 研棚， 白岱i + s 2 ，d = 白岱l ，乃白岱2 ，乃，白岱，死+ 死) = 勺岱，死) 已g 岱，死) ； 1 6 华东师范大学基于代数几何的可公开验证的多密钥共享方案 2 非退化性：岱，丁) = 1 ，v 丁e 研留】营s = d ；白岱，乃= l ，垤研们铮r = d 3 恒等性：( l 乃= l ，v r e 【办 4 交错性：勺( 瓦s ) = e g 岱，乃一1v s ，r e 【鼋】； 5 与自同态的相容性：设口是非零自同态，则( 口( s ) ，口( n ) = 白岱，d 姆 推论2 3 ( 【3 0 】推论3 1 0 ) 令 死。疋) 是研q 】的基，则白( 乃，死) 是1 的鼋次原根 证明：由域置的特征不整除正整数留，得等式妒= 1 没有重根因而，在巧中f = 1 有 霉个不同根且嘞是阶为留的循环群任何生成元f 是1 的留次原根也就是说严= l 当且仅当gl 七 假设已口( 乃，死) = f 且尹= 1 则( 乃，d 死) = 1 且白( 死，d 死) = 窖( 死，死尸= 1 对任 意的s e k 】，存在整数口，6 使得s = 口死+ 易死所以岱，d 乃) = 白( 孔，d 死尸白( 疋，d 疋户= 1 进而矾= d 而d 死= d 当且仅当gi 正所以f 是l 的鼋次原根 e 【万】是一个交换a b e h 锄群，称为n 阶扭点群定理2 4 给出了e 伽】的群结构 定理2 4 ( 【3 0 】定理3 2 ) e 是一条定义在域置上的椭圆曲线万是正整数p 是域x 的特 征如果p = 0 或pt 万，则e 【n 】= 乙乙如果p 0 且pi 记一= 矿q 十) ，则 e 【万】皇蜀舀或e 【n 】篁乙乙 w 醯对的以下结论是本文提出的密钥共享具有可验证性的基础 引理2 1 ( 【3 0 】引理5 1 ) 令e 是定义在有限域b 上的一条椭圆曲线只q e ) 窖是 p 的阶且g 以臼，p ) = 1 存在七使得q = 肛当且仅当留q = d 且白( 只q ) = 1 证明：若q = 肛，则留q = 鼋肛= d 僻q ) = 白( 只舛= 1 = 1 另一方面，若g q = d 则qe 研棚因为剃国，p ) = l ，所以e 【嘲皇乙z 把取点尺使得 只天) 是研g 】的基 则存在整数口，6 使得q = 口p + 坎由推论2 3e g 假固= f 是1 的霉次原根因此，若 白( 只q ) = l ，l = 勺假q ) = ( 只即口白假砂= 矿易兰o ( 删d 因而职= d ，q = 口p 定义2 3 4 ( 修正的w 醯对) 令岛：) 2 = j r 3 + l 是定义在素域耳q 兰2m o d3 ) 上的一 1 7 兰奎! 至垄奎兰 基于代数几何的可公开验证的多密钥共享方案 条椭圆曲线f 一是1 的3 次原根定义映射 。- - - - _ - _ 一 声：e ( f ；) e ( f ，) ，伉y ) 卜哼( c 以，) ，) ，嗣= d 在这个映射下，修正的w 醯对定义为：毛( p l ，p 2 ) = 白( p l ，觑( b ) ) ，其中是一般的 w 醯对，p i ，p 2 e 修正的w 醯对的以下结论是本文提出的密钥共享具有可验证性的另一个基础 引理2 2 ( 【3 0 】引理6 1 ) 假设3t 鼋，若p 岛的阶恰是g 则毛( 只乃是1 的鼋次原椒 证明：假设存在整数m ，v 使得归= 似p ) ，则触p ) = 似d = 卵岛以) 若讦= 0 ， 则“p = 0 从而兰0 ( 删d ，1 ，三0 ( 删d 若诈0 ，令忡= 瓴力且毛) ，b ，则 ( 毗y ) = 触p ) 岛噼) 注意到薯，必有工= o 因此1 ，p = ( o 士1 ) 且诈的阶为3 这与3 ，鼋矛盾所以若h p = 似即，必有“三0 ( m 以咖，1 ，兰0 ( m 以鼋) 所以只觑即是 e 嘲的基由推论2 3 知岛僻竹= 假烈即) 是l 的粤次原根 1 8 第三章密钥共享方案的相关研究 3 1 s h 锄i r s ，忍) 门限密钥共享方案 s h a m i r s 陬帕门限密钥共享方案分为3 个阶段：初始化，子密钥的分配和主密 钥重构前2 个阶段由密钥分发者完成，第3 个阶段由n 个成员中的任意k 个合作完成 n ，七 s 帕是正整数f p 为p 元有限域，p 是素数并且p 万为了使集合p = p - ，p 2 ，r ) 中的n 个参与者共享主密钥墨b ，密钥分发者进行如下操作： 1 密钥分发者在b 中随机选取n 个不同的元素，记为而，而，并公开参与 者只的身份信息薅a = l ，刀) 2 密钥分发者秘密地在b 中一致地随机选取七- 1 个不同的元素，记为口l ，口2 ，诹- 1 上一l 3 密钥分发者计算毋= 舳) ( 1 f 刀) ，这里八曲= s + 毋一eb m f 1 4 密钥分发者秘密地将子密钥母分配给只只l f ，1 这可通过一个秘密安全 信道传输完成，只不得向任何人泄露子密钥母 主密钥的重构阶段，一组参与者子集丑= p | l 一，如 只l 0 万希望通过共 享子密钥重构出主密钥s = 口o = ，( 0 ) 1 当j f 屯j f 个参与者可以通过差值方法得到主密钥毒这是因为 j = 删= 妻毋( i 点 j = 删= 毋兀圭 i - l 扣l 一 一i 2 当j f 七时，j f 个参与者得不到主密钥j = 口。的任何信息这是因为j 个参与者 利用身他们掌握的身份信息和j f 个子密钥信息可以得到含有七个变元的j 个 1 9 华东师范大学基于代数几何的可公开验证的多密钥共享方案 方程若j = 七一1 ，他们得到含有七个变元的七一1 个方程假设这七一1 个 参与者用他们掌握的七一1 个子密钥猜得主密钥是跖由于将主密钥的任何 假设值印和关于子密钥的七一1 个方程放在一起可得到唯一的多项式厶，使 得印= 厶( 0 ) ，厶) = 舷j ) ，1 j 七一1 没有一个主密钥的可能值被排除，因 而，七一1 个参与者合谋得不到主密钥的任何信息 s h 棚i r 的他咒) 门限密钥共享方案是理想、线性、完备密钥共享方案它不依赖 任何假设( 数学困难问题) 。是最简单、有效和实用的一类密钥共享方案这里的重构要 求指通