最近和朋友沟通，发现密码学虽然是程序开发中经常用到的知识，但是能恰当地用密码学的知识达到预期的效果，却还是有很多常见的误区。这里我根据自己的一些学习和体会，写成博客，姑且为作业供大家评述。如果有错误，请大家指正。

本文允许分享，但请注明来源网址。

区分“编码”和“加密”

最简单的错误是，希望通过ASCII移位、字母替换（如替换为十六进制表示）或者Base64“加密”保护信息。的确，这样的确可以让原来的信息变成一塌糊涂，但是原有信息并没有消失，比如字母e出现的概率。只要掌握足够多的信息，我相信破译这样的编码应该很容易。

对于ASCII移位，可能可以说移位长度就是密钥，但是这样的密钥只有8比特，256种可能，对于现在的电脑，枚举就可以了。改变字母表，或者使用维吉尼亚密码，虽然是比较好的改进，但是破译也不难，方法在二战结束之前就已经找到了。

区分密码和密钥

我们登录计算机时，需要输入密码。如果输入错误或者不知道，就无法登录。但是计算机里面的文件数据仍然在那里，只是操作系统此时不愿意给你服务，让你访问它们。这里，密码起到的作用是访问控制，但是并没有让信息变成不可轻易读出的样子。好比一个保险箱，我们可以把他锁起来，但是只要保险箱被砸烂，里面的文件还是可以拿起来就看的。

密钥不是这样的。密钥的作用是提供给一个加密算法，算法根据密钥进行一系列运算，将输入的信息打乱。如果没有密钥，即使公开了算法，也应该很难推出输入的信息是什么。这才是加密的意义。实际上，密码学的第一定律就是，攻击者永远知道你采用了什么算法，或者说，只有密钥的保密才是真的保密。

当然，在一些情况下，密码可以被用作密钥，但是可能不太安全。在对称加密中，安全的密钥长度需要至少128比特（16字节）。

区分散列与加密

众所周知的MD5算法是散列函数的代表之一。散列函数的作用是，给定任意长度的输入，给出一个固定长度的输出。输出应该能在很大的几率，但显然不是100%的几率，代表输入信息。之所以不是100%，是因为输出和输入之间是多对一映射的关系。也因此，决不可以说散列是加密。散列函数是单向的，多对一的关系让我们不能找到唯一解。

良好的散列应该能区分输入信息的不同。最好是输入信息的微小变化就可以导致输出完全不同，或者说产生相同输出的概率非常非常小。常见的散列函数，可以说对于绝大多数用途都做到了这一点。

举个例子，比如我们需要从网上的服务器下载一个光盘映像。映像有600MB，我们希望知道下载得到的映像和服务器的一致，或者，知道在传输中有错误以便纠正。如果我们一个字节一个字节地和服务器核对，那么这个代价是很大的：又产生了600MB的上传流量。简单的方法是，服务器和我分别产生一个映像文件的散列值（散列函数对文件这个输入的输出）。比较散列值相同，就可以在一定概率上确认文件是一致的。

对称加密 vs 不对称加密

对称加密非常常见，就是加密和解密需要同样的密钥的一类算法。不对称加密需要两个密钥，一个公开，一个私有（保密）。公开的密钥可以用来给别人加密信息，我们保存私钥，那么唯独我们才能解密发给我们的信息。公钥是不能解密由公钥和相应不对称算法加密了的信息的。

这两种算法各有优缺点，所以需要配合使用，扬长避短。对称加密的速度快，安全性高，但是作为通讯，要求加密者和解密者有共同的密钥。在通过不安全的信道（比如存在监听）沟通时，这种分配密钥的方法很困难。不对称加密允许（在一定前提下）安全地通过不安全的信道发送信息。但是不对称加密速度一般比对称加密慢，效率也较低。所以一般的做法是，用不对称加密在信道上分配一个临时密钥，然后用对称加密进行普通的数据传送。

数字签名：不对称加密的另一个重要应用

通过前面的技术，无论是对称加密，还是不对称加密，我们粗略的可以保证信息在传输过程中的机密性了。即，可以阻挡非预期的第三者（监听者，比如）看到我们的信息了。但是我们没法保证一个问题，即，确信我们的信息来自某个人，假设此人为Bob。因为如果使用不对称加密，那么能使用公钥给我们发送加密信息的实际上是任何人都可以。这样就必须避免冒充。如果使用对称密钥，我们也许可能简单的假设，能给我们发送信息的人就是Bob，但是还有另一种情况，使得我们不能容忍Bob否认他向我们说过什么。比如我们是银行职员，我们必须确认，声称是Bob的转帐指令的信息的确是Bob说的，而且我们还有必要记下这个指令，以免Bob日后否认这一转帐的事实。

这些需求促进了密码学的一个重要应用：数字签名的诞生。数字签名，如同签名的意义，是为了达成如下目的：

1. 让任何人都可以相信，他们看到的信息，就是签名者当初要发出的信息。
2. 假如签名之后，原来的信息被篡改，那么通过签名的检验任何人都可以发觉这样的事实。
3. 对于一段信息的签名，只能用于这段信息，直接搬走用于签署别的信息是不行的。这其实是（2）的推论。
4. 签名者在做出签名后，不能否认信息是他发送的。或者说，如果我们看到了某人对他的信息的签署，就可以确信某人的确签署过。而签署就意味着承认他，而非伪造者，确实发出过这样的信息。

数字签名是这样利用非对称加密技术的：首先，针对要被签署的信息，进行散列，得到一个散列值。其次，签名者用自己的私钥加密这个散列值，然后随同信息一起发布。因为利益原因，签名者是不太可能自己公布私钥的，那么私钥就只有签名者自己有了，所以一个通过验证的签名，只有签名者自己才可能发出（当然这还需要算法的保证）。

由于签名者已经事先公开了他的公钥，所以任何人都可以看到验证他的签名。方法就是，先对声称是被这个签名所签署的信息进行散列，然后用公钥解密签名。如果散列值等于解密后的内容，那么验证就通过了。

有了数字签名，我们就可以解决前面的银行问题。客户事先产生自己的私钥，然后把公钥交给银行。客户如果签署了转帐命令，银行就差不多可以相信是客户，而非冒充者，发出了命令了。而且客户是无法在银行收到信息后否认他发出过这个指令的。

对称加密：一些说明

对称加密是什么前面讲过了。现代密码学的对称加密，一般是基于块操作的。块是指一定长度的数据，比如128比特。密钥输入给算法后，块的内容就会被设计好的复杂算法进行各种变换。这种变换有时被称为伪随机变换，可见其深度。

仙农提出过这种加密变换的要求：confusion和diffusion。首先，变换必须能消除原来的消息中的某些语法上的特点，比如字母的频率分布（有些字母是常见的，有些不常见，对于各种语言都有这种特点）。此外，对输入的每个部分的变换，都要尽可能多地影响密文的全部，可以简单的想象，输入的一个字母被替换，则密文要产生尽量多的变化。

现代的优秀对称加密算法，适当的使用，是可以做到以上几点的。但是还有要说明的地方。刚才说对称加密是基于块操作的，那么当数据量大于一个块的时候，就有要注意的地方：

补全数据

一个叫法是padding。将数据补成块大小的整数倍。而且还要能在解密的时候找回原来的数据。有几种思路可以举例：比如在数据前面用一个已知长度的整数，记录补全时消耗了的字符长度；PKCS标准的方法是先计算需要补全的字符数——而鉴于块的大小一般是128，192或者256，都小于等于ASCII码表的长度，补充的字符也就正是这个需要的数量在ASCII码表中的代表字符。比如需要补充47个字符才能凑整，那么就补充47个“/”（“/”在ASCII码表里面位于47号）。

块间关系

对于一个块来说，仙农的diffusion要求是做到了。但是我们如果简单地把各个块的密文堆积起来发布出去，还是存在问题的。以银行为例，假设转帐命令的格式是：[128比特的命令代号][金额]，那么这是在128比特的块加密中，需要两个块，且金额在后一个块中。如果一个人曾经发出过转帐1元和转帐100元的两条命令，那么完全有可能攻击者直接替换第二个块上的密文，达到修改命令的目的（数字签名？这是另一回事，先不谈）。这就需要妥善处理块间关系，有很多模式可供选择，下面简单介绍几种。

• ECB模式。 这是最简单的模式，就是将各个块的密文堆积起来。因此不能避免上面的调换攻击。

• CBC模式。 这种模式，首先需要在密文前面添加一个随机内容的块（第零块），放置在最终输出的第一位置上。然后第一个密文块和第零块进行异或，放在最终输出的第二位置上。第二个密文块和第一个密文块异或的结果再次异或，放在第三位置上……如此等等。解密的时候，先逆序恢复出各个块的内容，然后解密。 如果传输中有一个密文块发生丢失或者破坏，则不能恢复全部密文。这就避免了前述攻击，鉴于多数时候明文能否看懂是一下子就知道的。 第零块，叫初始向量（IV），是必须和密文一起提供的。

• CFB模式。 这个也需要一个IV。但是有趣的是，加密是首先加密一次初始向量，得到中间第一块。然后再次加密中间第一块，得到第二块。如此迭代，直到中间块的长度不少于明文长度了。然后将明文逐个和中间流进行异或操作，得到输出结果。这样做是很有好处的：如果每次给出的IV都不同，调换攻击也是不行的。而且密文里面坏了一个比特，解密后受到影响的也只是一个比特。而且，这里面中间流是不依赖明文而存在的，也就是说可以事先利用系统的空余时间计算好，然后很快地产生密文。这种算法很适合网络电视、网络电话等需要发送连续数据流的地方。另外，存在一些方法，可以让数据丢失也不至于影响全部解密过程，参考这里（英文）。

散列函数，salt，HMAC

散列函数的一个不错的应用是保护登录密码。现在一些论坛已经这样做了。具体来说，是用户在注册时输入密码后，论坛并不直接储存，而是先进行散列，储存散列值。MD5是经典的用于此类操作的算法，然而因为一般的密码的长度都少于散列值的长度，而且散列函数也是固定的，不难用一些方法根据散列值反查。严格讲这不叫破解，叫碰撞，即找到一个输入，和给定散列值相等，但（数学上）不能保证这个输入就是当时的用户的输入。

对于MD5，如果直接用于散列密码，那么对于用生日或者其他的长度只有十位字符以内的密码，已经都能通过反查“字典”的方法找出碰撞了。对于在此范围之外的散列值，找出一个碰撞也是不太困难的了。

最简单的避免这类问题的方法，是使用更摩登一点的算法，比如SHA1，SHA512，WHIRLPOOL，RIPEMD-160等。但是造出它们的字典，也不过是时间和投资的问题。

还有一种方法，是储存密码的时候，进行salt。salt是一个字符串，可以是预先设定的论坛常数，也可以是随着账户而储存的一个值。在散列的时候，将salt和密码拼在一起送给函数。然而，没有任何证据说，salt长就更安全，或者salt+密码+salt比salt+密码的拼接方式更安全。因为散列并不能明显保证这一点。

我个人建议，与其使用散列+salt，不如使用HMAC。HMAC是一个算法，利用它，可以在散列值前，额外附加一个密钥。对于同样的信息，使用不同的密钥，得到的散列结果不同。对于同样的信息和同样的密钥，得到相同结果。HMAC是将一个普通散列函数“改造”成需要密钥输入的方法，并不依赖具体是哪个散列函数。HMAC一般用来认证消息是由具有密钥的人发出的方法，但是比数字签名稍弱，并无抗抵赖性——并非储存论坛密码之用。我也的确没法证明HMAC就能比salt方法更加安全。这里希望读者指出。

至此，已经解释了现代密码学的常见概念了。作为工程应用，列出一些常见的算法名称，供选择：

• 对称加密
  • DES(=Data Encryption Standard)，上个世纪70年代的产物，密钥长度56比特，不算长，除非为了向后兼容，应当避免使用。DES-3（三重DES）是一个给那些暂时无法升级为更好密码标准的DES系统的弥补方案，但也应当避免。
  • IDEA(=International Data Encryption Algorithm)，为了替代DES而设计的。
  • Rijndael，美国政府当前的加密标准（AES=Advanced Encryption Standard）的胜出者（86比10票）。经过了公开的征集和甄选，安全性可靠。
  • Serpent，AES落选者（59比7票），速度慢，但是认为比Rijndael还安全些。
  • Twofish，MARS，RC6，都是AES落选者，但也都是5个第一轮胜出者的成员（另外2个是Rijndael和Serpent）。安全性我不了解。
  • Blowfish，安全性不知，尚没有发现弱点（也可能是缺乏研究）。在软件上应用比较广泛。
  • TEA(=Tiny Encryption Algorithm)，XTEA，XXTEA，不是基于块加密的算法，安全性中等（要有足够的迭代次数），适合单片机等使用。
  • SM4，分组128比特，密钥128比特的对称加密算法，来自中国国家密码管理局。
• 非对称加密、数字签名算法
  • RSA，老牌的非对称加密算法，基于质数积分解困难的特性。安全性和密钥比特数相关，一般认为需要超过1024比特才能勉强，4096比特可以撑到2040年代。不适合加密长信息，既因为速度慢，也因为这样会导致安全性下降。
  • DSA(=Digital Signature Algorithm)，数字签名算法，不能用来加密。
  • ElGamal，可以用来加密。和DSA一样，基于另一个假设（CDH假设）。我不甚了解具体的数学原理。
  • EC(=Elliptic Curve)，椭圆曲线加密，速度比以上三种快相当多，安全性也认为不错（同样长度的密钥安全性超出RSA很多）。ECDH和ECDSA使得可以用来进行数字签名和加密信息两种用途。
  • SM2，基于椭圆曲线的算法，由中国国家密码管理局推出。应用范围我不了解。
• 散列函数
  • CRC32，输出32比特，用于要求很低的完整性校验（如RAR文件），适用于单片机实现。也有输出16比特的CRC16和输出64比特的CRC64。
  • ADLER32，类似上面的。
  • MD5，即将淘汰的通用散列函数，安全性比较凑合，不建议在新产品中使用。速度很快。
  • SHA(=Secure Hash Algorithm)1，输出160比特。安全性强于MD5，但也不建议在新产品中使用。但是SHA1一个应用是在版本1的hashcash中。hashcash技术本文没有介绍，请查阅相关网站。
  • SHA256，SHA512，安全性很高的散列函数，与SHA1一样，是美国国家安全局（NSA）推出的。
  • Whirlpool，输出位数和SHA512一样长，认为安全性也很高。
  • RIPEMD-160，输出位数160比特，可以考虑替代SHA1。
  • HAVAL，输出128,160,192,224,256比特均可，我没用过。
  • SM3，输出256比特的散列函数，中国国家密码管理局推出。

下面以即时通信为例，介绍一下典型应用中密码学的用法。这些是我的建议而已，可能不是最好的解决方案。

即时通信有多种模式。对于存在服务器的模式，可以在服务器上管理对称密钥数据库。用户甚至不需要明确的登录过程就可以发送给服务器信息——方法是，将信息用约定的对称密钥加密，用HMAC（密钥当然是客户的密钥）处理密文。将密文、HMAC散列值和用户ID发给服务器即可。服务器用客户的密钥先检验密文的HMAC散列值，如果结果与收到的一致，再花精力解密密文，转发给接收者。在接收之前，服务器可以先用接收者的密钥加密发送者的明文。

需要注意的一个地方：任何人截获前述数据参数，还可以再发给服务器一次或多次信息，造成一个人说了几次一样的话的感觉。这称为重放攻击（Re-play Attack）。避免的方法是加入标志，用时间+有效期就可以解决。当然，有效期也要在HMAC保护下。

但是这样做是有一定风险的。首先，是服务器的可信问题。服务器是能看到客户通信的。其次，是服务器一旦被入侵，就会带来严重的安全问题。

服务器和用户之间约定密钥的方法，例如通过注册或者修改密码，可以通过SSL协议保护。SSL协议是对称加密和不对称加密结合，保护http通信安全的有效方法。服务器的可信性由被世界承认的有信誉的公司确认，但是服务器一般可能不确认客户的身份。在https访问中，客户需要验证服务器的证书确实由这些公司签署了（实际上，客户之所以能如此相信，还在于相信他们所用的浏览器以及浏览器里面装载的这些公司的签署用的公钥证书——根证书——也是真实的），然后可以保证客户和服务器之间的通信安全。在此前提下，服务器和用户约定密钥倒是没什么问题，当然，需要事先验证用户的身份——提供旧的密钥，或者注册时的机密问题。

为了避免服务器的风险，无论使用，或者不使用服务器，建立通信双方之间的不对称加密和数字签名保护关系是很重要的。这样我们可以做到信息的完整、保密、可信性，甚至利用OTR方法做到可信抵赖性。

这样做，如何进行普通聊天、群聊天，还请读者思考。