密码学——对称加密&加密模式

加密机制，分为对称加密跟非对称加密，前者也叫做私钥加密，后者也叫做公钥加密。这篇文章单独来谈谈对称加密，可能有些地方说的不好或者不对，还望朋友们指正，共同探讨共同学习。

        对称加密中，根据对明文的处理方式，又可以分为流加密（Stream Cipher）跟块加密（Block Cipher）

        流加密，简单来说就是根据密钥产生一串跟明文长度一样的数据流，然后xor一下，速度快。可能有的人觉得流加密不够安全，也不尽然，只不过在使用流加密的时候需要格外的小心，一点小小的疏漏就可能导致很严重的安全问题。

        块机密，就是针对一个固定大小的数据块进行加密，常见的有des, 3des, aes，blowfish等等。

        这里就不依依详细介绍了，拿前3个用的比较多的说说，大家有兴趣可以自己去研究研究。关于他们具体的思想实现原理，也不在本文的讨论范围之内，这些东西网上一查有很多，而且讲的都很详细，这里只说说一些需要注意的东西或者不太好查的东西

DES：

        

        des一个块的大小是64bits，密钥是56bits，块的大小及密钥的长度都不能满足现在的安全需求了，抛开块大小及密钥长度不谈，des也有几个与生俱来的weakness。

• weak keys：des每一个回合的key（这里叫做round key）都是由加密key（这里叫做cipher key）里的一些bit位组合成的，如果cipher key全是0的话，所有的round key都一样，加密跟解密的过程也都一样了，除了全是0这样的weak key还存在其他的weak key

• complementation property（取反属性/补属性）：E(^K, ^P) == ^E(K,P)
  

        会不会有点太吹毛求疵了，第一个缺点可以避免，第二个即使避免不了，但是似乎也没什么太大的影响，但是这不是一个理想的块加密该有的属性，在密码学安全里容不得一点小小的瑕疵，所谓道高一尺魔高一丈，你永远想不到黑客们会采用什么样的攻击手段，这不是一个安全漏洞但也是一个安全隐患，所以实际的开发中尽量不要用des。

3DES：

        为了挽救des，毕竟他也是曾将的王者，出现了3des，也就是三重des，块的长度没变依旧是64bits，密钥扩展到56*2bits，56*3bits,虽然密钥长度变长了，加强了一定的安全性，但是块的大小没变，而且依旧存在des那几个与生俱来的weakness。这里补充一下块的大小对安全性的影响，类似md5,sha-1等哈希算法，位数过少的话导致的一个问题就是碰撞，对于哈希算法来说，产生碰撞了基本可以说这个算法已经走到尽头了，对于块加密来说，两个不同的明文块对应的密文块相同，这也是一个不小的安全隐患。如果块的大小有n bits，从密码学的角度讲，他可提供的安全性只有n/2 bits（这里涉及到生日攻击，有兴趣的朋友可以去研究研究）。

AES：

        aes一个块的大小是128bits，64位的安全性在目前来说足够了，密钥长度有128bits，192bits，256bits，一般情况下，在加密算法是安全的情况下，密钥越长可提供的安全性越高。但是aes有点除外，已经有研究显示存在针对aes-192跟aes-256的攻击了，但是这些攻击对aes-128似乎不起作用，当然只是理论上的，现实中还是可以放心大胆的用滴

        这里需要明确一下概念，像des跟aes这种块加密，严格的说并不是一个具体的加密算法。他们只是一个“内核”，他们的功能多了去了，不仅仅可以用来构造加密算法，还可以构造hash，mac，甚至伪随机数发生器。

        拿aes来说，如果照着教科书写了一个aes的实现，那么这个实现的功能仅仅是用来加密一个128bits的块。如果是一个100bits或者256bits的数据呢，他就无能为力了。对于前者，比较简单，填充一下，同时也引入了一个概念，填充模式。对于后者就需要先对明文进行分块，每块128bits，不够的话填充一下，然后对每一块进行加密。多个块怎么加密，这就是加密模式这个概念，加密模式通俗的说就是定义了一个规则，按照这个规则有组织有条理的来处理各个块。

        从简单入手，先看看有哪些填充模式，这是java下Bouncy Castle Provider提供的一些填充模式

• NoPadding. No Padding
• PKCS7Padding (PKCS5Padding). Padding mechanism defined in PKCS #5 and PKCS #7
• ISO10126-2Padding. Padding mechanism defined in ISO 10126-2
• ISO7816-4Padding. Padding mechanism defined in ISO 7816-4
• TBCPadding. Trailing Bit Complement padding
• X9.23Padding. Padding mechanism defined in X9.23
• ZeroBytePadding. Padding with zero bytes (not recommended)
  

        这些模式也都很简单，下图是PKCS7Padding，图片浅显易懂，胜我千言万语。有兴趣的朋友可以查一查其他的，一看就明白，甚至你不需要知道他们是什么，也完全不影响使用

        加密模式也有很多很多种，比较常见的有ECB,CBC,OFB,CTR等等

ECB:

        电子密码本模式（electronic codebook），简单的说就是对每一块分别加密然后简单的组合到一块

        C[i]=E(K,P[i]) for i=1,…,n;

        这是最简单的一种模式，但也是最不推荐的一种模式，因为他是不安全的，在这种模式下，如果明文块是相同的，输出的密文块也是相同的，这信息泄露的可不是一点半点，收集信息属于被动攻击的范畴，what's worse, ECB这种模式可以主动攻击，选择明文攻击（CPA-chosen plaintext attack）。实际应用中选择加密算法至少要是CPA安全的。

        选择明文攻击，赋予敌手一定的能力（或者权限），这个能力不是太高，敌手可以选择任意的明文m，提交给一个（中文译作预言机），Oracle可以返回加密后的密文c，示意图如下：


        如果第一次接触到这个概念，可能不太好理解，就像我第一接触到的时候，心中一大堆疑问，Oracle到底是个什么东西，现实中存在这样的Oracle可以让敌手随意的查询吗？便于理解还是举个活生生的例子。

        1942年，二次世界大战，美国海军情报局截获了日本一条军事情报（当时日本的主要通信加密系统为JN-25，而美国已经联合英国荷兰开始解读JN-25加密系统，并且取得了巨大突破），情报显示“AF”（密文中的某个片段，并未解读出）将会是下一个攻击目标，密码专家认为AF对应的是“Midway”（中途岛），但是美国当局认为日本不可能攻打中途岛。为了证实这一点，密码专家想出了一个方法，要求中途岛海军基地的司令官以无线电向珍珠港求救，说“中途岛上面临缺水的危机”。不久后，美国海军情报局便截夺到一则JN-25信息，内容果然提到了‘AF’出现缺水问题。结果‘AF’便证实为中途岛，也就是日本海军的下一个攻击目标。 

        这个例子里，日本军方便充当了这样一个Oracle的角色，虽然不是自愿的，但是敌手总可以通过各种方式获得这样一个Oracle

        与之对应的是另一种攻击方式，选择密文攻击，这种方式赋予敌手更高更强的能力，除了获得一个加密Oracle，还可以获得一个解密的Oracle，可以向解密Oracle递交任意的密文C（除了你想要破译的那个密文），Oracle返回解密后的明文m。

        如果你获得了一段密文C1，想要知道它是什么内容，但是你不能直接向Oracle查询这个C1，如果可以这样敌手就无敌了，敌手可以做的是根据密文C1，构造出另一段密文C2，然后查询C2，获得对应的明文m2，然后通过m2来推测m1可能包含的信息

        这个现实中的例子还真不好举，我试着说一个，加入说某公司的某经理正在跟秘密另一个公司做某种网上交易，你身为一个商业间谍，想知道做的是什么交易，所以你在监听公司的网络，数据包都被你截获了，但是加密的你破译不了，所以你就索性把密文中的一个bit位给取反了，但是凑巧的是，解密后的明文并不是乱码，只是交易数额由100w，变成了300w，这时候交易双反都奇怪了，然后开始打电话确认咋回事，“喂，黄总，我们刚才xxxxxxx”而正好你在经理的办公室装了监听器，偷听了她的谈话内容。。。

        这个只是我自己举的一个例子哈，现实中都会有hash，mac，或者数字签名什么的验证消息的完整性真实性不可抵赖性。类似的例子，比如访问web服务器时候，通过构造消息，服务器会给予相应的反馈，即使返回的是错误码，也可以从错误信息当中推测出一个有用的信息。

CBC：

        cipher block chaining，用的最广泛的一种加密模式

        C[i]=E(K, p[i] xor C[i-1]) for i=1,…,n;

        每一个明文块在加密之前都与前一个密文块异或一下，这样就有效的解决了ECB模式所暴露出来的问题，即使两个明文块相同，加密后得到的密文块也不相同。这里还有一个问题，C[1],C[2]…C[n]分别对应明文块的P[1],P[2]…P[n]。还有个C[0]是什么？C[0]其实就是经常看到的或者可能看到过的IV(initialization vector)。这个在写代码的时候IV是需要你提供的参数，不是系统或者算法自动产生的。不要小看这个IV，如果他的值设定的不好，一样会暴漏出安全问题。

关于IV的值的设定，有以下几种方案：

• 固定的IV：加密方跟解密方事先商量好一个IV，加解密的所有消息就用这个固定的IV，优点：简单。缺点：很多时候，消息的第一个块都一样（比如说一些协议头），这样加密出来的密文的第一个块也一样，虽然只有第一块一样，但是也有可能暴漏出一些信息
  

• Counter IV：第一条消息IV=0，第二条IV=1，以此类推。缺点：0跟1只有一个bit位之差，一个bit的差别也可能暴漏出一些信息
  

• Random IV：每次都随机生成一个IV，每一个消息的IV都是随机的，这个IV的长度正好是一个块的长度。优点：克服了上面的缺点。缺点：得让解密方知道这个IV才行啊，如果不知道这个IV是解密不了第一个密文块的，所以得把这个IV附加到密文里，这样密文就比明文多了一个块。如果要通过网络传送大量的短消息，会增加通信复杂度
  

• Nonce-Generated IV:这个的原理有点类似于random IV，只不过是先产生一个nonce（number used once），nonce这个东西接触过网络安全协议的人可能并不陌生，在通信双方建立连接的时候通常都会产生nonce来验证一些信息，在发送消息的时候也会附带nonce来表示一个消息的序列号防止重放攻击等等，nonce的值是唯一的而且只能used once。这里也是先产生一个nonce，然后（用你正在使用的加密算法跟密钥）加密这个nonce，用这个密文来做IV。跟raundom IV不一样的是不把这个IV发给解密方，而是把这个nonce发给解密方，因为IV的长度是一个块的长度，如128bits，但是nonce可能是一个int类型，只有32bits，减少了通信复杂度

接着回到加密模式，

OFB：

        output feedback，输出反馈模式，这种加密模式不再是加密明文块，如果流加密一样，产生一个伪随机（pseudorandom）流，将明文与伪随机流异或一下即是密文

K[0]=IV
K[i]=E(K,K[i-1]) for i=1…n;
C[i]=P[i] xor K[i]

OFB模式有两个优点：

• 不需要填充（padding）了
• 加密过程跟解密过程完全一样，一个算法完成加解密

缺点也是有的：

• 这里的IV跟之前的IV是同一个概念，这里的IV要求必须是Random IV或者nonce IV，如果每次加密IV都是固定的，根据上面的式子每次产生的k1,k2,…kn都是一样的,那问题可就严重了，我不说你也懂的

• 如果不够幸运的话，可能会产生碰撞，产生碰撞之后就会周期性的循环，例如：k0=iv,如果你非常不幸运，在产生k10的时候碰撞了，k10==k0，最后你会发现产生的k序列就在一直的这样以周期为10循环。

CTR：

        Counter，计数器模式，跟OFB模式类似，也是流模式，只不过为了克服OFB可能存在的碰撞攻击，定义入下：

K[i] = E(K,Nonce || i)

C[i] = P[i] xor K[i]

        一定要记住Nonce的定义，number used once，加密两个消息千万不要用同一个nonce。||表示连接符，Nonce||i构成一个块的大小，优点同OFB模式，需要注意的是Nonce的选择一定要唯一。

        到此为止，才算是一个真正意义上的加密算法，所有的块加密，可以跟任意的加密模式结合，跟任意的填充模式结合，所以，如果算上填充模式的话，如果有10种块加密，10种加密模式，10种填充模式，那其实就有1000种加密算法。

选择哪种填充模式？

        据我所知，选择哪种填充模式，对块加密来说好像没什么区别，但是对非对称加密来说直接关系到他的安全性，当然上面提到的填充模式仅适用于块加密，对非对称加密，如RSA，有专门的填充模式。（在教科书上看到的RSA，产生两个大素数p,q 计算n=pq等等等等，那只是阐述他的原理，textbook RSA，教科书式RSA）。

选择哪种块加密？

        推荐aes-128,128bits的块大小跟128bits的密钥在目前来说安全性足够了

选择哪种加密模式？

        CBC with Random IV 跟 CTR 这两种模式的安全性比较高，但是使用CTR需要额外的注意nonce的使用，CBC模式如果IV选择的不好，只能泄露一个块的信息，而CTR如果nonce选择的不好，整条消息都泄露了，而且在某些情况下由于某些条件的限制，很难产生nonce，所以还是选择CBC with Random IV更好一点

关于信息泄露

        没有一种加密模式是完美的，即使块加密是完美的，理想的，加密模式也可能会造成一定的信息泄露，如CBC with Random IV
        假设密文块 C[i] == C[j] ，在CBC这种模式下，并不意味着P[i] == P[j]，乍一看，好像也没泄露什么信息，但是…

C[i] == C[j] ==>
E(K, P[i] xor C[i-1]) == E(K, P[j] xor C[j-1]) ==>
P[i] xor C[i-1] == P[j] xor C[j-1] ==>
P[i] xor P[j] == C[i-1] xor C[j-1]

        如果P[i]这个明文块已经知道了，是不是P[j]就因此而泄露了