云计算中同态加密算法的实现.doc

1、云计算中同态加密算法的实现加密 摘 要 随着云计算的快速发展和推广应用，在云计算环境中数据安全和隐私保护成为云计算研究中的关键问题，以数据全生命周期模型为基础，提出云计算环境中数据安全和隐私保护框架，对云计算环境中数据安全和隐私保护的若干关键研究问题，包括密文检索、完整性验证和持有性证明、隐私保护及查询隐私进行了概述，详细综述了全同态加密的发展、原理、意义以及其在云计算数据安全和隐私保护中应用，并指明了未来的研究方向。 关键词：云计算，同态加密，隐私保护ABSTRACT Abstract With the rapid development of cloud computing ,data s

2、ecurity and privacy protection become the crucial problems in the research of cloud computing .Based on the full lifecycle model of data, this paper proposes forward data security and privacy protection framework ,expounds the critical problems of data security and privacy protection in cloud comput

3、ing environment ,including retrieval of enerypted data ,integrity validation and provable data possession ,privacy protection and query privacy ,and describes in detail the development, principle,significance of full homomorphic encryption and its application in data security and privacy protection

4、,thus pointing out a direction for future research.Key words：Cloud computing, Homomorphic encryption, Privacy protection. 目录1绪论1.1 文献综述41.2云计算的概念41.3 云计算的安全性51.4 同态加密在云计算中的实现62 项目理论分析2.1 项目应用背景82.2 项目实现意义和目的82.3 需求分析92.4 可行性分析92.5 项目评估10 2.5.1 技术评估10 2.5.2 性能评估10 2.5.3 风险评估10 2.5.4 经济评估112.6 项目概要设计1

5、2 2.6.1研究框架12 2.6.2 模块划分132.7运行环境153 同态加密方案3.1 同态加密的概念153.2 传统公钥加密体制的同态性163.3 ElGamal算法的实现流程163.4 RSA算法的实现流程17 3.4.1 密钥生成17 3.4.2 加密与解密流程193.5 同态加密方案20 3.5.1 方案一20 3.5.2 方案二20 4编码实现4.1测试214.1.1 测试用例设计214.1.2 测试结果244.1 3 测试结论244.1 4 缺陷分析254.1 5 改进结果25 结论25参考文献.25第1章 绪论1.1 文献综述 随着互联网的迅速普及，云计算，语义网，物联网，

6、智慧地球等概念或服务的推出，对网络信息安全提出了更高的要求。对于这些应用，我们可以看到，它都有一个特点，就是信息在网络中传送，在远程处理，或与远程协作处理，信息系统所处的环境不再是本地的，封闭的，个人的，而是远程的，开发的，共享的。然而，对于我们来说，很多时候是既想要利用网络资源，与别人共享信息，又不想透露涉及个人隐私的信息，那么这时候，同态加密算法的同态性便显示出了其巨大的作用。 本文将介绍一些常见的同态加密算法，该方案可以提供一种安全、高效的数据存取服务。分析他们的同态性，再介绍一些专门为了实现同态加密而提出的算法。第三部分是本文重点，将介绍同态加密在云计算中的应用，并提出一些可行的方案。

7、1.2云计算的概念 首次提出“云计算”（CloudComputing）的概念是在2006年8月9日，由Google首席执行官埃里克施密特（EricSchmidt）在 搜 索 引 擎 大 会（SESSanJose2006）提 出。这 里 引 用 维 基 百 科 的定义，即云计算（Cloudcomputing）的主要含义包括：是一种基于互联网的计算方式，通过这种方式，共享的软硬件资源和信息可以按需提供给计算机和其他设备。云计算描述了一种基于互联网的新的IT服务增加、使用和交付模式，通常涉及通过互联网来提供动态易扩展而且经常是虚拟化的资源。目前，云计算（Cloud Computing）是网格计算（G

8、rid Computing）、分布式计算（Distributed Computing）、并行计算（Parallel Computing）、效用计算（Utility Computing）、网络存储（Network Storage Technologies）、虚拟化（Virtualization）、负载均衡（Load Balance）等传统计算机技术和网络技术发展融合的产物。它旨在通过网络把多个成本相对较低的计算实体整合成一个具有强大计算能力的完美系统，并借助SaaS、PaaS、IaaS、MSP等先进的商业模式把这强大的计算能力分布到终端用户手中。Cloud Computing的一个核心理念就是通

9、过不断提高“云”的处理能力，进而减少用户终端的处理负担，最终使用户终端简化成一个单纯的输入输出设备，并能按需享受“云”的强大计算处理能力。 云计算是一种能为互联网上的用户提供按需数据存储和处理能力的计算机网络的服务。云计算是对基于网络的、可配置的共享计算资源池能够方便的、随需访问的一种模式。这些可配置的共享资源计算池包括网络、服务器、存储、应用和服务。并且这些资源池以最小化的管理或者通过与云计算服务提供商的交互可以快地提供和释放。云计算主要目标是提供高效的计算服务。 公众认可的云计算的三个服务模式IaaS、PaaS、SaaS：1、IaaS(Infrastructure-as-a- Servic

10、e)：基础设施即服务。消费者通过Internet可以从完善的计算机基础设施获得服务。目前，只有世纪互联集团旗下的云快线公司号称要开拓新的IT基础设施业务，但究其本质，它只能实现主机托管业务的延伸，很难与亚马逊等企业相媲美。 2、PaaS(Platform-as-a- Service)：平台即服务。PaaS实际上是指将软件研发的平台作为一种服务，以SaaS的模式提交给用户。因此，PaaS也是SaaS模式的一种应用。但是，PaaS的出现可以加快SaaS的发展，尤其是加快SaaS应用的开发速度。但是纵观国内市场，只有八百客一个孤独的舞者，拥有PaaS平台技术。可见，PaaS还是存在一定的技术门槛，国

11、内大多数公司还没有此技术实力。 3、SaaS(Software-as-a- Service)：软件即服务。它是一种通过Internet提供软件的模式，用户无需购买软件，而是向提供商租用基于Web的软件，来管理企业经营活动。相对于传统的软件，SaaS解决方案有明显的优势，包括较低的前期成本，便于维护，快速展开使用等。比如红麦软件的舆情监测系统。1.3云计算的安全性 首先，在技术方面，按照Google的理念，如果云计算得以实现的话，那么未来人们在本地硬盘上几乎不保存数据，所有的数据在云里。这种情况下，一旦发生由于技术方面的因素导致的服务中断，那么用户只能束手无策。 此外，云计算所面临的问题在目前网

12、络应用中全部清晰可见。以TCPIP协议为核心的互联网虽然取得了巨大的成功，却面临着许多重要的问题，其中安全性最为突出。特别是虚假地址和虚假标识问题导致了大量安全问题。对源地址不做检查使现在的互联网缺乏可信任的技术基础。导致互联网的安全事件频繁发生，可信任度大大降低，限制了互联网的进一步发展和应用。这也是网络银行所面临的巨大挑战。因此，互联网身份认证技术的发展也同样制约着云计算的发展。表1.1是云计算的一些安全性特点 表1.1云计算的特点安全威胁数据和服务外包（1）隐私泄露（2）代码被盗多租户和跨域共享（1）信任关系的建立、管理和维护更加困难;（2）服务授权和访问控制变得更加复杂；（3）反动、黄

13、色、钓鱼欺诈等不良信息的云缓冲（4）恶意SaaS应用虚拟化（1）用户通过租用大量的虚拟服务使得协同攻击变得更加容易，隐蔽性更强；（2）资源虚拟化支持不同租户的虚拟资源部署在相同的物理资源上，方便了恶意用户借助共享资源实施侧通道攻击。 下面我们介绍一个云计算安全性问题比较广为人知的环境，社交网络，即SNS（Social Networking Services），是依据六度理论，以认识朋友的朋友为基础，扩展自己的人脉。并且无限扩张自己的人脉，在需要的时候，可以随时获取一点，得到该人脉的帮助。世界上第一个社交网络是美国的facebook.在国内比较出名的是人人网。那么，它有哪些安全问题呢？ 在这个系

14、统上，用户使用的信息都是相对真实的（因为大家都是朋友），每一个用户对于该系统上的用户都会给出一个信任等级，以此确定它能获取到该用户的哪些信息。这样的话，用户就会依赖于这种信任等级。而如果有一个坏人，它窃取了一个用户的帐号，或者通过某种手段得到了某用户的信任，那么这个人就可以看到用户本来不希望他看到的信息，甚至可以传播恶意的信息，代码等。 另一方面，在该系统中，由于我们可以发布一些我们原创的作品与好友分享，例如博客，视频，并设置这些内容需要怎样信任等级的用户才可以获取到。而想要获取该内容的用户，它可以通过直接和间接的请求，去获得这个内容。但是，在这个过程中，请求者又不想让内容的拥有者知道他太多信

15、息（除了信用等级，其他都不想让他知道），如果是间接请求的，又不想让拥有者知道他与那个中间人之间的关系或者说信用等级。为了实现这样的需求，同态加密技术就有发挥的余地了。1.4 同态加密在云计算中的实现 在云计算中，数据注定是要以密文的形式存放在云中，这样是最基本也是最重要的一个安全手段。当然，也是让广大用户最放心安全手段。但是，如果数据完全是以密文形式存储在云端的话，那么云也就相当于一个巨大的硬盘，其他服务由于密文的限制很难得到使用。而我们知道，云存储只是云计算的其中一个服务，它主要提供的服务，SaaS、PaaS，就会受到影响。举些例子，如果你写了一个程序，要在云端进行编译，而你上传上去的是密文

16、，那么编译器就无法处理了。如果你要在云端进行图片或视频的格式转换，你上传上去的还是密文，那么云端的软件也无法处理。 在文中，我们的策略是设置一个隐私管理者（Privacy Manager），它的一个功能就是obfuscation以密文形式发送到云端，云端就以密文形式对数据进行处理，返回结果首先要传给隐私管理者，再通过隐私管理者以明文的形式返回处理结果给用户。在这里，用户要有一个密钥，这个密钥隐私管理者是知道的，但是云计算服务提供商无法知道。隐私管理者的实现形式有多种，最简单的就是一个安装在本地的软件。 很显然，同态加密技术又配上用场了。而为了让云端可以对数据进行各种操作，必须使用全同态加密技术

17、，本文着重讲解同态加密中的RSA算法和ElGamal算法。图1.1给出了同态加密在云计算的简单实现框图。CLOUD数据 加密，提交到云上查看结果 下载，解密 图1.1完全同态加密原理： 记加密操作为E，明文为m，加密得e，即e = E(m)，m = E(e)。已知针对明文有操作f，针对E 可构造F，使得F(e) = E(f(m)，这样E就是一个针对f 的同态加密算法。 假设f 是个很复杂的操作，有了同态加密，我们就可以把加密得到的e 交给第三方，第三方进行操作F我们拿回F(e)后，一解密，就得到了f(m)。第二章 项目理论分析2.1项目应用背景 人们在享受云计算带来极大便利的同时，数据的安全性

18、也成为人们面临的主要问题。由于云服务器中储存了大量用户信息，其中不乏企业重要的商业数据和私密文件，在这种情况下，用户数据的安全性就必须要保证。因此，对于用户来说，用户的数据必须要在在上传到云服务器前就要进行加密。在云计算环境中，传统的数据加密与检索方法已经不能满足用户的需要。目前的集中加密算法虽然可以快速地检索出用户所需信息，但由于其代价比较高，对于大规模数据检索的情况不适用。在本课题中，在保证数据私密性的前提下，我们提出一种基于全同态加密的检索方案。同态加密是一种加密形式，它允许人们对密文进行特定的代数运算得到仍然是加密的结果，与对明文进行同样的运算再将结果加密一样。换言之，这项技术令人们可

19、以在加密的数据中进行诸如检索、比较等操作，得出正确的结果，而在整个处理过程中无需对数据进行解密。其意义在于，真正从根本上解决将数据及其操作委托给第三方时的保密问题，例如对于各种云计算的应用。利用一项全新的技术，未来的网络服务器无须读取敏感数据即可处理这些数据。2009年，一项数学论证提出的几种可行性方案问世，这使得研究人员开始努力将方案变得更实际。下面用手套箱的比喻来解释同态加密技术在云计算中的运用：例如一个场景叫做爱丽丝的珠宝店主如何为自己的珠宝店防盗：“Alice是一家珠宝店的店主，她打算让员工将一些贵重的珠宝组合成首饰，但是她由担心被小偷盯上。于是她造了一个手套箱存放制作好的首饰，而钥匙

20、她随身保管。”通过手套箱，员工可以将手伸入箱子来装配首饰，仅限于此。爱丽丝则可以通过钥匙，向手套箱中添加原材料，并取出制作好的首饰。类比的关联。让我们看看是否能通过这个故事来理解同态加密在云计算中的实现：店主爱丽丝最终用户，首饰原材料原始数据，钥匙网络，锁住手套箱加密，员工数据计算过程，完整的首饰数据计算结果。记住这个比喻，然后让我们看看同态加密是如何处理2+3这样的问题的：假设数据已经在本地被加密了，2加密后变为22,3加密后变为33。加密后的数据被发送到服务器，在进行相加运算。然后服务器将加密后的结果55发送回来。然后本地解密为5。2.2项目实现意义和目的 有了同态加密，有预谋的盗取敏感数

21、据的情况将成为历史。因为在同态加密环境下，敏感数据总是处于加密状态，而这些加密数据对盗贼来说是没用的。举例一个合适应用同态加密的场景：“考虑到报税员，或者一些财务服务机构，如：你将个人财务信息提供给他们，他们通过计算来优化你的财务/税务策略。但是你真的会将自己的银行账号和个人财务信息提交到财务优化网站上么?现在换一种情况，你所提交的是一个代码，财务优化网站凭此代码可以从银行数据库下载同态加密过的你的财务数据。他们可以直接对加密数据进行计算，将所得到的税务优化结果再以加密的形式发送给你，这些加密的数据他们也无法破解，但是你可以。”那么，总的来说，同态加密在云计算中就显得相当有意义。通过全同态加密

22、算法加密的明文数据可以在不恢复明文信息的情况下把最相关的文档返回给用户，可以保护了用户的数据安全。 2.3需求分析 自从人类文明刚刚出现，加密技术就已经出现。在基于计算机的复杂加密方法，也就是我们现在最常用加密技术问世之前，人们就总是希望保护敏感信息以防外人的窥探。古希腊人通过在送信使者光头上纹身来保护他们的秘密信息。当信使到达目的地时，他们的头发又长出来，这样消息就会变得看不见了。而消息的接受方只需要有一个好的理发师就能够阅读送达的秘密消息了。那么，对于把敏感数据置于云计算的公司来说，他们还采取哪些措施呢？正如古希腊人一样，我们正在努力确保我们秘密信息的安全性以防外人的窥探。当然，具体的方法

23、发生了变化，但是其目的仍旧是相同的。在云计算中，确保私有数据安全性的最佳方法之一就是对传输的数据和存储的数据进行加密处理。当谈及云计算服务时，仍然存在一些加密方面的潜在问题。几乎所有的云计算服务供应商都支持对传输数据的加密，但是很少有供应商会支持对存储数据的加密。服务供应商的云计算加密能力需要与托管数据的敏感等级相匹配。2.4可行性分析 在计算机加密技术中，数据、加密引擎和密钥管理组成一个加密系统。这三组成部分都是在同样的位置进行储存或运行。在计算机应用系统架构中，为了提高安全性，往往会将这三部分进行分离。下面介绍云计算安全架构中的这三部分是如何实现的。（1）用户在将数据储存在云服务器中时，通

24、常会使用云服务器中的虚拟储存架构。（2）如果是对存储在IaaS应用程序中的数据进行加密，用户可以在应用程序实例中使用卷标进行加密，并把加密后的数据储存在第二个加密卷标中（3）在云计算中还可以应用更为先进的同态加密技术，可以在实例中将密钥和加密引擎分离 目前的集中加密算法虽然可以快速地检索出用户所需信息，但由于其代价比较高，对于大规模数据检索的情况不适用。在本课题中，在保证数据私密性的前提下，我们提出一种基于全同态加密的检索方案。该方案可以提供一种安全、廉价、高效的数据存取服务。2.5项目评估典型云计算服务供应商的基本业务模式是基于可扩展性的理念的：能够使用共享资源的客户越多，云计算服务供应商所

25、获得的利润也就越高。这个理念从另一方面来说也是正确的：能够使用共享资源的用户越多，那么每个用户所支付的成本也就越低。这些事实在云计算供应商决定提供加密服务中起了很重要的作用。加密需要消耗更多的处理器资源，所以它降低了每个资源的平均用户数量，也就增加了整体成本。正是由于这个原因，大多数云计算供应商将只对少量数据库领域提供基本的加密服务，例如密码和账户名。在加密系统三层结构中，有一个卷标储存加密数据，另一个实例运行加密引擎，而第三个卷标是密钥管理服务器，可以根据用户的需要提供加密密钥。如果用户希望密钥不储存在实例中用该方法可以实现，因为如果加密密钥储存在实例中，攻击者能够得到该实例的副本自然得到了

26、密钥的副本。使用实例中的密钥就能够攻击相同的一个新实例。而外部密钥管理服务器只有在满足一组基于规则的标准时才会返回密钥。这样，内存中的实例就可以使用密钥直至实例关闭。 2.5.1技术评估 基于云平台同态加密算法主要使用了以下的加密算法：基于小密钥、密文空间的动态加密技术；整数上的全同态加密技术；非填充RSA加密算法，ELGamal加密算法；Goldwasser-Micali加密算法；Benaloh加密算法；Okamoto-Uchiyama加密算法等等； 2.5.2性能评估 在云计算环境中，传统的数据加密与检索方法已经不能满足用户的需要。目前的集中加密算法虽然可以快速地检索出用户所需信息，但由于

27、其代价比较高，对于大规模数据的情况不适用。在本课题中，在保证数据私密性的前提下，我们提出一种基于全同态加密的方案，可以提供一种安全、高效的数据存取服务。 2.5.3风险评估 云计算供应商业通常也提供了对整个数据库进行加密的服务，但是其成本将大大增加，其云计算托管成本要远高于内部托管成本。 一些云计算供应商已为加密功能提供了没有相同性能影响的替代解决方案。这些技术包括了重新编辑或模糊私有数据。这听上去似乎很吸引人，但那只不过是“通过模糊化实现安全性”的另一种形式。这两种技术都无法高效地确保私有数据安全性，因为这两种技术都可以被轻易地绕过。 另一个由服务供应商提供的云计算加密替代解决方案可以降低加

28、密操作对性能的影响，即定义加密解决方案。目前的加密标准已经过众多聪明工程师和密码破解专家多年的测试与验证。一个云计算服务供应商是不可能达到一个专用加密标准开发水平的，它也无法达到目前公认标准的公共监督和反馈等级。这就增加了密码破解的概率，从而使得用户数据变得易于暴露。我们应不惜一切代价避免使用专用加密标准。对于提供基于标准的加密解决方案的云计算供应商，我们可能还需要考虑另一种风险。由于加密数据的安全性仅在使用密钥进行加密时才有效，因此密钥管理就成为了一个关键的问题，而云计算供应商必须有密钥存储、产生以及归档的特定策略和流程。请务必记得，任何拥有密钥的人都能够访问你的私有数据。当使用云计算服务供

29、应商，还有其他一些加密运行问题应予以注意。这些运行流程包括磁带备份和其他可移除媒体(如DVD-R和USB设备)的加密策略和程序。你的数据可能在供应商的数据库中是安全加密的，但是如果它在运行中使用了非加密存储介质，那么还是存在着数据暴露的风险;在把你的数据送交供应商管理之前，了解这些运行风险是非常重要的。最后，还有其他一些地方是不允许使用加密技术的。云计算供应商对数据的实际操作有可能要求数据在某几个环节被解密。这一情况有可能随着同态加密的出现而发生变化，同态加密由IBM公司于2009年推出，该技术允许在加密状态处理数据。这是一项未来的技术，但是它肯定会提升云计算供应商的安全功能。2.5.4经济评

30、估在传统经济中，集中业务与分散业务的主体，往往是同一个企业；而在云计算中，集中业务与分散业务的主体，竟然是不同的企业。在传统条件下，比如美国零售商西尔斯的集中业务是沿铁路线的大仓储业务，其分散的业务是多品种的零售业务。无论集中，还是分散，都是在一个企业内部进行分工。在云计算条件下，经营集中业务的，是基础业务服务商，如基础设施服务提供商(在IaaS情况中，如亚马逊)、平台服务提供商；经营分散业务(端业务)的，则是应用企业(如阿里巴巴的店主、苹果iPad开发者)。集中业务的共同点，都在承担初始固定资本投入的工作；分散业务的共同点，都在承担边际成本投入的工作。这里出现了经济学上的一个“意外情况”。云

31、计算居然是在进行初始固定投入与边际投入之间的社会分工。一部分厂商专注于初始固定投入，从事的是基础业务；另一部分厂商专注于边际投入，从事的是增值应用业务。而且从事边际投入业务的厂商，可以重复分享从事初始固定投入业务的厂商的资源。例如，网店店主在分享阿里巴巴免费提供的平台；iPad开发者在分享苹果提供的开发工具和网上商店。在这里，初始固定投入与边际投入结合的单位，不再是一个企业，而是一个商业生态共同体。这种情况，是传统经济没有的现象。传统经济的典型特点是，每个企业自己从事初始固定资本投入，如自己采购设备；自己进行边际投入。在从事生产时，都会利用专用资本，同时进行固定成本与流动成本、初始固定投入与边

32、际投入的投资。通俗地说，就是自己盖厂，自己生产。但是在云计算条件下，企业可以是别人盖厂，自己生产。而且别人盖的厂子，可以大家分享。谁想生产，就去分享别人建成的基础设施(I，信息基础设施)、“厂房”(P，平台)和“设备”(S，软件)，通过服务器共享资源。当然，分享不是白分享，在苹果案例中，双方的关系是三七分成。提供服务器共享资源的得三成，应用开发者得七成。相当于生产者在租赁厂房和设备，服务商在提供厂房和设备的租赁服务。为什么会出现这种现象？这要归结到生产资料的特点不一样。首先，厂房和设备得通用。这点对于传统经济很难。你不能租木工的手摇钻去打井，因为设备不通用。生产设备的实体性，导致它的专用性强，

33、而通用性弱。人们可以租赁生产资料，但由于通用性限制，成不了太大气候。而云计算的生产资料是虚拟的，通用性强，而专用性弱，iPad上可以进行五花八门的应用开发，使的工具都是相同的。其次，云计算的基础设施、平台和软件，可反复使用、多次使用，其使用价值几乎不会耗损。例如淘宝平台上的店主越多，平台的价值越高(相当于馒头越吃反而越多)。互补方式是指，集中业务(基础业务，初始固定投入)承担方以分享的方式“补”分散方，分散业务(增值应用，边际投入)承担方以交租金的方式“补”集中方。二者各得其所。其经济学上的特征，是规模经济与范围经济，即以共享方式配置资源比分别投入方式配置资源，取得的总效果更大(即规模或品种上

34、的一加一大于二，近似于成本次可加性、成本弱加性)。2.6项目概要设计 项目概要设计框图如下： 计算机服务器 存储器 外接设备： 计算机 手机等 输入 输出 图2.12.6.1框架结构该系统由一部装有服务器端程序的服务器和若干台装有客户端程序的客户端计算机组成。其中，服务器端主要负责核对用户身份，生成、存储以及分发密钥；客户端和可以从服务器端获取密钥；对客户端本机的文件进行加密，还可以与其他的客户端之间以密文形式传送加密信息。根据功能，得到系统框图2.2,系统拓扑图2.3。数据加密提交至云上查看结果Cloud computer下载解密 图2.2RSA加密、解密模块加密、解密文件流密钥用 户 界

35、面文件加密解密控制密文cloud computer 图2.3 2.6.2模块划分该系统由一部装有服务器端程序的服务器和若干台装有客户端程序的客户端计算机组成。其中，服务器端主要负责核对用户身份，生成、存储以及分发密钥；客户端和可以从服务器端获取密钥；对客户端本机的文件进行加密，还可以与其他的客户端之间以密文形式传送加密信息。根据功能，得到系统框图如下（图 2.4）：加密与解密系统加密模块算法实现与测试密钥生成与管理界面模块 图2.4 功能模块图根据供求分析得到的上图，将系统按功能划分成了以下几大功能模块（图示如上图）：界面模块、加密模块、密钥管理模块（只在服务器端程序有）。加密与解密系统算法实

36、现与测试加密模块密钥生成与管理界面模块RSAELGamal密钥存取密钥生成读取密钥保存密钥公钥计算私钥生成大随机数 图2.5 具体加密解密模块图2.7运行环境说明我们使用的是Visual Studio 2008集成开发环境。整个软件将用C+语言在VS2008集成开发环境下编写。鉴于软件规模较小，而且根据先前很多成熟的开发经验，很多软件公司都省略掉了详细设计这一部分，直接从概要设计起手做编码。借鉴这种经验，我们将详细设计的工作一半分给了概要设计、另一半在编码的过程中加以完成，故有效地缩短了开发周期。第三章 同态加密方案3.1同态加密的概念设一个代数系统U，它有一个集合，一组运算，一组谓词，一些可

37、出现的字符,我们把这代数系统定义为。例如，在整数集合下有这样的代数系统Z;+,-,*,/;0,1；再设一个代数系统C，把它定义为；有一个加密函数，和与之对应的解密函数；对于，满足，；如果是同态的，则满足，。 下面举一个简单的例子来说明这种性质： 对于一个整数群，Z;+,-,*,/;0,1，如果，对于两个明文，对其进行加密，得到密文后，对密文进行加运算，可以得到以下等式： 即： 则它满足加同态。再对密文进行乘运算，得到以下等式： 即： 因此它不满足乘同态。 再来看另一个例子。如果，对于两个明文，对其进行加密，得到密文后，对密文进行乘运算，可以得到以下等式： 即： 则它满足乘同态。用同样的方法，可

38、以得出，它不满足加同态。像以上举这样的例子，要么只满足加同态，要么只满足乘同态的称为偏同态。只有同时满足加同态和乘同态，才称为全同态。在文中给出的就是一个全同态方案。3.2传统公钥加密体制的同态性ElGamal在群G里，公钥为(G,q,g,h)，其中，x是私钥。加密函数，其中，则有下式：所以，ElGamal满足乘同态。RSA在群G里，选取两个大素数p和q，令n=p*q。公钥为，私钥为，其中，加密函数。则有下式： 所以RSA满足乘同态。3.3 ElGamal算法的实现流程密钥对产生办法。首先选择一个素数p，两个随机数, g 和x，g, x p, 计算 y = gx ( mod p )，则其公钥为

39、 y, g 和p。私钥是x。g和p可由一组用户共享。ElGamal用于数字签名。被签信息为M，首先选择一个随机数k, k与 p - 1互质，计算a = gk ( mod p )再用扩展 Euclidean 算法对下面方程求解b：M = xa + kb ( mod p - 1 )签名就是( a, b )。随机数k须丢弃。验证时要验证下式：ya * ab ( mod p ) = gM ( mod p )同时一定要检验是否满足1= a p。否则签名容易伪造。ElGamal用于加密。被加密信息为M，首先选择一个随机数k，k与 p - 1互质，计算a = gk ( mod p )b = yk M ( m

40、od p )( a, b )为密文，是明文的两倍长。解密时计算M = b / ax ( mod p )ElGamal签名的安全性依赖于乘法群(IFp)* 上的离散对数计算。素数p必须足够大，且p-1至少包含一个大素数。3.4 RSA算法的实现流程RSA的算法涉及三个参数，n、e1、e2。其中，n是两个大质数p、q的积，n的二进制表示时所占用的位数，就是所谓的密钥长度。e1和e2是一对相关的值，e1可以任意取，但要求e1与(p-1）*(q-1）互质；再选择e2，要求（e2*e1）mod(p-1）*(q-1）=1。（n，e1）,(n，e2）就是密钥对。其中(n，e1）为公钥，(n，e2）为私钥。R

41、SA加解密的算法完全相同，设A为明文，B为密文，则：A=Be2 mod n；B=Ae1 mod n；（公钥加密体制中，一般用公钥加密，私钥解密）,e1和e2可以互换使用，即：A=Be1 mod n；B=Ae2 mod n; 3.4.1密钥生成密钥生成的过程的核心大素数生成的实质是反复生成大整数，并进行快速素性检测，直到生成的大整数符合要求，然后将该大素数返回这样一个过程。 1 .选取长度相等的两个大素数p 和 q ,计算其乘积:n = p q然 后随机选取加密密钥e,使e和( p1 )( q1 )互素。 最后用欧几里德扩展算法计算解密 密钥 d ,以满足e d = 1 (mod ( p1 )

42、( q1 ) 即 d = e1 mod ( (p1 )( q1 ) e和n是公钥,d 是私钥。 2 .加密公式如下：c i = m i e（mod n） 3. 解密时 ，取每一密文分组c i并计算：m i = c i d（m o d n）Ci d =（mi e） d = mi (e d ) = m i k（p1）（q1）+ 1 = mi ,m i k（p 1）（q1 = m i * 1 = m i 4. 消息也可以用d加密用e解密算法的C语言描述如下void main()int p,q,e,d,m,n,t,c,r;printf(请输入两个素数p,q: );scanf(%d%d,&p,&q);n

43、=p*q;printf(计算得n 为%3dn,n);t=(p-1)*(q-1); /求n 的欧拉数printf(计算得t 为%3dn,t);printf(请输入公钥e: );scanf(%d,&e);if(et|fun(e,t)printf(e 不合要求，请重新输入: ); /et 或e 与t 不互素时，重新输入scanf(%d,&e);d=1;while(e*d)%t)!=1) d+; /由公钥e 求出私钥dprintf(经计算d 为%dn,d); 主函数实现求N的欧拉数,由公钥求解私钥、加密解密选择以及相应的密文明文输出。文中提到的欧几里得算法又称辗转相除法，自从被提出之时起，至今已经历了

44、两千多年，仍然是计算两个数的公约数最高效的算法。利用欧几里得算法可以快速地通过公钥e计算出私钥d，或者通过私钥d反求出公钥e。其计算过程如下： 设：在等式 中，ab（反之亦然）。则，该等式等价于：。又由于的结果必定小于b ，所以还可以对上式子 再使用欧几里得算法。由于算法是对x、y 的系数辗转取模运算、替换原有系数，所以该算法又称辗转相除法。下面是对该算法实际举例：例如：11x-49y=1，求x（a） 11 x - 49 y = 1 49%11=5 （b） 11 x - 5 y = 1 11%5 =1（c） x - 5 y = 1令y=0 代入（c）得x=1令x=1 代入（b）得y=2令y=2 代入（a）得x=9用C语言描述该算法的过程如下：int candp(int a,int b,int c) /数据处理函数，实现幂的取余运算 int r=1;b=b+1;while(b!=1)r=r*a;r=r%c;b-;printf(%dn,r