信息安全技术-密码学

信息安全技术——

密码学技术东北大学提纲密码技术概述对称密码技术非对称密码技术密钥分配与管理技术数字签名技术信息隐藏技术提纲密码技术概述对称密码技术非对称密码技术密钥分配与管理技术数字签名技术信息隐藏技术知识点密码学的基本概念密码学的发展历程密码学的应用密码学的技术基础什么是密码学密码学研究通信安全保密的学科密码编码学研究将明文转换成密文的技术寻找生成高强度密码的有效算法密码分析学研究分析破译密码的方法破译密码、伪造密码，窃取机密信息盾矛密码体制的组成密码体制的组成全体明文的集合M——明文空间全体密文的集合C——密文空间全体密钥的集合K——密钥空间加密算法E，由加密密钥控制的加密变换的集合解密算法D，由解密密钥控制的解密变换的集合密码技术的发展历程古典密码技术阶段~1949年现代密码技术阶段1949~古典密码技术阶段古典密码技术阶段早在四千年前，埃及人就开始使用密码技术思路”看“的到，但”看“不懂”看“的懂，但”看“不到”看“不到，也”看“不懂技术暗语、文字游戏以及其他信息隐藏方法1918年，WilliamF.Friedman

“TheIndexofCoincidenceandItsApplicationsinCrytography”(重合指数及其在密码学中的应用）特点基本依靠人工或借助器械小范围应用，少数人掌握加密/解密更多的是依靠经验和直觉艺术的成分>科学的成分现代密码技术阶段（1/10）香农（C.E.Shannon)1949在《贝尔系统技术杂志》上发表了“TheCommunicationTheoryofSecrecySystem”（保密系统的通信理论）奠定了密码学的理论基础艺术

科学（但仍不失艺术性的一面）现代密码技术阶段（2/10）戴维.卡恩

1967整理一战和二战的历史资料，出版了《破译者(TheCodebreakers)》为密码技术公开化、大众化奠定了基础20世纪70年代，随着IBM等公司陆续发表的关于密码技术的报告，使密码技术为更多的人所了解现代密码技术阶段（3/10）W.E.Diffie&M.E.Hellman1976发表“NewDirectioninCryptography(密码学新方向）”，提出了一种全新的密码设计思想（非对称加密），首次证明了在发送端和接收端之间不需要传送密钥的保密通信是可能的开创了公钥密码技术的新纪元使科学高效的密钥管理体制的建立成为可能现代密码技术阶段（4/10）美国国家标准局NBS（现在的NIST）

1977正式公布了数据加密标准DES(DataEncryptionStandard)DES算法公开，使密码技术的研究进入一个崭新的时代DES在相当长的时间内成为事实上的国际标准由于安全性原因，1998年正式退役现代密码技术阶段（5/10）李维斯特（R.L.Rivest）,沙米尔（A.Shamir）,艾德曼（L.Adleman）

1978提出RSA公钥密码技术杰出的公钥密码技术现代密码技术阶段（6/10）Bennett.Charles

H&Brassard.Gill1984提出量子密码技术——BB84协议基于量子定律的密码技术可以抗击具有无限计算能力的攻击量子计算机诞生后，量子密码技术有可能成为唯一真正安全的密码技术现代密码技术阶段（7/10）N.Koblitz&V.Miller1985将椭圆曲线理论引入公钥密码技术椭圆曲线密码体制——公钥密码技术研究的新亮点较之RSA相同的安全级别下，具有更短的密钥长度实现速度快现代密码技术阶段（8/10）R.Mathews&D.Wheeleretc.1989将混沌理论应用到序列密码及保密通信理论中为序列密码技术的研究开辟了新的途径混沌理论的应用主要用于密钥的生成*序列密码利用少量的密钥（制乱元素，保密的）通过某种复杂的运算（密码算法，公开的）产生大量的伪随机位流，用于对明文位流的加密。解密是指用同样的密钥和密码算法及与加密相同的伪随机位流，用以还原明文位流。现代密码技术阶段（9/10）JoanDaemen&VincentRijmen2000Rijndael密码算法

AES算法（AdvancedEncryptionStandard)新一代数据加密标准现代密码技术阶段（10/10）欧盟

2000启动欧洲数据加密、数字签名、数据完整性计划NESSIE目的：提出一套高鲁棒性的密码体制包括分组密码、序列密码、散列函数、消息认证码（MAC）、数字签名和公钥加密密码标准密码技术的作用密码技术作用基本功能提供保密性，使非授权用户无法知道信息的真实内容其他功能鉴别：信息的接收者应能够确认信息的真实来源完整性：信息的接收者应能验证信息在传输过程中有没有发生改变不可否认性：信息的发送方不能否认已发送过的信息密码技术的应用密码技术的应用所有需要信息保密的领域军事政治企/事/工/商业个人——信息时代尤为重要知识点密码学的基本概念密码学的发展历程密码学的应用密码学的技术基础技术基础密码技术分类密码分析计算复杂性理论密码学的技术基础Kerckhoff

假设对于所有的密钥，加密和解密算法迅速有效；密码体制的安全性不依赖于算法的保密，而是依赖于密钥的保密当前和今后较长的时间内，密钥仍然是密码体制安全性的关键；密钥的产生、分配和管理是密码技术中重要的研究方向现代密码技术普遍依赖于数学无论是加密/解密技术，还是密码分析技术密码技术的分类密码技术按执行的操作方式按收发双方使用的密钥是否相同替换密码技术换位密码技术对称密码技术非对称密码技术序列密码技术分组密码技术密码技术的可破译分析密码技术的可破译分析根据密文可以推算出明文或密钥，或者能够根据明文和相应的密文推算出密钥，则该密码技术是可破译的；否则是不可破译的；根据kerckhoff假设只要密钥是保密的、安全的，则密码技术就是安全的密码分析的主要方法（1/3）穷举法通过试遍所有的明文或密钥来进行破译穷举明文将可能的明文进行加密，将得到的密文同截获的密文进行比对，从而确定正确的明文；穷举密钥用可能的密钥解密密文，直到得到有意义的明文，从而确定正确的明文和密钥对抗手段在明文和密文中增加随机冗余信息增加密钥长度，提高生成密钥的随机性密码分析的主要方法（2/3）统计分析法通过分析密文、明文和密钥的统计规律来达到破译密码技术的方法；对抗手段设法使明文的统计特性与密文的统计特性不一样密码分析的主要方法（3/3）密码技术分析法根据所掌握的明文、密文的有关信息，通过数学求解的方法找到相应的加解密算法原则上，受密码技术分析破译的密码技术已经不能使用对抗手段选用具有坚实数学基础和足够复杂的加解密算法对密码技术进行攻击的4种情况惟密文攻击密码分析者仅知道一些密文，并试图恢复尽可能多的明文，并进一步推导出加密信息的密钥已知明文攻击分析者不仅知道一些信息的密文，而且还知道与之对应的明文，根据明文和密文试图推导出加密密钥或加密算法选择明文攻击分析者可以选择一些明文，并得到相应的密文，而且可以选择被加密的明文，并试图推导出加密密钥的酸法。选择密文攻击分析者可以选择不同的密文，并能得到相应的明文，并试图推导出加密密钥。其他自适应选择明文攻击、自适应选择密文攻击，…攻击方案的选择取决于能够掌握的可靠信息和所具有的技术手段计算复杂性理论密码技术的安全性在密码技术领域，安全性是相对的，而不是绝对的可证明安全性从理论上证明破译某个密码系统的代价不低于求解某个已知的数学难题计算安全性用已知的最好算法和利用现有的最大计算资源，仍然不可能在合理的时间内完成破译该系统所需要的计算——可证明安全性和计算安全性统称实际安全性密码安全性理论的基础密码安全性理论的基础计算复杂性理论给出问题求解困难性的数量指标，并确定其安全性密码分析所需的计算量是密码体制安全性的生命指标如果破译一个密码体制所需要的时间为指数阶的，则它在计算上是安全的

实际上也是安全的Diffie和Hellman通过证明指出，NPC问题更适合构造密码体制提纲密码技术概述对称密码技术非对称密码技术密钥分配与管理技术数字签名技术信息隐藏技术知识点对称密码技术概述古典密码技术数据加密标准DES国际数据加密算法IDEA高级加密标准AES技术思路对称密码技术概述对称密码技术加密密钥和解密密钥相同解密算法是加密算法的逆算法特点密钥必须安全传送和妥善保管典型代表古典密码技术序列密码技术分组密码技术（如DES，IDEA，AES等）对称密码技术的安全性对称密码技术的安全性依赖两个因素加密算法必须足够强，仅基于密文本身去解密在实践是不可能的加密方法的安全性依赖于密钥的安全性，而不是算法的秘密性对称密码技术的应用对称密码技术的应用优势实现速度快，算法公开，应用广泛，固化成本低存在的问题密钥的分发与管理非常复杂，代价高N个用户的网络，需要N（N-1）/2个密钥不能实现数字签名知识点对称密码技术概述古典密码技术数据加密标准DES国际数据加密算法IDEA高级加密标准AESDES产生的历史背景DES产生的历史背景美国国家标准巨为了满足计算机通信网络的发展对安全保密的需求，实现系统同一水平的安全性和兼容性，降低数据加密产品的生产成本，推广使用密码算法，而公开征集一种用于政府部门及民间进行计算机数据加密的密码算法1973年5月13日向社会首次公开征集——不理想1974年8月27日向社会再次公开征集——IBM公司的方案1976年11月23日——被采纳，并授权在非密级的政府通信中使用1977年1月15日——公布DES正式文本DES的使用DES的使用存在疑问，但仍被迅速推广使用最主要质疑：密钥长度不足（56位）在最初的使用中，DES没有受到实质性威胁顺利通过1983、1987、1992、1994年的安全性评估到1998年以后不再使用近年来，DES的问题逐渐暴露出来1991年，RSA数据安全公司宣布该公司发起的对56位DES的攻击已经由一个称为电子边境基金会的组织在22小时15分钟内完成（通过互联网上100000计算机合作完成）有必要以新的对称加密技术取代DES64位码64位码初始变换逆初始变换乘积变换明文密文输入输出IPIP-1DES实现过程+ƒK1+ƒK2+ƒKnDES设计原理重复交替使用选择函数S和置换运算P两种变换（confusion+diffusion)使用Feistel方法16次迭代变换每一次迭代变换都是以前一次迭代变换的结果（第一次以x0=L0R0作为输入）和用户密钥扩展得到的子密钥Ki作为输入；每一次迭代变换只变换一半数据，将输入数据的右半部分经过函数f后，将其输出与输入数据的左半部分进行异或运算，并将得到的结果作为新的右半部分，而原来的右半部分变成新的左半部分。）在最后一轮，左、右半部分并围变换，而直接将R16L16并在一起作为末置换的输入。f函数f函数非线性函数，DES算法安全性的关键以长度为32位的比特串作为输入，产生的中间结果为48位，并在最终产生长度为32位的比特串作为输出F以前一轮迭代的结果Ri-1作为输入，首先根据一个固定的扩展函数E“扩展”为48位。与子密钥异或：f将置换得到得到48位输出与子密钥Ki（48位）进行异或S盒替代：以6比特为单位将与子密钥异或得到的结果分为8个小组，并将它们送入替代函数（S盒）中进行替代运算S盒是函数f的核心，是非线性的。48位比特串经过8个S盒后，得到8个4位的分组，重新组合后形成一个32位的比特串。P盒置换：将S盒输出的32位比特串根据固定的置换P盒置换到相应的位置。P盒置换后得到的输出就是函数f(Ri-1,ki)的结果输入（64位）58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157输出（64位）初始变换IPL0（32位）R0（32位）加密函数(A,Ki)A(32位)加密时A=Ri;解密时A=Li;扩展置换E48位结果Ki+选择函数组(S1~S8)32位结果f(A,Ki)置换运算P32位左32位右32位Li-1Ri-1扩展置换48位(明文)64位密钥作第i次迭代的计算机子密钥Ki密钥程序表48位(密钥)8组6位码S1S2S8模2加S盒输入：6位输出：4位+++++…+++++32位置换32位32位LiRi左32位右32位Ri-1Li-1模2加+++++...++++++乘积变换中的一次迭代A32位3212345456789891011121312131415161716171819202120212223242524252627282928293031321选择运算E选择运算E的结果48位选择运算E扩展函数E的第一分组的工作过程123455678123453248……

012345678910111213141501441312151183106125907101574142131106121195382411481362111512973105031512824917511314100613S11

0110

0

1020010输入6位输出4位使用选择函数S1的例子64位码64位码初始变换逆初始变换L0明文密文输入输出IPIP-1R0选择函数的输出（32位）1672021291228171152326518311028241432273919133062211425置换P加密函数的结果（32位）置换码组输入（64位）40848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725输出（64位）逆初始变换IP-164位密钥置换选择1C0(28位)D0(28位)循环左移循环左移C1(28位)D1(28位)置换选择2K1(48位)(56位)循环左移循环左移Ci(28位)Di(28位)置换选择2Ki(48位)(56位)密钥表的计算逻辑循环左移：11912110232112421225213262142721528216157494133251791585042342618102595143352719113605244366355473931331576254463830221466153453729211352820124置换选择1密钥（64位）C0(28位)D0(28位)Ci(28位)Di(28位)1417112415328156211023191242681672720132415231374755304051453348444939563453464250362932Ki(48位)置换选择2L0R0←IP(明文)L1←R0

R1←L0(R0,K1)L2←R1

R2←L1(R1,K2)……L16←R15

R16←L15(R15,K16)密文←IP-1(R16L16)加密方程：L0R0←IP(<64位明文>)Ln←Rn-1Rn←Ln-1(Rn-1,Kn)<64位密文>←IP-1(R16L16)解密方程：R16L16←IP(<64位密文>)Rn-1←LnLn-1←Rn(Ln,Kn)<64位明文>←IP-1(L0R0)DES算法的脆弱性DES的半公开性：S盒的原理至今保密，所以不能算作真正的公开加密算法。1）函数构造与作用域：加密强度取决于函数f的复杂度(S、P)和f的执行次数。64位固定分组，短组模式，易造成密文重复组块有限的函数作用域ASCII码0~127子密钥只参与异或简单的运算，有可能损害变换精度。2）迭代问题无法证明迭代16次最好迭代在有限的作用域中存在封闭性；迭代次数多不仅费时，还可能被一次简单的变换所代替。DES算法的脆弱性3）S盒中的重复因子及密钥多值问题S盒设计中利用重复因子，导致S盒对不同输入可能产生相同输出，使加密、解密变换的密钥具有多值性。子密钥长度48位，只影响32位输出，因此加密强度达不到256，实际只有232x16=236S盒是精心设计的，它有利于设计者破译密码。提高加密强度（如增加密钥长度），系统开销呈指数增长，除提高硬件、并行处理外，算法本身和软件技术无法提高加密强度。DES算法存在的问题与挑战数据加密标准强力攻击：255次尝试穷尽搜索蛮力攻击差分密码分析法：247次尝试1991年提出，选择明文攻击。分析明文对的差值对密文对差值的影响。很有效。线性密码分析法：243次尝试1992年提出，已知明文攻击。寻找一个近似的线性表达式，通过选择充分多的明文——密文对来破解密钥。对DES更有效。多重DES及IDEA二重DES（二个密钥，长度112位）

：加密：C=Ek2[Ek1(P)]解密：P=Dk1[Dk2(C)]要防止中途攻击三重DES（二个密钥）加密：C=Ek1[Dk2[Ek1(P)]]解密：P=Dk1[Ek2[Dk1(C)]]IDEA加密算法1992年，瑞士的Lai和Massey128位密钥，8轮，快速，软硬件实现。高级加密标准(AES)

NIST(国家标准技术研究所)1997年9月12日发出征集高级加密标准的通知。1998年8月首次选出15个候选者，1999年3月遴选出5个，包括：E2、MARS、RC6、Rijndael、Twofish。2000年10月2日，美国商务部部长宣布比利时的Rijndael算法成为新的AES。选择的基本条件：公开；分组单钥，分组长度128；密钥可为128，192，256；可软硬件实现。优劣标准：安全性；计算效率；内存要求；简便灵活。此外：适应性；减少专利纠纷；分散目标减少攻击。AES被开发用于替代DES，但NIST预测TripleDES仍将在近期作为一种实用的算法，单DES将逐步退出。

提纲密码技术概述对称密码技术非对称密码技术密钥分配与管理技术数字签名技术信息隐藏技术知识点非对称密码技术概述RSA算法其他非对称密码技术简介传统密码体制的缺陷传统密码体制的缺陷密钥管理的麻烦n个用户保存n*(n-1)/2个密钥不能提供法律证据不仅要保密还要解决证实问题非对称密码技术的提出1976年，美国学者Diffie和Hellman发表了著名论文《密码学的新方向》，提出了建立“公开密钥密码体制”若用户A有加密密钥ka（公开），不同于解秘密钥ka’（保密），要求ka的公开不影响ka’的安全。若B要向A保密送去明文m,可查A的公开密钥ka，若用ka加密得密文c，A收到c后，用只有A自己才掌握的解密密钥ka’对x进行解密得到m。公钥体制的理论基础从本质上讲，设计一个公开密码体制就是构造一个陷门单向函数。设X为明文，Y为密文。满足以下两条件的f则称为陷门单向函数。算Y=f(X)容易，而已知Y，反求X则很难，即求X=f(Y)很难若陷门（参数）已知，则容易由Y求X保证从已知的Y，X和公钥难以推出秘密密钥的这种安全性，往往建立在著名的数学难题基础上，即要破译某种公钥密码，相当于要解一个公认的数学难题。目前世界上用得最多的公钥密码算法是RSA、离散对数和ECC。其中，RSA是基于大整数分解难题的基础上，而ECC是基于求椭圆曲线离散对数的难题基础上。陷门参数正是秘密密钥公钥密码体制的特点公钥密码体制有以下特点密钥分发简单由于加密密钥与解密密钥不能互推，使得加密密钥表可以像电话号码本一样由主管部门发给各个用户。需要秘密保存的密钥量少网络中每个成员只需秘密保存自己的解密密钥，N个成员只需产生N对密钥互不相识的人之间也能进行保密对话一方只要用对方的公开密钥加密发出，收方即用自己密藏的私钥解密，而任何第三方即使知道加密密钥也无法对密文进行解密。可以进行数字签名发信者用他的秘密密钥进行签名，收信者可用发信者的公钥进行验证。公钥密码体制的意义（1/2）解决大规模网络应用中密钥的分发和管理问题

需要管理的秘密密钥数量大大减少采用公钥密码体制，N个用户只需要产生N对密钥。以100万个用户为例，只需100万对密钥，需要秘密保存的仅100万个私钥。而利用传统密码体制，为保证不被第三方窃听，需要N（N–1）/2=4950万个密钥！分发简单，安全性好公钥密码加密密钥通常是公开的，而解密密钥是秘密的，由用户自己保存，不需要往返交换和传递减少了密钥泄露的危险性公钥密码体制的意义（2/2）实现网络中的数字签名机制

数字签名的数据需要有惟一性、私有性，而对称密钥技术中的密钥至少需要在交互双方之间共享，因此，不满足惟一性、私有性，无法用做网络中的数字签名。公钥密码技术由于存在一对公钥和私钥，私钥可以表征惟一性和私有性，而且经私钥加密的数据只能用与之对应的公钥来验证，其他人无法仿冒，所以，可以用做网络中的数字签名服务。知识点非对称密码技术概述RSA算法其他非对称密码技术简介RSA算法的提出与发展

1978年，美国麻省理工学院(MIT)的研究小组成员：李维斯特(Rivest)、沙米尔(Shamir)、艾德曼(Adleman)提出了一种基于公钥密码体制的优秀加密算法——RSA算法。

RSA算法是一种分组密码体制算法，它的保密强度是建立在具有大素数因子的合数，其因子分解是困难的。 RSA得到了世界上的最广泛的应用，ISO在1992年颁布的国际标准X.509中，将RSA算法正式纳入国际标准。1999年美国参议院已通过了立法，规定电子数字签名与手写签名的文件、邮件在美国具有同等的法律效力。

公开密钥算法数论知识简介互素：若gcd(a,b)=1，则整数a和b互素。定义：若a•xmodn=1，则称a与x对于模n互为逆元。用欧几里得Euclid算法求乘法逆元 若a和n互素，则a在模n下有逆元欧拉Euler函数φ(n)=与n互素的、小于n的正整数的个数，n>1。例： φ(3)=φ(4)=φ(6)=2，φ(5)=4，φ(7)=6 φ(12)=6

数论知识简介模运算性质：同余模运算满足自反性、对称性、传递性；

a=amodn；

若a=bmodn，则b=amodn；

若a=bmodn，b=cmodn，则a=cmodn若amodn=bmodn，则(a-b)modn=0；[(amodn)+(bmodn)]modn=(a+b)modn；--；**；例：152

mod12=(3*3)mod12=9若n是素数，则φ(n)=n-1若n=p*q，p、q是素数，则φ(n)=(p-1)*(q-1)

例：φ(21)=φ(3*7)=2*6=12费尔玛Fermat小定理：若m是素数，且a不是m的倍数，则am-1modm=1。或者：若m是素数，则ammodm=a例：47-1mod7=4096mod7=1

47

mod7=16384mod7=4欧拉Euler定理：aφ(n)modn=1推论：若a与n互素，则a与aφ(n)-1

互为逆元。

例：a=4，n=7，φ(7)=6，aφ(7)-1

=45=1024

所以，4和1024在模7下互为逆元。验证：4x1024mod7=1求乘法逆元FunctionEuclid(d,f)//求d在模f下的逆元(x1,x2,x3)<-(1,0,f);(y1,y2,y3)<-(0,1,d);Ify3=1thenprint“逆元是”y2elseprint“无逆元”;End.Q=[x3/y3](t1,t2,t3)<-(x1-Q*y1,x2-Q*y2,x3-Q*y3)(x1,x2,x3)<-(y1,y2,y3);(y1,y2,y3)<-(t1,t2,t3)Goto2)高次幂剩余的运算公开密钥算法

要计算gn

modp，因g、n、p都是大数而不能采用先高次幂再求剩余的方法来处理，而要采用平方取模的算法，即每一次平方或相乘后，立即取模运算。欧几里德算法欧几里德算法可以迅速地找出给定的两个整数a和b的最大公因数gcd（a，b），并可判断a与b是否互素，因此该算法可用来寻找加密密钥和解密密钥。

Xrmodp的快速算法流程图A<-xB<-rC<-1B=0输出CBmod2=0B<-B/2A<-A*AmodpB<-B-1C<-C*AmodpYNNYRSA算法概述

公开密钥算法每个合数都可以唯一地分解出素数因子 6=2·3 999999=3·3·3·7·11·13·37 27641=131·121 从2开始试验每一个小于等于√27641的素数。素数：只能被1和它本身整除的自然数；否则为合数。整数n的十进制位数因子分解的运算次数所需计算时间（每微秒一次） 50 1.4x1010 3.9小时 75 9.0x1012 104天 100 2.3x1015 74年 200 1.2x1023 3.8x109年 300 1.5x1029 4.0x1015年 500 1.3x1039 4.2x1025年素数的检验素数的检验Wilson定理：P是素数(P-1)!ModP=-1

当P较大时，很费时间，无实际价值。Rabin-Miller方法：概率检验适用于RSA算法的最实用的办法是概率测试法。该法的思想是随机产生一个大奇数，然后测试其是否满足条件，如满足，则该大奇数可能是素数，否则是合数。

Witness(a,n){/*将n-1表示为bk

bk-1…b0的形式

n是待检验的数，a是小于n的整数。若返回True，则n肯定不是素数；若返回False，则n有可能是素数。*/d=1fori=kdownto0{x=d;d=(d•d)modn;ifd=1&(x<>1)&(x<>-1)returnTrue;ifbi=1thend=(d•a)modn}ifd<>1thenreturnTrue;returnFalse;}对于s个不同的a，重复调用此算法，每次返回False，则n是素数的概率至少为1-2-sRabin-Miller方法RSA算法的实现

公开密钥算法RSA加密算法的过程

1．取两个随机大素数p和q（保密）2．计算公开的模数n=p*q(公开)3．计算秘密的欧拉函数

(n)=（p-1)*(q-1)（保密），丢弃p和q，不要让任何人知道。4．随机选取整数e,满足gcd(e,

(n))=1(公开e加密密钥)5．计算d满足de≡1(mod

(n))(保密d解密密钥)6．将明文x（按模为r自乘e次幂以完成加密操作，从而产生密文y（X、Y值在0到n-1范围内）。Y=xe

modn7．解密：将密文y按模为n自乘d次幂。X=Ydmodn举例

公开密钥算法例设p=43,q=59,r=p•q=43*59=2537,

(r)=(p-1)(q-1)=42*58=2436,取e=13,求e的逆元d解方程d•e=1

mod24362436=13*187+5,13=2*5+35=3+2,3=2+1所以1=3-2，2=5-3，3=13-2*55=2436-13*187所以，1=3-2=3-（5-3）=2*3-5=2*（13-2*5）-5=2*13-5*5=2*13-5*（2436-13*187）=937*13-5*2346即937*13≡1mod2436取e=13时d=937RSA算法的实现

公开密钥算法若有明文publickeyencryptions先将明文分块为pu

bl

ic

ke

nc

ryptions将明文数字化令abz分别为000125得1520011108021004240413021724151908141418利用加密可得密文0095164814101299136513792333213217511289公开密钥算法关于素数的分布1-10025101-20021201-30016301-40016401-50017501-60014601-70016701-80014801-90015901-100014素数定理：当X变得很大时，从2到X区间的素数数目

(X)与X/ln(X)的比值趋近于1，即(X)X/ln(X)=1limx

X

(X) X/ln(X)

(X)X/ln(X)10001681451.15910,0001,2291,0861.132100,0009,5928,6861.1041,000,00078,49872,3821