（计算机系统结构专业论文）rsa密码系统中的并行算法研究.pdf

内蒙古大学硕上学位论文 r s a 密码系统中的并行算法研究 摘要 近年来，随着网络技术的发展，安全问题越来越引起人们的关注。根据各 _? 种安全技术和应用的需求，人们提出了许多加密算法。其中r s a 体制被认为是 公钥密码体制研究的一个标准模板。r s a 的特点是算法完善，安全性良好，易 于实现和理解，便于密钥管理。但其计算量大、耗时太多的缺点是制约其广泛 应用的瓶颈。因此r s a 加密算法的快速实现( 包括算法优化和程序优化) 一直以 来都是研究热点。 随着多核技术与并行技术的发展，计算机系统的计算能力得到了巨大的提 升。然而硬件技术的飞速发展，必然带来软件编程方式的改变。通过使用 o p e n m p ，p t h r e a d s 等多线程技术，可以利用c p u 内更多的计算引擎，从而提高 程序的效率。而通过使用m p i 消息传递并行接口可以启用多个节点来共同完成 计算，从而缩短运算时间。在多核机群中，如果将两种并行技术结合，那么可 以使程序获得更好的性能。 本文正是基于以上背景，在理解传统r s a 算法原理的基础上，充分挖掘r s a 算法的并行性，再结合m p i 、o p e n m p 和p t h r e a d s 等并行技术和利用o p e n s s l 软件包，设计、实现了r s a 并行算法，并取得了明显的效果。最后通过测试对 比，分析了5 种r s a 并行算法的性能差异。 关键词：r s a ，o p e n s s l ，m p i ，o p e n m p ，p t h r e a d s r s a 密码系统中的并行算法研究 r e s e a r c ho fr s ap a r a l l e la l g o i u t h m a b s t r a c t i nr e c e n ty e a r s ，w i t ht h ed e v e l o p m e n to fn e t w o r k ，t h es e c u r i t ya r o u s e sp e o p l e s i n t e r e s tg r a d u a l l y v a r i o u sc r y p t o g r a p h ya l g o r i t h m sh a v eb e e np r e s e n t e dt om e e t d i f f e r e n ts e c u r i t y t e c h n o l o g ya n da p p l i c a t i o nn e e d s r s ai s c o n s i d e r e da sa n e x c e l l e n t c r y p t o s y s t e m i t sa l g o r i t h mi sp r e f e c t i t i s e a s y t or e a l i z ea n dt o u n d e r s t a n d i ti sa d v a n t a g e o u sf o rk e ym a n a g e m e n t b u ti t sh u g ec o m p u t a t i o nl o a d r e s t r i c t si t s w i d e s p r e a da p p l i c a t i o n t h e r e f o r e ，t h eo p t i m i z a t i o no ft h er s a c r y p t o g r a p h ya l g o r i t h mh a sb e e nt h eh o ts p o to ft h er e s e a r c h 一一 w i t hm u l t i - c o r ea n dp a r a l l e l t e c h n o l o g y sd e v e l o p m e n t ，c o m p u t e rs y s t e m s c o m p u t i n gp o w e ro b t a i n st h eh u g ep r o m o t i o n h o w e v e rh a r d w a r et e c h n o l o g y ss w i f t d e v e l o p m e n tb r i n g st h ec h a n g eo ft h es o f t w a r ep r o g r a m m i n gi n e v i t a b l y w i t h m u l t i t h r e a dt e c h n i q u e ，o p e n m pa n dp t h r e a d s ，t h ep r o g r a mc a nu s et h em o r e c o m p u t a t i o ne n g i n e si nc p u ，w h i c he n h a n c e st h ee f f i c i e n c y w i t hm p i ，t h ep r o g r a m c a nu s em a n yn o d e st oc o m p l e t et h ec o m p u t a t i o nt o g e t h e r ，w h i c hr e d u c e st h e o p e r a t i o nt i m e w i t hu n i o n so ft w ok i n d so fp a r a l l e lt e c h n o l o g i e s ，t h ep r o g r a mc a n o b t a i nab e r e r p e r f o r m a n c ei nm u l t i c o r ec l u s t e rs y s t e m b a s e do nt h ea b o v eb a c k g r o u n d ，t h ep r i n c i p l eo ft r a d i t i o nr s aa l g o r i t h mi s i n t r o d u c e da tf i r s t s e c o n d l y ，t h ep a r a l l e l i s mo fr s ac r y p t o g r a p h ya l g o r i t h mi s a n a l y s e d t h i r d l y ，w i t hm p i ，0 p e n m p ，p t h r e a d sa n dt h es d ko fo p e n ss l ，t h er s a 内蒙古人学硕士学位论文 p a r a l l e la l g o r i t h m s o r ed e s i g n e da n dr e a l i z e d ，w h i c ho b v i o u s l yi m p r o v et h e p r o c e s s i n go fe n c r y p t i o na n dd e c r y p t i o n f i n a l l yt h r o u g ht h et e s t ，t h ep e r f o r m a n c e d i f f e r e n c eo ff i v ek i n d so fr s a p a r a l l e la l g o r i t h m si sa n a l y s e d k e y w o r d ：r s a ，o p e n s s l ，m p i ，o p e n m p ，p t h r e a d s i i i 内蒙古大学硕士学位论文 图表目录 表3 1 o p e n s s l 部分目录的功能15 表3 2c r y p t o 子目录列表1 6 表4 1r s a 主要源代码文件2 5 表4 2r s a 的主要函数及功能2 7 表5 1r s a 并行程序的文件结构与功能。3 9 表6 1 单节点上r s a 并行程序的运行时间4 2 表6 2 o p e n m p 与p t h r e a d s 的比较4 2 表6 3r s a 的m p i 并行化程序运行时间4 4 表6 4r s a 的m p i 并行化程序加速比4 4 表6 5r s a 的m p i + o p e n m p 并行化程序运行时间4 5 表6 6 r s a 的m p i + o p e n m p 并行化程序加速比4 5 表6 7r s a 的m p i + p t h r e a d s 并行化程序运行时间4 6 表6 8r s a 的m p i + p t h r e a d s 并行化程序加速比4 6 图5 1r s a 的m p i 并行算法流程图3 0 图5 2r s a 的o p e n m p 并行算法流程图3 3 图5 3r s a 的p t h r e a d s 并行算法流程图3 4 图5 4r s a 的m p i + p t h r e a d s 并行算法流程图3 6 图5 5r s a 的m p i + o p e n m p 并行算法流程图3 8 图6 1r s a 的m p i 并行化程序加速比4 4 图6 2r s a 的m p i + o p e n m p 并行化程序加速比4 5 图6 3r s a 的m p i + p t h r e a d s 并行化程序加速比4 7 v i i 原创性声明 本人声明：所呈交的学位论文是本人在导师的指导下进行的研究工作及取得的研究成果。除本文已经 注明引用的内容外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得由墓直太堂及其 他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示谢意。 学位论文作者签名：羞叁1 2 尘指导教师签名：壅壹 在学期间研究成果使用承诺书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：内蒙古大学有权将学位论文的全 部内容或部分保留并向国家有关机构、部门送交学位论文的复印件和磁盘，允许编入有关数据库进行检索， 也可以采用影印、缩印或其他复制手段保存、汇编学位论文。为保护学院和导师的知识产权，作者在学期 间取得的研究成果属于内蒙古大学。作者今后使用涉及在学期间主要研究内容或研究成果，须征得内蒙古 大学就读期间导师的同意；若用于发表论文，版权单位必须署名为内蒙古大学方可投稿或公开发表。 、岍 学位论文作者签名： 基1 2 ：担 指导教师签名： 内蒙古大学硕士学位论文 1 1 论文研究背景 第一章绪论 随着计算机技术的发展，计算机已经在人们的生活中有了不可替代的位置。每天都有大 量的信息需要依赖强大的计算机系统来处理，然而，一旦计算机系统发生安全问题，就可能 造成信息的丢失、篡改、伪造、假冒等严重后果。因此，如何保障信息安全越来越受到人们 的重视，也是当前一个需要立即解决的严峻问题。 计算机信息安全涉及到多方面的内容，各种安全策略必须相互配合才能真正起到保护作 用。信息加密作为一项基本技术是所有通信安全的基石，其目的是为了防止信息未经授权就 被泄漏、篡改和破坏，同时防止对通信业务进行分析。随着计算机网络的发展和普及，传统 的对称密钥系统逐步暴露了它的严重缺陷。自1 9 7 6 年斯坦福大学的d i f f i e 和h e l l m a n 首次 提出公开密钥体制( 又称非对称密钥系统) 以来，公开密钥系统的研究已成为信息安全领域中 一个引人瞩目的研究课题。公开密钥系统的特征有：计算量大、加密解密速度慢、密钥长度 要求高和密钥分发比较容易。 非对称加密算法中最著名也是具代表性的是由美国m i t 的r i v s e t 、s h e m i r 、a d l e m a n 于 1 9 7 7 年实现的r s a 算法【。r s a 密码算法完善，既可用于数据加密，又可用于数字签名， 安全性良好，易于实现和理解。已成为一种应用极广的公钥密码体制。在广泛的应用中，不 仅它的实现技术日趋成熟，而且安全性也逐渐得到事实的证明。r s a 体制的特点使得它成为 公钥密码体制研究的一个标准模板【i 】。同时，由于r s a 算法发展至今，在实现技术上已经相 当成熟，因此本文算法的实现在许多方面都可以利用己有的技术，这对增强算法的实用性是 非常有益的。 虽然r s a 算法的安全性得到了人们的认可，但是r s a 的安全性是基于大数分解的困难 性。可以说r s a 的安全性同模数的长度成正比【。模数的长度越大，分解它就越困难，算法 的安全性也就越高。但是模数的长度越大，加密、解密运算所需要的时间就越长，算法实现 的速度也就越慢。为了尽可能使用大的模数而又不影响系统实现的速度，实际应用中通常使 用专门的硬件实现r s a 算法。 r s a 算法中最重要的影响速度的实现细节是加密、解密中的算术运算。因此关于如何实 现快速的r s a 算法也是目前的一个研究热点。r s a 算法的快速实现研究，包括算法优化和 r s a 密码系统中的并行算法研究 程序优化、软件实现和硬件实现。 随着多核技术和并行技术的发展，个人计算机的运算能力和计算机间的协同工作能力都 有了巨大的提高，所以研究r s a 的并行算法具有非常重要的现实意义。 并行计算技术提高了算法的效率，公钥系统的加解密技术确保了计算机网络的安全，所 以把并行技术和密码学技术结合起来研究r s a 密码系统的并行加密和解密算法具有重要的 理论意义和实用价值。 1 2 国内外研究现状 国内目前在密码基础理论的某些方面的研究做的很好，提出了一些公钥密码，另外在公 钥密码的快速实现上也做了一定的工作，比如在r s a 的快速实现和椭圆曲线公钥密码的快 速实现方面都有所突破。但在实际应用方面与国外的差距较大，没有自己的标准，也不规范。 国外目前不仅在密码基础理论方面的研究做的很好，而且在实际应用方面也做的非常 好。理论方面不断提出新的密码算法，并制定了一系列密码标准和应用规范。应用方面，一 些密码算法已经得到实际的应用，如r s a 算法已经在认证码，数字签名，身份识别，密钥 管理等技术中得到了应用。 然而，无论是国内还是国外，公钥密码算法的速度问题一直是人们关注的热点，也是实 际应用中的最大难点，因此公钥密码算法的快速实现( 包括算法优化和程序优化) 是当前的研 究热点。 1 3 论文研究的内容 本文主要采用多核技术以及并行技术来研究和设计r s a 并行算法，并通过r s a 并行算 法的实现来提高其加密解密速度。在r s a 算法的并行化过程中，作者分别使用p t h r e a d s 、 o p e n m a 、m p i 、m p i ( 节点f 日- j ) + p t h r e a d s ( 节点内) 和m p i ( 节点间) + o p e 洲p ( 节点内) 五种方式来 实现r s a 并行算法，并通过实验对其进行一系列的测试与分析。 本文对单个节点上的分析是基于一台含有1 个i n t e l ( r ) p e n t i u m ( r ) d ( p 8 2 02 8 0g h z ，双 核) 微处理器的计算机，采用l i n u x 操作系统的一个发行版f e d o r a 8 0 。线程库采用的是支持 o p e n m p 编译制导的g c c 4 1 2 版本，m p i 使用的是m p i c h l 。 对于机群系统，是基于本校实验室内的一个实验机群系统，一共4 个节点，每个节点含 有1 个i n t e l ( r ) p e n t i u m ( r ) d ( p 8 2 02 8 0g h z ，双核) 微处理器。操作系统采用f e d o r a 8 0 ，线 2 内蒙古火学硕士学位论文 程库采用的是支持o p e n m p 编译制导的g c c 4 1 2 版本，m p i 使用的是m p i c h l 。 1 4 论文结构 本论文分为六章。基本组织结构如下： 第一章绪论，讨论了国内外研究现状、本文的研究目标和意义以及创新点。 ：? 第二章并行编程模型，概述近年来多核技术的发展对编程模式所产生的影响和介绍并行 编程环境的搭建。 第三章开源工具包o p e n s s l 介绍，详细分析了o p e n s s l 的结构与功能，以及简要说明 了其在l i n u x 下的安装过程。 第四章r s a 公钥密码体制，介绍了r s a 加密算法的数学基础，以及加密原理，并举例 说明了r s a 算法的加解密过程。 第五章r s a 并行算法设计与实现，在理解了o p e n s s l 中r s a 源码的基础上，详细分析 了r s a 算法的可并行性，并结合o p e n s s l 开源工具包和并行技术设计实现了r s a 并行算法。 第六章测试对比及结果分析，通过测试r s a 并行算法，验证并行化后性能提升的效果， 并对比r s a 并行化算法之间的性能差异，最后给出分析结果。 第七章总结和进一步的工作。 1 5 论文创新点 本文基于多核技术和开源工具包o p e n s s l 研究r s a 算法的并行设计，分析当前多核技 术及其发展趋势，详细介绍了o p e n s s l 开源工具包，设计实现了r s a 的并行算法。本文主 要取得以下一些成果： 1 基于并行技术和o p e n s s l 开源工具包设计实现了r s a 并行算法，使其在多核处理器 和多核机群系统上的运行速度得到提升。 2 用多种并行技术分别实现r s a 并行算法，通过实验对比各r s a 并行算法的性能差异。 r s a 密码系统中的并行算法研究 第二章并行编程模型 2 1 多核技术对编程的影响 多内核是指在一枚处理器中集成两个或多个完整的计算引擎( 内核) f 熨。多核处理器的出现 实际上是一次编程方式的革命 3 1 。在多核处理器出现之前，单核处理器时钟频率的提升对程 序员而言是透明的，软件开发人员不需要针对处理器的特点来开发程序，只是单纯依靠提高 时钟速度来提高单线程应用程序的速度；如今随着多核技术的发展以及多核处理器的普及， 如果软件开发人员编写的程序没有针对多核的特点来设计，那么就不能发挥多核处理器的并 行处理能力 2 1 。因此，开发人员应该学习如何正确设计自己的应用程序，使其能够在多核环 境中运行。多核架构的单个处理器封装中包含两个或更多处理器“执行内核”或计算引擎， 在适当软件的辅助下，完全可以并行执行多个软件线程。 多核的好处非常明显。首先，由于是多个执行内核可以同时进行运算，因此可以显著提 升计算能力，而每个内核的主频可以比以前低，因而总体功耗增加不太。其次，与多c p u 相 比，多核处理器采用与单c p u 相同的硬件架构，用户在提升计算能力的同时无需进行任何硬 件上的改变，这对用户来说非常方便。 尽管多核的好处十分明显，但是能否善加利用还要取决于软件。多核平台使得多个程序 任务的并行执行更加流畅。同时也能更加高效地运行多线程程序。从这个角度上说，整个计 算环境正稳步向一个新的并行化的时代迈进。在这一过程中，多任务的并行执行和程序的并 行化显得尤其重要。也就是说，一个完全串行的程序是很难充分利用多核平台带来的好处的。 这对软件开发人员也就意味着：只有充分挖掘程序的并行性并把并行的理念融入到设计和实 现上才能使多核平台更加物尽其用1 4 1 。 2 2 并行程序的编程模型 一般来说，并行程序设计模型主要分两大类，一类是共享存储模型，一类是消息传递模 型嘲。共享存储模型主要是采用多线程，其主要开发环境是已经成为工业标准的o p e n m p 和 早期的p o s i xt h r e a d s ，目前主要是商业编译器如i n t e l 等的c + + 和f o r t r a n 编译器提供对该语 言的支持，而开源编译器g c c 也开始提供了对o p e n m p 的支持。对于多核来说，o p e n m p 和 早期的p o s i xt h r e a d s 都是可用的标准程序设计环境。虽然可用，但是对一般用户来说比较困 4 内蒙古大学硕上学位论文 难的是消息传递开发环境，包括m p i 和p v m 等，此类开发环境都是开源的，可以免费下载。 其中最常用的两个m p i 标准实现是m p i c h 和l a m m p i 。其中的l a m f m p i 也在从m p l l 0 版本向m p l 2 0 版本过渡，其下一代软件的名称是o p e nm p i ，已经发布了正式版本【3 1 。此外， 由于现有机器体系结构层次非常复杂，还可以把上面几种并行程序设计环境和向量并行等混 合使用，充分挖掘机器的性能潜力p j 。 并行算法的设计目标是挖掘问题求解过程的并行性，寻求并行算法和并行机器体系结构 的最佳匹配和映射，合理的组织并行任务，减少额外消息传递和数据移动开销。总体来说， 开发一个并行程序可以有三种途径【3 j ，一个途径是串行程序自动并行化，该技术尚在摸索阶 段。第二条途径是设计全新的并行程序设计语言，但它的代价就是需要全部改写原来的程序， 对用户来说成本和风险就相当高了，而且效率还没有保证。但是随着多核的出现，如果面向 大众推广并行计算环境的话，就必须有一种新的大众容易接受的程序设计语言，否则很难推 广普及。目前国际上正在研究几种新的并行程序设计语言。第三种途径就是串行语言加并行 库或编译制导语句的扩展，实际上就是增加一个库或一些新的制导语句来帮助进行消息传递 和并行。这正是m p i 和o p e n m p 所采取的途径，但缺点是程序开发效率很低，难度也比较大。 随着处理器体系结构变得越来越复杂，从语言到机器硬件的鸿沟越来越大，需要程序设 计语言对底层体系结构进行高度抽象，使用户的程序设计变得简单高效，同时又不损失过多 的性能。编译器就需要做很多工作来弥补这个鸿沟。现在大部分的多核处理器主频都是比较 低的，主要目的是为了降低散热和功耗。因此如果多核处理器的几个核没有被真正用起来， 让它们同时合作去完成一个任务，而只是一个核工作的话，摩尔定律就不起作用了。对很多 媒体应用，或大量相互之间不相关的w e b 访问来说，它们之间是没有依赖关系的，用户不必 改写程序，就自然可以通过操作系统的多核调度来获得性能的提升。但对于计算强度很大的 程序来说，如科学计算等，里面有大量数据要串行处理，且存在复杂的数据相关性，如果不 进行数据分割的话，只能由一个低频的单核来处理，执行时间会很长。即使很多应用可以同 时运行，多核还会带来一个运行资源冲突的问题，多核同时运行期间很多资源其实是共享的， 比如高速缓存、存储体、b u s 等，这就需要改进操作系统和用户调度，来加以缓解【3 】。 多核作为一种新的并行层次原来是没有的，如今，应对多核的方式最简单的是从硬件底 层对多核加以隐藏，让用户感觉不到，这是最理想的。用户的指令运行时，底层硬件进行相 关性分析，并在多核间进行调度。但这种方法的可扩展性很成问题。适用性是不是很广也成 问题，且增加了处理器设计的复杂性，很容易成为性能瓶颈和提高生产成本。对小规模问题 和少量的核来说也许可以，但问题规模更大或核数量更多之后，就不可行了。另外一个很自 r s a 密码系统中的并行算法研究 然想到的办法，就是把高端计算里面并行程序设计的语言和环境如m p i 和o p e n m p 、p o s i x t h r e a d s 等一起来用。再根据多核的特点，充分利用新的体系结构优势，加以性能优化。这是 自然且可行的应对措施【3 1 。 2 2 1 共享存储并行编程 在2 0 世纪8 0 年代，高性能的科学和工程计算中基于共享变量的共享存储的编程模式曾 是一统天下。进入2 0 世纪9 0 年代后，尽管分布式存储的大规模并行处理系统已夺走了峰值 计算速度的桂冠，但共享存储的并行处理仍以其可编程性和系统的可用性的优势，在科学和 工程计算中与分布存储系统共领风骚【6 】。 在共享存储的编程模式中，各个处理器可以对共享存储器中的数据进行存取，数据对每 个处理器而言都是可以访问到的，不需要在处理器之间进行传送，即数据通信是通过读写共 享存储单元来完成的。 共享存储的并行程序设计的基本问题包括【6 j ： 任务划分：任务划分就是把一个程序划分成若干个可以分配给不同的处理器去并行执行 的一组任务，划分的方法与并行程序设计风格相关：单程序多数据流( s p m d ) 编程风格采 用按数据流划分任务的方法，即域分解法，它将要计算的问题的区域分解成多个子域，每个 任务计算一个子域，这样实现的并行也称为数据并行；多程序多数据流( m p m d ) 编程风格 则采用按控制流划分任务的方法，即功能分解法，它将要计算的问题分解成多个子问题，每 个任务计算一个子问题，这样实现的并行也称为控制并行。 任务调度：调度就是把一个任务集合分配给一组处理器，传统的调度是操作系统管理的 事，但因为由操作系统施行调度开销较大，且操作系统难于从程序中获得优化调度信息，所 以现代并行机上一个程序内的调度多由用户、编译器和运行库来完成。任务调度有静态调度 和动态调度之分：静态调度( s t a t i cs c h e d u l i n g ) 由程序员在编程时，或者编译器在编译时将 任务分配给处理器。静态调度有确定的和非确定的两种模式：确定模式( d e t e r m i n i s t i cm o d e ) 任务之间的优先关系和任务所需的执行时间在调度之前是固定的已知的，常可使用g a n t t 图 来说明调度过程；非确定模式任务的执行时间可表示为一随机变量，这就使得调度问题更为 困难。动态调度在运行时将任务分配给处理器，分配的策略是在编程或编译时确定的，但具 体的分配是在运行时才能确定的。 6 内蒙古大学硕士学位论文 任务同步：同步对并行程序设计是非常重要的，同步常用来确定任务期间正确的执行次 序，或用于确保各任务对共享变量的正确的读写次序。简单高速的同步机制一般由硬件支持， 复杂多功能的同步机制常由软件实现。 任务通信：在共享存储系统中，任务间的通信借助于读写共享变量来完成，不需要专门 的机制，但应注意读写的时机，即要在发送者将正确的信息送出之后，接收者才可以读取， 为此常要使用路障同步操作，其实同步也可视为一种特殊韵通信，只不过所交换的是控制信 息，而不是一般通信所交换的数据信息。 纯共享存储环境的主要特点是：系统中存在着一个集中的，公共的共享存储器；系统中 集中的存储器对程序员而言是全局统一编址的；系统不提供对非一致存储访问应用程序的任 何支持。近代的纯共享存储并行编程标准有，p t h r e a d s 和o p e n m p 掣引。 p o s i x ( p o r t a b l eo p e r a t i n gs y s t e mi n t e r f a c e ) t h r e a d s ，即p t h r e a d s ，代表官方i e e e p o s 1 0 0 3 i c 1 9 9 5 线程标准，系由i e e e 标准委员会所建立，其功能和界面类似于s o l a r i s 线程的功能与界面【6 】。 o p e n m p 并行编程模型，首先，o p e n m p 是基于线程的并行编程模型( p r o g r a m m i n gm o d e l ) ， 一个共享存储的进程由多个线程组成，o p e n m p 就是基于已有线程的共享编程范例；其次， o p e n m p 是一个外部的编程模型，而不是自动编程模型，它能够使程序员完全控制并行化。 o p e n m p 使用f o r k j o i n 并行执行模型。所有的o p e n m p 程序开始于一个单独的主线程( m a s t e r t h r e a d ) 。主线程会一直串行的执行，直到遇见第一个并行域( p a r a l l e lr e g i o n ) 才开始并行执 行。实际上，所有o p e n m p 的并行化，都是通过使用嵌入到c c + + 或f o r t r a n 源代码中的编译 制导语句来达到的。并且，一个o p e n m p 应用编程接i z i ( a p i ) 的并行结构可以嵌入到别的并行 结构中去。应用编程接口还可以随着不同并行域的需要动态地改变线程数 7 1 。有些应用也可 能不支持上述性质。 在共享内存模型中，一个并行程序由多个共享内存的并行任务组成，数据的交换通过隐 含地使用共享数据来完成。此编程模式一般仅需指定可以并行执行的循环，而不需考虑计算 与数据如何划分，以及如何进行任务间通信，编译器会自动完成上述功能。确定程序的并行 性、数据的共享私有等信息。其目标是为s m p 系统提供可移植、可扩展的开发接口。o p e n m p 由o p e n m pa r c h i t e c t u r er e v i e wb o a r d 于1 9 9 7 年推出，现在已发展到2 0 版。o p e n m p 起源于 a n s ix 3 h 5 标准，它具有简单、移植性好和可扩展等优点，是共享存储系统编程的一个工业 标准。实际上o p e n m p 并不是- - i - j 新的语言，它是对基本语言( 如f o r t a n 7 7 、f o r t a n 9 0 、c 、 c + + 等) 的扩展。o p e n m p 规范中定义的制导指令、运行库和环境变量，能够使用户在保证程 7 r s a 密码系统中的并行算法研究 序的可移植性的前提下，按照标准将已有的串行程序逐步并行化。制导指令是对程序设计语 言的扩展，进一步提供了对并行区域、工作共享、同步构造的支持，并且支持数据的共享和 私有化。这样，用户对串行程序添加制导指令的过程，就类似于进行显式并行程序设计。运 行库和环境变量，使得用户可以调整并行程序的执行环境。o p e n m p 的提出，是希望遵循该 并行编程模型的并行程序，可以在不同的产商提供的共享存储体系结构间比较容易地移植。 实际上，已经有许多硬件和软件供应商提供支持o e p n m p 的编译器，如d e c 、i n t e l 、i b m 、 h p 、s u n 、s o l 、及u s d o ea s c ip r o g r a m 等，并且包括了u n i x 和n t 两种操作系统平台。 目前，f o r t r a n 7 7 、f o r t r a n 9 0 、c 、c + + 语言的实现规范已经完成 6 1 。 2 2 2 消息传递并行编程 在消息传递模型中，一个并行程序由多个并行任务组成。每个并行任务拥有自己的数据 并对其进行计算操作。任务之间数据的交换是通过显式的消息传递语句来完成的。 现在广泛使用的消息传递模型有两个：p v m 和m p i 。p v m 即p a r a l l e lv i r t u a lm a c h i n e ( 并 行虚拟机) 与m p i 即m e s s a g ep a s s i n gi n t e r f a c e ( 消息传递接口) 。p v m 与m p i 所提供的功能大 致相同，但两者的侧重点有所不同。p v m 强调在异构环境下的可移植性和互操作性，程序之 间可以互相通信，并支持动态的资源管理和一定程度的容错；而m p i 更强调性能，不同的 m p i 实现之间缺乏互操作性，本身也不支持容错( 可以通过专门的容错软件来支持容错) 。 一般而言，使用m p i 比较适合于开发m p p 或同构机群上的并行应用，可以有较高的通信性 能；而p v m 更适合于异构的机群系统。几乎所有的高性能计算系统都支持p v m 和m p i t l l 】。 2 3 并行编程环境的搭建 2 3 1f e d o r a 8 0 下m p i c h l 的安装与配置 l 、利用n f s 建立单一文件目录系统 ( 1 ) 在终端中键入撑s e t u p ，在s y s t e ms e r v i c e s 里将n f s l o c k 、n f s 、n e t f s 服务选中。 ( 2 ) 在服务器端和客户端建立统一的目录c l u s t e r ，在服务器端声明c l u s t e r 目录被哪些节点识 别，在文件e t c e x p o r t s 中写入：c l u s t e ri p ( r w ) ，其中i p 为允许映射该目录的客户端i p 地址， 参数r w 为读写权限。 ( 3 ) 在客户端声明统一目录的自动挂载，修西u e t c f s t a b 文件，加入：c l u s t e r 0 1 ：c l u s t e r c l u s t e rn f s d e f a u l t s00 ，其中c l u s t e r 0 1 为服务器名或者服务器i p 地址：第一个c l u s t e r 是服务器端的 8 内蒙古大学硕士学位论文 共享目录；第二个c l u s t e r 是客户端的挂载目录；n f s 表示文件格式类型；d e f a u l t s 设定了 权限为缺省设置；第一个零表示系统备份时，不备份该目录的内容；第二个零表示开机 不自动检查该文件系统。 ( 4 ) 机群连接结点声明，在服务器端和客户端修改e t c h o s t s 文件，加入如下语句： i pc l u s t e r 01 i pc l u s t e r 0 2 i p c l u s t e r 0 3 i pc l u s t e r 0 4 ( 5 ) 启动远程访问服务，在s y s t e ms e r v i c e s 里将r e x e c ，r l o g i n ，r s h 服务选中。 2 、配置n i s 服务 ( 1 ) 在服务器端和客户端分别运行命令群d o m a i n n a m en a m e ，其中n a m e 为n i s 域名； ( 2 ) 在s y s t e ms e r v i c e s 里面将y p s e r v 、y p p a s s w d d 和y p b i n d 服务选中； ( 3 ) 在服务器端初始化数据库：运行捍u s r l i b y p y p i n i t _ m ，其中_ m 表示要成为主服务器，然 后按c t r l + d 结束。 3 、安装m p i c h ( 1 ) m p i c h 的获得：可以到h t t p ：w w w s c c a s c n g b l e a m l e a m l 2 0 0 6 0 4 11 0 0 0 1 h t m l 下载m p i c h 1 2 7 p l 。 ( 2 ) 在服务器端c l u s t e r 目录下解压m p i c h 源程序包：拌t a rz x f m p i c h t a r t a r ，此时会得到一个 名为m p i c h 一1 2 7 p l 的文件夹。 ( 3 ) 创建安装的目标目录：荐m k d i rm p i c h l 。 ( 4 ) 进入m p i c h 一1 2 7 p l 文件夹，运行群c o n f i g u r e r s h = s s h 一- p r e f i x = c l u s t e r m p i c h l ，其中- r s h - - s s h 表示使用s s h 来代替r s h ；一p r e f i x = c l u s t e r m p i c h l 表示m p i 的安装目录为c l u s t e r m p i c h l 。 ( 5 ) 编译连接：# m a k e 。 ( 6 ) 安装：拌m a k ei n s t a l l 。 ( 7 ) 节点设置：撑c d c l u s t e r m p i c h l s h a r e m a c h i n e s l i n u x ，在文件m a c h i n e s l i n u x 中加入 m p i 要使用的节点名如下： c l u s t e r 01 c l u s t e r 0 2 c l u s t e r 0 3 c l u s t e r 0 4 9 r s a 密码系统中的并行算法研究 ( 8 ) 路径设置：在e t c p r o f i l e 文件中加入e x p o r tp a t h = e l u s t e r m p i c h l b i n ：$ p a t h 。 2 3 2f e d o r a 8 0 下并行程序的编译 本文中，可以使用支持o p e n m p 编译的g e e 或i c c 编译器来编译这五种并行程序。我们 使用f e d o r a 8 0 下的g e e 4 1 2 版本的编译器，如果需要使用i n t e l 的i c c 编译器，可以到i n t e l 的官方网站下载i n t e l 安装包后安装，这里就不详细说明了，下面主要介绍一下并行程序的编 译。 在自己的用户下使用如下面的命令( 本例为c 语言程序) ： 编译：拌g c c 0 目标文件源文件一l c l u s t e r m p i c h l l i b i c l u s t e r m p i c h l i n c l u d e 1 m p i c h f o p e n m p l p t h r e a d l s s l 其中参数一f o p e n m p 是指明编译o p e n m p 多线程，参数1 m p i c h 是指明编译m p i 并行程序， 参数- l p t h r e a d 指明编译p t h r e a d s 多线程，1 s s l 指明编译o p e n s s l 应用程序。如果需要编译c + + 源文件，可以使用g + + 编译器，参数不变。注意如果是使用i n t e l 的i c c 编译器编译o p e n m p 并行程序时，参数变为一o p e n m p ，其它与使用g c c 编译器编译并行程序的方法相同。 1 0 内蒙古大学硕士学位论文 第三章 开源工具包o p e n s s l 介绍 3 1s s l 安全传输协议 3 1 1s s l 概述 s s l t 2 0 1 是s e c u r es o c k e tl a y e r ( 安全套接层协议) 的缩写，可以在i n t e m e t 上提供秘密性 传输。该协议是n e t s c a p e 公司为了保证w e b 通信协议的安全于1 9 9 4 年开发的。该协议第一 个成熟的版本是s s l v 2 0 ，被集成到n e t s c a p e 公司等各种产品中。 s s l v 2 0 协议基本解决了w e b 通信中的安全问题。1 9 9 6 年，n e t s c a p e 公司发布了s s l v 3 0 ， 增加了对r s a 算法以外的其他算法的支持和一些新的安全特性，并且修改了前一个版本中存 在的安全缺陷。同s s l v 2 0 相比，新版本更加成熟和稳定，因此很快成为事实上的工业标准。 s s l 协议是p k i t 2 1 1 ( p u b l i ck e yi n f r a s t r u c t u r e ) 体系中的网络安全标准协议，被广泛用于互 联网上的安全传输、身份认证等。它采用公开密钥技术，其目标是保证两个应用间通信的保 密性和可靠性，可以在服务器和客户机两端同时进行。现在的w e b 浏览器普遍将h t t p 和 s s l 相结合，从而实现服务器和客户端浏览器间的安全通信。 s s l 采用t c p 作为传输协议提供数据的可靠传输。s s l 工作在t c p 层之上，因此独立于 更高层应用，可为更高层协议( 如f t p 、h t t p 以及t e l n e t 等) 提供安全服务。s s l 提供的安 全服务采用了公钥体制为w e b 服务器和客户机的通信提供保密性、数据完整性和认证。在建 立连接中采用非对称密钥，在会话过程中采用对称密钥。加密的类型和强度则在两端建立连 接的过程中判断决定。s s l 协议在应用层协议通信之前就己经完成了加密算法通信密钥的协 商以及服务器认证工作。在此之后应用层协议所传输的数据都会被加密，从而保证通信的私 密性。s s l 协议提供的安全信道有以下三个特性【9 】： 1 数据的保密性：信息加密就是把明码的输入文件用加密算法转换成加密的文件以实现 数据的保密。加密的过程需要用到密匙来加密数据然后再解密。没有了密钥，就无法解开加 密的数据。数据加密之后，只有密匙要用一个安全的方法传送。加密过的数据可以公开地传 送。 2 数据的一致性：加密也能保证数据的一致性。例如：消息验证码( m a c ) ，能够校验用 户提