密码疑云 (1)——加密与签名

佚名 5年前 (2019-03-14) 算法 1045人围观抢沙发百度已收录

　　希尔顿·丘比特的先生拿着一张稀奇古怪的纸条找到福尔摩斯，上面画着一行跳舞的小人：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

　　他的妻子看到这些小人就会非常惊恐，而且这些奇怪的小人文字会经常出现在他家的窗台上和工具房的门上，他对此感到相当困扰，因此想求福尔摩斯帮忙解开这个谜团。

　　福尔摩斯拿着这些画着小人的纸条仔细观察，发现这些小人只有有限的几种，而且某些小人出现的频率远比其他小人更高，于是福尔摩斯得出一个结论——每一个跳舞的小人代表一个英文字母。在接连收到一些纸条后，福尔摩斯终于推测出了跳舞的小人所对应的字母，最后一组小人隐藏了一个穷凶极恶的威胁：“ELSIE，PREPARE TO MEET GOD(埃尔希，准备去见上帝）”。可惜福尔摩斯仍然晚了一步，当他赶到希尔顿家时，希尔顿先生和他的妻子已经遭遇了不幸。后来，福尔摩斯用同样的小人向凶手写了一封信，最终捉到了凶手。

　　福尔摩斯是根据英文字母的使用频率推测出答案的，英文中最常见的字母是E，把出现最多的一种小人看作E，由此进一步猜测其它单词（幸好是英文）。在今天看来，这种简单的方法已经起不到保密作用，它们都可以用统计的方法较为容易地破解，真正能够服务于大众的加密还需要经过数学法则的驱动。

从战争到民用

古老的密码

　　或许少年时代在某一时刻，我们都曾经希望自己的一些信息成为秘密，于是不约而同地想到了一种加密方法——把拼音文字向后偏移。例如，当偏移量是3的时候，所有的字母A将被替换成D，B变成E，以此类推。这确实是一种加密技术，而且是在密码学中最广为人知的替换加密的技术——明文中的所有字母都在字母表上向前或向后按照一个固定数目进行偏移后被替换成密文。这个加密方法是以罗马共和时期恺撒的名字命名的，被称为该撒密码。当年恺撒曾用此方法与将军们进行联系。

　　凯撒密码的缺点是加密算法太过简单，最多在字母表上移动26次就可以轻松破解，知不知道文字偏移根本无所谓。在悬疑大师肯·福莱特的《无尽世界》中，梅尔辛和凯瑞斯就曾经用凯撒密码加密自己的信件并且沾沾自喜，最后被修道院的院长发现，轻松破解。

军事密码

　　在战火纷飞的年代，信息决定着战争的成败，为了保护信息不被敌方获取而产生的加密方式更显的至关重要，“阴符”便是最早的军事密码，据《六韬·龙韬》所载，3000年前由姜尚（公元前1128年—公元前1015年）发明。

　　相传武王伐纣期间，有一次，姜子牙和商军作战，情况危急需要援兵，姜太公令信使突围，通知武王派兵。他担心机密被敌人截获，又怕武王不认识信使，产生犹豫耽误军机，就把自己当年“太公钓鱼”的鱼竿折成长短不一的数节，令信使仔细保管。信使突围回到西岐后，武王令侍卫将几节鱼竿合在一起，辨认出是姜子牙的心爱之物，于是赶快率大军支援，解了姜太公之危。战事结束后，姜子牙对着那几节鱼竿冥思许久，最终和武王一起发明了独有的专用凭证，这就是“阴符”。

　　太公的阴符一共有八种：“大胜克敌之符，长一尺；破军杀将之符，长九寸；降城得邑之符，长八寸；却敌报远之符，长七寸；警众坚守之符，长六寸；请粮益兵之符，长五寸。败军亡将之符，长四寸；失利亡士之符，长三寸。”

　　这种加密程度确实比凯撒密码高级多了，确实是“敌虽圣智，莫之能识”；相应地，阴符的缺点也很明显，那就是能够传递的信息相当有限。

　　在谍战片中，地下党的情报员们收到的指示是一连串的4位数字，通常这些数字是某本畅销书（大多数时候是《三国演义》，外国是《圣经》）的页码和文字索引，情报员们翻书查找每一个字，阅读后迅速销毁。这些畅销书就是解开密文时必须持有密钥，面对一大堆杂乱无章的数字，敌军往往无从下手——试想，一个最常用的“的”字可以出现在一本书的每一页上出现多次，因此也就可以用无数的数字编码，没有密钥又如何知道含义呢？

　　真实的二战中，加密的方式更是千奇百怪，纳粹分子将摩尔斯码与五线谱、国际象棋棋谱和图书上的符号结合的天衣无缝；甚至时装模特的设计图纸也能被设计成一条条密码。

电子时代的密码

　　时间迈入了电子时代，计算机刚一出现就用被用来破解密码，一大批密码被计算机判处死刑，密码也因此飞速升级。随着因特网的发展，网络安全也日趋严重，大量在网络中存储和传输的数据都需要保护。然而不幸的是，应用层中最主要的HTTP协议是无状态的，且没有任何加密机制，这就意味着计算机网络天生就是不安全的，需要一种有效的加密机制来为用户提供通信的保密性。加密机制也是许多其他安全机制的基础，比如最典型的登录口令，取款时的输入密码。

　　网络是公用的，一个服务器可以同时对多个终端提供服务，每个终端与服务器间的通信都想要对其它终端保密；而作为服务的提供者，服务器并不接受终端的编程，这就意味着用户没办法自己定制密码规则，于是，依赖于数学原理的更复杂的密码机制产生了。

被窃听和被冒充

　　网络上处处存在坏蛋，也许是单纯地出于炫耀，也许是为了达到非法的目的，他们会想尽办法窃听他人的通信：

　　有时候，发送的信息对于截获者来说并不容易理解，但坏蛋们仍然可以通过分析正在传输的报文的长度和传输频度来了解数据的某种性质，从而知道正在通信的终端的位置和身份。这种攻击行为属于被动攻击。

　　被动攻击并不涉及数据的任何改变，只是偷窥，只要把门关上就可以有效预防，比如使用虚拟专网VPN。另一类坏蛋就可恶了，他们会改变、删除一个合法消息的某些部分，从而欺骗服务器，得到一个未授权的结果：

　　为了保护自己信息安全，人们设计了多重防线，而数据加密就是防线中相当重要的一环，相应的密码体制也应运而生。

密码体制

　　信息论的创始人克劳德·香农在1949年发表了《保密系统的通信理论》，将密码学放置在坚实的数学基础之上，标志着密码学作为一门科学的形成。随着计算机技术的发展，密码的研究更加突飞猛进。20世纪70年代后期，美国联邦政府颁布数据加密标准DES（Data Encryption Standard）和公钥密码体制的出现，成为近代密码学的两个重要里程碑。

对称加密

　　人们常用Alice和Bob的故事来解释解密模型，一般的加密模型是这样：

　　Alice向Bob发送一条明文X，询问“今天是星期几？”。为了数据的保密性，Alice使用加密密钥K通过E运算对X进行加密运算，从而得到了密文Y：

　　密文在网络中传输，过程中可能出现坏蛋Mallory，但是他没有密钥，因此无法知道Alice的询问到底是什么。当Bob收到密文Y后，并不理解是什么含义，所以必须用密钥K对Y通过D运算进行解密，还原出明文X：

注： E和D是一种函数运算，输入数据，得出结果，并不关心输入是什么，因此也可以直接对明文进行D运算，从而得到另一种形式的密文。

　　模型中完成加密和解密的算法就是常说的密码体制，由于使用了相同的加密密钥与解密密钥，所以称为对称密钥密码体制，简称对称加密。谍战片中的加密几乎都是这种体制，通讯双方使用同一本畅销书。

　　作为公开的加密体制，对称加密体制存在一个数据加密标准，它就是IBM研制的DES，1977年被美国定为联邦信息标准，后来又被ISO作为数据加密标准。

　　DES在加密时先对明文进行分组，每一组是64位的二进制数据，然后再使用一个64位的密钥对每一组数据加密，得到相应的64位密文，最后再把所有密文串联起来：

　　在DES标准中，加密算法是公开的，数据的保密性完全取决于密钥，密钥共有64位，其中又有8位用于奇偶校验，这意味着一共有2⁵⁶种密钥。如果使用蛮力搜索密钥，那么找到密钥的平均时间复杂度是O(2²⁸)。尽管这是个指数级别的复杂度，但是相对于破解密码后产生的价值而言，O(2²⁸)并没有复杂到不可接受，今天的普通台式机可以在数小时内破解。

　　后来出现了用来代替DES的国际加密算法IDEA（International Data Encryption Algorithm），它使用128位密钥，因此远比DES安全。

　　无论是哪种密码体制，密钥都是解开一切的关键，密钥的保管也因此成为重中之重。对称加密中双方都使用相同的密钥，但怎样才能做到这一点呢？一种方法是事先约定，Alice和Bob约定好使用相同的密钥K，如果有一天Alice或Bob觉得密钥不安全，则他们需要共同更换一个新的密钥K₁。但是Alice还有其他朋友Merry和Kerry，现在持有密钥的人数就变成了4个，于是问题来了，随着人数的增多，不但密钥的管理会变得越来越困难，密钥的安全性也变得越来越差——一个秘密如果被100个人知道，早晚也会被1000个人知道。

　　还有一种方法是通过密钥分配中心KDC（Key Distribution Center）管理。KDC是一种运行在物理安全服务器上的服务，作为发起方和接收方共同信任的第三方，维护着领域中所有安全主体账户信息数据。KDC知道属于每个账户的名称和密钥，Alice和Bob的会话密钥就是由KDC分发的。KDC虽好，却无形中增加了网络成本，于是，在人们强烈的需求下，公钥密码体制诞生了。

非对称加密

　　公钥密码体制的概念有斯塔福大学在1976年提出的，由于使用了不同的加密密钥与解密密钥，所以也称为非对称加密。

　　在非对称加密中，公钥 PK（加密密钥，public key）、加密算法、解密算法是向公众开放的，私钥 SK（解密密钥、秘钥，secret key）是需要保密的。非对称加密的加密过程：

　　Bob通过密钥生成器生成了一对密钥，用于加密的公钥PK_B和用于解密的密钥SK_B。Bob把SK_B小心保管起来，然后向公众开放了PK_B，Alice也收到了一份。如果Alice想和Bob通讯，就需要用Bob的公钥PK_B对发送的明文X进行加密，从而得到密文Y：

　　Bob收到密文后，需要对其解密，还原出明文X：

　　公钥是用来加密的，不能用来解密，这意味着：

　　公开密钥与私有密钥是一对，如果用Bob的公钥对数据进行加密，只有用Bob的私钥才能解密；如果用Bob私钥对数据进行加密，那么同样只有Bob的公钥才能解密。如果Bob主动向Alice发送讯息，那么Bob需要用自己的私钥对数据进行加密，而Alice可以用公钥对数据解密：

　　这个过程以为意味着：

　　联合①可以更清楚地看到公钥与私钥的关系：

　　当然， Bob的两把密钥存在一定的关联性，否则Bob也无法对Alice的密文进行解密。同时，非对称加密的开销也远大于对称加密。

　　一个问题是，Bob的信息极有可能被同样持有公钥PK_B的Mallory截获并翻译成明文，为了实现秘密通讯还需要做出改进，这需要Alice的配合：

　　Bob向Alice发送信息时除了使用自己的私钥加密外，还需要另外使用Alice的公钥再进行一次加密：

　　这样一来，必须持有Alice的私钥才能撕开第一道防线，Mallory手里的Bob公钥也就失去了意义。Alice需要两次解密才能看到明文：

　　由此可见，非对称加密的开销远大于对称加密，这也是公钥密码体制并没有完全取代对称密码体制的重要原因。

数字签名

　　秦汉时期，出于对官方的通信保密的需要，封泥被大量使用。一份文件就是一捆竹简，官员要将竹简捆好，再用自己的专有印章在竹简的封口处盖上封泥，之后在火上烤，使之干燥。在对方收到文件时，封泥完好，表示信件没有被私拆过，封泥破损，意味着信息可能泄露。

　　随着纸张的流行，封泥退出了历史舞台，取而代之的亲笔签名。作为验证真实性依据，签名一直被沿用至今，信用卡办理需要签名，买房贷款需要签名，燃气开通需要签名，就连小学生的听写作业也要家长签名。

　　纸质文件可以签名验证真实性，计算机上的数字信息的真实性能否用类似的机制验证呢？当然可以，这就是数字签名。

　　当Bob向Alice发送信息时，数字签名需要实现三种功能：

　　1. Bob的签名是独一无二的，Alice能够核实Bob对信息的签名，以便确信信息确实是Bob发送的；

　　2. Alice能够通过Bob的签名确信信息没有被Mallory篡改过；

　　3. Bob事后不能对自己的签名抵赖。

　　数字签名的实现方法有多种，由于非对称加密实现起来更为容易，所以大多数数字签名都是基于非对称加密的。

　　签名的过程如下：

　　Bob用自己的私钥SK_B对自己发送的信息进行D运算，由于Bob的私钥只有他自己持有，因此密文Y上的签名是独一无二的。Alice收到带有Bob签名的密文后，用Bob的公钥进行解密，如果是被篡改过，那么无法还原出有效的明文。如果Bob赖账，不承认自己曾经发送给Alice任何信息，Alice就可以拿出用公钥还原出的明文给进行公证的第三方看：

　　看看，明文是用你的公钥还原的，还有什么可抵赖的？

　　任何人都可以核对签名，但无法伪造，签名的任何一位发生了变化都会使签名失去效力。对于电子票据票据和需要认证的电子信息来说，数字签名是一种理想的工具。

数字证书

　　Bob的签名需要用Bob的公钥来核实，问题是Mallory可以伪造公钥，此时Alice核实签名就无从谈起，她永远都验证不了签名的合法性。为了保证Alices收到的确实是Bob的公钥，数字证书就派上的用场。

　　Bob的证书会包含Bob的公钥和他的一些相关信息，在经过证书的签名后（用证书的私钥加密），形成了一个“公章”，这个公章就是数字证书。“公章”盖在Bob的数字签之后，

　　Alice通过“公章”的公钥识别出Bob的信息和公钥，确认文件确实是Bob发送的，然后对文件解密。问题是Mallory 太烈害了，他连“公章”都可以伪造，又如何确保这个公章是真的？如此下去，就会陷入无限循环。为了解决这个问题，需要一个能够确保证书公钥合法性并且能够对证书签名的第三方机构，这个机构就是CA认证机构（Certification Authority）。

　　现在，Alice用CA的公钥解开数字证书，就可以拿到Bob真实的公钥，再用Bob的公钥核实数字签名是否真的是Bob的。

　　我们常用的网银Usb Key就是数字证书的硬件载体，是由银行指定的CA认证机构颁发的属于我们自己的“公章”，此外还存有自己的私钥。Usb Key相当于大门的钥匙，如果钥匙丢了，需要及时通知银行，以便对之前的证书进行作废。

　　作者：我是8位的

　　出处：http://www.cnblogs.com/bigmonkey

　　本文以学习、研究和分享为主，如需转载，请联系本人，标明作者和出处，非商业用途！

　　扫描二维码关注公众号“我是8位的”