（计算机应用技术专业论文）通用加解密算法在嵌入式系统中的研究与实现.pdf

摘要 摘要 随着无线通信技术的和计算机技术的发展，移动电子商务，无线上网等应用 已成为时代焦点，各种安全技术已逐步从有线领域向无线领域迈进，全方位满足 人们对安全通信的需求。作为信息安全技术的核心，通用加密算法扮演着极为重 要的角色。目前针对嵌入式设备开发的通用加密算法库产品般都是由国外公司 研发，国内在这一领域的研究较少，因此深入研究通用加密算法在嵌入式系统中 的实现与应用并研制出自己的嵌入式通用加密算法库具有极其重要的意义。 d e l t a c r y p t o 是北京科银京成技术有限公司开发的嵌入式通用加密算法库。 d e l t a c r y t o 具备良好的可移植性能很容易地移植到不同的嵌入式操作系统中并 根据所在系统的特性提供本地优化实现并满足速度与尺寸的要求。 d e l t a c r y p t o 提供全套的通用加密算法，其中包括r s a 公开密钥算法，对称 加密算法，单向散列算法，b a s e 6 4 编解码算法以及p k c s # 1 2 加密算法。此外为 满足未来技术的发展嵌入式通用加密算法库提供了支持硬件加密设备的功能。 本文详细阐述了嵌入式通用加密算法库的体系结构设计与实现，并对r s a 算 法优化实现技术进行了细致的研究。在理论研究的基础上根据嵌入式系统的特 点，提出了适合嵌入式设备的通用加密算法优化实现技术，实现了各加密算法的 高速运行。 该项目已经成功产品化，并应用于波导的某款手机中。该产品具有接口清晰， 易移植，代码紧凑，运行高效等特点，是一个面向嵌入式安全领域的稳定的，实 用的通用加密算法产品。 关键词：嵌入式通用加密算法库，嵌入式系统，优化技术，蒙哥马利算法 r s a 算法 a b s t r a c t a b s t r a c t w i t ht h ed e v e l o p m e n to fr e l a t e dt e c h n o l o g yi nw i r e l e s st e l e c o m m u n i c a t i o na n d c o m p u t e rf i e l d s ，m o b i l ee - b u s i n e s sa n ds u r f i n g t h en e tw i r e l e s s l yh a v eb e e nt h ef o c u s o ft h ee r a ，w h i c hm a k ek i n d so f s e c u r i t yt e c h n o l o g yu s e di nw i r ef i l e db e f o r ea p p l i e d t ow i r e l e s sf i l e di no r d e rt os a r i s f yt h er e q u i r e m e n to fs e c u r ec o m m u n i c a t i o n a st h ec o r eo fi n f o r m a t i o ns e c u r i t y , c r y p t o g r a p h ya l g o r i t h m sp l a ya ni m p o r t a n t r o l ei n s e c u r i t y f i e l d s a tp r e s e n t ，t h e r ei sal i t t l ed o m e s t i cr e s e a r c hw o r ka b o u t e m b e d d e d c r y p t o g r a p h yp r o d u c t s f o r e i g nc o m p a n i e s h a v ea l m o s t o c c u p i e d t h ew h o l e m a r k e t s oi ti su r g e n tf o ru st od e e p l yr e s e a r c hi n t ot h eo p t i m i z a t i o na n da p p l i c a t i o n o fc r y p t o g r a p h ya l g o r i t h m si ne m b e d d e ds y s t e m sa n dp r o d u c eo u ro w ne m b e d d e d c r y p t o g r a p h yp r o d u c t s d e l t a c r y p t o i sa ne m b e d d e d c r y p t o g r a p h yp r o d u c tp r o d u c e db y c o r t e k c o r p o r a t i o n d e l t a c r y p t o c a nb e e a s i l yp o r t e d t od i f f e r e n te m b e d d e d o p e r a t i n g s y s t e m sa n di t sf e a t u r e si n c l u d et h ea b i l i t yt oo p t i m i z ec o d ef o rd i f f e r e n tp r o c e s s o r s a n df o rs p e c i f i cs p e e da n ds i z er e q u i r e m e n t s d e l t a c r y p t oo f f e r saf u l l s e to fc r y p t o g r a p h i ca l g o r i t h m s ，i n c l u d i n gp u b l i ck e y o p e r a t i o n s w h i c hm a i n l yf o c u so nr s a a l g o r i t h m ，s y m m e t r i c ，b l o c ka n ds t r e a m e l p h e r s ，o n e w a ym e s s a g ed i g e s t s ，b a s e 6 4 ，s y m m e t r i cc i p h e r sd e f i n e db yp k c s # 1 2 b e s i d et h a td e l t a c r y p t oa l s op r o v i d ea l li n t e r f a c et o s u p p o r th a r d w a r ee n c r y p t i o n d e v i c e s ，w h i c hm a y b ew i d e l yu s e di ne m b e d d e dd e v i c e si nt h en e f l rf u t u r e t h i sd i s s e r t a t i o n d e t a i l e d l y i l l u m i n a t e st h ea r c h i t e c t u r eo f d e l t a c r y p t o a n d t e c h n o l o g yo fo p t i m i z i n gd i f f e r e n ta l g o r i t h m sf o re m b e d d e ds y s t e m sw h i c hm a i n l y f o c u so nr s a p u b l i ck e yo p e r a t i o n s o nt h eb a s i so f t h e o r e t i c sr e s e a r c ho f o p t i m i z i n g t e c h n o l o g yo fc r y p t o g r a p h ya l g o r i t h m sa n dc h a r a c t e r i s t i c so fe m b e d d e ds y s t e m ，w e p r o p o s e do p t i m i z a t i o nt e c h n o l o g yo fc r y p t o g r a p h i ca l g o r i t h m ss u i t a b l ef o re m b e d d e d s y s t e m sa n d r e a l i z e d h i 曲s p e e dc r y p t o g r a p h i co p e r a t i o n s d e l t a c r y p t oh a s b e e n s u c c e s s f u l l y u s e di nam o b i l e p h o n e o fb i r d ，a n d c h a r a c t e r i z e da sf l e x i b l e i n t e r f a c e ，e a s y t o t r a n s p l a n t ，s m a l l c o d e s i z e ，e f f e c t i v e i m p l e m e n t a t i o n k e y w o r d s ：e m b e d d e d c r y p t o g r a p h i ca l g o r i t h ml i b r a r y , e m b e d d e d s y s t e m ， o p t i m i z a t i o nt e c h n o l o g y , m o n t g o m e r ya l g o r i t h m ，r s a a l g o r i t h m i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：燮日期：毒沪4 年上月j 4 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：燮导师签名：妄碰 日期：c j 妒印年，1 月一j ，日 电子科技大学硕士学位论文：通用加解密算法在嵌入式系统中的研究与实现 1 , 1 通用加密算法简介 第一章引言 当今社会是一个信息化的社会，大量的机密数据正通过开放的互联网络相互 传送，在这种环境下数字通信很容易受到干扰，窃听，如何保障信息的安全成为 了人们日益关注的问题。通用加密算法就是为保障信息的机密性，完整性，可鉴 别性，不可抵赖性而提出的信息处理技术，它共分为三类，公开密钥算法，对称 加密算法，以及单向散列算法。 公开密钥算法拥有两个密钥，分别被称为公开密钥以及私有密钥。公开密钥 是公开的，任何人都能得到它并用它来加密数据，而私有密钥是保密的，只能被 某个特定的人掌握。用公开密钥加密的数据能用私钥解密，反之亦然。该类算法 的设计要求是在合理的假定时间内无法通过其中的一个密钥推导出另一个，这充 分地保障了私钥的私密性。 对称加密算法通常只有一个密钥，它的安全性完全取决于加密密钥的安全 性，安全强度取决于密钥的长度，因而使用对称加密算法进行安全通信时，通信 双方必须秘密地协商好密钥。在通常的应用中往往对称加密算法和公开密钥算法 配合使用，也就是说，通信的一方使用公开密钥算法的公钥加密对称加密算法的 密钥，通信的另一方用私钥解密出对称加密算法的密钥，之后的通信采用对称加 密算法加密数据。之所以这样做是因为公开密钥算法计算速度慢，内存消耗大， 而对称加密算法执行速度快，消耗内存小。 单向散列算法就是作用于任意长度的消息返回一个固定长度散列值的算法。 它具备三点特性。第一，给定消息很容易计算出散列值。第二，给定散列值很难 计算出消息。第三，给定某个消息，很难找到另一个消息使其与给定消息的散列 值相同。 上述三类算法的各自特性以及用途如表1 1 表1 1 髑蕊德圈黼一 矗一一一霉嘲 髓隔疆l 焉赋糊隔鼹嬲髓豳麟 公开密钥算法执行速度慢，消耗内存大保障数据机密性，完整性，可 鉴别性，不可抵赖性 对称密钥算法执行速度快，消耗内存小保障数据机密性 单向散列算法执行速度快，消耗内存小 保障数据完整性 第一章引言 1 2 通用加密算法与嵌入式设备 随着移动通信技术以及计算机技术的发展，嵌入式设备在消费领域的应用越 来越广泛，诸如手机和p d a 等这类高速发展的嵌入式设备正在改变个人电脑的 定义：今天的“个人电脑”，意味着“计算+ 沟通十娱乐”。在这股浪潮的推动下， 嵌入式设备中的软件变得日益复杂，功能日益强大，现在在这些功能中最抢眼的 有无线上网，移动电子商务和基于j a v a 、b r e w 的游戏类业务等。这些功能的 实现或未来的发展无不依赖于通用加密算法的应用。 w a p 作为移动终端中实现移动电子商务以及无线上网功能的关键技术，安 全性是它考虑的重要因素。目前w a p 常用版本有两个，一个是1 2 版，另一个 是2 0 版。w a p l 2 的安全协议采用的是w t l s 。w t l s 协议定义了三层安全级 别，即c l a s s l ，c l a s s 2 和c l a s s 3 。c l a s s l 使用对称加密算法和单向散列算法实现了 数据的私密性与完整性。c l a s s 2 在c l a s s l 的基础上新增服务器验证，通过对服 务器证书的验证实现了鉴别功能。c l a s s 3 在c l a s s 2 的基础上新增客户端验证，通 过对客户端证书的验证增强了鉴别功能。由于w t l s 协议与有线网络中的s s l 协议存在不兼容，需要网关进行协议转换，因而无法保障端到端的安全性。于是 在w a p 2 0 中，安全协议新增了s s l t l s 协议，实现了与有线网络的无缝连接， 保障了端到端的安全性。此外为最大限度的保障网络的安全性，以及通信过程中 用到的一些敏感数据，w a p 2 0 还提出了w i m ( w i r e l e s si d e n t i t ym o d u l e ) 的概 念，它使用存储在w i m 中的签名私钥向应用层提供数据签名功能，并在硬件级 实现了各类加密算法和证书验证操作。 移动终端的j a v a 应用方面s u n 公司于2 0 0 2 年在t e l e c o ma s i a2 0 0 2 发布了 m i d p 2 0 ( m o b i l ei n f o r m a t i o nd e v i c ep r o f i l e ) 版。m i d p 2 0 和m i d p i 0 相比， 它大大加强了对用户界面、多媒体和游戏功能、网络连接功能的支持，同时将 o t a 应用程序下载包含到规范中来， ( e n d t o e n d ) 的安全机制。在通信方面， 另外还为无线信息设备提供了端到端 m i d p 2 0 增加了对h 兀p s 、报文、s o c k e t 通信以及串口通信的支持。所有这些与安全相关的技术都大量使用了通用加密算 法。 1 3 阻碍通用加密算法在嵌入式设备中应用的原因 通用加密算法尤其是公开密钥算法在执行过程中具有运算量大，内存占用多 的特点。目前通用计算机已经具备了极高的运算速度和较大的内存，因此在通用 计算机上运行通用加密算法能获得比较理想的计算速度。然而嵌入式设备，特别 2 电子科技大学硕士学位论文：通用加解密算法在嵌入式系统中的研究与实现 是移动通信类设备，一般只具备相当有限的计算能力，存储能力和供电能力，在 嵌入式设备中实现通用加密算法显然具有相当的难度。过去开发人员不得不在加 密强度以及加密速度之间选择其一。这些情况都大大制约了通用加密算法在嵌入 式设备上的应用。 国际上对通用加密算法在嵌入式设备中优化实现的研究工作在前几年已经 开始，国内在这方面的研究工作则并不多。对通用加密算法在嵌入式设备中优化 实现以及应用研究工作将具有强大的生命力和实用价值。 1 4 课题综述 本课题来源于北京科银京成技术有限公司内部项目d e l t a s s l ，主要研究通 用加密算法( 包括：m d 2 ，m d 5 ，s h a l ，r c 4 ，d e s ，r s a 等) 在通用嵌入式设备中的 优化实现。同时为了便于上层软件开发人员方便使用这些算法，在具体加密算法 的基础上增设了一个算法统一封装层，向编程者提供统一的编程接口并隐藏算法 内部实现细节。最终将算法封装层与具体算法整合为一个算法库，提供一套完整 的针对通用嵌入式平台的通用加密算法综合解决方案。 本课题从立项到正式投入商业应用历时六个月。本人作为通用加密算法库的 设计人员严格遵循软件开发流程，独立完成了从概要设计，详细设计，编码，调 试以及移植的全部过程。 本课题的主要工作有： 1 深入研究了当前通用加密算法，特别是公开密钥加密算法的优化实现技 术。 2 分析o p e n s s l 源代码，根据嵌入式设备的特点实现通用加密算法在嵌入 式设备中的优化实现。 3 分析设计通用加密算法封装接口。 4 分析设计了第三方算法注册以及硬件加密设备支持模块。 5 设计并实现通用加密算法模块，达到可靠性高，功能强大，可剪裁，移 植性好，体积小，执行效率高等目标，使之达到国内领先水平。 6 移植通用加密算法库到多种目标平台( x 8 6 a r m 7 a r m 9 ) 和多种操作 系统( w i n d o w s l i n u x d e l t a o s ) 下。 7 完成通用加密算法库的单元测试，集成测试，系统测试以及性能测试。 3 第一章引言 1 5 章节安排 第一章介绍了本课题的背景。 第二章介绍密码学基本概念。 第三章介绍通用加密算法的优化实现技术。 第四章嵌入式通用加密算法库的概述。 第五章详细阐述通用加密算法库的设计与实现。 第六章详细说明嵌入式通用加密算法库优化实现。 第七章介绍嵌入式通用加密算法库的移植与测试。 第八章对本文进行的总结。 最后是致谢和参考文献。 4 电子科技大学硕士学位论文：通用加解密算法在嵌入式系统中的研究与实现 第二章背景知识概述 在本章中，我们将简要介绍与通用加密算法相关的密码学理论基础。首先， 介绍对称加密算法( 传统密码算法) 和公开密钥算法( 非对称密码算法) ，然后 介绍单向散列算法，最后，介绍伪随机数发生器以及p k c s # 1 2 相关内容。 2 1 信息安全技术 2 1 1 对称加密算法 对称加密算法( s y m m e t r i ca l g o r i t h m ) 有时又称为传统密码算法，就是加密 密钥能从解密密钥中推算出来的算法。在大多数对称加密算法中，加密密钥和解 密密钥是相同的，并且算法的安全性完全依赖于密钥，泄露密钥就意味着任何人 都能对消息进行加解密。只要通信需要保密，密钥就必须保密，其j j n 解密过程 可分别表示为e k ( m ) = c ，d k ( c ) = m ，其中m 代表明文，c 代表密文，e k ( ) 代表 加密操作，d k o 代表解密操作，并且对称加密算法具有如下特性：d k ( e k ( m ) ) = m ， e k ( d k ( m ) ) = m 。 对称加密算法根据它的工作方式可分为流密码算法和分组密码算法两类。流 密码算法一次只处理输入数据中的一位。分组密码算法一次则处理输入数据中的 一个分组。 对称加密算法的优点是： 运算效率高( 加解密速度通常能达到十兆，秒或更多) ，算法简单，系统开销 小，适合加密大量数据。 缺点是： 1 算法的安全性取决于密钥的安全性，因此使用对称加密算法进行安全通 信前必须以安全的方式进行密钥交换。这一步，在某些情况下是可行的， 但在某些情况下会非常困难，甚至无法实现。 2 密钥管理困难。假设在一个有n 个用户的网络中，每两个用户问都使用 对称加密算法进行安全通信，则每两个用户间就必需协商一个加密密钥， 对每个用户而言他必须管理n 一1 个密钥，整个系统共存在n + ( n 1 ) 2 个密钥。这给整个系统的密钥管理提出了巨大的挑战。 目前常用的对称加密算法有r c 4 ，r c 5 ，d e s ，i d e a 等。 5 第二章背景知识概述 2 1 1 1 流密码算法 流密码算法将明文逐位转换成密文。该算法工作流程如图2 1 所示。密钥流 发生器输出一系列比特流( k l ，k 2 ，k 3 k j ) 。这些密钥流跟明文比特流 ( p l ，p 2 ，p 3 ，p i ) 进行异或运算产生密文比特流。 其中，在加密端c i = p i o k i 。 在解密端，密文流与完全相同的密钥流异或运算恢复出明文流。 p ；= c i0 k i 由于满足条件p i o k 1o k i = p ，所以该方式是正确的。 p p 图2 1 流密码算法工作流程 2 1 1 2 分组密码算法 分组密码算法即将明文划分为若干固定长度的分组，然后对每个分组进行加 密的算法。根据分组密码的工作方式可将分组密码划分为电子密码本模式 e c b ( e l e c t r o n i cc o d e b o o km o d e ) ，密码分组链接模式c b c ( c i p h e r b l o c k c h a i n i n g ) ，密 码反馈模式c f b ( c i p h e rf e e d b a c k ) 以及输出反馈模式o f b ( o u t p u tf e e d b a c k ) 四大 类。 电子密码本模式e c b ( e l e c t r o n i cc o d e b o o km o d e ) ：e c b 模式是直接应用密码 算法的工作模式。给定明文的一个比特串x = x 1 x 2 ，x i 是b 比特分组。对每一 个x ，使用加密算法，产生密文分组c i ，记为c i = e k ( ) ( i ) ，其中e k 是加密操作。按 次序将c i 连接起来得到完整的密文c ，即c = c l c 2 c j 。 密码分组链接模式c b c ( c i p h e r b l o c kc h a i n i n g ) ：给定明文的一个比特串x = x 1 x 2 ，x i 是b 比特分组。将第一个分组x 1 与一个b 比特的初始化向量( i n i t i a l v e c t o r , i v ) 作异或运算，对所得的结果应用加密算法，得到第一个密文分组c 。 以后的明文分组x i 与前一个密文分组c i - 1 先作异或运算，对结果再使用加密算 法。上面的描述可以表示为：c l = e k i 审i v ) ，c 2 = e k ( x 2o c 。) ，c i _ e k ( x io c ，一。) 。 6 电子科技大学硕士学位论文：通用加解密算法在嵌入式系统中的研究与实现 _ _ _ _ _ _ _ _ _ _ _ _ 一一 密码反馈模式c f b ( c i p h e rf e e d b a c k ) ：该模式利用以前产生的密文作为密码 算法的输入，产生伪随机输出。输出的结果再与明文异或得到密文。有关步骤可 描述如下：算法作用于一个初始化向量1 v ，产生输出z l ；接着将x 1 和z 1 作异或 运算产生第一个密文分组c l 。以后的密文分组c 。是对前一个密文分组使用加密 算法，将输出和对应的明文x i 作异或运算得到。上面的描述可以表示为z i = e k ( r e ) ， c 1 = x l o z 1 ，z 2 ：e k ( c i ) ，c 2 = x 2 o z 2 ，z i = e k ( c i j ) ，c i 2 x f o z i 。 输出反馈模式o f b ( o u t p u t f e e d b a c k ) ：该模式与c f b 相似，只是它不对密文 进行链接而是对初始向量加密来产生z i ，即z 1 = e k ( ) ，c l = x 1 o z 1 ，z i = e k ( z i 一1 ) ，c i = x io z i ，。 上述四种模式间的比较见表2 2 ，其中“+ ”号表示优点，“一”号表示缺点。 表2 2 分组密码模式间的比较 灏阐暴礴翻嘲豳嚣睡嗣疆醺晶总啊圉圉睡 安全性： 安全性： “一”不能隐藏明文模式 “+ ”通过跟前一个密文分组相异或 “一”分组密码的输入并不一定是随 隐藏明文模式 机的 “+ ”与前一个密文分组异或后分组 “+ ”同一个密钥可以加密多个消息 密码的输入是随机的 “一”明文很容易被篡改，分组可被 “+ ”同一个密钥可以加密多个消息 删除，再现或互换 “+ 一”篡改明文稍有点难度；分组可 效率： 以被从消息头和尾处删除，第一块分组 “+ ”速度跟分组密码一样 的数据可被更换 效率： “+ ”处理过程并行进行 “+ ”速度同分组密码一样 “一”由于填充，密文比明文长 “一”由于填充，密文比明文长 “一”不能进行预处理 “一”不能进行预处理 容错性： “一”一个密文错误会影响整个明文 “+ 一”加密不是并行的，解密是并 行的且有随机存取特性 分组 容错性： “一”同步错误不可恢复 “一”一个密文错误会影响整个明文 分组以及下一个分组的相应位 “一”同步错误不可恢复 7 第二章背景知识概述 国鬻黼圈强呵蕊醐尉瞄辫懑醑黼鞠戳聪霸鲼髑臻麓嘲嗣疆醺晶总鞠黧潮翻潮隧 安全性：安全性： “+ ”可以隐藏明文模式“+ ”可以隐藏明文模式 “+ ”密文分组的输入是随机的“+ ”密文分组的输入是随机的 “+ ”用不同的，同一个密钥可以“+ ”用不同的，同一密钥可以加 加密多个消息密多个消息 “+ 一” 对明文的篡改稍难：分组可“一”明文很容易被控制篡改，任何 以被从消息头和尾处删除，第一块分组对密文的改变都会直接影响明文 的数据可被更换 效率： 效率： “+ ”速度同分组密码一样 “+ ”速度同分组密码相同 “一”密文与明文同大小，不计算 “一”密文与明文同大小，不计算 “+ ”消息出现前作些预处理是可能 “+ 一”加密不是并行的，解密是并的 行的且有随机存取特性，在分组出现之 “+ 一”o f b 处理过程不是并行的， 前作些预处理是可能的，前面的密文分 计数器处理是并行的 组可以被加密 容错性： 容错性： “+ ”一个密文错误仅影响明文的对 “一”一个密文错误会影响明文的相 应位 应位及下一个分组 “一”同步错误不可恢复 “+ ”同步错误是可恢复的。 2 1 2 公开密钥算法 1 9 7 6 年w h i t f i e l dd i f f i e 和m a r t i ne h e l l m a n 首先提出了这种密码体制，它 的出现在很大程度上解决了密钥管理问题，使得大规模的安全通信得以实现。 2 1 2 1 公开密钥算法基本原理 公开密钥算法采用两个不同的密钥：公钥和私钥。其中公钥对外公开，可供 任何人查阅，使用。私钥只能被所有者拥有，对它必须严格保密。用公钥加密 的数据只能用相应的私钥解密，反之亦然。但从公钥或密文分析出私钥或明文， 在计算上则是极其困难的。 目前全球有多种实用的公开密钥算法，其中比较著名的有：r s a 算法， d i f f e h e l l m a n 算法，d s a 算法以及椭圆曲线算法，它们的安全性基于以下三种 8 电子科技大学硕士学位论文：通用加解密算法在嵌入式系统中的研究与实现 复杂的数学难题中的一种： 1 大整数因子分解系统( 代表性算法是r s a ) 。 2 有限域( 数学中的种代数结构) 离散对数系统( 代表性算法是d s a ) 。 3 有限域椭圆曲线离散对数系统( 代表算法是e c c 算法) 2 1 2 2 r s a 算法 1 9 7 8 年，m i t 的三位学者r o n a l dl r i v e s t ，a d is h a m i r 和l e o n a r dm a d l e m a n 利用数论中大整数分解的困难性，创造了r s a 算法，构造了双密钥体制。它即 可用于加密，又可用于数字签名，是被研究得最广泛，应用得最广泛的公钥算法， 目前仍然是安全的。国际标准化组织如i s o ，i t u 等均已接受r s a 体制作为标准。 r s a 算法的描述如下： 1 独立地选取两个大素数p 和q ，计算乘积n = p t q 。 2 计算欧拉函数的值：巾( n ) = ( p - 1 ) ( q - 1 ) 。 3 随机选取一个整数e ，且1 e 巾( n ) ，并使e 和巾( n ) 互素。 4 计算解密密钥d ：d = e 。1 m o d 由( n ) 。 取( e ，n ) 为公开密钥，( d ，n ) 为私有密钥。这时p 和q 不再需要，为了保密应 该将其销毁，或者被严格保密。 r s a 的加( 解) 密公式为： 加密：c = m e ( m o dn ) ；( 其中c 为密文，m 为明文) 解密：m = c o ( r o o d n 1 p k c s # 1 规范了r s a 的公钥以及私钥形式，公钥依然为( e ，n ) 而私钥有两 种形式，第一种是( d ，n ) ，第二种是( p ，q ，d p ，d q ，q l n v ) 其中d p = e - t m o d ( p 1 ) ，d q e - i m o d ( q - 1 ) ，q l n v = q m o dp 。私钥的第二种表示形式是为了加快私钥3 n 解密运 算运用中国剩余定理分解第一种表示形式的来的嘲。 2 1 3 单向散列算法 散列算法( 又称杂凑算法) 是对不定长的输入产生定长输出的一种特殊算 法，它的函数表示形式是：h = h ( m ) 其中m 是变长的消息，h = h ( m ) 是定长 的散列值( 或称为消息摘要) 。 2 1 3 1 单向散列算法的性质 散列算法的目的是为文件、消息或其它数据产生“指纹”。要用于消息认证， 散列算法h 必须具有如下性质： 9 第二章背景知识概述 1 h 能用于任何大小的数据分组，产生定长的输出。 2 对于任何给定的x ，h ( x ) 要相对易于计算。 3 对任何给定的散列值h ，寻找x 使得h = h 在计算上不可行( 单向性) 。 4 对任何给定的分组x ，寻找不等于x 的y ，使得h ( x ) = h ( y ) 在计算上不 可行( 弱抗冲突) 。 5 寻找任何的( x ，y ) ，使得h ( x ) = h ( y ) 在计算上不可行( 强抗冲突) 。 前两个性质使得散列算法用于消息认证成为可能。第2 和第3 两个性质保证 散列算法的单向性：给定消息产生散列值很简单，反过来由散列值产生消息计算 上不可行，这保证了攻击者无法通过散列值恢复消息。第4 个性质保证了攻击者 无法在不修改散列值的情况下替换消息而不被察觉。第5 个性质比第4 个性质更 强，保证了一种被称为生日攻击的方法无法奏效。 满足上述性质的散列算法被称为单向散列算法。 2 1 3 2 数字签名 数字签名主要完成对信息来源的鉴别，保证信息的完整和不可否认的功能。 数字签名的原理是将要传送的明文通过单向散列( h a s h l 算法计算出对应的 消息摘要，将消息摘要加密后与明文一起传送给接受方，接受方将接受到的明文 产生新的消息摘要与发送方的发来消息摘要解密比较，比较结果一致表示明文未 被改动，如果不一致表示明文己被篡改。 数字签名技术利用了非对称加密算法的特性，用户用自己的私钥对要发送的 数据加密作为数字签名，然后把明文和签名一起发送。接收者收到后，用发送者 的公钥对签名数据解密，再和明文对比，如果相同，说明数据没有被修改，否则 说明数据在传输过程中被篡改了。同时，通过数字签名，可以确定数据的来源， 并可以防止发送者否认发送过数据，这样就实现了身份认证和防抵赖的功能。 由于非对称加密算法运算量比对称加密算法大得多，因此对所有数据进行私 钥加密作为签名效率很低。在实际应用中采用的方式是：首先对数据使用单向散 列算法进行处理，计算出消息对应的消息摘要，再对消息摘要进行私钥加密作为 数字签名，这样做大大提高了运算速度。接收者收到数据和签名后，用同样的算 法算出数据的消息摘要，并用发送者的公钥对签名解密，最后把解密结果和上一 步得到的消息摘要比较，就可以对签名进行校验。 2 1 4 随机数发生器 随机数在现代密码学中起着越来越重要的作用，它被广泛应用于加密算法的 密钥生成以及安全协议中。它的随机性直接影响到加密算法以及安全协议的安全 1 0 电子科技大学硕士学位论文：通用加解密算法在嵌入式系统中的研究与实现 性。 2 1 4 1 随机数 随机数是指一个序列，它包含的数字是相互独立的，它们具有一定的分布而 且在给定取值范围内出现的可能性也是一定的。根据这个定义可阻知道，一个理 想的随机数发生器可以产生一个均匀分布的、非确定的、独立的具有无限长度的 数据流，即没有规律性和周期性。 随机数在实际应用中使用的是随机数所组成的序列，即随机序列。根据其产 生的方式，随机序列可以分为两类： 1 伪随机序列 伪随机序列由数学公式计算产生。实质上，伪随机数并不随机，序列本身也 必然会重复，但由于它可以通过不同的设计产生满足不同要求的序列并且该序列 可以复现( 相同的初始种子将产生相同的序列) ，因而得到广泛的应用。只要由伪 随机数发生器所产生的伪随机序列的周期足够长并能通过一系列检验，就可以在 一定的范围内将它当作真随机序列来使用。 2 真随机序列 真随机序列是不可预测的，因而也不可能出现周期性重复的真随机序列。它 只能由随机的物理过程所产生，如电路的热噪声、宇宙噪声、放射性衰变等。 2 1 4 2 衡量随机序列质量的主要指标 1 周期性 伪随机序列是由具有周期性的数学公式计算产生，其本身也必然会表现出周 期性，即序列中的一段予序列与另一段子序列相同。它的周期必须足够长，才能 为应用提供足够多的可用数据。只有真随机序列才能提供真正的、永不重复的随 机序列。 2 相关性 随机数发生器所产生的一个随机序列中的各个随机数应该不相关，所产生的 各个随机序列中的随机数也应该不相关。真随机序列满足这种不相关性。对于伪 随机数发生器，应该仔细地设计所用的数学公式，以尽量满足不相关的要求。 3 分布的均匀性 包括蒙特卡罗( m o n t e c a r l o ) 计算在内的大多数应用都要求所采用的随机序 列服从均匀分布，即同一范围内的任一个数出现的概率相同。从均匀分布的随机 序列也很容易导出其它类型分布的随机序列。 第二章背景知识概述 2 1 4 3 随机数发生器 随机数发生器可以用硬件方法实现，也可以用软件方法实现。 软件方法实现的随机数发生器产生的随机序列一般服从均匀分布。然而，这 个序列的产生决定于采用的算法和初始种子。由于存在这个特性，软件实现的随 机数发生器通常被称为伪随机数发生器( p s e u d or a n d o mn u m b e rg e n e r a t o r1 。当 然这种软件算法也可以用硬件实现，叫做“硬件随机数发生器”。这种随机数发 生器还是属于伪随机数发生器，因为它需要初始种子并且产生确定性的数字序 列。 硬件方法实现真随机数发生器主要依赖于物理元件的随机特征，例如弧光 灯、原子核的射线衰变、电阻或者二极管的噪声。真随机数发生器不像伪随机数 发生器那样需要设定初始种子。 2 2p k c s 弹1 2 中的加密际准 公钥密码标准p k c s ( p u b l i ck e yc r y p t o g r a p h ys t a n d a r d s ) 是美国r s a 数据安 全公司为公钥密码学提供的一个工业标准接口。p k c s 包含一系列标准，其中 p k c s # 1 2 是个人信息交换语法( p e r s o n a li n f o r m a t i o ne x c h a n g es y n t a x ) ，该标准 定义了一个个人信息交换的语法标准，用来在互联网上传输或存放各种个人信 息，其中最重要的应用是存放个人证书，以及个人证书对应的私钥。私钥信息存 放格式详细定义在p k c s # 8 ( p r i v a t e k e y i n f o r m a t i o ns y n t a xs t a n d a r d ) 9 。 p k c s # 1 2 规定了一套个人信息的存储格式，其基本单元称为为p d u ( p r o t o c o ld a t a u n i t ) ，最顶层p d u 称为p f x 它呈现出一种分层的格式，每层都 有相应的格式定义。 p k c s # 1 2 定义了四种私有模式与完整模式的组合。私有模式使用加密算法 保护个人信息不被窃取。完整模式保护个人信息不被篡改。私有模式分为如下两 类： 1 公钥私有模式( p u b l i c k e yp r i v a c ym o d e ) ：在个人信息的颁发端颁发者 使用接受者的加密公钥加密个人信息。接收者通过对应的私钥就能解密出个人信 息。 2 密码私有模式( p a s s w o r d p r i v a c ym o d e ) ：在个人信息的颁发端颁发者使 用从用户名以及一个私有口令中导出的密钥利用对称加密算法加密个人信息。 完整模式分为如下两类： 1 公钥完整性模式( p u b l i c k e yi n t e g r i t ym o d e ) ：该模式的完整性通过使用 个人信息的颁发端颁发者的私有密钥对整个p f xp d u 进行签名保障。签名可以 1 2 电子科技大学硕士学位论文：通用加解密算法在嵌入式系统中的研究与实现 通过对应的公钥验证。 2 密码完整性模式( p a s s w o r di n t e 酣t ym o d e ) ：该模式的完整性通过从秘密 的完整口令中导出的消息验证码( m e s s a g e a u t h e n t i c a t i o n c o d e ) 保障。 p k c s # 1 2 规定密码私有模式和密码完整性模式中的密钥使用p k c s # 5 中规 定的盐，迭代次数，口令以及p k c s # 1 2 规定的密码生成函数生成。通常情况下， 盐，迭代次数包含在p k c s # 1 2 的p d u 中，在解析p d u 时就能获取。密码通常 是在解析p k c s # 1 2p f x 时由用户输入。 一般情况下存放在p k c s # 1 2 的p d u 中的个人证书，私钥信息都是使用密码 模式进行了加密保护的，因此在解析过程中必须先进行解密，然后再处理。 2 3 b a s e 6 4 数据编码 b a s e 6 4 是网络上最常用的用于传输8 位字节代码的编码方式之一。b a s e 6 4 将每三个8 位的字节转换为四个6 位的字节，然后在6 位字节的高两位添0 ，组 成四个8 位字节。从上面的描述可以看出经b a s e 6 4 编码后的数据在理论上比原 来的长三分之一。 在安全领域很多安全解决方案都采用了b a s e 6 4 ，比如p e m ( p r i v a c y e n h a n c e dm a i l ) ，p g g s m i m e 等，以p e m 应用最早，最广，以至通常将b a s e 6 4 编码的格式称为p e m 格式。b a s e 6 4 在安全领域的另一个用途是编码p k i 体系 架构中的数字证书，这在证书解析时经常用到。 2 4 本章小结 随着数字信息技术的迅猛发展，网络上的信息安全问题日益突出，而密码学 则是解决信息安全问题的最根本方法。本章从概念的角度介绍了各种通用加密算 法，伪随机数发生器，p k c s # 1 2 规范以及b a s e 6 4 数据编码技术。 1 3 第三章通用加密算法的优化实现技术 第三章通用加密算法的优化实现技术 3 1 公开密钥加密算法的优化实现技术 公开密钥算法是通用加密算法中最耗时的算法。公开密钥加密算法的优化实 现技术的目标就是优化公开密钥的实现，减少计算时对系统资源的消耗，提高它 的运行速度。由于本课题中公开密钥算法仅限于r s a 算法，并且限于在通用嵌 入式设备中实现，所以研究的重点是如何在通用的嵌入式c p u 上( 例如a r m 7 ) 上最有效地运行r s a 算法。 r s a 算法的核心的运算是模幂运算( m o d u l a re x p o n e n t i a t i o n ) ，它会被转化为 基本的模乘运算，最终变成大数运算，因此，在本章我们将分三部分详细介绍 r s a 优化实现技术。 3 1 1 大数的结构 大数是公开密钥算法的基础，本节我们将详细说明大数的结构。假设w 是 一个大数，则它以b 为基数的表示形式如下： w 2 一1 b ”1 + 既一2 b ”2 + + 6 + = ( 一l 呒- 2 w o ) 6 ，0 彬b 一1 。 例如整数1 1 7 可以表示为如下形式： 1 1 7 = ( 1 1 1 0 1 0 1 ) 2 或1 1