（微电子学与固体电子学专业论文）rsa公钥密码体制的硬件实现.pdf

摘要 随着数字化信息技术的发展，有线数字电视逐渐走入我们日常生活。作 为一种方兴未艾的新兴产业，其发展前景是不可限量的。为了确保数字电视 新业务的实现，一个安全可控的综合管理业务平台就尤为重要，其中最重要 的组成部分之一就是条件接收系统。在蓉件接收系统中，控制字的安全传输 具有很重要的意义。本文针对以上的问题，对公钥密码体制及该体制中目前 最广泛流行的r s a 算法进行深入研究，并且分析了算法的多种实现方式， 如二元算法，s m m 算法，改进s m m 算法以及m o n t g o m e r y 算法。针对于 这些算法在实现过程中存在的不足，本文基于不同的设计理念，提出了改进 m o n t g o m e r y 算法和基于面积优化的算法，克服了算法效率低下和消耗电路 面积大的问题，更有利于硬件的实现。 本文中改进的m o n t g o m e r y 算法把对任意数的取模运算转化为对特定 数月的取模运算。根据算法本身性质并结合二元算法，只需进行一次预处 理和调整运算，大大提高了算法效率。基于面积优化的算法是把大数模乘运 算转换成加，减运算和比较运算，避免了预处理和调整阶段电路以及1 0 2 4 位 乘法器的应用。此算法具有硬件实现开销小的特点。本文对以上两种算法都 进行了硬件电路设计，完成了功能仿真和电路综合。本文设计的r s a 硬件 电路，达到了国微技术有限公司的设计要求，已经应用于p o d 系统中。 关键词条件接收系统；公钥密码体制；r s a 矍玺堡三些奎兰三兰堡圭耋堡丝兰 1 1 课题背景 第1 章绪论 随着高速互联网接入、电视会议、可视电话、数字交互电视这些崭新业务 的出现，有线电视网络迎来了新的一轮产业机遇。数字电视作为其中最先得到 应用的业务，目前正在全世界范围内迅速普及，而由数字电视衍生出来的增值 业务，如视频点播( v o d ) 、按次付费( p p v ) 、软件下载、网络游戏、信息点 播( i o d ) 、数据广播等应用呈现出迅猛的增长趋势。对有线宽带网络运营商 来说，这些新业务无疑是新的利益增长点，但是为了确保这些新业务的实现， 一个安全可控的综合管理业务平台就尤为重要，其中最重要的组成部分之一就 是条件接收系统【“。 条件接收系统涉及到信息安全工程学和密码学领域，包括三大要素：一是 对信息安全需求的分析与定义，也就是通过系统分析，明确信息安全受到何种 可能的威胁和所需防范的内容；第二是信息安全的策略，即采用怎样的安全协 议来保障信息的安全传输和存储；第三是具体实施信息安全的工具。所以说， 密码技术就是保障信息安全最重要的工具。 密码技术1 2 j 是集数学、计算机科学、电子与通信等诸多学科于一身的交叉 学科。它不仅能够保证机密性信息的加密，而且能够实现数字签名、身份验 证、系统安全等功能。是现代化发展的重要科学之一。本文将对公钥密码体制 及该体制中目前最广泛流行的r s a 口】算法进行分析，并且基于不同的设计理念 实现该算法的硬件电路。 本课题来源于深圳国微技术有限公司，对于数字电视条件接收系统中控制 字的传输安全性和实用性的要求，本文选用r s a 公钥密码体制，并最终基于 不同的设计思想，实现两种不同的硬件电路，均达到了深圳国微技术有限公司 的设计指标。现在此硬件模块应用到公司p o d 项目中。 堕至鋈三兰奎耋三兰鎏圭兰堡鎏兰 1 2 数字电视条件接收系统的发展状况 1 2 1 条件接收系统介绍 数字电视条件接收系统是一个综台性系统，系统涉及到多种技术，包括加 解密技术、加解扰技术、编码技术、复用技术、智能卡技术、网络技术、接收 技术，此外还涉及到用户管理、节目管理、收费管理等信息管理技术。条件接 收是数字电视加密控制的核心技术保证，为数字电视的运营提供了必要的技术 手段，使拥有授权的用户合法的使用某一项业务，而未经授权的用户不能使用 这一业务。条件接收系统是基于m p e g 2 和d v b 标准开发设计的，并符合广 电总局制定的数字电视广播条件接收系统规范。 数字视频广播标准d v b l 4 】( d i g i t a lv i d e ob r o a d c a s t ) 是数字电视的通用国 际标准，d v b 标准以m p e g 一2 编码系统为基础，用m p e g ，2 数据包结构作为数 据容器，并使用严格的d v b 服务信息格式，有效地、方便地实现了多种媒体之 间的传输，并实现它们之间的数字信号转换。应用领域涉及到卫星传输、电缆 传输、地面传输。 d v b 有两种加扰方式，即周密1 5 】( s i m u i c r y p t ) 和多密1 6 】( m u l t i c r y p t ) 。 同密要求前端可以使用多个c a 系统，每个c a 系统可以使用不同的加密系统加 密各自的相关信息，但对节目内容的加扰必须采用同一个加扰算法和加扰控制 字，这样可以保证接收端使用不同的接收设备而同时又能接收相同的数字电视 节目，使用周密技术后，可以方便多级运营商的管理，为多级运营商选择条 牛 接收系统提供了灵活性。而多密技术主要是针对接收端而言的，用户可以采用 多密的方式接收不同的加扰加密系统所加密的不同的节目。由于d v b 中的同 密与多密都规定了标准接口，从而方便了多个c a 系统的集成，也方便了用 户， 目前在国际上占主流的有欧洲的d v b 标准、北美国家的a t s c 标准及日 本的i s d b 标准。在这三种标准中对于c a 部分都作了简单的规定，并提出了 三种不同的加扰方式。欧洲d v b 组织提出了一种称之为通用加扰算法 ( c o m m o ns c r 鲰b l i n ga l g o r i t h m ) 的加扰方式，由d v b 组织的四家成员公司 授权，a t s c 组织使用了通用的三迭d e s 算法，而日本使用了松下公司提出的 一种加扰算法。 矍玺鋈三些奎兰三兰耋圭耋竺鎏兰 1 2 2 条件接收系统内容 1 ，22 1 条件接收系统原理下文介绍一下条件接收系统的原理。 在讲述原理之前，先了解两个在c a 设备中容易混淆的概念：一个是加解 扰( s c r a m b l i n g - d e s c f a m b l i n g ) ，另一个是加解密( e n c r y p t i o n d e c i y p t o n ) 。加 解扰技术被用来在发送端c a 系统的控制下改变或控制被传送的服务( 节目) 的某些特征，使未被授权的用户无法获取该服务提供的利益；而加密技术被用 来在发送端提供一个加密信息，使被授权的用户端解扰器能以此来对数据解 密，该信息受c a 系统控制，并以加密形式配置在传输流信息中以防止非授权 用户直接利用该信息进行解扰，不同的c a 系统管理和传送该信息的方法有很 大不同。 简单地说就是：加扰是通过控制字口1 ( cw c o n t m lw o r d ) 对传输流进行按 位加密的过程，而加密部分实际完成对控制字的保护。这两种技术是c a 系统 重要的缀成部分，在技术上有相似之处，但在c a 系统标准中是独立性很强的 两个部分。在目前各标准组织提出的条件接收标准中，加扰部分往往力求统 一，而在加密部分则一般不作具体规定，是由各厂商定义的部分。 境簟簟胃 童囊节- 鬟蠢耋 张卡 图l - 1c a 系统整体框架结构 f i g 1 - 11 1 1 e 鲫幽i l e c t u r eo f w h o l ec as y s t e m 条件接收的核心是控制字c w 传输的控制。在采用m p e g 2 标准的数字电 视系统中，与节目流条件接收系统相关的有两个数据流：授权控制信息 e c m ( e m m ec o n 呐lm e s s a g e ) 和授权管理信息e m m 【9 l ( e n t i t l em 扑a g e m e s s a g c ) 。由业务密钥s k ( s e r v i c ek e y ) 加密处理后的c w 在e c m 中传送， 节目即时购买( i p p v ) ：不同的节日号及价格，按次记费方式。i p p v 数据 可经电话或电缆回传。即时购买的节目是最灵活的收看方式，节目提供商可以 为每个即时购买的节目定好收看的费用，预览时间长度 以控制字计) 。节目 播出时用户可以收看一段预览节目，预览结束后会在屏幕上显示该节目的价 钱，并询问用户是否购买收看该节目。如果用户选择购买，并输入正确的用户 密码，就完成了节目的购买，而无需提前打电话预定节目。 以上的三种基本形式实际上可以将节目流进行任意定制组台，为不同爱好 的观众提供最适合其特点的个性化的服务。 ( 2 ) 实现地区的阻塞节目提供商可以通过使用地区阻塞，禁止指定地区 内的用户收看节目，尽管他们有授权，这种方式是地区阻塞。一般情况下，地 区是基于智能卡所有者所在的地理位置来划分的，智能卡中的每个密钥集都有 自己的g c a ，用来指明地理位置。 ( 3 ) 发送e m m 消息e m m 消息可以分为惟一寻址的消息和全局消息。 全局消息发给所有属于该节目提供商的用户，这个消息将通过在屏显示 ( o s d ) 显示在用户的电视上，一般用于发送第二天的节日预报或者新节目 的介绍等内容。 惟一寻址消息意思是这个消息将通过惟一的l d 发送给指定的用户。只在 这个用户的屏幕上显示节目提供商发送出的消息，其他用户无法收到这个消 息。这种消息适用于通知用户交费等用途。 节目提供商可以设定消息显示的时间，比如6 0 秒，用户可以手动取消 它。实际上这是一种广告或节目通知的手段。 ( 4 ) 发送邮件邮件可以分为惟一寻址的邮件和全局邮件。用户收到邮件 后，由西件并不马上显示在屏幕上而只是提醒用户有新邮件。只有用户手动查看 邮件时，邮件的内容才会显示在屏幕上。惟一寻址邮件意思是这个邮件将通过 惟一的i d 发送给指定的用户。用户查看后，邮件并不会丢失而是存储在机顶 盒中，直到用户手动删除邮件或者存储达到最大数目的限制而又收到新邮件时 删除最旧的邮件。 ( 5 ) 不同层次的加扰方式分别对p e s 层( p r o g r a me l e m e n t a r ys t r e a m ) 和 t s 层( t r a n s p o i ts t r c a m ) 加扰。当对t s 加扰时，对视青频和数据都采用同一 个控制字进行加扰，c w 在个相同p l d 的e c m 流中传输；如果对p e s 加 扰，视音频和其他数据流分别在最基本层次被不同的控制字加扰，而且在不同 p i d 标识的e c m 中传输。这种不同层次的加扰方式为用户提供了更多的选择 和灵活性，例如可以在同套数据流中加入多国语言的支持，满足不同要求。 鉴互董三兰查兰耋翌圭兰堡堡塞 ( 6 ) 成人级分类智能卡严格按照成人级分类对密码进行验证。保证适当 年龄的人群收视适当的节目。 ( 7 ) 指定机卡方式默认情况下，一般不指定这种方式，但如果想禁 止用户持自己的卡而借用他人的机顶盒收看节日，就可以以这种一机一卡方式 进行匹配验证。 ( 8 ) 智能卡认证智能卡和机顶盒之间的通信是加密的。用来保护智能卡 解密出来的传输给机顶盒的控制字。此功能将智能卡和机顶盒之间的通信又加 了一把锁，严格控制着通信的安全性。 1 2 ，2 4 条件接收系统安全性条件接收系统安全性最值得我们关注。 一个条件接收系统包括两个加密子系统，一个是节目加密系统，对播出的 节目内容进行加密，习惯上称为加扰，它的作用是扰乱节目信号，使得未经 授权的用户不能收看加密节目。另一个加密系统是分层密钥加密系统，其目的 是使用一环紧扣一环的层次加密，保护控制字的安全。 对节目的加扰，采用d v bc s 算法，该加扰算法使用的是基于密钥的算 法，控制密钥是c w ，为了保证加扰的安全可靠，c w 通常5 1 0 秒变化一 次，并且保证充分的随机性，有效地抵抗黑客的攻击，由于前端采用了标准的 通用加扰算法，从而增强了接收设备的通用性，只要接收设备配备了同样的解 扰算法，并完成了c a 系统集成，即具备了收看加扰节目的条件，如果有授权 即可收看加扰节目。 而对于分层加密技术，在密码学中，它已经成为一项公认的成熟的技术。 其中控制字用于加扰节目内容，该密钥是经s k 加密后通过e c m 传送给用户端 的，而s k 、p d k 、l k l l 4 j ( 节目发行商密钥) 等依此使用p d k 、l k 和p p k ( 个 性化密钥) 加密后通过e m m 发送到用户端。在用户接收端，接收控制智能卡 中按照相反的次序依此解开l k 、p d k 、s k 、c w ，如果用户拥有收看节目的授 权，将解出c w 明文，并传送给接收设备，由接收设备完成摄终的解扰工作。 1 2 _ 3 国内外的发展现状 在欧洲和北美都有自己独立的c a 系统，软硬件都自我研发，形成一种良 好的市场应用环境。 在我国c a 系统发展比较晚，大部分的有限电视c a 系统都移植外国成型 的c a 系统，比如像中视联、清华同方等都是引进或者是与外国公司进行合 作。整体上我们还停留在软件系统上，对硬件电路的开发还没有形成自己的产 哈尔滨工业大学工学硕士学位论文 业，受制于外国公司，也就是说我们还没有真正的核心技术。 通过上一节的分析，我们可以看到在c a 系统中，最重要和核心的部分就 在于对控制字的加密过程和控制字的加扰过程，这就要我们深入研究密码体 制。在国际上对密码体制的研究已经很成熟，不过在国内不管是理论还是实际 应用上都存在严重的滞后现状。尤其是在转化成硬件电路上，国内还尚处于起 步阶段。 在美国s e c 删t yd y n a m i c si n c 公司首先发现了这种技术的商业价值，并且 于1 9 8 6 年开发出相关类型的产品，将过去主要与操作系统或系统软件进行捆 绑的销售方式转向应用领域，投放到银行、政府、军队、保险和企业内部安全 等领域并取得了巨大的成功。 在2 0 世纪9 0 年代中期，国内的电子工业部第1 5 所、中科院研究生院、 d c s 中心( 中国数字安全技术研究中心) 、国家安全机构和一些科研院所就在 跟踪国外密码技术的发展，并做出了一些样品。不过直到1 9 9 7 年，福建凯特 才从国家d c s 中心取得了技术支持，将其变成了一个产品，成为国内第一个 吃螃蟹者。随后中兴通讯，北京天一也进行了此领域的研究和科研工作。 在我国数字电视急速发展的今天，国内所使用的智能卡都是与外国c a 厂 商( 主要是飞利浦公司) 合作引进的，研制具有自主知识产权的算法硬件电 路就成了国内数字电路厂商的当务之急。在这种现状下，研究r s a 算法的硬件 电路具有很高的理论和实际意义了。 1 3 论文研究的主要内容和章节安排 本文在研究数字电视条件接收系统，密码体制的基础上，对公钥密码体制 r s a 算法和实现此算法的方法进行了深入的研究。并最终基于不同设计思想实 现了两种硬件电路，达到了国微技术的设计要求。本文研究的主要内窖包括： 第一，r s a 算法的算法实现，参数选取和安全性分析。第二。基于不同算法理 论研究，r s a 算法的硬件实现。 本文的章节安排： 第l 章为绪论，介绍了课题背景和国内外发展的情况。 第2 章详细论述了密码体制以及公钥密码体制在数字电视c a 体统中的应 用。 第3 章深入研究了r s a 算法的实现方式，参数选取和安全性的分析。 第4 章深入研究了r s a 算法的各种实现方案，为下一步实现硬件电路傲 第2 章密码体制及其在条件接收系统中应用 密码体制按密钥方式可分为单钥密码密码体制和公钥密码密码体制，经过 多年的发展都已经形成成熟的算法，它在条件接收系统中也具有举足轻重的作 用。 2 1 密码体制 2 。1 1 单钥密码体制 又称对称式密码1 1 6 】密码体制，是一种比较传统的加密方式，其加密运算、 解密运算使用的是同样的密钥，信息的发送者和信患的接收者在进行信息的传 输与处理时，必须共同持有该密码( 称为对称密码) 。因此，通信双方都必须 获得这把钥匙，并保持钥匙的秘密。 单钥密码体制的安全性依赖于以下两个因素：第一，加密算法必须是足够 强的，仅仅基于密文本身去解密信息在实践上是不可能的；第二，加密方法的 安全性依赖于密钥的秘密性，而不是算法的秘密性，因此，我们没有必要确保 算法的秘密性( 事实上，现实中使用的很多单钥密码系统的算法都是公开 的) ，但是我们定要保证密钥的秘密性。 从单钥密码体制的这些特点我们容易看出它的主要问题有两点：第一，密 钥量问题。在单钥密码系统中，每一对通信者就需要一对密钥，当用户增加 时，必然会带来密钥量的成倍增长，因此在网络通信中，大量密钥的产生，存 x 兰玺鎏三些奎耋三兰堡圭兰竺鲨兰 2 1 2 公钥密码体制 正因为单钥密码体制存在如此难以解决的缺点，发展一种新的、更有效， 更先进的密码体制显得更为迫切和必要。在这种情况下，出现了一种新的公钥 密码体制，它突破性地解决了困扰着无数科学家的密钥分发闯题，事实上，在 这种体制中，人们甚至不用分发需要严格保密的密钥，这次突破同时也被认为 是密码史上两千年来自单码替代密码发明以后最伟大的成就。 在公钥密码体制【2 0 j 中，使用一对密钥对( k p ) 对消息进行加密和解密。 公开密钥1 2 l j ( p k ) 是公开信息，私有密锯 2 2 】( s k ) 是保密信息，私有密钥不 能根据公开密钥直接计算出来。加密算法( e ) 和解密算法( d ) 都是公开 的。公开密钥和私有密钥是一一对应的。发送者用公开密钥对明文加密后，合 法接收者用私有密钥解密，即可恢复出明文。 公钥密码体制的算法中最著名的代表是r s a 系统，此外还有：背包密码、 m c e l i e c e 密码、d i 仃e 出e l l m a i l 吲、r a b i n 、椭圆曲线1 2 4 】、e i g a m a l 算法等。 2 2 公钥密码体制在条件接收系统中的应用 在c a 系统中，公钥密码体制主要用于对私有密钥( 控制宇) 的加密过 程。每个用户如果想要对数据进行加密和解密，都需要自己的密钥对。密钥对 中的公开密钥和加解密算法部是公开的，私有密钥由密钥主人妥善保管。对数 据进行加密传输的实际过程1 2 5 】是： ( 1 ) 发送方生成一个私有密钥并对数据流用私有密钥进行加扰，然后用 网络把加扰后的数据流传输到接收方。 ( 2 ) 发送方生成一对密钥对，用公开密钥对私有密钥进行加密，然后通 过网络传输到接收方。 ( 3 ) 接收方用自己的私有密钥( 存放在接收机智能卡中) 进行解密后得 到私有密钥，然后用私有密钥对数据流进行解扰，得到透明的数据流。 因为只有接收方才拥有自己的私有密钥，所以其他人即使得到经过加密之 后的私有密钥，也无法进行解密得不到私有密钥，从而保证了传输数据流的安 全行。实际上，在数据传输过程中实现了两个加密解密过程：数据流本身的加 解扰和私有密钥的加解密。这分别通过公共密钥和私有密钥来实现。图2 1 展 示了c a 系统中公钥密码体制的应用口6 】。 哈尔滨工业大学工学硕士学位论文 2 3 本章小结 图2 1c a 系统中公钥密码体制的应用 f i 9 2 - 1t h e 印p l i c 鲥o no f p u b 】j c k e yc r y p l i ) s y 5 f e mj nc as y s l e m 本章中介绍了密码体制和公钥密码体制在条件接收系统中的应用，主要研 究了公钥密码体制如何对控制字进行加密和解密过程。下面的章节将介绍一种 公钥密码体制r s a 及其硬件电路的实现。 第3 章r s a 算法 3 1r s a 算法加解密及数字签名 公钥密码体制有多种实现方式，r s a 算法是其中的典型代表。1 9 7 8 年美国 麻省理工学院三名密码学者r l 刚v e s t 、a s h a m i r 、lm a d l e m a n 鲫提出了一 种基于大合数因子分解困难性的公开密钥体制，简称为r s a 密码算法。r s a 算 法的基础是数论的欧拉定理，它的安全性依赖于大数因子分解的困难性，至今 没有很好的破解方法，并且r s a 算法既可以用于加密，又可以用于数字签名， 因此r s a 公钥密码算法在信息交换过程中使用比较广泛，安全性很高。许多国 家标准化组织，如i s o ，i t u 和s w i f t 【2 8 】等都已接受r s a 作为标准。i n t e m e t 网 的e m a i i 保密系统g p g 以及v i s a 和m a s t e r 组织的电子商务协议( s e t 协议) 中都将r s a 密码作为传送绘画密钥和数字签名的标准【2 9 】。在数字电视应用中， 更是把r s a 算法应用在智能卡中，用来传送控制字。可见r s a 算法本身的特性 得到业内的共识。 r s a 算法描述如下1 3 0 】： 消息明文以分组的方式进行加密，每一个明文分组用整数m 表示，密文 用整数c 表示。r s a 算法的密钥选择方法如下： ( 1 ) 选择两个大素数p 和g ( 可以用r 丑b i n m i l l e r 素数检验法) ： ( 2 ) 计算模数 和的欧拉函数 n = p x q 西( 砷= ( p 一，) ) 啪一，) ( 3 ) 选择公开密钥口，满足o p 口，进而求出p 和叮值来。 3 21 4 一，) 和( 口一，) 的最大公园子要小才能达到安全要求。 在密文攻击中，攻击者截获了某个密文，攻击者进行迭代加密攻击，即令 f = 2 ，3 ，依次计算 c ，= ( c f - 1 ) 9 = ( m ) 。m o d ( 3 _ 8 ) 如果是 p = l m o d 矿( )( 3 9 ) 必然会有 c ，= m m o d ( 3 lo ) 于是，通过迭代加密获得明文，攻击成功。 如果满足式( 3 9 ) 的f 值很少，则上述的攻击计算就很容易进行。根据式( 3 - 9 ) 和欧拉定理可知 f = 矿( ( ) ) = 妒“p 1 ) ( g 1 ) ) = d 庐( p 1 ) 矿( g 1 ) 庐( d ) ( 3 1 1 ) 其中d = ( 矿j ) ( q j ) 为p j 和g ，的最大公因子。 由式( 3 1 1 ) 可知，当d 越小，矿( d ) 就更小，从而使f 值变大。当f 值足够大的 时候，便可以抵抗这种攻击。因为p j 和g j 均为偶数，所以有公因子2 。如果 达到理性情况，其最大公因子为2 p 习。 设p 和q 为理想的强素数，令p = 知+ j 。q = 拍+ ，其中口，6 为奇素数。 若d _ 2 ，( d ) = l 时，把它们带入公式( 3 1 1 ) ，根据公式可以得到下面结果， 卢妒( ( ) ) = 庐( ( 2 口) ( 2 6 ) ) = 2 ( 2 a ) 矿( 2 6 ) = 2 ( 玎) ) 2 2 f 小 伪一d a 3 2 2 公开密钥窖的选择 为了使加密的速度快，口的二进制表示中应当含有尽量少的1 。一种方法 是选择尽可能小的p 或者选择某些特殊的p 。若口太小，对于明文肘，则有 c = j ：i ， = o ；f 一) tp 。f ， _ l ( i n o d 研 i f ( e 严1 ) r 尸n 州+ m ( m o d 。； 哈羹僻础薹萋噶纂薹囊 谁舅钤l j 垫箪蚓淤一粤引a 警童d 培巩霉 矍癸磊蓦矧枣莉丞魏鞭翌i 袭隳鲐蘩珀蜴k 嚣。珞鼙岂蠹；生f f 鐾浮熊螫薷；弦鲥 丽譬埕辇墓h j 蛩当囊甜帮撕恤摹鬟盏墓耋茎蕈餮再；j ；并珏墨雾酸翼鬻掣璧鳋；凳“莲蓼 砬张瑾蛀冀； | j ! m 蕃雏蚕i 西! l 毫i i 玎遗塑鬟 玎_ 囊型雾；薹| 重墓嚣毡萄黼鐾髦壅蠹缨甏 蓦目4 ? | “菩且女饕妻：蔷 笺霄葫萎一 刁篓丽锚塑簦篷警劐则上- 面刚争。潮囊徽萋l 简鞘誊筑鞘戳文鬻| 琶l 嚣藩赫瀑嵯琴鼢耋 范嘎。：! ! 南喜蓑蓁是捌焉； 豁器；妻i i ；“e 墓；h ? 如锚萱跫裂磐舟钤ij g i ；g 浩瓣淹臻萌衙d 秀坪茹旁 东ii 。【j j 誊漕g 矍滞i 蟊雕劐蛰尉崮乏3 囊羹鍪 鏊i 目莓 蓄；i i ；l l 丽褂f f 甑袖蔓鍪蓍蠡落掣i 委i ；! ，；藿| 霸巨商画搿叭j _ 蓑 l l i 囊囊搿引雌 炷豆影卜i 勤皇i i j i 霎l i 囊誉l 葩嗣爵骣裂擎热 刘挺；l 蓦；目喜j 垂| x 陇& 强荆裂瑁。莲囊萎疑9 自姣翻 裔浔j ：椎游鸳逐? ! 鬈q q 要蠢蒂州斧扣矗毹颦l ? 堇j 要篓薹= 耋耋基甏l i i 蕊塾茧舅酞簿 j 目自a i g n 委l 趔难州翻匕生歼蛙 _ 薹u u 琵驺鸶秘明 剖蚕卿疆强建繇激；冀鋈瓢测艄虿岜k ) q l 矧剖侧霭 精终型帚掩 j j f 璧型捌鞋乙副；i ；藿自f i ；! 以麓溺一 魏涮尝删崩；霎； 捌弹疆器霎： 娱越藉挝莉璧澎堆哩之罨岍照渤舞。 止娄嚣l i i 囊i 膏荆一拟甬缸f 电颤 x 哈尔滨工业大学工学硕士学位论文 j = 一m ， 0 ，l ，二= 二( 4 8 ) z 分别用爿和肘分别用j 和替换，计算扩( m o d 9 ，由公式( 4 - 4 ) 可知 = ( 一f ) ( r 一，) = 爿 f( m o d 叻( 4 9 ) 同理，当4 ( _ j ) 2 ，肘甄_ j w 时，彳用f 代替，计算m ( m o d 加；当爿兰( _ ) 门，胗( - ) 门时，m 用，代替，计算叫，( m o d 川。可以根据公式( 4 5 ) 验 证。 一n f = 【 f f a f = ( 一f ) m = 彳h ( m o d d ( 4 1 0 ) 一4 = 一一= 一( 一，) = 一m ( m o d ) ( 4 - “) 按照上面的替换规则，把较大的数代换成较小的数进行乘积或者平方运 算，计算公式公式( 4 2 ) 中的每一步迭代，可以快速的完成运算。我们可以看 出，当m 越大时，节约的运算量也就越大。 4 3 改进s m m 算法 根据上述所示，r s a 算法的迭代步数取决与指数口的二迸制长度以及它的 非o 元素个数。这里我们可以改变p 的指数形式，使其进行迭代的次数减少， 增加算法的效率h ”。 我们使用“1 ”表示“1 ”，通过以下方法把e 转化为二进制冗余数r ( p ) ： ( 1 ) 连续的“1 ”形式的变化： ( 1 1 ) 2 _ ( 1 0 0 ) 2 ( 1 ) 22 1 0 l ( 1 1 1 ) 2 = ( 1 0 0 0 ) 2 - ( 1 ) 2 = i o ol ( 1 1 1 1 ) 2 = ( 1 0 0 0 0 ) 2 - ( 1 ) 2 - 1 0 0 0l ( 1 l 1 ) 2 = 1 0 0 1 ( 2 )当1 l o ”和“1 1 1 0 ”码型之后出现 个( 七2 ) 连续“l ”时，可以进 行如下代换 哈尔滨工业大学工学硕士学位论文 ( 1 1 0 1 1 ) 2 = ( 1 0 0 0 0 0 ) 2 - ( 1 ) 2 一( 1 0 0 ) 2 = l o o o o l _ ( 1 0 0 ) 2 = 1 0 0 l0 1 ( 11 1 0 1 1 ) 2 。1 0 0 010 o l 按照上面的方法，e 就可以表示成l ，0 ，1 形式的二进制冗余数。很容易 看出，当连续的“1 ”的个数大于等于3 或者“1 1 0 ”及“1 1 1 0 ”码型之后的连 续“l ”的个数大于等于2 时，进行的迭代运算次数明显减少。 根据公式( 4 2 ) ，要对公式进行迭代，包含有三种基本运算，即 一? ( m o d ) ，4 m ( m o d ) ，爿，m 一。( m o d ) 。m 是肘对模的乘逆。 算法描述如下 ( 1 ) 我们按照二进制冗余数的转换方法，用尉p ) 代替p ，公式( 3 - 4 ) 变成 c = ，m 8 m o d ( 4 - 1 2 ) n j 一 其中r ( p ) - = e ，ne ， 0 ，l ，1 ) ( 2 ) 用欧几里德算法【2 】，由公式( 4 1 3 ) 求出删模的乘逆1 埘m = j ( m o d ) ( 4 - 1 3 ) c s ，令肘= 芳一肘 = f ： ( 4 ) 从只0 ) 的高位开始， 则具体的迭代算法为： m 型 z m 型 ? m ls 盟 2 m 一， 型 z 进行迭代运算。若爿为第涉迭代的中间结果 ：兰玺堡三些銮耋三兰塑圭耋堡篁耋 姐簿嫩一们删式 爿h = 一? ( m o d )( 4 1 4 ) 一h = 彳。肘( m o d )( 4 - 1 5 ) 爿h = 爿 ，一( m o d )( 4 - 1 6 ) 当r ( e ) 的第f 位为“0 ”时，进行( 4 1 4 ) 的运算；当r ( p ) 为“1 ”时，进行 ( 4 一1 5 ) ，( 4 1 4 ) 的运算；当敢f ) 为“l ”时，进行( 4 - 1 6 ) ，( 4 1 4 ) 的运算。从尉f ) 的最高位开始，直至r 0 ) 的最低位计算完成。 4 4 m o n t g o m e r y 算法 虽然在以上的分析中，每个算法都可以简化运算，但是仍然没能从根本上 避免大数的模乘计算。m 0 n t g o m e r y l 4 2 】算法把部分积对任意的 暾模运算转化为 对数基r 的取模，由对基数点的取模运算要比对i 拘取模运算简单的多，尤其是 对于特别选择的r 可使得对尺的取模运算变为移位运算。从而可以大大的提高取 模运算的速度。这里如果选取月为2 的次幂，这样在硬件实现中，我们就可以 通过移位运算完成。通过对寄存器的移位运算，彻底解决了部分积取模的棘手 问题，使运算更加清晰、简化。下面就是m 0 n t g o m e r y 算法的具体实现过程。 设为模数。选择一个与互素的正整数r 做为基数。再选择正整数月。和 ，满足条件0 月o ，o 月，并且使得 矗r 7 _ = 1 ( 4 1 7 ) 根据公式( 4 1 7 ) 有 r r 。= lm o d 4 = 1m o d r 于是称f 7 为r 的模i 蓖，。为的模r 负逆。 设彳和曰是要相模乘的两个数，且满足 m o n 口，e r j ) 给出了计黝b r 。m o d f 勺算法 f u n c t i o n m o n 口，b ，r ，) ( 4 - 1 8 ) ( 4 - 1 9 ) 0 叫嚣 幔，m o n 培o m e f y 算法 ：互鋈王些奎兰兰堡圭耋堡篁塞 ( 1 ) y = 一口； ( 2 ) f 7 m o d r ； ( 3 ) f = ( 删偎； ( 4 ) i f ( 仑) f = f ， e l s e 卢；f ： 根据算法m o n 似，占，月朋可知，户( 升膪，则& - 丁_ r = 一r m o dr ，所以 ( 7 h _ ) = o m o d r( 4 - 2 0 ) 公式( 4 2 0 ) 说明( 删是r 的倍数，因此f 为整数。根据f = ( n s ) 值，有识= ( 升m 1 ，于是 f = 豫。刊b r 。7 ( m o d 奶( 4 2 1 ) 这就证明了m 0 n t g o m e r y 算法完成了一且r 。m o d 的计算，即 m o n 口，b 皿朋刊br “m o d ( 4 2 2 ) 根据以上分析得知，o 勺 足，于是o 龟 兄m 另外，根据m o n t g o m e r y 算 法对r 范围的要求0 r r ，所以有o n s r + 删三2 兄。所以函数m o n 0 ，b ，r 朋计算的结果f 取值的范围是0 f 电。由于丁和r 都有町能大于，所 以说存储r 和f 要用更大的存储器。正是使用了更多的存贮资源，才节省了时 间资源，使计算速度更快。 在实际计算中，我们并没有直接对进行取模运算，只是进行了对月的取 模运算。一般r 要比，j 、的多或者r 取特殊值，如r = ，这样进行取模运算的时 候更简单高效。 利用函数m o n a ，口，r v ) ，计算，一曲m o d ，0 珥6 ( 1 1 预处理： 爿= 口r m o d ，庐6 r m o d ( 4 2 3 ) ( 2 ) m o n 计算 y _ m o n 叫，e 足柳刊br “= ( 枷) ( 6 r 皿。邗掀( m o d 聊( 4 2 4 ) ( 3 ) 调整运算 尸m o n ( z j ，冠) = 豫。= 0 6 r ) _ 口6 ( m o d 抑( 4 - 2 5 ) 上面的运算过程完成了部分积对大数的取模运算，通过三个步骤运算完成 操作，不过细心的观察之后，发现公式( 4 - 2 4 ) 和( 4 2 5 ) 都是采用了m 0 n 计算，只 是有一个参数换成l 而已，所以说，整个算法的运算过程就分为预处理和m o n 计算的迭代过程【4 3 1 。 哈尔滨工业大学j 二学硕士学位论文 4 5 本章小节 本章研究了多种r s a 实现方案，包括二元算法、s m m 算法、改进s m m 算法和m 0 n t g o m e r y 算法，逐步深入的探讨基于不同理念实现算法的可行性和 实现过程。对不同种方法的改良和改进，为今后进一步实现硬件电路打下良好 的基础。下一章，结合各种算法的优点，基于不同的设计理念，设计出不同 r s a 硬件实现。 5 1 1 改进m o n t g o m e q 算法 根据上一章的分析，采用m o n 蟾o m e r y 算法一次性地进行曲m o d 膜算并不 划算，每一次地预处理和调整都需要大量地运算。m o n t g o m e r y 算法最适合大量 地计算模乘运算，r s a 算法