揭秘密码背后的原理

　　密码学（Cryptography）是一门古老而年轻的科学，它的起源可以追溯到古罗马时代约公元110年的恺撒（Caesar）加密。然而，直到1949年Claude Elwood Shannon发表了《保密系统的通信理论》这篇划时代的论文，才标志着现代密码学的诞生。经典密码学所使用的密码设计和分析方法不是基于数学推理而是依赖密码学家的直觉和灵感。
　　凯撒密码盘
　　1976年，Diffie和Hellman发表了一篇影响力巨大的＂密码学新方向＂的文章。它标志着公钥密码学的诞生，从此密码学走出秘密领域，进入公开研究领域。在此之前，人们完全依靠彼此共享的秘密密钥来实现秘密通信，而公钥密码技术使得通信双方在没有事先共享任何秘密信息的情况下能够通信。在对称密钥加密情况下，两方同意共享一个可同时用于（任何一方）加密和解密的秘密密钥k。公钥加密在这个意义上是非对称的，具体来说，接收方产生一对密钥（pk,sk），被分别称为公钥和私钥，发送方用公钥将消息加密后发送给接收方，接收方用自己的私钥解密收到的密文。
　　公钥pk可以是通信发生之前，接收方以明文形式发给发送方。需要强调的是：两方之间的通信信道可以是公开的，但假设是认证的，即敌手无法修改接收方发给发送方的公钥（特别是敌手不能用自己产生的密钥去替换），这个问题可以用数字签名解决；也可以是接收方广泛地传播它的公钥pk，比方说通过她的个人网页，将公钥放置在她的名片中，公布在报纸上面，或者是放在某个公共目录使得任何想和接收方秘密通信的人都可以查到她的公钥。这种应用模型中，所有通信中多个发送方可以利用同样的pk与接收方多次通信。
　　由于公钥pk是公开的，因此公钥加密的安全不依赖于公钥的安全性，而仅仅依赖于私钥的安全性。与之相比，对称密钥加密假设了所有密钥的完全保密性，即通信双方必须共享密钥，并且不允许第三方获得此密钥。公钥加密方案可使多个发送者与单个接受者秘密通信，与之不同的是，依靠双方共享密钥的对称密钥加密只能让两方进行秘密通信。公钥加密体制的最主要的缺点是较对称密钥加密而言要慢至少2～3个数量级，因此，如果对称密钥加密是一种选择（换言之，如果双方能够事先安全地共享一个密钥），它就应当被使用。
　　不同种类的公钥加密算法
　　自公钥密码体制问世以来，密码学家们提出了多种公钥加密方案，它们的安全性都是基于数学基础问题的计算困难性。对于这些数学问题，如果利用已知的求解算法由公开信息计算出私钥的时间越长，那么基于这一数学问题的公钥加密系统被认为是越安全。
　　传统的公钥加密算法，根据所基于的数学困难问题来分类，有以下三类系统目前被认为是安全高效的(不考虑具有量子计算能力的敌手)：1.大整数分解系统(代表性的有RSA)；2.离散对数系统（代表性的有DSA）；3.椭圆曲线离散对数系统（ECC）。
　　自从1978年RSA体制提出来以后，人们对大整数分解问题的研究产生了强烈的兴趣，并取得了丰富的成果。在1985年，ElGamal型公钥密码体制提出以后，学术界又对有限域上离散对数的计算问题产生了浓厚的兴趣。值得注意的是，大整数分解问题的求解和有限域上离散对数问题的求解在本质上具有某种一致性，因而基于RSA假设的RSA和基于有限域上离散对数假设的DSA的安全强度几乎一致。
　　经过人们的不断努力，随着计算机运算效率的迅速提升，目前人们对于这两类问题的求解能力大大地提高，使得基于大整数分解的RSA体制受到很大的冲击，密钥长度为512比特的RSA不再认为是安全的（对于DSA也是如此），这就迫使RSA体制中使用的模数和基于有限域上离散对数问题的公钥密码体制中有限域的规模越来越大，同时需要更长的密钥来保证系统安全，这造成运算速度的降低，如DSA体制的运算速度随着其密钥长度的增加将以指数级下降。
　　椭圆曲线密码体制（Elliptic Curve Cryptography,ECC）是1985年由Koblitz和Miller分别提出的，利用基于有限域上椭圆曲线上点组成的加法群构造基于椭圆曲线离散对数问题的密码体制，二十多年来人们对椭圆曲线离散对数问题的经典求解算法的研究几乎没有本质进展。
　　椭圆曲线密码体制的安全性是建立在求椭圆曲线离散对数问题（Elliptic Curve Discrete Logarithm Problem,ECDLP）难解的基础上。ECC与RSA、DSA相比有很多技术优点：椭圆曲线离散对数问题目前只存在指数时间的经典算法，而大整数分解和有限域上离散对数问题存在亚指数级的经典算法，这就体现在ECC比RSA的每比特密钥的安全性能更高，密钥长度160比特的ECC与1024比特的RSA、DSA有相同的安全强度，而210比特ECC与2048比特的RSA、DSA具有相同的安全强度，即达到相同安全强度的ECC的密钥大小和系统参数与RSA、DSA相比要小得多，意味着它所占的存储空间较小，且ECC的运算速率比RSA、DSA快得多。ECC的上述特点使得它在许多领域已经取代RSA,成为通用的公钥加密算法，包括作为轻量密码算法模块和应用于网络传输层协议TLS等。
　　必须注意实际工程中实现的密码不同于教科书式密码。下面我们将介绍＂教科书式RSA＂加密和＂教科书式ElGamal＂加密，并分析其不安全性。
　　＂教科书式RSA＂加密方案
　　KeyGen:输入1^n，随机选择两个n比特的素数p,q,N=pq，∅(N)=(p-1)(q-1)，选择满足gcd(e,∅(N))=1的e，计算d=e^(-1) mod∅(N)，输出公钥pk=(N,e)，私钥sk=(N,d).
　　＂教科书式ElGamal＂加密方案
　　KeyGen：输入1^n,执行多项式时间算法输出一个循环群G，其阶为q(其中‖q‖=n)，生成元为g。然后选择随机的x←Z_q并且计算h≔g^x。公钥是(G,q,g,h)，私钥是(G,q,g,x)。
　　上述两个算法加解密的正确性能够简单地验证。在分析它们的安全性之前，我们必须明确攻击场景。根据敌手的能力，主要有以下几种攻击类型：
　　（1）唯密文攻击（Ciphertext-only attack），这是最基本的攻击方式，表示敌手只能观察到密文，并且试图确定相应的明文；
　　（2）已知明文攻击（Known-plaintext attack），这里敌手学习一个或者多个使用相同密钥加密的明密文对，目标是确定其它密文对应的明文；
　　（3）选择明文攻击（Chosen-plaintext attack，CPA），这种攻击中，敌手能够选择明文，并得到相应的密文,试图确定其它密文对应的明文；
　　（4）选择密文攻击（Chosen-ciphertext attack，CCA），这最后一种攻击类型是指敌手甚至可以选择密文并得到相应的明文，目标依然是确定其他密文的明文。
　　前两种攻击类型是被动的，符合实际场景的，唯密文攻击在实践中最容易实现，敌手唯一要做的就是窃听传输密文的公共信道；而已知明文攻击符合实际是因为不是所有加密的消息都是保密的，至少不是无限期的保密，举个例子，通信开始是双方可能通常加密＂hello＂消息，又或者加密可用来保证某机密直到公开的那一天，任何窃听并获得密文的人，将在后来获得相应的明文。
　　相对而言，后两种攻击类型是主动的，敌手能够适应性地有选择地请求加密和解密，这是否代表了一个真正值得关注的现实的敌对威胁？针对选择明文攻击（CPA），有个二战时期的军事历史说明了这一点。
　　在1942年的5月，美国海军的密码专家截获了一份通信消息，该消息中包含了一份密文字段＂AF＂,他们相信这对应着明文＂中途岛＂，认为日军正计划对中途岛发动攻击，然而华盛顿的指挥者并不相信，通常认为中途岛不可能成为攻击的目标。于是海军密码专家命令在中途岛的美军军队发送一个明文消息，说他们的淡水供给不足。日军截获了该消息，立刻报告给其上级＂AF＂淡水不足。于是确信＂AF＂的确就是中途岛，美军迅速派三架运输机抵达该位置，结局就是中途岛被解救了，日军受到了重创，这里海军密码专家就完成了一次经典的选择明文攻击。
　　至于选择密文攻击(CCA)，我们可以设想一个用户和他们的银行通信的场景，其中所有的通信都是经过加密的。如果该通信没有被认证，则敌手能够代表用户发送特定密文,银行将解密这些密文,敌手可能能够从结果中掌握某些信息。此外，加密经常在高级别的协议中使用；比如，一个加密方案可能被作为认证协议的一部分来使用，其中一方发送一份密文给对方，对方解密返回结果。在这种情况下，一个诚实方可能正好扮演了一个解密预言机的角色，所以该方案必须是CCA安全的。
　　公式详解＂教科书式RSA加密＂方案
　　明显可以看出＂教科书式RSA加密＂方案是确定性加密，因此不是CPA安全的。尽管＂教科书式ElGamal加密＂在判定Diffie-Hellman（DDH）假设下被严格证明是CPA安全的，却容易受到选择密文攻击。选择密文攻击（CCA）安全的一个密切的相关问题就是密文的可延展性，直观上来解释，即一个加密方案拥有这样一个属性:给定未知消息m的密文c，可以得到未知消息m_1的密文c_1，其中m和m_1具有某种已知的关联。＂教科书式RSA＂加密就容易出现上面的攻击,比方说敌手观察到使用公钥〈N,e〉加密的密文c=m^e mod N，则有密文c_1=2^e c mod N，解密为2m mod N，因为〖c_1〗^d≡〖(2^e m^e )〗^d≡2^ed m^ed≡2m mod N。对于＂教科书式ElGamal加密＂，比如说敌手A拦截了使用公钥pk=(G,q,g,h)加密消息m的密文c=〈c_1,c_2〉，这意味着c_1=g^y,c_2=h^y∙m。一些随机选择的y←Z_q对敌手来说是未知的，但敌手可以计算〖c_2〗^/=c_2∙m^/,则很容易知道密文c^/=〈c_1,〖c_2〗^/〉是消息m∙m^/的密文，这个观察结果就容易引起选择密文攻击。有人可能会反对:如果接收者收到两个密文c、c^/,并且密文的前一个元素相同，将产生怀疑（确实，对于正常生成的密文，密文的第一个元素相同的概率是可忽略的）。然而，敌手很容易避免其发生，令c_1,c_2,m,m^/如上面所述，敌手可以选择随机的y^/←Z_q，并且设〖c_1〗^((2))=c_1∙g^(y^/ ),〖c_2〗^((2))=c_2∙h^(y^/ )∙m^/，容易验证c^((2))=〈〖c_1〗^((2)),〖c_2〗^((2))〉是消息m∙m^/的密文，且密文的第一个元素是完全随机的。
　　依据上述分析，＂教科书式RSA加密＂形式简单高效，但是不满足密码的安全要求。事实上，RSA实验室公钥加密标准PKCS#1v1.5版本，利用了填充加密的原理，对于一个常见形式的公钥pk=〈N,e〉,令k为N的字节长度，即k是一个满足2^8(k-1)≤N<2^8k的整数，假设要加密的消息m是一个8比特长的倍数，并且长度最长可以达到k-11字节，现加密一个D字节的消息计算如下：(00000000‖00000010‖├r┤‖├00000000┤‖m)^e mod N，其中r是随机生成的(k-D-3)字节的字符串，这些字节均不为0（该条件使得消息在解密的时候没有歧义）。注意到m的最大允许长度能保证r的长度至少为8个字节，这样对于所有随机填充的r值的蛮力搜素是不可行的（复杂度≥2^64）。
　　尽管至今还没有基于RSA假设的证明，PKCS#1v1.5仍然被认为是CPA安全的，但是对该方案的选择密文攻击已被证实。因为标准中的填充部分是以特别的方式完成（且不由任意比特组成），如果密文没有正确的格式，将会返回一个错误消息，这些错误消息的存在足以发起选择密文攻击：给定一个正确生成的密文c，攻击者可以恢复出明文m，方法是通过提交多个密文并且观察哪个密文能成功解密，哪个会产生错误。由于这类信息可以来源于当接收到不正确格式的消息时，发出错误消息的服务器，因此在实践中是可行的。
　　也就是说，基于RSA假设的高效且CCA安全的方案还不存在。密码学家们为了提高现有方案的效率，提出新的假设，并且探索使用现有的假设，能够达到的最高效率上界。在实际中获得很大成功的一种方法，是在＂完全严格的安全性证明＂和＂没有证明＂之间提供一个＂中间地带＂。该方法就是在证明密码学方案的安全性中，引入了一个理想模型，最流行的例子就是随机预言机（Random Oracle，RO）模型。
　　依此，密码学家们构造了随机预言机模型下的CCA安全的RSA加密，进一步，为了消除最初版本方案中密文比Z_N^*中的单个元素要长（即使是加密一个短消息时）的缺陷，结合最优非对称填充（OAEP）技术，构造了RSA-OAEP加密方案，修订了之前的PKCS#1v1.5标准。尽管旧版本由于兼容性仍然被广泛使用，但现在新的实现系统应该倾向于这个更新后的版本。
　　相对来说，＂教科书式ElGamal＂加密方案不仅有效并且能够基于DDH假设证明是安全的，却没有在实践中得到广泛采用，或许因为有限域上存在亚指数算法求解离散对数问题。而工程实现ElGamal式加密时,出于安全和效率的考虑，现在广泛使用ECC，至于实现的标准可以参考商用密码算法标准-SM2椭圆曲线公钥密码算法或者美国国家标准与技术研究所（National Institute of Standards and Technology，NIST）颁布的ECC标准。
　　抗量子计算机攻击的公钥密码方案提上日程？
　　前面介绍了网络时代为了保护被传输数据的机密性（Confidentiality）而广泛使用的公钥加密体制，它们的安全性或者基于大整数分解问题的困难性，或者基于离散对数问题的困难性。然而，1994年美国数学家Peter Shor在量子计算模型下提出一个算法使得解决以上数学困难问题成为可能。Shor算法在量子计算机上可以在多项式时间内解决大整数分解与离散对数问题。这意味着，一旦量子计算机或者针对大整数分解问题或者离散对数问题的专用量子计算机被制造出来，将会完全破解基于这些困难问题的公钥加密算法。二零一七年三月三日，谷歌量子AI实验室三名科学家Mohseni、Read和Neven在《自然》杂志上宣称＂量子计算机五年内将实现商用化＂。虽然文章同时指出，真正的量子计算机所需要的技术还需要十年左右的时间才能完成，但这已经使得传统的公钥密码系统的安全性存在巨大的风险。因此，迫切需要设计下一代的抗量子计算机攻击的公钥密码方案。
　　对于某些问题，经研究表明量子算法相对于传统算法并没有明显的优势。目前，主要的抗量子计算机攻击的公钥密码方案的候选有基于格的、基于编码的、基于哈希函数的、基于多变量的密码系统等。其中，格上的若干困难问题，如最短向量问题（Shortest Vector Problem，SVP）、独立最短向量问题（Shortest Independent Vector Problem，SIVP）等，还没有发现能够在多项式时间内解决的量子算法，因此被认为其可以抵抗量子计算攻击。
　　另一方面，格上的困难问题之间存在平均情形困难性（Average-case Hardness）与最差情形困难性(Worst-case Hardness)之间的归约关系(简单来说，Worst-case Hardness属于计算复杂性理论范畴，密码方案直接使用的密码学原语(cryptographic Primitive)我们希望是Average-case Hardness)，且在格上的数学运算主要是矩阵向量乘法，计算简单高效，可并行实现。此外，相比于基于编码、哈希函数、多变量等其他的抗量子计算攻击的公钥方案，以格为基础的数学结构，不仅可以构造加密方案，也可以构造签名方案、密钥协商方案。这意味着，基于格的公钥系统可以部署多个公钥密码方案模块，有利于整个公钥密码系统在通信网络系统上的功能整合。综合上述诸多优势，基于格的加密方案已经成为抗量子计算攻击的最有希望的候选算法之一。
　　目前，已有的基于格的加密方案主要分为两大类，一类是NTRU密码系统，其方案的实现效率较高，但缺乏可证明安全性。另一类是基于格上平均情形下的困难问题如带误差学习问题（Learning with Errors, LWE）,环上带误差学习问题（Ring Learning with Errors, RLWE）等的加密方案，也是基于格的加密体制的一个热门研究领域。基于平均情形下困难问题的主要加密方案包括基于一般格的最早的Regev加密方案、对偶Regev（dual-Regev）加密方案以及基于理想格的RLWE的加密方案等。在这里，我们就不深入介绍了。
　　截止2017年11月30日，NIST已经完成了第一轮后量子密码（Post-Quantum Cryptography，PQC）（也被称为是抗量子的或量子安全的密码）算法的征集。到目前为止，23个PKE/KEM的格密码提案，有3个方案（Compact-LWE，HILA5，Odd Mantattan）已经被攻破，4个方案被攻击候已提出解决办法，还有2个方案存在其它问题；5个Signature的格签名提案的Comments较少，目前没有被攻破。
　　正如NIST所说：＂后量子标准化的发展过程不应该被视为竞争，某些情况下，也许不可能作出一个候选方案优于另一个方案的具有良好支撑的判断。相反，NIST将以公开和透明的方式对提交的算法进行深入全面的分析，并鼓励密码团队共同进行分析和评估。这种结合的分析方式将影响NIST对后量子标准化的后续发展的决策。
　　NIST预计将进行多轮评估，为期3至5年，而且由于目前科学对于量子计算能力的认知还远远不够全面，这个评估过程将比SHA-3和AES的评选更为复杂。此外，一些候选后量子密码系统可能有完全不同的设计属性和数学基础，不同类型之间的候选算法的比较将是困难甚至不可能的。虽然距离大规模地应用量子计算机还有一段路要走，但由于从传统公钥密码体制到后量子密码的过渡不太可能是一个简单的＂drop in＂，开发、规范和部署新的后量子密码系统将需要付出极大的努力。因此，应当及早地进行这个过渡。＂
　　现在到未来几年时间，正是后量子密码标准化的黄金阶段，感兴趣的研究人员应当抓住这个机遇，踊跃地参与其中！