（计算机应用技术专业论文）基于离散对数问题的一次签名方案研究.pdf

河南大学研究生硕士学位论文第1 页 摘要 信息安全是一切基于计算机网络的通信活动得以正常运行的前提和基础。但 是，我国信息安全技术还处于低水平状态，因此我们在信息安全技术领域还有许 多工作要做。 公钥基础设施p k i 是认证中心c a 的基础，为c a 进行密钥管理提供了一个平 台，是一种新的网络安全技术和安全规范。它能够为所有网络应用透明地提供采 用加密和数字签名等密码服务所必需的密钥和证书管理。到目前为止，完善并正 确实施的p i g 系统是全面解决所有网络交易和通信安全问题的最佳途径。 签名方案是一种给以电子形式存储的消息签名的方法，签名之后的消息能通 过计算机网络传输。签名方案可以用来验证身份的真实性、文档的完整性和不可 否认性，是信息安全研究的重要内容。签名方案使用强大的密码技术和p k i ，以更 好地保证身份的真实性、文档的完整性和不可否认性。 椭圆曲线离散对数问题是目前公认的可用于密码体制的三大数学难题之一。 自1 9 9 7 年开始，国际上对椭圆曲线公钥密码体制进行了较为广泛的研究。目前， 椭圆曲线公钥密码体制已经开始从理论研究阶段走向应用实现阶段j 但我国还尚 处于起步阶段。 基于公钥密码思想和p k i 技术规范，本文提出了基于椭圆曲线离散对数问题 的一次签名方案。 所谓的一次签名方案就是仅对一则消息进行签名，但签名可以被进行任意次 验证的签名方案。一次签名方案的安全性主要依赖于构造签名方案的单向双射函 数所依据数学难题的难解性和每次签名时随机选取的签名密钥对。 主要工作包括： 第一，设计了一个基于椭圆曲线离散对数问题的单向双射函数； 第二，提出了基于该单向双射函数的一次签名方案，通过构造相关定理证明 其安全性，并通过仿真实验验证其安全性； 第三，给出了签名方案理论模型的运算算法。 关键词：椭圆曲线；离散对数问题；单向双射函数；一次签名方案 第1 i 页河南大学研究生硕士学位论文 a b s t r a c t i n f o r m a t i o ns e c u r i t yi st h ep r e c o n d i t i o na n db a s i so fe v e r y t h i n gt h a tc a l lw o r kr e g u l a r l y b a s e do nt h e c o m p u t e rn e t w o r k c o m m u n i c a t i o n ，b u tt h ei n f o r m a t i o n s e c u r i t y t e c h n o l o g yi si nl o wl e v e li no u rc o u n t r y ，s ow es h o u l dd om u c hr e s e a r c hi nt h i sf i e l d 1 1 1 ep u b i ck e yi n f r a s t r u c t u r e ( p k i ) i sb a s i so fc e r t i f i c a t i o na u t h o r i t y ( c a ) ，a n dp r o v i d ea p l a t f o r mt oc a t oa d m i n i s t r a t es e c r e tk e y s 1 h ep i gi so n ek i n do fn e wn e t w o r ks e c u r i t y t e c h n o l o g ya n ds e c u r i t yc r i t e r i o n i tp e l l u c i d l yp r o v i d e sa d m i n i s t r a t i o no f t h es e c r e tk e y a n dc e r t i f i c a t ew h i c hi su s e da s e n c r y p t i o n a n d d i g i t a ls i g n a t u r e t oa l ln e t w o r k a p p l i c a t i o n s a tp r e s e n t ，t h ep i gs y s t e m ，w h i c hp e r f e c tm o r e o v e rc o r r e c t l yb e i n gp u t i n t oe f f e c t ，i st h eb e s to fw a yt os e t t l et h es e c u r i t yo fb u s i n e s sa n dc o m m u n i c a t i n go v e r n e t w o r k a s i g n a t u r es c h e m ei sam e t h o do fs i n g i n gam e s s a g es t o r e di ne l e c t r o n i cf o r m ，a n dt h e s i g n e dm e s s a g ec a nb et r a n s m i t t e do v e rac o m p u t e r n e t w o r k t h es i g n a t u r es c h e m ec a l l v e r i f yt h ea u t h e n t i c i t y , i n t e g r i t ya n du n d e n i a b l e n e s so fad o c u m e n t ，a n ds i g n a t u r e s c h e m ei st h ei m p o r t a n tc o n t e n tt h a ti n f o r m a t i o ns e c u r i t ys t u d i e s t h es i g n a t u r es c h e m e u s e st h ep o w e r f u lc r y p t o g r a p h yt e c h n o l o g ya n dp k i ，w i t hm u c hf o r c et og u a r a n t e et h e a u t h e n t i c i t y , i n t e g r i t ya n du n d e n i a b l e n e s so fo n ed o c u m e n t t h ee l l i p t i cc u r v ed i s c r e t el o g a r i t h mp r o b l e m ( e c d l p ) i sr e c o g n i z e do n eo ft h r e e m a t h e m a t i c sd i f f i c u l tp r o b l e m sw h i c hc a l lb eu s e dt od e s i g nc r y p t o s y s t e ma tp r e s e n t s i n c e19 9 7 ，t h ep u b l i ck e yc r y p t o s y s t e mb a s e do ne c d l ph a sb e e nw e l ls t u d i e di n i n t e r n a t i o n a lc r y p t o g r a p h yf i e l d a tp r e s e n t ，t h ep u b l i ck e yc r y p t o s y s t e mb a s e do n e c d l pa l r e a d ys t a r t e df r o mt h ef u n d a m e n t a ls t u d y s t a g et om o v et o w a r d st h e a p p l i c a t i o nr e a l i z a t i o ns t a g e ，h o w e v e ri ts t i l li si ns t a r t 堍p h a s ei no u rc o u n t r y b a s e do nt h ep u b l i ck e yc r y p t o s y s t e ma n dp k it e c h n o l o g yc r i t e r i o n ，i nt h et h e s i s ，p ut f o r w a r dao n e - t i m es i g n a t u r es c h e m eb a s e do ne c d l p t h es o c a l l e do n e t i m es i g n a t u r es c h e m ei sas i g n a t u r es c h e m ew h i c hs i g n so n l yo n - e ；, - - i 南大学研究生硕士学位论文第1 i i 页 m e s s a g ea n dt h es i g n a t u r ec a r lb ev e r i f i e da na r b i t r a r yn u m b e ro ft i m e s t h es e c u r i t yo f t h eo n e - t i m es i g n a t u r es c h e m er e l i e so nt h ei n t r a c t a b i 珏t yo ft h em a t h e m a t i c sd i f f i c u l t p r o b l e mw h i c hu s e d t od e s i g nt h eo n e w a y b i j e c t i v ef u n c t i o n ，a n dr e l i e so nt h e r a n d o m l ys e l e c t e ds i g n a t u r ek e y - p a i r se v e r yt i m eo n em e s s a g ei ss i g n e dt o o m a m m ys t u d y - i n c l u d i n g ： f i r s t l y , d e s i g nao n e - w a yb i j e c t i v ef i m c t i o nb a s e do ne c d l p ； s e c o n d l y , p u tf o r w a r da o n e - t i m es i g n a t i t r es c h e m eb a s e do na o n e - w a yb i j e c t i v e f u n c t i o n ，c o n s t i t u t es o m et h e o r e mt op r o v et h es i g n a t u r es c h e m ei ss e c u r e ，a n dv e r i f y t h es e c u r i t yo f t h es c h e m eb ys i m u l a t i n ge x p e r i m e n t ； 、 r h 珏d l y , g i v es o m ea l g o r i t h mo f t h e o r ym o d e lo f t h es i g n a t u r es c h e m e k e yw o r d ：t h ee l l i p t i cc u r v e ；t h e d i s c r e t e l o g a r i t h mp r o b l e m ；o n e - w a yb i j e c t i v e f u n c t i o n ；o n e 4 i m es i g n a t u r es c h e m e 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位中请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他人p s 经发表或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构的学位或证书而 使用过的材料。与我一同工作的凰燕瓣蒜霸窥所儆的任何贡献均已在论文中作 了明确的说明并表示了谢意苫j毪魏ij 、。”毒强j ，j 毫、髦；i 。i ， 壬，i ?j 。l 。i 学噻擀菇蹲焦裁基囊黪戆豢，j 漕鳝螫一 豢。”囊爹j 鬻：攀j 荔j l 、簪滚蕊日。沁，j 鍪? 7 、。二爱鬻。霉萋瀚曝烀么溉日 露 。 、毒妻j 麓r |蔓 ：一。? 置 1 。l 舅iiij i 蠹；麓_ ；i ； 篓嚣j ，。，。、銎董j 蠹爱。i 攀 潆：震燃；慧爹憋麓 本人经河角大学审核批臻蠛鬻黼藏维：作为学位论文娜者，本人完全 了解并同意河南淑学有关保管攀鬻灏鬻瓣漆瀵稠、要求，即确大学有权向国家 图书馆、科研信息梗掏、数据收羲机掏表毒榱图书馆等攮祺学位论文( 纸质文 本和电子文本) 以供公凇索、羹阐c 笤$ 本人摭枳河、赢灾学出于宣扬、展览学校 学术发展和进行学术交流竽静镳鬻擎惑瞄蔫毒舄澎印。：缩印、扫描和拷贝等复制手 段保存、汇编学位论文( 甄质文本和电子文本) 。 ( 涉及保密内容的学位论文在解密后适, r f l 本授权书) 学住获得者( 学住论文作者) 签名一韩二b l 2 0 驴7 年月，扩日 学位论文指导教师签名： 河南大学研究生硕士学位论文第1 页 第1 章绪论 随着信息技术和网络技术的快速发展，大量的机密信息和重要数据得以不必通 过专用的设施进行传输和存储，大大降低了信息传输的成本，因此，基于计算机 网络的各种商务活动和政务活动也迅猛发展起来。相应地，这些在公共信道上传 输的信息的安全问题也就显得更为突出。 信息安全是一切基于计算机网络的通信活动得以正常运行的前提和基础。但 是，我国的信息安全技术还处于低水平的状态，我们在信息安全技术领域方面还 有许多工作要做。信息安全不仅关系着我国信息化建设的成败更关系着国家的利 益和安全【l , 2 , 3 1 。 数字签名可以用来验证文档的真实性、完整性和不可否认性，是信息安全研究 的重要内容。数字签名使用强大的密码技术和公开密钥基础设旌嘶b h ck e y i n f r a s t r u c t u r e ，p k i ) ，以更好地保证文档的真实性、完整性和不可否认性。 本文将以公开密钥基础设施为基础背景，对数字签名的相关内容展开研究。 1 1 信息安全概述 信息安全问题主要包括在公共信道中传输的数据安全和在计算机系统中存储 的数据安全两个方面的问题。 一 其中计算机系统中存储的数据主要面临的安全威胁形式【4 】有：浏览( b r o w s i n g ， 指通过搜索计算机内存或外存的方法非法获取数据) 、泄露( l e a k a g e ，指非授权用 户通过对数据的访问非法获取保密信息) 、推理( i n f e r e n c e ，指通过统计分析数据 非法获取敏感数据) 等被动攻击手段；同时，对于计算机系统中存储的数据和程 序，威胁其完整性的形式还有增加记录、删除记录、修改记录等。特别地，计算 机病毒和木马会使计算机系统瘫痪、数据丢失等灾难性后果。对于这些威胁通常 采用采用密码控制、存取控制、推理控制和数据的备份与恢复手段来解决。 对于这种基于存储数据安全的问题，不是本文研究的内容。因此，这里的信息 安全就特指是公共信道中传输的数据安全问题1 5 , 6 , 7 j 。 1 1 1 安全威胁 对于一个计算机网络通信系统，可以根据信息流的流动情况来分析其工作是否 第2 页河南大学研究生硕士学位论文 正常、是否受到攻击。在正常情况下，信息流是从数据发送方的数据源流到接收 方的目的地，这种正常情况下的信息流动可以如图1 1 所示。 当信息流动与图1 1 不同时，说明通信过程受到了攻击。攻击分为被动攻击 ( p a s s i v e a t t a c k ) 和主动攻击( a c t i v e a t t a c k ) 两种。 图1 - 1 正常的信息流动 ( 1 ) 被动攻击 这种攻击是指攻击者非法搭线窃听和监视，从网络通信双方所交换的信息数 据流中获取所需要的信息。被动攻击下的信息流动如图l - 2 所示。 图1 - 2 被动攻击 根据对所截获信息的处理方式不同，被动攻击又可以分为析出消息型和通信 量分析型。 1 析出消息 。 析出消息是指直接从信息数据流中获取所需的消息。 2 通信量分析 当通信的双方使用加密技术对所传输的信息进行了屏蔽和变换，使得攻击者 无法直接从所截获的信息中析出消息时，攻击者可以通过观察所交换的信息的频 率、长度等通信量，应用统计学方法分析消息的性质，猜测信息中所包含的可能 的内容，这就是通信量分析。 由于被动攻击难以被检测，所以，对于被动攻击的重点在于防范。对于析出 消息型被动攻击，可以用加密技术来预防；而对于通信量分析型被动攻击，则要 求经过加密等处理后的信息在统计学上无规律。 ( 2 ) 主动攻击 主动攻击是指攻击者非法修改通过公共信道传输的信息。对于网络通信活动 而言，主动攻击的危害更大。主动攻击者直接参与网络通信，干扰信息的流动， 篡改信息的内容，甚至产生虚假的信息流。具体地说，主动攻击有四种类型：伪 河南大学研究生硕士学位论文第3 页 装攻击、重放攻击、篡改消息和拒绝服务。 1 伪装攻击 伪装攻击是指攻击者通过产生一个虚假的信息流，伪装成另一个合法的通信 实体，参与通信过程。伪装攻击一般与其他类型的攻击联合使用例如，攻击者 可以把以前截获的某一合法的鉴别信息进行重放，伪装成某一合法的通信实体参 与通信。 伪装攻击的信息流动如图1 - 3 所示。 图1 3 伪装攻击 2 重放攻击 重放攻击是指攻击者通过重传被动攻击截获的某一通信信息流的方式，参与 通信过程，以产生一个未授权的效果。重放攻击一般与其他类型的攻击联合使用， 其信息流动如图1 - 4 所示。 图l _ 4 重放攻击 3 篡改消息 篡改消息是指攻击者通过篡改合法的通信信息的某一部分，或者改变信息的 传输顺序，以得到一个攻击者所期望的结果。其信息流动如图1 - 5 所示。 4 拒绝服务 图1 - 5 篡改消息攻击 第4 页河南大学研究生硕士学位论文 拒绝服务是指攻击者通过干扰公共信道，中断正在进行的网络通信或降低网 络公共信道的性能，破坏网络通信的可用性。其信息流动如图1 - 6 所示。 1 1 2 安全需求 图1 6 拒绝服务攻击 信息要在公共信道上传输，这些信息时刻都要面临着各种类型的攻击，而这些 信息的合法参与者则会根据信息机密程度的不同，提出不同的需求这些需求综 合起来，可以归纳为四种。 1 保密性需求 保密性是指在没有专门的保密通道的情况下，保证在通信过程中通信各方之间 的通信内容不被未授权的第三方阅读。它可以保护在公共信道中传输的信息免受 被动攻击，防止攻击者析出消息内容，保护通信量免受分析。 2 真实性需求 真实性需求是指通信的一方能够鉴别另一方的身份，确保数据源的可靠性和真 实性。它关心的是参与通信的实体是否真正是他所宣称的那个实体。在通信的双 方关于所传输的数据来源的真伪发生争执时，可以由合法的、公正的第三方来解 决争执。 3 完整性需求 完整性需求是针对数据的有效性提出的，完整性要求防止未经授权的数据被修 改，确保信息在传输过程中没有冗余、插入、篡改、伪造等。在电子商务活动中， 这一需求非常重要。 4 不可否认性需求 不可否认性也称抗否认性、不可抵赖性。由于通信过程中参与通信的各方不是 面对面地会谈，所以，人们期望能有一种技术确保通信各方对自己行为的承诺， 防止人们否认自己曾做过的行为。具体地说，不可否认性需求一方面要求数据发 河南大学研究生硕士学位论文第5 页 送方在发出消息之后，就不能再否认他所发出的消息；另一方面，要求数据接收 方在收到消息后不仅能够证实消息确实由其所宣称的那个人发送的，而且事后也 不能否认曾经接受过该消息。 1 2 基于公开密钥基础设施的签名方案工作流程概述 公开密钥基础设施p k i ( p u b l i ek e yi n f r a s t r u c t u r e ) 是一种遵循标准的利用公钥密 码体制提供一套安全基础平台的技术和规范。它为安全认证体系进行密钥管理提 供了一个平台，能够为所有网络用户透明地提供加密和数字签名等密码服务所必 需的密钥和证书管理。它是一种新的网络安全技术和规范。 签名方案( s i g n a t u r es c h e m e ) 又称数字签名( d i g i t a ls i g n a t u r e ) ，它是一种可 以在计算机网络环境下实现身份真实性，数据数据完整性和不可否认性功能的密 码体制。基于公钥密码体制和私钥密码体制都可以获得数字签名，特别是公钥密 码体制的诞生为数字签名的研究和应用开辟了一条广阔的道路。目前，关于数字 签名的研究主要集中在基于公钥密码体制的数字签名研究。 基于公开钥密码体制的签名方案在验证时需要签名者的公开钥( p u b l i ck e y ) ， 而这个公开钥就是由p k i 来提供的，因此，p k i 是签名方案的基础 1 2 1 。p k i 模型 p k i 模型如图1 7 所示。 图1 7p k i 模型 第6 页河南大学研究生硕士学位论文 从图1 7 可以看出，p k i 由以下五个部分组成：密钥备份及恢复系统、证书库、 c a 认证系统、证书作废处理系统和客户端证书处理系统五部分。 其中c a 认证系统包括： 1 证书认证部门，简称c a ( c e r t i f i c a t i o n a u t h o r i t y ) ，负责产生和确定用户实体 的数字证书； 2 审核授权部门，简称r a ( r e g i s t r y a u t h o r i t y ) ，它负责对证书的申请者进行 资格审查，并决定是否同意给申请者发放证书； 3 证书操作部门，简称c p ( c e r t i f i c a t i o np r o c e s s o r ) ，它为已被授权的申请者 制作、发放和管理证书； 4 密钥管理部门，简称k m ( k e y m a n a g e m e n t ) ，它负责产生用户实体的信息 加密钥对，并对用户实体解密私钥提供托管服务； 5 证书存储地( c e r t i f i c a t i o ns t o r a g e ) ，包括所有的证书目录。 1 2 2 公开钥的公布流程 在我国的公开密钥基础设施中，所有用户实体都必须使用统一规范的双密钥证 书。一对是专门用于进行数字签名的签名密钥对，另一对是专门用于信息加、解 密的密钥对。 下面是公开密钥基础设施p k i 公布公开钥( 包括签名方案公开钥和信息加密公 开钥) 的一般工作过程： 一 ( 1 ) 申请者从国家密码委员会认可的密钥设备中产生一个签名方案密钥对； ( 2 ) 申请者把签名私有钥留下，签名公开钥和申请者信息用c a 的公开钥加 密，提交给c a ； ( 3 ) c a 收到申请者的证书请求后，进行审核，同时向k m 发出密钥请求， 并将申请者的签名公开钥一同交给k m ； ( 4 ) k m 从密钥池中取出一对加密密钥对，并将加密私有钥用申请者的签名 公开钥加密后，一同交给c a ； ( 5 ) c a 用自己的私有钥对申请者信息、签名公开钥、信息加密公开钥和信 息加密私有钥( 该私有钥经签名公开钥加密) 四项内容进行数字签名，即得到申 请者所需要的证书。此时，用户申请者的身份也变为用户实体。用户实体从c a 那 里下载证书和信息加密私有钥。 ( 6 ) 证书生成，用户实体的公开钥直接由c a 发布在c s 中，便于用户查询 和访闽。 河南大学研究生硕士学位论文第7 页 1 2 3 签名方案工作流程模型 一个的签名方案的工作流程如图1 - 8 所示。 图1 - 8 签名方案工作流程 一个签名方案必须有签名算法和验证算法，签名算法及签名用的私有钥是保密 的，而验证算法的是公开的，验证算法需要的验证密钥可以由验证者向p k i 查询 得到。 1 3 研究内容和研究意义 数学是密码技术的理论基础，密码技术又是签名方案的核心技术。初等数论、 抽象代数和代数几何是本文研究内容的理论工具也是研究对象之一。数字签名是 信息安全技术的一个重要组成部分，它的安全性是研究问题的重中之重。本文着 重研究相关密码技术，构造个可证明安全的签名方案。 i n t e m e t 的迅猛发展使商务、政务甚至军事事务都通过网络来进行，然而，人 们从面对面的作业，变成网上互不见面的操作，这样就产生了很大的安全隐患。 如何保证网上传输数据的安全和对方的身份确认是网络用户关心的内容，而数字 签名是保证数据完整性和身份确定性的一种有效解决方案。希望本文的研究内容， 也能在这方面做出点贡献。 1 4 论文组织安排 论文的具体安排如下： 第8 页河南大学研究生硕士学位论文 第1 章概括介绍公共信道上传输的信息所面临的安全问题，以及相关的安 全需求，并给出了基于公开密钥基础设施的签名方案工作流程。在此基础之上确 定了本文将要研究的主旨和内容。 第2 章简要介绍本文研究内容所必需的数学基础。首先介绍初等数论中的 三个重要结论，其次介绍近世代数中群、环、域和有限域的基础内容，然后给出 椭圆曲线的理论知识。 第3 章基于离散对数问题的难解性经常被用来构造密码体制，重点介绍几 个有效的离散对数问题求解方法，研究这些求解方法是为了设计出更好、更安全 的密码体制。 第4 章从h a s h 函数的概念开始，给出h a s h 函数的常用分类，研究经常用于 签名方案中的安全h a s h 函数：s h a 1 、s h a - 2 5 6 和s h a 2 2 4 ，给出h a s h 函数的几 种攻击方法。 第5 章是对签名方案的研究，给出几个常用的签名方案。 第6 章利用公钥密码设计一个基于椭圆曲线离散对数问题的一次签名方案。 在设计一个椭圆曲线群上单向双射函数的基础上，给出签名算法和验证算法，并 用定理和仿真的形式证明基于椭圆曲线离散对数问题的一次签名方案的安全性， 同时给出了与其他常用签名方案的定性分析比较。 本章小结 首先介绍了公共信道上信息面临的安全威胁和安全需求。接着介绍了p k i 模 型，以及基于p k i 的公开钥公布流程，同时介绍了一个签名方案的完整工作流程。 给出了本文的研究内容和研究意义，确定了本文的研究主旨。最后是本文的组织 安排。 河南大学研究生硕士学位论文第9 页 2 1 数论基础 第2 章数学基础 数论是信息安全保密技术的一个重要工具，大部分现行的公开钥密码体制和 计算机网络安全系统都是以数论中的问题为基础。在这里主要讨论的是欧拉函数、 中国剩余定理和欧几里德算法伟, 9 1 。 2 1 1 欧拉函数 定义2 1 欧拉( e u l e r ) 函数西是一个定义在正整数上的函数，西 的值等于 序列0 ，1 ，2 ，p - 1 中与p 互素的数的个数。 定理2 1 欧拉定理若g c d ( a ，p 产1 ，则a 叩) ；l ( m o d p ) 。 推论2 1 若p 是素数，g c d ( a ，p 产1 ，则a p - 1 ；l ( m o dp ) 。 2 1 2 中国剩余定理 定理2 。2 同余式西- = b ( m o d m ) 有解的充要条件是，其中d = g c d ( a ，删) 。令 m = ，若而是该同余式的一个解，则该同余式的所有解均满足工= 而( m o d m 。 推论2 2 设g c d ( a ，所) = l ，则同余式甜9 6 ( m o d 册) 恰有惟- - 解x f f i - x o ( m o d m ) 。 定理2 3 中国剩余定理设码，鸭，是两两互素的正整数， m = r n 2 ，m = 篇o = 1 ，七) ，则同余方程组x - g b , ( r o o d m , ) ，i = 1 ，2 ， 后。 有惟一解x = - t 】i m , y , + 岛鸩儿+ + 吃鸩妖( m o d m ) ，其中，m 乃- = l ( m o d m ，) ， i = 1 。2 。七。 第1 0 页河南大学研究生硕士学位论文 2 ，1 3 欧几里德算法 欧几里德算法( e u c l i d e a na l g o r i t h m ) 就是辗转相除法，利用欧几里德算法可 以迅速地找出给定的两个整数a 和b 的最大公因数g e d ( a , b ) ，并判断a 和b 是否互 素，在求得g c d ( 柚) 的同时，还能给出满足g c d ( a , b ) = s a + t b 的两个常数s 和t 。 当g c d ( a ，b 沪1 时，利用欧几里德算法可以找出两个常数s 和t 使得s a + t b - - - i 。 于是可得s a = 1 ( r o o d b ) ，和t b ；1 ( r o o da ) ，于是s 是a 模b 的乘法逆，t 是b 模a 的 乘法逆。 下面给出可以完成上述任务的扩展欧几里德算法的伪代码： 算法2 1e x t e n d e de u c l i d e a na l g o f i t h m ( a , b ) a o - a ，b o 十- b ，t o + - 0 ，t _ 1 ，s o + - 1 8 。0 q 。陪j , r - - a o - q b o w h i l er 0 d 0 1 t e m p + 一t o q t t o t t 一t c m p t e m p + 一s o q s s o + - s s + t e m p a o 。b o b o - r 旷剖 r a o - q b o r + - b o r e t u m ( r , s , o 河南大学研究生硕士学位论文第l l 页 2 2 代数基础 2 2 1 群 群( g r o u p s ) 是抽象代数学的重要组成部分本节探讨群的有关概念和性质【l 仉 1 n 。 定义2 2 一个群( g ，) 由一个满足下列三个条件的二元运算“- ”构成： ( 1 ) 群运算是可结合的。 ( 2 ) 有一个称作单位元的元素1 e g ，使得对所有的口g ，有a 1 = 1 a = a 。 ( 3 ) 对每一个a g ，有一个称作口的逆元素6 使得b o = a b = l ，把b 记为一 一个群g 是a b e l i a n 群，如果它还满足下列条件： ( 4 ) 对所有的口，b g 有b 口= 口b 。 对加法群而言，通常用0 来表示单位元素，用一a 表示口的逆。 定义2 3 如果l g 渥有限的，那么群g 是有限群。一个有限群的元素个数称为 它的阶( o r d e r ) 。 定义2 4 设g 是个群，如果g 中有一个元素盯使得对每一个b 仨g 都存在 一个整数i 使得b = 口，则称g 是一个循环群，口称为g 的一个生成元。 定义2 5 设g 是一个群，口g ，口的阶定义为使得= 1 的最小整数t 。 定义2 6 设h 是群( g ，) 的一个非空子集，如果h 本身在群g 的运算“” 之下构成一个群，则称h 是g 的一个子群。如果h 是g 的个子群且h g ，则 称h 是g 的一个真子群。 定理2 4 ( l a g r a n g e 定理) 设g 是一个有限群，h 是g 的一个子群，则i h i l j g j 关于循环群有以下基本性质： ( 1 ) 循环群的子群也是循环群。 ( 2 ) 设g 是一个群，如果口g 的阶是t ，则矿的阶是t g c d ( t , k ) 。 ( 3 ) 设g 是一个阶为n 的循环群，d 陋，则g 恰有m ( d ) 个阶为d 的元素。特 别地，g 有m ( n ) 个生成元。 2 2 2 环 环( r i n g ) 是抽象代数学的重要组成部分。本节将探讨环的有关概念和性质盼 第1 2 页河南大学研究生硕士学位论文 1 3 , 1 4 i 5 1 。 定义2 7 一个环( r ，+ ，) 是由两个满足下列条件的r 上的二元运算“+ ”和 “”构成： ( 1 ) ( r ，+ ) 是一个a b e l i a n 群，单位用0 表示。 ( 2 ) 运算是可结合的，也就是说，对所有的口，b ，c r ，有a x ( b x c ) = ( a x b ) x c 。 ( 3 ) 有一个乘法单位1 ，使得对所有的a x l = l x d = 4 。 ( 4 ) 乘法和加法由分配律联系着，也就是对所有的a ，b ，c r 有 口( 6 + c ) = ( a x b ) + ( a xc ) 和( 6 + c ) a = ( b x 西+ 0 力 如果一个环限，+ ，) 还满足条件：对所有a ，b e r ，有a x b = b x a ，则环限， + ，) 为交换环。 定义2 8 设r 是一个环，ae r ，如果存在一个元素b r 使得a x b = l ，则称a 是一个单位或可逆元素。 环r 的所有单位之集关于乘法形成一个群，称为r 的单位群。 定义2 9 假设p 是一个素数。定义z v 【z 】是变元x 的所有多项式集合。按照 通常多项式的乘法和加法定义( 并且模p 归约系数) ，它构成一个多项式环对于 ( 功，g ( 乙嘲满足g ( 力= g ( 功，( 力，则说，( 功整除g ( 力( 记做：f ( x ) l g ( x ) ) 。 对于厂c 力乙吲，的阶数d 昭( ) 定义为厂的项中最高次数。假设( 功，g ( 力， ( 力z 。【明，且d e g ( 力= n2 1 。如果，( 功i ( g ( 功 ( 功) 则定义：g ( 曲； ( m o d f ( x ) ) 。 定义2 1 0 如果不存在多项式a ( x ) ，五( d 乙【工】满足，( 功= 石 ) l ( x ) ，则 称多项式，( 功z ，【x 】是不可约的。其中，d e g ( z t ) o 和d e g 旺) o 。 2 2 3 域 域( f i e l d ) 是抽象代数学的重要组成部分本节将探讨域的有关概念和性质 1 0 ，1 2 ，瑚。 定义2 11 满足下列条件的一个交换环称为一个域：所有的非零元素都有乘法 逆。 定义2 1 2 设f 是一个域，如果对任何m l ，1 + l + + 1 4 = 0 ( m 个l 相加) ， 则称f 的特征为0 ，否则，f 的特征是使得罗1 = 0 的最小正整数m 。 1 = 1 定理2 5 乙是一个域，当且仅当力是素数。如果露是素数，则乙的特征值是 河南大学研究生硕士学位论文第1 3 页 刀。 关于特征值有以下重要事实：如果一个域的特征不是0 ，贝它的特征必是素数。 定义2 1 3设e 是一个域，f 是e 的一个子集，如果f 关于e 的运算本身形 成一个域，则称f 为e 的子域，也称e 为f 的扩域。 定义2 1 4 对于多项式环乙 x 】( ( ) ，当且仅当厂( 功是不可约时，z ，m ( ，( 力) 是多项式域。 多项式域z a x ( 八x ) ) 中元素的乘法逆元可以直接通过改进的欧几里德算 法( e u c l i d e a n a l g o r i t h m ) 计算。 2 2 4 有限域 密码学中用到很多有限域【l 坷( f i n i t ef i e l d ) 中的运算，因为可以应用数论中的 理论，保持数的大小在有限的范围内，且不会有取整的误差。 只含有有限个元素的域称为有限域。有限域中元素的个数是一个素数，或者是 一个素数的乘方，记为z 。或者f _ ，其中p 为素数。 ， n z 。是一个具有，个元素的素数有限域。如果g = 矿，p 是素数，雄l 是整数， 则，l 是个具有g 个元素的多项式有限域。有限域中元素的个数称为该域的阶。 ， 在有限域中，加法单位元是0 ，乘法单位元是1 ，每一个非0 的元素都有一个 惟一的乘法逆元。有限域中运算满足交换律、结合律和分配律。 很多密码系统是基于乙的，为了使系统更复杂。可以使用多项式有限域只。来 构造密码系统。在对多项式有限域的实际研究中，用到最多是有限域凡，在硬件 上，利用线性反馈移位寄存器可以快速地实现e ，上的运算。因此，只上的计算 通常比磊上的运算快。 已经知道，乘法群z ，( p 是素数) 是一个阶为p 1 的循环群。事实上，任何 有限域的乘法群都是循环群：一、 o ) 是一个矿一1 阶的循环群。 定义2 1 5 多项式有限域中，生成元多项式称为本原多项式，且其系数是互素 的。 第1 4 页；- 7 南大学研究生硕士学位论文 2 3 椭圆曲线 根据密码体系的研究需要，这里将探讨的是光滑的椭圆曲纠1 1 “。这一曲线在 解析平面中表现为一条非奇异( n o n s i n g u l a r i t y ) 的三次平面曲线。由r i e m m a n r o c h 定理和亏格公式可知，任何一条椭圆曲线都可以用一个三次方程来表示，这个三 次方程一般称为w e i e r s t r a s s 方程。w e i e r s t r a s s 方程为： y 2 + q 砂+ 呜) ，= p + a 2 x 2 + a 4 x + a 6 ( 2 。1 ) 在仿射坐标系下椭圆曲线e ，可用w e i e r s l r a s s 方程式外加一个特殊的点o 来表 示。满足方程式w e i e r s t r a s s 的数偶( 并，y ) 为域f 上椭圆曲线上的点。其中，域f 是代数闭域，它可以是有理数域r ，也可是有限域只。 与椭圆曲线公钥密码学有关的有限域主要有三类：乙，e 。和乃。 2 3 1 椭圆曲线的简化形式 对于w c i e r s t r a s s 方程式，令 如= 砰+ 4 a 2 6 4 = q 呜+ 2 a 4 66=霹+4a6(2-2) 6 i = 彳口6 + 4 a 2 a 6 一q 呜口+ 吒露一面 c 4 = 蟹一2 4 6 及 心e ) 2 哆2 二。3 - 2 7 b , 2 + 9 b ：b , b , ( 2 - 3 ) i j ( e ) = 司a ) 显然，当且仅当a ( d 0 时，椭圆曲线方程式是光滑的，或者称为非奇异的。 本文均研究a ( e ) 0 的椭圆曲线。 定义2 1 6 设有椭圆曲线e ，其仿射方程为w e i e r s l r a s s 方程，则a ( d 为椭圆曲 线e 的判别式，而，( 印为椭圆曲线e 的j 不变量。 根据域f 的特征c h a r ( f ) 和j 不变量，可以得到w e i e r s t r a s s 方程的不同简化形 式。 ( 1 ) c h 砸) 2 ，3 时 ，= 矿+ 甜+ b ( a ，6 刀( 2 4 ) 河南大学研究生硕士学位论文第1 5 页 ( 2 ) c h a r ( f ) = 2 时 j y ：+ x y = x 3 + a 2 x 2 + ! a 2 ，a 6e f ，( e ) o ) ( 2 - 5 ) 【厂+ 吗y = r + a 4 x + a 6 ( a 3 ，q ，只，( d = 0 ) ( 3 ) c h m - ( f ) = 3 时 、 j 2 蔓+ 呸，+ 口6 ( 呸，f ，( e ) o ) ( 2 - 0 l ，= ，+ a s x + a 6 ( a 4 ，a te f ，_ ，( d = 0 ) 当需要设定一条椭圆曲线的方程时，若对域的情况已有所约定，则可以根据 域f 的特征c h a t ( f ) 和j 不变量等情况，选取上面5 个方程式中的一条作为该曲线 的w e i e r s t r a s s 方程进行研究。 2 3 2 椭圆曲线上点的运算 根据代数几何理论，椭圆曲线e 构成一个a b e l 加法群，o 是其单位元。椭圆 曲线上的点对应于a b e l 加法群中的元素。下面给出仿射坐标系下椭圆曲线上点的 运算公式。 ( 1 ) 求逆元 设p = ( 而) ，) e e ，根据w e i e r s t r a s s 方程式，由根与系数的关系易知 - p 2 ( 一y 一日p a 3 ) ( 2 - j 7 ) ( 2 ) 求和 设p 气五，m ) q - - - ( , 吃，y 2 ) e e ，且p 一q ，l 坤+ q ，则点r ( x 3 ，乃) 的坐标为： 铲旯：j q 旷矿而( 2 - 8 ) 【乃= a + q 地一i ，一呜 其中 l 耽一乃 拈 嚣w m 【2 乃+ q 黾+ a 3 y , x 2 - y 2 x x ，q 予( 2 - 1 0 ) 蔓警掣兰等盟，；q 2 乃+ q 西+ a j 叻 - q q q = p p 第1 6 页河南大学研究生硕士学位论文 2 3 3 素数有限域椭圆曲线 素数有限域( p r i m ef i n i t ef i e l d s ) z 。的特征值为c h a r f e ) = p ，其中p 为大于3 的素数。由前文可知，此时的w e i e r s t r a s s 方程式为 y 2 = 矿+ a x + b ( a ，b f ) 且a ( e ) = 4 矿+ 2 7 b 2 m o d p 。 此时，椭圆曲线群上点的运算为： ( 1 ) 逆元公式