公钥密码体制的研究.doc

目录 第一章 绪 论.1 1.1 研究背景与意义.1 第二章 预备知识.5 2.1 复杂性理论.5 2.2 可证明安全理论.6 2.2.1 困难问题假设.6 2.2.2 形式化证明方法.8 2.3 公钥密码体制.9 2.3.1 PKE 形式化定义 .9 2.3.2 PKE 的安全模型 .10 2.5 密钥泄露.10 2.5.1 问题描述.10 2.5.2 解决方法.11 2.6 本章小结.12 致 谢.14 第一章 绪论 第一章 绪 论 本章主要阐述了公钥密码体制的研究背景和积极意义，并简单介绍了代理重 加密体制的研究现状以及该密码体制在云存储数据共享领域的独特优势。最后， 本章介绍了本文的主要研究工作和论文结构。 1.1 研究背景与意义 密码学是伴随着信息保密而产生的，但是随着密码学技术本身的不断发展和 通信网络技术的不断发展，现代的密码学研究已经远远超越了信息保密的范围， 被广泛应用于各种安全和隐私保护应用之中。它是一门古老的学科，又是一门新 兴的交叉学科，在今后人类社会的发展历程中必将发挥越来越重要的作用。密码 学的发展可分为 3 个阶段： 第一阶段：从古代一直到 1949 年，密码学都是停留在应用于军事政治等神 秘领域的实践技术。从 1949 年香农（Shannon）发表了保密系统的信息理论 Error! Reference source not found.后，密码学才由理论基础指导而上升为学科。这一阶段， 密码学研究的突破并不大，而且应用方面仍然只局限于特殊领域。 第二阶段：以 1976 年迪菲（Diffie）与赫尔曼（Hellman）发表的论文密码 学的新方向Error! Reference source not found.以及 1977 年美国发布的数据加密标准 （DES）加密算法为标志，密码学进入了现代密码学。 第三阶段：伴随着相关理论的完善，以及由集成电路和因特网推动的信息化 工业浪潮，密码学进入了一个全新爆发的时代：研究文献和成果层出不穷，研究 的方向也不断拓展，并成为了一个数学、计算机科学、通信工程学等各学科密切 相关的交叉学科，同时各种密码产品也走进了寻常百姓家，从原来局限的特殊领 域进入了人民群众的生产、生活之中。 在信息社会，加密体制为保证信息的机密性提供了重要的技术手段。根据密 钥的特点，可将加密体制分为对称密钥体制和非对称密钥体制两种。在对称加密 体制中，通信双方为了建立一个安全的信道进行通信，需要选择相同的密钥，并 将密钥秘密保存。根据对明文的加密方式不同，对称密码算法又分为分组加密算 法和流密码算法。分组加密算法将明文分为固定长度的分组进行加密，而流密码 算法则将明文按字符逐位加密，二者之间也不是有着不可逾越的鸿沟，很多时候， 分组加密算法也可以用于构建流密码算法。目前，世界上存在的分组密码算法可 能有成千上万种，而其中最有名的就是美国的 DES、AES 以及欧洲的 IDEA 算法。 电子科技大学硕士学位论文 2 相对于对称体制中的密钥必须保密，非对称密钥体制有一个可公开的公钥为 其最大特征，因此也叫公钥密码体制。在非对称密码体制中，不再有加密密钥和 解密密钥之分。可以使用公钥加密，而用私钥解密，这多用于保护数据的机密性； 也可以用私钥加密而公钥解密，这多用于保护信息的完整性和不可否认性。1976 年，公钥密码体制（Public Key Cryptography，PKC）的概念被 Diffie 和 HellmanError! Reference source not found.首次提出。PKC 在整个密码学发展历史中具有里 程碑式的意义。随后出现了一些经典的公钥密码体制，比如 RSAError! Reference source not found. Rabin 算法Error! Reference source not found. ElGamalError! Reference source not found.密码体 制和椭圆曲线密码体制 Error! Reference source not found.Error! Reference source not found.Error! Reference source not found.等。公钥密码体制的安全性依赖于不同的计算问题，其中 RSA 密码体 制基于大整数分解的困难性，而 ElGamal 密码体制则基于离散对数问题的困难性。 在密码系统中，安全的核心是密钥，一个安全系统无论设计得多么完美，如 果其中的密钥安全没办法保证，则整个系统的安全也将是空中楼阁。在实际应用 中，非对称密钥管理主要通过公钥基础设施（Public Key Infrastructure，PKI）来 对用户的公私钥对进行管理，而且非对称与对称两种体制的密码管理往往是结合 在一起使用的。但是，基于 PKI 的公钥密码系统存在计算开销昂贵的公钥证书管 理问题。为避免此问题，Shamir 在 1984 年率先提出了基于身份的公钥密码体制 Error! Reference source not found.（Identity-based Cryptography，IBC）的概念，2001 年， 第一个安全实用的基于身份公钥加密（Identity-based Encryption，IBE）方案才由 Boneh 和 FranklinError! Reference source not found.基于椭圆曲线上的双线性对构造而来。 与基于 PKI 的传统公钥密码体制相比，IBC 不存在繁琐的公钥证书管理问题，用 户公钥由惟一标识用户身份信息的 ID 推导而来，其私钥则是由可信第三方密钥 生成中心（Key Generation Center，KGC）生成。诚然，IBC 避免了传统 PKI 中证 书管理问题，但由于 KGC 的存在，使得该密码体制无法摆脱密钥托管问题。随 后，Al-Riyami 和 PatersonError! Reference source not found.于 2003 年首次提出了基于无证 书的公钥密码体制（Certifi cateless Public Key Cryptography，CL-PKC）的概念， 该密码体制不仅可以消除 PKI 中存在的证书管理问题，也可以克服 IBC 中存在的 密钥托管问题，即 CL-PKC 继承了 IBC 的优点而克服了其缺点。此后，多个无证 书公钥加密（Certifi cateless Public Key Encryption，CL-PKE）方案 Error! Reference source not found.Error! Reference source not found.Error! Reference source not found.被提出。 尽管公钥密码体制已被广泛应用于社会各领域，但公钥密码学依然要不断发 第一章 绪论 展以适应社会的进步。如今，云计算作为一种新兴服务模式，能够方便地为远程 用户提供计算和存储资源，从而节省本地开销。一旦数据拥有者将数据上传给半 可信的云服务提供商（Cloud Service Provider，CSP） ，将失去对数据的控制权。 因此，出于安全考虑，数据拥有者在上传数据之前需要对数据进行加密处理。考 虑如下场景 Error! Reference source not found.Error! Reference source not found.Error! Reference source not found.：数据拥有者 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 可用其自身私钥解密这些共享数据。在共享过程中，数据 拥有者无需将数据下载到本地，从而节省开销。此后，代理重加密成为密码学与 信息安全领域的一个研究热点，积累了大量研究成果，且在云计算 Error! Reference source not found.Error! Reference source not found.Error! Reference source not found.、数字版权管理Error! Reference source not found.Error! Reference source not found.、加密电子邮件转发Error! Reference source not found.、分布式文件系统Error! Reference source not found.Error! Reference source not found.、加密病毒 过滤 Error! Reference source not found.Error! Reference source not found.等领域的应用前景广阔。 2003 年，基于密钥分享机制，Ivan 和 DodisError! Reference source not found.给出了构 造单向代理重加密方案的一般方法，即用户私钥被分割成两份，一份分发给代理 者，另一份分发给被委托者。 2005 年，Ateniese 等人 Error! Reference source not found.首次形式化地描述了代理重加 密及其安全模型，并设计出第一个基于双线性对的单向代理重加密方案。 Deng 等人 Error! Reference source not found.提出第一个不依靠双线性对、可证明 CCA 安全的双向代理重加密方案。 电子科技大学硕士学位论文 4 2012，Hanaoka 等人 Error! Reference source not found.在 CT-RSA 会议上给出了一个更 强的代理重加密安全模型，并给出了一个通用方法用于构造 CCA 安全的单向代 理重加密方案。Sun 等人 Error! Reference source not found.提出了第一个 CCA 安全的单向 广播代理重加密（Broadcast PRE，BPRE） ，该方案在标准模型下满足自适应选择 密文安全。 在 AsiaCCS 2009 会议上，Weng 等人 Error! Reference source not found.第一次介绍了条 件代理重加密（C-PRE）的概念，当且仅当密文满足委托者设置的条件时。 在 CT-RSA 2009 上，密钥隐私代理重加密（key-private PRE，K-PRE）的概 念由 Ateniese 等人 Error! Reference source not found.提出， 2010 年，YauError! Reference source not found.和 Shao 等人 Error! Reference source not found.分 别提出了带关键字的代理重加密（PRE with keyword research，PRES）的概念， 并构造出具体方案。 针对代理重加密密钥的安全性，Yang 等人 Error! Reference source not found.利用可信 计算来解决代理重加密中转换钥泄露的问题。为了对代理者的密文权限进行控制， Tang 等人 Error! Reference source not found.提出基于类型代理重加密（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 是通过 欺骗随机预言的回答来适合自己的需要的。 随机预言模型为证明密码体制的安全性提供了一个很好的方法，但是随机预 言模型并不反映真实世界的计算。在随机预言模型下安全的密码体制只能说是可 能在真实的世界是安全的，不能确保一定在真实的世界是安全的。文献给出了在 随机预言模型下安全的密码体制在真实的世界中不安全的例子。许多密码学研究 者开始设计在标准模型（不依赖于随机预言模型）下安全的密码体制。移除随机 预言模型是需要代价的，通常需要更强的困难问题假设，而且在标准模型下的密 码体制通常效率较低。 选择密文攻击：选择密文攻击也称为午餐时间攻击，是一种比选择明文攻击 电子科技大学硕士学位论文 6 稍强的攻击模型。在选择密文攻击中，敌手可以访问一个黑盒，这个黑盒能进行 解密。在午餐时间，敌手可以选择多项式个密文来询问解密盒，解密盒把解密后 的明文发送给敌手。在下午时间，敌手被告知一个目标密文，要求敌手在没有解 密盒帮助的情况下解密目标密文，或者找到关于明文的有用信息。 适应性选择密文攻击：是一种非常强的攻击模型。除了目标密文之外，敌手 可以选择任何密文对解密盒进行询问。目前普遍认为，任何新提出的公钥加密算 法都应该在适应性选择密文攻击下达到多项式安全性。 、 有了安全目标和攻击模型，就可以给出公钥加密体制的安全性定义了。 公钥加密体制的选择明文攻击游戏由下面三个阶段组成，这是一个挑战者 C 和敌手 A 之间的游戏。 初始阶段：C 运行密钥生成刷法生成一个公钥、私钥对。C 将 pk 发送给 A 并且保密 sk。 挑战阶段：A 产生两个相同长度明文 m0 和 m1 并将它们发送给 C。C 随机选 择一个比特，并计算 第二章 预备知识 第二章 预备知识 数学理论是现代密码学建立和发展的基础，包括复杂性理论、可证明安全理 论等，这些理论中的许多概念在设计密码算法时是必不可少的。本章主要介绍本 本文中可能会用到的一些基本概念和结论。 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 对 Error! Reference source not found.和 Tate 对Error! Reference source not found.可 被用于构建双线性映射 e。 定义定义 2.9 令为循环加法群，阶为 q，生成元为 P，已知， 其中是不可知的，求解，即中的 CDH 问题。 定义定义 2.10 令为循环加法群，阶为 q，生成元为 P，已知 ，其中是不可知的，然后判定等式是 否满足，即中的 DDH 问题。 定义定义 2.11 令为循环加法群，阶为 q，生成元为 P，在 DDH 预言机的协助 电子科技大学硕士学位论文 10 下，求解已知元组的 CDH 问题，即 GDH（gap Diffie-Hellman） 问题。 定义定义 2.12 令为循环加法群，阶为 q，生成元为 P，已知 ，求解，即 q-SDH（q-strong 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 形式化证明方法 在可证明安全理论中，形式化安全模型被用来评估一个密码系统的安全性。 一个形式化的安全模型包含两个定义 Error! Reference source not found.Error! Reference source not found.：一方面，它必须指出一个任意概率的攻击者如何与密码系统中的合法用户 进行多项式时间的交互；另一方面，它必须说明该攻击者要达到哪些目的，才能 认定该密码系统被攻破。一般来说，有两种方式来描述形式化的安全模型。 一种是基于游戏（game-based）的方式。在这种形式化安全模型中，攻击者 需要与一个假定的概率算法，也就是挑战者，进行交互。挑战者生成密码系统中 使用的所有密钥，可能响应来自攻击者的询问。当攻击者终止时，游戏结束，然 后，评估此时的攻击者是否具备破坏该密码系统的能力。如果一个密码系统被证 明是安全的，那么我们必须给出说明任意一个攻击者能够攻破该密码系统的概率 都非常小。基于游戏的安全模型已经被广泛接受，且已被应用于多种类型的密码 系统的安全性证明，包括数字签名、非对称加密和对称加密。本文所描述的形式 化安全模型都是基于游戏的安全模型。 基于游戏的安全模型的优点是容易理解和实现。然而，Canetti 等 Error! Reference 第二章 预备知识 source not found.发现基于游戏安全模型下的安全性证明只能独立的证明密码系统的安 全性，无法说明当该密码系统部署于复杂环境下时也是可证明安全的。大部分密 码方案都不是独立存在的，而是作为大型计算机系统的子程序。在这种情况下， 为了确保所使用的密码算法的安全性，必须要在给定的复杂环境下进行安全性证 明。因此，对于基于游戏的安全模型而言，它往往难以更好的表述大型复杂环境 的安全需求。 另一种是基于仿真(simulation-based)的方式。在基于仿真的安全模型下，假 设一个密码系统中一个任意概率的攻击者能够与该密码系统中的每个算法进行多 项式时间的交互，并且其它各方也可能多项式时间的访问密码系统的算法。我们 假设存在一个理想化的密码系统，该密码系统永远都不会被攻破。它不是一个实 际的系统，通常会涉及到使用一个抽象的可信第三方来确保数据被安全的传输， 并且该可信第三方所进行的操作对攻击者和其它各方而言是透明的。为了判断一 个密码方案是否安全，攻击者和其它各方需要分别与真实的密码系统和理想化的 密码系统进行多项式时间的交互，然后，检查攻击者和其它各方的输出。由于理 想化的密码系统不可能被攻破，如果在真实密码系统下攻击者和其它各方的输出 与在理想化密码系统下的输出结果大致相同，那么这一真实的密码系统是可证明 安全的。因此，我们认为一个密码系统是安全的，当且仅当上面两种输出是不可 区分的或者可区分的概率极小。 应该明确，基于仿真的安全模型比基于游戏的安全模型更强。特别地，基于 仿真的安全模型提供的安全性证明考虑到了部署于复杂环境下密码系统，为该密 码系统提供了更可靠的安全保障。目前，一些基于仿真的安全模型被广泛使用 Error! Reference source not found.。然而，已被证明，某些密码函数无法在基于仿真的安全 模型下可证明安全 Error! Reference source not found.Error! Reference source not found.。 2.3 公钥密码体制 密码学产生至今，大部分密码体制都是基于替换和置换的对称密码。Alice 和 Bob 秘密地选取密钥 K，根据 K 可以得到加密算法和解密算法，在对称 密码体制中，或者与相同，或者可以容易地从中导出。从而，或者 的泄露会导致系统的不安全。 1976 年，公钥密码体制（Public Key Cryptography，PKC）的概念被 Diffie 和 HellmanError! Reference source not found.首次提出。PKC 在整个密码学发展历史中具有 里程碑式的意义。在公钥密码体制中，可以扎到一个密码体制，使得由给定的 来求是计算不可行的。PKC 的优势为通信发送发能够用通信接收方的公钥 电子科技大学硕士学位论文 12 加密明文消息并发送给接收方，然后，接收方就可利用其自身私钥解密来自发送 方的密文。 随后出现了一些经典公钥密码体制，比如 RSAError! Reference source not found.和 ElGamal Error! Reference source not found.等。PKC 的安全性取决于不同的难解问题，例如， RSA 密码体制的安全性依赖于大整数分解问题， ElGamal 的安全性依赖于 DL 假 设。本节主要介绍公钥加密体制的形式化定义和安全模型。 2.3.1 PKE 形式化定义 定义定义 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）技术 Error! Reference source not found.：该技术的特 点是将密钥切割成多个子密钥，只有用户掌握一定数量的子密钥或 所有子密钥，该用户才会正确的还原出完整密钥； (2) 门限密码体制（Threshold Cryptosystem）Error! Reference source not found.：与 秘密共享技术类似，在一个门限密码系统中，密钥需要分割成 n 个子密钥，当且仅当用户掌握 t 个以上的子密钥时，才可成功还原 密钥； (3) 前摄密码体制（Proactive Cryptosystem）Error! Reference source not found.：在 电子科技大学硕士学位论文 14 前摄密码体制下，需要预先定义一个密钥生命周期，然后将密钥生 命周期分为一个时间序列，即多个时间片，每个时间片内都存在一 个独立且不同的门限密码体制，这种系统。当系统从当前时间 片过渡到下一个时间片时，系统会采用当前时间片对应的门限密码， 而删除上一个时间片对应的门限密码。 然而，上述分布式密钥存储技术都会产生昂贵的计算开销和通信开销， 若一定数量的子密钥出现泄露，也将造成原密钥泄露。 3、 密钥进化技术：密钥进化是一种基于 PKC 的密码技术，是目前应对密钥 泄露问题最有效的技术。该技术的本质是将系统周期切分成多个时间片， 在整个系统周期内，每个时间片对应的用户私钥都不相同，而用户公钥 却是唯一且保持不变的。目前，基于密钥进化技术，存在以下三种密码 体制能够有效抵抗密钥泄露问题， (1) 前向安全密码体制（Forward-Secure Cryptosystem）Error! Reference source not found.：该密码体制的思想是通过借助树型结构，确保用户无法依据 当前时间片对应的密钥推导出当前时间片之前的任意时间片对应的 密钥，从而保证当前的密钥不能根据当前时间片的密