更改格式后十二张强密码技术浅.doc

四川理工学院成都新华学院毕业论文（设计）课题名称： 密码技术浅析 年级专业： 2010级计算机软件技术 学 号： 10503011143 姓 名： 张 强 指导教师： 陈 侠 2013年 X 月 XX 日四川理工学院成都新华学院毕 业 论 文（设计）任 务 书姓 名张强学 号105030111432010年级计算机软件技术 专业题 目密码技术浅析设计任务网络安全日益得到大众的重视，在这个杀毒软件总是跟在病毒后面跑的现实中，如何能更有效的保护好个人的资料。密码技术是解决这个问题的有效手段之一。请分析目前网络中面临的问题，阐述密码技术的原理，提出相应的解决措施。时间进度主要参考文献 和原始资料(1) 密码学理论与技术主编 范明钰，王光卫 清华大学出版社 2008 10(2) RSA算法缺陷分析主编 杨云江 贵州大学学报(自然科学版)，贵州大学，2006 2(3) 密码学与网络安全(美) BEHROUZ A. FOROUAAN 著 清华大学出版社 2009(4)加密与解码:密码技术剖析与实战应用 许主洪编 著 人民邮电出版社 2002(5)应用密码学:协议、算法与C源程序 (美)B.施奈尔Bruce Schneier著 机械工业出版社 2000(6)RSA算法的安全性分析王启明 王一凡 著 中南民族学院学报(自然科学版)，华中理工大学，2000 9 指导教师：陈侠2013年XX 月 XX 日摘 要密码学是信息安全的重要技术，是用于保护国家机密及决策的一个重要工具，也是保护个人信息以及其他重要资料的重要方法。可以有效保障信息的机密性、完整性和鉴别。密码学的研究涉及到很多技术的学习，主要包括怎样把数据加密，怎样传送加密数据，怎样解密加密的数据，使需要数据的合法者得到自己要的数据。关键词关键词：RSA；RSA算法；加密；解密；非对称密钥；密码学；公钥；私钥。AbstractCryptography is an important information security technologies for protection of state secrets and an important tool for decision-making is also important to protect personal information and other information important way. Information can effectively protect the confidentiality, integrity and differentiation. Cryptography research involves many technical learning, including how to data encryption and how to send encrypted data, how to decrypt the encrypted data, so that the legitimate needs of those who have their own data to the data.Keywords : RSA; RSA algorithm; encryption; decryption; non-symmetric key; cryptography; public key; private key.目 录1 密码学的概述21.1 密码学的基本术语 21.1.1 密码学 21.1.2 密钥 21.1.3 加密与解密 31.1.4 密码体制 31.2 密码学的应用 31.3 密码算法的概念及其分类 41.3.1 对称密码算法 41.3.2 公开密钥算法 41.3.1 Hash算法 51.4 密码编码学的基本概念 51.5 密码分析学的基本概念 61.6 密码学的信息论基础 61.7 密码学的起源和发展 72 公钥密码体制基础82.1 整数算法 62.1.1 二进制运算62.1.2 整数除法72.2 模运算 82.2.1 模算符 82.2.2 余集 82.2.3 同余 92.2.4 在集合Zn当中的运算92.2.5 逆102.2.6 在集合Zn当中的运算 112.3素数 112.3.1 定义122.3.2 素数的基数122.3.3 素数检验122.4 中国剩余定理122.5 指数与对数132.5.1 指数13 2.5.2 对数133 RSA密码系统153.1 RSA简介 153.2 RSA的加解密过程及算法分析 153.3 RSA的安全分析 183.3.1 针对RSA的攻击183.3.2 因数分解攻击183.3.3 选择密文攻击193.3.4对加密指数攻击 193.3.5对模的攻击 203.4 使用RSA的意义214 RSA的C程序实现224.1 RSA编程设计 22结束语 28致 谢 29参考文献 30前 言信息社会中，每天都有大量的信息在传输、交换、存储和处理，而这些处理过程几乎都要以来强大的计算机系统来完成，一旦计算机系统发生安全问题，就可能造成信息的丢失、篡改、伪造、假冒，以及系统遭受坏等严重后果，因此，如何保证计算机系统的安全，是当前一个需要立即解决的十分严峻的问题。通常保障信息安全的方法有两大类：一是以防火墙技术为代表的被动防卫型，二是建立在数据加密，用户授权确认机制上的开放型网络安全保障技术。第二种就要采用密码学的知识来解决。密码学是一门既古老又年轻的科学，它最早的应用可以追溯到几千年前的古罗马，但成为一门独立的学科则是从近几十年才开始的。1949年Shannon发表的保密系统的信息理论和1976年Diffie和Hellman的密码学的新方向首次提出的公钥密码思想奠定了现在密码学的理论基础。1977年美国加密数据加密标准DES的正式发布和1977年R.L.Rivest，Shamir，L.Adleman三人共同提出的第一个公钥密码思想的密码体制-RSA公钥密码成为现在密码学研究迅速发展的两个里程碑。根据加密密钥和解密密钥是否相同或者本质上等同，即从其中一个容易推出另一个，可将现有的加密体制分为两种。一种是单钥加密体制，其典型代表是美国的数据加密标准DES（DataEncryptionStandard）；另一种是公钥密码体制，其典型代表是RSA密码体制。我这次的论文主要就是研究RSA的算法和算法的程序实现。自19世纪以来，由于电报特别是无线电报的广泛使用，为密码通信和第三者的截收都提供了极为有利的条件。通信保密和侦收破译形成了一条斗争十分激烈的隐蔽战线。1917年，英国破译了德国外长齐默尔曼的电报，促成了美国对德宣战。1942年，美国从破译日本海军密报中，获悉日军对中途岛地区的作战意图和兵力部署，从而能以劣势兵力击破日本海军的主力，扭转了太平洋地区的战局。在保卫英伦三岛和其他许多著名的历史事件中，密码破译的成功都起到了极其重要的作用，这些事例也从反面说明了密码保密的重要地位和意义。1 密码学的概述1.1密码学的基本术语1.1.1密码学密码学（cryptography），它是一门研究秘密书写的科学，是以认识密码变换的本质、研究密码保密与破译的基本规律为对象的学科。密码的另一种定义是一门与信息安全密切相关的数学科学，是信息安全的核心。密码提供的最基础的服务是使合法通信者进行信息的交换，而其他人员难以获得通信内容。密码学一般包括两个对立统一的分支学科：密码编码学和密码分析学。研究密码变化的客观规律，应用于编制密码以保守通信秘密的，称为编码学；应用于破译密码以获取通信情报的，称为破译学，总称密码学。密码编码学与密码分析学相辅相成，共处于密码学的统一体中。现代密码学除了包括密码编码学和密码分析学两个主要的学科外，还包括一个新产生的分支密码密钥学。它是以密码体系最核心部分的密钥作为研究对象的学科。密钥管理是一种规程，它包括密钥的产生、分配、存储、保护、销毁等环节，因而在密码管理体系中密钥管理至关重要。上述三个分支学科构成了现代密码学的主要科学体系。密码在早期仅对文字或数码进行加、脱密变换，随着通信技术的发展，对语音、图像、数据等都可实施加、解密变换。1.1.2密钥明文到密文的转换往往由一些特殊的函数完成，控制这些函数的参数称为密钥，用K表示。所谓密钥，是指由用户事先选定的较短的字符或数字序列，其作用近似于打开保险箱的钥匙。所有密钥的集合构成密钥空间，用SK表示。密钥空间中不相同密钥的个数称为密钥体制的密钥量，它是衡量密码体制安全性的一个重要指标。密钥是一个数值，它和加密算法一起生成特别的密文。密钥本质上是非常非常大的数。密钥的长度尺寸用比特来衡量。在公开密钥加密方法中，密钥的长度越大，密文就越安全。在同种加密算法中，密钥越大越安全。但是传统方法和公开密钥方法所用的加密算法不一样，因此它们的密钥尺寸不能直接比较。公钥和私钥是算术相关的，仅凭公钥推算出私钥是困难的。然而如果有足够的时间和计算能力，总是可能导出私钥的。这使得选择合适尺寸的密钥变得非常重要。为了安全需要足够大的密钥，而为了速度则要用小的密钥1.1.3加密与解密加密是在密钥K的作用下，把明文P从明文信息空间SP对应到密文信息空间SC的一种变换，明文和密文的关系可表示为CEK（P）。密文传送到接收者，合法用户利用密钥对密文C进行与加密变换相反的逆变换，称为解密变换，用DK表示。解密变换是把密文C从密文信息空间SC对应到明文信息空间SP的变换。逆变换的过程称为解密或译密。解密变换的目的是恢复出明文P：P=DK（C）DKEK（P）。上式中的EK和DK为可逆变换对。K不同，EK和DK也不同。可见，信息的保密性完全依赖于密钥K的保密性。1.1.4密码体制一个完整的密码体制（cryptosystem）由5部分组成：明文信息空间SP、密文信息空间SC、密钥空间SK、加密变换族EK、解密变换族DK。密码体制应满足以下3个一般性要求：加解密变换对所有密钥都一致有效；体制必须是简单易行的，应易于找到密钥用于逆变换；体制的安全性仅依赖于密钥的保密性而不能依赖于加、解密算法的强度。一个好的密码体制则应至少满足以下两个条件：在已知明文P和密钥K时，计算CEK（P）容易；在已知密文C和密钥K时，计算PDK（C）容易。在不知密钥K时，不可能由密文C推知明文P。对于一个密码体制，如果能够根据密文确定明文或密钥，或者能够根据明文及其生成的密文确定密钥，这个密码体制就是可以破译的，反之则为不可破译的。1.2密码学的应用在很长的时间内，密码仅限于军事、政治和外交的用途，其知识和经验也仅掌握在与军事、政治和外交有关的密码机关手中，再加上通信手段比较落后，故不论密码理论还是密码技术发展都很缓慢。随着科学技术的进步，信息交换的手段越来越先进，信息交换的速度越来越快，信息交换的内容越来越广泛，信息交换的形式越来越多样化，信息交换的规模也越来越大。到了20世纪70年代，随着信息的激增，对信息保密的需求也从军事、政治和外交等领域，逐步扩展到民用和商用领域，从而导致了密码学知识的广泛传播。计算机技术和微电子技术的发展，为密码学理论的研究和实现提供了强有力的手段和工具。进入20世纪80年代以后，随着网络的兴起，对密码理论和技术的研究更是呈爆炸性增长的趋势，密码学在雷达、导航、遥控、遥测等领域占有重要地位。除此之外，密码学正渗透到通信、电力、金融、医疗、卫生、交通等各行业的管理信息系统，甚至到个人和家庭等领域，而且保密的作用也已不再仅仅是保密，还有认证、完整性检验和抗抵赖等新的功能。对普通的家庭来说，生活中许多地方需要保密，如各种银行密码、信用卡密码、网络账号和密码等。1.3密码算法的概念及其分类密码算法也叫密码，是用于加密和解密的数学函数。通常情况下，有两个相关的函数，一个用作加密，另一个用作解密。如果算法的保密性是依赖于保持密钥的秘密，这种算法称为非受限制的算法，也称基于密钥的算法。在非受限密码算法中，根据密钥的特点，加密算法分为两类：秘密密钥算法和公开密钥算法。现在的密码学算法一般基本上都是，非限制算法！1.3.1对称密码算法秘密密钥算法通常称之为对称密码算法或传统密码算法，也称单密钥算法。对称密码算法要求发送者和接收者在安全通信之前，商定一个密钥。其算法的安全性依赖于密钥，密钥一旦泄露，整个安全系统都要崩溃。换句话说，在使用对称密码加密算法时，只要通信需要保密，密钥就必须保密。对称算法可分为两类。一类只对明文中的单个比特（有时对字节）运算的算法称为序列算法或序列密码。另一类算法是对明文的一组比特运行运算，这些比特组称为分组，相应的算法称为分组算法或分组密码。1.3.2公开密钥算法公开密钥算法也叫非对称密码算法或双密钥算法。公开密钥加密法可以解决密钥发布的问题，公开密钥的概念由Whitfield Diffie和Martin Hellman在1975年提出。现在也有证据表明英国情报机关先于Diffie和Hellman几年发明了这种方法，但是却作为军事秘密不为人知，并且没有什么有价值的成果。公开密钥算法不要求通信双方共享一个密钥，其用作加密的密钥不同于用作解密的密钥，而且解密密钥不能根据解密密钥计算出来。用于加密的密钥可向所有使用者公开，使用加密密钥加密后的信息只有用相对应的解密密钥才可解密。公钥加密法的主要优势在于可以让事先没有安全通道的人安全地交换信息。收发双方通过安全通道共享密钥的前提条件不存在了，所有的通信中只包含了公钥，私钥是不会传输或共享的。公钥加密法是加密技术的革命，它可以为普通人提供较强的加密手段，因而可以说公钥加密法是密码学发展史上的一个里程碑。1.3.3 Hash算法Hash算法也称为消息摘要或单向函数，是密码学中的一种重要的算法。它是许多安全认证协议的重要组成部分，是实现有效、安全可靠的数字签名和认证的重要工具。Hash算法是一种将任意长度的输入消息计算产生出一个固定长度的输出的数学变换，即消息m的Hash为h（m）。这类算法具有以下特点：对于任何消息，计算h（m）相对来说较为容易，这意味着要使用该函数，并不需要占用太多的计算时间。给定h（m），寻找一个消息使得其Hash值为h（m）的难度与穷举所有可能的m并计算h（m）的难度相比，不会有明显的差别。虽然理论上存在很多不同数值，其Hash值都是h（m），但是要找到两个Hash结果相同的数值，从计算的角度来说是很困难的。要从密码学的角度认为一个Hash函数是安全的，其必备条件如下：找到一个消息，使其消息摘要为一预先给定的消息摘要值，在计算上是不可行的；以现有的计算能力，不可能找到两个具有相同消息摘要的消息；给定一个消息，不可能找到另一个消息与其具有相同的消息摘要。1.4密码编码学的基本概念密码编码学的主要目的是确保明文、密钥等秘密信息不被窃听者及攻击者窃听或破译。密码编码学希望能够解决在下述环境下即信息的存储（可能为非授权者接触）、信息的交换（可能被冒用或抵赖）以及信息的传输（可能被截获）过程中，信息的安全保护问题。密码编码系统应具有以下独立的特征：（1）转换明文为密文的运算类型有的算法的保密性可能依赖于保护算法本身，称为受限制的密码算法；也有的算法仅依赖于使用算法时所采用的密钥，称为基于密钥的密码算法。（2）所用的密钥类型如果发送方和接收方使用相同的密钥，这种密码称为对称密码、单密钥密码或传统密码。如果发、收双方使用不同的密钥，这种密码就称为非对称密码、双钥密码或公钥密码。（3）处理明文的方法分组密码每次处理一个输入分组，相应地输出一个输出分组。而序列（流）密码是连续地处理输入元素，每次输出一个元素。1.5密码分析学的基本概念密码分析学，是一门研究在不知道通常解密所需要的秘密信息的情况下对加密的信息进行解密的学问。通常，这需要寻找一个秘密的钥匙。密码分析的目标在密码学的历史上从古至今都一样，实际使用的方法和技巧却随着密码学变得越来越复杂而日新月异。密码学算法和协议从古代只利用纸笔等工具，发展到第二次世界大战时的恩尼格玛密码机，直到目前的基于电子计算机的方案。而密码分析也随之改变了。无限制地成功破解密码已经不再可能。在上个世纪70年代中期，公钥密码学作为一个新兴的密码学分支发展起来了。而用来破解这些公钥系统的方法则和以往完全不同，通常需要解决精心构造出来的纯数学问题。其中最著名的就是大数的质因数分解。1.6密码学的信息论基础1949年，Shannon以其在信息论方面的基本著作为依据，为密码学提供了理论基础。依据已经收到的密文来得到的明文的不确定性，来度量密码在理论上的保密度。如果不论截取了多少密文，对明文仍然一无所知，则此密码达到完全保密。所有现用密码都会在密文中留下一些有关明文的信息（唯一例外是一次一密）。随着密文长度的增加，明文的不确定性通常会下降，最后到零，此时意味着，有足够的信息来唯一地确定明文，这样，此密码至少在理论上是可破译的。只要有数百比特长的明文，大多数密码在理论上是可破译的。但这并不意味着这些密码不安全，因为要确定明文在计算上的耗费，可能会超过可利用的资源。因此，重要的问题不在于密码是否绝对安全，而是计算上是否安全。1.7密码学的起源和发展密码学在公元前400多年就早已产生了，密码学的起源的确要追溯到人类刚刚出现，并且尝试去学习如何通信的时候。为了确保通信的机密，最先是有意识地使用一些简单的方法来加密信息，通过一些（密码）象形文字相互传达信息。接着由于表音和表意文字的出现和使用，确保通信的机密性就成为一种艺术，古代发明了不少加密信息和传达信息的方法。密码学真正成为科学是在19世纪末和20世纪初期，特别是两次世界大战中对军事信息保密传递和破获敌方信息的需求，密码学得到了空前的发展，并广泛用于军事情报部门的决策。20世纪初，随着技术的进步，产生了最初的可以实用的机械式和电动式密码机，同时出现了商业密码机公司和市场。这一阶段又称为机械密码时代。在计算机出现以前，密码算法主要是通过字符之间代替或易位实现的，我们统称这些密码体制为古典密码。这些密码算法的使用和分析破译，为今天电子时代尤其是网络时代的密码算法提供了坚实有力的理论基础。20世纪60年代后，电子技术的发展，使得基于复杂计算的密码成为可能。这一阶段电子密码机得到较快的发展和广泛的应用，使密码学的发展进入了一个新的阶段。同时充分利用了古典密码留下来的经验，对于算法的设计有了更科学的思路。密码破译是随着密码的使用而逐步产生和发展的。1412年，波斯人卡勒卡尚迪所编的百科全书中载有破译简单代替密码的方法。到16世纪末期，欧洲一些国家设有专职的破译人员，以破译截获的密信。密码破译技术有了一定的发展。1949年美国人香农发表了秘密体制的通信理论一文，应用信息论的原理分析了密码学中的一些基本问题。2 公钥密码体制基础2.1整数算法2.1.1二进制运算在密码学中，我们感兴趣的主要是三种应用于整数集的二进制运算。二进制运算用两个输入创建一个输出。三种普通的二进制运算分别是：加法、减法和乘法。每种运算都是利用两个输入(a和b)并创建一个输出(c)。两个输入来自整数集，输出也进入整数集。在该范畴内除法是不适用的，因为正像我们了解到的那样，除法产生两个输出而不是一个。2.1.2整数除法在整数计算中，如果我们用n除a，就会得到q和r。这4个整数之间的关系表示如下：。在这种关系中，a是被除数，q是商，n是除数，r是余数。这不是运算，因为a除以n的结果是两个整数q和r，我们只能称其为除法关系。在密码学中，当我们运用以上的除法关系时，要有两种限制。首先，要求除数是正数；其次，要求余数是非负数。我们使用计算机或计算器的时候，如果a是负数，r和q就是负数。那我们如何去满足r必须是正数这个限制要求呢？解决的方法很简单，q的值减1然后再把n的值和r相加，就可以使其变为正值。如：-255=(-23 11)+ (2) -255 = (-24 11) + 9 。用23去减1就得出24，把11和2相加得9。上述关系依然是正确的。2.2模运算在以上讨论的除法关系(a=qn+r)中有两个输入(a和n)和两个输出(q和r)。在模运算中，我们只对一个输出有兴趣，那就是余数r，并不关心商q的值是多少。换句话说，我们想要知道的是a除以n时，r的值是多少。这就表明，我们利用两个输入a和n和一个输出r，可以将上述关系更改为二进制算符。2.2.1模算符上述二进制算符被称为模算符，表示为mod。第二个输入(n)称为模数，输出r称为余数。模算符(mod)从集合Z和一个正的模(n)中取出一个整数(a)。算符就会创建一个不小于零的余数(r)。我们有。2.2.2余集：Zn对模数n的模运算结果总是一个在0到n1之间的整数。换句话说，的结果总是一个小于n的非负数。也可以说模运算创建了一个集，这种集在模运算中称为最小余数集n，或Zn。不过，还要记住，虽然只有一个整数集(Z)，但是对于每一个n值，却有多个余数集(Zn)。2.2.3同余在密码学中，我们经常用同余这个概念而不是不等式。从Z到Zn的映射不是一一对应的。Z的无穷多个元素可以向Zn的一个元素映射。例如、等。在模算法中，像2、12和22这样的整数称为同余模10。为了表明这两个整数是同余，我们使用同余算符()。我们把段()加到同余的右边，来确定使关系成立的模的值。如我们写作：，。同余的概念有几点需要解释。(1)同余算符看起来像等号，其实是有区别的。首先，等号是把Z集合的一个元素向它本身映射，而同余算符是把Z集合的一个元素向集合Zn映射。其次，等号是一对一的，同余算符是多对一的。(2)插在同余算符右侧的段(mod n)只表示目标集合(Zn)，加这个符号是为了表明模是用作映射的。这里使用符号mod和二进制算符的意义并不相同。换句话说，在中，符号mod是一个算符，段(mod10)在中是指目标集Z10。2.2.4在集合Zn当中的运算l 性质我们提到，在模运算中对于三个二进制运算的两个输入可能来自集合Z或Zn。下面的两个性质允许我们在应用三种二进制运算(+、-、)之前，先把两个输入映射于Zn(如果来自于Z话)中。性质1：性质2：性质3：下图就是在应用上述性质之前或之后的过程。如果我们应用上述性质，如图所示过程是比较长的，但是应当记住，在密码学中要处理的整数都是非常大的。例如，如果要把一个非常大的整数乘以另一个非常大的整数，也许会产生特别大的整数，以至计算机中不能储存。在进行乘法运算之前，应用以上性质可以使开始的两步运算简化，性质为我们使用较小整数提供了可能。Z或Zn+ 、-、 modnZn=0,1,2. . . .，（n-1）Z或Znnmodmod+ 、-、 modnZn=0,1,2. . . .，（n-1）a mod nb mod nna.原过程 b.应用性质模算符的性质图下面是上述性质的应用：(1)(1723345+2124945)mod11=(8+9)mod11=6(2)(1723345-2124945)mod16=(8-9)mod11=10(3)(17233452124945)mod16=(89)mod11=62.2.5逆我们在做模运算时，常常需要求与某种运算相关的一个数的逆。通常就是求一个加法逆(与加法运算有关)或者乘法逆(与乘法运算有关)。l 加法逆在Zn中，如果a+b=0(mod n)成立，则数字a和b互为加法逆。如果在集合Zn中，a的加法逆可以按b=n-a计算，那么在集合Zn中，a和b互为加法逆。例如，在集合Z10中，4的加法逆就是10-4=6。在模算法中，每一个整数都有一个加法逆。一个整数与其加法逆的和与同余。在模运算中，每个数都有一个加法逆而且这个逆是唯一的；每个数都有且仅有一个加法逆。不过，数的逆也可能是数本身。如Z10的6对加法逆是(0，0)、(1，9)、(2，8)、(3，7)、(4，6)和(5，5)。表中，0和5是其本身的加法逆。注意，加法逆是相互的，如果4是6的加法逆，那么6也是4的加法逆。l 乘法逆在集合Zn中，如果成立，则两个数a和b互为乘法逆。如果模是10，那么3的乘法逆就是7。也就是说我们有(37)mod10=1。在模运算中，一个整数也许有乘法逆也许没有乘法逆。如果有乘法逆，整数与其乘法逆的乘积与同余。可以证明，在集合Zn中当且仅当gcd(n，a)=1时，a具有一个乘法逆。如求集合Z10中8就没有乘法逆。因为gcd(10，8)=21，所以没有乘法逆。换言之，我们不能求出任意一个0到9之间的数字，使得它乘以8时，结果与1同余。在前面讨论的扩展Euclidean算法中，如果给定n和b且b在Zn中有逆，就可以求出b在集合Zn中的乘法逆。为了把这一点表示出来，我们用n(模数)代替第一个整数a。我们可以说算法能求出s和t，使得成立。然而，如果b的乘法逆存在，gcd(n，b)必为1。关系是：(sn)+(bt)=1，现在，我们在两边都使用模算符。也就是说，每一边都映射到Zn。我们有：在Zn中t是b的乘法逆当n和b给定且gcd(n，b)=1时，用扩展Euclidean算法可以求Zn中b的乘法逆。b的乘法逆就是t映射于Zn之后的值。注意，在第三行中(sn)modn为0，因为(sn)除以n的商为s，余数为0。2.2.6加法集和乘法集的不同在密码学中我们常常用逆来运算。如果发送方使用一个整数(作为加密密钥)，接收方就用该整数的逆(作为解密密钥)。如果这种算法(加密/解密算法)是加法，Zn就可以当作可能密钥的集，因为该集合中的每个整数都具有一个加法逆。另一方面，如果运算(加密或解密算法)是乘法，就不能成为可能密钥的集，因为该集合中仅有一部分元素具有乘法逆。我们需要另外一个集合，这个新集合是Zn的子集，仅包含Zn中具有乘法逆的整数。这个集合就称为Zn*。2.3 素数2.3.1 定义非对称密钥密码需要广泛运用素数。正整数可以分为三类：1、素数和复合数。一个正整数如果能被且只能被1和它本身整除，那么这个数就是一个素数(prime)。复合数就是具有两个以上约数的正整数。素数只能被1和它自身整除。如果gcd(a，b)=1，两个正整数a和b就称为互素数或互质数。注意，数1与任意整数互素。如果p是一个素数，那么1到p-1所有的整数都与p互素。之前我们讨论了集合Zn*，其元素都与n互素。除mod（p）是素数以外，集合Zp*也是这样。2.3.2 素数的基数说明了素数的概念之后，自然就会提出两个问题：素数的个数是有限的还是无限的？给定一个数n，小于或等于它的素数有多少个？素数的个数是无限的。这里有一个非正式的证明：假定素数的集合是有限的，设p是最大的素数。把这个素数集合成倍扩大，并调用结果P=23 p。整数(P+1)不可能有一个素因数。因为我们知道q可以整除P，如果q也可以整除(P+1)，那么就可以整除(P+1)-p=1，可以整除1的数只有一个那就是1，1不是素数，所以。如此则与假设矛盾，所以素数集合是无限的。为了回答第二个问题，要定义一个可以求出小于或等于n的素数的函数，称为p(n)。下面所示的就是这个函数对于不同n的值。但是如果n是非常大的，我们怎样才能算出p(n)呢？答案是我们只能运用近似算法。表示如下：这个上限值是Gauss发现的，Lagrange发现了下限。2.3.3 素性检验我们想到的下一个问题就是：给定一个数n，怎样才能确定n是不是素数呢？答案是我们需要知道这个数能不能被任意大于1小于的整数整除。不能就是素数，否则就不是。我们仅知道这种方法效率不高，但这也是个好的开头。2.4中国剩余定理中国剩余定理(CRT)用来解决一组带有两两互素数的一个变量和不同模的同余方程。中国剩余定理表明，如果模互素，上述方程具有唯一的解。要注意，即使模不是相关素数但适应另一种条件，方程组也可以只有一个解。不过在密码学中，我们只对运用互素的模解方程有兴趣。中国剩余定理在密码学中有几种应用。一种应用是解二次同余方程，像在下一部分中讨论的那样；另一种是根据一列小整数，提出一个非常大的整数。2.5指数与对数指数和对数是互逆的。下面就表示出了它们之间的关系，其中a称为指数或对数的底数。指数y =ax对数:x=logay2.5.1 指数在密码学中，一个普通的模运算是指数的，即我们通常要计算：，我们将在讨论的RSA密码系统，运用指数非常大的求幂运算进行加密和解密。遗憾的是，大多数计算机语言还没有可以有效计算求幂的算符，特别是当指数很大的时候更是如此。为了使这类计算更为有效，我们就需要有更有效的算法。快速求幂运用平方乘方法是可能的。在传统算法中，只用乘法来模拟求幂，但是，快速求幂算法既运用平方也运用乘法。这种方法的主要想法就是把指数当作nb比特(x0到xnb -1)的二进制数来处理，例如x=22=(10110)2。注意，y是nb项的乘积。每一项既是1(如果相关的比特是0)也是a2i(如果相关的比特是1)。也就是说，如果比特是1，a2i这一项包含在乘积当中；如果比特是0(乘以1是没有作用的)，就不包含在乘法当中。我们可以对底数连续平方，a，a2，a4。如果相关的比特是0，这一项就不包括在乘法过程中；如果比特是1，就包括在乘法过程中。选择性算法，注意算法左到右(最不重要的到最重要的)检验了x中比特的值。运用相反的阶次就可以写出一个算法。因为平方运算是完全独立于乘法运算的，我们就选出了上述算法。它们可以做并行，在提高过程速度的同时就能完成这些运算。2.5.2对数在密码学中，我们也需要讨论模对数。如果我们运用指数运算来加密和解密，对手就可以运用对数进行攻击。我们需要知道指数运算的逆运算的难度。我们可能会想起的第一种解决办法就是解x=logay (mod n)。我们可以写一个算法继续计算，直到求出给定的y的值。详细分析见第三章的3.2加解密过程及算法分析。3 RSA密码系统3.1 RSA简介公钥密码算法最主要的特点是加密和解密使用不同的密钥，且加密密钥能公开，而仅需保守解密密钥的机密的密码算法。在这种加密算法中，从公开的加密密钥无法推导出保密的解密密钥，也无法从加密密钥和密文恢复出相应的明文。最有影响的公钥密码算法是RSA，它能抵抗到目前为止己知的所有密码攻击。RSA算法是第一个既能用于数据加密也能用于数字签名的算法，算法的名字以发明者的名字命名。RSA算法的安全性依赖于大数分解问题的难解性。算法中使用的公钥和私钥都是两个大素数（大于100个十进制位）的函数。据猜测，从一个密钥和密文推断出明文的难度等同于分解两个大素数的积【5】。3.2 RSA的加解密过程及算法分析(1)随机选择两个大素数p和q；以时间作为随机种子，在电脑里生成随机整数，并且每次生成的随机数都不一样，再通过函数来控制生成随机的两个大素数（并用素数检测法检测是否是强伪素数）。检验的伪代码为：Miller_Rabin_Test (n，a)/n是数字；a是基数。 求 m和k使得 n- 1 = m2kT am mod nif (T = 1) 返回 一个素数for(i 1 to k- 1) / k-1是步骤中的最大数.T T2 mod nif(T=+1) 返回 一个复合数if(T=-1) 返回一个素数返回n一个复合数。(2)计算乘积n=p*q和=(p-1)(q-1)；(3)选择一个大于1而小于的随机整数e，使得gcd(e，)=1；并采用欧几里德算法和Stein算法求最大公约数。设明文为m则，密文。(4)计算d使得；这里我们可以这样理解：已知a、b，求x，满足a*x=1(mod b)，相当于求解a*x-b*y=1的最小整数解。用扩展的欧几里德算法来求d。扩展欧几里德算法解线性方程ax-by=c。问题转化为：已知a、b、c，求解使等式ax-by=c，成立的一组x，y。其中a、b、c、x、y均为整数。a，b的最大公约数为gcd(a，b)。如果c不是gcd(a，b)的倍数，则该等式无解，因为等式左边除以gcd(a，b)是整数，而等式右边除以gcd(a，b)后为小数。因此，只有当c是gcd(a，b)的倍数的时候，该等式有解。这样，可以通过计算使ax1+by1=gcd(a，b)成立的x1、y1，然后有x=(c/gcd(a，b)*x1，y=(c/gcd(a，b)*y1，得到x，y。问题就被转换为求使ax+by=gcd(a，b)成立的一组x，y。这可以用扩展欧几里德算法求解。求解过程如下：如果b为零，则gcd(a，b)=a，那么x=1，y=0为一组解。当然在RSA中b参数是不会等于0的。如果b不为零，根据欧几里德定理，可以设ax1+by1=gcd(a，b)=gcd(b，a%b)=bx2+(a%b)y2=bx2+(a-(a/b)*b)y2化简后有x1=y2，y1=x2-(a/b)y2。因此x1，y1依赖于x2，y2，同理依次类推递归调用求出x3，y3，x4，y4，类似于辗转相除，直到b=0时，求出xn，yn，便可以推出x1，y1的值。扩展欧几里德算法：扩展欧几里德算法，解gcd(a，b)=ax+by，结果存储在x，y中，用户调用时保证a、b、c都是整数返回a，b的最大公约数int extended_euclid(int a，int b，int &x，int &y)if(b=0) / gcd(a，b)=ax=1；y=0；return a；int n = extended_euclid(b，a%b，x，y)；int tmp=x；x=y；y = tmp - static_cast(a/b)*y；return n；(5)对每一个密钥k=(n，p，q，d，e)，定义加密变换为Y=Ek(x)=xemodn，解密变换为Dk(x)=Ydmod n，这里X，YZn。这里我们要用到模取幂运算。事实上，可以直接计算，没有必要先算me，那样肯定不行，计算量将很大。叫做模取幂运算，根据简单的数论知识，可以设计一个分治算法。具体如下：设是整数b的二进制表示（即b的二进制有k+1位，bk是最高位），下列过程随着c的值从0到b成倍增加，最终计算出。Modular-Exponentiation(a, b, n) 1. c 0 2. d 1 3. 设 是b的二进制表示 4. for ik downto 0 5. do c 2c 6. d (d*d) mod n 7. if bi = 1 8. then c c + 1 9. d (d*a) mod n 10. return d 首先说明一下，上述伪代码中用缩紧表示语句之间的层次关系，例如第59行都是for循环体内的语句，第89行都是then里面的语句。这是我比较喜欢的一种表示方法。上述伪代码依次计算出的每个幂或者是前一个幂的两倍，或者比前一个幂大1。过程依次从右到左逐个读入b的二进制表示已控制执行哪一种操作。循环中的每次迭代都用到了下面的两个恒等式中的一个： 。用哪一个恒等式取决于bi=0还是1。由于平方在每次迭代中起着关键作用，所以这种方法叫做“反复平方法”。在读入bi位并进行相应处理后，c的值与b的二进制表示的前缀的值相同。事实上，算法中并不真正需要变量c，只是为了说明算法才设置了变量c：当c成倍增加时，算法保持条件不变，直至c=b。(6)将e，n作为公开密钥，d，n作为私有密钥。3.3 RSA的安全性分析3.3.1针对RSA的攻击还没有发现针对RSA的破坏性攻击。已经预言了几种基于弱明文、弱参数选择或不当执行的攻击。图就是这些潜在攻击的分类。针对RSA的潜在攻击因数分解选择密文加密指数解密指数明文模执行针对RSA潜在攻击的分类3.3.2因数分解攻击RSA的安全性基于这么一种想法，那就是模要足够大以至于在适当的时间内把它分解是不可能的。收信者选择p和q，并且计算出n=pq。虽然n是公开的，但p和q是保密的。如果攻击者能分解n并获得p和q，她就可以计算出f(n)=(p- 1) (q- 1)。然后，因为e是公开的，攻击者还可以计算出。私密指数d是攻击者可以用来对任何加密信息进行解密的暗门。有许多种因数分解算法，但是没有一种可以分解带有多项式时间复杂度的大整数。为了安全，目前的RSA要求n必须大于300个十进制数位，这就是说模必须最小是1024比特【5】。即使运用现在最大最快的计算机，分解这么大的整数所要花费的时间也是不可想象的。这就表明只要还没有发现更有效的因数分解算法，RSA就是安全的。3.3.3选择密文攻击针对RSA的潜在攻击都基于RSA的乘法特性，我们假定发信者创建了密文：并且把c发送给收信者。我们也假定收信者要对攻击者的任意密文解密，而不是只解密c。攻击者拦截c并运用下列步骤求出m：(1) 攻击者选择Zn*中的一个随机整数x。(2) 攻击者计算出。(3) 为了解密攻击者把y发送给收信者并得到；这个步骤就是选择密文攻击的一个例子。(4) 攻击者能够很容易地得到m，因为攻击者运用扩展的欧几里得算法求x的乘法逆，并最终求得m。3.3.4对加密指数的攻击为了缩短加密时间，使用小的加密指数e是非常诱人的。普通的e值是e=3。不过有几种针对低加密指数的潜在攻击，在这里我们只作简单的讨论。这些攻击一般不会造成系统的崩溃，不过还是得进行预防。为了阻止这些类型的攻击，我们推荐使用e=216+1=65537(或者一个接近这个值的素数)。主低加密指数攻击称为Coppersmith定理攻击。该项定理表明在一个e阶的mod n多项式f(x)中，如果有一个根小于n1/e，就可以运用一个复杂度log n的算法求出这些根【5】。这个定理可以应用于的RSA密码系统。如果e=3并且在明文当中只有三分之二的比特是已知的，这种算法可以求出明文中所有的比特。如果一个实体使用相同的低加密指数