王保仓，贾文娟，陈艳格,3

(1.西安电子科技大学 综合业务理论与关键技术国家重点实验室，陕西 西安 710071; 2.西安电子科技大学 通信工程学院，陕西 西安 710071; 3.许昌学院 信息工程学院，河南 许昌 461000)

0 引言

密码学(Cryptography)来源于希腊语Kryptós(隐藏的，秘密的)和Gráphein(书写)，是在被称为敌手的第三方存在的情况下安全通信技术的实践和研究。早期的密码学研究如何秘密地传送消息，而现在的密码学从最基本的消息机密性延伸到消息完整性检测、发送方/接收方身份认证、数字签名以及访问控制等信息安全的诸多领域，是信息安全的基础与核心。

密码学可以分为密码编码学和密码分析学两个分支。其中密码编码学是研究对信息进行编码以实现隐蔽信息的学问，而密码分析学是关于如何破译密码或其实现的研究，两者相互对立又相互促进。

密码体制有两种：对称密码体制(又称为单钥密码体制)和非对称密码体制(又称为双钥密码体制或公钥密码体制)。对称密码体制使用相同的密钥(秘密密钥)对消息进行加密/解密，系统的保密性主要由密钥的安全性决定，而与算法是否保密无关。对称密码体制设计和实现的中心课题是：用何种方法产生满足保密要求的密钥以及用何种方法将密钥安全又可靠地分配给通信双方。对称密码体制可以通过分组密码或流密码来实现，它既可以用于数据加密，又可以用于消息认证。非对称密码体制使用公钥加密消息，使用私钥来解密。使用非对称密码体制可增强通信的安全性。

本文首先简单介绍密码学的发展历程，详细阐述了几种最基本的密码学原语：Hash函数；对称密码体制中的分组密码、流密码和消息认证码(MAC)；非对称密码体制中的密钥交换、公钥加密和数字签名，最后对于密码学的发展趋势，主要介绍了格密码的发展。

1 密码学的发展历程

密码学的发展大致可以分为3个阶段：1949年之前的古典密码学阶段；1949年至1975年密码学成为科学的分支；1976年以后对称密钥密码算法得到进一步发展，产生了密码学的新方向——公钥密码学。

1949年以前仅凭一些直观的技巧和经验对文字进行变换来设计大多数密码系统，保密通信和密码学中一些最本质的东西并未被揭示。

被称为“信息论之父”的香农(Shannon)于1949年发表了经典论文“保密系统的通信理论”[1]，他在密码学中引入信息论，为密码学的发展奠定了坚实的理论基础，从而把已有数千年历史的密码学推向科学的轨道，形成了密码学学科。

1976年，W.Diffie和M.Hellman在发表的文章“密码学的新方向”[2]中首次公开提出了公钥密码(Public-key Cryptography)的概念。公钥密码的提出实现了加密密钥和解密密钥之间的独立，解决了对称密码体制中通信双方必须共享密钥的问题，在密码学界具有划时代的意义。

2 Hash函数及其应用

2.1 概念

Hash函数(也称为散列函数、哈希函数或杂凑函数)是一个从消息空间到像空间的不可逆映射。换言之，Hash函数h是一个用于将任意长的消息m映射为较短的、固定长度的一个值h(m)的公开函数，称函数值h(m)为Hash值或Hash码或消息摘要，因此，Hash函数是一种具有压缩性质的单向函数。一个“好”的Hash函数具有下述特点：在大的输入集合上使用该函数，其结果是均匀分布且看起来随机的。概括地说，Hash函数的首要目标是用来保证数据的完整性，对于消息m中任何一个或几个比特的改变，都将极大可能地改变其对应的Hash值。

密码学Hash函数是在安全应用中使用的Hash函数。密码学Hash函数要求如下2种情况在计算上是不可行的(即没有比穷举攻击更有效的攻击方法)：① 对预先指定的Hash值找到其对应的消息(单向性)；② 找到2个对应相同Hash值的不同的消息(抗碰撞性)。由于Hash函数具有单向性和抗碰撞性，故常用Hash函数来判断数据是否被篡改过。

2.2 密码学Hash函数的应用

密码学Hash函数的压缩性、单向性和抗碰撞性等特点使其能够解决实际应用中遇到的很多棘手的安全问题，下面简要介绍密码学Hash函数的几个重要应用。

2.2.1 消息认证

用来验证消息完整性的一种机制或服务称为消息认证。消息认证用来确保接收方收到的数据确实和发送方发送的一样(即没有修改、插入、删除或重放)。此外，一般还要求消息认证机制能够确保发送方所声称的身份的真实有效性。当Hash函数用于提供消息认证功能时，其函数值通常被称为消息摘要。

消息认证中使用Hash函数的本质为：发送方使用该Hash函数计算待发送消息的Hash值，然后将Hash值和消息一起发送给接收方。接收方收到发送方发送的Hash值和消息后，对消息执行相同的Hash计算，并将结果与收到的Hash值进行比较。如果计算的Hash值与收到的Hash值不一致，则接收者推断出消息(也可能是Hash值)被篡改了。必须通过安全的方式传输Hash函数的运算结果，因为Hash函数必须得到保护，使得如果攻击者替换或篡改消息的话，对于攻击者而言，他(她)不能轻易地同时修改Hash值来蒙骗接收方。

用来提供消息认证的Hash函数的基本使用方式有6种：① 用对称密码算法加密消息与Hash值的链接，该方式还可以提供保密性；② 用对称密码算法仅加密Hash值，在不要求保密性的情况下，可以用该方式减少处理负担；③ 用公钥密码算法和发送方的私钥仅加密Hash值，该方式还对发送方发送的消息提供了数字签名；④ 用公钥密码算法和发送方的私钥加密消息的Hash值与消息链接，再用对称密码算法加密链接后的结果，该方式还可以提供保密性和数字签名；⑤ 通信双方A和B共享秘密值S，A计算消息M和S链接在一起的Hash值，并将该Hash值附在M后面发送给B。B收到A发送的信息后，重新计算M和S的链接的Hash值以对M进行认证，该方式仅提供认证；⑥ 用对称密码算法加密⑤中消息M与Hash值的链接，该方式还可以提供保密性。

2.2.2 数字签名

在进行数字签名的过程中，使用用户的私钥对消息的Hash值加密，其他任何知道该用户公钥的人都能通过数字签名对消息的完整性进行验证。在这种情况下，如果攻击者想要篡改消息，则需要知道用户的私钥。

用于提供数字签名的Hash函数的基本使用方式有2种：① 利用发送方的私钥，用公钥密码算法仅加密Hash值，该方式还可以提供认证；② 利用发送方的私钥加密Hash值，再用对称密码算法对消息和公钥密码算法加密后的Hash值进行加密，该方式还可以提供保密性。

Hash函数的应用除了消息认证和数字签名外，还可以利用Hash函数来产生单向口令文件等，关于Hash函数的更多应用可以阅读参考文献 [3-6]。

3 对称密钥密码体制

3.1 流密码

流密码(Stream Cipher，又称序列密码)的基本思想是利用密钥k产生密钥流z=z0z1…，并使用规则y=y0y1…=Ez0(x0)Ez1(x1)…对明文串x=x0x1…进行加密得到密文串y=y0y1…，解密时以同步产生的同样的密钥流z=z0z1…实现解密。密钥流由密钥流生成器G产生：zi=G(k,σi)，其中σi是加密器中的记忆元件(存储器)在i时刻的状态，G是由密钥k和i时刻的状态σi产生的函数。流密码的强度完全依赖于密钥流生成器所生成的序列的不可预测性(Unpredictability)和随机性(Randomness)，故流密码的核心是密钥流生成器的设计。实现可靠解密的关键技术是保持接收端和发送端密钥流的精确同步。

流密码通常可以分为同步流密码(Synchronous Stream Cipher，SSC)和自同步流密码(Self-Synchronous Stream Cipher,SSSC)两大类。如果σi与明文消息无关，则称此类流密码为同步流密码，否则为自同步流密码。

一个性能良好的序列密码最基本的设计原则是密钥流生成器的不可预测性，可将其分解为以下基本原则：① 大周期；② 高线性复杂度及好的k-错线性复杂度；③ 良好的统计特性；④ 足够的“混乱”；⑤ 足够的“扩散”；⑥ 可以抵抗不同形式的攻击。

近年来提出了不少新的易于实现的流密码算法，其设计思想差异较大且各有特点。有些算法适合硬件实现，有些适合软件实现，有些则兼顾两者的需要来设计。下面简单介绍几种比较典型的流密码算法。

祖冲之算法集(ZUC算法)是由中国科学院数据保护和通信安全研究中心(DACAS)研制，包括ZUC-128流密码算法(LTE算法的核心)、加密算法128-EEA3(由ZUC定义的LTE加密算法)和完整性算法128-EIA3(由ZUC定义的LTE完整性保护算法)，2011年9月通过3GPP全会，正式成为LTE的第3种密码算法。2018年1月，为了满足5G应用的需求，中国科学院软件研究所公布ZUC-256算法草案，让各界专家对算法安全性进行评估。

SOSEMANUK[7]是由Come Berbain，Olivier Billet，Anne Canteaut等人提出的基于字运算的面向软件的同步流密码，是eSTREAM计划最后选出的4个面向软件的流密码算法之一。SOSEMANUK算法包括初始化阶段和密钥流产生阶段，其密钥长度在128～256 bit之间变化，初始化向量IV的长度为128 bit，任何密钥长度可达到128 bit的安全。 SOSEMANUK的算法结构受流密码SNOW和分组密码SERPENT的影响，既使用SNOW2.0的基本设计原则，也使用来自SERPENT的转换。与SNOW相比，SOSEMANUK具有更高的性能，初始化阶段使用SERPENT的缩减版本，从效率和安全性方面改进了传统的初始化过程。

Grain[8]算法是由Martin Hell，Thomas Johansson和Willi Meier共同设计的一种面向硬件的二元加法流密码算法，算法分为初始化过程和密钥流产生过程，其设计面向门电路数、功耗以及内存等硬件资源受限的环境。Grain算法包括Grain-80算法和Grain-128算法2种，其中Grain-80算法是eSTREAM项目最终入选的面向硬件的3种流密码算法之一，其接收80 bit的密钥和64 bit的初始向量(IV)，初始化160个时钟周期后产生密钥流，在硬件上实现起来更容易且更小。由于Grain-80不足以抵抗时间-存储-数据(TMD)折衷攻击，Martin Hell等人设计了Grain-80的密钥增长版本——Grain-128，Grain-128在继承Grain-80优势的基础上，具有更强的安全性，且在以更多的硬件为代价时可以很容易地提升其速度。

其他几种典型的流密码算法，如RC4、A5/1等，可以阅读参考文献 [3,6]，此处不再赘述。

3.2 分组密码

分组密码(Block Cipher)是将明文消息编码表示后的序列划分成长为m的组，每组(长为m的矢量)分别在密钥的控制下变换成等长的输出序列(长为n的向量)，其加密函数为E:Vm×K→Vn，其中Vm是m维向量空间，K为密钥空间。通常取m=n，若m>n，则为有数据压缩的分组密码；若m

分组密码算法的设计应满足：① 为避免遭遇明文穷举攻击，明文分组长度应足够大；② 为避免防遭遇密钥穷举攻击，密钥长度足够大，但考虑到密钥的管理和加/解密速度，密钥又不能过长；③ 由密钥确定置换的算法要足够复杂，充分实现明文与密钥的扩散和混淆，可以抵抗已知的各种攻击；④ 加解密运算简单，易于软硬件的快速实现；⑤ 无数据扩展；⑥ 尽可能小的差错传播。

分组密码算法的基本设计原则为：① 混淆(Confusion)：密码设计者所设计的密码应使用密钥和明文以及密文之间尽可能复杂的关系以至于这种关系对密码分析者来说是无法利用的；② 扩散(Diffusion)：密码设计者所设计的密码应使得密钥的每一比特影响密文的许多比特以防止对密钥进行逐段破译，且明文的每一比特也应影响密文的许多比特以隐藏明文比特的统计特性。

分组密码的实现应该满足以下软硬件实现原则：① 软件实现原则：使用子块和简单的运算，如将分组n划分为子段，每段长为8，16或32 bit，选用作用于子段上的加、乘、移位等易于标准处理器实现的简单运算，避免用于软件难于实现的逐比特置换；② 硬件实现原则：加密和解密可用同样的器件来实现。

分组密码的运行模式有：电子密码本(ECB)模式、密码分组链接(CBC)模式、密码反馈(CFB)模式、输出反馈(OFB)模式和计数器模式(CTR)。对于每一种运行模式以及一些著名的分组密码算法的详细介绍可以阅读文献 [3-6]。

3.3 消息认证码

消息认证码(Message Authentication Code，MAC)指利用消息和一个由通信双方A和B共享的密钥K控制的公开函数来生成一个固定长度的、用做认证符的短数据块(也称为密码校验和)的一种消息认证技术。MAC的功能为：抗主动攻击、验证消息来源的完整性和真实性、验证消息的顺序性和时间性。

假设A要给B发送消息M，A先计算MAC=CK(M)，其中CK()是由密钥K控制的公开函数，再将M||MAC发送给B，B收到M||MAC后做与A相同的计算，得到一个新MAC，并比较新MAC与收到的MAC。如果仅收发双方A和B知道密钥K，且B计算得到的MAC与接收到的MAC一致，则上述过程就实现了以下功能：① B相信A发送的消息没有被篡改；② B相信A没有被冒充；③ 若消息中含有序列号，则接收方可以相信消息顺序是正确的。

MAC函数与加密算法相似，区别之一为MAC函数不必是可逆的，而加密算法必须是可逆的，因此与加密算法相比，MAC函数更不易被攻破。上述过程中，由于消息本身是以明文形式发送的，故这一过程只提供认证性而不提供保密性。文献 [3-5] 给出了MAC的其他几种使用方式，有兴趣的读者可以深入了解。

4 非对称密码体制

4.1 公钥密码算法

公钥密码算法的最大特点是使用2个不同但相关的密钥将加密和解密能力分开，其中公开的一个密钥称为公开密钥，简称公钥，用于加密；另一个密钥是用户专用的，因而是保密的，称为私有密钥，简称私钥，用于解密。

一般来说，公钥密码算法的应用可分为3类：① 加密/解密：发送方用接收方的公钥对消息加密，接收方用自己的私钥对密文进行解密得到原消息；② 数字签名：发送方用自己的私钥对消息进行签名；③ 密钥交换：通信双方交换会话密钥。公钥密码算法的密钥必须足够长以防受到穷搜索攻击，但是由于公钥密码算法所使用的可逆函数的计算复杂性与密钥长度往往不是呈线性关系的，而是增大得更快，故密钥长度太大会使得加解密速度太慢而不实用。因此公钥密码算法目前主要用于密钥交换和数字签名。公钥密码算法的安全性依赖于密码算法底层的数学问题(如整数分解和离散对数问题)的困难性，故设计安全的公钥密码算法的关键是先找到一个合适的单向函数。

定义1[6]：令函数f是集合A到集合B的映射，以f:A→B表示。若对任意x1≠x2，x1,x2∈A，有f(x1)≠f(x2)，则称f为单射，或可逆的函数。

定义2[6]：一个可逆函数f:A→B，若它满足：① 对所有x∈A，易于计算f(x)；② 对“几乎所有x∈A”由f(x)求x“极为困难”，以至于实际上不可能做到，则称f为单向(One-way)函数。

单向函数是给定函数值的情况下难于求逆的函数，而陷门单向函数(Trapdoor One-way Function)是在不知道陷门信息的情况下难于求逆，但在知道陷门信息后，可以在多项式时间内计算出函数的逆。

定义3[6]：单向陷门函数是满足下列条件的一类不可逆函数fk：① 若k和x已知，则容易计算y=fk(x)；② 若k和y已知，则容易计算x=fk-1(y)；③ 若y已知但k未知，则计算出x=fk-1(y)是不可行的。

自1976年W.Diffie和M.Hellman提出公钥密码体制的思想后，国际上出现了许多公钥加密算法，如基于大整数分解问题的公钥加密算法(如RSA等)、基于有限域乘法群上离散对数问题的公钥加密算法(如ElGamal公钥加密算法等)、基于椭圆曲线上离散对数问题的公钥加密算法(如椭圆曲线公钥加密算法等)、基于背包问题的公钥加密算法(如MH背包公钥加密算法等)、基于格上最短向量问题的公钥加密算法(如NTRU公钥加密算法等)、基于代数编码中线性解码问题的公钥加密算法(如McEliece公钥加密算法等)等。关于上述各种公钥加密算法的详细介绍可以阅读参考文献 [3-6]。

4.2 数字签名

NIST将数字签名(Digital Signature)定义为：在电子通信中鉴别发送者的身份，以及该通信中数据的完整性的一种密码学方法。数字签名是计算机及其在生活中的影响的结果，使用最广泛的数字签名类型依赖于公钥密码。

数字签名应具有以下特性：① 可信性：任何人可验证签名的有效性；② 不可伪造性：除合法签名者外，其他人伪造签名是困难的；③ 不可复制性：一个消息的签名不能复制为另一个消息的签名；④ 不可改变性：经签名的消息不能被篡改；⑤ 不可抵赖性：签名者事后不能否认自己的签名。

一个数字签名体制由3个算法(G，S，V)构成，其中G表示密钥生成算法(Key Generation Algorithm)，S表示签名算法(Signature Algorithm)，V表示验证算法(Verification Algorithm)。密钥生成算法的输入为1n(n为安全参数)，输出为一对公/私钥对。签名算法的输入是消息m和私钥sk，输出是对m的数字签名，记为s=Sigsk(m)。验证算法的输入是公钥pk、消息m和签名s，输出是接受或拒绝。

数字签名算法的安全性在于从m和s难以推出私钥sk，或伪造一个消息m′，使m′和s可被验证为接受。

数字签名算法有许多，除了基于大整数素因子分解困难性的RSA签名方案之外，还有基于离散对数问题的ElGamal签名方案、Schnorr签名方案、DSA签名方案、GOST签名方案、ESIGN签名方案、Okamoto签名方案等；基于大数分解的Fiat-Shamir签名方案等；基于身份的ElGamal签名方案、Schnorr签名方案等；基于椭圆曲线的签名方案SM2等。此外，在数字签名的实际应用中，往往需要将一般数字签名方案进行扩展，以满足各种特殊需求。例如，使用盲签名(Blincl Signature)保护信息拥有者的隐私；使用代理签名(Proxy Signature)实现签名权的安全传递；使用多重签名(Multi-Signature)实现多人对同一消息的签名；此外还有面向社团或群体的群签名(Group Signature)等。对于上述提到的各种基于不同困难问题的数字签名和各种特殊的数字签名的详细介绍，读者可以阅读文献 [3-6]。

4.3 密钥协商

密钥协商协议或机制指其中2个或多个参与方共同提供消息，推导出一个共享密钥，(理想状态下)任何一方不能预先确定会话密钥的值。密钥协商可分为动态密钥协商和静态密钥协商2种。这里主要介绍动态密钥协商技术。

Diffie-Hellman密钥协商协议是由W.Diffie和M.Hellman于1976年提出的通过公共信道安全地协商会话密钥的方法，已在商业产品中得到广泛应用。Diffie-Hellman密钥协商仅限于进行密钥交换，不能用于加/解密，算法的安全性由求解离散对数问题的困难性决定。关于Diffie-Hellman密钥协商协议的具体内容可以阅读参考文献 [9]。

两方Diffie-Hellman密钥协商协议可以很容易地扩展到三方或多方密钥协商协议，但是随着人数的增加，通信的轮数会迅速增加，因此在现实通信中该方法并不适用于群组密钥协商。

Diffie-Hellman密钥协商协议不包含通信双方的身份认证过程，所以处于通信双方中间的攻击者能够截获并替换他们之间交互的消息，最终可以监听到实际通信的数据，这种攻击被称为中间人攻击(Man-in-the-Middle Attack)。为了抵抗这种攻击，在协议运行时，参与者必须确定收到的消息的确来自目标参与者。为了抵抗中间人攻击，W.Diffie和P.C.Van Orschot等人于1992年提出了一种认证密钥协商方案(也称为端-端密钥协商方案，简记为STS)，该方案是Diffie-Hellman密钥协商协议的改进。STS的介绍以及关于密钥协商的其他知识见文献 [8]。

5 密码学应用

密码学在实际生活中的应用有很多，包括公开密钥基础设施(Public Key Infrastructure，PKI)、GSM鉴权过程、电子信封技术实现、密钥建立协议及区块链等。本小节主要介绍PKI。

PKI，又称公开密钥基础架构，简称公钥基础设施或公钥基础架构，是创建、管理、分发、使用、存储和撤销数字证书以及管理公钥加密所需的角色、策略和过程的集合。PKI的目的是促进用于一系列网络活动的信息的安全电子传输，如电子商务、网上银行及机密邮件等。

一般来讲，PKI由证书签发机构、证书注册机构、证书库、密钥备份/恢复/更新系统、证书废除处理系统及应用系统接口组成。

证书签发机构(Certification Authority，CA)是PKI的核心，用来存储、颁发和签署数字证书。证书注册机构(Registration Authority，RA)是CA的组成部分，是CA面对用户的窗口，它负责验证请求将其证书存储在CA的实体的身份。证书库是证书的集中存放地，用户可以从此处获得其他用户的证书，构造证书库可以采用X.500，LDAP，WWW，FTP，数据库等。

密钥的备份与恢复应该由可信机构来完成，且密钥的备份与恢复只针对解密私钥，签名私钥不能备份。当一个密钥由于某种原因或基于安全预防的考虑需要被换掉时，会进行密钥更新。由于一些不可预见的情形，如私钥丢失、被盗或其他一些利用私钥进行的诈骗活动，使得证书在有效期内(有效期在证书中指定)可能需要被废除。证书废除一般是将证书列入证书黑名单(CRL)，CRL一般存放在目录系统中。

6 密码学的发展趋势

公钥密码学自1976年提出到现在已发展了40余年，且在加密、签名和密码协议等各方面都取得了不错的成果。大多数数论密码，例如Diffie-Hellman协议和RSA密码系统，依赖于整数因子分解或离散对数问题的困难性假设。然而，Shor于1994年证明了整数因子分解和离散对数问题在量子计算机模型下是多项式时间可求解的[10-11]；2003年Shor的量子计算机又被推广到了椭圆曲线上[13]。这将使数论密码系统在可以使用大规模量子计算机的未来变得不安全。相比之下，对于格密码学中使用的经典问题，目前还没有已知的有效量子算法。这使得研究抗量子攻击的密码体制的重要性被提升到一个前所未有的高度。

2006年，国际密码学会举办了第一届后量子密码会议(Post-Quantum Cryptography)；2013年以来，欧洲电信标准研究所(ETSI)开展了3次“量子安全密码学”工作讨论会；2015年，NIST开展主题为“后量子世界里的网络安全”研讨会；2015年8月，美国国家安全局(NSA)发布了“向抗量子密码算法迁移的通告”；NIST于2016年2月启动了抗量子算法标准化工作，并于2016年4月发布了一篇题为“后量子密码学报告”的内部报告；欧盟ETSA也启动了量子安全密码标准化相关工作；Microsoft、CISCO、INTEL、Amazon等开始研究部署后量子密码计划；2016年6月在中国成都举行“亚洲抗量子密码论坛”；2018年4月，NIST主持召开了首届后量子时代公钥密码标准化的国际会议。

目前用于构建后量子密码系统的主要数学技巧有格、多变量方程、代数编码、Hash函数以及超奇异椭圆曲线同源问题等。下面主要介绍格密码。

从抽象代数的观点来看，所谓格(Lattice)就是n维实数空间Rn的一个离散加法子群。格中基向量的个数称为格的秩(Rank)，而基向量的维数称为格的维数(Dimension)。一般而言，总有格的秩不超过格的维数，若格的秩等于格的维数，则称该格为满秩格。

目前，存在很多基于格上困难问题构造公钥加密方案的方法。其中一部分主要是为了理论研究，这些方案相对于实际应用中的方案而言效率极低，但它们具有很强的可证明安全保证；另一部分是为了实际应用而提出的，这些方案比理论构造更加高效，但缺少严格的安全性证明。

1996年，Ajtai[14]首先给出了格上困难问题小整数解(Short Integer Solution，SIS)问题的困难性规约，并基于此问题构造了抗碰撞Hash函数。1997年，Goldrich，Goldwasser和Halevi提出了GGH加密方案[15]，它是McEliece方案的一个格近似版本，也是基于格的最早的加密方案。McEliece方案是一个基于有限域上线性译码问题的困难性构造的公钥加密方案。但是即使在设置较高参数的情况下，GGH方案仍然受到相应的密码攻击。因此，从实际应用的角度看，GGH方案是不安全的。然而在很多其他基于格的加密方案中经常会出现GGH及其HNF变形的形式，由于GGH/HNF方案的简洁性，其经常被作为讨论基于格的公钥密码方案的一个出发点。

Hoffstem，Pipher和Silverman于1996年提出了NTRU公钥加密方案(直到1998年才出版)[16]，它是一个基于环的公钥密码系统，且可以用特殊结构的格进行等价描述。目前，NTRU公钥加密方案是基于格的最实用的公钥加密方案，但不论是GGH还是早期的NTRU都不具有严格的安全性证明。2011年，Damien Stenhle和Ron Steinfeld通过对NTRU算法进行适当修改[17]，给出了NTRU的可证明安全版本，但其密钥生成算法和密钥格式发生改变，效率也因此降低。

1997年，Ajtai和Dwork构造了一个安全性基于格上u-SVP问题在最差情况下困难性假设的公钥密码方案——Ajtai-Dwork公钥密码方案[18]。该方案建立了格上困难问题的最差情况和平均情况之间的相互归约。同时，该方案也是第一个基于格上最差情况下的困难问题构造的具有严格安全性证明的公钥加密方案，为基于格问题构造密码方案开辟了新领域。

Regev于2005年首先提出LWE问题(Learning With Error Problem)[19]，同时给出了格上最差情况下的困难问题到平均情况下的LWE问题的一个归约，从而保证了LWE问题的困难程度。Regev提出的基于LWE的公钥加密方案是目前所有具严格安全性证明的方案中最高效的一个。尽管与NTRU相比，该方案效率仍然很低，但这是第一个在实际应用中具有合理计算特性的高安全性的理论构造。由于此方案的简洁性和高安全性，之后出现了许多满足其他安全性目标(如KDM安全、抗泄漏安全、抗辅助输入安全和满足同态性质的等)的变形。

2008年Gentry等人提出了格上的第一个可证明安全的签名方案和第一个基于身份的加密方案之后[20]，格上很多特殊性质的签名和加密方案被提了出来。尤其是2010年，基于身份的分级加密方案取得了大量的成果[21-23]。其他特殊性质的方案，如盲签名[24]、群签名[25]、基于身份的分级签名[26-27]等也都被提了出来。

毫无疑问，在现代密码学的研究领域，基于格的加密和签名等都取得了不错的成果。关于格上加密和签名的发展情况，有兴趣的读者可以阅读文献 [28]。

7 结束语

分组密码和流密码各有优势，在加密方案的设计中往往会将两者组合使用，如在面向软件的流密码SOSEMANUK中，初始化阶段使用分组密码SERPENT的30轮缩减版。为了达到不同的安全要求，实际应用中，并不是单一使用某一种加密体制，往往会将对称密码与非对称密码结合，如使用公钥密码算法协商出一个用于对称密码算法的会话密钥；为了提供保密性和数字签名，使用公钥加密算法和发送方的私钥加密消息M的Hash值后与M链接，再用对称加密算法加密。

密码技术是实现网络信息安全的核心技术，是保护数据的最重要的工具之一。通过加密变换，将可读文件变换成不可理解的乱码，从而起到保护信息和数据的作用。随着密码理论和技术的不断进步，出现了很多具有代表意义的密码系统。其中基于格理论的公钥加密方案由于其良好的安全特性和简单的代数结构成为目前研究的热点之一。量子算法和量子计算机的出现，使得设计可以抵抗量子攻击的标准化公钥密码方案成为密码学领域的重要研究内容。