目录
第一章绪论 (1)
1.1 研究背景与意义 (1)
第二章预备知识 (7)
2.1 复杂性理论 (7)
2.2 可证明安全理论 (8)
2.2.1 困难问题假设 (8)
2.2.2 形式化证明方法 (10)
2.3 公钥密码体制 (11)
2.3.1 PKE形式化定义 (11)
2.3.2 PKE的安全模型 (12)
2.5 密钥泄露 (12)
2.5.1 问题描述 (12)
2.5.2 解决方法 (13)
2.6 本章小结 (14)
致谢 (16)
第一章绪论
第一章绪论
本章主要阐述了公钥密码体制的研究背景和积极意义，并简单介绍了代理重加密体制的研究现状以及该密码体制在云存储数据共享领域的独特优势。最后，本章介绍了本文的主要研究工作和论文结构。
1.1 研究背景与意义
密码学是伴随着信息保密而产生的，但是随着密码学技术本身的不断发展和通信网络技术的不断发展，现代的密码学研究已经远远超越了信息保密的范围，被广泛应用于各种安全和隐私保护应用之中。它是一门古老的学科，又是一门新兴的交叉学科，在今后人类社会的发展历程中必将发挥越来越重要的作用。密码学的发展可分为3个阶段：
第一阶段：从古代一直到1949年，密码学都是停留在应用于军事政治等神秘领域的实践技术。从1949年香农（Shannon）发表了《保密系统的信息理论》错误！未找到引用源。后，密码学才由理论基础指导而上升为学科。这一阶段，密码学研究的突破并不大，而且应用方面仍然只局限于特殊领域。
第二阶段：以1976年迪菲（Diffie）与赫尔曼（Hellman）发表的论文《密码学的新方向》错误！未找到引用源。以及1977年美国发布的数据加密标准（DES）加密算法为标志，密码学进入了现代密码学。
第三阶段：伴随着相关理论的完善，以及由集成电路和因特网推动的信息化工业浪潮，密码学进入了一个全新爆发的时代：研究文献和成果层出不穷，研究的方向也不断拓展，并成为了一个数学、计算机科学、通信工程学等各学科密切相关的交叉学科，同时各种密码产品也走进了寻常百姓家，从原来局限的特殊领域进入了人民群众的生产、生活之中。
在信息社会，加密体制为保证信息的机密性提供了重要的技术手段。根据密钥的特点，可将加密体制分为对称密钥体制和非对称密钥体制两种。在对称加密体制中，通信双方为了建立一个安全的信道进行通信，需要选择相同的密钥，并将密钥秘密保存。根据对明文的加密方式不同，对称密码算法又分为分组加密算法和流密码算法。分组加密算法将明文分为固定长度的分组进行加密，而流密码算法则将明文按字符逐位加密，二者之间也不是有着不可逾越的鸿沟，很多时候，分组加密算法也可以用于构建流密码算法。目前，世界上存在的分组密码算法可能有成千上万种，而其中最有名的就是美国的DES、AES以及欧洲的IDEA算法。
电子科技大学硕士学位论文
相对于对称体制中的密钥必须保密，非对称密钥体制有一个可公开的公钥为其最大特征，因此也叫公钥密码体制。在非对称密码体制中，不再有加密密钥和解密密钥之分。可以使用公钥加密，而用私钥解密，这多用于保护数据的机密性；也可以用私钥加密而公钥解密，这多用于保护信息的完整性和不可否认性。1976年，公钥密码体制（Public Key Cryptography，PKC）的概念被Diffie和Hellman错误！未找到引用源。首次提出。PKC在整个密码学发展历史中具有里程碑式的意义。随后出现了一些经典的公钥密码体制，比如RSA错误！未找到引用源。Rabin 算法错误！未找到引用源。ElGamal错误！未找到引用源。密码体制和椭圆曲线密码体制错误！未找到引用源。错误！未找到引用源。错误！未找到引用源。等。公钥密码体制的安全性依赖于不同的计算问题，其中RSA密码体制基于大整数分解的困难性，而ElGamal密码体制则基于离散对数问题的困难性。
在密码系统中，安全的核心是密钥，一个安全系统无论设计得多么完美，如果其中的密钥安全没办法保证，则整个系统的安全也将是空中楼阁。在实际应用中，非对称密钥管理主要通过公钥基础设施（Public Key Infrastructure，PKI）来对用户的公私钥对进行管理，而且非对称与对称两种体制的密码管理往往是结合在一起使用的。但是，基于PKI的公钥密码系统存在计算开销昂贵的公钥证书管理问题。为避免此问题，Shamir在1984年率先提出了基于身份的公钥密码体制错误！未找到引用源。（Identity-based Cryptography，IBC）的概念，2001年，第一个安全实用的基于身份公钥加密（Identity-based Encryption，IBE）方案才由Boneh和Franklin错误！未找到引用源。基于椭圆曲线上的双线性对构造而来。与基于PKI的传统公钥密码体制相比，IBC不存在繁琐的公钥证书管理问题，用户公钥由惟一标识用户身份信息的ID推导而来，其私钥则是由可信第三方密钥生成中心（Key Generation Center，KGC）生成。诚然，IBC避免了传统PKI中证书管理问题，但由于KGC的存在，使得该密码体制无法摆脱密钥托管问题。随后，Al-Riyami和Paterson错误！未找到引用源。于2003年首次提出了基于无证书的公钥密码体制（Certi?cateless Public Key Cryptography，CL-PKC）的概念，该密码体制不仅可以消除PKI中存在的证书管理问题，也可以克服IBC中存在的密钥托管问题，即CL-PKC继承了IBC的优点而克服了其缺点。此后，多个无证书公钥加密（Certi?cateless Public Key Encryption，CL-PKE）方案错误！未找到引用源。错误！未找到引用源。错误！未找到引用源。被提出。
尽管公钥密码体制已被广泛应用于社会各领域，但公钥密码学依然要不断发展以适应社会的进步。如今，云计算作为一种新兴服务模式，能够方便地为远程用户提供计算和存储资源，从而节省本地开销。一旦数据拥有者将数据上传给半可信的云服务提供商（Cloud Service Provider，CSP），将失去对数据的控制权。因此，出于安全考虑，数据拥有者在上传数据之前需要对数据进行加密处理。考虑
2
第一章绪论
如下场景错误！未找到引用源。错误！未找到引用源。错误！未找到引用源。：数据拥有者Alice希望将其外包在云服务器中的敏感数据与其他用户Bob共享，除了Bob，包括CSP在内的任何人都无法解密这些共享数据。Alice直接将其私钥告知Bob是不可取的，最简单、安全的方法是Alice先将云中数据下载到本地并解密，然后将解密后的消息再用Bob 的公钥加密并发送给Bob，此时，Bob可以利用其自身私钥获得共享数据。显然地，此方法牺牲了数据拥有者的计算开销、通信带宽以及本地存储资源，这不符合用户通过云计算节省资源开销的初衷，因此，传统的公钥密码方案无法解决云存储数据安全共享问题。
为此，代理重加密（Proxy Re-Encryption，PRE）——一种具备安全转换功能的密码系统，能够有效地实现云存储数据安全共享。在PRE密码系统中，一个半可信代理者扮演着密文转换的角色，它可以将由Alice公钥加密的密文转换为由Bob公钥对同一明文加密的密文，然后Bob可利用其自身私钥解密该转换后的密文。因此，通过利用PRE的思想，当Alice收到Bob的共享请求后，Alice产生一个代理重加密密钥并将该密钥发送给CSP。后者利用该代理重加密密钥能够将Alice存储在云端的外包数据转换为由Bob公钥加密的密文，而无法获知共享数据的内容。然后，Bob可用其自身私钥解密这些共享数据。在共享过程中，数据拥有者无需将数据下载到本地，从而节省开销。此后，代理重加密成为密码学与信息安全领域的一个研究热点，积累了大量研究成果，且在云计算错误！未找到引用源。错误！未找到引用源。错误！未找到引用源。、数字版权管理错误！未找到引用源。错误！未找到引用源。、加密电子邮件转发错误！未找到引用源。、分布式文件系统错误！未找到引用源。错误！未找到引用源。、加密病毒过滤错误！未找到引用源。错误！未找到引用源。等领域的应用前景广阔。
2003年，基于密钥分享机制，Ivan和Dodis错误！未找到引用源。给出了构造单向代理重加密方案的一般方法，即用户私钥被分割成两份，一份分发给代理者，另一份分发给被委托者。
2005年，Ateniese等人错误！未找到引用源。首次形式化地描述了代理重加密及其安全模型，并设计出第一个基于双线性对的单向代理重加密方案。
Deng等人错误！未找到引用源。提出第一个不依靠双线性对、可证明CCA安全的双向代理重加密方案。
2012，Hanaoka 等人错误！未找到引用源。在CT-RSA会议上给出了一个更强的代理重加密安全模型，并给出了一个通用方法用于构造CCA安全的单向代理重加密方案。Sun等人错误！未找到引用源。提出了第一个CCA安全的单向广播代理重加密（Broadcast PRE，BPRE），该方案在标准模型下满足自适应选择密文安全。
在AsiaCCS 2009会议上，Weng等人错误！未找到引用源。第一次介绍了条件代理重加
电子科技大学硕士学位论文
4
密（C-PRE ）的概念，当且仅当密文满足委托者设置的条件时。
在CT-RSA 2009上，密钥隐私代理重加密（key-private PRE ，K-PRE ）的概念由Ateniese 等人错误！未找到引用源。提出，
2010年，Yau 错误！未找到引用源。和Shao 等人错误！未找到引用源。分别提出了带关键字的代理重加密（PRE with keyword research ，PRES ）的概念，并构造出具体方案。
针对代理重加密密钥的安全性，Yang 等人错误！未找到引用源。利用可信计算来解决代理重加密中转换钥泄露的问题。为了对代理者的密文权限进行控制，Tang 等人错误！未找到引用源。提出基于类型代理重加密（Type-based PRE ）的概念，该密码系统能够使代理者只转换部分委托者的密文。
Setup ：KGC
以安全参数作为Setup 算法的输入，然后，KGC 返回一个系统主密钥mk 和一组公开参数params ；
在一个无证书的密码系统中，用户的私钥是由KGC （Key Generation Center ）生成的部分私钥和由用户选择的秘密值组成的。
Game I （Type I 敌手）
：该游戏为敌手和挑战者之间进行的安全游戏。初始化阶段：挑战者以一个安全参数作为Setup 算法的输入,然后返回一组系统公
开参数params 和一个主密钥mk 。
且ID
没有被
询问过
或
。如果
，选取，计算挑战密文Encrypt(params ,
,,)，然后，
返回给一个挑战密文。
PRE 方案并不直接用于加密数据拥有者的外包数据，而是利用对称加密算法保护用户数据的机密性，否则就会使得该协议非常低效。因此，本章利用PRE 来处理协议中使用的对称加密算法的对称密钥。
数据接收者需要先利用其自身私钥解密出对称密钥，接着再使用得到的对称密钥解密出共享数据。
一个CKI-PRE 方案由多项式时间算法Setup 、UserKeyGen 、CertGen 、SetInitialKey 、UpdH 、UpdS 、SetReKey 、Encrypt 、ReEncrypt 以及Decrypt 组成。
密码学是以研究保密通信为内容的学科，是信息安全的核心。密码学中用提供信息安全服务的密码学原语称为密码体制。密码体制提供的基本安全服务有机密性、完整性、认证和不可否认下。机密性是指信息只为授权用户使用，不能泄露给未授权的用户。完整性是指信息在传输或存储过程中，不能被偶然或蓄意的删除、修改、伪造、重放、插入等破坏和丢失的特性。认证时确保通信方的确是他所声称的那位。加密可以看作是一种变换，这种变换将可读的明文信息变换为
第一章绪论
不可读的密文信息。数字签名也是一种基本的密码原语，它可以取得完整性、认证和不可否认性。
显示一个密码体制安全的现代方法是可证明安全性。可证明安全性的目的在于证明：如果一个敌手能够攻破一个密码体制的某个安全概念，那么就可以利用该敌手解决某个工人的数学困难问题。例如，如果一个敌手能够在选择密文攻击下攻破RSA的语义安全性，那么就可以利用该敌手分解大整数；
可证明安全的思想就是给定一个算法A，提出一个新算法C，C把A作为子程序。输入给C的是希望解决的困难问题，输入给A的是某个密码算法。然而，如果A是一个积极攻击敌手（选择密文攻击敌手或者适应性选择密文攻击敌手），即A可以对输入公钥进行解密预言机询问或签名预言机询问。算法C要想使用A 作为子程序，就得对A的询问提供回答。算法C需要应对以下四个问题：为了回避这个问题，可以使用随机预言机模型。随机预言是一个理想的Hash 函数。对于每一个新的询问，随机预言产生一个随机值作为回答，如果问相同的询问两次，那么回答仍然相同。在随机预言机模型中，假设敌手并不使用密码算法中定义的那个Hash函数。也就是所，即使将随机预言换成真实的Hash函数。敌手A也是成功的。对于A的解密预言询问或者签名预言询问，算法C是通过欺骗随机预言的回答来适合自己的需要的。
随机预言模型为证明密码体制的安全性提供了一个很好的方法，但是随机预言模型并不反映真实世界的计算。在随机预言模型下安全的密码体制只能说是可能在真实的世界是安全的，不能确保一定在真实的世界是安全的。文献给出了在随机预言模型下安全的密码体制在真实的世界中不安全的例子。许多密码学研究者开始设计在标准模型（不依赖于随机预言模型）下安全的密码体制。移除随机预言模型是需要代价的，通常需要更强的困难问题假设，而且在标准模型下的密码体制通常效率较低。
选择密文攻击：选择密文攻击也称为午餐时间攻击，是一种比选择明文攻击稍强的攻击模型。在选择密文攻击中，敌手可以访问一个黑盒，这个黑盒能进行解密。在午餐时间，敌手可以选择多项式个密文来询问解密盒，解密盒把解密后的明文发送给敌手。在下午时间，敌手被告知一个目标密文，要求敌手在没有解密盒帮助的情况下解密目标密文，或者找到关于明文的有用信息。
适应性选择密文攻击：是一种非常强的攻击模型。除了目标密文之外，敌手可以选择任何密文对解密盒进行询问。目前普遍认为，任何新提出的公钥加密算法都应该在适应性选择密文攻击下达到多项式安全性。、
有了安全目标和攻击模型，就可以给出公钥加密体制的安全性定义了。
电子科技大学硕士学位论文
公钥加密体制的选择明文攻击游戏由下面三个阶段组成，这是一个挑战者C 和敌手A之间的游戏。
初始阶段：C运行密钥生成刷法生成一个公钥、私钥对。C将pk发送给A并且保密sk。
挑战阶段：A产生两个相同长度明文m0和m1并将它们发送给C。C随机选择一个比特，并计算
6
第二章 预备知识
第二章 预备知识
数学理论是现代密码学建立和发展的基础，包括复杂性理论、可证明安全理论等，这些理论中的许多概念在设计密码算法时是必不可少的。本章主要介绍本本文中可能会用到的一些基本概念和结论。
2.1 复杂性理论
在计算机中，某一个算法执行的时间是以比特运算的形式来测量的。为完成某一个算法而需要的必要的比特运算数量，称为这个算法的计算复杂性或简称复杂性。它确切定义了求解一个问题是计算“容易”还是“困难”的，并由此对问题和算法的复杂性加以分类。由于算法的计算复杂性是正整数的函数，因此要比较两个算法的计算复杂性主要是比较当x 充分大时，它们随x 增大而增大的数量级。
定义 2.1 设f 和g 是两个正整数函数，若存在正整数和常数c ，使得当
时，则将
记作
，或简写为。
是对算法复杂性的一个数量级分类，它表示算法所需的比特运算次数的上界，与计算机的操作时间，运行速度等固有的性质无关。在复杂性的分析过程中，我们需要知道执行某个算法的确切的比特运算次数。
计算机执行某个算法所需的时间，是和比特元素的数量成正比的。这个比例常数和计算机的性能有关。在执行一个算法的过程中，基本的时间估计是多项式
时间的，或简称多项式的。也就是说，一个算法的复杂性是，其中是常数，n 是算法的输入长度且c 与n 无关，则称这个算法是多项式的。一般来说，由于这些算法是最快的算法，因此它们都是可取的，即多项式时间算法是有效的算法。多项式时间算法是对基本的加、减、乘、除运算而言的算法。然而，有些
算法的复杂性是，其中，c 为常数且f
是一个关于
的多项式，则这种算法称为指数时间算法，或简称为指数的。一个亚指数时间算法
是
，其中，
，，c
为常数表示
满足
的函数
。亚指数时间算法要比指数时间算法快，但是落后于多项式时间算法。例如：对于
，若n
是素数，则用次除法即可证明。
假设输入算法的最大比特长度为
，则，这是指数时
间算法。若一个算法的复杂性为，其中c
为常数，是介于常数和线性函数之间的函数，称该算法为超多项式时间算法。对现在已知的密码体制有效的攻击算法都是超多项式时间算法，但是并没有证明不存在有效的多项式时间攻击
电子科技大学硕士学位论文
8 算法。 下面给出关于的一些性质：假定f 和g 是正多项式，则有
(1) 若
，则有； (2)
；
(3)
。 证明：（1）
若
，
则存在常数和正整数，
使得当
时，
。因此，
，可得
，即。 （2
）令，
，则存在和正整数，使得当
时，
，
。因此，
，
，故可得。 （3
）令，
，则存在和正整数，使得当时
，
，
。因此
，，
即。
上述性质中的（1）是（3
）在
下的特殊情况。同样，如果，则对任意的，成立。 2.2 可证明安全理论
本小节将列出本文可能涉及的各类困难问题，如无特殊说明，均假设这些问题是难解的，并称为对应的困难问题假设。然后，介绍形式化证明方法。
2.2.1 困难问题假设
群：S
是一个非空集合，
表示异或操作，
表示一个群，如果 (1)
闭包：
；
(2)
结合性：
； (3)
恒等性：
； (4)
反身性：
。 阶：一个群中元素的个数称为阶。 循环群：令为阶为q
的群，各不相同，则称为循环群，g 为群的生成元。
定义 2.2 已知一个阶为素数q 的群，生成元为P 。DL(Discrete Logarithm)
难解问题是对任意已知元素
，有
，求整数。离散对数假设意味着在群
上的离散对数困难问题不能够被敌手以不可忽略的概率解决。
定义 2.3
令为一个阶为q
循环乘法群，群上的CDH （Computational
第二章 预备知识
Diffie-Hellman
）问题是已知二元组
（未知）
，求解
。设在时间t 内敌手
成功输出的概率为：，其中是可忽略的。如果可忽略不计，则CDH
问题是是难解的。
定义 2.4 令为一个阶为q
循环群，已知
，其中不可
知，判断输出与是否一致，即DDH （Decisional Diffie-Hellman ）难
解问题。DDH 假设意味着在多项式时间t 内任意攻击者能够
以
的概率解决DDH 问题，
其中是可忽略的，则称DDH
问题是难解的。
定义 2.5 令为一个阶为q
循环群，已知
，求解，即s -CDH （s -Computational Diffie-Hellman
）难解问题，其中是在中随机选择的。特别地，当s =2时，称s -CDH 问题称为平方-CDH 问题。
定义 2.6 令为一个阶为q
循环群，已知
，其中是不可知的，P -CDH
问题意味着计算
是困难的。 定义 2.7
令
为一个阶为q 循环群，已
知，其
中是不可知的，P -DDH
问题意味着判断是否成立是困难的。
定义 2.8
如果映射
满足如下性质，则认为该映射是一个双线性映射（Bilinear Map ）：
(1)
都代表群，且具有相同的素数阶q ；
(2)
对所有的
，
，等式
成立； (3)
该映射是非退化的，即
； (4) 映射e 是高效可计算的。
一般地，Weil 对错误！未找到引用源。和Tate 对错误！未找到引用源。可被用于构建双线性映射e 。 定义 2.9
令
为循环加法群，阶为q ，生成元为P
，已知，其
中
是不可知的，求解
，即中的CDH 问题。 定义 2.10
令为循环加法群，阶为q ，生成元为P ，
已知，
其中
是不可知的，
然后判定等式
是否满足，
即中的DDH 问题。
定义 2.11
令
为循环加法群，阶为q ，生成元为P ，在DDH 预言机的协助
下，求解已知元组
的CDH 问题，即GDH （gap Diffie-Hellman ）问题。
定义 2.12
令为循环加法群，阶为q ，生成元为P ，已
知
，求
解，即q -SDH （q-strong
电子科技大学硕士学位论文
10
Diffie-Hellman ）问题。
定义 2.13
令
为循环加法群，为循环乘法群，阶都为q
，双线性映射
以及群生成元为P
，已知
，其中
是不可知的，求解
，即BDH （Bilinear Diffie-Hellman ）问题。 定义 2.14
令
为循环加法群，为循环乘法群，阶都为q
，双线性映射
以及群生成元为P
，已知
，
，其中
是不可知的，判定等式是否成立，即DBDH （Decisional
Bilinear Diffie-Hellman ）问题。 定义 2.15
令
为循环加法群，
为循环乘法群，阶都为q
，双线性映射
以及群生成元为P ，在DBDH
预言机的协助下，计算已知
的BDH 问题，即GBDH （gap Bilinear Diffie-Hellman ）问题。
2.2.2 形式化证明方法
在可证明安全理论中，形式化安全模型被用来评估一个密码系统的安全性。一个形式化的安全模型包含两个定义错误！未找到引用源。错误！未找到引用源。：一方面，它必须指出一个任意概率的攻击者如何与密码系统中的合法用户进行多项式时间的交互；另一方面，它必须说明该攻击者要达到哪些目的，才能认定该密码系统被攻破。一般来说，有两种方式来描述形式化的安全模型。
一种是基于游戏（game-based ）的方式。在这种形式化安全模型中，攻击者需要与一个假定的概率算法，也就是挑战者，进行交互。挑战者生成密码系统中使用的所有密钥，可能响应来自攻击者的询问。当攻击者终止时，游戏结束，然后，评估此时的攻击者是否具备破坏该密码系统的能力。如果一个密码系统被证明是安全的，那么我们必须给出说明任意一个攻击者能够攻破该密码系统的概率都非常小。基于游戏的安全模型已经被广泛接受，且已被应用于多种类型的密码系统的安全性证明，包括数字签名、非对称加密和对称加密。本文所描述的形式化安全模型都是基于游戏的安全模型。
基于游戏的安全模型的优点是容易理解和实现。然而，Canetti 等错误！未找到引用源。发现基于游戏安全模型下的安全性证明只能独立的证明密码系统的安全性，无法说明当该密码系统部署于复杂环境下时也是可证明安全的。大部分密码方案都不是独立存在的，而是作为大型计算机系统的子程序。在这种情况下，为了确保所使用的密码算法的安全性，必须要在给定的复杂环境下进行安全性证明。因此，对于基于游戏的安全模型而言，它往往难以更好的表述大型复杂环境的安全需求。
另一种是基于仿真(simulation-based )的方式。在基于仿真的安全模型下，假设
第二章 预备知识
一个密码系统中一个任意概率的攻击者能够与该密码系统中的每个算法进行多项式时间的交互，并且其它各方也可能多项式时间的访问密码系统的算法。我们假设存在一个理想化的密码系统，该密码系统永远都不会被攻破。它不是一个实际的系统，通常会涉及到使用一个抽象的可信第三方来确保数据被安全的传输，并且该可信第三方所进行的操作对攻击者和其它各方而言是透明的。为了判断一个密码方案是否安全，攻击者和其它各方需要分别与真实的密码系统和理想化的密码系统进行多项式时间的交互，然后，检查攻击者和其它各方的输出。由于理想化的密码系统不可能被攻破，如果在真实密码系统下攻击者和其它各方的输出与在理想化密码系统下的输出结果大致相同，那么这一真实的密码系统是可证明安全的。因此，我们认为一个密码系统是安全的，当且仅当上面两种输出是不可区分的或者可区分的概率极小。
应该明确，基于仿真的安全模型比基于游戏的安全模型更强。特别地，基于仿真的安全模型提供的安全性证明考虑到了部署于复杂环境下密码系统，为该密码系统提供了更可靠的安全保障。目前，一些基于仿真的安全模型被广泛使用错误！未找到引用源。。然而，已被证明，某些密码函数无法在基于仿真的安全模型下可证明安全错误！未找到引用源。错误！未找到引用源。。
2.3 公钥密码体制
密码学产生至今，大部分密码体制都是基于替换和置换的对称密码。Alice 和Bob 秘密地选取密钥K ，根据K
可以得到加密算法
和解密算法，在对称密码
体制中，
或者与
相同，或者可以容易地从
中导出。从而，
或者的
泄露会导致系统的不安全。
1976年，公钥密码体制（Public Key Cryptography ，PKC ）的概念被Diffie 和
Hellman 错误！未找到引用源。首次提出。PKC 在整个密码学发展历史中具有里程碑式的意义。在公钥密码体制中，可以扎到一个密码体制，
使得由给定的
来求是计算不可行的。PKC 的优势为通信发送发能够用通信接收方的公钥加密明文消息并发送给接收方，然后，接收方就可利用其自身私钥解密来自发送方的密文。
随后出现了一些经典公钥密码体制，比如RSA 错误！未找到引用源。和ElGamal 错误！未找到引用源。等。PKC 的安全性取决于不同的难解问题，例如，RSA 密码体制的安全性依赖于大整数分解问题， ElGamal 的安全性依赖于DL 假设。本节主要介绍公钥加密体制的形式化定义和安全模型。
2.3.1 PKE 形式化定义
电子科技大学硕士学位论文
12
定义 2.16 公钥加密方案（Public Key Encryption ，PKE ）. 一个PKE 方案由算法KeyGen 、Enc 、Dec 组成:
(1)
：
密钥产生算法
是概率算法，以一个安全参数作为输入，
生成一个公、私钥对
，可表示为； (2) Enc ：加密算法Enc 以消息
及公钥pk 作为输入，算法Enc 产生明文m 对应的密文c
，并记为
，其中Enc 是概率算法； (3) Dec ：解密算法Dec 以密文c 及私钥sk 作为输入，算法Dec 产生密文c 对
应的明文m
，并记为
，或是输出符合，表示解密失败，其中Dec 是概率算法。
对于每一个n ，
输出的每一组密钥对，以及每一个明文m ，
等式总是成立。 2.3.2 PKE 的安全模型
对于任一公钥加密方案（KeyGen ，Enc ，Dec ），其安全性依赖于攻击者的能力。针对一个PKE 方案的主动攻击有以下三种方式，这些方式被用于分析密码系统的安全性。
定义 2.17 选择明文攻击（Chosen Plaintext Attack ，CPA ）攻击者选择明文消息并寻求加密帮助以获得相应的密文消息。攻击者的目标是利用已获得的明-密文对破坏密码系统的安全性。
定义 2.18 选择密文攻击（Chosen Ciphertext Attack ，CCA ）一个攻击者选择密文消息并寻求解密帮助以获得相应的明文消息。攻击者的目标是利用已获得的明-密文对破坏密码系统的安全性。当攻击者结束解密帮助后，如果攻击者能够从给定的目标密文中获得相应的明文消息，则认为攻击成功。也就是说，一旦攻击者接收到咪表密文，攻击者的解密帮助能力将不可用。
定义 2.19 适应性选择密文攻击（Adaptive Chosen Ciphertext Attack ，CCA2）CCA2的攻击能力要比CCA 的攻击能力强，在CCA2中，攻击者可以始终获得解密帮助，但是不能对目标密文寻求解密帮助。
2.5 密钥泄露
2.5.1 问题描述
对于一个密码系统，密钥泄露问题被认为是最具破坏性的一种攻击类型，因为密码算法（如：加密、解密和签名生成等）通常被放到一个相对不安全的设备
第二章 预备知识
（如：移动设备或者联网设备）上来执行，而由此类设备维护的密钥将不可避免的发生泄露。因此，密钥泄露问题可能是密码学在实际应用中存在的最大威胁：相对于解决密码系统中的困难性问题，攻击者很容易从单纯、不设防的用户那里获得密钥。当今社会，随着越来越多的用户使用移动互联设备，密钥泄露问题的威胁也随之增加。
2.5.2 解决方法
如何有效地解决密钥泄露问题，学术界对此进行了大量研究，通常存在三种解决方法：
1、 在线密钥生成中心（Private Key Generator ，PKG ）：在线PKG 是完全可信
的，其作用是协助用户实现密钥更新。然而，当用户量巨大时， PKG 将面临巨大的维护压力，甚至系统瘫痪的风险。此外，用户与PKG 交互时也会牺牲大量的通信开销。
2、 分布式密钥存储技术：基于分布式存储技术，密钥通常被划分成多个子密
钥，而每个子密钥分别由不同的用户掌握。当需要用到该密钥时，其可通过多个子密钥重新组合而成。此外，该技术又可分为以下三种方法：
(1) 秘密共享（Secret Sharing ）技术错误！未找到引用源。：该技术的特点是将密钥切
割成多个子密钥，只有用户掌握一定数量的子密钥或所有子密钥，该
用户才会正确的还原出完整密钥；
(2) 门限密码体制（Threshold Cryptosystem ）错误！未找到引用源。：与秘密共享技术
类似，在一个门限密码系统中，密钥需要分割成n 个子密钥，当
且仅当用户掌握t 个以上的子密钥时，才可成功还原密钥；
(3) 前摄密码体制（Proactive Cryptosystem ）错误！未找到引用源。：在前摄密码体制
下，需要预先定义一个密钥生命周期，然后将密钥生命周期分为一个
时间序列，即多个时间片，每个时间片内都存在一个独立且不同的
门限密码体制，这种系统。当系统从当前时间片过渡到下一个时
间片时，系统会采用当前时间片对应的门限密码，而删除上一个时间
片对应的门限密码。
然而，上述分布式密钥存储技术都会产生昂贵的计算开销和通信开销，若一定数量的子密钥出现泄露，也将造成原密钥泄露。
3、 密钥进化技术：密钥进化是一种基于PKC 的密码技术，是目前应对密钥
泄露问题最有效的技术。该技术的本质是将系统周期切分成多个时间片，在整个系统周期内，每个时间片对应的用户私钥都不相同，而用户公钥却
电子科技大学硕士学位论文
14
是唯一且保持不变的。目前，基于密钥进化技术，存在以下三种密码体制能够有效抵抗密钥泄露问题，
(1) 前向安全密码体制（Forward-Secure Cryptosystem ）错误！未找到引用源。：该密
码体制的思想是通过借助树型结构，确保用户无法依据当前时间片对
应的密钥推导出当前时间片之前的任意时间片对应的密钥，从而保证
当前的密钥不能根据当前时间片的密钥推导得出该时段之前任意时
间片对应的密钥。
(2) 密钥隔离密码体制（Key-Insulated Cryptography ）错误！未找到引用源。：2002年，
Dodis 率先提出了基于公钥密码的密钥隔离密码体制。该密码体制的
系统模型由用户、协助者、密钥生成中心组成，且将密钥切割为两个
子密钥。其中，一个子密钥由用户自身保存，称为用户临时密钥，另
一个子密钥由一个物理安全的协助者维护，称为协助者密钥，用户需
要整合上述两个子密钥才能获得一个用于密码操作的合法密钥。在整
个系统周期内，协助者密钥始终保持不变，用户临时私钥将随着时间
片的更新而更新，而协助者密钥的作用就是协助用户更新临时私钥。
在一个密钥隔离密码算法中，系统周期被划分成N 个时间片，
如果存在t 个时间片以下的密钥发生泄露，则系统只有在被泄露密钥
对应的时间片内才会存在威胁，而对被泄露密钥对应时间片之前或之
后的系统没有威胁。当超过t 个时间片的密钥发生泄露时，系统周期
内的其它N-t 个时间片的安全性才会受到威胁。
(3) 入侵容忍密码体制（Intrusion-Resilience Cryptosystem ）错误！未找到引用源。：与
密钥隔离密码体制相比，入侵容忍密码体制存在一些类似的地方，例
如，其入侵容忍密码体制同样存在一个协助者，N 个时间片构成一个
完整的系统周期，且具有前向/后向安全性等。以及后向安全等。然而，
两者也存在不同之处。在入侵容忍密码体制中，协助者密钥也岁时间
片更新而更新。当某个时间片对应的用户临时密钥和协助者密钥同时
丢失时，该密码系统的安全性才会受到严重威胁。
2.6 本章小结
本章首先介绍了现代密码学中的一些重要数学理论，包括复杂性理论、困难性问题、以及形式化证明方法。然后，本章分别描述了公钥密码体制以及代理重加密的形式化定义与安全模型，并进一步对代理重加密的研究现状进行了对比分析。最后，本章讨论了公钥密码体制下的密钥泄露问题，并简述了当前针对密钥
第二章预备知识泄露问题的通用解决方法。
电子科技大学硕士学位论文
16
第六章总结与展望
致谢
在代理重加密研究以及将本研究整理成论文的过程中，我得到了很多人的帮助，没有他们，也就没有这篇论文。因此，我想在这里对他们诚挚的说一声：谢谢！
首先我要感谢我的研究生导师秦志光教授以对我的悉心指导与帮助。秦志光老师对待学生和蔼亲切，对待工作兢兢业业，值得每个学生去学习和尊敬。秦老师的鼓励让我在代理重加密这一课题上的研究从研一开始坚持到了现在，也正是由于秦老师的悉心指导，我最终在代理重加密这一研究课题中取得了不错的研究成果，并完成了本论文的撰写工作，再次感谢秦老师。
在本课题的研究过程中，我得到了项目组熊虎老师和赵洋老师的帮助。熊老师的学术水平很高，对学生要求严格、负责，在学术研究上给予了我巨大的助力，每每遇到问题，熊老师总会耐心的帮我答疑解惑，我也很高兴能够得到熊老师的信任和认可。赵洋老师在科研项目中给予了我很多帮助，时常教诲我们做事要有始有终，天道酬勤，在论文撰写过程中，也给我提供了很多好的意见。本文能够顺利完成，离不开熊老师和赵老师的无私奉献。
同时，还要感谢实验室的杨韵硕、李杨、包文意、岳峰、王士雨、陈阳以及任化强等同学，研究生期间我们一起学习、生活、运动、相互帮助，一起探讨项目工作以及学术研究上的难题，感谢各位对我的帮助和支持，愿我们永谊长存。
三年来，我异地求学，远在家乡的父母是我强大的精神支持，感谢他们对我的关心和鼓励，爸妈，您们辛苦了。
最后，非常感谢对我毕业论文进行评阅和答辩的老师们，感谢他们对我的论文提出的宝贵意见，谢谢！
电子科技大学硕士学位论文
18
数学文化课程报告论文题目：公钥密码体制的现状与发展 公钥密码体制的现状与发展 摘要：文中对公钥密码体制的现状与发展进行了介绍，其中着重讨论了几个比较重要的公钥密码体制Ｍ－Ｈ背包算法、RSA、ECC、量子密码、NTRU密码体制和基于辫群上的密码体制。 关键词：公钥密码体制;离散对数问题；格基归约；量子密码
1949年，Claude Shannon在《Bell System Technical Journal》上发表了题为“Communication Theory of Secrecy Systems”的论文，它是现代密码学的理论基础，这篇论文将密码学研究纳入了科学轨道，但由于受到一些因素的影响，该篇论文当时并没有引起人们的广泛重视。直到20世纪70年代，随着人类社会步入信息时代才引起人们的普遍重视，那个时期出现了现代密码的两个标志性成果。一个是美国国家标准局公开征集，并于1977年正式公布实施的美国数据加密标准；另一个是由Whitfield Diffie和Martin Hellman，在这篇文章中首次提出了公钥密码体制，冲破了长期以来一直沿用的私钥体制。自从公钥密码体制被提出以来，相继出现了许多公钥密码方案，如RSA、Elgamal密码体制、背包算法、ECC、XTR和NTRU等。 公钥密码体制的发现是密码学发展史上的一次革命。从古老的手工密码，到机电式密码，直至运用计算机的现代对称密码，这些编码系统虽然越来越复杂，但都建立在基本的替代和置换工具的基础上，而公钥密码体制的编码系统是基于数学中的单向陷门函数。更重要的是，公钥密码体制采用了两个不同的密钥，这对在公开的网络上进行保密通信、密钥分配、数字签名和认证有着深远的影响。文章共分为5部分：第１部分首先介绍了Merkle－Ｈellmen背包算法，第2,3,4,5,5部分分别讨论了RSA、ECC、量子密码、NTUR，同时对公钥密码体制进行了展望。 1、Merkle－Hellmen背包算法 1978年，Ralph Merkle和Martin Hellmen提出的背包算法是公钥密码体制用于加密的第一个算法，它起初只能用于加密，但后来经过Adi Shamtr的改进使之也能用于数字签名。其安全性基于背包难题，它是个NP完全问题，这意味
目录 第一章绪论 (1) 1.1 研究背景与意义 (1) 第二章预备知识 (7) 2.1 复杂性理论 (7) 2.2 可证明安全理论 (8) 2.2.1 困难问题假设 (8) 2.2.2 形式化证明方法 (10) 2.3 公钥密码体制 (11) 2.3.1 PKE形式化定义 (11) 2.3.2 PKE的安全模型 (12) 2.5 密钥泄露 (12) 2.5.1 问题描述 (12) 2.5.2 解决方法 (13) 2.6 本章小结 (14) 致谢 (16)
第一章绪论 第一章绪论 本章主要阐述了公钥密码体制的研究背景和积极意义，并简单介绍了代理重加密体制的研究现状以及该密码体制在云存储数据共享领域的独特优势。最后，本章介绍了本文的主要研究工作和论文结构。 1.1 研究背景与意义 密码学是伴随着信息保密而产生的，但是随着密码学技术本身的不断发展和通信网络技术的不断发展，现代的密码学研究已经远远超越了信息保密的范围，被广泛应用于各种安全和隐私保护应用之中。它是一门古老的学科，又是一门新兴的交叉学科，在今后人类社会的发展历程中必将发挥越来越重要的作用。密码学的发展可分为3个阶段： 第一阶段：从古代一直到1949年，密码学都是停留在应用于军事政治等神秘领域的实践技术。从1949年香农（Shannon）发表了《保密系统的信息理论》错误！未找到引用源。后，密码学才由理论基础指导而上升为学科。这一阶段，密码学研究的突破并不大，而且应用方面仍然只局限于特殊领域。 第二阶段：以1976年迪菲（Diffie）与赫尔曼（Hellman）发表的论文《密码学的新方向》错误！未找到引用源。以及1977年美国发布的数据加密标准（DES）加密算法为标志，密码学进入了现代密码学。 第三阶段：伴随着相关理论的完善，以及由集成电路和因特网推动的信息化工业浪潮，密码学进入了一个全新爆发的时代：研究文献和成果层出不穷，研究的方向也不断拓展，并成为了一个数学、计算机科学、通信工程学等各学科密切相关的交叉学科，同时各种密码产品也走进了寻常百姓家，从原来局限的特殊领域进入了人民群众的生产、生活之中。 在信息社会，加密体制为保证信息的机密性提供了重要的技术手段。根据密钥的特点，可将加密体制分为对称密钥体制和非对称密钥体制两种。在对称加密体制中，通信双方为了建立一个安全的信道进行通信，需要选择相同的密钥，并将密钥秘密保存。根据对明文的加密方式不同，对称密码算法又分为分组加密算法和流密码算法。分组加密算法将明文分为固定长度的分组进行加密，而流密码算法则将明文按字符逐位加密，二者之间也不是有着不可逾越的鸿沟，很多时候，分组加密算法也可以用于构建流密码算法。目前，世界上存在的分组密码算法可能有成千上万种，而其中最有名的就是美国的DES、AES以及欧洲的IDEA算法。
公钥密码体制原理及展望 ----读《New Directions in Cryptography》 姓名 学号 指导教师 时间2010年11月19日星期五
公钥密码体制原理及展望 ----读《New Directions in Cryptography》 摘要：本文通过读《New Direction in Cryptography》一文，简述了密码学的发展，重点讨论了公钥密码体制的算法及安全性。并在此基础上介绍了ECC和量子密码，了解了非对称密码体制的应用，展望了密码学未来的发展方向。 关键字：公钥密码体制，单向陷门函数、ECC、量子密码 一概述 密码学是研究如何隐密地传递信息的学科。在现代特別指对信息以及其传输的数学性研究，常被认為是数学和计算机科学的分支，和信息论也密切相关。回顾密码学的发展历程： 第一个阶段是古典密码学（19世纪以前），主要包括代替密码、换位密码以及代替密码与换位密码的组合方式等。 第二阶段是中世纪密码学，它是宗教上被刺激的原文分析对Quran那些导致了发明频率分析打破的技术替换密码。它是最根本的cryptanalytic前进直到WWII。所有暗号根本上依然是脆弱直到这个cryptanalytic技术发明polyalphabetic暗号。 第三阶段是从1800到第二次世界大战，由第二次世界大战机械和机电暗号机器在宽用途，虽然这样机器是不切实际的地方继续的人工制在使用中。巨大前进被做了暗号打破所有在秘密。 第四阶段是现代密码学，C.E.Shannon于1949年发表的划时代论文“The Communication Theory of Secret Systems”，这是现代密码学的第一次发展也是开端。而更重要的一次发展是1976年，当时在美国斯坦福大学的迪菲（Diffie）和赫尔曼(Hellman)两人提出了公开密钥密码的新思想，论文《New Direction in Cryptography》把密钥分为加密的公钥和解密的私钥，这是现代密码学的经典之作，是密码学的一场革命。 《New Direction in Cryptography》一文为解决传统密码体制（主要针对对称密码体制）密钥分发困难、密钥集中了密文的安全性等缺陷，设计了公钥密码体制，是非对称密码学的开山之作。下面简要地介绍一下这篇文章的主要内容。 二公钥密码体制基本原理 公钥密码算法中的密钥依性质划分，可分为公钥和私钥两种。用户或系统产生一对密钥，将其中的一个公开，称为公钥；另一个自己保留，称为私钥。任何获悉用户公钥的人都可用用户的公钥对信息进行加密与用户实现安全信息交互。由于公钥与私钥之间存在的依存关系，只有用户本身才能解密该信息，任何未受授权用户甚至信息的发送者都无法将此信息解密。所以在公钥密码系统中，首先要求加密函数具有单向性，即求逆的困难性。即： 一个可逆函数f：A→B，若它满足： 1o对所有x∈A，易于计算f(x)。 2o对“几乎所有x∈A”由f(x)求x“极为困难”，以至于实际上不可能做到，则称f为一单向(One-way)函数。 但是，要做加密处理，对加密函数仅有单向的要求还不够，必须还要满足，
ElGamal公钥密码体制 1、问题描述 设计ElGamal公钥密码体制算法。 2、算法设计 (1)选取大素数p和p的一个原根a，(a,p)=1,1 r[j+1]=r[j-1]-q[j]*r[j]; if(j>=2) { s[j]=s[j-2]-q[j-1]*s[j-1]; t[j]=t[j-2]-q[j-1]*t[j-1]; } } return s[j-1]; } int gcd(int a,int b) { int c; if(a 公钥密码体制的研究 目录 第一章绪论 (1) 1.1 研究背景与意义 (1) 第二章预备知识 (7) 2.1 复杂性理论 (7) 2.2 可证明安全理论 (8) 2.2.1 困难问题假设 (8) 2.2.2 形式化证明方法 (10) 2.3 公钥密码体制 (11) 2.3.1 PKE形式化定义 (11) 2.3.2 PKE的安全模型 (12) 2.5 密钥泄露 (12) 2.5.1 问题描述 (12) 2.5.2 解决方法 (13) 2.6 本章小结 (14) 致谢 (17) 第一章绪论 本章主要阐述了公钥密码体制的研究背景和积极意义，并简单介绍了代理重加密体制的研究现状以及该密码体制在云存储数据共享领域的独特优势。最后，本章介绍了本文的主要研究工作和论文结构。 1.1 研究背景与意义 密码学是伴随着信息保密而产生的，但是随着密码学技术本身的不断发展和通信网络技术的不断发展，现代的密码学研究已经远远超越了信息保密的范围，被广泛应用于各种安全和隐私保护应用之中。它是一门古老的学科，又是一门新兴的交叉学科，在今后人类社会的发展历程中必将发挥越来越重要的作用。密码学的发展可分为3个阶段： 第一阶段：从古代一直到1949年，密码学都是停留在应用于军事政治等神秘领域的实践技术。从1949年香农（Shannon）发表了《保密系统的信息理论》错误!未找到引用源。后，密码学才由理论基础指导而上升为学科。这一阶段，密码学研究的突破并不大，而且应用方面仍然只局限于特殊领域。 第二阶段：以1976年迪菲（Diffie）与赫尔曼（Hellman）发表的论文《密码学的新方向》错误!未找到引用源。以及1977年美国发布的数据加密标准（DES）加密算法为标志，密码学进入了现代密码学。 第三阶段：伴随着相关理论的完善，以及由集成电路和因特网推动的信息化工业浪潮，密码学进入了一个全新爆发的时代：研究文献和成果层出不穷，研究的方向也不断拓展，并成为了一个数学、计算机科学、通信工程学等各学科密切相关的交叉学科，同时各种密码产品也走进了寻常百姓家，从原来局限的特殊领域进入了人民群众的生产、生活之中。 在信息社会，加密体制为保证信息的机密性提供了重要的技术手段。根据密钥的特点，可将加密体制分为对称密钥体制和非对称密钥体制两种。在对称加密体制中，通信双方为了建立一个安全的信道进行通信，需要选择相同的密钥，并将密钥秘密保存。根据对明文的加密方式不同，对称密码算法又分为分组加密算法和流密码算法。分组加密算法将明文分为固定长度的分组进行加密，而流密码算法则将明文按字符逐位加密，二者之间也不是有着不可逾越的鸿沟，很多时候，分组加密算法也可以用于构建流密码算法。目前，世界上存在的分组密码算法可能有成千上万种，而其中最有名的就是美国的DES、AES以及欧洲的IDEA算法。 关键词公钥密码体制－数字签名身份认证 引言 公开密钥密码体制地概念是年由美国密码学专家狄匪（）和赫尔曼（）提出地，有两个重要地原则：第一，要求在加密算法和公钥都公开地前提下，其加密地密文必须是安全地；第二，要求所有加密地人和把握私人秘密密钥地解密人，他们地计算或处理都应比较简单，但对其他不把握秘密密钥地人，破译应是极困难地.随着计算机网络地发展，信息保密性要求地日益提高，公钥密码算法体现出了对称密钥加密算法不可替代地优越性.近年来，公钥密码加密体制和、数字签名、电子商务等技术相结合，保证网上数据传输地机密性、完整性、有效性、不可否认性，在网络安全及信息安全方面发挥了巨大地作用.本文具体介绍了公钥密码体制常用地算法及其所支持地服务.文档来自于网络搜索 公钥密码算法 公钥密码算法中地密钥依性质划分，可分为公钥和私钥两种.用户或系统产生一对密钥，将其中地一个公开，称为公钥；另一个自己保留，称为私钥.任何获悉用户公钥地人都可用用户地公钥对信息进行加密与用户实现安全信息交互.由于公钥与私钥之间存在地依存关系，只有用户本身才能解密该信息，任何未受授权用户甚至信息地发送者都无法将此信息解密.在近代公钥密码系统地研究中，其安全性都是基于难解地可计算问题地.如：文档来自于网络搜索 （）大数分解问题；（）计算有限域地离散对数问题；（）平方剩余问题；（）椭圆曲线地对数问题等. 基于这些问题，于是就有了各种公钥密码体制.关于公钥密码有众多地研究，主要集中在以下地几个方面： （）公钥体制地研究；（）椭圆曲线密码体制地研究；（）各种公钥密码体制地研究；（）数字签名研究.文档来自于网络搜索 公钥加密体制具有以下优点： （）密钥分配简单；（）密钥地保存量少；（）可以满足互不相识地人之间进行私人谈话时地保密性要求；（）可以完成数字签名和数字鉴别.文档来自于网络搜索 .算法 算法是，和在年提出地，是一种公认十分安全地公钥密码算法.算法是目前网络上进行保密通信和数字签名地最有效安全算法.算法地安全性基于数论中大素数分解地困难性.所以，需采用足够大地整数.因子分解越困难，密码就越难以破译，加密强度就越高.其公开密钥和私人密钥是一对大素数地函数.从一个公开密钥和密文中恢复出明文地难度等价于分解两个大素数之积.因式分解理论地研究现状表明：所使用地密钥至少需要比特，才能保证有足够地中长期安全.文档来自于网络搜索 为了产生两个密钥，选取两个大素数和.为了获得最大程度地安全性，两数地长度一样.计算乘积：＝，然后随机选取加密密钥，使和互素.最后用欧几里得扩展算法计算解密密钥，以满足：＝则＝－注重：和也互素.和是公开密钥，是私人密钥.两个素数和不再需要，可以舍弃，但绝不能泄漏.文档来自于网络搜索 加密消息时，首先将它分成比份小地数据分组.加密后地密文，将由相同长度地分组组成.加密公式可表示为：＝×（）解密消息时，取每一个加密后地分组并计算：＝×（）.文档来自于网络搜索 由于：＝（）＝＝（－）（－）＝×（－）（－）＝×＝（）这个公式能恢复出全部明文.公开密钥：两个素数和地乘积；：与互素.私人密钥：与互素.加密＝×（）；解密＝×（）.文档来自于网络搜索 .算法 目录 第一章绪论 1.1 研究背景与意义 第二章预备知识 2.1 复杂性理论 2.2 可证明安全理论 2.2.1 困难问题假设 2.2.2 形式化证明方法 2.3 公钥密码体制 2.3.1 PKE形式化定义 2.3.2 PKE的安全模型 2.5 密钥泄露 2.5.1 问题描述 2.5.2 解决方法 2.6 本章小结 致谢 第一章绪论 本章主要阐述了公钥密码体制的研究背景和积极意义，并简单介绍了代理重加密体制的研究现状以及该密码体制在云存储数据共享领域的独特优势。最后，本章介绍了本文的主要研究工作和论文结构。 1.1 研究背景与意义 密码学是伴随着信息保密而产生的，但是随着密码学技术本身的不断发展和通信网络技术的不断发展，现代的密码学研究已经远远超越了信息保密的范围，被广泛应用于各种安全和隐私保护应用之中。它是一门古老的学科，又是一门新兴的交叉学科，在今后人类社会的发展历程中必将发挥越来越重要的作用。密码学的发展可分为3个阶段：第一阶段：从古代一直到1949年，密码学都是停留在应用于军事政治等神秘领域的实践技术。从1949年香农（Shannon）发表了《保密系统的信息理论》[1]后，密码学才由理论基础指导而上升为学科。这一阶段，密码学研究的突破并不大，而且应用方面仍然只局限于特殊领域。 第二阶段：以1976年迪菲（Diffie）与赫尔曼（Hellman）发表的论文《密码学的新方向》[2]以及1977年美国发布的数据加密标准（DES）加密算法为标志，密码学进入了现代密码学。 第三阶段：伴随着相关理论的完善，以及由集成电路和因特网推动的信息化工业浪潮，密码学进入了一个全新爆发的时代：研究文献和成果层出不穷，研究的方向也不断拓展，并成为了一个数学、计算机科学、通信工程学等各学科密切相关的交叉学科，同时各种密码产品也走进了寻常百姓家，从原来局限的特殊领域进入了人民群众的生产、生活之中。 在信息社会，加密体制为保证信息的机密性提供了重要的技术手段。根据密钥的特点，可将加密体制分为对称密钥体制和非对称密钥体制两种。在对称加密体制中，通信双方为了建立一个安全的信道进行通信，需要选择相同的密钥，并将密钥秘密保存。根据对明文的加密方式不同，对称密码算法又分为分组加密算法和流密码算法。分组加密算法将明文分为固定长度的分组进行加密，而流密码算法则将明文按字符逐 公钥密码体制的核心思想是：加密和解密采用不同的密钥。这是公钥密码体制和传统的对称密码体制最大的区别。对于传统对称密码而言，密文的安全性完全依赖于密钥的保密性，一旦密钥泄漏，将毫无保密性可言。但是公钥密码体制彻底改变了这一状况。在公钥密码体制中，公钥是公开的，只有私钥是需要保密的。知道公钥和密码算法要推测出私钥在计算上是不可行的。这样，只要私钥是安全的，那么加密就是可信的。 显然，对称密码和公钥密码都需要保证密钥的安全，不同之处在于密钥的管理和分发上面。在对称密码中，必须要有一种可靠的手段将加密密钥（同时也是解密密钥）告诉给解密方；而在公钥密码体制中，这是不需要的。解密方只需要保证自己的私钥的保密性即可，对于公钥，无论是对加密方而言还是对密码分析者而言都是公开的，故无需考虑采用可靠的通道进行密码分发。这使得密钥管理和密钥分发的难度大大降低了。 加密和解密:发送方利用接收方的公钥对要发送的明文进行加密,接受方利用自己的 私钥进行解密,其中公钥和私钥匙相对的,任何一个作为公钥,则另一个 就为私钥.但是因为非对称加密技术的速度比较慢,所以,一般采用对称 加密技术加密明文,然后用非对称加密技术加密对称密钥,即数字信封技术. 签名和验证:发送方用特殊的hash算法，由明文中产生固定长度的摘要，然后利用 自己的私钥对形成的摘要进行加密，这个过程就叫签名。接受方利用 发送方的公钥解密被加密的摘要得到结果A，然后对明文也进行hash操 作产生摘要B.最后,把A和B作比较。此方式既可以保证发送方的身份不 可抵赖，又可以保证数据在传输过程中不会被篡改。 首先要分清它们的概念: 加密和认证 背包密码体制之背包算法 姓名：张全英 学号：20143967 专业：信息与计算科学1班 学院：数学与信息科学 摘要：网络和信息安全正在成为一个国家政治、军事、经济以及社会生活正常运行的基础,它将是一个国家综合实力的重要体现。而密码学是信息安全的核心。公钥密码又是将加密、解密密钥甚至加密、解密函数分开,用户只保留解密密钥,而将加密密钥和加密函数一起公之于众,是密码学的重要组成部分。背包公钥和RSA一样是著名的公钥体制之一,特别是背包公钥的安全基础是背包问题,这是一个NP难问题。虽然在提出不久就遭到破解,但是在提出的背包公钥系统的改进方案中依然有几个被证明是安全的。背包公钥是首个把NP问题用于公钥密码的密码体制,而其他现阶段应用的公钥密码体制都是基于因式分解或离散对数问题的,他们都不是NP问题构造的,因此背包公钥体制的研究是十分有意义的。本文从背包体制的常用攻击方法入手,寻找被破解的原因,并针对这些原因提出了新的构造思路,利用非超递增序列构造背包体制。利用非超递增序列构造背包公钥有2个必须解决的问题是加密结果的不唯一性和解密的困难性。本文对一种同余多模背包序列进行分析,并利用得出的性质构造一种新的L序列,并证明了L序列能解决以上2个问题,并提出了利用L序列构造背包公钥体制的方案。为了加快加解密速度,还提出了模M和W-1的逆向构造算法。然后给出了非超递增背包公钥体制的模拟实现。 关键字：模逆，欧几里德算法，同余式，超递增序列 目录： 1.公钥密码的原理 2.公钥密码的数学基础： 一个公开密钥密码系统必须满足的条件是： A.通讯双方A和B容易通过计算产生出一对密钥（公开密钥K1，私钥密钥K2）。 B.在知道公开密钥K1和待加密报文M的情况下，对于发送方A，很容易通过计算产生对应的密文： C.C = Ek1（M） D.接收方B使用私有密钥容易通过计算解密所得的密文以便恢复原来的报文： E.M = Dk2（C）= Dk2[Ek1（M）] F.除A和B以外的其他人即使知道公钥k1，要确定私钥K2在计算上也是不可行的。 G.除A和B以外的其他人即使知道公钥k1和密文C，要想恢复原来的明文C在计算上也是不可行的。 3.数论基础知识： 这些要求最终可以归结到设计一个单向陷门函数。 4.单向函数：单项陷门函数： 一个单向函数是满足下列条件的函数：它将一个定义域映射到值域，使得每个函数值有一个唯一的原像，同时还要满足下列条件：函数值计算很容易，而逆计算是不可行的。 所谓单向陷门函数是这样的函数，即除非知道某种附加的信息，否则这样的函数在一个方向上容易计算，而在另外的方向上要计算是不可行的。有了附加的信息，函数的逆就可以在多项式时间内计算出来。 一个实用的公开密钥密码系统的建立和发展依赖于找到一个单向陷门函数。 公钥密码体制总结及展望 摘要：计算机网络的发展突飞猛进，与此同时产生了公钥密码体制，本文重点介绍了当前公钥密码体制的几种常见的算法以及公钥密码体制的未来发展趋势。 关键词公钥密码体制 RSA DSA ECDSA SHA-1 数字签名身份认证 1 引言 公开密钥密码体制的概念是1976年由美国密码学专家狄匪(Diffie)和赫尔曼(Hellman)[1]提出的，有两个重要的原则：第一，要求在加密算法和公钥都公开的前提下，其加密的密文必须是安全的；第二，要求所有加密的人和掌握私人秘密密钥的解密人，他们的计算或处理都应比较简单，但对其他不掌握秘密密钥的人，破译应是极困难的。随着计算机网络的发展，信息保密性要求的日益提高，公钥密码算法体现出了对称密钥加密算法不可替代的优越性。近年来，公钥密码加密体制和PKI、数字签名、电子商务等技术相结合，保证网上数据传输的机密性、完整性、有效性、不可否认性，在网络安全及信息安全方面发挥了巨大的作用。本文详细介绍了公钥密码体制常用的算法及其所支持的服务。 2 公钥密码算法 公钥密码算法中的密钥依性质划分，可分为公钥和私钥 两种。用户或系统产生一对密钥，将其中的一个公开，称为公钥；另一个自己保留，称为私钥。任何获悉用户公钥的人都可用用户的公钥对信息进行加密与用户实现安全信息交互。由于公钥与私钥之间存在的依存关系，只有用户本身才能解密该信息，任何未受授权用户甚至信息的发送者都无法将此信息解密。在近代公钥密码系统的研究中, 其安全性都是基于难解的可计算问题的。如: (1)大数分解问题；(2)计算有限域的离散对数问题；(3)平方剩余问题；(4)椭圆曲线的对数问题等。 基于这些问题, 于是就有了各种公钥密码体制。关于公钥密码有众多的研究, 主要集中在以下的几个方面: (1)RSA 公钥体制的研究；(2)椭圆曲线密码体制的研究；(3)各种公钥密码体制的研究；(4)数字签名研究。 公钥加密体制具有以下优点: (1)密钥分配简单；(2)密钥的保存量少；(3)可以满足互不相识的人之间进行私人谈话时的保密性要求；(4)可以完成数字签名和数字鉴别。 2.1 RSA算法 RSA算法[2]是Ron Rivest, Adi Shamir和Len Adleman 在1978年提出的，是一种公认十分安全的公钥密码算法。RSA算法是目前网络上进行保密通信和数字签名的最有效安全算法。RSA算法的安全性基于数论中大素数分解的困难性。 多变量公钥密码体制的设计与安全性分析研究随着量子计算研究的进展,后量子公钥密码逐渐成为了密码学研究的热点之一。多变量公钥密码学是后量子公钥密码学的研究分支之一。由于多变量公钥密码体制尚未有适当的可证明安全方法,因此衡量多变量公钥密码体制的安全性依赖于抵抗现有的攻击方法。目前,多数二次多变量公钥密码算法遭受到了各种代数工具的分析,难以确保体制既高效又安全。本文的研究工作首先对现有的一些公钥密码体制进行了安全性分析,然后针对现有攻击方法,考虑将体制的次数提高到三次来抵抗现有的攻击,提出了一系列的三次多变量公钥密码体制。具体如下:(1)利用线性化方程结合差分攻击破解了一类l-可逆循环类的公钥加密体制。该体制和l-可逆循环公钥加密体制一样满足线性化方程,在找到所有的线性化方程后,给定合法密文,可将原体制退化为Square加密体制,从而可用差分攻击破解,找到合法密文相应的明文。利用二次化方程结合直接攻击方法破解了扩展的多变量公钥密码体制的两个实例。在找到所有的二次化方程后,给定合法密文,就可得到明文变量的二次多项式方程,从而降低了求解过程中的正则次数,使得直接攻击方法可以找到合法密文相应的明文。(2)提出了三次中间域方程公钥加密体制和数字签名体制。方案中设计使用三个二阶矩阵的乘积来构造中心映射中的三次多项式,而且采用二阶矩阵的行列式来作为锁多项式隐藏其中的三角形结构。当公钥多项式的次数从二次提高到三次,有效地避免线性化方程的出现,也能够抵抗直接攻击。和三次简单矩阵多变量公钥密码体制相比,在同等安全强度下, 本文提出的体制密钥规模较小。(3)提出了三次不平衡油醋签名体制。三次不平衡油醋体制中存在大量的油变量的二次项,可以抵抗油醋分 离攻击,而且醋变量个数可以少于油变量的个数。相比于二次不平衡 油醋签名体制,三次方案的签名长度要短得多,密钥生成的时间也更短。选择合适的参数之后,该方案同样可以抵抗秩攻击和直接攻击。(4)提出了两个三次多变量数字签名体制。第一个三次签名体制使用 的中心映射是立方映射,结合投影方法和减方法可使得构造的签名体 制能够抵抗差分攻击,同时合适的参数选择可使得体制能够抵抗现有 的其他攻击方法。第二个三次签名体制的中心映射类似于l-循环公 钥密码体制,不过l-循环体制的中心映射是二次的,而本文的方案中 心映射是三次的,合适选择参数后,可抵抗差分攻击、线性化方程攻击、直接攻击等现有攻击。本文中所提出的密码体制和攻击及安全性分析过程均在普通PC机上通过Magma来实现,验证了文中的理论分析结果。论文的工作为多变量公钥密码体制的设计与分析提供了新的思路。 毕业设计（论文）开题报告 题目公钥密码体制RSA安全分析及应用 系（院）数学与信息科学系年级 专业数学与应用数学班级 学生姓名学号 指导教师职称 学院教务处 二〇一二年三月 一、课题的目的意义： 随着计算机和电子通讯技术,包括因特网的迅猛发展,金融电子化的步伐大大加快,这种电子化、数字化的趋势已经波及社会生活的几乎所有的方面。人与人之间的许多交往活动,包括商业贸易、金融财务和其他经济活动中,不少已以数字化信息的方式在网上流动着。"数字化经济"（Economy Digital）的图景已经浮现,电子商业、电子银行和电子货币的研究、实施和标准化正在紧锣密鼓地进行中。许多传统上基于纸面的,常常需要签名盖章的重要凭证,诸如纸币、存单、支票、股票、公函、合同、租约、遗嘱、选票、法律文书、身份证件、学历证书等等,已陆续转化为数字电子媒体的形式出现。 那些机密的、甚至价值连城的重要信息常常需要在公开的网络上传送。怎样才能确保原始信息不会被窃取、窃听不能被伪造、篡改怎样才能确认信息发送者的真实性怎样才能保证信息发送者无法抵赖？。"公开密钥密码系统"ystem keycryptos public ,或称"公开密钥密码体制")的巧妙方法比较成功地解决了上述问题,并已在业界得到了广泛的应用。 公开密钥密码体制是现代密码学的最重要的发明和进展。说起密码学在大家的印象中主题应该是保护信息传递的机密性。确实,保护敏感的通讯一直是密码学多年来的重点。但这仅仅是当今密码学的主题的一个方面,对信息发送人的身份的验证,正是密码学主题的另一方面。公开密钥密码体制为这两方面的问题都给出了出色的答案,并正在继续产生许多新的思想和方案。目前公钥密码体制最典型的代表是RSA体制。 二、文献综述： 中国古代秘密通信的手段，已有一些近于密码的雏形。宋曾公亮、丁度等编撰《武经总要》“字验”记载，北宋前期，在作战中曾用一首五言律诗的40个汉字，分别代表40种情况或要求，这种方式已具有了密本体制的特点。 公开密钥密码体制的概念是由ford S tan大学的研究人员Diffie及Hellman于1976年提出的。公开密钥密码体制的产生主要有两方面的原因：一是由于常规密钥密码体制的密钥分配问题；而是由于对数字签名的需求。目前比较流行的公钥密码体制主要有两类:一类是基于大整数因子分解问题的,其中RSA算法是公钥密码体制中的重要成员，也是目前最流行的公钥密码体制之一。另一类是基于离散对数问题的,如ElGamal公钥密 浅析几种公钥密码体制 摘要：论述了RSA、Merkle-Hellman背包加密体制和椭圆曲线密码体制的基本原理，以及它们的优缺点，通过对比指出椭圆曲线密码体制的明显优点。 关键词：RSA；Merkle-Hellman背包加密体制；ECC；优缺点 1引言 公钥密码体制于1976年由W.DIffie和M.Hellman提出，同时R.Merkle在1978年也独立的提出这一体制[2]。该密码体制就是针对私钥密码体制的缺陷被提出来的。在公钥加密系统中，加密和解密是相对独立的，加密和解密会使用两把不同的密钥。加密密钥向公众公开，谁都可以使用。解密密钥只有解密人自己知道，非法使用者根据公开的加密密钥无法推算出解密密钥。故其可称为公钥密码体制。 自从公钥密码体制被提出以来，出现了许多公钥密码方案如RSA、ELGamal 密码体制、背包算法和ECC、XTR、NTRU等。 下面就介绍一下各种密码体制的优缺点，并进行比较。 2RSA 在Diffie和Hellman提出公钥系统观点以后，1977年麻省理工大学的Rivest、Shamir和Adleman提出了第一个比较完善的公钥密码算法,即RSA算法[2]。 RSA系统是公钥系统的最具有典型意义的方法，大多数使用公钥密码进行加密和数字签名的产品和标准使用的都是RSA算法。RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已经二十多年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价，即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NP问题。 RSA的缺点主要有：（1）产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。（2）分组长度太大，为保证安全性，至少也要600bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级，且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化[6]。 3Merkle-Hellman背包加密体制 基于公钥密码体制的数据加密 摘要：公开密钥算法的原理是加密密钥和解密密钥分离，可将加密密钥公之于众，谁都可以使用；而解密密钥只有解密人自己知道。任何人利用这个加密密钥和算法向该用户发送的加密信息，该用户均可以将之还原。公钥加密算法中使用最广的是RSA。RSA使用两个密钥，一个公共密钥，一个专用密钥。如用其中一个加密，则可用另一个解密。本文综述了公钥体系及其应用RSA算法，也讨论了相关的攻击手段。 关键字：公钥密码加密技术 RSA Abstrat：Public-key algorithm encryption and decryption key principle is key separation, but will encryption key in the open, who can use; And decryption decryption key only themselves know. Any person to use the encryption key and to the user to send the algorithm of the encrypted information, the user can be will restore. Public key encryption algorithm used in the most extensive is RSA. RSA use two keys, a public key, a special key. If use one of the encryption, usable another decryption. This paper reviewed the application of RSA public key system and its algorithm, and also discussed the related attack means. Key：Public key password Encryption technology RSA 1 公钥密码体系背景 通常信息安全的目标可以概括为解决信息的以下问题：保密性(Confidentiality)保证信息不泄露给未经授权的任何人；完整性（Integrity）防止信息被未经授权的人篡改；可用性（Availability）保证信息和信息系统确实为授权者所用；可控性（Controllability）对信息和信息系统实施安全监控，防止非法利用信息和信息系统。 密码是实现一种变换，利用密码变换保护信息秘密是密码的最原始的能力，然而，随着信息和信息技术发展起来的现代密码学，不仅被用于解决信息的保密性，而且也用于解决信息的完整性、可用性和可控性。可以说，密码是解决信息安全的最有效手段，密码技术是解决信息安全的核心技术。 公开密钥算法是在1976年由当时在美国斯坦福大学的迪菲（Diffie）和赫尔曼(Hellman)两人首先发明的（论文"New Direction in Cryptography"），思想不同于传统的对称密钥密码体制，它要求密钥成对出现，一个为加密密钥(e)，另一个为解密密钥(d)，且不可能从其中一个推导出另一个，其原理是加密密钥和解密密钥分离。在公钥体制中，加密密钥不同于解密密钥。人们将加密密钥公之于众，谁都可以使用；而解密密钥只有解密人自己知道。这样，一个具体用户就可以将自己设计的加密密钥和算法公诸于众，而只保密解密密钥。任何人利用这个加密密钥和算法向该用户发送的加密信息，该用户均可以将之还原。 自1976年以来，已经提出了多种公开密钥密码算法，其中许多是不安全的，一些认为是安全的算法又有许多是不实用的，它们要么是密钥太大，要么密文扩展十分严重。多数密码算法的安全基础是基于一些数学难题，这些难题专家们认为在短期内不可能得到解决。因为一些问题(如因子分解问题)至今已有数千年的历史了。 一般理解密码学(Cryptography)就是保护信息传递的机密性，而对信息发送与接收人的真实身份的验证、对所发出/接收信息在事后的不可抵赖以及保障数据的完整性是现代密码学主题的另一方面。公开密钥密码体制对这两方面的问题都给出了出色的解答，并正在继续产生许多新的思想和方案。 公用密钥的优点就在于，也许你并不认识某一实体，但只要你的服务器认为该实体的CA是可靠公钥密码体制的研究
公钥密码体制综述及展望
公钥密码体制的研究
公钥密码体制的核心思想是
浅谈背包公钥密码体制全解
公钥密码体制总结及展望
多变量公钥密码体制的设计与安全性分析研究
RSA公钥密码体制开题报告
浅析几种公钥密码体制
基于公钥密码体制的数据加密
相关主题
文本预览