本书共分3篇15章, 第1篇为网络安全基础, 共3章, 主要介绍计算机网络和网络安全的基础知识; 第2篇为密码学基础, 共5章, 详细讨论了密码学的理论与技术; 第3篇为网络安全技术与应用, 共7章, 深入介绍了网络安全实践中的技术和产品。本书内容丰富, 概念清楚, 语言精练。在网络安全基本知识和保密学理论方面, 力求深入浅出, 通俗易懂; 在网络安全产品的介绍方面, 力求理论与实践相结合, 具有很强的实用性。

       第5章  双（公）钥密码体制  双钥（公钥）体制于1976年由W. Diffie和M. Hellman提出，同时R. Merkle也独立提出了这一体制。J. H. Ellis的文章阐述了公钥密码体制的发明史，说明了CESG的研究人员对双钥密码体制发明所做出的重要贡献。这一体制的*大特点是采用两个密钥将加密和解密能力分开：一个密钥公开作为加密密钥，称为公钥；一个密钥为用户专用，作为解密密钥，称为私钥。通信双方无须事先交换密钥就可进行保密通信。但是从公开的公钥或密文分析出明文或私钥，则在计算上是不可行的。若以公开钥作为加密密钥，以用户专用钥作为解密密钥，则可实现多个用户加密的消息只能由一个用户解读；反之，以用户专用钥作为加密密钥而以公开钥作为解密密钥，则可实现由一个用户加密的消息而使多个用户解读。前者可用于保密通信，后者可用于数字签名。这一体制的出现是密码学史上划时代的事件，它为解决计算机信息网中的安全提供了新的理论和技术基础。  自1976年以来，双钥体制有了飞速发展，人们不仅提出了多种算法，而且出现了不少安全产品，有些已用于NII和GII之中。本章介绍其中的一些主要体制，特别是那些既有安全性，又有实用价值的算法。其中，包括可用于密钥分配、加解密或数字签名的双钥算法。一个好的系统不仅算法要好，还要求能与其他部分（如协议等）进行有机 组合。  由于双钥体制的加密变换是公开的，任何人都可以采用选择明文来攻击双钥体制，因此，明文空间必须足够大才能防止穷尽搜索明文空间攻击。这在双钥体制应用中特别重要（如用双钥体制加密会话密钥时，会话密钥要足够长）。一种更强有力的攻击法是选择密文攻击，攻击者选择密文，然后通过某种途径得到相应的明文，多数双钥体制对于选择密文攻击特别敏感。攻击者通常采用两类选择密文攻击：            （1）冷漠选择密文攻击。在接收到待攻击的密文之前，可以向攻击者提供他们所选择的密文的解密结果。

     （2）自适应选择密文攻击。攻击者可能利用（或接入）被攻击者的解密机（但不知其秘密钥），而可以对他所选择的、与密文有关的待攻击的密文，以及以前询问得到的密文进行解密。  本章介绍双钥体制的基本原理和几种重要算法，如RSA、ElGamal、椭圆曲线、基于身份的密码体制和中国商用密码SM2算法等密码算法。  Diffie [Diffie 1992]曾对双钥体制的发展做了全面论述。   双钥密码体制的基本概念  对于双钥密码体制来说，其安全性主要取决于构造双钥算法所依赖的数学问题。要求加密函数具有单向性，即求逆的困难性。因此，设计双钥体制的关键是首先要寻求一个合适的单向函数。

        5.1.1 单向函数  定义 5-1 令函数f是集A到集B的映射，用表示。若对任意 ，有，则称f为单射，或1-1映射，或可逆的函数。  f为可逆的充要条件是，存在函数，使对所有有。  定义5-2 一个可逆函数，若它满足：

       （1）对所有，易于计算。

       （2）对“几乎所有”由求x“极为困难”，以至于实际上不可能做到，则称f为单向（One-Way）函数。  定义中的“极为困难”是对现有的计算资源和算法而言。Massey称此为视在困难性（Apparent Difficulty），相应函数称为视在单向函数，以此来与本质上的困难性（Essential Difficulty）相区分[Massey 1985]。  例5-1 令f是在有限域GF(p)中的指数函数，其中p是大素数，即  （5-1）  式中，，x为满足的整数，其逆运算是GF(p)中定义的对数运算，即  （5-2）  显然，由x求y是容易的，即使当p很大，例如时也不难实现。为方便计算，以下令(=2。所需的计算量为log次乘法，存储量为(log p)2b，例如时，需做100次乘法。利用高速计算机由x计算可在0.1ms内完成。但是相对于当前计算GF(p)中对数*好的算法，要从计算x所需的存储量大约为b，运算量大约为。当p=2100时，所需的计算量为次，用计算指数一样快的计算机进行计算需时约秒（1年=秒，故约为1600年。其中假定存储量的要求能够满足）。由此可见，当p很大时，GF(p)中的，为单向函数。  Pohlig和Hellman对(p-1)无大素因子时给出一种快速求对数的算法[Pohlig等 1978]。特别是当时，从求x的计算量仅需次乘法。对于，在高速计算机上大约仅需时10ms。因此，在这种情况下，就不能被认为是单向 函数。  综上所述，当对素数p，且p-1有大的素因子时，GF(p)上的函数是一个视在单向函数。寻求在GF(p)上求对数的一般快速算法是当前密码学研究中的一个重要课题。

        5.1.2 陷门单向函数  单向函数是求逆困难的函数，而陷门单向函数（Trapdoor One-Way Function）是在不知陷门信息下求逆困难的函数，当知道陷门信息后，求逆易于实现。这是Diffie和Hellmam[Diffie等 1976]引入的有用概念。  号码锁在不知预设号码时很难打开，但若知道所设号码则容易开启。太平门是另一例，从里面向外出容易，若无钥匙者反向难进。但如何给陷门单向函数下定义则很棘手，因为：

       （1）陷门函数其实不是单向函数，因为单向函数是在任何条件下求逆都是困难的。

      （2）陷门可能不止一个，通过试验，一个个陷门就可容易地找到逆。如果陷门信息的保密性不强，求逆也就不难。  定义5-3 陷门单向函数是一类满足下述条件的单向函数：，，Z是陷门信息集。

      （1）对所有，在给定z下容易找到一对算法和，使对所有，易于计算及其逆，即  （5-3）  （5-4）  而且当给定z后容易找到一种算法，称为可用消息集鉴别函数，对所有易于检验是否，是可用的明文集。

      （2）对“几乎所有”，当只给定和时，对“几乎所有”，“很难”（即“实际上不可能”）从算出x。

      （3）对任一z，集必须是保密系统中明文集中的一个“方便”集。即便于实现明文到它的映射（在双钥密码体制中是默认的条件）。（Diffie和Hellman定义的陷门函数中，，对所有Z成立。实际中的取决于Z）。

       5.1.3 公钥系统  在一个公钥系统中，所有用户共同选定一个陷门单向函数，加密运算E及可用消息集鉴别函数F。用户i从陷门集中选定zi，并公开和。任一要向用户i发送机密消息者，可用检验消息x是否在许用消息集之中，然后送给用户x即可。  在仅知y，和的情况下，任一用户不能得到x。但用户i利用陷门信息，易于得到。  定义5-4 对和任意，。若  （5-5）  成立，则称F为可换单向函数。  可换单向函数在密码学中更有用。

       5.1.4 用于构造双钥密码的单向函数  Diffie和Hellman在1976年发表的文章虽未给出陷门单向函数，但大大推动了这方面的研究工作。双钥密码体制的研究在于，给出这种函数的构造方法以及它们的安全性。  陷门单向函数的定义并没有指出这类函数是否存在，但其中指出：一个单钥密码体制，如果能抗击选择明文攻击，就可规定一个陷门单向函数。以其密钥作为陷门信息，则相应的加密函数就是这类函数。这是构造双钥体制的途径。  下面是一些单向函数的例子。目前多数双钥体制是基于这些问题构造的。

       1. 多项式求根  有限域GF(p)上的一个多项式   当给定，p及x时，很容易求y，利用Honer's 法则，即  （5-6）  *多有n次乘法和n－1次加法。反之，已知，要求解x需能对高次方程求根。这至少要次乘法（这里，表示不大于a的*大整数），当n，p很大时很难求解。

       2. 离散对数DL（Discrete Logarithm）  给定一大素数p，p-1含另一大素数因子q，可构造一乘群，它是一个p-1阶循环群。其生成元为整数g，。已知x，容易求，这只需次乘法，如，g15= (((1·g)2·g)2·g)2·g mod p，要用3+4?1＝6次乘法。  若已知y, g, p，求为离散对数问题。*快求解法运算次数渐近值为  （5-7）  p=512时，。  若离散对数定义在中的阶循环群上，Shanks和Pohlig-Hellman等的离散对数算法预计算量的渐近式为  （5-8）  求一特定离散对数的计算量的渐近式为  （5-9）  具体请参阅[LaMacchia等 1991；McCurley 1990]。  广义离散对数问题是在n阶有限循环群G上定义的。  3. 大整数分解FAC（Factorization Problem）  判断一个大奇数n是否为素数的有效算法，大约需要的计算量是，当n为256或512位的二元数时，用当前计算机做可在10分钟内完成。  若已知两个大素数p和q，求n = p·q只需一次乘法，但若由n，求p和q，则是几千年来数论专家的攻关对象。迄今为止，已知的各种算法的渐近运行时间如下：

      （1）试除法：*早的也是*慢的算法，需试验所有小于sqrt(n)的素数，运行时间为指数函数。

      （2）二次筛（QS）：  （5-10）  该算法为小于110位整数*快的算法，倍多项式二次筛（MPQS）是QS算法的变型，它比QS算法更快。MPQS的双倍大指数变型还要更快一些。

       （3）椭圆曲线（EC）：  （5-11）  （4）数域筛（NFS）：  （5-12）  式中，p是n的*小的素因子，*坏的情况下。当，要用年（一秒进行100万次运算）。虽然整数分解问题已进行了很长时间研究，但至今尚未发现快速算法。目前对于大于110位的整数数域筛是*快的算法，曾用于分解第9个Fermat数。目前的进展主要是靠计算机资源来实现的。二次筛法可参阅[Pomerance 1984；Carton等 1988]；数域筛法可参阅[Lenstra等 1993]；椭圆曲线法参阅[Pollard 1993；Lenstra 1987；Montgomery 1987]。  T(n)与L(p)的表示式大致相同，一般当n=p时，解离散对数要更难些。  RSA问题是FAC问题的一个特例。n是两个素数p和q之积，给定n后求素因子p和q的问题称为RSAP。求分解问题有以下几种形式：

      （1）分解整数n为p和q。

      （2）给定整数M和C，求d使。

      （3）给定整数e和C，求M使。

      （4）给定整数x和C，决定是否存在整数y使（二次剩余问题）。

        4. Diffie-Hellman问题（DHP）  给定素数p，令(为的生成元，若已知和，求的问题为Diffie-Hellman问题，简称DHP。若(为循环群G的生成元，且已知和为G中的元素，求的问题为广义Diffie-Hellman问题，简记为GDHP[den Boer 1988；Maurer 1994b；Waldvogel等1993；McCurley 1988]。  在[Menezes等 1997]一书的第4章对双钥密码体制公钥参数的生成和有关算法进行了全面介绍，该书的第3章对密码中用到的数学难题进行了全面系统的论述。此外，还可参阅[Pomerance 1990；Adleman等1994；Bach 1990；Lenstra等1990a，1990b]。  RSA密码体制  1978年，MIT的3位年轻数学家R.L.Rivest，A.Shamir和L.Adleman发现了一种用数论构造双钥的方法[Rivest等 1978，1979]，称为MIT体制，后来被广泛称为RSA体制。它既可用于加密，又可用于数字签名，易懂且易于实现，是目前仍然安全并且逐步被广泛应用的一种体制。国际上一些标准化组织（如ISO，ITU和SWIFT等）均已接受RSA体制作为标准。在因特网中所采用的PGP（Pretty Good Privacy）中也将RSA作为传送会话密钥和数字签名的标准算法。  RSA算法的安全性基于5.1节介绍的数论中大整数分解的困难性。

        5.2.1 RSA密码体制  独立选取两个大素数和（各100～200位十进制数字），计算  （5-13）  其欧拉函数值为  （5-14）  随机选一整数e，，。因而在模((n)下，e有逆元  （5-15）  取公钥为n，e。密钥为d（，不再需要，可以销毁）。  加密：将明文分组，各组在mod n下，可*地表示出来（以二元数字表示，选2的*大幂小于n）。各组长达200位十进制数字。可用明文集为   注意，是很危险的。的概率