（应用数学专业论文）基于pki的混合签密方案研究.pdf

河南大学研究生硕士学位论文第l 页 摘要 信息安全是一切基于计算机网络的通信活动得以正常运行的前提和基础。公 钥基础设施p k i 是一套安全服务的集合，为信息安全提供了一个平台，它运用公钥 密码的基础理论，为网络应用提供诸如认证、授权、加密、解密、数字签名等安 全服务，是一种新的信息安全技术和规范。到目前为止，完善并正确实施p k i 技术 是全面解决所有网络信息系统和通信安全问题的最佳途径。密码技术是信息安全 的核心技术，面对紧迫的形势，加强对密码技术的研究和发展创新具有重要的理 论意义和实用价值。 主要研究内容如下： 第一，利用r s a 公钥密码体制和单向函数，结合现有的一些门限签名思想， 提出一个新的相对安全的签名方案。 第二，通过对已有密码算法的安全性和效率进行分析，以及对p k i 体系进行详 细研究，在此基础上，设计了基于p k i 的混合签密方案。 第三，通过对数字化校园安全需求的分析，提出了一个基于p k i 的网络信息系 统的安全框架，并将所设计的混合签密方案应用于安全数字校园建设。 关键词：公钥基础设施；密码体制；混合签密；r s a 第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 m i s ea n df o u n d a t i o no fa l lc o m m u n i c a t i o n sb a s e do n c o m p u t e rn e t w o r k p u b l i ck e yi n f r a s t r u c t u r e ( p k i ) ，as e to fs e c u r i t ys e r v i c e s ，s u c ha s a u t h e n t i c a t i o n ，a u t h o r i z a t i o n ，e n c r y p t i o n ，d e c r y p t i o n ，d i g i t a ls i g n a t u r e ，e t c ，p r o v i d e sa p l a t f o r mf o ri n f o r m a t i o ns e c u r i t y p k i ，b a s e do np u b l i ck e yc r y p t o s y s t e m ，i san e w i n f o r m a t i o ns e c u r i t yt e c h n o l o g ya n dc r i t e r i o n u pt on o w ，t h eb e s tw a yi ns o l v i n ga l l p r o b l e m so f n e t w o r ki n f o r m a t i o ns y s t e ma n dc o m m u n i c a t i o ns e c u r i t yi sc o n s u m m a t i n g a n de x e c u t i n gp k is y s t e m m o r e o v e r ，c r y p t o g r a p h i ct e c h n i q u ei st h ek e r n e lt e c h n o l o g y o fi n f o r m a t i o ns e c u r i t y i nt h ef a c eo fp r e s s i n g s i t u a t i o n ，e n h a n c i n gs t u d ya n d i n n o v a t i o no f c r y p t o g r a p h i ct e c h n i q u ei si m p o r t a n to nt h e o r ya n da p p l i c a t i o nv a l u e t h em a i ns t u d y i n gc o n t e n ti n c l u d i n g ： f i r s t l y ，u s i n gr s aa l g o r i t h ma n dh a s hf u n c t i o n ，c o m b i n gs o m ee x i s t i n gt h r e s h o l d g r o u ps i g n a t u r e ，p r o p o s e dan e ws a f es i g n a t u r e s e c o n d l y ，w i t ht h er e s e a r c ho ns e c u r i t ya n de f f i c i e n c yo fe x i s t i n gc i p h e ra l g o r i t h m ， a n ds t u d yo np k i ，d e s i g n e da h y b r i ds i g n c r y p t i o ns c h e m eb a s e do np k i t h i r d l y ，b ya n a l y s i n gt h es e c u r i t yd e m a n do fd i g i t a lc o m p u s ，p r o p o s e das e c u r i t y f l a m eo fn e t w o r ki n f o r m a t i o ns y s t e mb a s e do np k i ，a n da p p l i e dt h ed e s i g n e dh y b r i d s i g n c r y p t i o ns c h e m ei n t ot h ec o n s t r u c t i o no fs a f ed i g i t a lc o m p u s k e y w o r d s ：p k i ；c r y p t o s y s t e m ；h y b r i ds i g n c r y p t i o n ；r s a 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位中请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构的学位或证书而 使用过的材料。与我一同工作的同事对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。i? i ：，j j 、r o 学位乎苏i 。靴乏囊轰兰：篁学位乎请水j ( 学位论变炸者) 一签名：二兰! 、j ”一：m “：寥7 ，0 。：；i ：。j ：，j ! 参。蠢，。? - 二。每，渤矿7 年细。，! 日 名 “ ；。1i ， 尊 。一占v 9 。rp 7 、? ! “ 筹 ，j 爹多基l ：0 羹 i ，关于学位论文著作权使用授权书芝 ? 。 i 幺一0 。i 、，j 、一。，、 髫7 j ： ：。 o ，i ”一磐i 。，、i ：o ，一” ”， ，f l ， 本人经河南犬学审核批准授子硕士学位。作为学位论文的作者，本人完全 了解并同意河南丧学有关保留、艘用学位论竞酌要求，即河南大学有权向国家 图书馆、科研信息机构、数据收集机构和本校图书馆等提供学位论文( 纸质文 本和电子文本) 以供公众检索、查阅- o 本人授权河南大学出于宣扬、展览学校 学术发展和进行学术交流等同锄，。可蹦采取影印、缩印、扫描和拷贝等复制手 段保存、汇编学位论文( 纸质文本和电子文本) 。 ( 涉及保密内容的学位论文在解密后适用本授权书) 学住获得者( 学住论文作者) 签名： 学位论文指导教师签 名孛 ；- i 南大学硕士研究生学位论文第1 页 第1 章绪论 随着信息化的发展，信息安全成为全社会的需求，不但关系国家的政治安全、 经济安全、军事安全、社会稳定，也关系到社会中每一个人的数字化生存的质量。 信息安全成为国际社会关注的焦点，是信息化发展中不可缺少的技术基础。 1 1 选题背景 计算机、通信、半导体科学技术的突破，形成了巨大的新型生产力，数字化 的生存方式席卷全球。面对人机结合和非线性、智能化的复杂信息系统，还有许 多科学技术问题需要研究。农业革命、工业革命、信息革命成为了人类历史上生 产力发展的三座丰碑，信息革命给人类带来的高效率和高效益，取决于信息安全 的保障。保证信息的真实性、机密性、完整性和不可否认性已经成为信息安全研 究领域的主要课题。 信息加密技术是保障信息安全的最基本、最核心的技术措施。信息加密主要 是通过数据加密和数字签名来实现的，其中对数据的加密处理主要是为了防止数 据不会被窃听。如果使用非对称加密算法，它还可以保证发送方和接收方身份的 确认。对数据进行加密和数字签名的理论基础是密码算法，它的基本思想是对原 始数据进行复杂的变换，使非法接收者很难从中破译出原始的信息，而合法用户 则可以利用密钥解密密文。 1 2 研究现状 随着信息技术的发展与应用，信息安全的内涵在不断延伸，从最初的信息保 密性发展到信息的完整性、可用性、可控性和不可否认性，发展为“攻( 攻击) 、 防( 防范) 、测( 检测) 、控( 控制) 、管( 管理) 、评( 评估) 等多方面的基础理 论和实施技术。信息安全是一个综合的交叉学科领域，它综合利用数学、物理、 第2 页河南大学研究生硕士学位论文 通信和计算机诸多学科的长期知识积累和最新发展成果，进行自主创新研究，加 强顶层设计，提出系统的、协同的、完整的解决方案。 信息安全的核心和基础是密码学，而密码理论与技术主要包括两部分，即基 于数学的密码理论与技术( 包括公钥密码、分组密码、序列密码、认证码、数字 签名、h a s h 函数、身份识别、密钥管理、p k i 技术等) 和非数学的密码理论与技 术( 包括信息隐藏、量子密码、基于生物特征的识别理论与技术等) 。 加密技术作为保障数据安全的一种方式，起源要追溯于公元前2 0 0 0 年。随着 时问推移，巴比伦、美索不达米亚和希腊文明都开始使用一些方法来保护他们的 书面信息。 近期加密技术主要应用于军事领域。1 9 4 9 年，s h a n n o n 发表了论文“保密系 统的通信理论 ，由此奠定了信息论的理论基础，从而诞生了密码学这一新科学。 1 9 7 6 年，d i f f i eh e l l m a n 发表了“密码学的新方向”，该论文首次证明了发送 方和接收方无共享密钥的保密通信是可能的，由此开创了公钥密码学的新纪元。 到目前为止，国际上已经提出了许多种公钥密码体制，较流行的主要有两类：一 类是基于大整数因子分解问题的，典型的代表是r s a ；另一类是基于离散对数问 题的，比如e 1 g a m a l 公钥密码和椭圆曲线公钥密码。r s a 是著名密码学家r i v e s t 、 s h a m i r 和a d l e m a n 设计出的第一个实用的公钥密码体系。美国国家标准局( n b s ) 于1 9 7 7 年公布了美国数据加密标准d e s ，以其高速率、低开销、实现简单和易于 标准化的特点在密码学中占着十分重要的位置。 1 3 主要研究内容 p k i 体系的建立是各方都非常关注的焦点。由于教育机构的特殊性，不可能采 用国外的p k i 中心，而国内尚未建立一个非常完善的p k i 体系结构和权威的c a 中心及管理规范，那么自主的网络信息的校园p k i 体系是非常有必要和有意义的。 因此基于p k i 技术，结合国内先进加密算法，研制一整套的安全网络信息系统是 河南大学硕士研究生学位论文第3 页 必要的。 本文对密码学中各种数据加密的算法、实现及其特点进行了探讨；介绍了有 关d e s 算法以及r s a 算法所涉及的数学原理和性能分析；讨论分析了基于数据加 密标准( d e s ) 与公钥密码算法r s a 的混合密码算法；设计了基于r s a 和单向函 数的门限群签名方案。最后以p k i 为基础背景，研究p k i 体系架构的选型分析和 设计，不仅设计给出了一个网络信息系统通用的安全框架，并在此基础上给出了 一个合理完善的校园p k i 模型，设计并给出了混合签密体制的算法实现，扩展了 加密算法的应用空间。 1 4 论文体系结构 论文具体安排如下： 第l 章首先阐述本文的研究背景，并对信息安全及信息加密技术的研究现状 进行了介绍。在此基础上确定了本文的研究主旨和内容。 第2 章介绍本文研究内容所涉及的密码学知识及相关数论知识和算法，其中 也包括密码体制和h a s h 函数的相关理论，对涉及的密码算法d e s 和r s a 进行了 分析。 第3 章主要介绍p k i 安全体系，包括p k i 系统组件、认证中心、核心服务、 相关协议标准，并介绍了p k i 的基本功能和开发模式。 第4 章对信息加密算法和签名方案进行研究，根据其特性设计讨论了基于 p k i 的混合签密方案的算法设计，用来实现消息的机密性、完整性和不可否认性。 设计了一种安全的网络信息系统安全框架模型，对校园p k i 进行了模型构造和分 析，并给出了该方案在数字化校园中的应用分析。 本章小结 首先从信息安全的概念和面临的问题入手，介绍了论文的选题背景，然后介 绍了信息安全加密技术的发展和研究现状，提出了本文的研究内容，确定了本文 的研究主旨。最后是本文的体系结构。 第4 页河南大学研究生硕士学位论文 第2 章密码学知识 密码学( c r y p t o l o g y ) 是信息安全的核心技术，是研究密码系统或通信安全的 一门科学。在当今信息时代，大量的敏感信息如病历、资金转移、私人财产等常 常通过公共通信设施或计算机网络来进行交换，而这些信息的秘密性和真实性是 人们迫切需要的。 2 1 基础数学知识 e u c l i d e a n 算法 定义2 1 对任一6 z ，都有一个乘法逆6 ，求解乘法逆6 叫的算法，称为扩 展e u c l i d e a n 算法。算法描述如下： 算法2 1e u c l i d e a na l g o r i t h m ( 口，b ) 卜a 1 卜b m 卜1 w h i l e r m 0 d o 卜酬 r m + 1 卜一1 一q m r m ，押七一，竹+ 1 ，纷七一m 一1 r e t u r n ( q l ，q 。；厂卅) c o m m e n t ：= g c d ( a ，6 ) 河南大学硕士研究生学位论文第5 页 中国剩余定理( c r t ) 假定，m r 为两两互素的j 卜整数( 即当f - ，时，g c d ( m ，m ) = 1 ) 。假定 口1 ，口，为整数，m ：玛坼，m ，：一m ，则同余方程组x = a i ( m 。d 朋，) 有 m ： 唯一解为y = 口f m 乃( m o d m ) ，( 其中m ，乃- - - l ( m o d m ，) l a g r a n g e 插值公式 月+ l 已知一个以次多项式上的n + 1 个点( ， ) ，令缈( z ) = 1 - i ( x - - x i ) ， i = l 1 1 4 i 厂( x ) - - z 仍( 工) y ，其中仍( x ) = 缈( x ) ( o 一薯) 缈( 一) ) ，则( 工) 就是此多项式。 其他结论 定理2 1 若m ，和m 2 互素，则 ( 聊i m 2 ) 2o ( m 1 ) ( ) e u l e r 定理若a 和m 互素，则 矿( ”) = 1m o dn 费尔玛定理若m 是素数，则 a ”= 口m o dm 定义2 2 给定一个正整数，z ，把它叫做模，如果用m 去除任意两个整数a 与b 所得的余数相同，我们就说口，b 对m 同余，记作a 兰b ( m o d m ) 。如果余数不同， 则记为a b ( m o d m ) 。 定理2 2 整数a ，b 对m 同余的充分必要条件是mi 口一b ，即a ：6 + m t ，f 是 整数。 定理2 3 若厶口三吃m ( r o o d m ) ，一- = y ，( m o d m ) ，i = 1 ，2 ，尼， 则 以r q x 户x 兰皖r 以y 卜虻( m o d m ) 。 第6 页河南大学研究生硕士学位论文 特别地，若q 兰b ，( m o d m ) ，i = 1 ，2 ，n ，则 巳z ”+ a n l z ”1 + + a o 兰玩x ”+ 吃一l x ”一1 + + b o ( m o d m ) 定理2 4 ( l a g r a n g e ) 假定g 是一个阶为n 的乘法群，且g g 。那么g 的阶整 除甩。 推论2 1 如果6 乏，那么b 蚋三l ( m o dn ) 。 推论2 2 ( f e r m a t ) 假定p 是一个素数，且6 z 。，那么b p 兰b ( m o dp ) 。 定理2 5 如果p 是一个素数，那么z ：群是一个循环群。 定理2 6 假定p 2 是一个素数，且口z ：。那么口是一个模p 的本原元素当 且仅当a ( p - o q l ( m o dp ) 对于所有满足qi ( p 一1 ) 的素数q 成立【4 1 。 2 2 密码体制 密码学主要包括两个分支，即密码编码学( c r y p t o g r a p h y ) 和密码分析学( c r y p t a n a l y t i c s ) 。密码编码学的主要目的是寻求保证消息保密性或认证性的方法，密码 分析学的主要目的是研究加密消息的破译或消息的伪造。 采用密码技术可以隐蔽和保护需要保密的消息，使未授权者不能提取信息。 被隐蔽的消息称作明文( p l a i nt e x t ) ，隐蔽后的消息称作密文( c i p h e rt e x t ) 或密报 ( c r y p t o g r a m ) 。将明文变换成密文的过程称作加密( e n c r y p t i o n ) ，其逆过程，即由 密文恢复出原明文的过程称作解密( d e c r y p t i o n ) 。加密和解密算法的操作通常都是 在一组密钥( k e y ) 控制下进行的，分别称为加密密钥( e n c r y p t i o nk e y ) 和解密密 钥( d e c r y p t i o nk e y ) 。 根据密码体制所使用的密钥，可以将它分为两类，即对称密码体制与非对称 密码体制【1 7 】。 河南大学硕士研究生学位论文第7 页 2 2 1 对称密码体制 对称密码体制也称为秘密密钥密码体制、单密钥体制或私钥密码体制，其特 点是加密与解密的密钥是相同或等价的，并且密钥是保密并不向外公开的。对称 密码体制的模型如图2 1 所示。 固 i 图2 一l 对称密码体制模型 对称密码体制的安全性依赖以下两个因素。第一，加密算法必须是足够强的， 仅仅基于密文解密信息在计算上是不可能的；第二，加密方法的安全性根本上依 赖密钥的秘密性，而不仅是算法的秘密性。即使算法的秘密性暴露，但由于保证 了密钥的秘密性，依然可以保证加密的效力。对称密码体制对明文信息的加密有 两种方式：一种是明文信息按字符进行逐字符加密，称之为流密码；另一种是将 信息分组( 含多个字符) ，逐组进行加密，称之为分组密码，比较典型的对称密码 有d e s 、i d e a 、a e s 等。 1 数据加密标准( d e s ) 数据加密标准( d a t ae n c r y p t i o ns t a n d a r d ，d e s ) ，作为美国国家标准局( a n s i ) 的数据加密算法( d a t ae n c r y p t i o na l g o r i t h m ，d e a ) 和i s o 的d e a 一1 ，成为世界 范围内的标准，d e s 算法流程如图2 2 所示。 第8 页河南大学研究生硕士学位论文 图2 - 2d e s 密码算法流程 河南大学硕士研究生学位论文第9 页 d e s 算法描述如下： d e s 属于对称密码体制，以6 4 位为分组对数据加密，加密和解密用的是同一 算法，密钥长度为6 4 位( 密钥通常表示为6 4 位的数，但每个第8 位都用作奇偶 校验，可以忽略) 。d e s 的分组方式是先替代后置换，基于密钥作用于明文，所有 的保密性依赖于密钥。d e s 有1 6 轮，这意味着要在明文分组上1 6 次实施相同的 组合技术。 一个6 4 位明文分组x ，通过一个固定初始置换，尸，置换x 获得x o ，记 x o = l e ( x ) = l o r o ，这里l o 是- - x o 的前3 2 比特，r ox o 的后3 2 比特。置换i p 如表 2 1 所示。 表2 1 初始置换i p 1 6 轮完全相同的运算，根据下列规则计算l i r i ，1 i 1 6 ： 在这里，o 表示两个比特的异或，厂是一个函数，k i ( 1 f 1 6 ) 是密钥k 的函 数，我们称它们是子密钥，长度均为4 8 比特。 对比特串r l 。l 。应用初始变换上p 的逆置换伊，获得密文y ，即 y = 1 p 一( r 1 6 l 1 6 ) 。在最后一次迭代后，左边和右边未交换，将墨。厶。作为胪一的输 入，使得算法可同时用于加密与解密。其中初始置换胪的逆置换伊。1 如表2 2 所 示。 、- 、 k r ，- 、 ，0 一 一 尺三 = = 尺 第1 0 页河南大学研究生硕士学位论文 d e s 对称密码体制的加密效率比较高，在软件实现的时候，加密速率每秒钟 可以达到几兆个字节，但是在加密的时候，需要事先交换密钥，在任何密文未发 送之前，通信双方必须利用安全通道进行密钥的预先通信。在这个预先通信的过 程中，要进行严格的保密，而在实际应用中，这个要求是非常困难的。此外对称 密码体制在密钥分配与管理上也是极不方便的。使用对称密码体制进行秘密通信， 显然要求不同用户之间应约定不同的密钥。如果网络上有n 个用户，而这n 个用 户两两之间都需要秘密的交换信息，那么则需要n ( n 1 ) 2 个密钥。这么多密钥的管 理和更换是个非常繁重的工作，而且每个用户必须记下其他n 1 个用户通信所用的 密钥【2 1 。 2 d e s 算法改进 为了增加d e s 密钥的长度，可以将d e s 密码进行级联，在不同的密钥作用下， 连续多次对一组明文进行加密，即采用构造三重d e s 的方法来增强安全性。 三重d e s 是d e s 的一个更安全的变形，它以d e s 为基本模块，通过组合分 组设计出分组加密算法。具体实现如下： 设e t k i ) ( x ) 和b 村) ( x ) ，( f _ 1 ，2 ，3 ) 表示用d e s 算法对6 4 位明文进行加密和解密， k ，为密钥。k l , k 2 ，屯为5 6 位d e s 密钥。 密文c = 臣k 3 ) ( d ( ( 巨 ) ) ) 明文x = d ( k 1 ) ( & k 2 ) ( d ( k 3 ) ) ) ) 河南大学硕士研究生学位论文第11 页 为获得更高的安全性，k l , k 2 ，k ，应不同，这就相当于用一个1 6 8 位的密钥进行 加密。若数据对安全性要求不高，k ，则可以等于毛，则密钥的有效长度位1 1 2 位。 3 d e s 算法安全性 在d e s 算法中，有一个弱密钥( w e a kk e y ) 的概念。将d e s 加密运算记为 d e s ( k ，x ) ( 这里x 表示任意6 4 位的比特串，k 为密钥) ，d e s 解密运算记为 d e s 。1 ( k ，x ) 。如存在一个k ，使得d e s ( k ，x ) = d e s 。1 ( k ，x ) ，则k 为弱密钥； 如存在两个密钥k 和k ，使得d e s ( k ，x ) = d e s 1 ( k ，x ) ，则k 为半弱密钥( 当 然k 也是) 。使用这些密钥，在选择明文攻击下，会使d e s 加密变得很脆弱。由 于d e s 是采用5 6 比特的加密算法，所以总共有2 5 6 种可能的组合，选择到一个弱 密钥的可能性是很小的，不会危及到d e s 的安全性。 用穷举法破译d e s 密码。即给定一段密码文c 及与它对应的明码文m ，用一 切可能的密钥k 加密m ，直到知道一个k 得到d e s ( k ，m ) = c ，这时所用的密钥k 即为要破译的密码的密钥。穷举法的时间复杂性是t = d ( ，z ) ，空间复杂性是 s = d ( 1 ) 。对于d e s 密码，玎= 2 5 6 7 x 1 0 1 6 ，即使使用每秒钟可以计算一百万个密 钥的大型计算机，也需要算1 0 6 天才能求得所使用的密钥，因此看来是很安全的。 s 盒的设计。s 盒的设计原理尚未完全公开，有人怀疑s 盒里隐藏了“陷门 ， 使知道这个密码的人可以很容易地解密。但到目前为止，还没有任何证据能证明 d e s 里确实存在陷门。 补密钥。将密钥的每一位取反，即将所有的0 用1 代替，所有的1 用0 代替。 假设用原来的密钥加密一个明文分组得到个密文分组，那用该密钥的补密钥加 密该明文分组的补便得到该密文分组的补。这表明，对d e s 的选择明文攻击仅需 测试其可能的2 5 6 个密钥的一半，即2 5 5 个就可以了。 第1 2 页；p - i 南大学研究生硕士学位论文 2 2 2 非对称密码体制 非对称密码体制也称为公开密钥密码体制、双密钥密码体制。它使用的加密 钥匙( 又称为公钥) 和解密钥匙( 又称为私钥) 是不同的，且加密钥匙是公开的， 通过加密钥匙计算解密钥匙是困难的。非对称密码体制与以前的密码体制完全不 同，其算法基于数学问题求解的困难性，而不再是基于替代和置换。非对称密码 体制的模型如图2 3 所示。 图2 - 3 非对称密码体制模型 除了使用公开信道进行密钥交换之外，相比于对称密码体制，非对称密码体 制还具有如下特点。第一是依赖于数学难题。对称密码算法的安全性一般依赖于 复杂的混淆和扩散操作，而非对称密码算法的安全性是建立在数学难题上，如大 整数因子分解、离散对数等。第二是计算速度较慢。在相同的安全强度下，非对 称密码算法的速度远远慢于对称算法。因为非对称密码算法中通常会有大整数的 模幂或者乘法计算，所需要的内存和计算量远远大于对称密码算法。第三是密钥 数量少。对于非对称密码算法，每一个用户只需要保存一对公私密钥对，就可以 与其他用户进行保密通信。第四是可以实现非否认服务。由于非对称密码算法的 非对称特性，通信双方所掌握的密钥信息不一样，私钥是用户独立秘密保存的。 甲 河南大学硕士研究生学位论文第13 页 所以使用私钥产生的数据可以用于实现非否认服务的证据。 目前比较典型的非对称密码体系是： ( 1 ) 基于整数因式分解的公钥密码技术，如r s a ( 2 ) 基于离散对数的公钥密码技术，如e l g a m a l ( 3 ) 基于椭圆曲线的公钥密码技术，如e c c 1 公钥密码算法r s a r s a 算法的理论基础是一种特殊的可逆模指数运算。1 9 7 8 年，r l r i v e s t ， a s h a m i r 和l a d l e m a n 发现了一种用数论构造双钥的方法，称作m i t 体制，后来 被广泛称之为r s a 体制，既可用于加密，又可用于数字签名，是目前仍然安全并 且逐步被广泛应用的一种体制。 r s a 公钥密码体制描述如下： 设n = p q 。其中p 和g 为奇素数。设p = e = 瓦，且定义 瓦= ( ，p ，q ，a ，6 ) ：a b 三1 ( m o d ( ) ) 对于k = ( 门，p ，q ，口，6 ) ，定义 e k ( x ) = 夕m o d n 以( y ) = y 。m o d n ( x ，y z ) 。值和b 组成了公钥，且值p ，g 和a 组成了私钥。 其中，r s a 算法描述如下： 密钥生成： 找两个随机的大素数p 和g ，计算n = p q 和( 甩) = ( p 1 ) ( g 1 ) ； 选择随机数e ，满足e 与( 船) 互素； 计算d = e m o d e ( n ) ； 公开( ，z ，e ) 作为公钥，保留( 甩，d ，p ，q ) 作为私钥。 加密： 第1 4 页河南大学研究生硕士学位论文 对于明文p ，计算密文c = p 。m o d n 。 解密： 对于密文c ，计算明文c d = p 甜= p 1 m 州o ( ”) = p m o dn 。 2 r s a 算法中的计算问题 在r s a 公钥密码体制中加密和解密时，都要进行形式为x 8 m o d 胛的运算，如 果对r m o d 玎直接进行计算，中间结果可能很大，超出计算机允许的整数取值范围。 “平方和一乘法 方法将计算x 。m o d n 的模乘法的数目缩4 , - n 至多为2 l ( l 是指数 e 的二进制表示的比特数) 。 如指数e 以二进制形式表位为： l - i c = c f 2 。= c o + c 1 2 + + c l 1 2 卜1 式中c i = 0 或1 ( 0 i l - 2 ) ，c 一l = 1 ，贝0 ： x 。= ( ( ( z 。l 一1 ) 2xx 。l 一2 ) 2 xx c l 一3 ) 2 z 。1 ) 2x x 加 因此，计算r r o o d n 的算法描述如下： 1 z = l ： 2 f o rf = l ld o w n t o0d o ( 1 ) z = z 2 m o d n ( 2 ) i fc i = 1 ，t h e nz = z x 在第2 步( 1 ) 中总要执行l 次平方运算，在第2 步( 2 ) 中进行模乘法的次 数等于c 的二进制表示中1 的个数，在0 与l 之间。因此模乘法的总是至少为l 次，至多为2 l 次。 r s a 算法的实际使用，一般需要有如下考虑： ( 1 ) n 的长度 在实际使用的r s a 算法中，通常所说的r s a 算法密钥长度就是指n 的有效长 度度，通常是1 2 8 b i t 、2 5 6 b i t 、5 1 2 b i t 或1 0 2 4 b i t 。 河南大学硕士研究生学位论文第15 页 ( 2 ) e 的选取 通常情况下，在实际使用中e 的取值很小，有效长度不超过3 2 比特，甚至在 很多时候，e 都等于6 5 5 3 7 ( 十六进制表示为0 x 1 0 0 0 1 ) 。 ( 3 ) 数据填充 r s a 算法能够直接处理长度不大于n 的明文。对于1 0 2 4 比特的r s a 密钥， 可以直接加密长度不大于1 0 2 4 比特的明文消息。为了保证安全性，在实际使用中 会在明文的高位比特填充一定长度的数据，然后再进行计算。 3 r s a 算法安全性 r s a 的安全性是基于大整数的素分解问题的难解性，目前尽管尚未从理论上 证明大整数的素分解问题是难解问题，即在数学上从未证明过需要分解n 才能从c 和e 中计算出m ，但迄今为止还没有找到一个有效算法的事实，使得大整数的素分 解问题成为众所周知的难题，这是r s a 的基础。也可通过猜测( p 一1 ) ( g 一1 ) 的值来 攻击r s a ，这种攻击还没有分解n 容易。对密码分析者而言，他有可能尝试每一 种可能的d ，直到获得正确的一个。这种穷举攻击还没有试图分解刀更有效。1 9 9 3 年w i l l i a mp a y n e 的论文草案提出了一种基于费尔马小定理的方法，但它的速度仍 比分解模数要慢。如果r s a 的模数n 被成功分解为p ，q ，则立即可算出 o ( n ) = ( p 一1 ) ( g 一1 ) 和d ，因此攻击成功，而且分解n 也是攻击r s a 最显然的方法。 随着计算能力的不断提高和分解算法的进一步改善，原来认为不可能被分解的大 数可以被成功分解，因此为了抵抗现有的整数分解算法，保证算法的安全性，对p ，g 的选取提出了以下要求： ( 1 ) i p - q l 很大，通常p 和q 的长度相同； ( 2 ) p - 1 和日一1 分别含有大素因子p 。和q 。； ( 3 ) p l - 1 和仍一1 分别含有大素因子见和q 2 ； ( 4 ) p + 1 和g + 1 分别含有大素因子见和9 3 。 第1 6 页河南大学研究生硕士学位论文 4 r s a 的速度 硬件实现时，r s a 比d e s 慢大约1 0 0 0 倍。最快的具有5 1 2 位模数的v l s i 硬件实现吞吐量为6 4 k 位秒，也有一些实现1 0 2 4 位r s a 的加密芯片。先进设计的 具有5 1 2 位模数的芯片可达到1 m 位秒，该芯片在1 9 9 5 年制成。在智能卡中已开 始采用r s a ，这些实现都较慢。 软件实现时，d e s 大约比r s a 快1 0 0 倍。这些数字会随着技术发展而发生相 应的变化，但r s a 的速度将永远不会达到对称算法的速度，表2 3 中给出了r s a 软件速度的实例。 表2 3 具有8 位公开密钥的r s a 对于不同长度模数的加密速度 5 1 2 位7 6 8 位10 2 4 位 加密0 0 3 秒0 0 5 秒o 0 8 秒 解密0 1 6 秒0 4 8 秒0 9 3 秒 签名0 1 6 秒0 5 2 秒o 9 7 秒 验证o 0 2 秒o 0 7 秒 o 0 8 秒 如果选择一个恰当的e 值，r s a 加密速度将快很多。最常用的三个e 值是3 ， 1 7 和6 5 5 3 7 ( 2 1 6 + 1 ) 。x 5 0 9 中建议采用6 5 5 3 7 ，p e m 中建议采用3 ，p k c s # 1 中建 议采用3 或6 5 5 3 7 。即便是一组用户使用同样的e 值，采用这三个值中的任何一个 都不存在安全问题，也可使用随机数填充消息【3 2 】。 2 3h a s h 函数 h a s h 函数h 是一个公开函数，用于将任意长的消息m 映射为较短的、固定长 度的一个值h ( m ) ，称函数值h ( m ) 为消息m 的消息摘要。消息摘要h ( m ) 是消息m 中所有比特的函数，它提供了一种错误检测能力，即改变消息m 中的任何一个比 特或几个比特，h ( m ) 都会发生变化。 河南大学硕士研究生学位论文第17 页 1 h a s h 函数分类 根据h a s h 函数的安全水平，将h a s h 函数分为两类：强无碰撞的h a s h 函数和 弱无碰撞的h a s h 函数。 强无碰撞的h a s h 函数是满足下列条件的一个h a s h 函数h ： ( 1 ) h 的输入可以是任意长度的任何消息或文件m ； ( 2 ) h 的输出长度是固定的； ( 3 ) 给定h 和肘，计算办( m ) 是容易的； ( 4 ) 给定h ，和一个随机选择的z ，寻找消息m ，使得矗( m ) = z ，在计算上 是不可行的。这一性质称为函数的单向性。 ( 5 ) 给定h ，找两个不同的消息m 和心，使得h ( m 。) = 办( 鸠) ，在计算上是 不可行的。 弱无碰撞的h a s h 函数是满足下列条件的一个h a s h 函数h ： ( 1 ) h 的输入可以是任意长度的任何消息或文件m ； ( 2 ) h 的输出长度是固定的； ( 3 ) 给定h 和m ，计算h ( m ) 是容易的； ( 4 ) 给定h ，和一个随机选择的z ，寻找消息m ，使得向( m ) = z ，在计算上 是不可行的。 ( 5 ) 给定h ，和一个随机选择的消息m ，找另一个不同的消息旭，使得 办( m ) = 向( m 2 ) ，在计算上是不可行的。 由强无碰撞的h a s h 函数和弱无碰撞的h a s h 函数的定义可知，强无碰撞的h a s h 函数的安全性要比弱无碰撞的h a s h 函数的要好f 2 】。 2 h a s h 函数构造方法 ( 1 ) 基于对称分组算法的h a s h 函数 把分组算法作为h a s h 函数，最显而易见的方式是使用分组算法c b c 或c f b 方式，以一个固定的密钥和一个初始向量，y 加密消息，将最后的密文作为h a s h 第1 8 页河南大学研究生硕士学位论文 函数值。 基于对称分组算法的h a s h 函数描述如下： 设x 是一个串，通过某种填充方式将x 填充成长度为行的倍数的串。 假定工= 而1l 而li - il x n ，其中_ ( f = l ，f ) 的二进制表示长度为，z ，利用 分组算法构造h a s h 函数的基本做法是给定一个初始的值h o = i v ， 根据下列规则依次构造。，h 2 ，q ： h ，= f ( x f ，h f _ 1 ) 其中函数厂是由分组密码体制的加密函数来确定。然后将一作为函数值。 下面给出了几种构造方案： h i = e h i 。( x , ) e x i h ，= e m 。( 一) o 一0 h f - l h i2e h h b i 0h i o q x t 日，= e 以。( oh j 1 ) o 薯0h i l ( 2 ) 基于非对称算法的h a s h 函数 假如非对称算法使用分组链接模式工作，那么它作为h a s h 函数是可能的。没 有解密密钥破译将与没有解密密钥恢复明文一样困难。 基于非对称算法的h a s h 函数描述如下： 消息m ，刀为两个大素数p 和q 的乘积，e 是一个与( p 一1 ) ( g 1 ) 互素的大数， h a s h 函数日( 脚) ，定义如下： ( 册) = m 。m o d n 破译这个问题可能与解决e 的离散对数问题同样困难。 ( 3 ) 直接构造方法 直接构造法不基于任何密码体制和任何困难性问题假设，而是直接构造h a s h 函数。这样构造的h a s h 函数速度很快，并且易于实现。 河南大学硕士研究生学位论文第19 页 目前使用的h a s h 函数有：m d 2 、m d 4 、m d 5 、h m a c 、s h a 、s h a 1 。m d 5 ( m e s s a g ed i g e s ta l g o r i t h m - 5 ) 算法是由r r i v e s t 设计的，在r f c l 3 2 1 中描述。 m d 5 按5 1 2 位数据块为单位来处理输入，产生1 2 8 位的消息摘要。 s h a ( s e c u r eh a s ha l g o r i t h m ) 算法是由美国国家技术标准协会( n i s t ) 开发， 并在1 9 9 3 年作为信息处理标准公布。s h a 与m d 5 的设计原理相似，同样也按5 1 2 位数据块为单位来处理输入，但它产生1 6 0 位的消息摘要，具有比m d 5 更强的安 全性【1 8 1 。 本章小结 本章主要介绍本文涉及的相关基础数学知识和密码学知识，中国剩余定理在 数论中主要用来解同余方程组；欧几里德算法主要是解决两个整数的最大公因子 的问题，并介绍了密码体制的分类，分析了涉及的d e s 和r s a 算法，并对h a s h 函数的分类和构造进行了介绍和分析。 第2 0 页河南大学研究生硕士学位论文 第3 章p ki 安全体系 互联网的发展和信息技术的普及，给人们的工作和生活带来了前所未有的便 利，然而由于互联网所具有的广泛性和开放性，决定了其不可避免地存在着信息 安全隐患。为了防范信息安全风险，许多新的安全技术和规范不断涌现，p k i 便是 其中一员。 p k i 是在公开密钥理论和技术基础上发展起来的一种综合安全平台，能够为所 有网络应用透明地提供采用加密和数字签名等密码服务所必需的密钥和证书管 理，从而达到保证网上传递信息的安全、真实、完整和不可抵赖的目的。 3 1p k i 定义 p k i 是p u b l i ck e yi n f r a s t r u c t u r e 的缩写，即公开密钥基础设施，是指用公开密 钥的概念和技术来实施和提供安全服务的具有普适性的安全基础设施。这个定义 说明，任何以公钥技术为基础的安全基础设施都是p k i ，利用非对称密码学的优势， 通过基础设施的工程概念，利用标准的接口为用户提供真实性、保密性、完整性 和不可否认性的安全服务。到目前为止，仍没有一种技术能够完全替代p k i 技术 来提供如此全面的安全服务。 美国国家审计总署在2 0 0 1 年和2 0 0 3 年的报告中都把p k i 定义为由硬件、软 件、策略和人构成的系统，当完善实施后，能够为敏感通信和交易提供一套信息 安全保障，包括保密性、完整性、真实性和不可否认性。尽管这个定义没有提到 公开密钥技术，但到目前为止，满足上述条件的也只有公钥技术构成的基础设施【l 】。 p k i 的优势主要表现在以下几个方面： 1 采用公开密钥密码技术 采用公开密钥密码技术，能够支持可公开验证并无法仿冒的数字签名，从而 在支持可追究的服务上具有不可替代的优势。这种可追究的服务也为原始数据的 河南大学硕士研究生学位论文第2 1 页 完整性提供了更高级别的保证。 2 保护机密性 由于密码技术的采用，p k i 可以实现保护机密性，不仅能够为相互认识的实体 之间提供机密性服务，同时也可以为陌生的用户之间的通信提供保密支持。 3 采用数字证书方式进行服务 p k i 采用数字证书方式进行服务，即通过第三方颁发的数字证书证明末端实体 的密钥，而不是在线查询或在线分发。这种密钥管理方式突破了过去安全验证服 务必须在线的限制。 4 提供证书撤销机制 p k i 提供了证书的撤销机制，从而使得其应用领域不受具体应用的限制。撤销 机制提供了在意外情况下的补救措施。有了撤销技术，不论是永远不变的身份， 还是经常变换的角色，