1、第2章 现代密码学概论本章要点r 现代密码学框架r 现代密码学的理论基础r 对称加密标准：DES和AESr 公钥密码体制：RSA和ElGamal体制2.1 现代密码学框架 2.1.1 什么是密码学 定义定义1 密码学密码学是研究与信息安全各方面有关的(比如机密性、数据完整性、实体认证及数据源认证)数学技术数学技术的一门学科。2.1.1 什么是密码学(续)发送者Alice密钥源分析者Eve接收者Bob安 全信道公 共信道加密器Ek解密器Dk明文m密文c明文m密钥k密钥k图 2.1 Shannon保密系统 2.1.1 什么是密码学(续)通信中的参与者通信中的参与者 (1)发送者(Alice)：在双
2、方交互中合法的信息发送实体。(2)接收者(Bob)：在双方交互中合法的信息接收实体。(3)分析者(Eve)：破坏通信接收和发送双方正常安全通信的其他实体。可以采取被动攻击和主动攻击的手段。信道信道 (1)信道：从一个实体向另一个实体传递信息的通路。(2)安全信道：分析者没有能力对其上的信息进行阅读、删除、修改、添加的信道。(3)公共信道：分析者可以任意对其上的信息进行阅读、删除、修改、添加的信道。2.1.2 现代密码学中的对称与非对称密码思想加密器EK1(m)=c分析者Eve解密器DK2(c)=m明文消息源目的地mmc公共信道AliceBob#对称密码的加密密钥与解密密钥同：K1=K2代表系统
3、：DES和AES2.1.2 现代密码学中的对称与非对称密码思想(续)若互联网上有n个用户，则需要个密钥，若n=1000，则NK500 000。#如此众多的密钥如何建立，如何保存？)1(22nnnNK2.1.2 现代密码学中的对称与非对称密码思想(续)加密器EK1(m)=c分析者Eve解密器DK2(c)=m明文消息源目的地mmc公共信道AliceBob#非对称密码的加密密钥与解密密钥不同：K1K2代表系统：RSA和ElGamal2.1.3 密码学的演进及目前的状态安全依赖于保密加密方法安全依赖于保密密钥安全依赖于保密部分密钥古典密码私钥密码公钥密码#公钥密码体制以其强大的功能使得私钥密码体制显得
4、已经过时，但是强大的功能不是无代价获得的，公钥密码的计算量远大于相同情况下的私钥密码。因此，不适合加密大量数据，只适合于完成少量数据加密，如传送私钥密码的密钥、签名等等。2.1.4 现代密码学主要技术Security PrimitivesPublic-key PrimitivesSymmetric-key PrimitivesUnkeyed PrimitivesArbitrary length hash functionsSymmetric-key ciphersRandom sequencesOne-way permutationsB l o c k ciphersS t r e a m c
5、iphersArbitrary length hash functions(MACs)SignaturesPseudorandom sequencesIdentification primitivesPublic-key ciphersSignaturesIdentification primitives图2.2 密码学本原分类2.1.4 现代密码学主要技术(续)(1)加密加密 加密基本术语加密基本术语 明文消息空间M:某个字母表集 密文消息空间C:可能的密文消息集 加/解密密钥空间K:可能的加/解密密钥集 加/解密函数EeK(mM)/DdK(cC):一个 从M到C/C到M的有效变换2.1.4
6、 现代密码学主要技术(续)加密方案加密方案 加密方案是由一个加密函数集Ee:eK和解密函数集Dd:dK构成，并且满足任意一个加密密钥eK存在唯一一个解密密钥dK使 Dd=Ee1，也就是对于所有明文消息mM，存在Dd(Ee(m)=m，(e,d)称为密钥对。设计加密方案就是确定M、C、K、Ee:eK、Dd:dK的过程。定义定义2 一个加密方案可以被破译是指，第三方在没有事先得到密钥对(e,d)的情况下，可以在适当适当的时间的时间里系统地系统地从密文恢复出相对应的明文。#适当的时间由被保护数据生命周期来确定。2.1.4 现代密码学主要技术(续)私钥加密私钥加密 定义定义3 一个由加密函数集Ee:eK
7、和解密函数集Dd:dK组成加密方案，每一个相关联的密钥对(e,d)，如果知道了e在计算上很容易确定d，知道了d在计算上很容易确定e，那么，就是私钥加密方案。#私钥加密需要一条安全信道来建立密钥对。主要技术：分组密码分组密码与流密码流密码 定义定义 4(分组密码分组密码)将明文消息在编码集按照固定长度t进行分组，再一组一组地加解密明密文消息。#著名的DES、AES都是这类密码。2.1.4 现代密码学主要技术(续)定义定义5 K 是加密变换集的密钥空间，序列 e1e2 eiK称为密钥流。定义定义6(流密码流密码)消息m以串的形式(m1m2mi)给出，密钥e1e2ei是K上的密钥流。流密码通过ci=
8、Eei(mi)给出密文消息(c1c2ci)；如果di为ei的逆，解密则通过mi=Ddi(ci)完成。2.1.4 现代密码学主要技术(续)公钥加密公钥加密 定义定义 7 一个由加密函数集Ee:eK和解密函数集Dd:dK组成加密方案，每一个相关联的加/解密密钥对(e,d)，加密密钥e公开，称为公开密钥，而解密密钥d保密，称为秘密密钥。#显然安全公钥密码系统要求从e计算d为不可能。2.1.4 现代密码学主要技术(续)公钥加密实例公钥加密实例Ee(m1)=c1A1Ee(m2)=c2A2Ee(m3)=c3A3Dd(c1)=m1Dd(c2)=m2Dd(c3)=m3Bobec1eec2c3#因为存在替代攻击
9、问题，公钥系统中公开密钥e必须认证，一般是建立PKI。2.1.4 现代密码学主要技术(续)(2)数字签名技术数字签名技术 基本术语基本术语 明文消息空间M:某个字母表中串的集合 签名空间S:可能的签名集合 签名密钥空间K:用于生成签名的可能密钥集，具体取值k需要保密 验证密钥空间K:用于验证签名的可能密钥集，具体取值k需要公开 签名函数SK(mM):从M到S的有效变换 验证函数VK(mM,s):一个从MS到输出True,False的有效变换2.1.4 现代密码学主要技术(续)签名过程签名过程 签名签名(签名者完成)1)对一条需要签名的消息mM计算签名s=Sk(m)。2)将对消息m的签名(m,s
10、)发送出去。验证验证(验证者完成)1)得到对应签名者的验证算法Vk，计算u=Vk(m,s)。2)如果u=True，接受签名；如果u=False，拒绝签名。2.1.4 现代密码学主要技术(续)签名和认证函数必须满足的性质签名和认证函数必须满足的性质 1)当且仅当Vk(m,s)=True时，s是消息m的合法签名。2)对于任何签名者以外的实体在计算上不可能得到任意的一组mf和sf满足Vk(mf,sf)=True。数字签名的争议解决数字签名的争议解决(不可否认不可否认)如果签名者和验证者对签名发生争议，可由验证者带着签名(m,s)提交给可信任第三方(TTP)，由TTP验证该签名，最后进行仲裁。2.1.
11、4 现代密码学主要技术(续)数字签名技术在公钥基础设施数字签名技术在公钥基础设施(PKI)中的应用中的应用 除非对密钥产生的认证性和合法性有足够的信任，否则公钥密码的优势就十分有限。公钥基础设施或简称PKI是一个框架。这个框架主要由一组策略策略组成。策略确切定义了关于密码系统运行和密钥产生和发布与其证书的规则。X.509是设计用来在大型计算机网络中提供目录认证服务的国际标准。由于它本身是ISO/ITU 的一个标准，很多实用产品都基于它开发出来。例如，X.509被用在Visa和Mastercard的安全电子交易标准中。2.1.4 现代密码学主要技术(续)图2.3 X.509的结构原理2.1.4
12、现代密码学主要技术(续)8定义 一个公钥证书是由数据部分和签名部分组成的一个数据结构。数据部分至少包含的明文数据有：公开密钥以及标识指定实体身份的位串。签名部分是证书权威对数据部分的一个数字签名，其将目标用户的身份与特定的公开密钥相绑定。2.1.4 现代密码学主要技术(续)图2.4 证书认证过程A1A6认证VT(A6|e6,s6)秘密密钥 d6A2,e2,ST(A2|e2)=s2A3,e3,ST(A3|e3)=s3A4,e4,ST(A4|e4)=s4e6,s6Dd6(c)=mc=Ee6(m)Public fileA1,e1,ST(A1|e1)=s1A5,e5,ST(A5|e5)=s5A6,e6
13、,ST(A6|e6)=s6A2,e2,ST(A2|e2)=s2#证书权威负荷小(离线、非交互、存储证书)，权限低2.1.4 现代密码学主要技术(续)公钥证书的产生公钥证书的产生 情况情况1 可信方产生密钥对。可信方为实体产生公钥算法的密钥对，并将公开密钥和绑定身份的公钥证书通过公共信道发给该实体。实体在证明了自己的身份(例如，出示身份证或个人可信照片)后，将通过安全信道得到对应的秘密密钥。情况情况2 实体产生自己的密钥对。实体产生自己的公钥算法的密钥对，并安全地将公开密钥传送给可信方(例如，通过可信通道或派人送达)，这里主要是保证公开密钥的真实性。在验证了公开密钥来源的真实性后，可信方为公开密
14、钥生成证书。2.1.4 现代密码学主要技术(续)证书链和证书路径证书链和证书路径图2.5 证书链 2.1.4 现代密码学主要技术(续)(3)认证与鉴别技术认证与鉴别技术 鉴别或实体认证鉴别或实体认证 定义定义 9 鉴别或实体认证是一个过程。在这个过程中一方通过获得一些确定的证据来确认参加实体认证的另一方的身份，而具有相应身份的实体也确实就是正在参与这一认证过程的另一方。例子例子1 实体A与B通电话，如果A与B认识就可以通过声音来确定对方的真实性。例子例子2 实体A通过信用卡在银行ATM机上取钱。#特点：时实性。特点：时实性。2.1.4 现代密码学主要技术(续)直观安全目标安全目标：a 在宣称者
15、A和验证者B都诚实地执行认证时，A能向B成功地证明自己，也就是B将完成执行并接受A所宣称的身份。b(不可转移性)验证者B不能从与宣称者A交互中获得的信息，成功地向第三方C来冒充A。c(不可冒充性)任何一个非宣称者A的C想通过扮演A的身份，通过验证者B的认证，让B接受A的身份的可能性可以忽略。这里，可以忽略的含义是概率小到没有具体的实际意义，准确的度量需要根据实际应用而定。d 即使如下情况存在，以上三个条件仍然成立。d.1宣称者A和验证者B之间以前进行的多项式次认证会话且被窃听;d.2 冒充者C以前参与了同宣称者A或（和）验证者B的认证执行;d.3 冒充者C可能发起多个认证会话并行运行。2.1.
16、4 现代密码学主要技术(续)数据源认证数据源认证 定义定义10 数据源认证或消息认证技术，提供一方通过一些附加的证据，确定消息的产生一方的真实身份。例子例子3 实体A向实体B发送电子邮件，电子邮件通过网络传输并存储，在某个时间由B接收到，由于没有直接通信，B这时可能要求认证邮件确实来自A。2.1.4 现代密码学主要技术(续)(4)密码密码Hash 函数技术函数技术 定义定义11 Hash函数h()是一个有效的计算方法，它将一个任意长度的二进制位串影射成固定长度的二进制位串，这个固定长度的二进制位串叫Hash值。修改发现码修改发现码(MDCs)附加性质附加性质 1)Hash函数是单向函数，即给定
17、y，找到任意x，满足 y=h(x)计算不可能。2)已知x，找x，满足h(x)=h(x)计算不可能。3)找一任意对x和x，满足h(x)=h(x)计算不可能。#修改发现码可以进一步分类，单向Hash函数(1-2)(OWHFs)和碰撞抵抗Hash函数(2-3)(CRHFs)。2.1.4 现代密码学主要技术(续)消息认证码消息认证码(MACs)消息认证码的目的，通俗讲就是不附加任何其他机制，确保消息来源的真实性的Hash函数。消息认证码有两个不同功能的参数，即消息和秘密密钥。Hash函数无密钥有密钥修改发现码(MDCs)其他应用其他应用消息认证码(MACs)图2.6 密码Hash函数的简单分类2.1.
18、4 现代密码学主要技术(续)(5)随机数与随机序列随机数与随机序列 密码中以伪随机序列发生器代替随机序列发生器。伪随机序列发生器以短的随机数做种子，以固定方式产生伪随机序列。#伪随机序列与真随机序列不可区分假设，与安全数字签名、公钥密码的存在性等价。2.1.5 评价现代密码算法的标准 Kerckhoffs准则准则 在评估一个密码系统安全性时，应该总是假定我们的敌人了解实际使用的各种方法。#落实到现代密码算法中就是攻击者知道密码算法的所有执行细节，算法的安全不应该依赖于对算法的保密。2.1.5 评价现代密码算法的标准(续)Shannon提出的“优质”密码算法特征 (1)加解密的工作量应该由所要求
19、的安全程度决定。(2)密钥集合和加密算法不应该过于复杂。(3)执行过程应该尽量简单。(4)密码中的差错不应该具有传播性，也不应该影响报文中的其他信息。(5)加密后的文本大小不应该比原始报文显著增大。2.1.5 评价现代密码算法的标准(续)“可信赖的”加密体制的特点(1)有可靠的数学基础。(2)经过专家的严格分析，证实是可靠的。(3)经得起时间的检验。2.2 现代密码学的理论基础 现代密码学要求很高的数学基础，包括：数论、抽象代数与有限域、计算复杂理论、信息论、概率论等。但是掌握基础的密码算法并不需要精通过多的底层数学理论。这里我们仅讲述掌握本章的密码算法所需要的计算复杂理论、数论等的基础知识。
20、2.2.1 计算复杂理论 如果加密算法建立在一个已知非常难解决的问题或者可能解的数目巨大的问题之上，那么攻击者要破译算法就注定要完成一个即便不是不可能，也是另人沮丧的任务。即使有计算机的支持，一个穷尽的暴力解答也是不可行的。NP完全问题就是这样一类具有计算复杂特点的问题。我们用非形式化非形式化的方式来描述NP完全问题。2.2.1 计算复杂理论(续)NP完全问题完全问题 几个具体实例 例子例子4 可满足问题 给定逻辑公式满足如下条件：(1)它由变量v1，v2，vn和它们的逻辑非v1，v2，vn 组成。(2)它表现为一系列子句，且每个子句的形式是变量以及逻辑非的逻辑或()(3)它表示为这些子句的逻
21、辑与()是否存在一种变量的赋值法(赋真或假)，使得公式为真？如果存在，说这个公式是可满足的可满足的。例如，(v1)(v2 v3)(v1 v3)为可满足的，(v1)(v2 v3)(v1 v3)(v2)为不可满足的。2.2.1 计算复杂理论(续)例子例子5 背包问题12121,0,01 =4,7,1,12,10=17174 1 121,0,1,1,0=25 nininiiiSa aaTaVv vvvavTSTVT 给定一个集合和一个目标和，其中，是否存在一个选择向量，其中或，使得。例如，集合 为。对于目标和存在一个解，即。对应的选择向量。而当时无解。2.2.1 计算复杂理论(续)例子例子6 团 给
22、定一个图G和一个整数n，是否存在一个包含n个顶点的子图，使得子图中的每个顶点与其他顶点之间都有一条边每个顶点都与其他所有顶点相连的图被称为团(clique)?例如，图2.7有4顶点的团，但无5顶点的团。图 2.7 图的团子图2.2.1 计算复杂理论(续)NP完全问题的特征完全问题的特征 (1)每个问题都有解法，且总有一个相对简单的解法(尽管该解法也许十分耗时)。(2)如果要列举所有可能性，就需要考虑2n中情况(n与问题有关)(3)这些问题是无关的，分别来自逻辑学、数论和图论。(4)如果能完全猜中，则可以在相对较少的时间内求解每一个问题。2.2.1 计算复杂理论(续)P类和类和NP类类 P类问题
23、是一类问题的集合，这个集合中的问题都可以在一个与问题大小相关的多项式函数时间内完成。NP类问题是所有这样一类问题的集合，假设能够完全猜中，这些问题可以在一个多项式函数时间内得到解决(猜测函数被称为是预言机或非确定性图灵机)。这种猜测是非确定性的。EXP类，它由所有存在指数时间cn内的确定性解法的问题组成，其中，c是一个常数。它们有如下关系，PNP EXP。2.2.1 计算复杂理论(续)NP完全的含义完全的含义 Cook证明了：如果可满足问题有一个确定性的、多项式时间的算法(不带猜测)，那么对NP中的每个问题都会有一个确定性、多项式时间的算法，即NP=P。Karp证明了背包问题和团问题具有和可满
24、足问题一样的性质。这一问题的逆否命题是：如果可以证明这些问题中的某个问题没有在多项式时间内完成的确定性算法，那么它们中所有问题都不存在确定性多项式时间算法。这里对一个问题的解决这里对一个问题的解决是要求找到一个通用算法来解决它的每个实例是要求找到一个通用算法来解决它的每个实例。2.2.1 计算复杂理论(续)图 2.8 复杂性的层次结构#P=NP或PNP2.2.1 计算复杂理论(续)已经有很多人对NP完全问题进行了长期研究，如果对确实存在多项式时间算法，那么有理由认为已经有人找到了解法。目前，已经有数以百计的问题被证明是NP完全问题。我们列举的这类问题越多，就越有理由确信不存在一个能解决所有问题
25、的简单方法。2.2.1 计算复杂理论(续)NP完全性与密码学完全性与密码学 (1)一个NP完全问题不能保证不存在一种比指数时间更容易的算法，它仅表示我们不大可能找到这一算法。(2)每个NP完全问题都有一个确定性的指数时间算法，即可以与2n成比例的时间运行完成。(3)硬件的不断进步，越来越大规模的问题都能计算了。(4)即使一个加密算法是基于难解问题的，但攻击者未必总是去解这个难解问题才能破译加密算法。2.2.1 计算复杂理论(续)其他固有的难解问题其他固有的难解问题 数论中存在大量难解问题，但大多数数论中的难解问题都是NP问题，不是NP完全问题。公钥密码体制主要依赖数论中的两个难解问题：大整数分
26、解问题和离散对数问题。2.2.2 数论知识(1)基本概念基本概念整除性整除性。，记不整除不存在，如果这。的倍数，记做 的因数，做，使得，如果存在一个整数整除。我们，0对于整数 b|abaka|babbab=kakbaba为我们说个为叫叫我们把说 定义12定义12。即，所以，由定义可写出。，所以有，满足由定义存在显而易见。是任意整数。和，这里，则，如果。，则，如果。，对于任意，对于任意tca|sbatksktcsbakcakbklaclbckablktstcsbaa|ca|bcacba|b|bba|aa|a )(3)和 2)1 )(|3)|)2 10 0)1 2121证明.证明.性质1性质12.
27、2.2 数论知识(续)。0 0，成立，使得及个唯一的整数，则存在两是两个整数，其中设brrbq arqbba定定理理1 12.2.2 数论知识(续)素数素数是有限的假设矛盾。，因此，与素数的个数其它素数然存在之中任意一个整除，必，不可为而，知其必为合数，是全体素数。再令，的可令如果素数的个数是有限素数的个数是无穷的。是合数时，是素数，并且当数以外的最小正因的除的整数，则是任一大于设否则就叫做合数。它本身，就叫做素数，和因数只有的正整数，如果它的正一个大于(?)1 32 11 11 212121kkkpppppppppppaqaqaa证明.证明.定理2定理2引理1引理11313 定义定义 2.2
28、.2 数论知识(续)200以内的素数：2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 2.2.2 数论知识(续)。时，比率，也就是说当则有的所有素数个数，表示小于如果素数数量定理1)ln()(ln)()()(xx/xxxxxxx 定理3定理3因此，足够使用。，我们可以估计通过位左右的十进制素数，要求使用在各种密码应用中经常2972992
29、99300300299300103.110ln1010ln10)10()10(300定理3定理32.2.2 数论知识(续)。，是整数，则其中，整数，且是任意三个不全为零的，设互素。，就说，若，公因数，记作叫最大的公因数中最大的一个，公因数。整数的一个，就叫，那么它们之中每一个的因数是整数个不全为零的整数。若是，设)()(1)()(212121212121cbbaqcbqacbaaaaaaaaaaaaaaaaddnaaannnnnn 定理4定理4定义14定义14 2.2.2 数论知识(续)。，即一个不等于零的余数，就是上述过程中最后，则，任意。，有，不失一般性假定任意算法的表述nnnnnnnnn
30、nnnnnnnnnrbababarrqrrrrrqrrrrrqrrrrrqrrrrrqrbbrrbqaba)()(00 0 0 0 0 0 0 00Euclidean111111221112323332112221111定理5定理52.2.2 数论知识(续)忽略的过程。被除数除数：余数可以看到余数都经历了。，因此，。，计算 21180)(4820281621635016504216051622482216482211801180)(482例例子子7 7。，使得，则存在两个整数，若任给整数nbmabanmba)(00 定理6定理62.2.2 数论知识(续)。，则，若算法。这一过程被称为扩展。，所
31、以同样有。，因此，。，则，公式，我们还可以得到递推根据cababcayxxxxxxxxbabyaxyyqyqqyqyxxqxqxxnnjjjjjjjj|1)(|Euclidean)1180 482(271482)29(1180712939421)(11:523412321212121121221定定理理7 7定定理理5 52.2.2 数论知识(续)整数唯一分解定理整数唯一分解定理。或，则是素数，若。，或是任一整数，则有是一素数，若bpapp|abpapapap|1)(|引理3引理3引理2引理22.2.2 数论知识(续)。，以此类推，最后可得，可以得。进一步，由，因此，和。同时有，为素数，所以，
32、由于，可知，由引理知和证明唯一性。由其次成立。故也能表示为素数乘积，因此都能表示为素数乘积，和可知则必有分解如果为合数如果为素数显然成立，的正整数都成立，考虑切小于显然成立，假定一时成立，数学归纳法，当首先证明证明：。，都是素数，则，其中，并且若都是素数，其中，有即对于整数的乘积数的正整数都能分解成素任何大于整数唯一分解定理mnmnkjkjkjmniimmmnnnqpnmqpqqppqppqqppqqppqpqqpqqqpppacbacbbcaaaanipqnmqqqqqqqqqapppppppppaa222211111111112121212121212121|3)II()I(,(I),1,
33、)I(2(I)21(II),(I)1,1)(定理8定理82.2.2 数论知识(续)一次不定方程一次不定方程为任意整数。的一组解，为，其中，的全部解可表示为，则，设。，件是有整数解的充分必要条方程。是给定的整数，其中，二元一次不定方程是指tyxtayytaxxaanaaaanaanyaxa)III(III)|)(III)0(III)0010202121212121 1 1)(定理10定理10定理9定理92.2.2 数论知识(续)(2)同余同余同余定义与概念同余定义与概念(mod)(mod)(mod)2)(mod)(mod)3)(mod)(mod)mmababmabmabmabmaamabmbam
34、abmbcmac 义给定正整数，如果用 去除两个整数 和 所得的余数相同，我们就说，对 同余，记为，如果余数不同，对 就不同余，记为。质自反性；对称性，则；传递性，定定 15 15性性 2 2 1)1)(mod)|(mod)(mod),1)(mod)2)(mod)3)(mod)4)()()(mod)()nnmabmm ababmmaxybxymxyabmabmf af bmf x。整数，对模 同余的充分必要条件是。如果，则有，其中，为任意整数；，为任意给定整系数多项式。定定理理1111定定理理1212 2.2.2 数论知识(续)公倍数。表示最小，这里，则，若)(mod21)(mod21nimm
35、mbanimba 定定理理1 13 32.2.2 数论知识(续)剩余类和完全剩余系剩余类和完全剩余系011011(011)01 01)012)(mod)rmmjmC rmqmrqCCCmmCCCmCjmxyxym设 是一个给定整数，表示所有形如的整数组成的集合，其中，则，叫做模 的剩余类。设，是模 剩余类，则有每个整数都包含在某一个剩余类中，这里；两个整数，属于同一类的充分必要条件是定定1616定定理理1414义义011011011#011mjjmmCCCaCjmmaaammmmmm。在模 的剩余类，中各取一个数，此 个数，称为模 的一组完全剩余系。由定义立即得到：个整数成为模 的完系的充要条
36、件为两两对模 不同余。常用的完全剩余系，称为模 的非负最小完全剩余系。定定1717定定理理1515 义义2.2.2 数论知识(续)缩系缩系的缩系。也是模的缩系则是通过模，若不同余。两模系的充要条件为它们两为缩，互素的整数，则个与是，若个数。的一组缩系含有模。是素数时互素的数的个数。显然中与，的值为序列函数，是一个定义在整数上的欧拉函数的一组缩系。组成的集叫模各取一个数互素的剩余类，在其中，就把它叫做一个与模互素显然一个互素全部互素的剩余类里的数与如果一个模maxmxmamaammaammpppnnnnmmmmmm1)()()(1)(110)()()()(1)(1 定理18定理18定理17定理1
37、7定理16定理16定义19定义19定义18定义182.2.2 数论知识(续)mod()mod1(1)(1 )(。是素数，则若费马小定理立刻可得：由。，则，设欧拉定理paapmamampm )()(定定理理2 20 0定定理理1 19 9定定理理1 19 92.2.2 数论知识(续)。，则的标准分解设。，则，若立得由的缩系。通过模的缩系，则，过模分别通，而，设kkpppnnpppnnmmmmmmmmxmxmmmxxmmmmk111111)()()()(1)(1)(0021212121212121122121212121 定理21定理21 定理22定理22推论1推论1定理21定理212.2.2 数
38、论知识(续)一次同余式一次同余式1110000()0(01)0 ()0(mod)0(mod)()0(mod)(mod)nnnninf xa xaxa xana inmf xmmamnxf xmxxmam 义设，其中，是整数，又设，则叫模 的同余式。若，则 叫次数。如果 满足，则叫同余式的解。不同的解是指互不同余的解。设，定定 20 20 定定理理2323()1()1()1()110 (mod)(mod)1(mod)mmmaxbmxbamaxmaaa，则同余式恰有一个解，这个解就是。特别地，我们将的解称为 的逆元，记为。2.2.2 数论知识(续)1110()00(mod)()0(mod)nnnn
39、npf xa xaxa xanapf xpn 定理 设 是素数，是一个整系数多项式，则同余式最多有 个解。定定理理24 24(Lagrange)(Lagrange)2.2.2 数论知识(续)(3)原根原根 0()1 1(mod)1(mod)0|()lnmmalamlamamlamnl namllm设，是使成立的最小正整数，则 叫做 对模 的次数。设 对模 的次数为，如有，则。论设 对模 的次数为，则。定定2121定定理理2525推推 2 2 义义 2.2.2 数论知识(续)。次数都为的们对模两两不同余的整数，它个对模，则恰有为的次数，它对模整数是一个素数，如果存在设。的次数均为对模，个数，则的
40、次数是对模设。，则，的次数为对模，的次数是对模设两两互不同余。对模，则的次数为对模设lppllpaplmll allmallllmalmamaaalmal)(0 1)()()(01 1112 定理28定理28推论3推论3定理27定理27 定理26定理262.2.2 数论知识(续)2()2 0()1()()10 2 42(1)mllmgmgmmgmgmmgmgggmmpp lpm设整数，如果整数 对 的次数为，则 叫模 的一个原根。设，则 是 的一个原根的充分必要条件是，组成模 的一组缩系。，为奇素数 时，有原根。定定 2 2定定理理2929定定理理3030 义义2.2.2 数论知识(续)的一个
41、原根。是知由，故，设的一个原根。是。，分必要条件是的一个原根的充是，则，的所有不同素因子是，设4 41 12 24 41 12 2 1)41(mod11812)41(mod14012525240)41(411)21()(mod1 1)()(2820213)(21定定理理3 31 1例例子子8 8定定理理3 31 1 qqmsimgmgmgqqqmmiqms2.2.3 群环域的概念(1)群群1111()1)()()()2)1 11 3)1()GG ab cG ab ca bcGaGa aaaGaGaaaaaaG 一个群，是由一个非空集合 和在其上的一个二元运算组成，且满足如下属性：对任意，结合律
42、；存在一个单位元对于所有的，有；对任意，存在一个，满足，叫做 的逆元。一个群是阿贝尔群 交换群，如果定定 23 23 义义4)a bGa bb a还满足对于所有，。2.2.3 群环域的概念(续)11)02)3)2 204)eTFXOReFTT整数集在加法下构成群，单位元；有理数，实数，复数集在乘法 下构成群；所有矩阵在加法下构成群，所有行列式不等于 的矩阵在乘法 下构成群；集合，在逻辑异或下构成群，单位元，。例例子子9 9 2.2.3 群环域的概念(续)(2)环环(,)()()1)(,)02)()()3)()()()()RRRa b cRab ca bca b cRabca ba cbca 一
43、个环是一个非空集合和在其上定义的两个二元运算加法 和乘法，且满足如下属性：是一个阿贝尔群，加法单位元为；运算的结合律。即对于所有，；运算对运算的分配律。即对于所有，和定定 24 24 义义()()1 01 1 b acaa bRa bb aaRaaa。进一步，如果对于所有，有，称其为交换环。如果对于所有，存在乘法单位元满足，称其为有单位的环。2.2.3 群环域的概念(续)1)2)m整数，有理数，实数，复数集上的加法和乘法运算均构成单位交换环；对于整数集上的模任意整数 的加法和乘法也构成单位交换环。例例子子10 10 2.2.3 群环域的概念(续)01)1 12)p 如果一个交换环中的非 元在乘
44、法运算下构成一个群，则该交换环叫做域。有理数，实数，复数集上的加法和乘法运算下均构成域，但是整数集上的加法和乘法运算不构成域，因为只有和 有乘法逆元；整数集上的对于模素数 的加法和乘法构成域。一个代数结构的元的数量是有限的我们称这个代数结构是有限的，否则是无限的。元的个数叫做代数结构的阶。定定 25 25 例例子子11 11 义义(3)域域2.3 对称密码算法：DES和AES 对称密钥体制的问题对称密钥体制的问题 (1)在安全加密体制中，密钥是需要经常变更的，使得已丢失的密钥只能泄露数量有限的信息。(2)密钥的分发必须保证安全。一种方式就是对密钥分解分发，如图2.9。(3)密钥数目的增长与交换
45、信息的人数的平方成正比，在人数多的时候，可以考虑使用信任中心，如图2.10。2.3 对称密码算法：DES和AES(续)图2.9 密钥的分块分发图2.10 加密信息分发中心2.3 对称密码算法：DES和AES(续)2.3.1 DES算法描述 1974年，IBM 向国家标准局(NBS)提交了一个名为 LUCIFER的加密算法。NBS将其转给了国家安全局(NSA)进行审定，之后就得到了一个名为数据加密标准DES的算法。1977年，NBS 正式将其用于无限制级的政府通信。其间NBS和NSA可能存在某些误会。NSA原本打算DES仅用于硬件执行，但是NBS却公布了过多的技术细节以致于人们可以根据其写出DE
46、S加密软件。如果NSA预料到后续的情况发展变化，他们或许不会同意公布DES。2.3.1 DES算法描述(续)DES是分组密码，每个分组为64比特数据。64比特明文通过加密最后成为64比特密文。DES的密钥通常写为64比特，但每8比特有一位奇偶效验位，可以忽略。因此，实际只有56比特。算法只使用不超过64位的标准算术操作和逻辑操作，所以在70年代仅使用硬件就可以容易地实现算法。算法的重复特性非常适合专用芯片执行。DES 的核心是一个被称为Feistel系统的部件。2.3.1 DES算法描述(续)图2.11 DES算法总体流程2.3.1 DES算法描述(续)相反的次序。的过程，除了密钥使用解密过程
47、使用完全相同。初始计算的逆得到密文接着使用，调换前后次序得到系统。算过程就是要定义的函数。这一计是一个在后面将比特的串，产生的一个是从密钥这里，进行如下操作：，对于比特。是后比特是前，这里写为，初始计算得到的比特串通过一个固定消息组成：算法的加密由三个阶段)(3)Feistel 48)(161 (2)32 32 )(1)DES161611616111000000LRIPcLRfKKKRf LR RLiRLRLmmIPmmiiiiiii2.3.1 DES算法描述(续)载入芯片而提出的。的年代为了使算法更有效意义，它可能只是在初始计算没有任何密码最终计算初始计算702557174994113326
48、5818501042234275919511143335286020521244436296121531345537306222541446638316323551547739326424561648840 71523313947556351321293745536131119273543515919172533414957816243240485664614223038465462412202836445260210182634425058 1IPIP初始计算初始计算2.3.1 DES算法描述(续)函数函数 f(Ri-1,Ki)Ri1扩张E(Ri1)KiB1B2B3B4B5B6B7B8S1S
49、2S3S4S5S6S7S8C1C2C3C4C5C6C7C8置换f(Ri-1,Ki)图 2.12 f函数计算结构2.3.1 DES算法描述(续)。，比特输出到每个盒的决定。通过这种方法得列由由盒的行的输入。盒做为为写比特。为，这里每个并将其写成计算扩展计算。比特使用如下表扩展为比特按如下描述运行：函数82154326162182111114 -.(3)6 )()2(1323130292829282726252425242322212021201918171617161514131213121110989876545432132)(48)()(32(1),CCCbbbbbbSSSBbbbBBBBB
50、KRERERKf(Rjjjjiiiiii2.3.1 DES算法描述(续)图 2.13 DES的S盒2.3.1 DES算法描述(续)2541122630131993273214248210311852623151172812292120716-P)(32 (4)1821计算盒的值。，比特串就是函数算。结果通过下面的表做置换计串iiKRfCCC2.3.1 DES算法描述(续)密钥变换密钥变换41220285132129374553616142230384654627152331394755633644526031119273543515921018263442505819172533414957
