（微电子学与固体电子学专业论文）高速rsa片上系统研究.pdf

j ： 目录 目录 iy$11111111118llllt1lll11llll7llli|,tllllll5lllly 18 117 1 5 摘要二h i a b s t r a c t 第一章引言 1 1 1 密码学概论l 1 1 1 信息安全与密码学1 1 1 2 密码学研究分类2 1 2 高速r s a 片上系统研究的意义4 1 3 本文内容及结构安排6 第二章r s a 密码算法和m o r g o m e r y 模乘算法8 2 1r s a 密码算法8 2 1 1r s a 算法简介8 2 1 2r s a 的安全性分析9 2 1 3r s a 模幂算法9 2 2m o n t g o m e r y 模乘算法1 1 2 2 1m o n t g o m e r y 算法1 1 2 2 2 高基可扩展m o m g o m e r y 算法1 2 第三章改进型r s a 密码算法和m o n t g o m e r y 模乘算法1 5 3 1 流水线型模幂算法1 5 3 2 流水线型m o n t g o m e r y 算法结构1 7 3 3p h sm o n t g o m e r y 模乘算法2 0 第四章高速m o n t g o m e l w 乘法器设计2 2 4 1 经典型可扩展m o n t g o m e r y 乘法器结构2 2 4 2 改进结构一：基为1 6 的m o n t g o m e r y 乘法器2 3 4 4 改进结构二：应用动态扩展技术的高效流水线调度方案2 7 4 3 改进结构三：p h sm o n t g o m e r y 乘法器。3 0 第五章高速可配置r s a 协处理器设计3 3 5 1 单模乘部件型r s a 协处理器3 3 5 2 双模乘部件型r s a 协处理器3 7 5 3 流水线型r s a 协处理器4 0 ：7 7 2 2g c o si i 简介5 8 7 - 2 3 采用多任务来处理多协处理器。6 0 第八章系统实现和分析6 6 8 1a s i c 设计：2 0 4 8 位长的高速r s a 密码芯片6 6 8 1 1a s i c 设计流程6 6 8 1 22 0 4 8 位长的r s a 密码芯片6 7 8 2f p g a 设计：1 0 2 4 位长的高速r s a 多核系统7 0 8 2 1 基于s o p c 的f p g a 设计流程7 0 8 2 11 0 2 4 位长的r s a 密码系统7 3 总结与展望。7 7 参考文献7 8 硕士学习期间录用和发表的学术论文。 8 1 j 致谢8 2 ：j 7 7 盎 摘要 摘要 互联网的快速发展使得信息安全技术显得尤为重要，诸如在线购物、网上银 行、数据下载等方面都需要一套身份认证系统。信息安全主要是利用密码技术来 保证信息的保密性、完整性、可用性和抗抵赖性，密码技术，特别是公钥制密码 技术的芯片实现，代表着信息安全领域的技术水平。在公钥制密码体制中，应用 最为广泛的是r s a 密码算法，r s a 密码算法简单有效，但是却非常耗时，其主 要运算过程是模幂运算，密钥长度越长，安全等级越高，同时计算量也越大，速 度就越慢。 本文针对如何实现一个高速的r s a 片上系统进行研究。分别在算法层次、 硬件结构层次、系统架构层次和系统软件层次上进行探讨。在算法层次上，本文 分析了r s a 的密码算法和m o n t g o m e r y 模乘算法，并在此基础上提出了流水线 型模幂算法、流水线结构m o n t g o m e r y 模乘算法和p h sm o n t g o m e r y 模乘算法， 这些新算法在提高r s a 加解密速度上都具有很好的效果；在硬件结构层次上， 本文在研究经典型高基可扩展m o n t g o m e r y 模乘器基础上提出了三种 m o n t g o m e r y 模乘器的改进方案，同时还提出了三种r s a 协处理器的实现方案； 在系统架构层次上，本文分析比较了总线型、片上网络型和流水线型的系统结构， 根据r s a 运算的特点提出了三种多处理器r s a 片上系统架构；在系统软件层次， 本文分别给出了多协处理器系统和单协处理器系统的软件解决方案，并分析比较 了目前主流的嵌入式操作系统，最终详细介绍了基于开源嵌入式操作系统一 g c o s 的r s a 片上多核系统软件解决方案。 最后，本文分别采用a s i c 和f p g a 进行系统实现。在a s i c 上实现了2 0 4 8 位长的r s a 密码处理器，在算法层次和硬件结构层次验证了本文提出的高速 r s a 片上系统；在f p g a 上实现了1 0 2 4 位高速r s a 片上系统，在系统架构层 次和系统软件层次验证了本文提出的设计思想。 关键词：r s a 、高速、s o c 、可配置、可扩展、m o n t g o m e r y 、信息安全 中图分类号：t p 3 0 9 7 ? ， 一一 a b s t r a c t ： a bs t r a c t i n f o r m a t i o ns e c u r i t yi sb e c o m i n gm o r ea n dm o r ei m p o r t a n t 、析也t h ei n c r e a s i n g p o p u l a r i t yo fe l e c t r o n i cc o m m u n i c a t i o n n sn e e do fa ni n f o r m a t i o ns e c u r es e r v i c e s y s t e mu s e di no n l i n eb u s i n e s s ，e - b a n ka n dd a t ad o w n l o a d i n g t h ec o r et e c h n o l o g y u s e df o ri n f o r m a t i o np r o t e c t i o ni sc r y p t o g r a p h y p u b l i c k e yc r y p t o s y s t e mc a l lp r o v i d e c o n f i d e n t i a l i t y , a u t h e n t i c a t i o n , d a t ai n t e g r i t y a n dn o n - r e p u d i a t i o n a m o n gt h e p u b l i c k e yc r y p t o g r a p h i ca l g o r i t h m s ，r s aa l g o r i t h mi st h es i m p l e s tb u tw i d e l yu s e d h o w e v e r , r s aa l g o r i t h mi st i m e - c o n s u m i n g t h ep e r f o r m a n c eo fr s ac r y p t o s y s t e m i sm a i n l yd e t e r m i n e db yt h ei m p l e m e n t a t i o ne f f i c i e n c yo ft h em o d u l a re x p o n e n t i a t i o n a st h eo p e r a n d sb e c o m el o n g e r , t h es p e e do ft h ee n c r y p t i o n d e c r y p t i o nb e c o m e s s l o w e r ， i nt h i st h e s i s ，i td i s c u s s e dt h ei m p l e m e n t a t i o no fah i g h - s p e e dr s as y s t e mo n c h i pf r o mt h ea s p e c to fa l g o r i t h ml e v e l ，h a r d w a r el e v e l ，s y s t e ml e v e la n ds o f t w a r e l e v e l i na l g o r i t h ml e v e l ，t h r o u g ha n a l y s i n gt h eo r i g i n a lr s aa l g o r i t h ma n dh i g h - r a d i x s c a l a b l em o n t g o m e r ya l g o r i t h m ，t h r e en e wa l g o r i t h m sa r ep r o p o s e d ：p i p e l i n e d m o d u l a re x p o n e n t i a t i o na l g o r i t h m ，p i p e l i n e dm o n t g o m e r ya l g o r i t h ma n dp h s m o n t g o m e r ya l g o r i t h m t h e s e t h r e e a l g o r i t h m s a c c e l e r a t et h e s p e e d o fr s a e x e c u t i o n i nh a r d w a r el e v e l ，i tp r o p o s e dt h r e em e t h o d st oo p t i m i z et h em o n t g o m e r y m u l t i p l i e ra n dt h r e em e t h o d st oi m p l e m e n tt h er s ac o p r o c e s s o r i ns y s t e ml e v e l ， t h r o u g ha n a l y s i n gt h e b u s b a s e d s y s t e m a n d n e t w o r k - o n c h i p - b a s e ds y s t e m ，i t p r o p o s e dt h r e ea r c h i t e c t u r e st oi m p l e m e n tm u l t i - c o r er s a s o cc h i p i ns o f t w a r e l e v e l ，i tp r o v i d e dt h es o l u t i o nf o rs i n g l e - c o p r o c e s s o rs y s t e ma n dm u l t i - c o p r o c e s s o r s y s t e m m o r e o v e r , i td i s c u s s e ds e v e r a ll e a d i n ge m b e d e do p e r a t i o ns y s t e m a n d p r o p s e dt h es o f t w a r es o l u t i o nb a s e dt h eo p e n s o u r c eo p e r a t i o ns y s t e m ( i c o s ) f o r m u l t i c o r er s as o c s y s t e m a tl a s t ，t h eh i g h - s p e e dr s as y s t e mi s i m p l e m e n t e di na s i ca n df p g a a 2 0 4 8 一b i tr s a c o p r o c e s s o ri si m p l e m e n t e db ya s i c ，i tv e r i f i e dt h ec o r r e c t n e s sa n d e f f i c i e n c yo ft h ea l g o r i t h m sa n dh a r d w a r es t r u c t u r e s a 10 2 4 - b i th i g h s p e e dr s a s y s t e m i s i m p l e m e n t e db yf p g a ，t h es y s t e m s o l u t i o na n ds o f t w a r es o l u t i o ni s v e r i f i e d k e yw o r d s ：r s a ，h i g h - s p e e d ，s o c ，r e c o n f i g u r a b l e ，s c a l a b l e ，m o n t g o m e r y , i n f o r m a t i o ns e c u r i t y ：， 第一章引言 第一章引言 【本章简介】本章首先阐述密码学的基本概念，介绍了密码学在信息安全领域的 作用，同时还介绍了密码学的最主要的两个分支：对称密钥密码学和公钥密码学； 其次，介绍了高速r s a 密码系统研究的重要t g ；最后，简要介绍了本文的内容 和结构安排。 1 1 密码学概论 一直以来，人类对保护信息以不被他人所知抱有强烈的兴趣，作为保护信息 最强力的手段一密码学发展至今已经有几千年的历史。早期的密码学研究密写和 非法解密问题，电报发明以后，商业方面对密码学的兴趣主要集中在密码本的编 制上，到2 0 世纪初集中在与机械运动和电动机械加密机的设计和制造上。信息 技术的发展迅速改变了这一切，随着计算机和通信技术的迅猛发展，大量敏感信 息要通过公共通信设施或计算机网络进行交换。i n t e m e t 的广泛应用大大促进了 电子商务和电子政务。大量的个人信息，比如信用卡号、银行帐号密码等都需要 保护以防止泄漏给他人造成经济损失。密码学的应用已经不仅仅局限于政治、军 事、外交等领域，它的商业和社会价值日益显著，与人们的日常生活愈加密切相 关。 密码学领域实际上已经被当作应用数学和计算机科学的一个分支。数学理论 在当前的密码学研究中发挥着重要的作用，其中包括数论、群论、组合逻辑、复 杂性理论、遍历理论以及信息论。对于计算机科学家而言，密码学与操作系统、 数据库、计算机网络联系非常紧密；而对于芯片设计者来说，密码学与并行计算、 计算机体系架构、数据通路微结构等都是密切联系的，密码学的理论和技术已经 得到了迅速的发展【i j 。 1 1 1 信息安全与密码学【2 】 对于一个通信系统而言，基本的通信方案如图1 1 所示， - 焉艘s 兀 j 0 a h e e 矽 图1 1 非安全的通信 暨 基 融 ， 第一章引言 它包括两个当事人a l i c e 和b o b ，彼此要进行通信，第三方e v e 是一个可能 的窃听者。当a l i c e 通过一个非保密的信道要发送一个消息给b o b 时，很显然作 为窃听者的e v e 是很容易就可以截获信道中的信息，从而知道a l i c e 发送给b o b 的消息的。 为了确保通信的保密性，a l i c e 和b o b 可以通过以下几个基本的安全步骤来 实现保密通信： 用户认证：a l i c e 和b o b 必须首先验证对方是否是合法，使得e v e 无 法冒充任何一方。 密钥协商：当a l i c e 和b o b 互相都验证了对方的身份后，他们之间需 要建立一种仅仅他们两人之间共享的而e v e 无法得到的秘密信息，该秘密信 息可以用来构建私钥。 数据加密解密：当私钥建立了之后，a l i c e 和b o b 就可以通过这个 私钥运用某种加密算法来加密他们的通信内容了，这个时候即使e v e 可以完 全截获通信信道中的信息，也无法获知a l i c e 和b o b 之间的通信内容，因为 她不知道密钥信息。 数据完整性检查及数字签名：a l i c e 和b o b 希望能够确保他们接收到 的数据和对方发送过来的数据是完全一样未被窜改过的，同时他们也都希望 能够知道他们接受到的数据确实是对方发送过来的，而不是e v e 假冒的数据。 这样，一个安全的通信方案如图1 2 所示： 图1 2 安全的通信 可见，通过采用密码技术，可以在a l i c e 和b o b 之间构建一个安全的通信环 境，使得窃听者e v e 无从获知a l i c e 和b o b 之间的通信内容。 1 1 2 密码学研究分类 根据密码学研究内容的不同可以将密码学研究分为两大类：对称密钥密码学 和公钥密码学【1 ，3 4 ，5 ，6 1 。 2 协 第一章引言 对称密钥密码学 对称密钥加密是指密码方案中，从加密密钥很容易计算出解密密钥( 或反过 来从解密密钥很容易计算出加密密钥) 。加密和解密经由复杂的非线性变换实现， 对称密钥加密技术包括分组密码和流密码。 a 分组密码 分组密码体制一直是密码学的研究热点，当前的分组密码广泛用在数据的加 密传输和存储加密上。分组密码是在定长的块上进行替代操作、换位操作或他们 的合成( 乘积加密) 。所谓的替代操作是将明文中的一个字母用密文字母表中的 其他字母替代。而换位是一块中的字母简单的置换。分组密码在许多的密码系统 中都是最重要的组成部分，用分组密码能够实现保密性，作为基本的部件，它可 以用在许多方面，如：构造伪随机数生成器、流密码、认证码和h a s h 函数。更 进一步讲，分组密码在消息认证技术、数据完整性机制、实体认证协议以及数字 签名方案中也可以作为核心部件。 d e s ( d a t ae n c r y p t i o ns t a n d a r d ) 算法是最为广泛使用的一种分组密码算法。 1 9 7 2 年美国商业部所属的美国国家标准局( n b s ) 开始实施计算机数据保护标 准的开发计划，1 9 7 5 年3 月首次公布d e s 算法的描述，1 9 7 7 年正式批准为无密 级应用的加密标准( f i p s 4 6 ) 。d e s 对推动密码理论的发展和应用起到了重大作 用。 a e s ( a d v a n c e de n c r y p t i o ns t a n d a r d ) 是美国最新的加密标准。美国国家标准 和技术协会n i s t 从1 9 9 7 年开始征集和评估新的数据加密标准a e s ，其目标是 在新的世纪保护敏感信息的安全。1 9 9 8 年n i s t 发布1 5 个a e s 的候选算法，一 年之后从中挑选出5 个算法进入新一轮的评估。2 0 0 0 年1 0 月宣布r i j n d a e l 算法 为a e s 的最终算法。2 0 0 1 年n i s t 正式宣布a e s 成为美国政府新的加密标准以 取代1 9 7 7 年开始使用至今的d e s 。 b流密码 目前流密码是各国军事和外交领域使用的主要密码体制。流密码也可以看成 是块长度为l 的分组密码。它是重要的一类对称密钥密码方案，即加密变换只改 变一位明文。在出现传输错误的情况下，使用流加密不会产生错误传播。因为每 次只加密一位，所以可以在没有存储器或数据缓冲区较小的情况下使用。 流加密的加密变换相对简单一些，比如2 0 世纪2 0 年代的v e m a m 密码就是 一次一密的密码体制。令明文m = m ，m 2 m 3 m 厅，密钥k = - k ，心岛，则密文 c = c ，c 2 c 3 c n ，其中c i = m fo 岛，j 何向。这里的重要问题是使生成的密码流周期 长、复杂度高、随机性足够好，使之尽可能接近一次一密的密码体制。由于有限 的算法不能够产生真正的随机序列，所以一般都是基于伪随机序列的流密码，例 如线性移位寄存器的非线性组合。 如果生成的密钥流独立于消息流，传输过程中丢失了一个密文位，那么通信 双方在进一步传送之前必须将他们的密钥生成器重新同步。这种流密码称双同步 ， a ： 第一章引言 流密码。而在自同步流密码中，密钥流的一位是前面全部消息流的函数，那么传 输的一位错误( 丢失或改变) 会向前传播数位，其后密码又能自行同步。实用中 往往要求恢复丢失或破坏的一些位，这时就要重新传输。用于启动和终止连接以 及同步密钥流需要经由通信协议完成。 公钥密码学 公钥密码学是现代密码学中最重要的研究内容之一。密码学研究包括两个方 面，其一是保护信息传递的机密性；其二是对信息发送人的身份认证以及信息的 完整性的检验。公钥密码很好地解决了这两个方面的问题，并正在产生许多新的 思想和方案。而对称密钥密码用于加密和解密的密钥是相同的，虽然算法比较简 便、高效、密钥短、安全性高，但是传送和保管密钥是一个严峻的问题。 公钥密码的观点由d i f f i e 和h e l l m a n 于1 9 7 6 年在他们的论文“密码学的新 方向”一文中首次提出的，它使密码学发生了一场变革。d i 衔e 和h e l l m a n 为解 决密钥管理问题提出了一种密钥交换协议，允许在不安全的信道上通信双方交换 信息，安全地达成一致的密钥。在此新思想的基础上，很快出现了公钥密码。在 公钥密码中，加密密钥不同于解密密钥，加密密钥公之于众，谁都可以使用。解 密密钥只有解密人自己知道，分别称为公开密钥( 公钥) 和秘密密钥( 私钥) 。 在至今为止的所有公钥密码中，最著名的是由r r i v e s t ，a s h a m i r 和l a d l e m a n 三位教授于1 9 7 7 年提出的r s a 。r s a 之所以具有安全性，是基于数论中的一个 事实：将两个大的素数合成一个大数很容易，而相反过程则非常困难。由此可见， r s a 的安全性依赖于作为公钥的大数n 的位数长度。虽然2 0 世纪8 0 年代关于 大整数素因子分解方法有很大进展，但是人们仍然认为r s a 是安全的。1 9 8 5 年 又出现了一个基于离散对数问题的e i g a m a l 公钥加密方案。 公钥密码与传统密码相比，有其不可取代的优势。然而它的运算量却非常浩 大。因此，网络上全都使用公钥密码来传送机密数据是不现实的。最好的解决方 案是使用某种传统的密码算法( 比如a e s ) 来加密传输机要信息，而同时使用 r s a 等公钥密码来传送a e s 的密钥。这样就可以综合发挥两种密码的优势，即 a e s 高速、简便性和r s a 密钥管理的方便、安全性。 1 2 高速r s a 片上系统研究的意义 r s a 是一种安全性很高的公钥制密码算法，也是目前应用最为广泛的公钥 制密码算法。当前，r s a 密码算法在具体的应用中主要受到来自以下两个方面 的限制： 1 算法角度：运算复杂度高 r s a 的安全性是基于大整数分解的难题，所以为了保证其安全性，有必要 采用很高位数的密钥。但是，随着密钥位数的提高，同时也带来了运算复杂度的 提高，通过分析r s a 密码算法可以知道，其运算复杂度是和密钥长度呈指数关 4 口 鼬 第一章引言 系增长的。另一方面，r s a 密码算法本身就是求幂取模的过程。从数学角度上 看，求幂取模的过程本身计算量就非常浩大。 2 应用角度： a ) 软件加解密方案虽然灵活性很高，但是无法满足系统实时性和安全性的 需求。 目前的r s a 密码方案还是以软件加解密为主，软件加解密的优点是灵活性 高，无需额外的硬件资源，节省成本。但是，软件加解密具有两大缺点：第一， 对于强调安全性的应用来说，软件解决方案会导致很多的安全漏洞，这些漏洞容 易被别人攻破；第二，对于强调实时性的系统来说，因为r s a 算法自身的复杂 性和处理器硬件资源的通用型，导致软件r s a 加解密运算的速度无法达到实时 性的需求。 b ) 一般的硬件加解密方案虽然在安全性上有所提高，但是无法满足灵活性 的需求，同时也无法满足实时性的需求。 采用专用的加解密硬件来实现安全系统能够提高系统的安全性，使得大部分 的恶意攻击能够得到防护。但是，一般的硬件加解密都是采用外围集成专用的密 码芯片，这样一来使得系统很大程度上依赖于芯片的功能多样性，如果芯片功能 比较单一，则顶层系统设计的灵活性就大大降低。并且，当系统需要升级和更新 换代时，这些专用模块往往不能实现同步升级，需要采用新的模块以代替原有的 模块，这样一来使得成本大幅度提升。 在另一方面，专用的密码芯片根据不同的应用场合也分为不同的性能等级， 低速率的密码芯片适用于客户端产品，高速率的密码芯片适用于服务器端产品。 所以，在有些强调实时性的安全系统中，即使采用了密码芯片也无法满足系统实 时性的需求。对于芯片来说，速度越高，其中所包含的技术含量也就越高，价格 也就越贵，并且一些高速率、高性能的芯片都是受到贸易限制的，尤其是能够用 于军事用途的产品，更是各国限制出口的对象。 基于以上两个现状，高速r s a 片上系统研究的意义体现在： 1 满足来自对r s a 加解密速度的需求。 高速r s a 片上系统可以采用专用的加解密硬件来完成运算，这些硬件都是 针对r s a 加解密运算的特点而优化设计的，它可以在速度、功耗、吞吐率等等 方面加以优化，使得r s a 加解密运算可以达到很高的速度和效率。而这种对速 度的需求是非常迫切的，一方面，有来自于商业应用需求：比如银行系统、c a 中心等，它们都有着及其庞大的数据需要进行加解密处理：另一方面，有来自于 普通的消费者：随着对安全性需求的提升，在各种电子产品中集成安全模块变得 越来越普遍，r s a 作为最主流的密码算法势必会进入到每个人的日常生活领域， 而注重实时性和可靠性的电子产品就会对高速的r s a 片上系统有需求。 c ，f 1 全 第一章引言 2 满足来自对r s a 加解密安全性的需求。 安全性的需求是r s a 应用的重中之重，这也是软件加解密的最大隐患，通 过采用硬件芯片来实现r s a 加解密运算，可以从根本上杜绝安全漏洞，大大提 高各个应用系统的安全性。同时，若攻击者想从硬件上对r s a 进行攻击，其付 出的成本是非常高的，攻破的可能性也很渺茫。所以，硬件实现r s a 也是未来 的一大趋势。 3 满足来自对安全系统设计灵活性的需求。 高速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 片上系统的优势是，它结合了软件 r s a 密码方案和硬件r s a 密码方案的双重优点，既通过采用系统软件方式提高 了芯片功能的灵活性、兼容性和可升级性，同时也通过采用硬件方式提高了系统 的实时性和安全性。 综上所述，高速r s a 片上系统研究是一项既有理论价值也有实际意义的研 究，它对提高我国在信息安全领域的地位，保护国家重要的信息资源、提升在密 码芯片领域的国际竞争力都有非常重大的意义。 1 3 本文内容及结构安排 本文的主要目标是提出一整套的高速r s a 片上密码系统的解决方案。这些方 案以以下四个部分为主线贯穿全文： 算法层次解决方案 硬件结构层次解决方案 系统架构层次解决方案 系统软件层次解决方案 本文根据以上四个部分的顺序，在各个层次分别展开讨论，并在各个层次中 都提出了多种解决方案和改进方案。本文不局限于设计实现某一个具体的r s a 密码系统，而是在系统设计的方法、原理及各种改进措施上展开笔墨，提供了更 为丰富的系统设计方案。 6 二l 第一章引言 下面简单介绍一下各个章节的主要内容： 第二章主要介绍r s a 密码算法和m o n t g o m e r y 模乘算法。分别介绍了r l 和 l r 型的r s a 模幂算法和m o n t g o m e r y 原始算法及其改进算法。 第三章主要介绍改进型的r s a 密码算法和m o n t g o m e r y 模乘算法。其中，对 r s a 密码算法的改进是采用流水线的模幂算法来提高r s a 模幂运算的速度和可 配置性；对m o n t g o m e r y 模乘算法的改进采用了两种方案，一种是采用流水线技 术提高可配置性、可扩展性和运算速度；另一种是提出了p h sm o n t g o m e r y 模乘 算法，它采用操作数预扩展技术来解决关键路径问题，使得系统时钟频率得到提 升。 第四章主要介绍m o n t g o m e r y 乘法器的硬件设计。首先，回顾了t e n c a t o d o r o v k 0 9 的硬件设计；其次，提出了三种m o n t g o m e r y 乘法器的改进结构。改进结构 一针对采用更高基值的m o n t g o m e r y 乘法器设计，改进结构二是采用操作数动态 扩展技术以改进流水线运行性能，改进结构三针对的是采用p h sm o n t g o m e r y 算 法的硬件设计。 第五章主要介绍r s a 协处理器的设计。分别提出了三种协处理器设计方案： 单模乘部件型方案、双模乘部件型方案和流水线型方案。其中的单模乘部件型方 案根据采用的算法不同，还有两种实现模式。 第六章主要介绍高速r s a 的片上系统结构。提出了三种片上系统解决方案， 分别是基于片上总线型的设计、基于片上网络型的设计和基于流水线型的设计。 第七章主要介绍软件设计方案。提出了两种软件设计方案：针对单核系统的 单进程软件设计方案和针对多核系统的多进程软件设计方案。并在多进程方案 中，介绍了几种常用的嵌入式操作系统，最后详细介绍了基于开源内核t c o si i 的软件设计方案。 第八章主要介绍了两个具体的系统实现。一个是采用a s i c 实现的2 0 4 8 位 长的r s a 密码芯片，它验证了算法和硬件设计的正确性；另一个是采用f p g a 实现的1 0 2 4 位长的r s a 密码系统，它验证了系统设计和软件设计的正确性。 7 以 c | 掣 2 1r s a 密码算法 r s a 是目前使用最为广泛的公钥密码系统，它由r i v e s t ，s h a m i r 和a d l e m a n 首次于1 9 7 7 年提出，它的安全基于大整数素因子分解的困难性上【刀。 2 1 1r s a 算法简介 假设通信各方( a l i c e 和b o b ) 都有自己的公钥( e ，m ) 及私钥( p 、q 、d ) ， 其中p 、q 是两个大的素数，m 2 p x g ，p d 兰1 m o d 缈( 刀) ，其中伊( 刀) 为欧拉函 数9 ( 以) = ( p 一1 ) x ( q 1 ) 。显然，p 应该满足g c d ( p ，p ( 刀) ) = 1 。b o b 加密消息p ，将 密文在公共信道上传送给a l i c e ，a l i c e 接收到密文后对其解密【4 】。 具体的算法如下： 加密算法： b o b 做如下操作： 1 得到a l i c e 的公钥( m ，e ) ； 2 把消息表示成整数p ，0 p 玎一1 ； 3 使用模幂算法，计算c = p 。m o dm ； 4 将密文c 发送给a l i c e 。 解密算法： a l i c e 做如下操作： l 得到b o b 发送过来的密文c ； 2 使用自己的私钥( m ，d ) ，计算p = c 4m o d m 3 得到密文c 的原文p 。 ：, x ；j s m z 。，有色( 丘( 聊) ) = 柳做个简要的证明：首先证明聊耐- - - m m o d p 。 8 ；， a 嘞 第二章r s a 密码算法和m o n t g o m e r y 模乘算法 对pl 聊，显然有聊p l m 量0 m o d p 。当g c d ( m ，p ) = 1 时，由f e r m a t 定理知， 聊p - l m o d p ，从而有m d - m ( 朋p - i ) 9 。1 - - - m m o d p ，同理可以推出 m 鲥兰m m o d q 。最后得到m 副三m r o o d m 。 密钥生成 a l i c e 和b o b 在通信之前都需要事先生成一对密钥，r s a 的公钥和私钥生成 方法如下： 1 生成两个大的随机素数p 和q ，p q 并且它们的位长大体相同； 2 计算i = p q ，妒( 胛) = ( p - 1 ) ( q - 1 ) ； 3 选择随机数e ，0 e = mt e ns ：= s m 7 1e n d 礤 x 是乘数，y 是被乘数，m 是模数，r 是一个等于2 n 的常数，x 、y 、m 都 ： 一 第二章r s a 密码算法和m o n t g o m e r y 模乘算法 是位长为n 的整数。如算法所示，首先对s 置零，然后按位逐次扫描x j 并将其 乘上y 后加到s 上，通过判断s o 的位来决定是否要加m ( 因为s 需要通过右移 来除以2 ，需要将s o 位变成0 ，而m 是奇数，最低位肯定是1 。若s o 位是1 ，加 上m 后就变为0 ) ，然后右移一位。依次循环，直到所有的x 位都被扫描完毕。 最后判断s 是不是大于m ，若大于则减去一个m ，最后的结果是x y r - 1 m o d m 。 m o n t g o m e r y 算法采用一系列的移位运算来替代除法，最终的运算结果是 x y f lr o o dm 而不是真正的模乘运算结果：x yr o o dm 。为了实现模乘运算，需要 对初始输入数据进行域转换。m o n t g o m e r y 模乘运算使用一种称为m 域的表示形 式来表示整数。比如，将x ( o _ 叫姒- 。 _ 一 炒t 。少 t o t a lt 掉s t a g e s t a g e s s t a g es t 一1 图3 1 流水线模幂算法 3 2 流水线型m o n t g o m e r y 算法结构 c 算法2 4 提出了一种很好的高基可扩展m o n t g o m e r y 算法，为了达到可扩展 的目的，采用了按字运算的方法来实现，即每个节拍读入操作数的一个字，通过 多个节拍来读取整个操作数，这样做的好处是可以设计出一个固定长度的运算部 件来实现无限长度的模乘运算。但是，如果仅仅采用一个运算部件