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

四川理工学院成都新华学院毕业论文（设计）课题名称： 密码技术浅析 年级专业： 2023级计算机软件技术 学 号： 姓 名： 张 强 指导教师： 陈 侠 2023年 X 月 XX 日四川理工学院成都新华学院毕 业 论 文（设计）任 务 书姓 名张强学 号2023年级计算机软件技术 专业题 目密码技术浅析设计任务网络安全日益得到大众的重视，在这个杀毒软件总是跟在病毒后面跑的现实中，如何能更有效的保护好个人的资料。密码技术是解决这个问题的有效手段之一。请分析目前网络中面临的问题，阐述密码技术的原理，提出相应的解决措施。时间进度重要参考文献 和原始资料(1) 密码学理论与技术主编 范明钰，王光卫 清华大学出版社 2023 10(2) RSA算法缺陷分析主编 杨云江 贵州大学学报(自然科学版)，贵州大学，2023 2(3) 密码学与网络安全(美) BEHROUZ A. FOROUAAN 著 清华大学出版社 2023(4)加密与解码:密码技术剖析与实战应用 许主洪编 著 人民邮电出版社 2023(5)应用密码学:协议、算法与C源程序 (美)B.施奈尔Bruce Schneier著 机械工业出版社 2023(6)RSA算法的安全性分析王启明 王一凡 著 中南民族学院学报(自然科学版)，华中理工大学，2023 9 指导教师：陈侠2023年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世纪以来，由于电报特别是无线电报的广泛使用，为密码通信和第三者的截收都提供了极为有利的条件。通信保密和侦收破译形成了一条斗争十分剧烈的隐蔽战线。192023，英国破译了德国外长齐默尔曼的电报，促成了美国对德宣战。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年代后，电子技术的发展，使得基于复杂计算的密码成为也许。这一阶段电子密码机得到较快的发展和广泛的应用，使密码学的发展进入了一个新的阶段。同时充足运用了古典密码留下来的经验，对于算法的设计有了更科学的思绪。密码破译是随着密码的使用而逐步产生和发展的。142023，波斯人卡勒卡尚迪所编的百科全书中载有破译简朴代替密码的方法。到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)(172)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