（计算机科学与技术专业论文）嵌入式ecc算法性能改进及系统容错技术的研究与实现.pdf

， 一事 静 ， 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名： 关于论文使用授权的说明 r 期：，d 多f 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：衅导师签名：缸 摘要 摘要 互联网技术的蓬勃发展使得信息安全领域面临重大的挑战。个人信息泄漏， 恶意木马篡改，密钥的丢失等成为严重的网络安全隐患。人们在探索研究一种更 为可靠的安全机制的道路上付出了巨大的艰辛。传统的数据加密，信息认证，数 字签名等安全机制越来越不能胜任当前复杂多变的网络环境。 本课题所研究的内容基于一种先进的信息安全解决方案，即采用嵌入式设备 对信息进行加密解密处理，同时负责密钥的管理；采用目前公认的安全性最高的 椭圆曲线密码体制( e l l i p t i cc u r v ec r y p t o g r a p h y , e c c ) 加密算法对数据进行保密 处理。这样的系统可以最大限度地将数据的加密、解密过程与p c 相隔离，同时 保护了密钥，防止恶意木马的攻击和信息的泄漏，也杜绝了数据信息在传输过程 中被攻击者截获并破解的可能。 但是这样的系统会存在着两个不可回避的问题，一是e c c 算法复杂度过高， 性能不佳，尤其很难与低端的嵌入式设备相兼容；二是由于嵌入式系统自身的可 靠性缺陷所带来的数据传输以及数据存储过程中的容错问题。本论文主要围绕着 嵌入式加密系统中存在的这两个关键问题开展研究和讨论。 本文首先分析了e c c 算法的瓶颈，找到影响e c c 算法性能的关键因素，并 结合本嵌入式系统所使用的e c c 算法提出了从大数模幂和大数模乘两级改善整 体算法性能的方案。这个算法改进方案属于e c c 算法素域运算层的改进方案， 经过测试，算法性能改进明显。 接下来本文讨论了嵌入式系统在数据传输以及数据存储过程中的容错问题， 具体结合本课题所研究的系统，分析了系统容错的需求。同时提出了一种基于本 原b c h 码的n a n df l a s h 的容错方案，并提出了b c h 容错系统的软件实现方法， 通过演示程序给出了系统的测试结果。 嵌入式系统e c c 算法性能改进方案以及系统容错方案的提出对于应用于低 端嵌入式设备中的e c c 算法的性能改进以及一些资源稀缺、可靠性一般的相关 嵌入式加密系统、嵌入式n a n df l a s h 存储设备的开发具有实际意义。 关键词e c c ；大数模幂；b r 算法；容错；b c h i l a b s t r a c t a b s tr a c t t h er a p i dd e v e l o p m e n to fi n t e m e tt e c h n o l o g yh a sm a d ei n f o r m a t i o ns e c u r i t yi s f a c i n gm a j o rc h a l l e n g e s p e r s o n a li n f o r m a t i o nl e a k a g e ，m a l i c i o u st r o j a nt a m p e r i n g a n dl o s so fs e c r e tk e yh a v eb e c o m es e r i o u ss e c u r i t yr i s ko fn e t w o r k s p e o p l ep a ya g r e a th a r d s h i pt or e s e a r c ham o r er e l i a b l es e c u r i t ym e c h a n i s m t r a d i t i o n a ld a t a e n c r y p t i o n ，m e s s a g ea u t h e n t i c a t i o n ，d i g i t a ls i l a g ea n do t h e rs e c u r i t ym e c h a n i s m s b e c o m ei n c r e a s i n g l yi n c a p a b l ea b o u tc u r r e n tc o m p l e xn e t w o r ke n v i r o n m e n t t h es t u d yc o n t e n to fm ys u b je c ti sb a s e do na na d v a n c e di n f o r m a t i o ns e c u r i t y s o l u t i o n t h a ti su s i n ge m b e d d e dd e v i c ef o re n c r y p t i o na n dd e c r y p t i o no fi n f o r m a t i o n p r o c e s s i n g ，a l s or e s p o n s i b l ef o rs e c r e tk e ym a n a g e m e n t ，u s i n gt h ec u r r e n t l ya c c e p t e d t h eh i g h e s ts a f e t ye l l i p t i cc u r v ec r y p t o g r a p h ye c ce n c r y p t i o na l g o r i t h mo nd a t a c o n f i d e n t i a l s u c has y s t e mc a nm a x i m i z et oi s o l a t et h ep r o c e s so fe n c r y p t i o na n d d e c r y p t i o nt op c ，w h i l ep r o t e c tt h es e c r e tk e y a n dp r e v e n tt h em a l i c i o u st r o j a nh o r s e a t t a c ka n di n f o r m a t i o nl e a k a g e ，b u ta l s op u ta ne n dt ot h ep o s s i b i l i t yo ft h ed a t ac o u l d b ei n t e r c e p t e da n dd e c i p h e r e db yt h ea t t a c k e rd u r i n gt r a n s m i s s i o n h o w e v e rt h e r ea r et w ou n a v o i d a b l ep r o b l e m si nt h i ss y s t e m o n ei st h eh i g h c o m p l e x i t ya n dp o o rp e r f o r m a n c ee x i s t i n g i ne c ca l g o r i t h m ，s oa st oi ti sn o t c o m p a t i b l ew i t hl o w - e n de m b e d d e dd e v i c ea n dt h eo t h e ri st h en e e do ff a u l t t o l e r a n t f o re m b e d d e ds y s t e mi n t h ed a t at r a n s m i s s i o np r o c e s sa n dd a t as t o r ep r o c e s ss i n c et h e r e l i a b i l i t yo ft h ee m b e d d e ds y s t e mi t s e l f s ot h i sp a p e rg i v e sd i s c u s s i o na n da n a l y s i s a r o u n dt h et w oi s s u e s f i r s t l yt h i sp a p e ra n a l y z e st h eb o t t l e n e c kt h a ti m p a c te c ca l g o r i t h mp e r f o r m a n c e ， a n dp r o v i d e san e wm e t h o d ，t h a tm o d i f yt h em o d u l ee x p o n e n t i a t i o ns u b a l g o r i t h ma n d m o d u l em u l t i p l i c a t i o ns u b a l g o r i t h mt os p e e du pw h o l ea l g o r i t h mc o m p u t a t i o n a c c o r d i n gt h er e a le c ca l g o r i t h mu s e di nt h i ss y s t e m t h i sa l g o r i t h mi m p r o v e m e n t p r o g r a mb e l o n g st op r i m ef i e l do p e r a t i o nl e v e lo fe c ca l g o r i t h m ，a n dt h eo b v i o u s i m p r o v e m e n tw a ss h o w nb yt e s tr e s u l t s s e c o n d l yt h i sp a p e rd i s c u s s e sf a u l t t o l e r a n tt e c h n o l o g y i nt h ep r o c e s so fd a t a t r a n s m i s s i o na n dd a t as t o r e ，a n dc o m b i n e dw i t ht h es y s t e ms t u d i e di nt h i si s s u e ， a n a l y s i sf a u l t t o l e r a n c er e q u i r e m e n to ft h i se m b e d d e ds y s t e m a tt h es a m et i m e ，t h i s p a p e rp r o p o s e s p r i m i t i v eb c hc o d eb a s e df a u l t t o l e r a n tp r o g r a m ，p r o p o s e st h e s p e c i f i cm e t h o do fh o w t op r o g r a mt or e a l i z et h es y s t e ma n dg i v e sad e m op r o c e d u r e u i 北京t 业人学下学硕l ：学位论史 e c ca l g o r i t h mp e r f o r m a n c ei m p r o v e m e n tp r o g r a mo fe m b e d d e ds y s t e ma n d s y s t e mf a u l t t o l e r a n tp r o g r a ma r em e a n i n g f u lt ot h ei m p r o v e m e n to fe c ca l g o r i t h m t h a ti su s e di ne m b e d d e dd e v i c ea n dt h ed e v e l o p m e n to fe m b e d d e de n c r y p t i o ns y s t e m a n de m b e d d e dn a n df l a s hs t o r a g ed e v i c ew i t i ls c a r c er e s o u r c e sa n dl o wr e l i a b i l i t y k e yw o r d se c c ，m o d u l ee x p o n e n t i a t i o n ，b ra l g o r i t h m ，f a u l t - t o l e r a n t ，b c h i v 目录 摘要i a b s t r a c t i i i 第1 章绪论1 1 1 课题研究的背景及意义。l 1 1 1 课题研究背景1 1 1 2 课题研究的意义l 1 2 本论文的内容安排3 1 2 1 主要研究内容3 1 2 2 研究的重点难点3 1 2 3 论文的结构安排4 第2 章嵌入式密码器系统的介绍5 2 1 系统整体结构5 2 2 嵌入式设备的硬件组成6 2 3 系统存在的问题8 2 4 本章小结9 第3 章e c c 算法基本原理1 l 3 1 实数域上的椭圆曲线1 1 3 2z d 上的椭圆曲线1 2 3 3e c c 算法的实现1 3 3 4 本章小结1 5 第4 章e o c 算法性能的分析及瓶颈的研究1 7 4 1e c c 算法性能的分析1 7 4 2e c c 算法瓶颈的研究1 7 4 3 本章小结2 0 第5 章e c c 算法性能的改进2 1 5 1 传统的大数模幂算法b r 算法2 l 5 2 改进的b r 算法2 2 5 32 。进制k 值的选取2 3 5 4 大数平方算法的改进2 5 5 5 算法性能测试2 7 5 6 进一步的改进策略2 9 5 7 本章小结3 0 第6 章嵌入式加密系统的容错方案3 3 6 1 系统的容错需求3 3 6 2u s b 协议中的容错机制3 4 6 3n a n df l a s h 的容错机制3 6 6 4 可行的容错方案3 7 6 4 1 容错方案的分析3 7 6 4 2 一种基于本原b c h 循环码的n a n df l a s h 容错机制3 8 v 北京丁业人学丁学硕卜学位论文 6 5 本章小结4 0 第7 章b c h 码的基本理论4 1 7 1 差错控制码4 l 7 2 循环码4 2 7 2 1 循环码的定义及其性质4 2 7 2 2 循环码的编码方法4 3 7 2 3 循环码的译码方法4 4 7 3b c h 码的基本理论4 4 7 3 1 有限域的概念4 5 7 3 2 构造g f ( 2 m ) 4 5 7 3 3 有限域g f ( 2 m ) 中元素的三种表示方法4 6 7 3 4 最小多项式4 7 7 3 5b c h 码的定义4 7 7 3 6 求b c h 码的生成多项式4 7 7 4b c h 码的编码译码方法4 8 7 4 1b c h 码的编码方法4 8 7 4 2b c h 码的译码方法4 8 7 5 本章小结4 9 第8 章基于本原b o h 码的容错机制的实现5l 8 1b c h 编译码器的软件实现5 1 8 1 1 公用部分软件的实现5 1 8 1 2b c h 编码过程5 2 8 1 3b c h 码的译码及纠错过程5 3 8 2b c h 编译码系统演示5 5 8 3 嵌入式系统容错机制的实现5 7 8 4 本章小结5 9 j ； i 论6 1 参考文献6 3 攻读硕士学位期间取得的研究成果6 7 致谢。6 9 v i 第l 帝绪论 皇鼍鼍皇詈! 曼曼鼍曼! 暑篡量皇皇i l l 一1 iii - -皇l 寰曼曼篁皇曼曼曼! 毫皇曼量鼍鼍! 曼皇曼毫篁皇篁皇鲁孽 第1 章绪论 1 1 课题研究的背景及意义 1 1 1 课题研究背景 随着互联网技术的蓬勃发展，网络环境成为人们信息共享，信息交流的理想 空间。但随之而来，也产生了许多令人棘手的信息安全问题。 目前信息安全领域方面的一种先进的安全保密机制就是采用嵌入式设备对 文件进行加密处理，对通信中的密钥进行管理，以隔绝使用p c 机处理所带来的 信息泄露和信息破坏等问题。常用的安全加密体制包括对称加密体制( d e s ，a e s 等) 和非对称的公钥密码体制( r s a ，椭圆曲线算法等) 。随着密码学技术的不 断发展，对称加密体制的安全性逐渐遭到人们的质疑。目前使用先进的技术，仅 需5 6 小时便可以成功破解d e s 。同时对称密码体制存在的先天不足还在于密钥 的管理非常困难。因此可以预见，公钥密码体制将最终在信息安全领域中发挥更 为重要作用。而在公钥密码体制中，椭圆曲线密码体制( e l l i p t i cc u r v e c r y p t o g r a p h y , e c c ) 加密算法比经典的公钥密码体制算法r s a 和d l 有更小的 参数，而对于更高的安全级别，参数大小的差异更加明显，因此更加倍受青睐l j j 。 因而可以得出这样的结论，将嵌入式设备与安全性最高的椭圆曲线算法相结合是 解决目前信息安全问题的一个十分可行的方案。 但是椭圆曲线算法的瓶颈在于密钥长度过大( 相对于对称密码体制的加密算 法而言) ，加密解密速度较慢，系统开销大。这与运算速度较慢，资源相对稀缺 的嵌入式系统是很难相容的。因此基于嵌入式系统对椭圆曲线算法性能进行改进 很有必要，也具有实际的研究价值。 同时，由于应用嵌入式系统作为信息加密解密和密钥管理保存的载体，在 信息的传输过程中，在信息的加密解密过程中，在密钥的存储过程中，信息的 出错和丢失的几率相比在p c 上完成上述工作要大很多。因此要完善整个嵌入式 加密系统的性能，要从两方面入手：l 、改善椭圆加密算法的性能，提高算法的 速度，减少其系统开销，使之适应低端的嵌入式设备；2 、解决信息传输，信息 加密解密过程以及信息存储方面的系统容错问题。 1 1 2 课题研究的意义 据最新发布的( 2 0 0 9 年中国电脑病毒疫情及互联网安全报告指出：“2 0 0 9 年， 北京t 业人学丁学顾i 学位论文 计算机病毒和木马处于一个低调增长期，虽然一些类似熊猫烧香的重大恶性 病毒越来越少见，但一些小范围、针对性强的新病毒、木马的数量依然在飞速增 长。 2 1 。信息安全问题依然是摆在人们面前一个亟待解决的重要课题。特别是 木马程序在网络上肆意的传播，严重地危害了用户的个人隐私的安全，无孔不入 的木马程序潜入用户的计算机中窃取和篡改重要信息，给国家和个人都带来了重 大的损失。据金山毒霸“云安全 中心监测数据显示，2 0 0 9 年金山毒霸共截获 新增病毒和木马2 0 ，6 8 4 ，2 2 3 个，与2 0 0 8 年相比增加了4 9 。图1 1 为近几年来 的新增病毒和木马数量对比【2 j 。 瑚绰2 0 0 a i 鞠萍期磷2 0 0 r 擎铷嘲埠z , o o , 蛐g歉纛 图l - l 近几年来的新增病毒和木马数量对比 f i g u r el 。1t h ec o m p a r i s o nb e t w e e nt h en u m b e ro fn e wv i r u s e sa n dt r o j a n si nr e c e n ty e a r s 在这种情况下，一些更为先进的安全技术应运而生，嵌入式技术在这里可以 具有“用武之地 。嵌入式网络技术是近几年随着计算机网络技术的普及和发展 而发展起来的一项新兴概念和技术，将嵌入式技术引入网络安全，可以从物理层 面改善系统的安全性。例如，采用嵌入式加密设备对文件进行加密及解密，可以 有效地杜绝在操作过程中数据的外漏和密钥的丢失。采用嵌入式设备对密钥进行 管理可以有效地将密钥与p c 相隔绝，最大限度地保证了密钥的安全性，防止木 马的侵袭。但是事情也并非如人们想象的那样一帆风顺，嵌入式设备本身存在着 一些弱势。例如，一般的嵌入式系统性能都不及p c 的性能，这就导致了在处理 一些复杂度较高的算法时嵌入式设备的能力远低于p c 。同时引入了嵌入式设备 也就意味着在数据的存储和传输过程中发生错误的几率会大大增加( 相比仅在 p c 中进行处理而言) 。 因此本课题的研究意义就是在于提出了基于嵌入式系统的e c c 算法性能的 改进策略，同时针对本课题的u s b 嵌入式系统提出了一种基于本原b c h 码的容 错方案。实验证明，这些改进方案对系统的整体性能及可靠性都有所提高。固然 本论文所阐述的内容是基于本课题所研究的一款嵌入式u s b 设备而讨论的，但 是它是具有通用性的，将这种改进方案和系统容错机制应用到其他相对低速的、 资源较稀缺的，可靠性较差的嵌入式系统的开发中具有着实际的意义。 2 = 三一口 2 奢 i 重 第l 帝绪论 暑皇曼i 一i i ：i , , , i i , i i i i i 鼍! 鼍! ! 曼! 曼! ! 曼! 皇! 鼍! 詈! 皇! ! 皇皇! 皇邕 1 2 本论文的内容安排 1 2 1 主要研究内容 本论文主要探讨了两方面的内容：( 1 ) 基于嵌入式系统的e c c 算法性能的 改进；( 2 ) 提出一种系统的容错方案。这也是构成本论文的两个核心内容。在这 两个大问题下面有许多细节的研究点，在此简要地罗列一下： l 、基于嵌入式设备的e c c 算法性能的改进 口e c c 算法的理论研究，嵌入式系统硬件特性的研究； 口影响e c c 算法性能的瓶颈的研究； 口结合嵌入式系统自身的特性，针对系统的瓶颈提出合理的改进方案； 口算法改进前后系统性能的比较分析。 2 、提出一种系统的容错方案 口系统可靠性的研究，找出系统可靠性方面的漏洞； 口容错理论的研究，基于b c h 检错纠错机制的研究及b c h 编码的软件实现； 口提出并实现一种基于嵌入式系统的系统容错方案。 ， 1 2 2 研究的重点难点 本课题的研究重点在于( 1 ) 针对传统的e c c 算法，提出一种适应于本嵌入 式系统的算法的改进方案；( 2 ) 本原b c h 编码理论的研究及实现，并设计一种 基于b c h 码的系统容错机制。 本课题的难点主要集中在以下的几个方面： ( 1 ) e c c 算法性能瓶颈的研究：e c c 算法是一种基于离散对数问题的公钥 密码体制，它有着深刻的数学理论基础作为支撑，涉及到域算术、a b e l 群理论、 椭圆曲线算术等方面的知识，因此找到已有的e c c 算法瓶颈是一件有难度 的事情。 ( 2 ) 提出e c c 算法的改进方案：由于e c c 算法本身的理论深度，加之该 算法要应用到嵌入式设备之上，因而寻求一种合理的改进方案也就比较困难。 ( 3 ) 容错机制的研究：需要分析研究系统的可靠性方面的漏洞，提出一种 可行的系统容错方案。 ( 4 ) 本原b c h 编码理论的研究及程序的实现：b c h 循环码的性能超过了所 有具有相同码长和编码效率的其他编码，是目前世界上比较先进的一种检错纠错 循环码，因此本文选取b c h 码作为研究的对象。但是b c h 编码理论的基础是近 世代数和线性分组码理论，有着比较深刻的理论基础，实现的难度也比较大。 北京t 业大学t 学硕 j 学位论文 1 2 3 论文的结构安排 本论文共包含两大方面的内容嵌入式e c c 算法性能的改进和系统容错 技术的研究与实现。在章节的编排上，本论文共包含八章。下面简要地介绍一下 每章的内容。 第1 章绪论，总体介绍一下课题研究的背景和意义，并介绍一下本论文主 要研究内容，研究重点难点以及论文结构的安排。 第2 章嵌入式密码器的介绍，宏观地介绍了本课题研究的平台环境，包括 嵌入式加密系统的整体结构，嵌入式设备的硬件组成，并简要地分析了系统存在 的问题，为后续的深入探讨作铺垫。 第3 章e c c 算法基本原理，简要地介绍了椭圆曲线算法的基本理论，包括 实数域上的椭圆曲线，z o 域上的椭圆曲线以及e c c 算法的实现。 第4 章e c c 算法性能的分析及瓶颈的研究，主要分析了e c c 算法的性能， 并结合本研究课题，分析了e c c 算法的瓶颈。 第5 章椭圆加密算法性能的改进，本章是论文的一个核心部分，主要介绍 了e c c 算法的改进方案。内容包括：传统的大数模幂算法，改进的b r 算法， 2 。进制中k 值的选取，大数平方算法的改进，算法改进后性能的比较以及算法进 一步改进的策略。 第6 章嵌入式系统的容错方案，本章结合本课题研究的内容，分析了嵌入 式加密系统的容错需求，简要介绍了u s b 协议中的容错机制和n a n df l a s h 的容 错机制，并结合本课题的具体内容提出了一种基于本原b c h 码的容错方案。 第7 章b c h 码的基本理论，介绍了差错控制码的基本概念，循环码的基本 概念以及b c h 码的基本原理和编码译码等问题。 第8 章基于本原b c h 码的容错机制的实现，介绍了软件实现b c h 编码译 码器的方法，给出了b c h 编码译码系统的原型演示，并结合本课题具体的工作 阐述了嵌入式系统容错机制的实现方法。 结论部分总结了本文所做的工作，并展望了后续研究工作。 4 第2 幸嵌入式密码器系统的介绍 第2 章嵌入式密码器系统的介绍 本课题研究的基础是一个嵌入式加密系统。它作为本课题研究的实验平台， 同时也是本论文提出的理论的实践基础。因此在系统地阐述本论文的核心内容之 前，首先简要地介绍一下该嵌入式加密系统。 2 1 系统整体结构 本课题所研究的嵌入式加密器实际上是一个类似于u 盘的u s b 设备。与u 盘一样，当将该设备接入到p c 的u s b 插槽时，p c 可以识别该设备，同时在 w i n d o w s 的硬件设备管理器中可以显示该设备的描述信息。目前该设备采用的是 基于m s d 类( m e s s a g es t o r a g ed e v i c e 海量存储设备类) 的通信和存储方法，除 了核心处理芯片之外，还外置一个外部f l a s h ，用来海量存储。因此该设备既可 以作为普通的u 盘使用，又可以与p c 端的终端程序配合实现加密器的功能。但 是这一方案有可能在不久被改变，因为我们正在着手研究基于h i d 类( h u m a n i n t e r f a c ed e v i c e 人机接口设备类) 的新一代加密器。h i d 设备的优势在于数据传 输控制方便，易于程序设计开发，但是它的传输速率要比m s d 类低一些。系统 的整体结构如图2 1 所示。 匕二啦醯蚓 翌翅趱四 图2 l 系统整体结构 f i g u r e2 - 1t h e o v e r a l ls t r u c t u r eo ft h es y s t e m 图2 1 给出了最为直观的系统描述。由p c 驱动将明文数据通过u s b 接1 2 1 发 送到嵌入式加密器设备中，设备会对传送过来的数据进行指定的处理( 加密操作 或解密操作) ，然后再将处理后的文件通过u s b 接口传输给p c 。加密与解密的 操作完全放在嵌入式设备中执行，另外嵌入式加密器中保存了加密解密时所需要 的私钥，私钥的管理完全由加密器设备负责。这样嵌入式设备将大部分与加密解 密相关的处理和绝对不能泄露的私钥与p c 完全隔离开来，从而最大限度地保证 了信息的安全。将加密解密程序与私钥同p c 有效地隔离开来，可以防止木马程 序对应用程序的感染，同时避免了密码发送型的木马程序在p c 中窃取用户的私 钥。 5 北京t 业人学t 学硕l j 学位论文 2 2 嵌入式设备的硬件组成 嵌入式加密器设备的核心组件总共有四部分组成，包括a t m e l ( 爱特梅尔) 公司生产的a t 9 1 s a m 7 x 2 5 6m c u ：h y n i x ( 海力士) 公司生产的h y 2 7 u s 0 8 2 8 1 a 1 6 m bn a n df l a s h ；u s b 的主通信接1 2 1 和其他丰富的外围接口【3 】，如图2 - 2 所示。 裔物辨限接f 1 图2 2 嵌入式加密器设备框图 f i g u r e2 - 2b l o c kd i a g r a mo f e m b e d d e de n c r y p t i o nd e v i c e 下面对加密器设备各部分器件做一个简要的介纠4 卅。 a t 9 1s a m 7 x 2 5 6 的a 剐7m c u a t 9 1s a m 7 x 2 5 6 芯片是基于3 2 位a r mr i s c 处理器，结构如图2 3 所示。 图2 3a t 9 1 s a m 7 x 2 5 6 内部结构图 f i g u r e2 - 3a t 9 1s a m 7 x 2 5 6i n t e r n a ls t r u c t u r e 从图2 3 中可以看到a r m 7 t d m ip r o c e s s o r 处理器，可通过j t a g 对其编程。 从处理器向下将使用m e m o r yc o n t r o l l e r 对s r a m 、r o m 、f l a s h 进行管理。通过 a p b 总线( a p b 主要用于低带宽的周边外设之间的连接，例如u a r t 等) 管理 右下的u s b 接口与p c 通信和左下的p i o 接口去访问n a n df l a s h 。 1 a r m 7 t m d i 是目前使用最广泛的3 2 位嵌入式r i s c 处理器，属低端a r m 6 第2 章嵌入式密码器系统的介绢 处理器核。采用3 级流水线结构、a r m 3 2 位高性能指令集和t h u m b l 6 位高代码 密度2 个指令集。运行速度可达5 5 m h z ，平均每个时钟周期可执行指令数为 o 9 m i p s m h z 。t d m i 的基本含义为： t ：支持1 6 位压缩指令集t h u m b ； d ：支持片上d e b u g ； m ：内嵌硬件乘法器( m u l t i p l i e r ) ； i ：嵌入式i c e ，支持片上断点和调试点。 2 片内存储器 ( 1 ) 2 5 6 k 字节的f l a s h 存储器： 一1 0 2 4 页，每页2 5 6 字节： 一快速访问时间，最差条件下一个访问周期仍能达到3 0 m h z ； 一1 0 ，0 0 0 次擦写寿命，1 0 年数据保存能力； 一a t 9 1 s a m 7 x 2 5 6 将片内f l a s h ，s r a m ，r o m 等统一编址，f l a s h 存储器 的地址始终映射在0 x 0 0 1 0 0 0 0 0 。复位后可以在0 x 0 访问。 ( 2 ) 6 4 k 字节s r a m s r a m 的访问可在单时钟周期内完成，通过地址0 x 0 0 2 0 0 0 0 0 对s r a m 进 行访问。 ( 3 ) 片内r o m - r o m 首地址始终映射在地址0 x 3 0 0 0 0 0 。r o m 包含了s a m b a 。 h y n i x ( 海力士) h y 2 7 u s 0 8 2 8 1an a n df l a s h h y n i x ( 海力士) h y 2 7 u s 0 8 2 8 1 a 系列拥有1 6 m * 8 b i t s 容量。设备提供了1 8 v 电源电压供应以及3 3 v 电源电压供应。存储器被分成独立的块，这样可以在其 他块的数据被清除的时候本块仍可以保存有效的数据。设备包含2 0 4 8 个块，由 3 2 页组成。一个编程的操作允许在典型的2 0 0 u s 内写入5 1 2 b y t e s 页，一个清除 操作可以在典型的2 m s 内在一个1 6 k b y t e 块上执行，页中的数据可以被循环以 5 0 n s 一个b y t e 读出。 外围控制设备接口 1 1 时钟发生器( c k g r ) ； 2 ) 电源管理控制器( p m c ) ； 3 ) 先进中断控制器( a i c ) ； 4 ) 调试单元( d b u g ) ； 5 ) 内存控制器( m c ) ； 6 1 时间窗看门狗定时器( w d t ) ； 7 ) 两个并行输入输出控制器( p i o ) ： 8 ) u s b 2 o ； 7 北京t 业人学t 学珂! i j 学位论文 9 ) 串口调试单元( d b g u ) 。 开发时将编译好的应用程序通过j t a g 下载到目标机，程序被保存到2 5 6 k 字节的内部f l a s h 存储器中，并在那里保存程序。加密系统的密钥也被保存在内 部的f l a s h 存储器中，并通过密钥匹配算法在那里得到维护。 2 3 系统存在的问题 嵌入式设备的优势在于体积较小，使用灵活方便，功能专一，结构简单。但 是它与p c 相比在性能上仍存在着不小的差距。通过表2 1 可以看出一台普通的 基于i n t e lp e n t i u m 4 的p c 与a t 9 1s a m 7 x 2 5 6 之间的差距。 表2 - 1 i n t e lp e n t i u m 与a t 9 1s a m t x 2 5 6 性能比 t a b l e2 1t h e c o m p r a s i o no f i n t e lp e n t i u ma n da t 91s a m 7 x 2 5 6 比较项目 i n t e ip e n t i u m4a t 9 1 s a m 7 x 2 5 6 处理器速度 1 3g h z 到3 8g h z5 5 m h z 程序运行空间2 5 6 m b l g b6 4 k b 虽然这种性能上的差异是很显著的，但嵌入式设备并不需要做成像通用的 p c 那样的性能。因此就带来了一个问题运行于该嵌入式设备中的应用程序 也必须符合其低端环境的要求。 e c c 算法是一个时间复杂度和空间复杂度都很高的公钥密码体制算法。因此 不难理解，将该算法运行于6 4 k b 的存储空间( 最理想的状态下) ，主频为5 5 m h z 的环境上是有挑战性的。事实也证明了以上的观点，即使在性能较高的p c 上运 行e c c 加密程序，所花费的时间仍然很让人难以接受。因此将算法的性能进行 改进是一项必需的工作。具体的改进方案以及性能的比较将在后面的章节中介 绍。 另外，本课题中采用的是基于u s bm s d 类的通信和存储方式。使用这种方 式的好处就是数据传输速度快，同时加密器可作为一个u s b 存储设备。因此在 开发设备电路时，不但要使用核心处理器a t 9 1 s a m 7 x 2 5 6 ，同时还要外接一个 n a n df l a s h 作为外部存储介质。a t 9 1 s a m 7 x 2 5 6 与n a n df l a s h 之间通过p i o 总 线连接，其连接电路如图2 4 所示。 8 图2 - 4n a n df l a s h 与m c u 连接管脚不意图 f i g u r e2 - 4n a n d f l a s ha n dm c u c o n n e c tp i nf i g u r e 本课题中采用的n a n df l a s h 是h y n i x ( 海力士) 公司生产的h y 2 7 u s 0 8 2 8 1 a 。 n a n df l a s h 的功能主要有两个：( 1 ) 存放p c 端的应用程序，实现设备插入p c ， 程序自启动的功能；( 2 ) 在p c 与设备进行通信时，需要将数据先写入n a n df l a s h 中缓冲，再从n a n df l a s h 中将数据读出。之所以要先将数据写入n a n df l a s h 中 缓冲是因为本系统采用的是m s d 类的通信方式，因此嵌入式加密器设备在整个 系统中如同一个u 盘，数据的读写目标都是针对n a n df l a s h 的，而且p c 中 w i n d o w s 自带的驱动程序也会将要加密解密的数据写入到n a n df l a s h 之中。 由于很难保证数据在写入或读出n a n df l a s h 的过程中不发生任何错误，因此 需要设计n a n df l a s h 容错系统，。传统的n a n df l a s h 容错技术多采用纠错能力不 强的h a n m i n g 码。对于一个5 1 2 字节的数据块，它至多可以纠正l 位的误码。 但是作为一个嵌入式加密解密设备，需要一种更为强大的容错机制。因此，系 统的容错技术也是本论文的研究重点之一。 2 4 本章小结 本章主要就本课题所研究的嵌入式系统平台进行了简要地介绍。首先介绍了 系统的整体结构，从功能的角度介绍了嵌入式加密器的作用和使用方法。然后介 绍了嵌入式设备的硬件组成，包括选用的核心处理器芯片，外围电路，通信接口 等相关参数。最后就本嵌入式加密系统所存在问题进行了宏观上的说明，为后续 章节的具体阐述做了铺垫。 9 北京t 业人学t 学硕i j 学位论文 l o 第3 章e c c 算法基本原理 第3 章e c c 算法基本原理 在讨论e c c 算法的改进之前，首先简要地介绍一下e c c 算法的基本原理， 在此基础之上再讨论算法中影响系统性能的瓶颈以及算法改进策略。 1 9 8 5 年，n e a lk o b l i t z 和v i c t o rm i l l e r 将椭圆曲线引入密码学。他们提出了椭 圆曲线公钥密码体制，也就是说利用有限域g f ( p ) 上的椭圆曲线上的点集构成的 群上定义的离散对数系统，构造出基于离散对数的公钥体制椭圆曲线离散对 数密码体制( e c d l c ) 【7 1 。椭圆曲线公钥密码体制的安全性理论基础是椭圆曲线 上离散对数问题的困难性，即椭圆曲线对数难题。正是因为这种安全性的保障， 椭圆曲线公钥密码体制才可能