（微电子学与固体电子学专业论文）usb安全钥片上系统设计.pdf

摘要 随着i n t e r n e t 在全世界的迅速发展，计算机信息安全被上升到极其重要的高度。 特别对于电子商务作为信息网络的一个特殊应用领域，运行着大量需要保护的数据和信 息，对此的安全保障，是尤为重要的。然而，由于在安全领域技术上的滞后，这将可能 是我国今后网络商务稳步发展的一个瓶颈。为此，本课题将针对电子商务领域安全性、 方便性和低成本的需要设计u s b 安全钥，它是利用u s b 技术与r s 加密解密芯片结合进 行研究和设计，其主要功能就是要实现数据的硬件加密解密与身份认证。 u s b 是现今应用得最普遍的一种外围设各，更重要的是u s b 有随身携带和即插即用 的优点，这些优点都将有利于u s b 在身份认证领域的应用和推广。本课题研究和设计的 核心内容是r s 算法的理论基础和硬件实现，设计过程中将使用硬件描述语言 v e r i l o g h d l 进行寄存器传输级程序设计。 本文将深入研究r s 算法，提出用除法求余函数代替轮减求余函数实现加解密中基 本的运算，求模。另外还将对r s a 算法中的模幂和模乘运算进行探讨。在此基础上，利 用x i l i n x 进行算法的程序设计，用m o d e l s i m 设计进行仿真验证，并对结果进行分析。 关键词：u s b ， r s a ，加密解密，v e r i l o gh i ) l a b s t r a c t b e c a u s eo ft h es p e e d yd e v e l o p m e n to ft h ec o m p u t e ra n di n t e r n e tn e t w o r kt e c h n o l o g y ， t h es e c u r i t yi s s u e so ft h ec o m m u n i c a t i o na r ep l a y i n gam o r ea n dm o r er o l ei nt h e d o m a i n f o rt h ee l e c t r o n i cc o m m e r c e 。b e c a u s ei t sas p e c i a la p p l i c a t i o ni nt h e c o m m u n i c a t i o nn e t w o r k ，w h i c hi sf l o w i n gag r e a td e a lo fd a t aa n di n f o r m a t i o nw h i c h n e e d i n gp r o t e c t i o n t h i sp r o t e c t i o ni sv e r yn e c e s s a r ya n di m p o r t a n t h o w e v e r ， h a n g i n gb e h i n dt ot h eo t h e rp r e c u r s o ri ns a f e t yt e c h n o l o g ym a k e sab o t t l e n e c kf o r o u rn a t i o n a ld e v e l o p m e n to ft h en e t w o r kc o m m e r c e b e c a u s eo ft h i s ，t h i ss t u d ya i m a tt h es a f e t y 、c o n v e n i e n c ea n dl o wc o s tt od e s i g nu s bc r y p t o g r a p h yk e yo nr s af o r t h ee l e c t r o n i c c o 口n e r c e a n d ，i tw o u l du s et h et e c h n i q u eo fu s ba n dt h er s a e n c r y p t d e c r y p ta r i t h m e t i ct os t u d ya n dd e s i g n 。w h o s ep r o d u c ec a nb eu s e dt oi d e n t i f y t h ei d e n t i t ya n de n c r y p tt h ed a t a t h eu s bt e c h n o l o g yi so n eo ft h em o s te x t e n s i v ea p p i i e dp e r i p h e r a le q u i p m e n t ， w h a ti sm o r e ，t h eu s bt e c h n o l o g yi sap o c k e ta n d “p l u ga n dp l a y ”d e v i c e ，w h i c h c a nm a k et h ea p p l i c a t i o no fu s bm o r ee a s i l ya n dp o p u l a r i z e di nt h ei d e n t i f yd o m a i n i na d d i t i o n ，t h em a i n w o r ko ft h i ss t u d yt o p i ci st os t u d yt h er s ac r y p t o g r a p h y a l g o r i t h m i ca n d h a r d w a r ed e s i g n w ew i l ld e s i g nt h i si t e mi nt h eh a r d w a r ed e s c r i p t i o n 1 a n g u a g e - v e r ii o g h d la n di tw o u l db eo nt h eb a s i so ft h er t ld e s c r i p t i o n t h i sd i s q u i s i t i o nw o u l ds t u d yt h er s ap u b l i c k e yc r y p t o g r a p h ya l g o r i t h m ，a n df i n d ab e t t e rw a yt oc a r r yo u tt h eb a s i co p e r a t i o n ，m o d u l a r ，i nt h ec r y p t o g r a p h ya l g o r i t h a u a n d ， i tw i l lp r o b ei n t ot h eo p e r a t i o no ft h em o d u l a re x p o n e n t i a t i o na n dm o d u l a r m u l t i p l i c a t i o n o nt h eb a s i so ft h e s e ，e d as o f t w a r et o o l ，x i l i n x 。w o u l db eu s e dt o d e s i g nt h eh d lp r o g r a m , a n dm o d e l s i ma sae m l u a t o ra n dv a l i d a t i o n i nt h ee n d ，t h e r e s u l t sn e e dt ob ea n a l y z e da n dv a l i d a t e d k e yw o r d s ：u s b ，r s a ， e n c r y p t d e c r y p t 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写过的科研成果。对本文的研究在做 出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识 到本声明的法律责任由本人承担。 论文作者签名：螂 日期：幽生丝旦 关于学位论文使用授权的声明 本人完全了解贵州大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅；本人授权贵州大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：链埤翩签名：缇良日期：回生臼 第一章绪论 1 1 课题研究背景及意义 随着i n t e r n e t 在全世界的迅速扩展，计算机信息安全被上升到极其重要的高度。 特别对于电子商务作为信息网络的一个特殊应用领域，运行着大量需要保护的数据和信 息，由于其自身特殊性，如果系统的安全性被破坏，造成敏感信息暴露或丢失，或网络 被攻击等安全事件，这将可能导致严重的后果。因此对于信息的安全保障，将变得尤为 重要。 目前我国企业和政府部门所用的网络安全技术大多数来自国外，这将使得我国在网 络安全技术的发展受制于他人。世界己进入信息时代，人们在计算机面前就可以完成购 物、汇款、邮递等活动。然而，如果这些交易行为受到攻击、或有黑客伪装为交易的其 中之一，那么他就有可能从中窃取利益或者扰乱交易行为。如果交易双方进行的是巨额 的金融贸易，那么攻击所造成的损失将会相当巨大。如果交易双方通过具有权威性的第 三方作为传输数据和用户身份的认证，那么其成本将可想而知的高。为了实现基本信息 的安全我们可以利用密码技术。基本的信息安全包括信息的机密性、完整性、鉴别性和 不可否认性，而密码技术正适合用作保障信息安全的核心技术。近年来，密码技术己经 应用于各种信息安全系统中，保障了网络传输中信息的安全性为了使密码技术能够有 多种方法的应用，本设计把近年来得到广泛应用的u s b 技术与之结合，设计u s b 安全钥 硬件设备，实现数据加密或身份认证。 1 2 u s b 技术在网络信息安全应用的优势 为了更方便地利用密码技术，我们将u s b 与加解密算法结合起来。这是因为，u s b 有着多方面的应用优势，并且u s b 接口技术已经在p c 机的多种外设上得到广泛的应用， 包括扫描仪、数码相机、输入设备等，这使得人们对于u s b 设备的使用很熟悉。这些因 素总得起来会使得u s b 技术的研究很容易得到推广和应用。 u s b 安全钥大致有以下几个优点。： 1 ) 终端用户的易用性。即插即用，使用方便；自我检测外设，自动地进行设备驱动、 设置。 2 ) 应用广泛，适应不同设备，传输速率从几千比特率到几十兆比特率。 3 ) 兼容性好，与p c 产业的一致性，基本上每台p c 都能安装u s b 驱动程序。 4 ) 灵活性好，它允许选择设备缓冲器大小，通过指定数据缓冲区大小和执行时间，支 持各种数据传输率。 5 ) 健壮性，具有出错处理和差错恢复机制。 6 ) 同步传输带宽，确定的带宽和低延迟适合各种实时设备。 7 ) 价格便宜，实际上就是一个带有u s b 接口的微控制器，成本只有十几美元。 1 3 密码密钥体系 1 3 1 对称型公钥密码体系 对称型公钥密码是一种加密和解密具有相同密钥的一种加密技术。对称加密算法的 特点是算法的运算量小，实现简单，运算速度快。 但是对称型公钥密码对密钥的管理要求严格，一旦密钥管理出现问题就严重影响信 息的安全性。因为在发送加密数据的同时，也需要将密钥通过网络传输通知接收者，第 三方在截获加密数据的同时，只需再截取相应密钥即可将数据解密使用或进行非法篡 改。为了提高其安全性，密钥必须经常更换以确保所泄露的内容为有限数量。但是，很 明显这种方法并没有从根本上消除密码体系的脆弱性。因此，对称型公钥密码算法的应 用受到了威胁。 1 3 2 公钥密码体系 公钥密码的思想“”是1 9 7 6 年，美国密码学专家w d t f f i e 和m e h e l l n a n 在“密码 学新方向”这篇文章中提出的，然而他们并没有给出一个实用的公钥密码系统。而第一 个公钥密码体制是r s a 算法，它是美国麻省理工学院( m i t ) 的研究小组成员李维斯特 一2 一 ( r lr i v e s t ) 、沙米尔( a s h a m i r ) 和艾德勒曼( l a d l e r m n ) 在1 9 7 8 年提出的( 取每人第 一个字母命名) 。r s a 是一种以幂模函数为密码算法的公钥体制。到目前为止，仍不失 为最有希望的一种公钥密码体制。 加密解密算法r s a 是一种非对称密码体制。在r s a 算法中，使用两个正整数作为加 密和解密密钥：加密密钥( e ，n ) ，解密密钥( d ，n ) 。它的理论基础是： 若整数g 和n 互素，则g 忡一l ( m o d ，1 ) 其中中0 ) 表示比n 小，但与n 互素的正整 数的个数，中o ) 称为n 的欧拉函数。 要建立一个r s a 密码系统，首先任意选取两个大素数p 、q ，计算乘积：n = p 章q ； 并得到欧拉函数： o ( n ) - ( p - 1 ) ( 口- 1 ) ，其中o c i , ( n ) s q r t ( n ) ，直到找到一个整数，使x 2 一n ，是完全平方记为y 2 ， 于是p = x + y ，q = x y 因此应使i p - q i 同p 、q 的规模差不多，这只要p 、q 相差几位就行 即要求p 、q 长度相差不大 d 、应排除某些明文和某些加密指数e ，若e - i 是p - i 、q - i 的倍数，则存在m ，使得 e ( m ) 铀，故e = 中( n ) 2 + i 应绝对排除。 ( 2 ) 对公共模数n 的攻击 如果n 相同，但有不同的e 和d ，产生的问题是假如同一消息，用两个不同的指数 加密，且两个密钥互素。那么无需任何一个解密指数就可恢复明文。 因为c i 铀 m o dn c = m o dn ( n ，e l ，e 2 ，c i ，c 2 已知) 由e i ，e 2 互素，有r x e l + s e 2 - - 1 求出r 、s ( c 一锄。= m m o dn 避免这种攻击的方法是不能在一组用户之间共享n 。 ( 3 ) 对r s a 低加密指数和低解密指数n 攻击 应使解密密钥d 很大，随机填充消息，确保m 和n 相同长。但是，由于r s 进行的 都是大数计算，所以速度一直是r s a 的缺陷；另外，产生密钥很麻烦，受到素数产生技 术的限制，因而难以做到一次一密。 1 3 5 数字签名 数据或文件是根据亲笔签名或印章来证明其真实性。但在计算机网络中传送的数据 文件又是如何“盖章”呢? 就是数字签名所要解决的问题伽。数字签名必须保i , t 以- f - - 点： ( 1 ) 接收者能够核实发送者对文件的签名； ( 2 ) 发送者事后不能抵赖对文件的签名： 一b 一 ( 3 ) 接收者不能伪造对文件的签名。 到现在为止已有多种形式数字签名方法，但采用公开密钥算法要比采用常规密钥算 法更容易实现。下面就来介绍这种数字签名 发送者a 用其密钥s k a 文件x 进行运算，将结果d 。传送给接收者b 。b 用已知的公 开密钥解密得出e 。( 陆( x ) ) = x 。因为除a 外没有别人能具有a 的解密密钥s k a ，所 以除a 外没有别人能产生密文d 。( x ) 。这样，文件x 就被签名了。如图1 1 所示： 发送者a接收者b sk a 用秘密密钥 进行签名 pk a 用公开密钥 核实签名 图1 i 数字签名的实现 简单地解释签名密钥对为：发送者a 收到数据后，使用私钥对其签名并通过网络传 输给接收者b ，接收者b 用公钥解开签名，由于私钥具有唯一性，可证实此签名信息确 实为由发送者a 发出。此过程中，任何人都没有私钥，因此无法伪造接收方的签名或对 其作任何形式的篡改，从而达到数据真实性和不可抵赖性的要求。 1 3 6 文件鉴别的意义 在信息安全领域中，对付被动攻击的重要措施是加密，而对付主动攻击中的篡改和 仿造则要用文件鉴别的方法。文件鉴别就是一种过程，它使得通信的接收方能够验证所 收到的文件的真伪。 使用传统的加密方法就可以达到文件鉴别的目的。如果能够确信只有文件的发送者 和接收者才知道所用的加密密钥，那么可以推断，只有发送者才能制作此秘密文件。使 用软件进行加密往往会消费很长的时间，而硬件加密就完全不同了，但其费用并不会很 便宜，但其速度相对软件实现会快很多。 一6 一 1 4 利用数字硬件设置现实算法 r s 密码体制是运算复杂度高的密码算法，在实现r s 密码算法时，可以通过软件 和硬件f p g a 方式实现。硬件实现相对软件实现有运算速度快、安全性能高、兼容性好 等优点。 利用硬件描述语言( 皿l ) 能够很容易实现大型复杂电路系统的设计和管理。采用 l t d l 能够通过基于语言的描述，对正在进行设计的电路自动进行综合忆“1 。h d l 主要有两 种语言：v e r i l o g h d l 和v t l d l 。他们的特点在于；能形式化地抽象地表示电路的行为和 结构；支持逻辑设计中层次与范围的描述；可借用高级语言的精巧结构图来简化电路行 为的描述；具有电路仿真与验证机制以保证设计的正确：支持电路描述由高层到低层的 综合转换；硬件描述与实现工艺无关；设计可重用。 1 4 1 v e r i l o gh d l 的设计流程 用v e r i l o g 进行设计时一般采用自项向下的设计方法“。利用层次化和结构化的方 法，一个完整的硬件设计要划分为由若干个可操作的模块，然后设计出相应的模块并通 过仿真验证后，再把各模块整合成一个整体。由于采用v e r i l o g i t d l 自顶向下的设计方 法是首先从系统设计入手的，因而从顶层进行功能划分和结构设计。系统的总体仿真是 顶层进行功能划分的重要环节，这时的设计是工艺无关的。由于设计的主要仿真和调试 过程是在高层次完成的，所以能够早期发现结构设计上的错误，避免设计工作的浪费。 同时也减少了逻辑仿真的工作量。图1 2 为基于h d l 的硬件电路系统设计流程图，它简 要地说明了模块的编译和测试过程。 一7 一 1 4 2 设计输入 图1 2 ：基于h d l 的硬件电路系统设计流程图 设计输入是指编写基于h d l 语言的描述文件，而行为建模描述方法是工业界使用的 主要描述方法，用它能够进行大规模的芯片设计m 1 。行为建模是指在描述一个设计的功 能特性时，仅指定所设计电路将要做什么，而不明确提出怎样来构建该硬件电路，也就 是只需要详细描述逻辑电路的输入输出模式，而没有必要对其物理层门级实现细节进行 描述。行为建模是把设计的重点放到能够实现的电路功能上，而不是具体的逻辑门及其 互连。 行为建模的一般设计步骤：( 1 ) 快速创建一个设计的行为级原型电路；( 2 ) 验证它 的功能性：( 3 ) 利用一种综合工具将去除其中的冗余逻辑，并且将在其他结构和多级等 效电路之间进行权衡，最终完成一个能兼顾面积限制或定时约束的设计。 一8 一 1 4 3 仿真与功能验证 设计的功能是通过仿真来进行正确性验证的，当设计出现问题时返回设计输入进行 修改。验证工作分三步：( 1 ) 测试方案的拟定；( 2 ) 测试平台的改进；( 3 ) 测试执行。 测试方案要经过组织、编写，以确定什么功能特性是需要测试的，应该用什么方法 进行。测试平台是一个v e r i l o g 模块，要把待测单元连同仿真过程中模型输入所用到的 图形发生器一起通过具体实例加以说明。图形是测试平台的主要组成部分。编制测试平 台是为了识别在仿真进行过程中所观测的目标和它的时序性动作。通过对观测到的时序 动作判断所设计功能的正确性，如果出现问题，则应返回设计输入进行修改。 1 4 4 映象和布局布线 由于各种f p 6 a 器件的工艺各不相同，因而当用不同厂家的不同器件来实现已验证 的逻辑网表时，需要不同的基本单元库与布线延迟模型与之对应才能进行准确的优化、 映象和布局布线 1 1 1o 逻辑设计时只需要用文件说明所用的工艺器件和进行条件约束，e d a 工具就会自动地根据这一文件相应的库和模型进行准确的处理从而大大地提高了设计 效率。 1 5 论文的主要内容 本课题的任务就是把u s b 技术与用硬件实现r s a 系统有机地结合起来，设计成u s b 安全钥，其中最好主要的是研究如何用硬件实现r s a 的加解密。首先要傲的是对其算法 进行研究，对求模运算、模乘和模幂运算进行分析，对各种实现方法进行比较并选取适 合的算法实现。然后还要对设计的r s a 密码芯片进行了仿真，证明设计的正确性。本课 题将利用硬件描述语v e r i l o g h d l 对其进行r t l 级描述，使用m o d e l s i m 仿真工具进行仿 真。 一9 一 第二章u s b 技术的研究 2 1u s b 技术简介 通用串行总线( u n i v e r s a ls e r i a lb u s ) 咖1 是用于将适用u s b 的外围设备连接到主 机的外部总线结构，其主要是用在中速和低速的外设。u s b 是由c o m p a q 、d i g i t a l 、i b m 、 i n t e l 、m i c r o s o f t 、n e c 以及n o r t h e r nt e l e c o m 七家公司共同开发的一种新的外设连 接技术。这一技术将最终解决对串行设备和并行设备如何与计算机相连的争论，大大简 化计算机与外设的连接过程。u s b 是通过p c i 总线和p c 的内部系统数据线连接，实现 数据的传送。u s b 同时又是一种通信协议，他支持主系统( 主机) 和u s b 的外围设备 ( d e v i c e ) 之间的数据传送，而主机与设备之间是由h u b 连接的。 2 2u s b 的即插即用 u s b 在各种接口技术中优越性最大的可谓算其即插即用功能。所谓即插即用( p l u g p l a y ) ，主要包含两个方而的内容：一、是热插拔，二、是自动配置。热插拔决定于物理 层的实现，而自动配置则主要依靠软件协议。 众所周知，传统的串口并不支持热插拔，因为串口在热插拔时会产生很强的电流， 容易烧毁硬件电路或接口芯片。u s b 在这方而做了很多努力，使得热插拔在u s b 设备成 为可能。 u s b 采用四线电缆来传输信号与电源“”，如图2 1 所示。 5m e t e r sm a j t v r 厂，、ir n d +r d ih h ：h h 。k ”。i ， 【j n d 图2 1 ：u s b 采用四线电缆 一1 0 一 其中d + 和d - 是一对差模的信号线，使用3 3 v 的电平，而v b u s 和g n d 则提供了+ 5 v 的电源。而u s b 正是在电缆和连接点的设计上做了处理，才使得热插拔产生的强电流可 以被安全地吸收至于自动配置，主要是指设备在插入h u b 的下行端口后能够被主机自动 识别并进行信息交换，最终使设备在整个i j s b 网络中可以正常工作。这一功能主要依靠 u s b 的总线枚举过程来实现。 首先，u s b 总线应该能够自动探测出新设备的插入图2 2 是i j s b 设备与h u b 的连 接示意图： 主机h u h p a r t全速设备h u bp o r t d + 屏蔽双绞线 d + d -d - 低速设备 i主机鼬薹 斐星蔽非双绞线 d + d 图2 2u s b 设备连接示意图 主机或h u b 的下行端口( 图左) 的d + 与d 一都用1 5 k 欧姆电阻接地，使得在没有设备 插入的时候，d + 与d _ 上的电平始终为低。全速设备的上行端口的d + 通过1 5 k 欧姆电阻 接到3 3 v ，而低速设备的上行端口的砬过1 5 k 欧姆电阻也接到3 3 v ，使得在设备 插入主机或h u b 的时候，d + 或d - 上会产生一个上升沿。主机或h u b 就依靠这个上升沿 判断设备的插入和设备的类型，是全速的还是低速的。 有了即插即用这一特点，u s b 设备可以随时插入和拔出，在使用上极其方便，这是 u s b 最吸引普通用户的地方。 2 3 i j s b 的基本特性 每一个设备会有一个或者多个的逻辑连接点在里面，每个连接点叫端点。每个端点 有四种数据传送方式：控制方式传送；同步方式传送；中断方式传送；批量传送。但是 所有的端点0 都被用来传送配置和控制信息口。1 。 在主机和设备的端点之间的连接叫作通道，端点0 叫做缺省( d e f a u l tp i p e ) 。对于 同样性质的一组端点的组合叫做接口，如果一个设备包含不止一个的接口就可以称之为 复合设备。 同样的道理，对于同样的类型的接口的组合可以称之为配置。但是每次只能有一个 配置是可用的，而一旦该配置激活，里面的接口和端点就都同时可以使用。主机从设备发 过来的描述字中来判断用的是哪个配置，哪个接口等等，而这些的描述字通常是在端点 0 中传送。传输方式在u s b 的数据传送的方式下，有四种的传输方式：控制、同步、中断 和批量魄嘲 通常所有的传送方式下的主动权都在p c 边，也就是主机边。控制方式传送：控制传 送是双向传送，数据量通常较小。u s b 系统软件用来主要进行查询、配置和给u s b 设备 发送通用的命令。控制传送方式可以包括8 、1 6 、3 2 和6 4 字节的数据，这依赖于设备 和传输速度。控制传输典型地用在主计算机和u s b 外设之间的端点0 之间的传输，但是 指定供应商的控制传输可能用到其它的端点。 同步方式传送：同步传输提供了确定的带宽和间隔时间。它被用于时间严格并具有 较强容错性的数据流传输，或者用于要求恒定的数据传送率的即时应用中。例如执行即 时通话的网络电话应用时，使用同步传输模式是很好的选择。同步数据要求确定的带宽 值和确定的最大传送次数。对于同步传送来说，即时的数据传递比完美的精度和数据的 完整性更重要一些，也就是会舍弃数据部分完整性为代价来取得即时的数据传输。 中断方式传送：中断方式传输主要用于定时查询设备是否有中断数据要传送。设备 的端点模式器的结构决定了它的查询频率，从l 到2 5 5 m s 之间。这种传输方式典型的应 用在少量的分散的、不可预测数据的传输。键盘、操纵杆和鼠标就属于这一类型。中断 方式传送是单向的并且对于主机来说只有输入的方式。 批量传送：主要应用在数据大量传送传送和接受数据上，同时又没有带宽和间隔时 间要求的情况下，要求保证传输。打印机和扫描仪属于这种类型。这种类型的设备适合 于传输非常慢和大量被延迟的传输，可以等到所有其它类型的数据的传送完成之后再传 送和接收数据。 一1 2 一 2 4 u s b 安全钥的完整功能 u s b 安全钥最早基于u s b 的热插拔、速度以及硬件等优势，结合加密算法，用于办 公文件、软件等的存储和加密嘲1 。但u s b 安全钥的用武之地远不止这些，与网络技术结 合，用于时下最时尚的电子商务中，才使其大显神通。u s b 安全钥结合传统的电子商务 核心技术和新兴的u s b 技术，用于实现电子商务中的关键技术身份识别，在未来电 子商务领域具有广阔的应用前景。u s b 安全钥集数据加密和数据存储两大功能于一体， 推出了电子商务的发展。 传统的电子商务或是网络e m a i l 等的身份认证基本上是通过两种方式来实现。一种 是密码机制，双方约定好规则。这是目前最为普遍的方式，但是这种方式的严重缺点显 而易见。密码作为最重要的信息，在网络上传输，很容易被黑客攻击截获，经常发生密 码被盗。第二种方式是通过第三方的认证，双方共同信任第三方公司提供的信息，从而 进行交易。微软在n e t 计划中推出的认证服务器就提供这种服务。但是，如果信誉度 建立在第三方上，那么就会受到第三方的制约，掏钱不说，还要担心第三方是否会倒闭。 u s b 安全钥解决了这两种方式无法解决的问题。 完整的u s b 安全钥系统由三部分组成：安全钥端；p c 端，由任何一台可按入网络的 p c 构成，并安装p c 端的用户身份认证软件；s e r v e r 端，任何一台网络服务器安装用于 身份认证的s e r v e r 端软件由于整个设计内容庞杂，技术难度高，所以本文只对安全 钥端的加解密作详细阐述。 u s b 安全钥系统结构体系及功能流程如图2 3 所示，列出了九个步骤，描述了u s b 安全钥从插入p c 到完成一身份识别的完整流程。 一1 3 图2 3u s b 安全钥在电子商务中的应用 1 ) 插入u s b 安全钥，p c 得到安全钥的i d 号 2 ) 用户输入自己的用户名和密码 3 ) p c 将安全钥的i d 、用户名和密码发往服务器 4 ) 服务器产生一个随机数，并发往p c 5 ) p c 将这个随机数传递给u s b 安全钥 6 ) u s b 安全钥使用内部存储的密钥和算法加密随机数，并将结果发回p c 7 ) p c 将加密结果传递给服务器 8 ) 服务器解密p c 发来的数据，并与原随机数比较，如果符合即认为用户身份合法 9 ) 向p c 发送身份确认信息 2 5 小结 本章对u s b 技术和u s b 安全钥做了比较简单的介绍，由u s b 安全钥在电子商务中的 应用可知，u s b 安全钥其规模是相当大的，要独立完成整个u s b 安全钥的可能性不大， 所以在今后工作中将着力于对r s a 算法硬件实现的研究。 - 1 4 第三章r s a 算法理论基础的分析与研究 在r s a 算法会涉及到一些数学知识，本章将进行相关数学基础知识和密码学的基本 概念做一些必要的介绍。 3 1 数学基础 3 1 1 素数 素数“枷1 是指一个大于1 且因子只有1 和它本身的整数。没有其他数可以整除他。2 是一个素数，其他素数如1 7 、5 3 和1 2 3 4 5 6 7 等。如果单凭印象去捉摸，是无法确定它 到底是不是素数的但有些数则可以马上说出它不是素数。一个数，不管它有多大，只 要它的个位数是2 、4 、5 、6 、8 或0 ，就不可能是素数。此外，一个数的各位数字之和 要是可以被3 整除的话，那么它也不可能是素数。在本章所用到的素数都是大素数，这 是为了公钥密码的安全性需要，越大的素数的使用，算法就越难被破译。 3 1 2 互素 如果有两个数，它们除1 之外没有其他共同的因子，则称这两个数是互素的。也就 是说，如果整数a 和n 的最大公因子( 记为：g c d ) 等到于1 ，则：g e d ( a ，n ) = l 。 如11 和1 9 ，1 2 3 和1 2 3 4 5 6 7 互素。如果说一个数是素数，那么他与自己倍数以外 的任何其他数都是互素的。 3 1 3 模运算 对任意整数a 和任意正整数n ，存在唯一的整数q 和r ，满足o r n ，并且 a - q + n + r ，值口一p 叫称为除法的商( 其中卜j 表示小于等于x 的最大整数) 。值r = a ( r o o d n ) 称为除法的余数，因此，对于任一整数，可表示为： 一1 5 一 a * a n j n + a m o c h 或者 a m o d , l - a 一 a n j n 给定一个整数n ，如果用n 去除两个整数a 和b 所得的余数相同，则称a 和b 关于 模l l 同余，即( a m o dn ) = ( b m o dn ) 可以记为a = b m o dr l m l 。 从0 到n - i 的整数组成的集合构成了模n 的完全剩余系，即0 到n - 1 都是某个数关 于n 的模的集合。运算a ( dn ) 表示a 被n 除的剩余，称为模n 运算。 模算术同普通的算术一样，是可交换的、可结合和可分配的。而且模r t 运算的每一 个中间结果与先进行全部运算再对最后结果取模n 的作用是一样的。 ( a + b ) ( m o dn ) = ( ( a m o dn ) + ( b r o o dn ) ) m o dn ； ( a - b ) ( r o o dn ) = ( ( a m o d1 1 ) 一( b r o o dn ) ) m o dn ； a b ( m o dn ) = ( a m o dn ) 幸( b r o o dn ) m o dn ； a ( b + c ) m o dn = ( ( a b ) m o dn ) + ( a c m o dn ) ) m o dn ； ( a 血o dn ) = ( b r o o dn ) 等价于a = b ( m o dn ) ； a = b ( dn ) 等价于b = a ( m o dn ) ： 若a = b 佃o dn ) 且b = c ( r o o dn ) ，则a = c ( m o dn ) ； 密码学中用了很多模n 运算，因为像计算离散对数和模n 平方根这样的问题是困难 的。模运算也很容易在计算机上实现，因为它将所有中间值和最后结果限制在一个范围 内。对一个k 比特的模n ，任何加、减或乘的中间结果都不会超过2 k 比特长。因此我们 可以用模算术作指数运算而又不会产生巨大的中间结果。 计算一个数的a 的x 方幂模n 为： 口。m o d n 只是一系列的乘法和除法。有方法可使其运算得更快。因为操作划分后，取幂可作为一 串乘法，并且每次都进行模运算，可使模幂运算加快。对一般的数，这与通常取幂没有 多大差别，但当用2 0 0 b i t 的数字进行操作时，情况就不同了。 一1 6 一 3 2 r s a 加密算法 r s a 算法是一种分组密码算法“鸡钉，它以数论中的欧拉定理为理论基础。对欧拉 定理的表述如下： 若整数g 和n 互素，则g - 1 ( r o o d n ) 其中m 0 ) 表示比n 小，但与n 互素的正整 数的个数，称为1 1 的欧拉函数。 要建立一个r s a 密码系统，首先任意选取两个大素数p 、q ，计算乘积：n = p * q ； 并得到欧拉函数： m o ) - o 一驰一1 ) ，其中o n ； ( 3 ) a = 2 8 9 = 1 9 。a n ；依次减得a = l o ，a = l ； ( 4 ) a n ，故得c = a = l ，即g = - a m o dn - l ； 本求模口m o d l 一口一 a n n 算法容易理解，也很简单，而且不会出现乘法功能部 件。因为乘法器在芯片中会占很大的面积，如果能少用乘法就会大减小芯片的面积。但 是此算法要完成一次求模所用的时序周期数目跟a 和n 的差值有关，当两者的差值很大 时会导致求模运算所耗的周期数很多，这就有可能当1 1 比a 小很多时，会淹没后面输入 的数，这样的话就有可能丢失部分后输入的数据。但如果程序相当长一段时间内输入一 组数据的话，就不会有数据丢失。 4 1 2 除法求模函数 除法求模函数实际上并没有用到除法，而是用移位和循环减法实现求模。算法如图 4 2 所示： 暖m 习 i和c 分别存i i 苎皇塑垒茎 i 图4 2 除法求余函数示意图 为实现g = m m o dn ，把m 放入r e g i s t e rm ，n 放在r e g i s t e rn ，r e g i s t e rc 初始化 为0 ，然后开始作1 1 次除法的步骤( n 是商的字长) 。n 次循环后，m 和c 分别存放商和余 数。 每个步骤将包涵： ( 1 ) 向左平移寄存器( c ，m ) 一个b i t ； 一2 l 一 ( 2 ) 寄存器c 减寄存器n ，并把结果再存回寄存器c ； ( 3 ) 如果c 是负的：则向左平移c 、m 这两个寄存器一个位，然后加n 到c ；如果 c 是正的：则向左平移c 、m 这两个储存器一个位，把c 减n 除法求模函数与连减法求模相比，算法的复杂性较高点，但其执行所用的周期时间 要短很多。 4 2 产生素数p ，q ，并求n 在r s a 体制描述中，要求p ，q 必须是素数，否则算法不成立。因此在第一步选取p ，q 的时候，必须判定它是不是素数。 产生n 根据修改的欧拉定理，如p 为素数，则对于x 的所有整数值，应满足： x 9 一一l m o d p 这是一个必要条件而非充分条件，不过，如果有5 个以上的x 值能满足上述条件，则p 可基本断定为素数。如果x 从l 5 之间变化时，均能满足上述条件，则p 为素数，否 则将p + l 。重复计算，直到获得素数为止。由此求得p 和q ，其乘积即为n ，而 西o ) 一o - a ) ( q 一1 ) 4 2 1 素数的素性检测 在公钥密码体制中，有效生成公钥参数是一个先决条件。索性检测就是判定一个整 数p 是否为素数。如果p 通过检测，则它可能就是素数，否则就肯定是合数( 非素数的 自然数就是合数) 令p 是个大的奇整数，假设想确定p 是否为素数，最简单的检测就 是“试除法”，即取奇整数皿，看m 是否能整除p 。如果l ，p 且不能被皿整除，则p 通过了m 的试除法检测。当m 跑遍了从3 开始到- 之问的所有奇数，而p 通过了所有 这些试除法检测，则p 肯定是素数。但显然这个检测p 是否为素数的方法十分耗时 在实际应用最多的素性检测是m i l l e r r a b i n 检测，也称为强伪索性检测“”。如果p 是一个奇素数，且令p 一1 一z x r ，其中r 是奇数，令a 是任意整数，满足g c d ( a ，p ) = l ， 一2 2 则或者以7 i m o d p ，或者口2 一l m o d p 对某个j ( o j s 一1 ) 。由此引入下面定义。 设p 一1 - z x f ，t 是奇数，b 与p 互素，- l m o d p 或存在r ( o r s ) ，使 6 砂1 m o d p ，则称p 是以b 为基的强伪素数。 例如，考虑合数p - - - 9 1 = 7 1 3 t 因为9 1 1 - - 9 0 2 * 4 5 ，s = l 且t = 4 5 ，因为9 - 1 r o o d 9 1 ， 故9 1 是以9 不基的强伪素数。 m i l l e r - r a b i n 素性检测算法： m i l l e r - r a b i n ( p ，t ) 输入：一个奇整数p 3 和安全参数t 1 ； 输出：p 是“合数”或“素数” ( 1 ) 记p - i = z r ，使得r 是奇数； ( 2 ) 对i 从l 到t ，执行： 选取随机整数a ( 2 a n 1 ) ； 计算y 一口7 m o d p a ：如果y 1 且y c p 一1 ，则完成下列步骤： j 1 ； 当j s 一1 且y p 一1 ，则计算y y m o d p ； 如果y = 1 ，则返回“合数” j - - j + l ： b ：如果y c p - 1 。则返回。合数” ( 3 ) 返回“素数” 4 3 用于求g c d ( a ，b ) 的算法一欧几里德最大公因子算法 欧几里德最大公因子( g r e a t e s tc o i i l m o r ld i v i s o r ，g c d ) 算法有两种形式。其中一种 一2 3 是关于整数的，另一种是关于多项式的。由于本论文里涉及整数的运算，没有关于多项 式的部分，故这里不对多项式的欧几里德最大公因子算法做阐述。 利用除法算法可以求出两个整数的g c d 。其中除法算法表述为：对任何整数c 和d ( d 为非零整数) ，存在惟一一对整数q ( 商) 和r ( 余数) 使得c = d q + r ，其中，o 1 r l l d l 。 整数欧几里德g c d 算法： 给定两个正整数s 和r 。它们的公因子能够利用除法算法，通过辗转方法计算出。 假定r o ，执行： 如果x 是奇数，则r ( - r x a m o dn ； a ( - a x a m o dn ； 。 x i x 2 i ； ( 3 ) 返回r 如果x 的长度是k 比特，这项技术可将操作数平均减少到1 5 k 次操作。但是用同一个 一2 7 n 做多次模幂运算最有效的算法是m o n t o g o m e r y 算法，另一个算法是b a r r e n t 算法。以 后我们将会对m o n t o g o m e r y 算法作相关的介绍。 4 6 2 动窗口求模幂法 输入：m ，n ，o m t 0 ，执行： 如果e t ：o ，则计算s & ，i i - l ； 否则( e l 0 ) ，寻找最长的比特串er e i - i e i 使得i - i + 1 k 且e l = 1 ，计算 s ( - s 2 i - 1 + 1 ( e i e h e 1 ) 2 ，i 1 - 1 ； ( 5 ) 返回s 4 6 3 从左到右的二进制模幂算法 模幂运算的基本形式为c = 矿m o d n ，其中e 表达为： e 。，e i e 。，e o 。m 是小于n 的整数，那么从左到右的指数扫描算法可描述如算法以下所示： 算法：模幂算法( l r ) m e l ( m e ，n ) 输入：n ( 模) ，e ( 幂) ，m ( 消息) ， ( c = l ； f o ri = l - it o0d o ( 指数是从高位向低位扫描) c - - c * c ( m o dn ) ； i f ( e i - 1 )c = m * c ( m o d n