（交通信息工程及控制专业论文）RSA加密算法及其改进措施的研究和实现.pdf

摘要 摘要：国际互连网的发展、国际社会信息化进程的加快，使得信息 安全问题变地日益重要，保密通信是信息安全问题的核心，采用良好 的密码体制对信息设施保护和真伪鉴别，是解决信息安全问题的有效 途径之一。 r s a 是国际上广泛使用的公钥密码体制，但其运算速度特别缓慢， 这成为高速加密的瓶颈。因此研究r s a 快速算法是密码学界十分重视 的研究课题。 本文研究和介绍了国际上流行的几种对r s a 进行改进的方法，并提 出了构造了融合多种快速算法的新的r s a 算法，理论分析表明，新算 法中无论乘法还是模运算，都比传统的二元算法( b i n e r yr e p r c s e i i t a t i o n ， 简称b r 算法) 快，迭代步数也比b r 算法少，在理论分析的基础上， 并利用s u a lc + + 进行了新算法的软件实现。 关键词：信息安全r s a算法密码学公开密钥私有密钥 模幂模乘迭代 前言 前言 自2 0 世纪9 0 年代以来，计算机的普及和应用进一步得到推广和 发展，计算机网络技术在全球得以迅猛发展和推广，成为当代发展最 迅猛的技术，其应用几乎已经深入到人类社会生活和活动的一切领 域。但是计算机在给人们的生活和工作带来极大方便的同时也带来了 许多亟待解决的问题，大量敏感信息如何保护成为一个主要的问题。 一个安全、健壮的信息系统离不开各种信息安全技术的支持。计算机 网路中所采用的核心安全技术都是由密码学派生出来的技术和应用， 现代密码学技术的研究和发展是计算机技术尤其是网络安全技术发 展的重要保障。 根据各种安全技术和应用的需求，人们提出了许多密码的算法， 在广泛的应用中，一些优秀的密码体系的性能和安全性不断得到证实 和加强，但是，随着计算机运算能力的提高以及分布式计算技术的发 展，各种密码系统的安全性都受到了不同程度的威胁。有些密码系统 已经破解，例如d e s 密码体制。另外许多著名的密码体制也岌岌可危， 例如经典的r s a 公钥密码体制。r s a 算法曾被公认为是最优秀的密码 体制之一，它由r l r i v e s t ，a s h 锄i r 和l a d l e m a n 于1 9 7 7 年提出， 在广泛的应用下它的安全性和性能不断得到人们的肯定，从而成为最 流行的密码体制。随着计算机计算能力的提高以及分布式计算的发 展，一个5 1 2 b i t 的r s a 模数在1 9 9 9 年8 月被成功分解，以及还有更 早被攻破的r s a 一1 2 9 ( 1 9 9 4 年) 和r s a 一1 3 0 ( 1 9 9 6 年) 。 为此，人们提出了许多新的方案和算法以替代和加强现有的密码 体系，量子密码以及混沌密码的提出更是给现代密码学注入了新的血 托京交遥大学硕士学位论文 液。但是现有的情况下，r s a 密码体系仍被认为是不可破解的密码体 系，但这是以增加密钥的长度为代价，不可避免的增加了运算的时间， 这成为rsa高速举嚣威亘讦；算飙；稿秘秘纠嬲番l妻蠛型芟到 引引引若型器改昀鞯聃甄鼙鑫， w葡篡拣辖蛋蕴帮；豁羚瑟显鲁岂i蒌鑫墨显憔登咎露挚爱受撵 裂釜茬半遣雳灞带蔷型雨鬈涤浠温罐满；簇爵算机系统的安全是当前一个亟待解决的问题。 1 1 1 计算机系统面临的安全威胁 计算机系统中可能存在种种不安全因素，大体可以分为如下几个 方面： l _ 网络部件不安全因素 ( 1 ) 算机系统的硬件设备容易造成人为的损害： ( 2 ) 网络端口、传输线路和处理机都有可能因屏蔽或者未屏蔽造成 电磁泄漏； ( 3 )犯罪分子为了获取情报，可能监听通信，伪装合法用户，线路 干扰等手段非法接收信息； ( 4 )计算机病毒也可以以多种方式入侵计算机网络，并不断繁殖， 扩散到网上的计算机，以破坏整个网络。 2 软件方面不安全因素 ( 1 )网络软件安全功能不健全或被安装了特洛伊木马等造成信息 泄漏： 4 x 前言 基本思想、算法、参数选择并且重点讨论了与本科题密切相关的r s a 算法的安全性与速度问题。 第五章是重点，在详细介绍传统b r 算法的基础上，介绍了三种 r s a 算法的改进算法，并予以理论上的证明，并在最后给出了一个三 种改进算法的组合算法模型，论述了改进的高效r s a 算法的设计。 第六章是在实际测试的基础上给出了一个最为有效的r s a 改进算 法的软件实现。 概论 ( 2 ) 计算机软件每天都在不停地运行大量的软件，由于工作人员的 不慎或者其他存心不良的人的有意删除，造成软件的损坏、丢失； ( 3 ) 软件内部有秘密陷阱，接到秘密指令后摧毁计算机系统； ( 4 ) 利用盗取系统的磁盘、光盘等纪录载体，或者利用废旧的打印 纸、复写纸来盗取系统或者用户的信息 3 数据攻击 计算机硬件的损伤和软件方面的漏洞往往会给计算机系统造成极 大的损伤和破坏，但是它不会给攻击者带来有价值的利益，只要对计 算机系统的硬件设备和软件实施有效的保护，可以减少它们带来的麻 烦。但是，计算机系统中的数据往往才是攻击者的目标，攻击者往往 希望得到程序的结果。 对于期望获得计算机数据的网络的攻击包括对静态数据的攻击和 对动态数据的攻击。对静态数据的攻击主要有： ( 1 ) 口令猜测：通过穷举方式搜索口令空间，逐一测试，得到 口令，进而非法进入系统； ( 2 ) i p 地址欺骗：即攻击者伪装成源自一台内部主机的一个外 部地点传送信息包，这些信息包中包含有内部系统的源i p 地址，以 次来假冒他人，窃取信息； ( 3 ) 制定路由：即发送方制定一信息包到达目的站点的路由， 而这种路由是经过精心设计的，绕过没有安全控制的路由到达发送方 想到的地方。 对动态信息的攻击方式不同，可以将攻击分成主动攻击和被动攻 击两种： ( 1 ) 主动攻击：主要指攻击者在网上监听传递的信息流，从而 获取信息的内容，或仅仅希望得到信息流的长度、传输频率等数据， 北京交通大学硕士学位论文 称为流量分析； ( 2 ) 被动攻击：指攻击者通过有选择的修改、删除、延迟、复 制、插入数据流或者数据流的一部分以达到其非法目的。 主动攻击可以归纳为中断、篡改、伪造三种。中断，指阻断由发 送方到接受方的信息流，使得接收方无法收到该信息，这是针对信息 可用性的攻击：篡改，指攻击者修改、破坏由发送方到接受方的信息 流，使得接收方接到错误的信息流，从而破坏信息的完整性；伪造， 指针对信息的真实性的攻击，攻击者或者事先记录一段发送方接受方 之间的信息流，然后在合适的时间向接受方或者发送方重放该段信 息，或者是完全伪造一段信息流，冒充接收方可信任的第三方向接收 方发送。 1 1 2 计算机网络中的安全策略 针对上述计算机系统中的种种威胁，可以采取以下的安全对策： 1 保护传输线路的安全 对于传输线路，应有露天保护措施或者埋于地下，并要求原理各 种辐射源，以减少由于电磁干扰引起的数据错误；电缆铺设要使用金 属导管，以减少各种辐射引起的电磁泄漏和对发送线路的干扰。集线 器和调制解调器应放在受监视的地方，以防止外连的企图：对连接要 进行定期的检查，以检测是否有搭线窃听、外连或者破坏行为。 2 。防入侵措施 应加强对文件处理的限制，控制重要文件的处理。利用警报系统 检测违反安全规程的行为，对安全码的不正确使用或者使用无效的安 全码。对规定次数内不正确的安全码使用者，网络系统可以采取行动 锁定该终端并报警，以防止非法者突破安全码，入侵系统。 概论 3 网络加密 网络加密是网络中采用的最基本的安全技术。网络中的数据加密， 除了选择加密算法和密钥以外，主要问题是加密方式以及实现的网络 协议层和密钥的分配以及管理。网络中的数据加密方式主要有：链路 加密、节点加密和端对端加密等方式。数据可咀在o s i 协议参考模型 的多个层次上实现。 4 存取控制 访问控制是在由鉴别机制提供的信息基础上，对于个体或者过程 特权的获得与实现。鉴别是为存取控制提供任何非授权的资源存取。 对于文件和数据库设置安全属性，对其共享的程度予以划分，通过存 取矩阵来限制用户的使用方式，如只读、只写、读写、可修改、可 以执行等。数据库的存取控制，还可以分库、结构文件、纪录和数据 四项进行。 5 鉴别机制 鉴别是为每一个通信方查明另一个实体身份和特权的过程。它是 在对等实体间交换认证信息，以便检验和确认对等实体的合法性。鉴 别机制中采用报文鉴别，也可以采用数字签名或终端识别等多种方 式。 报文鉴别是在通信双方建立通信联系后，每个通信者对收到的信 息进行验证，以保证收到的信息是真实性的过程，也就是验证报文完 整性a 一旦这种鉴别信息被得知，并且它的准确性和完整性有保证， 那么本地用户或系统就可以做出适当的判断，从而决定什么样的数据 可以发送到对方。 6 数字签名 数字签名是个密文收发方签字和认证的过程。所用的签署信息 概论 时，对用作防火墙的服务器的性能要求很高，不要造成信息的延迟， 处理速度要很快。但是，它不能防止经过伪装后的信息的接入，一些 新的用户和节点，经过修改关键词可以骗过这种简单的防火墙。 ( 2 ) 增加认证和签名等功能 该服务器还负责对过往信息的签名检查，使用密码技术，做一些 身份验证、口令核实、审计等工作，可以有效抵抗内部局域网的破坏 和捣乱。 ( 3 ) 自身安全 防火墙本身不受各种攻击的影响，人机界面良好，用户配置使用 方便，容易管理。 2 加密技术 数据加密技术是可以与防火墙技术配合使用的一种安全技术，这 种技术可以提高信息系统以及数据的安全性和保密性，防止秘密数据 被外部剖析所采用的主要技术手段之一。按照起作用的不同，数据加 密技术主要分为数据传输、数据存贮、数据完整性的鉴别以及密钥管 理技术四种。加密技术是通过计算机网络中的加密机构，把网络中的 各种原始数据信息( 明文) 按照某种特定的加密算法变换成语明文完 全不同的数字信息，即转换成密文。计算机网络中的加密技术主要采 用链路加密以及端到端加密两种方式。 ( 1 ) 链路加密 链路加密是目前最常用的加密方式，这种方法是在物理层对数据 进行加密。当数据进入物理层传输时，对所有的信息进行加密保护， 解密过程在信息进入计算机之前进行。它主要用于保护通信节点之间 传输的数据。这种加密方式比较简单，具体实现起来比较容易，只要 把一对密码设备安装到两个节点之间的线路上。即把密码设备安装在 9 概论 1 2 信息保密技术 信息保密技术是信息安全技术的核心技术，其主要目的是防止恶 意攻击者非法破译系统中的机密信息。密码学属于信息保密技术范 畴，它是一门即古老又年轻的科学，它最早的应用可以追溯的几千年 前的古罗马，但成为一门独立的学科则是从最近几十年才开始的。 1 9 4 9 年s h a n n o n 发表的“保密系统的信息理论”和1 9 7 6 年d i f f i e 和h e l l m a n 的“密码学的新方向”首次提出的公钥密码思想奠定了现 在密码学的理论基础。1 9 7 7 年美国数据加密标准d e s 的正式发布和 1 9 7 7 年r l - r i v e s t ，a s h 8 m i r 和l a d l e m a n 三人共同提出的第一个 d i f f i e h e l l m a n 公钥密码思想的密码体制r s a 公钥密码成为现在 密码学研究迅速发展的两个里程碑。 1 2 1 密码体制 为了实现信息的保密性，抗击密码分析，保密系统应当满足以下 要求： 1 即使达不到理论上是不可破解的，也应当是实际上不可破解 的。也就是说，从截取的密文或某些以知明文密文时，要确定密钥或 者任意明文在计算上是不可行的： 2 保密系统的安全性依赖于密钥，而不是依赖于密码体制或算法 本身的细节的安全性； 3 加密解密算法适用于所有密钥空间的元素； 4 系统应该易于实现和使用方便。 根据加密密钥和解密密钥是否相同或者本质上等同，即从其中 个容易推算出另一个，可将现有的加密体制分为两种：一种是单密钥 北京交通大学硕士学位论文 加密体制( 也称对称密钥加密体制) ，其典型代表是美国的数据加密 标准d e s ；另一种是公钥加密体制( 也称非对称加密密钥体制) ，其典 型代表是r s a 密码体制。 根据对明文的加密方式的不同，又将单密钥加密体制分为两类： 一类是流密码，在这类体制中，明文按字符逐位地被加密：另一类是 分组密码，在这类体制中，先将明文分组，然后逐组地进行加密。公 钥密码体制大部分都是分组密码，一般不在按明文的加密方式对其进 行分类。 1 2 2 古典密码 古典密码是密码学的渊源，这些密码都是由基于字符串的密码算 法构成的，可用手工或机械操作实现加杰密。不同的密码算法是字符 间互相代换或是互相置换，好的密码算法世界和这两种方法，每次进 行多次运算。虽然现在已经很少采用了，但是原理还是没变，重要的 变化是对位而不是对字符进行变换，实质上这只是字母长度的改变。 古典密码的基本运算由两种：替代和置换。替代是指每一个或一 组字符被另一个或一组字符所取代；置换是不改变明文字符，而按一 定的规则重新安排字符序列。实际的密码算法是进行一系列这两种基 本运算的不同组合，即得到所谓的乘积密码。 比较有名的古典密码包括恺撤密码、维吉利亚密码、维尔南密码、 普莱费厄密码和希尔密码等。 1 2 3 单钥密码体制 单钥密码体制有时又叫传统密码算法，是指能够从解密密钥中推 算出加密密钥，反过来也成立。在大多数的单钥密码体制中，加密密 1 2 概论 钥和解密密钥是相同的，它要求发送者和接收者在通信之前先协商一 个安全的密钥，因此有时单密钥也称为对称密钥。单密钥体制的安全 性主要取决于算法和密钥的长度，泄漏密钥就意味着任何人都能对消 怠进行加解密。 单钥密码体制不仅可以用于数据加密，也可以用于消息认证。但 是单钥密码体制存在着严重的缺陷：在进行安全通信之前，通信的双 方必须通过安全信道商定和传送密钥，而在实际的通讯网中，通讯双 方很难确定一条合理的安全通道；另外一个问题就是密钥的管理。在 拥有大量用户的计算机通信网中，n 个相互进行保密通信的用户需要 ( n + 1 ) 2 个密钥；当n 值太大时，密钥管理的开销极大，密钥只能 纪录在计算机内存或者外存上，这本身就是极不安全的。 著名的数据加密标准( d e s ) 属于单钥密码体制，它作为世界范围 内的标准已经有2 0 多年的历史了。其它比较有名的分组密码算法还 有国际数据加密算法( i d e a ) g o s t 算法等。 d e s ( d a t ae n c r y p t i o ns t a n d a r d ) 数据加密标准d e s 是迄今为止最为广泛应用的一种加密算法，也 是最具代表性的一种分组密码体制。d e s 是美国1 9 7 7 年公布实施的第 一个公开绝大部分加密原理和算法细节的分组密码体制。美国政府目 前正在征集、评估和制定新的数据加密标准，新的数据加密标准称为 a e s 。尽管如此，d e s 对于推动密码理论的发展和应用起了重大作用。 掌握和了解这一算法的基本原理、设计思想、安全性分析等问题，对 于研究分组密码理论及其实际应用具有重要意义。 d e s 是一种对二元数据进行加密的方法，数据分组长度是6 4 位， 密文分组长度也是6 4 位，没有数据扩展。其算法基本思想是： 通过循环和迭代，将简单的基本运算( 例如左移、右移、模2 加 北京交通大学硬士学位论文 法等) 和变换( 选择函数、置换函数) 构造成数据流的非线性变换( 加 密变换和解密变换) 。d e s 算法的数据流程的基本框架是固定的，通过 密钥分解将一个实际上是5 6 位( 二进制) 的密钥分解成1 6 个4 8 位 的子密钥，每个子密钥控制一次循环或迭代。加密和解密的密钥和流 程是完全相同的，区别仅仅是加密与解密使用子密钥序列的操作顺序 刚好相反。 1 2 4 公钥密码体制 单钥密码体制的特点是解密密钥和加密密钥相同或者很容易从加 密密钥导出解密密钥。在单钥密码体制中，加密密钥的暴露会使系统 变得不安全。单钥密码系统的一个严重缺陷是在任何密文传输之前， 发送者和接收者必须使用一个安全信道预先商定和传送密钥。在实际 的通讯网络中，通信双方则很难确定一条合理的安全通道。 为了解决这些问题，w d i f f i e 和m e h e l l m a i 在1 9 7 6 年发表的 划时代的“密码学的新方向”一文，提出了公钥密码体制思想，为近 代密码学指明了方向，克服了单钥密码体制的缺点。它的提出是密码 学研究中的一项重大突破，也是现代密码学诞生标志之一。在公钥密 码体制中，解密密钥和加密密钥不同，难以从一个计算出另一个，解 密运算和加密运算可以分离。通信双方无须事先交换密钥就可以建立 起保密信道。公钥密码体制克服了单钥密码体制的缺点，特别适用于 计算机网络中的多用户通信，她大大减少了多用户通信所需的密钥 量，节省了系统资源，也便于密钥管理。1 9 7 7 年r i v e s t ，s h a m i r 和 a d l e m a n 提出了第一个比较完善的公钥密码算法，这就是著名的r s a 算法。自从那时起，人们基于不同的计算问题，提出了大量的公钥密 码算法。比较重要的有r s a 算法、m e r k e h e l i m a i i 背包算法、m c 日i e c e 1 4 概 论 算法、e l g a m a l 算法和椭圆曲线算法等。 设计公钥密码体制的关键是先要寻找一个合适的单向函数，大多 数的公钥密码体制都是基于计算单向函数的逆的困难性而建立的。例 如，r s a 体制就是典型的基于单向函数模型的实现，这类密码的强度 取决于它所依据的问题的计算复杂性。值得注意的是，公钥密码体制 的安全性是指计算安全性，而绝不是无条件安全性，这是由它的安全 性理论基础即复杂性理论决定的。 单向函数在密码学中起一个中心作用。它对公钥密码体制的构造 的研究是非常重要的，虽然目前很多函数都被认为或被相信试单向 的，但目前还没有一个函数等被证明是单向的。 1 3 小结 当前，以电子商务为标志的计算机网络和h l t e m e t 应用的迅速发 展使得信息安全技术成为信息科学与技术的一个重要研究领域。现代 密码技术是信息安全技术的核心。密码理论与技术的研究与应用是信 息安全技术的核心研究领域。 就信息的安全性来说，密码技术不仅可以保障信息的保密性，而 且可以保障信息的认证性和完整性，防止信息被篡改、伪造。从密码 体制的特点而言，它包括单钥密码体制和公钥密码体制。近年来，人 们提出的密码算法和体制数不胜数，比较著名的密码算法包括d e s 、 i d e a 、g o s t 、r s a 、背包密码、r a b i n 、e l g a m a l 、椭圆曲线密码等。 最近提出的一些新体制包括：多密钥公钥密码体制，可以将r s a 体制推广为具有多个密钥的公钥密码体制( 包括加密算法和数字签名 算法) ；量子密码技术：隐含域方程和多项式同构等。另外，最近关 北京交通火学硕士学位论文 “模”的运算：a 。m o dn 将导致一系列的乘法和除法运算，但是也有 加速运算的方法：一种方法旨在最小化模乘运算的数量；另一种至在 优化单个模乘法运算。因为操作步骤划分后，当完成一串乘法，并且 每次都进行模运算后，指数运算就更快，这样就与一般取幂没有多大 差别，当你用2 0 0 位或更高位的数字进行操作时，情况会大相径庭。 例如，要计算a 8m o dn ，不要直接计算7 次乘法和一个大数的模 化简： ( a a x a x a x 职a x a a ) 删) dn 相反，应进行三次比较小的乘法和三次较小的模化简： ( ( a 2 m o d n ) 2 m o d n ) 2 咖d n ，依次类推 当x 不是2 的幂次方时，计算a 。m o dn 稍微要困难些。可将x 表 示成2 的幂次方之和：在二进制中，2 5 是1 1 0 0 l ，因此2 5 = 24 + 2 3 + 2o 。故： a 2 5 i n o d n = ( a a 2 4 ) m o d n = ( a a 8 x a l 6 ) 1 0 d n = ( a ( ( a 2 ) 2 ) 2 ( ( ( a 2 ) 2 ) 2 ) 2 ) m o dn=( ( ( ( a 2 a ) 2 ) 2 ) 2 a ，m o d n 适当利用存贮的中间结果，只需六次乘法： ( ( ( ( ( ( ( ( ( a 2m o d n ) x a ) m o d n ) 2 m o d n ) 2 ) m o d n ) 2 m o d n ) x a ) m o dn 这种算法被称为加法链，或二进制序列的乘法方法。它用二进制表 示了一个简单明了的加法链。算法的c 语言描述如下： u n s i g n 甜l o n gq e 2 ( u d s i g n e d l o n gx ，u n s i g i l e d l 叩g y ，u n s i g n e d l o n gn ) u n s i g n e dl o n gs ，t ，u ： w h i l e( u ) i f ( u 1 ) s = ( s + t ) n ： 北京交通大学硕士学位论文 位，甚至更长) 。 2 1 3 求模逆元 在模运算领域，“求己知量a 的模n 的逆元”这个问题可以描述为 以知a 和n ，求解方程a x 1 ( m o dn ) 。 这个方程等价于寻找一组x 和k ，使得： a x = n k + 1x 、k 均为整数 求模逆元问题很困难。有时候有一个方案，有时候却没有方案。例 如，5 模1 4 的逆元是3 ：5 3 = 1 5 = l ( m o d1 4 ) ，2 模1 4 却没有逆元。 在这种情况下我们把x 称为是a 的模m 的逆，记做a 一( m o dm ) 或a 一。 2 1 4 欧拉定理及相关概念 r s a 的理论基础是数论中的欧拉定理。 定义3 ：数n 的模n ( n 1 ) 的余数化简集中元素的数目，称为该数 的欧拉函数v ( n ) ，它表示与n 互为素数的小于n 的正整数的数目。如果 n 是素数，那么v ( n ) = n 一1 ，如果n = p j ，并且p 和q 互为素数，那么 ( n ) = ( p 一1 ) ( q 1 ) ，这是公开密钥密码系统的基础。 定理l ( 欧拉定理) ：若整数a 和m 互为素数，即g c d ( a ，m ) = l ，则有 a “) e l ( m o dm ) 。特别当p 为素数时，对任意的a ，有a p5 a ( m o dp ) 。 定理2 ：若g c d ( m ，n ) = l ，则有v ( m n ) = v ( m ) v ( n ) 。一般的，对 f d f n = n p ， 可证明v ( n ) _ ”i = l ( 1 _ ( 1 聃) 定理4 ：若a i b ( 1 i l o dm 1 ) ，a b ( m o dm 2 ) ，a i b ( m o dm ) ，则： 数学背景 a 三bm o d ( m l 【1 2 m t ) 。 2 2 素数的产生 公开密钥算法需要素数，任何合理规模的网络也需要许多这样的素 数。下面衙单介绍产生素数的一些基本算法： 2 2 1 s o l o v a g s t r a s s e n 算法 r o b e r ts o l o v a g 和v o l k e rs t r a s s e n 开发了一种概率的基本测试 方法【”。这个算法使用了雅可比函数来测试p 是否为素数： ( 1 ) 选择一个小于p 的随机数a ； ( 2 ) 如果g c d ( a ，p ) l ，那么p 通不过测试，它是合数； ( 3 ) 计算j = a ( p n 7 2m o dp ； ( 4 ) 计算雅可比符号j ( a ，p ) ； 5 ) 如果j j ( a ，p ) ，那么p 肯定不是素数； ( 6 ) 如果j = j ( a ，p ) ，那么p 不是素数的可能性至多是5 0 。 数a 被称为一个证据( w i t n e s s ) ，如果a 不能确定p ，p 肯定不是 素数。如果p 是合数，随机数a 是证据的概率不小于5 0 9 6 。对a 选择t 个不同的随机值，重复t 次这种测试。p 通过所有t 次测试后，它是合 数的可能性不超过1 2 。 2 2 2 l e h 腿n n 算法 另一种更简单的测试是由l e h m a n n 独自研究出的【”。下面是它的测 北京交通大学硕士学位论文 试算法： ( 1 ) 选择一个小于p 的随机数a ： ( 2 ) 计算a 9 “7 2m o dp ； ( 3 ) 如果a ( p 。7 21 i l 或一l ( m o d p ) ，那么p 肯定不是素数： ( 4 ) 如果a 9 。1 7 2i 1 或一1 ( m o dp ) ，那么p 不是素数的可能性至多 是5 0 。 同样，如果p 是合数，随机数a 是p 的证据的概率不小于5 0 。对 a 选择t 个不同的随机值，重复t 次这种测试。如果计算结果等于l 或 者一1 ，并不恒等于l ，那么p 可能是素数所冒的错误风险不超过1 2 。 这是一个很容易而且广泛使用的简单算法，它基于g a r ym i l l e r 的 部分想法，由m i c h lr a b i n 发展”。 首先选择一个待测试的随机数p ，计算b ，b 是2 整除p 一1 的次数 ( 即，2 6 是能整除p 1 的2 的最大幂数) 。然后计算m ，使n = l + 2 6 m 。 ( 1 ) 选择一个小于p 的随机数a ； ( 2 ) 设j = 0 且z = a 4m o dp ； ( 3 ) 如果z = 1 或者z = p 一1 ，那么p 通过测试，可能是素数； ( 4 ) 如果j o 且z = l ，那么p 不是素数。 ( 5 ) 设j - j + 1 ，如果j ( b 且z p 一1 ，设z = z 2 m o d p ，然后回 到( 4 ) 步。如果z = p 一1 ，那么p 通过测试，可能是素数； ( 6 ) 如果j = b 且z p 一1 ，那么p 不是素数。这个测试较前一个速 数学背景 度更快。数a 被当成证据的概率为3 4 。这意味着当迭代次数为t 时， 它产生一个假的素数所花费的时间不超过1 ，4 。对于大多数随机数， 几乎9 9 9 肯定a 是证据”。 2 4 小结 本章简单介绍了密码学中数论中有关概念以及因子分解的各种方 式，并讨论了流行的素数产生方式一一s 0 1 0 v a g s t r a s s e n 算法、 l e h m a n n 算法、r a b i n - m i l l e r 算法。并给出了“模运算”中递归算法 和加法链的c 语言实现，为后续的工作打下了基础。 密码学中的随机序列发生器 性的，因此产生的数值序列并不是统计随机的。然而，如果算法很好， 所得的序列就可以通得过许多随机性的合理测试。这些数经常被称为 伪随机数。本章介绍几种伪随机数的实现过程。 3 1 线性同余发生器 到目前为止，使用最广泛的为随机数产生技术是由l e h m e r 首先 提出的一个算法，这个算法称为线形同余方法。这个算法有四个参 数，分别是： m ：模数 a ：乘数 c ：增量 x 。：初始值或种子 随机数序列( x 。) 通过下列迭代方程得到： x 。“=( a ) ( 。+ c ) m o d 如果m 、a 、和x 。都是整数，那么这个技术就将产生一系列的整数， 其中每个都在0 x 。 m 的范围内。 数值m 、a 、c 的选择对于做出一个好的随机数产生器十分关键。 例如考虑a = c = 1 ，这样产生的序列明显不能令人满意。再考虑 a - 7 ，c = 0 ，m - 3 2 和x 。= 1 ，这将产生出序列( 1 、7 、1 7 、2 3 ) ，它也显然 不能令人满意在所有可能的3 2 个值中，这个序列才用了4 个，因而 这个序列被称为具有周期4 如果将a 的值改为5 ，那么序列变为( 1 、 5 、2 5 、2 9 、1 7 、2 1 、9 、1 3 、1 、等等) ，在这里周期增加为8 。 我们希望m 很大，以便可能产生出一个很长序列的不同的随机数 一个常用的准则是将m 选为几乎等于一个给定计算机所能表示的最 北京交通大学硕士学位论文 大非负整数。因而，通常选择的m 值是一个接近或者等于2 3 1 的数。 文献【6 5 】提出了用于评价一个随机数产生器的三种准则： l ：这个函数应该是一个完整周期的产生函数。也就是说，这个函 数应该在重复之前产生0 到m 之间的所有数； 2 ：产生的序列应该看起来是随机的。这个序列本身不是随机的， 因为它是以确定性的方法产生的，但是有许多统计测验可以用来评价 一个序列所具有的随机密度； 3 ：这个函数应该用3 2 b i t 算数高效实现。 只要对a 、“m 选取适当的值，算法就可以通过这三种测验。对 于准则l ，可以证明如果m 是素数而c = 0 ，那么对于一定的a 的值， 这个产生函数的周期就是m l ，只有数值0 不在其中。对于3 2 b i t 算 数来说，m 的一个方便的素数取值是2 ”一l 。因而产生函数就可以写 为： x = ( a x 。) m o d ( 2 “一1 ) 在乘数a 超过2 0 亿的可选数值中，只有不多的几个可以通过所有 三个测验。其中的一个是a _ 75 = 1 6 8 0 7 ，这个数值最初被设计用于 i b m 3 6 0 系列计算机。这个产生器得到了广泛的应用，并且它受到的 测验比其它任何伪随机数产生器都彻底，它经常被推荐用于统计以及 模拟工作。 线性同余算法的优点是，如果对于乘数和模数进行适当的选择，得 到的数值序列从统计意义上看与从集合1 、2 、m 一1 中随机抽取( 但 不重新放回) 的数值序列是无法分辨的但是对于初值x 。的选取之外， 这个算法本身并没有什么随机之处 密码学中的随机序列发生器 由于线性同余发生器是可以预测的，因此应该避免将其用于密码 学中，必须考虑采取其它的伪随机数产生方法。 3 2 线性反馈移位寄存器 移位寄存器序列被用于密码学和编码理论中，这方面已经有很多 报道。自从电子时代开始以来，基于移位寄存器的序列密码己被广泛 的用于军事密码学中。 一个反馈移位寄存器( f e e d b a c ks h i f tr e g i s t e r ) 由两部分组成： 反馈移位寄存器 移位寄存器是个位序列，它的长度用“位”来表示。每次需要一 个位，移位寄存器中所有位向右移一位。新的最左端的位根据寄存器 中其它位计算得到。移位寄存器输出的一个位常常是最低有效位。最 简单的反馈移位寄存器是线性反馈移位寄存器( u n e a rf e e 曲a c ks l l i f t r c g i s t e r ，u s r ) ，反馈函数跟积存器中某些位简单异或。在密码学中， l f s r 是移位积存器中最普通的类型。 3 3 附加式发生器 附加式发生器非常的高效，因为它的随机字取代了随机位，它本 身并不安全，但是可以作为安全发生器的一个改造模块。 发生器的初始状态是一个n 位比特的字：8 位、1 6 位或3 2 位，无 北京交通大学硕士学位论文 论是哪一种令其为x l ，x ：，x 。初始状态就是密钥。发生器 的第i 个字是： x f = ( x f 一。+ x 。曲+ x f 一。+ x i - 卅) m o d2 “ 如果系数a 、b 、c 、m 选择正确，那么发生器的周期将至少是 24 一l 。系数的一个必要条件是用最少的位组成最大长度的l f s r 。 3 4b l u mb 1 u ms h u b 产生器 一个流行的产生安全的伪随机数的方法称为b l u mb 1 u ms h u b ( b b s ) 产生器，这个产生器是用它的研制者的名字命名的【“。它的 密码编码强度也许具有最强的公开证明。这个过程如下所示。首先选 择两个大素数p 和q ，要求它们被4 除的时候都余3 ，也就是说： p 5 q 5 3 ( m o d4 ) 令n = p q ，接着选择一个随机数s ，使得s 与n 互为素数，也就是说 p 和q 都不是s 的因子。那么b b s 产生器就根据下列算法产生一系列 的比特b ；： x o = s2 m o dn f o r i _ l t o o 。 x i = ( x l 一1 ) 2 i n o dn b = = x 因而，每次迭代都取出最低位的比特。下表是摘自文献【3 6 】的 一个表示b b s 操作过程的一个例子。这里，n = 1 9 2 6 4 9 = 3 8 3 5 0 3 ，而 种子s = 1 0 1 3 5 5 。 2 8 北京交通大学硕士学位论文 第四章臌公钥密码体制 著名的r s a 公钥密码体制是在1 9 7 8 年由r l r i v e s t ，a s h a m i r 和 l a d l e m a n 三入共同提出。r s 是最具有代表性的公钥密码体制，由于 算法完善，安全性好，易于实现和理解，r s a 已成为种应用极广的公 钥密码体制。在广泛的应用中，不仅它的实现技术日趋成熟，而且其 安全性逐渐得到证明。由此人们越发对r s a 偏爱有加，并提出了许多 基于r s a 的加强或者变形公钥密码体制。根据不同的应用需要，人们 基于r s a 算法开发了大量的加密方案与产品。例如，i n t e r n e t 所采用 的电子邮件安全协议p g p ( p r e t t y g 0 0 d 跏v a c y ) 将r s a 作为传送会话密 钥和数字签名的标准算法。 虽然r s a 的算法的安全性得到了人们的认可，可是由于r s a 算法所 采用的幂剩余计算耗时太多的问题一直是制约其广泛应用的瓶颈问 题。本章将详细阐述r s a 公钥密码体制的基本思想、算法及其实现， 并且重点讨论了与本课题的算法实现密切相关的r s a 的安全性与速度 问题。 4 1 单向函数 同大多数公钥密码体制一样，r s a 的安全性主要取决于构造其加密 算法的数学函数的求逆的困难性，我们称这样的函数为单向函数。单 向函数在密码学中起一个中心作用。它对公钥密码体制的构造是非常 重要的。单向函数的研究是公钥密码体制理论中的一个重要课题。但 是，虽然很多函数被认为或被相信是单向的，但目前还没有一个函数 能被证明是单向的。下砸介绍一下单向函数的基础知识。 北京交通大学硕士学位论文 解密的有效性以及安全性等问题。下面分别描述r s a 加密算法和r s a 数字签名算法的具体步骤。 4 2 1r s a 加密算法 r s a 加密算法的具体步骤为： a r s a 算法的初始化 系统产生两个大素数p 、q 、“保密) ； p 、q 是两个相异的质数，r 是与( p 一1 ) ( q 1 ) 巨为质数，私钥 便是p 、q 、r ； 计算n = p q ( 公开) ，欧拉函数m ( n ) = 0 1 ) ( q 一1 ) ； 随机选取整数e 作为公钥( 加密密钥) ，满足g 。d ( e ，1 l ( ) ) = k 公 开) ；也即e 与欧拉函数v ( n ) 互为质数； 计算私钥d ( 解密密钥) ，满足e d ；l ( m o d ( v ( n ) ) ) ，也就是说 d = e 。1 m o d ( 1 l r ( 1 1 ) ) 。销毁p 、q 及( n ) 。 b r s a 加密、解密变换 首先将明文分块并数字化，每个数字化明文块的长度不大于 【l o g ：i i 】。然后对每个明文块m ( 0 m n ) 依次进行加、解密变换： 加密变换：使用公钥e 和加密密文m ，即c = m 。( m o dn ) ； 解密变换：使用私钥d 将密文c 解密，获得明文m ，即m = c 4 ( m o dn ) 。 4 2 2r s a 加密算法实例 为了便于理解和掌握r s a 算法的基本思想，我们给出一个简单的 r s a 加密算法实例。 3 2 r s a 公钥密码体制 例1 ：设p = 4 3 ，q = 5 9 ，n = p q = 4 3 s 9 = 2 5 3 7 ，则v ( n ) = 4 2 5 8 = 2 4 3 6 ， 设e = 1 3 ，解方程e d l ( m o d 2 3 4 6 ) 根据欧凡里德扩展算法，有 2 4 3 6 = 1 3 1 8 7 + 5 ，1 3 _ 2 5 + 3 ， 5 ：3 + 2 ，3 1 2 + 1 1 = 3 2 ，2 = 5 3 ，3 = 1 3 2 5 ，5 = 2 4 3 6 1 3 1 8 7 1 = 3 2 = 3 一( 5 3 ) = 2 3 5 、 = 2 ( 1 3 2 5 ) 一5 = 2 1 3 _ 5 5 = 2 1 3 _ 5 ( 2 4 3 6 1 3 1 8 7 ) = 9 3 7 1 3 - 5 2 4 3 6 即9 3 7 1 3 e 1 ( m o d 2 4 3 6 ) 得到d = 9 3 7 设要传送的明文为：p u b l i ck e ye 哪t i o n s 发送方首先将明文分块：p ub l i c k e y e n c r y p t i 0 s 这里使用将英文字母表的序号：即a 为o o ，b 为0 1 ，c 为0 2 ，v 为2 4 ，z 为2 5 。 将明文数字化得： 1 5 2 00 1 1 10 8 0 21 0 d 4 2 4 0 4 1 3 0 2 1 7 2 41 5 1 9 0 8 1 4 1 4 1 8 使用加密变换求得密文：c 铀( m o d n ) 0 0 9 51 6 4 81 4 1 01 2 9 91 3 6 5 1 3 7 92 3 3 32 1 3 21 7 5 11 2 8 9 发送方将密文送给接收方； 接收方将收到的信息解密，m = c 。( r n o dn ) 1 5 2 00 1 1 10 8 0 21 0 0 42 4 0 4 1 3 0 21 7 2 41 5 1 90 8 1 41 4 1 8 得到明文并转换为字母原文。 北京交通大学硕士学位论文 4 2 3r s a 数字签名算法 假定对明文信息m 进行签名，则r s a 的数字签名算法描述如下： 签名过程：发送方使用自己的私钥d 对明文信息m 进行数字签 名变换：s = m 。( m o dn ) ；将加密后的消息m 和签名发送给接收方： 验证过程：接收方使用发送方的公钥e 对收到的消息s 进行数字 签名验涯变换：m = s 。伍如d n ) ；并使用发送方的公钥解密恢复消息m ， 比较m 与m ，如果m 。= m 则证实发送方的身份合法。 r s a 数字签名的优点是易于实现，并且可以和加密算法相结合。 但是，r s a 数字签名算法的容易导致以下的攻击： 任何人都可以通过对某一y 计算x = y ( m o dn ) 伪造一个随机消息 x 关于某合法用户u 的签名y ，这是因为y = x 4 ( m o dn ) ； 如果消息x 1 和x2 的签名分别是y l 和y2 ，则拥有x l ，y 1 ，x2 ， y ：的任何人都可以伪造合法用户u 关于消息x 。x 2 的签名y 。y ：。这是 因为对任意的消息x 。和x ：，总有( x 。x ：) 4 ( m o dn ) 一( ( ( x 。( m o d ) ) ( x2 。( m o d n ) ) ) ( m o dn ) ： 签名者每次只能签名【l o g ：n 】比特长的消息，获得同样长的签 名。一般说来，如果所要签的消息很长，签名前只能把消息分成【l o g ：n 】 大小的分组，逐组进行签名。由于r s a 数字签名中基本运算都是大数 模乘和大数模幂运算，这样做的缺陷是速度慢，而且签名太长，降低 系统的时空效率。 克服上述三个缺陷的办法之一是在对明文消息进行签名之前做变 r s a 公钥密码体制 换，一般可以采用杂凑函数。 4 3r s a 的安全性 理论上，r s a 的安全性取决于因式分解大数模n 的困难性。从严 格的技术角度上来说这是不正确的，在数学上至今还未证明分解模数 就是攻击r s a 的最佳方法。事实情况是，大整数因子分解问题过去数 百年来一直是令数学家头疼而为能有效解决的世界性难题。人们设想 了一些非因子分解的途径来攻击r s a 体制，但这些方法都不比分解n 来得容易。因此，严格地说，r s a 的安全性基于求解其单向函数的逆 的困难性。r s a 单向函数求逆的安全性没有真正因式分解模数n 的安 全性高，而且目前人们也无法证明这两者等价。许多研究人员都试图 改进r s a 体制使它的安全性等价于因式分解模数n 。 r s a 算法从提出到现在已经有2 0 多年的时间了，广泛的应用证明 r s a 体制的安全性是相当可靠的。但是在特定的条件下，r s a 的实现 细节的漏洞会导致对r s a 算法的攻击。但是，通过精心考虑r s a 体制 实现的细节是可以避免这些安全性缺陷的。 对r s a 算法的攻击主要有以下几种： 4 3 1 对r s a 的分解模数n 攻击 分解模数n 是最直接的攻击方法，也是最困难的方法。攻击者可以 获得公开密钥e 和模数n ；如果模数n = p q 被因式分解，则攻击者通 过p ，q 便可计算出1 l ，( n ) = ( p 一1 ) “一1 ) ，进而由e d 1 ( m o d v ( n ) ) 而得 到解密密钥d 。大整数分解研究一直是数论与密码理论研究的重要课 题。 r s a 公钥密码体制 伪造合法签名。攻击者利用自己伪造的两个消息x 。和x ：来拼凑 出所需要的x 3 5 ( x l x2 ) ( m o dn ) 。攻击者如果得到用户u 对x 。和xz 的 签名x t4 ( m o dn ) 和x2 。( m o dn ) 就可以计算x ，的签名，x34 ( m o d n ) = “x 1 。( m o d n ) ) ( x24 ( m o d n ) ) ) m o d 。 通过对明文消息使用