（计算机软件与理论专业论文）指定多接收者签名的研究及实现.pdf

摘要 摘要 随着i n t e r a c t 的高速发展，信窟、安全理论与技术越来越显示 b 其重要地位，而 数字签名技术是信息安全理论与技术的基础和重要保证，在网络通信安全方面起 着重要的保护作用。 实际应用中，数字签名的使用需求有多种多样。在许多情况下，同一个消息 需要同时发送给多个特定的接收者，签名者要求他的签名仅能由这些指定的多个 接收者验证真伪，并且这每一个指定接收者都希望能够独立验证签名的有效性， 无需相互协作，而任何无关的其他人在没有得到签名者或者指定接收者的帮助下 都无法证实签名。这种特殊的签名就是指定多接收者签名。 但是，现阶段对指定多接收者签名技术的系统性研究并未得到足够的重视， 特别是当指定接收者人数过多时，一些现有的签名实现方法可行性很差。本论文 正是针对这个问题，对此签名方式进行了分析探讨。在研究总结现有的相关数字 签名的利弊的基础上，利用t a t e 对具体构建出三种安全、高效且各具优势的指定 多接收者签名方案，并分别对其可用性进行分析；另外，还深入研究了签名实现 的核心运算t a t e 对计算，实现了t a t e 对的快速计算，保证了签名实现效率。 具体来说，本论文的主要研究成果包括以下几个方面： ( 1 ) c h a m e l e o n 签名是一种设计简单、易于实现的有向签名，但其在面对多名 指定接收者时实现复杂、效率低。针对此缺陷，提出设计实现同样简洁有效且有 利于保护签名者利益的指定多接收者的c h a m e l e o n 签名方案。无论有多少个指定 接收者，签名者只需利用该方案一次性地计算出所有指定接收者的公钥和，即通 过一次签名，便可以方便地控制其签名的可验证性，无需交互式验证，也不用重 复签名，签名效率极高。并且，签名长度短，签名长度不会随着指定接收者人数 增加而加长。 ( 2 ) 对指定多接收者的c h a m e l e o n 签名方案进行时效性的推广改进，提出具有 时效性的指定多接收者c h a m e l e o n 签名方案。陔方案不仅具有签名的多向性，而 且增加了签名时效性的新功能，在签名效率与安全性等方面也都优于现有的可转 换c h a m e l e o n 签名方案，适用于签名需要指定多名接收者，且对签名时效有一定 要求的场合。 ( 3 ) 签名消息有时对指定接收者个人具有十分重要的意义，针对此情况，我们 利用基于身份的加密思想，提m 有利1 二保护签私接收者隐私的指定多接收暂的基 于身份的签密方案，该方巢既保持了撼于身份密码体制平数字签密的优点，又麒 有签名多向。眺。签名执ij ：放：钲 r l ：j ，整个签密过稚蹦信1 次 f a t e 对计算，指定 接收者的人数越多叫效率优势越7 j i | i l i j 。 ( 4 ) 分析探讨了指定多接收者签名实现的相关技术。由于双线性映射的训算直 接刻划了椭圆曲线双线性映射密码系统的实现速度，t a t e 对计算的快慢对指定多 接收者签名的实际应用有着极大的影响，所以为进一步保证签名实现的效率，本 论文还广泛研究了现有的计算t a t e 对的各种算法及有关成果，在此基础l ，快速 实现了t a t e 对的计算，加快了指定多接收者签名的实现。 关键词：数字签名：c h a m e l e o n 签名：基于身份加密；椭圆曲线；t a t e 对：有限域 a b s t r a c t a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e r a c t ，t h et h e o r ya n dt e c h n o l o g yo fi n f o r m a t i o n s e c u r i t yb e c o m em o r ea n dm o r ei m p o r t a n tt h ed i g i t a ls i g n a t u r ei s t h ef o u n d a t i o na n d g u a r a n t e eo ft h ei n f o r m a t i o ns e c u r i t ya n dp l a y sak e yr o l ei np r o t e c t i n gt h es e c u r i t yo f n e t w o r k i n gc o m m u n i c a t i o n i np r a c t i c a la p p l i c a t i o n ，t h e r ea r ev a r i o u sd e m a n d st ot h eu s eo f d i g i t a ls i g n a t u r e i n s o m es i t u a t i o nam e s s a g en e e d st ob es e n tt om o r et h a no n el e g a lr e c i p i e n ta tt h es a m e t i m e as i g n e re x p e c t sh i ss i g n a t u r et ob ev a l i d a t e do n l yb yt h e s ea p p o i n t e dr e c i p i e n t s e v e r yr e c e i v e ra l s oh o p e sh ec a ne a s i l yv e r i f yt h es i g n a t u r er e s p e c t i v e l yw i t h o u ta n y o t h e r s h e l p ，b u tt h o s ei r r e l e v a n to n e sc a nn o tw i t h o u tt h es i g n e r so rh i sc o o p e r a t i o n t h i sk i n do fs p e c i a ld i g i t a ls i g n a t u r ei sa p p o i n t e dm u l t i r e c e i v e rs i g n a t u r e h o w e v e r , a tp r e s e n tt h es y s t e m i cs t u d ya b o u ta p p o i n t e dm u l t i r e c e i v e rs i g n a t u r e t e c h n o l o g yh a sn o tb e e ns e r i o u s l yc o n s i d e r e d s o ，w em a i n l yd i s c u s st h ek i n do fs p e c i a l s i g n a t u r ei n d e t a i l i n t h i st h e s i s b a s e do i lt h ea n a l y s i sa n ds u m m a r i z a t i o nt os o m e e x i s t i n gr e l a t e dd i g i t a ls i g n a t u r e s ，t h r e ek i n d so fa p p o i n t e dm u l t i r e c e i v e rs i g n a t u r e s c h e m e su s i n gt a t ep a i r i n ga r ep r o p o s e da n dt h e i ra p p l i c a b i l i t i e sa r ea l s op r o v e d r e s p e c t i v e l yb yu s o u rs t u d ys h o w st h et h r e es c h e m e sa r es e c u r e ，e f f i c i e n ta n de a c hh a s i t ss t r o n gp o i n t i na d d i t i o n ，ap r a c t i c a la n de f f i c i e n tm e t h o dt oa c h i e v ef a s tc o m p u t a t i o n o ft a r ep a i r i n gi sp r o v i d e di no r d e rt og u a r a n t e et h ea p p o i n t e dm u l t i r e c e i v e rs i g n a t u r e e f f i c i e n c y t h em a i na c h i e v e m e n t sc o n t a i n e di nt h i sd i s s e r t a t i o na r ea sf o l l o w s ： ( 1 ) c h a m e l e o ns i g n a t u r eb e c o m e sc o m p l e xa n di n e f f i c i e n ti ft h e r ea r em o r et h a n o n er e c i p i e n t a i m i n ga tt h ef l a w ，a na p p o i n t e dm u l t i - r e c e i v e rc h a m e l e o ns i g n a t u r e s c h e m ei sp r o p o s e dt h a ti sa d v a n t a g e o u si np r o t e c t i n gt h ei n t e r e s t so ft h es i g n e r n o m a t t e rh o wm a n ya p p o i n t e dr e c e i v e r s ，t h e s i g n e rc a nc o n v e n i e n t l y c o n t r o lt h e v e r i f i c a t i o no ft h es i g n a t u r eo n l yb yc o m p u t i n gt h es u mo fa l lr e c i p i e n t s p u b l i ck e y sa t o n et i m e t h ed e s i g na n di m p l e m e n t a t i o no ft h es c h e m ei ss i m p l ea n dv e r ye f f i c i e n t f u r t h e r m o r e ，t h es i g n a t u r ei sv e r ys h o r ta n dw i l ln o tb el e n g t h e n e de v e nw i t ht h e i n c r e a s ei nn u m b e ro ft h ea p p o i n t e dr e c i p i e n t s ( 2 ) a ni m p r o v e da p p o i n t e dm u l t i r e c e i v e rc h a m e l e o ns i g n a t u r es c h e m ew i t ht i m e l i m i ti sp r e s e n t e db a s e do nt h ea p p o i n t e dm u l t i r e c e i v e rc h a m e l e o ns i g n a t u r es c h e m e i t ss i g n a t u r ee f f i c i e n c ya n ds e c u r i t ya r eb e t t e rt h a nt h ee x i s t i n gc o n v e r t i b l ec h a m e l e o n s i g n a t u r es c h e m e s ag o o dw a yt os o l v et h ep r o b l e mo fs i g n a t u r ew i t ha p p o i n t e d r e c e i v e r sa n dt i m el i m i ti so f i e r e db yt h es c h e m e 山东人学硕十学位论文 ( 3 ) b a s e do nt h ei d e n t i t y b a s e de n c r y p t i o ni d e a s a na p p o i n t e dm u l t i - r e c e i v e r i d e n t i t y b a s e ds i g n c r y p t i o ns c h e m ei sp r o p o s e dt h a tc a nk e e pt h ep r i v a c yo ft h el e g a l r e c i p i e n t s t h es i g n c r y p t i o ns c h e m en o to n l yh a st h ea d v a n t a g e so fi d e n t i t y b a s e d c r y p t o - s y s t e m ，b u ta l s oc a ns i g na n de n c r y p tm e s s a g e sa tt h es a m et i m eo n l yo n et a t e p a i r i n gc o m p u t a t i o ni sn e e d e dt os i g nas i n g l em e s s a g ef o ra l la p p o i n t e dr e c e i v e r s a sa r e s u l t ，t h ee f f f i c i e n c yg a i no ft h es c h e m ei sh u g ee s p e c i a l l yw h e nt h e r ea r eal a r g e n u m b e ro fr e c e i v e r s ( 4 ) t h i sp a p e ra n a l y z e ss o m er e l a t e ds i g n a t u r er e a l i z a t i o nt e c h n o l o g i e s b e c a u s e p a i r i n gi st h eh e a v i e s to p e r a t i o ni nt h ep a i r i n g - b a s e dc r y p t o s y s t e m sa n dt h ep e r f o r m a n c e o fp a i r i n ga f f e c t st h ea p p l i c a t i o no ft h ea p p o i n t e dm u l t i r e c e i v e rs i g n a t u r es c h e m e si n p r a c t i c e ，c a l c u l a t i n gp a i r i n gi se s p e c i a l l yd i s c u s s e dt oe f f i c i e n t l yi m p l e m e n ta p p o i n t e d m u l t i r e c e i v e rs i g n a t u r e b yt h es t u d yt os o m ee x i s t i n ga l g o r i t h m sa n dr e s u l t so ft h e i m p l e m e n t a t i o no fp a i r i n gi nd e t a i ld u r i n gt h ep r o c e s so fr e a l i z i n gt h es i g n a t u r e ，af a s t m e t h o dt oc o m p u t e r a t ep a i r i n gi sp r e s e n t e da n de v a l u a t e d k e y w o r d s ：d i g i t a ls i g n a t u r e ；c h a m e l e o ns i g n a t u r e ；i d b a s e de n c r y p t i o n ；e l l i p t i cc u r v e t a t ep a i r i n g ；f i n i t ef i e l d 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行硼贫：所取 得的威：果。除文中已经注明引用的内容外，席毫仑文不包俐唾睡f 也个 或集体已经发 表或撰写过舶利硼i 成果。j c 寸本文的研究作出重要员蒯c f 眭价 和集体，均已在文中以明 确意捌。本声明白勺i 商聿责任由本 再担。 论文作者签名：奎整日期：兰! ! ! ：生：曼 本 完全了解山东大学有；镖留、使用学位敝的夫腚，同意哮校保留或向国家有 关部门或机悔塑乏论文的复印件和电子版，允许论文被查阅和借阅；本 授权山东大学 可眺际格新z 论文的全瓿墨涪盼内容编入有关数据嘲荭彳亍检索，可绷影印、缩印或 刘蝮制手段翮手论文币7 豳辫学位论丈。 ( 保密 仑= 蛔确张i 后应五罄守l 雌腚) 一：塑剔嗽锄期：丛业 第】章i j m 1 1 研究背景与意义 第1 章引言 随着通信网络，特别是因特网的迅速发展希1 同益普及，通过网络进行远距离 的、快速的信息交流和信息处理已变得越来越普遍。人们对信息的安全存储、安 全处理和安全传输的需求也愈加迫切，数字签名技术应运而生，并开始用于商业、 政治等各种用途中。 数字签名技术是网络安全通信的需要，是信息安全理沦与技术的基础和重要 保证。作为保障汁算机数据安全的一项重要安全机制，数字签名技术主要用来实 现认证服务、数据完整性服务，从而保汪通信双方的利益，因此在计算机网络安 全通信中具有重要的应用价值和广泛的应用前景，数字签名及其相关课题的研究 也成为现代密码学和信息安全最活跃的领域之一，成为当前网络安全领域的研究 热点。 一般的数字签名具有签名可以被普遍证实的特点，任何人只要知道签名者的 公开密钥，就可以在任何时间验证其签名的真实性，而不需要签名者的同意。但 是在实际生活中，签名者往往不希望他的签名能够被任何人验证，而是希望其签 名具有有向性，也就是说，只有他认定的某个合法的签名接收者刁能验证签名的 真伪，任何第三方没有得到签名者或者接收者的合作都无法确认签名的有效性。 这种只涉及通信双方的签名就是指定接收者签名。 指定接收者签名中，签名的可验证性受到签名者或者指定接收者的控制，签 名具有有向性，只能被某个特定接收者确认。现有的一些特殊数字签名，如不可 否认签名、指定确定人签名吐c h a m e l e o n 签名等都是这种签名，它们一般都是 通过对签名进行加密或者进行交互式验证来实现签名有向接收的目的。 然而，在许多时候，签名的合法接收者往往不止一个人，签名具有多向性， 同一个消息需要发送给多个指定接收者，并且每一个指定接收者都希望能够独立 验证签名的有效性，无需相互协作，任何无关的其他人若没有签名者或接收者的 镪助都无法验证：簦名真伪。这种情况在现实生活中十分常见，例如，国家政府、 安全和情报部门签署的机密文件，需要同时发送给一些特定的机构或具有定级 别的官员；又盘a 公司3 1 ：展某个项1 】过程中，有1 1 个固定合作公司，项目进行 期i h j ，a 公司需要经常给所有合作公司发送何关项日进展的文件，似他并不希望任 何非合作公司能够掌握这些文什的内容。 以上这种签钉仪能合法的n 名( n ，1 ) 接i 改盏独、j 验的掺j 方式桃是指定多 山尔人学硕十学位论文 接收者签名。这种签名的实现方法有多种，例如，可以通过现有的指定接收者签 名方案，为多个特定接收者分别单独签名。因为指定接收者签名往往与接收者的 私钥公钥对有关，所以对于每一个指定接收者，签名者只需分别使用其相应的 公钥对消息进行签名，接到签名后，每一个指定接收者用其私钥即可验证签名。 通过这种重复签名，就能够把同一个消息发送给多名指定接收者。除此之外，还 可以通过其它一些方式，诸如变通一些现有方案，达到只能有指定多接收者验证 签名的目的。但是，在实际应用中，特别是签名的指定接收者人数过多时，这些 实现方法的可行性有时并不理想：多次重复签名会增加很多通信量，导致签名效 率过低，某些变通方案签名过程繁琐，或是密钥共享、分发复杂，不易实现。 所以，针对现阶段缺乏对指定多接收者签名技术的系统性研究分析，以及这 个领域中存在的一些不成熟性，有必要丌展对此类签名的研究，推广创新现有的 相关签名方案，构建出一些设计简单、实现方便、快速高效、抗攻击性好的指定 多接收者签名方案，为需要多名合法接收者的签名问题提供更好更多的解决途径。 1 2 论文章节安排 本论文共分六章，其中第三、四章着重于签名方案的设计与分析，第五章着 重于签名的实现，具体安排如下： 第二章：介绍研究指定多接收者签名所需要的数学及密码学的知识。首先给 出群环域的基本概念、椭圆曲线的基础理论，然后简要介绍1 h e 对的定义及相关性 质，最后对数字签名的原理、分类等进行分析，侧重介绍了几种与指定多接收者 签名相关的有向签名，如不可否认签名、特殊门限签名等。 第三章：首先回顾c h a m e l e o n 签名，对这种设计实现都简单有效的签名进行 了简要介绍与分析，然后针对其不适用于签名具有多名指定接收者的缺陷，对其 进一步优化改进，通过t a t e 对具体设计出指定多接收者的c h a m e l e o n 签名方案， 并分析了方案的设计简洁性、安全性、效率与签名转换性等方面。最后对指定多 接收者的c h a m e l e o n 签名方案进行时效性的推广改进，进一步设计出其时效性改 进方案，既保证了签名的多向性，又保证了签名的时效性，并对此方案的时效性、 安全性进行分析。 第四章：首先介绍多接收者加密及基于身份加密的理论，然后在其基础上， 结合多接收者i b e 方案及改进的旗r 身份的签密办案，通过t a t e 对具体设计出指定 多接收者的基于身份的签密方案，并肘其进行安全性、执行效率等方面的叮用性 分析。 第 章：研究探讨指定多接收青签名丈现i 涉及的天键技术，包括椭圆曲线 的选取、有限域构造多项式的确定、i h t e 3 “门汁锋算法及 1 l 灭运饽等。尤其深入研 第1 章引言 究了签名实现的“瓶颈”运算t a t e 对计算，在广泛探讨现有的各7 f l t , t a t e 对计算 相关成果的基础上，实现了t a t e 对快速计算，并对其进行了具体实施和测试，给出 测试结果与测试结论。 第六章：给出本文总结乘j 研究展望。 1 3 主要研究成果 本论文主要的研究成果是：利用t a t e 对构建出三种指定多接收者签名方案： 指定多接收者的c h a m e l e o n 签名方案及其时效性推广方案、指定多接收者的基于 身份的签密方案，为同一消息具有多名独立的合法接收者的签名问题提供了更好、 更多、更快的解决途径：并且对签名实现中涉及的相关技术进行分析，研究且完 成了快速t a t e 对计算，保证了签名实现的效率。 ( 1 ) 在c h a m e l e o n 签名的基础上，提出指定多接收者的c h a m e l e o n 签名方案。该 方案不仅保持了c h a m e l e o n 签名设计简单、易于实现的优点，而且克服了c h a m e l e o n 签名在面对多名指定接收者时实现复杂、效率低的缺陷。无论有多少个指定接收 者，签名者只需利用该方案一次性地计算出所有指定接收者的公钥和，即通过一 次签名，便可以方便地控制其签名的可验证性，无需交互式验证，也不用重复签 名，签名效率得到了极大的提升，签名长度短且不会随着接收者人数增多而加长。 同时，该方案构建在椭圆曲线群之上，比一般的签名方案具有更高的安全性、更 快的签名速度，在同等安全强度下具有更短的密钥长度。 ( 2 ) 对指定多接收者的c h a m e l e o n 签名方案进行时效性的推广改进，提出设计 实现简单有效的具有时效性的新方案。该方案不仅具有签名的多向性，而且增加 了签名时效性的新功能，适用于签名需要指定多名接收者，且对签名时效有一定 要求的场合。并且该方案通过引入时间戳的概念，保证即使签名者为相同接收者 进行多次签名，接收者的私钥也不会产生暴露的危险。 ( 3 ) 利用基于身份的加密思想，提出指定多接收者的基于身份的签密方案。该 方案既保持了基于身份密码体制的优点，又可以在一个逻辑步骤内同时完成消息 加密和数字签名两项功能，其代价显著低于常规的“先签名再加密”方法。同时， 浚方案具有签名多向性，只有特定的多名接收者才能够独立地恢复消息、验证签 名有效性，更好地保护签名接收者的隐私，因而它在签名消息对指定接收者个人 具有重要意义的场合中十分有用。该方案执行效率很高，整个签密过程只需2 个t a t e 对计算( 其中，1 个t a t e 对可以预先计算 “束，故签密过程实际只需1 个t a t e 对计算) ， 当指定接收者的人数越多时，其效率的优势会) 哒j j l l 明显。另外，陔方案陶建在椭 圆曲线群之上，同样具有椭吲曲线密码的优势。 ( 4 ) 对指定多接收者签名实现中涉及的州关技术进行分析，也牺椭刚曲线的选 山尔人学顾十学位论文 取、有限域构造多项式的确定、t a r e 对的计算算法及相关运算等。为保证签名实现 效率，在广泛研究现有t a t e 对的计算算法及成果的基础上，快速实现了t a t e 对计算， 并对其进行了具体的编程实施和测试。 第2 学理论基础 第2 章理论基础 现代密码学为信息系统的安全性提供了有效的技术保证。基于公开密钥密码 学发展起来的数字签名为抵抗攻击者对信息系统进行主动攻击提供了强有力的防 护手段，在商业系统和个人生活中扮演着越来越重要的角色。本章主要介绍研究 指定多接收者签名所需用到的数学及密码学的知识，并对相关签名技术进行了简 要的分析。 2 1 群、环、域 ( 1 ) 群 非空集合g 中，定义了一种代数运算：乘( 或加) ，且满足下面的条件，则称 g 构成一个群： 封闭性。对任意a , b g ，有a b e g 。 结合律成立。对任意a , b ，c g ，有( a b ) c = a ( b c ) 。 存在单位元e 。对任意a e g ，有e g ，使a e = e a = a 。 存在逆元。对任意a e g ，有b g ，使a b = b a = e ，称b 为a 的逆元。 群g 的阶是g 中元素的个数，记为# g 。阶有限称为有限群，否则称为无限群。 若群g 中的运算适合交换律，即对任意a ，b g ，有a b = b a ，则g 称为a b e l 群或可交换群。 若群g 中每一个元素均是它的某一个固定元素a 的某次幂，则称g 是由a 生成的 循环群，a 是g 的生成元，记为g = 。 ( 2 ) 环 非空集合r 中，定义了两种代数运算：加、乘，且满足下面的条件，则称r 构 成一个环： r 对加法构成a b e l 群。 乘法的结合律成立。对任意a , b ，c r ，有( a b ) c = a ( b c ) 。 乘法对加法的分配律成立。对任意a , b ，c r ，有 a ( b + c ) = a b + a c ，( b + c ) a = b a + c a 。 ( 3 ) 域 非空集合f 中，定义了两种代数运算：加、乘，且满足下面的条件，则称f 构 成个域： f 对加法构成a b e l 群。咳加法群甲何几写为0 。 t l l 尔人学硕十学位论文 f 中除去元素0 外，对乘法构成a b e l 群。该乘法群的单位元写为1 。 乘法对加法的分配律成立。对任意a , b e f ，有 a ( b + c ) ；a b + a c ，( b + c ) a = b a + c a 。 域f 的阶是f 中元素的个数。阶有限称为有限域，否则称为无限域。包含q 个元 素的有限域汜为f q 或g f ( q ) 。 注：群、环、域方面的详细知识请参考文献 4 】 5 。 2 2 椭圆曲线 2 2 1 w e i e r s t r a s s 方程与椭圆曲线 射影平面上的齐次表达式：y 2 z + a l x y z + a 3 y z 2 = x 3 + a 2 x 2 z + a 4 x z 2 + a 6 2 3 ，称为 w e i e r s t r a s s 方程，其中a l ，a 2 ，a 3 ，a a ，a 6 k 。 设f ( x ，y ，z ) = y 2 z + a 1 x y z + a 3 y z 2 - x s _ a 2 x 2 z a 4 x z 2 - a 6 2 3 ，称为w e i e r s t r a s s 多项式。 当f ( x ，y ，z ) ( 卯钗，o f o y ，o f o z ) ( 0 ，0 ，o ) 时，w e i e r s t r a s s 方程在射影平面上 所有点的集合即为椭圆曲线e 。椭圆曲线e 在射影平面上有一个z = 0 的点( 0 ，l ，o ) ， 称为无穷远点，记为d 。 为方便起见，w e i e r s t r a s s 方程可以写成仿射坐标的形式，令x = x z ，y = y z ， 则w e i e r s t r a s s 方程化为：y 2 + a l x y + a 3 y = x 3 + a 2 x 2 + a 4 x + a 6 ，此时椭圆曲线e 为仿射平 面上满足w e i e r s t r a s s 方程的解的集合，再加上一个无穷远点0 。 如果a 1 ) a 2 ，a 3 ，a 4 ，a 6 k ，则称e 定义在k 上，表示为e k 。如果k = f 。，则e k 是定义在有限域上的椭圆曲线。 e ( k ) 表示e 上有理点和无穷远点0 的集合，即椭圆曲线上所有点的集合： e ( k ) = ( x ，y ) eix ，y ek i u o 。 在e ( k ) 上引入加法运算“+ ”，从而使 e ) ，+ 构成一个a b e l 群，椭圆曲线密 码体制即是建立在a b e l 群e ( k ) 上的密码体制。 。 2 2 2 椭圆曲线上的运算 对于椭圆曲线e 上的点p 、q 和r ，p 和p + q 定义如下： ( ”d + 0 = 0 ，d = 0 。 ( 2 ) p + o = o + p = p 。o 可以看成加法单位元。 ( 3 ) 若p = ( x ，y ) d ，贝0 一p = ( x ，y a l x - a j ) 。 ( 4 ) 若0 = 一p ，则p + q = o 。 ( 5 ) 若p q 且p , q 的x 坐标不同则直线l = p q 截曲线钉且仪有点r f 若l 为曲线的切线，则令r = p 或r = q 为切点) ，定义p + q = r ，即所截的第- + a 的 第2 章理论基础 境像。 ( 6 ) 若p q 且p , q 的x 坐标丰h 同( 其y 坐标必定相反) ，则p + q = o 。 ( 7 ) 若p = q ，令l 为曲线上p 点的切线，l 截f f i 线仅有一点r ，则p + q = 2 p = 一r 。 由此可计算2 p 。对于k 个相同点棚加，即p + p + + p 表示为k p ，称为点乘、数乘 或标量乘。 2 2 3 椭圆曲线的阶、迹 椭圆曲线e 的阶指e ( k ) 中点的数目，记为# e ( k ) 。 计算# e ( k ) 是研究有限域上椭圆曲线的一个核心问题： 定理( h a s s e 定理) ：设k f q ，e k 为椭圆曲线，则i # e ( k ) q - 1 i 2 q 。( 定理 证明见 6 ) 。 定理：对任意ft 【2 q ，t o ( m o dp ) ，存在f q 上的椭圆曲线e ，使得 # e ( f 口) 2 q + l t 。 定理中的t 称为f r o b e n i u s 迹，简称为迹。 另外，对于椭圆曲线上的一点p ，满足n p = o 的最小正整数n 称为点p 的阶。 2 2 4 判别式与j 一不变量 对椭圆曲线e 定义以下的量： d 2 = a 1 2 + 4 a 2 d 4 = 2 a 4 + a l a 3 d 6 = a 3 2 + 4 a 6 d s = a 1 2 a 6 + 4 a 2 a 6 一a l a 3 a 4 + a 2 a 3 2 a 4 2 c 4 = d 2 2 2 4 d 4 = 一d 2 2 d 8 8 c h 3 2 7 d 6 2 + 9 d 2 d 4 d 6 j ( e ) = c 4 。a 式子称为w e i e r s t r a s s 方程的判别式。当不等于零时，j ( e ) 称为椭圆曲线e 的j 一 不变量。 2 2 5 除子 除子是研究代数曲线的个基本：【：具。 椭圆曲线e 上的除子是e 上的点的一个有限形式和d = ，a ，( p ) ，其中p 表 示椭圆曲线上的点，a ，为整数，且只有有限个不为0 。 除子d 的次数是d e g ( d ) = l ，a ，。 除予d 的支撑是点集s u p p ( d ) = p eia p o 。 i l i 东人学硕： = 学位论文 除予加法是d ，+ d ：= ，a ，( p ) + ，b ，( p ) = ，( a ，+ b p ) ( p ) 。 所有除子的集合形成一个加法交换群，通常记为d i v ( e ) 。所有次数为0 的除 子构成零除子群d i v o ( e ) ，为d i v ( e ) 的一个子群。 如果f 是有理函数且f 与椭圆曲线的交点只有有限个是零点或极点，o r d ( f p ) 表 示f 在p 点的次数，则定义函数的除子是d i v ( f ) = 乏：o r d ( f ，) ( p ) 。 函 如果除子d = ，a ，口) ，f 是有理函数且s u p p ( d ) m s u p p ( d i v ( f ) ) 2 十，则定义函 数在除子上的赋值f ( d ) = 兀f ( p ) “。 p e s u p 。p ( d ) 如果对于除子d ，存在一个有理函数f 使d = d i v ( 0 ，则称d 为主除子。 如果对于除子d l ，d 2 ，存在一个有理函数f 使d l = d 2 + d i v ( f ) ，则称d l 与d 2 等 价，记为d 1 d 2 。 定理：d = ，a ，( p ) 为主除子，当且仅当，a ，= q ，a ，p = o 。 2 2 6 椭圆曲线离散对数问题 离散对数问题( d l p ) 是指：给定一个素数q ，z 。的一个生成元及一个元素 1 3 z q ，寻找整数x ( 0 x q 一2 ) ，使得a x _ pm o d q 。 椭圆曲线离散对数问题( e d l p ) 是指：p 是e ( f q ) 上的一个点，设点q 是e ( f q ) 上为p 的倍数的点，即存在整数x 0 ，使q - 一x o ，则椭圆曲线离散对数问题就是由 给定的p 和q 确定出x 。 2 2 7 超奇异椭圆曲线 当椭圆曲线e 满足j ( e ) = 0 ，称为超奇异椭圆曲线。 曲线方程定义域曲线的阶安全乘子 y 2 = ) 【3 + ( 1 b ) x + b b 0 ，1 ) f d p + l 2 y 2 + y = x 3 + x + b ，b e o ，1 f 。 2 + l 2 ( ”1 y 2 4 y 2 = x 3 - x + b ，b ( 1 ，1 l 。 3 + l 3 ( ”1 y 2 6 表2 1 超奇异椭圆曲线 在密码学中特别感兴趣的是满足c h 叫k ) 1t 超奇异椭圆曲线，其中t 为f r o b e n i u s 迹。安全乘子k 的作用是，椭圆曲线的离散对数问题可以直接转化成有限域在扩张 k 次后的有限域上的离散对数问题，k 是这样的最小一个证整数。m o v 攻d i * 7 t ：足利 用这种特性。 注：椭圆曲线方面的洋细知以清参考文献 6 9 。 笫2 章理论基础 2 3t a r e 对 2 3 1t a r e 对的定义 e 为f q 上的一条椭圆曲线。d 是与q 互素的整数，一般取d 为素数，d i # e ( f q ) 。 k 为一个正整数，使e ( f q ) f m j 。域e ( f t ) 包含d 次单位根，即需要满足d l q u - 1 。 有理函数g f 0 t ( e ) ，满足d i v ( g ) 2 d ( p ) 一d ( d ) 。q 为e ( f - ) de ( f t ) 的个代 表点，构造零除子d ( q ) 一( d ) ，使s u p p ( d ) f l s u p p ( d i v ( g ) ) = m ，则定义t a t e 对是： e d ( p , q ) = g ( d ) 引吲_ e ( l 掣卜所有满足掣p _ d 的点的舱 但这样定义的t a t e 对值不唯一，所以t a t e 对通常定义为： e d ：e ( f q t ) d 】e ( f t ) d e ( f q t ) 一f q t d f t e d ( p ，q ) = g ( d ) 4 l 1 川 为了方便密码学中使用，提出了一个修改的t a t e 对的定义： e d ：e ( f q ) d x e ( f - ) d 一f - e a ( p , q ) = g 。( 中( q ) ) 4 。 其中中为d i s t o r s i o n 变换函数，p 为方程p p - p + 2 b = 0 的根，o 为方程6 2 + l = o 的根 定义中( q ) = 中( x ，y ) = ( p x ，0 3 ) 2 3 2 t a r e 对的性质 ( 1 ) 双线性性： e a ( p l + p 2 ，q ) = e a ( p b q ) xe d ( p 2 ，q ) ； e d ( p ，q l + q 2 ) = e d ( p q 1 ) e a ( p , q 2 ) ； e d ( a p ，q ) = e d ( p a q ) = e d ( p ，q ) 3 ，其中a z 。 ( 2 ) 非退化性：如果对任意q e ( f 。) ，有e d ( p , q ) = i ，那么p = o 。相反，对任 一个p d 总存在q e ( f 、) d ，使e d ( p q ) 1 。( 参考文献 1 0 0 0 的定理3 ) ( 3 ) 可计算性：如果d = h d7 ，p e ( f q ) d ，q e ( f 。) d ，那么e d ，( h p ，q ) = e d ( p ，q ) “。 2 3 3d i f f i e h e ii m a n 问题 g 是一个群p 是g 中的点素数q 是p 的阶数： ( 1 ) 计算性d i f f i e - h e l l m a ni n 题( c d h p ) ：对任意a , b z 。+ ，给定p , a p ，b p g ， 计算a b p 。 ( 2 ) 决定性d i f f i e h e l l m a n 问题( d d h p ) ：埘任意a , b ，c z q + ，给定p , a p ，b p ，c p 山东人学硕十学位论文 g ，决定是否c ；a bm o dq 。 g 是一个加法群，g 是个乘法群，在g 、g 中e d l p 是困难的。双线性映 射：g g g ( 可由椭圆曲线上的w e i l 对或l a t e 对得到) ： ( 3 ) 双线性d i f f i e h e l l m a n 问题( b d h p ) ：对任意a , b ，c z q + ，给定p , a p , b p , c p g ， 计算e ( p ，p ) o 。 g 1 、g 2 是两个不同的加法群，g 3 是一个乘法群，在g 卜g 2 、g 3 中e d l p 是 困难的。双线性映射6 ：g i x g 2 一g 3 ： ( 4 ) 相应的计算性d i f f i e h e l l m a n 问题( c o c d h p ) ：给定p ，a p g 1 ，q e g 2 ，计 算a q 。 ( 5 ) 相应的决定性d i f f i e h e l l m a n 问题( c o d d h p ) ：给定p ，a p e g l ，q ，b q 6 2 ， 其中p 与q 具有相同的阶q ，决定是否a m bm o d q 。 ( 6 ) 相应的双线性d i f f i e h e l l m a n 问题( c o b d h