（计算机应用技术专业论文）信息安全算法的gpu高速实现.pdf

摘要 摘要 近年来，随着各种高速超大容量网络迅速普及，人们对信息的安全性需求 变得越来越迫切，然而，信息安全技术仍然很落后，且信息安全算法的软件实 施已成为网络性能提高的系统瓶颈。与此同时，计算机图形处理器( g r a p h i c s p r o c e s s i n gu n i t ，g p u ) 近年来得到了极大的发展，从最初局限于图形渲染的图形 卡，发展为如今可编程的并行计算平台。与c p u 的串行计算模式不同，g p u 是 一种高度并行的流处理器。因此，通过对g p u 编程发挥其高强度计算能力来解 决信息安全算法的速度瓶颈，提高算法的执行效率，将是一个十分有应用价值 的研究。 本文首先系统的介绍了六种典型加密算法的基本理论及其实现过程。然后 介绍了g p u 的编程模型，其中重点介绍了d i r e c t x1 0 提出的统一着色器架构。 随后研究了计算统一设备架构( c o m p u t eu n i f i e dd e v i c ea r c h i t e c t u r e ，c u d a ) 的编 程模型和存储器模型，其目的是为了将加密算法移植到g p u 上实现。 本文的核心，提出了一种新的基于g p u 加密的并行化处理方法。 最后给出了五个加密算法的g p u 实现结果，从实验结果可以看出，g p u 上 的实现比c p u 上的实现要快得多，且还存在更大的潜能。 关键词：g p u ；并行计算；加密；c u d a a b s l r a c t a b s t r a c t i nr e c e n ty e a r s ，t h en e e do fi n f o r m a t i o ns e c u r i t yh a sb e c a m ei n c r e a s i n g l yu r g e n t w i t ht h er a p i d l yg r o w i n g p o p u l a r i t yo fh i g h s p e e dn e t w o r k h o w e v e r , t h ei n f o r m a t i o n t e c h n o l o g ys e c u r i t yk e e p s a ti t sl o wl e v e l ，t h es o f t w a r ei m p l e m e n t a t i o no fi n f o r m a t i o n s e c u r i t ya l g o r i t h m sb e c a m et h eb o r l e n e c ko fn e t w o r kp e r f o r m a n c e a tt h es a m et i m e ， g r a p h i c sp r o c e s s i n gu n i ta l s oh a sb e e ng r e a t l yd e v e l o p e d ，c h a n g e df r o mt h ei n i t i a l g r a p h i c sc a r d , w h i c hl i m i t e dt og r a p h i c sr e n d e r i n g ，i n t op r e s e n tp r o g r a m m a b l e p a r a l l e lc o m p u t i n gp l a t f o r m d i f f e r e n tf r o ms e r i a lc o m p u t i n gm o d e lo fc p u ，g p ui sa h i g h l yp a r a l l e ls t r e a mp r o c e s s o r s o ，i tw i l lb eav e r yv a l u a b l ea n dh e l p f u lr e s e a r c ht o s o l v et h es p e e dr e s t r a i n to fi n f o r m a t i o ns e c u r i t ya n di m p r o v ei m p l e m e n t i n ge f f i c i e n c y b yp r o g r a m m i n go ng p u t oe x p l o r ef u l l yi t sh i g hc a l c u l a t i o nc a p a b i l i t y s i xt y p i c a le n c r y p t i o na l g o r i t h m sa n dt h e i ri m p l e m e n t a t i o np r o c e s s e sw i l lb e f i r s t l yi n t r o d u c e di nt h i sp a p e r , f o l l o w e db yg p up r o g r a m m i n gm o d e lt h a tp a ym u c h i m p o r t a n c eo nu n i f i e ds h a d e ra r c h i t e c t u r ew h i c hp r o p o s e db yd i m c t x10 ，a n dt h e n t h ec u d a ( c o m p u t eu n i f i e dd e v i c ea r c h i t e c t u r e ) p r o g r a m m i n gm o d e la n dm e m o r y m o d e l ，t ot r a n s f e re n c r y p t i o na l g o r i t h mi n t ot h eg p u t h ek e yp o i i i to ft h i sp a p e rf o c u so n an e wm e t h o d - - - g p u - b a s e de n c r y p t i o ni n p a r a l l e lw a y i nt h ee n do ft h ep a p e r , f i v eg p u e n e r y p t i o na l g o r i t h m s r e s u l t sw i l lb eg i v e n f r o me x p e r i m e n t s ，y o uc a ns e et h ei m p l e m e n t a t i o no ng p ui sm u c hf a s t e rt h a nt h a t o nc p u ，a n dm u c hm o r ep o t e n t i a li np e r f o r m a n c e k e yw o r d s ：g p u ；p a r a l l e lc o m p u t i n g ；c r y p t o g r a p h y ；c u d a i i 学位论文独创性声明 学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得直昌太堂或其他教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名( 手写) ：代诵 签字日期：如如年月ge l 学位论文版权使用授权书 本学位论文作者完全了解直昌太堂有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权直昌太堂可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编本学位论文。同时授权中国科学技术信息研究 所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：倚娟 签字日期：z 、，| 口年1 月 l ，日 岣 乞月2 笸日 、v f，0 年 破而r 名期 签日币芋师字导签 学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 、作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得直昌太堂或其他教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名( 手写) ：柿垛 签字日期：olo 年1 月三e l 学位论文版权使用授权书 本学位论文作者完全了解直昌太堂有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权直昌太堂可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编本学位论文。同时授权中国科学技术信息研究 所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：竹桷导师签名： 签字日期：矽10 年j 月2 - e t签字e t 期：虎k 矽年拍“日 第一章绪论 第一章绪论 1 1 信息安全的发展历程 信息安全最早出现于人类的信息传递过程中，尤其自2 0 世纪7 0 年代以来， 随着计算机网络的飞速发展，网络信息安全问题不断暴露，信息安全技术也就 越来越被人们重视，并得到了快速发展。目前，信息安全已成为一门独立的学 科，是计算机网络体系中不可或缺的一部分。 到目前为止，信息安全的发展主要经历了三个阶段。第一阶段：信息安全 使用密码学技术保证机密数据的正确传输。第二阶段：信息安全的任务是，确 保信息和信息系统的安全，并没有考虑信息的可用性和有效性。在这一阶段， 信息安全技术主要包括：密码学技术、入侵检测技术、防火墙，等等。第三阶 段：信息安全不仅要保障信息的保密性和安全性，还要实现信息的有效性和可 用性，实现信息的可生存性，进而保障信息更高层次的安全。在这一阶段，信 息安全的主要技术包括密码学技术、访问控制、容忍入侵、防火墙和入侵检测 技术等。随着各种网络的互连和信息系统的广泛建立，信息安全已扩展到了很 大的范围。然而，到目前为止，信息安全的理论和技术还不是很完善，许多方 面有待突破。 由上文所提到的信息安全的发展历程可知，不论是在过去还是将来，密码 学技术扮演着非常重要的角色。现如今，密码学的发展已进入到计算机阶段， 其研究也涉及到数学的各个分支，同时，密码学分析也越来越依赖数学方面的 知识，例如，代数、概率论、数论、组合学和信息论等。除此之外，密码学的 研究还涉及到其它学科的知识，例如，计算机科学、量子力学、语言学、系统 工程等。如今，由于大量计算机网络通信和商业应用的需要，人们对数据保护、 数据传输安全性、防止工业间谍等问题日益重视密码学已大规模地扩展到 民用。 1 2 研究目的和意义 如今，随着社会的快速发展，计算机技术已被应用到越来越多的行业。如 果说，在过去十年里，个人计算机的快速普及是计算机工业的主旋律，那么， l 第一章绪论 在接下来的十年里，迅速发展的互联网正在把世界连成一个整体，信息高速公 路的建设将会是新的主题，信息流通的速度也大大提高了，使得社会生活的步 伐也越来越快。 广大的国际互联网用户，在感叹计算机和网络技术给工作和社会生活带来 巨大而深远的影响的同时，应该也注意到了，在国际互联网积极影响的背后， 也还存在很多阴暗面。以电子邮件为例，登陆电子邮箱所使有的密码被黑客盗 用的可能性就非常大，同时，电子邮件的伪造现象也非常普遍。然而，网络的 安全问题还远远不只存在于电子邮件系统，诸如：文件传输，网络新闻等，同 样存在类似的问题。激烈的市场竞争使得大部分商家都把公司的商业资料作为 机密信息，其资料是绝对不能向第三者透露的，其原因是，一份资料的泄露极 有可能造成一笔生意的告吹，甚至给公司带来毁灭性的灾难。在外交计算机系 统、军事计算机系统和国防计算机系统中，信息的机密性尤为重要，对一个国 家的安全或外交政策有极大的影响。 毫不夸张地讲，在缺乏信息保护的情形下，用户在网络上传输和存储的信 息都有可能被泄漏和篡改。因此，目前，在许多国际互联网上都使用了密码学 技术，例如网络软件加密狗，防火墙( f i r e w a l l ) ，等等，这样一来，这一在过去 应用范围很有限，仅被军事和间谍人员所使用的技术得以迅猛发展。 随着i n t e r a c t 的广泛应用，人们对信息安全性的需要变得越来越迫切，然而 信息安全技术仍然很落后。信息安全技术的核心是安全性算法，且安全性算法 的软件实施已经成为网络性能提高的系统瓶颈，标准化的商品c p u 和d s p 也无 法达到安全性算法性能要求，分组密码只能做到每秒几兆比特左右加密速度， 即使采用高速r i s cc p u 芯片，其加密速度也仅每秒几十兆比特左右，要作进一 步的提高非常困难。要满足上百兆到千兆加解密速率，必须找到更好的解决方 法。 近几年，由于计算机仿真、计算机游戏等实时需求向图形处理器提出了越 来越高的要求，庞大市场对g p u 以及相关软硬件的发展产生了强大动力，g p u 已得到了进一步的高速发展。同时，g p u 通过单指令多数据指令类型来支持数 据并行计算，提供惊人的计算能力。现代的o p u 在通用计算加速方面有如下优 势： ( 1 ) 强大的并行处理能力：主要体现在指令级、数据能和任务级三个层次； ( 2 ) 高效率的数据传输能力：主要体现在g p u 与显存之间的带宽为1 6 g b s 2 第一章绪论 和系统内存到显存的带宽为4 g b s 两方面。 这就为g p u 用于安全算法的计算提供丰富的功能和强大的能力。同时， c u d a 编程模型非常适合公开g p u 的并行功能。新一代的n v i d i ag p u 基于 t e s l a 架构，支持c u d a 编程模型，可显著加速c u d a 应用程序。因此，通过 对g p u 编程发挥其高强度计算能力来解决信息安全的速度瓶颈，提高算法的执 行效率，将是一个十分有应用价值的研究。 目前，国内外学者围绕加密算法g p u 高速实现做了大量的探索性研究，他 们的工作为后人的研究和应用提供了许多新思路，开拓了新的研究领域。 综上所述，本课题具有十分重要的理论和实际意义。 1 3 国内外研究现状 近年来，学术界开始探索用g p u 加速加密算法的技术。例如，很多学者研 究a e s 在g p u 上实现的可能性【。m o s s 和f l e i s s n e r ，他们致力于模幂运算在 g p u 上的有效实现【5 j 1 6 】，但是他们的结果并不让人乐观，主要是由于传统g p u 结构和接口的限制。 2 0 0 5 年，c o o k 等人 t l ，他们在n v i d i ag e f o r c e 3t i 2 0 0 上实现了a e s ，由 于t 1 2 0 0 只有有限的可编程性，所以他们的实现只能使用o p e n g l 库和固定功能 图形管线。他们使用可配置的颜色映射去完成字节转换，使用管线的最后输出 阶段( 光栅操作单元r o p ) 来实现x o r 操作。然而不幸的是，由于所使用硬件 的限制，必须在管线的最后阶段实现所有的x o r 操作，每个数据块需要多个管 线通道。他们最后展示了一个成功的全面的实现，其速率在1 8 4 k b p s 到1 5 3 m b p s 之间。 2 0 0 7 年，h a r r i s o n 等人【2 j 提出在g p u 上实现分组加密，他们使用当时最新 的能兼容新一代图形处理器( n d i a7 9 0 0 g t ) 的d x 9 来实现a e s 。该处理器 支持更多的可编程性，但只支持浮点数的操作。他们提出三种不同的方法，用 于克服在管线的可编程部分因缺乏整数位操作所带来的不足。a e s 中的与轮密 钥加的操作是通过4 位查找表和8 位x o r 来实现的。 同年，y a n g 等人t 7 j 着重于d e s 和a e s 的b i t s l i c i n g 实现，他们使用支持整 数数据和位运算的新一代的硬件- - a m dh d2 9 0 0x tg p u ，并利用其大寄存器 的优点，从而使性能大为提高。该实现使用4 路3 2 位处理器并行处理4 列3 2 位 3 第一章绪论 a e s s t a t e ，最终获得了1 8 5 g b p s 的速度。但b i t s l i c e d 实现并不适合一般用途， 因为它需要为输入块进行大量的预处理。 其它的非通用处理器也被用于实现加密算法，包括a s i c ( a p p l i c a t i o n s p e c i f i ci n t e g r a t e dc i r c u i t 特定用途集成电路) 设计8 - 1 0 j , of p g a 设计1 1 彤】。 c o s t i g a n 和s c o t t 1 6 1 提出7mp l a y s t a t i o n 的3i b mc e l l 处理器实现r s a 的方法。 1 4 论文的主要工作和组织结构 本文对信息安全算法的g p u 高速实现的理论，研究目的以及意义做了细致 的分析，介绍了一些已有的加密算法的g p u 实现方法。在掌握了c u d a 技术的 基础上研究了加密算法在新一代图形处理器上的处理，并最后给出了一些常用 加密算法在g p u 上的实现情况。 本文的章节具体安排如下： 第一章绪论。主要介绍本课题的研究目的以及意义，研究现状，并对本 论文的主要工作以及组织结构作了说明。 第二章典型的密码学算法。主要介绍了密码学的概念及其基本原理。并 对对称密钥加密算法中的d e s ，a e s ，r c 4 ，r c 5 ，非对称密钥加密中的r s a 和安全l l a s h 算法的算法原理作了详细的说明。 第三章g p u 编程模型。介绍了g p u 的发展、最新进展及其流式编程模型。 最后对g p u 和c p u 进行了简单的比较。 第四章c u d a 介绍。详细介绍了c u d a 编程模型和存储器模型。 第五章算法在g p u 上的实现。本文的核心部分。在前述的理论基础上， 提出了五种加密算法在g p u 上实现方法，并给出了相应的实现结果。 第六章总结与展望。对全文进行总结，并提出进一步需要开展的工作。 4 第二章典型的密码学算法 第二章典型的密码学算法 2 1 概述 密码学( c r y p t o l o g y ) 是研究密码系统或通信安全的一门学科，主要包括两 个分支，即密码编码学( c r y p t o g r a p h y ) 和密码分析学( c r y p t a n a l y s i s ) ： 密码 编码学的主要目的是寻求保证消息保密性或认证性的方法；密码分析学的主要 目的是研究加密消息的破译或消息的伪造。 加密就是这样一个过程将明文数据和信息转换为不可辨识形式，即密 文，使得该数据和信息不被不应了解的人知道和识别。而解密过程就是，已知 密文的内容，将其转变成为明文。如图2 1 所示： 不安全 网 i 一 图2 1 加解密示意图 2 2 典型的数据加密算法 加密算法的一般类型有对称密钥加密算法和非对称密钥加密算法两种【1 9 1 。 对称密钥加密算法使用相同的密钥来加密和解密数据。在此算法中，加密 和解密双方所用的密钥都要秘密地保存，不能让第三方知道，否者，他们所使 用的加密算法就失效了。由于对称密钥加密算法计算速度非常快，它被广泛应 用于大量数据的加密过程中，如文件的加密。 非对称密钥加密算法，它要用到两个密钥，分别用于对数据的加密和解密 的公开密钥和私有密钥，即，如果对数据进行加密时使用公开密钥，则只有用 与其相对应的私有密钥才能才能解密密文：如果对数据进行加密时使用私有密 钥，则只有用与其相对应的公开密钥才能解密密文。 5 第二章典型的密码学算法 2 2 1d e s d e s ( 数据加密标准1 2 0 1 ) 诞生于1 9 7 7 年，是密码学界的里程碑，是第一个 作为国际标准的加密算法，它的诞生，使得密码学发生了革命性的变化。在d e s 加密算法诞生之前，密码算法的安全性仅仅取决于对算法的保密。国际上的加 密算法种类非常多，而且这些算法大部分都是置换型的算法，它们都是以单表 多表为基础，一旦密码表被破获，算法就没有任何的安全性可言，就必须更换 新的算法。因此，在这些加密算法中，没有一个被作为标准的。d e s 算法诞生 之后，密码算法的安全性不再仅仅依赖于其本身，而是依赖于密钥，这就使得， 每个算法都可以公开地接受人们的检验，以验证其安全性，而且，万一密钥被 泄漏，仅需要更换密钥就可以了，而无需重新设计算法，仍可以继续维持其安 全性。因此d e s 作为密码算法的经典算法，作为密码算法的里程碑是当之无愧 的。d e s 加密算法的加密流程如图2 2 所示： 图2 2d e s 的加密流程图 6 第二二章典型的密码学算法 d e s 加密算法采用的是6 4 位的分组、6 4 位的密钥( 实际只有5 6 位，除去8 个字节中每字节的奇偶校验位) 。经过初始置换后，明文分成左右各3 2 位数据， 右路数据经过核心函数f 变换后，与左路3 2 位数据进行异或，如此迭代，最后 生成密文，总共经过1 6 轮变换。其f 函数结构如图2 3 所示： 困 图2 3f 函数 其中子密钥生成过程如图2 4 所示： 图2 4 子密钥生成 图2 5 解释了s 盒在f 中的作用。置换函数由8 个s 盒组成，每个s 盒都由6 位输入，产生4 位输出。盒s i 输入的第一位和最后一位组成一个2 位的- n 数， 用来选择s 盒4 行中的一行，中间4 位用来选择1 6 列中的某一列。行列交叉处的 十进制值转换为二进制之后可得到输出的4 位二进制表示。s 盒的每行都定义了 一个普通的可逆置换。8 个s 盒的3 2 位输出经过置换，使得每个s 盒的输出在下 一轮中尽可能地影响更多其他位。 7 第二章典型的密码学算法 3 2 位 图2 5s 盒在f 中的工作原理 2 2 2a e s 2 0 0 0 年，a e s ( 高级数据加密标准) 【2 1 】诞生，它是一种全新的分组密码加 密算法，是由比利时人j o a nd a e m e n 和v i n c e t nr i j m e n 提出的，它在强度和速度 上都高于三重d e s 。目前，a e s 加密算法已成为新一代的数据加密标准。a e s 加密算法的加密流程如图2 6 所示： 卜文节怿做母i 旧 j r j 计算轮密钥 l 用户密钥 重复n r 次 用户密钥 图2 6a e s 加密流程图 从图2 6 中可以看出，a e s 的结构与d e s 的完全不同，其可逆性并不来自于 它的结构，它所使用的大部分概念是有限域里的多项式乘法，并将其推演为可 逆矩阵的乘积，因此，a e s 加密算法是可逆的。 8 第二章典型的密码学算法 a e s 加密算法的分组长度和密钥长度都是可变的【翻，可以是1 2 8 位、1 9 2 位、 2 5 6 位，用户可以选择自己所需要的分组长度和密钥长度。其相关参数如表2 1 。 本文所使用的a e s 的密钥长度是1 2 8 位，这也是使用最广泛的实现方式。 表2 1a e s 的参数 密钥长度( w o r d s b y t e s b i t s ) 4 1 6 1 2 86 2 4 19 28 3 2 2 5 6 明文分组长度( w o r d s b y t e s b i t s ) 4 1 6 1 2 84 1 6 1 2 84 1 6 1 2 8 轮数 l o 1 2 1 4 每轮的密钥长度( w o r d s b y t e s b i t s ) 4 1 6 1 2 84 1 6 1 2 84 1 6 1 2 8 扩展密钥长度( w o r d s b y t e s ) 4 4 1 7 65 2 2 0 86 0 2 4 0 输入分组是用以字节为单位的正方形矩阵描述，该分组被复制到s t a t e 数组， 这个数组在加密或解密的每个阶段都会被改变。在执行了最后的阶段后，s t a t e 被复制到输出矩阵中。同样，1 2 8 位密钥也是用以字节为单位的矩阵描述的。然 后这个密钥被扩展到一个以字为单位的密钥序列数组中。每个字由4 个字节组 成，1 2 8 位的密钥最终扩展为4 4 字的序列。在矩阵中，字节排列顺序是从上到下 从左到右排列的( 见图2 7 ) 。 i n o i mi n si n l 2 s o , os o ，i s o , 2s o , 3 h a li n 5i n 9i n l 3 s 1 os t ，i8 1 , 2s i ，3 i n 2i n 6 i n l o i n t 4 s 2 0s 2 1s 2 a s 2 3 i n 3 i m i n l ll n l 5s 3 0s 3 1s 3 2s 3 3 s o , os o , ls o ，2s o , 3 s l , os i ，1s l ，2 s i 3 s 2 0s 2 is 2 - 2s 2 3 s 3 0s 3 is 3 1 2s 3 3 o u t o o u t ,o u t so u t l 2 o u t to u t 5o u t 9o u t l 3 o u t 2 o u t 6o u t l o o u t l 4 o u t 3 o u t 7o u t t lo u t l 5 ( a ) 输入、s t a t e 数组和输出 k k k sk 1 2 k l k 5k 9 k 1 3 k 2k 6 k l o k 1 4 k 3b k l l k 1 5 口i 王田 ( b ) 密钥和扩展密钥 图2 7a e s 的数据结构 9 第二章典型的密码学算法 字节代换变换是一个简单的查表操作。a e s 定义了一个s 盒一个由 1 6 1 6 个字节组成的矩阵，包含了8 位值所能表达的2 5 6 种可能的变换。s t a t e 中每个字节按照如下的方式映射为一个新的字节：把该字节的高4 位作为行值， 低4 位作为列值，然后取出s 盒中对应行列的元素作为输出。 行移位变换就是把s t a t e 的第一行保持不变，第二行循环左移一个字节，第 三行循环左移两个字节，第四行循环左移三个字节。行移位变换就是将某个字 节从一列移到另一列中，其线性距离是4 字节的倍数，且确保了某列中的四字 节被扩展到了4 个不同的列。 二 列混淆变换对每列独立地进行操作，每列中的每个字节被映射为一个新值， 此值由该列中的四个字节通过函数变换得到，如图2 8 ： s o ，2 s a s i , 2 s l s 2 , 2 s 2 8 3 , 2 s 3 一 图2 8 列混淆变换 在轮密钥加变换中，1 2 8 位的s t a t e 按位与1 2 8 位的密钥x o r 。 2 2 3r c 4 首先介绍流密码的整体结构，然后讲r c 4 算法原理。 一个典型的流密码每次加密一个字节的明文，当然流密码也可被设计为每 次操作一个比特或者大于一个字节的单元【1 7 1 。图2 9 给出了一个典型的流密码的 结构图。在该结构中，密钥输入到一个伪随机数发生器，该伪随机发生器产生 一串随机的8 比特数。简单地说，一个伪随机流就是在不知道输入密钥的情况 下不可预知的流。发生器的输出称为密钥流，通过与同一时刻一个字节的明文 流进行异或操作产生密文流。 1 0 、iiilfj 。够够珏 ss，ss ，蛇啦啦s s，s，s，s 蚍u 甜鲥 叩埔 加 秘 ，。，l 一 仉 l 幺 冀 s s s s o o o o 仉 二 刍 支 一s s s s ，。l 、iilllij l 3 2 o 0 o 0 1 c j 2 1 o 0 o 0 ，) 2 l l o 0 0 o 2 1 1 1 ，、 i 。0 0 o 一 -，。i。ii、 第二章典型的密码学算法 图2 9 流密码结构图 r c 4 是r o nr i v e s t 为r s a 公司在1 9 8 7 年设计的一种流密码【l 鳓，是一种可变 密钥长度、面向字节操作的流密码。该算法以随机置换为基础，分析显示该密码 每输出一字节的结果仅需要8 到1 6 条机器操作指令。r c 4 算法非常简单，易于描 述：用从1 到2 5 6 个字节的可变长度密钥初始化一个2 5 6 个字节的状态矢量s ，s 的元素记为s o ，s 1 ，s 2 5 5 ，从始至终置换后的s 包含从0 到2 5 5 的所有8 比特数。对于加密和解密，字节k 由s 中2 5 5 个元素按一定方式选出一 个元素而生成。每生成一个k 的值，s 中的元素就被重新置换一次。 初始化s ： f o ri = 0t o2 5 5d o s t i 2 i ； t 【i 】= k 【im o dk e y l e n ； ( 其中t 为临时矢量) 然后用t 产生s 的初始置换： j = 0 ； f o ri = 0t o2 5 5d o j - - t j + s i + t 【i 】) m o d2 5 6 ； s w a p ( s i ，s d 】) ；) 因为对s 的操作仅是交换，所以s 仍然包含所有值为0 到2 5 5 的元素。 密钥流的生成：i j = o ； w h i l e ( t r u e ) i i + 1 ) m o d 2 5 6 ； 第二章典型的密码学算法 j = ( j + s 【i 】) m o d 256；：moo j 2 u 十s 【l j ) ； s w a p ( s i ，s d 】) ； t - - - ( s i + s i j ) r o o d2 5 6 ； k - - s 【t 】； 加密中，将k 的值与下一明文字节异或。 2 2 4r c 5 s 2 i + l e 丑 是模2 加法 图2 1 0r c 5 加密流程图 1 9 9 4 年，r i v e s t 提出了r c 5 加密算法，它是一个新的分组密码，与前面几种算 法有所不同，它的分组长度、密钥长度和迭代轮数都是可变的，这使得用户可以 根据自己的需要进行选择，可以在加密速度和加密强度上进行选择n 7 1 。r c 5 力 密 算法引入了数据相倚旋转算法，它是一种新的密码基本变换，其含义是，对于两 组数据，其中一组数据循环左移另一组数据的低l o 矿位，其中，x 是分组长度。r c 5 加密算法的加密流程如图2 1 0 所示，图中s 表示密钥。 r c 5 力i 密算法的安全性来自于其复杂的s 表，以及数据相倚旋转算法。有所 不同的是，r c 5 加密算法的s 表用于密钥的生成【l 卅。 1 2 第二章典型的密码学算法 2 2 5r s a r s a 公钥密码体制于1 9 7 8 年瞄】，由美国麻省理工学院r i v e s t ，s h a m 柳 a d l e m a n 一= 人提出的，至今为止仍被公认为是公钥密码体制中最优秀的加密算 法，被认为是密码学发展史上的第二个里程碑。r s a 是一种特殊的可逆模指数运 算的加密体制，其理论基础是数论中的一条重要论断：求两个大素数之积是容 易的，而将一个具有大素数因子的合数进行分解却是非常困难的，因此，它的 安全性依赖于大数的分解。 r s a 算法除了用于加密之外，还能用于数字签名和身份认证。 r s a j i 密算法的具体加密过程描述如下： ( 1 ) 选取两个比较大的素数p 和q ，其值保密； ( 2 ) 计算n = p * q ，其中，n 被称作模，然后计算e u l e r 函数( n ) ，( 妒心1 ) ( q - 1 ) ， ( n ) 保密； ( 3 ) 选取正整数e ，1 锄( n ) ，使其满足g c d ( e ，( 1 1 ) 产1 ，e 是用户的公开密钥； ( 4 ) 计算满足d e - 1 ( m o d ( o ( n ) 条件的d 值，d 就是保密的用户私密密钥； ( 5 ) 加密公式为：g - - - m 。m o dn ； ( 6 ) 解密公式为：m = c dm o d l l 。 其中解密与加密互为逆变换。 2 2 6s h a 1 安全h a s h 算法( s h a ) 由n i s t 所设计。1 9 9 3 年，s h a 作为联邦信息处理 标准发布，1 9 9 5 年发布了它的修订版，通常称之为s h a 1 。s h a 算法建立在 m d 4 算法之上，其基本框架与m d 4 类似。 s h a 1 算法输入的消息长度小于2 “位，输出的消息摘要为1 6 0 位，输入的 消息是以5 1 2 位的分组为单位进行处理的。s h a 1 算法实现的具体步骤描述如 下： 步骤l ：添加填充位。在消息的最后添加适当的填充位( 一个l 和若干个o ) 使得数据位的长度满足：长度= 4 4 8 r o o d 5 1 2 。 步骤2 ：填充长度。在消息后附加“位( 包含填充前消息的长度) ，将其看 做6 4 位的无符号整数。 步骤3 ：初始化消息摘要缓冲区。个1 6 0 位的消息摘要缓冲区用以保存中 间和最终结果。 1 3 第二章典型的密码学算法 步骤4 ：以5 1 2 位数据块为单位处理消息。算法的核心是具有四轮运算的模 块，每轮执行2 0 步迭代，其处理过程如图2 1 l ，共计8 0 步。 步骤5 ：输出1 6 0 位的消息摘要。 图2 1 1s h a d 算法处理5 1 2 位分组的过程 s h a - i 压缩函数见图2 1 2 ： 1 4 第二章典型的密码学算法 w t k 图2 1 2s h a 的基本操作( 单步) a ，b ，c ，d ，e 卜( b + f ( t ，b ，c ，d ) + s 5 ( a ) + w t + k t ) ，a ，s 3 0 ( b ) ，c ， d 其中： a ，b ，c ，d ，e= 缓冲区的5 个字 t= 步骤编号，0 5 t _ 7 9 f ( t ，b ，c ，d )= 第t 步使用的基本逻辑函数 s k= 3 2 位的变量循环左移k 位 w t= 从当前5 1 2 位输入分组导出的3 2 位字 k = 加法常量。 q - = 模2 3 2 加法 2 3 本章小节 本章介绍了密码学的概念和原理，并重点讲解了d e s 、a e s 、r c 4 、r c 5 、 r s a 和s h a 1 的原理和实现步骤，为本文最后的实验打下基础。 1 5 第二三章g p u 编程模型 第三章g p u 编程模型 3 1g p u 的发展历程 计算机图形处理器，发展极其迅速，从1 9 9 3 年以来，每代产品的持续时间 只何六个月左右，而性能以大约3 倍处理器的摩尔法则速度增长【“i 。现在每隔 半年左右。新一代的g p u 便会诞生井带来很多优异的性能和很多图形开发的 a p i 。多流水线结构、向量处理特性以及3 2 位i e e e 标准浮点精度的实现使得 g p u 对于计算密集型的科学应用有非常大的吸引力，越来越成为通用计算的 个有效的井行平台。 如令，g p u 已发展成为一种高度并行化、多线程、多核的处理器，具有杰 出的计算能力和极高的存储器带宽，如图3 1 2 5 1 所示； 1 g t 瑚 一啪 m 一“ 盛。 i、十 i m u i ”一w ”鼍。一。：嚣 。翟事= o ：二竺。 j h hh l i i z ， 气”删 1 。7 一；# ”兰垒= 兰：三二 斟3 1 近几年c p u 和g p u 的每杪浮点运算次数和存储器带宽 1 6 第三章g p u 编程模型 具体地说，g p u 专用于解决可表示为数据并行计算的问题在许多数据 元素上并行执行同一程序，具极高的计算密度( 数学运算与存储器运算的比率) 。 由于所有数据元素都执行相同的程序，因此对精密流控制的要求不高，再加上 程序在许多数据元素上运行，且具有较高的计算密度，因而可通过计算隐藏存 储器访问延迟，而不必使用较大的数据缓存。 3 1 1g p u 的发展史 在过去的几年里，g p u 迅速发展【2 6 j ：2 0 0 4 年，n v i d i a 发布了g e f o r c e 6 8 0 0 u l t r a ，该产品被人们认为具有划时代的意义，其c i n e f x3 0 引擎使得n v i d i a 快速走出了f x 系列的阴影。大量改进后的c i n e f x3 0 可完全支持微软d i r e c t x 9 0 中的p i x e ls h a d e r3 0 和v e r t e xs h a d e r3 0 ，这是它最有改进价值的地方。不 仅如此，c i n e f x3 0 还采用了1 2 8 位浮点精度h d r ( h i g hd y n a m i cr a n g e ) 技术， 这就使得动态范围3 d 场景的画面质量得到大幅度的提升，而且，游戏的视觉效 果和渲染精度的水平都得到相当大的提高。2 0 0 6 年，微软发布了d i r e c t x1 0 后， a t i 和n v i d i a 公司就陆续开始了发布支持d i r e c t x1 0 的显卡的工作。一年之后， n v i d i a 就推出了g e f o r c e8 8 0 0g t x ，该产品是新一代图形加速卡，它基于全 新的图形核心g 8 0 ，采用了全新的技术特性和物理架构，且完全基于微软的 d i r e c t x1 0 。 在不断发展的同时，g p u 的可编程性能得到了很大的提高，成为计算机中 新的计算资源。g p u 技术的发展与进步主要体现在以下四方面【2 8 】：( 1 ) 扩展了 产品的功能，反映了g p u 技术的突破与创新；( 2 ) 大大增加了晶体管的数量， 反映了芯片的处理能力和复杂程度；( 3 ) 改进了总线标准，体现了芯片性能的发 挥受c p u 和g p u 之间的传输速度的制约；( 4 ) 改进了接口和渲染模型，从应用 角度与开发者角度反映了技术的进步。 综合以上各个方面，可以将g p u 技术的发展历程按照年代顺序整理为表 3 1 。纵览此发展历程，可以将其划分为三个时代 2 7 2 9 1 ： ( 1 ) 1 9 9 5 年- 2 0 0 0 年，固定功能架构时代：每个硬件单元形成一条处理流水 线，固定了每个流水级功能，且硬化了一些给定的函数，g p u 卸去了c p u 的计 算负担，加速了绘制，对图形学意义重大。 ( 2 ) 2 0 0 1 年2 0 0 5 年，分离着色器架构时代：g p u 用可编程的项点着色器替 换了t & l ，用可编程的像素着色器替代了混合与纹理采样等固定单元。顶点着 1 7 第三章g p u 编程模型 色器和像素着色器是实现图形特效最密集的部分，呈现出流处理器的特剧3 0 ， 使用着色器大大加强了图形处理的灵活性与表现力。这两个着色器在物理上是 两部分硬件，不可相互通用。 ( 3 ) 2 0 0 6 年至今，统一着色器架构时代：g p u 第一次提出了几何着色的概念， 通过调用统一的着色硬件来运行项点、像素、几何程序，它在体系结构上呈现 出并行机的特征，不再是流水线的形式。进一步完善了对指令、数据精度、纹 理等各方面的支持，对整数，单双精度浮点数的支持，遗憾的是，它仍不支持 递归程序。在这一阶段，g p u 厂商们推出了专门做通用计算的g p u ，从a p i 和 硬件上提供对g p g p u 的专门支持【3 1 1 1 3 2 1 。g p u 的操作对象从以图形为主发展为 图形和高性能计算并重。 表3 1g p u 的发展历程 显像管 渲染 年份主要进展代表产品总线 a p i 数量级模型 is g i i r i s 1 9 8 0 1 9 9 0 图形工作站系统 g e o m e t r y 1 mi r i s g l e n g i n e g p u ，硬件 3 d f xv o o d o o , 1 9 9 5 1 9 9 8n v i d i at n t 2 ，l o m p c i ，o p e n g l l 2 ， 光栅化 a g p 2 xd i r e c t x l - 6 a t i r a g e n v i d i a 硬件几何 g e f o r c e 2 , a t io p e n g l l 2 ， 1 9 9 9 2 0 0 02 5 ma g p 4 x 处理 r a d e o n 7 0 0 0 s 3 d i r e c t x7 s a v a g e3 d g e f o r c e3 4 ， o p e n g l i 3 ， 1 02 0 0 1 可编程顶点程序 6 0 m r a d e o n8 0 0 0 d i r e c t x8 g e f o r c ef x ， o p e n g l l 5 ， 2 02 0 0 2 2 0 0 3可编程像素程序1 0 0 ma g p 8 x r a d c o n9 0 0 0 d i