VPN | MD5、SHA、SM3 认证算法原理
一次性进群，长期免费索取教程，没有付费教程。
教程列表见微信公众号底部菜单
进微信群回复公众号：微信群；QQ群：460500587
微信公众号：计算机与网络安全
ID：Computer-network
一、MD5认证算法原理
MD5（Message-Digest Algorithm 5，信息摘要算法第5版）是计算机广泛使用的散列算法（也称“哈希算法”或“杂凑算法”）之一，采用带密钥的运算时，可同时用于消息完整性检测和消息源身份认证。它是由MD2、MD3和MD4版本一路发展而来，是Ronald Rivest 于1991年设计发布的，用于取代MD4。
1、MD5算法基本认证原理
尽管不同版本的MD算法的具体原理肯定有所区别，但它们的基本工作机制却是一样的：都是先在发送端将一个随机长度的消息（在带密钥运算的情况下，除包括原始消息外，还要同时包括双方共知的密钥）最终“压缩”（当然，这里并不是简单的压缩，需要经过一系列的各种逻辑运算，以打乱原始消息的次序，生成的是一段看不懂的密文）成一个128位的消息摘要（也称哈希值），并随着原始消息一起发送。
原始消息，连同摘要消息一起到了接收端后，再采用相同的方法对所接收到的原始消息（在带密钥运算的情况下，还要包括双方共知的密钥）进行“压缩”，看生成的消息摘要是否与随着原始消息一起发送过来的消息摘要一致，一致则认为所接收的消息是完整的，在传输途中没有被非法篡改。
因为在带密钥的MD5消息摘要的运算中，不是直接基于原始消息进行计算的，还要与机密的预共享密钥（采用预共享密钥认证方法时），或者本端的公钥（采用数字证书认证方法时）结合起来计算的，而预共享密钥和本端公钥只有发送者和接收者才知道的，所以能保证摘要计算的机密性，产生独一无二的“数字指纹”，起到了消息源身份认证的目的。
MD5摘要运算是不可逆的（即具有单向性，也称之为“单向密钥”），不可通过摘要消息还原出原始的消息。当然，其实所有身份认证算法都是这样的，仅用于认证，不需要在接收端进行数据还原。也正因为如此，MD5算法通常不认为是一种加密算法，不具有解密能力。
MD5算法的消息完整性验证和消息源身份认证的基本过程可用图1来描述。图中的“MAC”就是指摘要消息。MD5算法的总体消息摘要运算过程如下：
图1 MAC类算法基本工作原理示意
（1）把包括密钥和初始消息在内的二进制比特串（假设称之为“原始消息”），以及位于最后位置、新增的用于记录要原始消息（包括密钥和初始消息）的二进制64位长度一起被划分成一个个的512位（16个32位字长）的块；
虽然理论来说MD5算法可以计算的消息长度是任意的，即不受限制的，但是由于用于表示消息长度的二进制位只有64位，所以实际上它也最多只能计算264位的消息。如果消息长度超过这个值，则只会对低264位的消息进行计算。
（2）这些512位的块再经过多轮“与”（And）、“或”（OR）、“非”（NOT）、“异或”（AOR）逻辑算法（具体算法我们可以不做了解）处理，最终会输出四个32位分组，将这四个32位分组级联后将生成一个128位散列值（消息摘要）。
2、MD5算法消息填充原理
上面介绍的只是理想情况下的基本运算原理，其实这里涉及到一个非常重要的“填充”操作，因为大多原始数消息，加上用于表示原始消息长度的64位后可能仍不能恰好被512整除，也就是原始消息的二进制位数除以512后的余数不是488（512−64=448）。这时就表明需要对原始消息进行填充处理了。这里又有两种情况：一是余数小于448，另一种就是余数大于448。
如果原始消息二进制位数除以512后的余数小于448，则先在原始消息的最后一个512位块的最后填充一个1，然后再填充若干位0，使得该块的原始消息总长度等于448位，然后加上用于标识原始消息长度的64位，正好形成一个512位的块。
如一个有600位的消息，则可划分成两个512位的块：第一个块是512位全部为原始消息；第二个块中有88位原始消息，然后进行填充：先在最后填充1位“1”，再填充359位“0”，使得88位原始信息+1位1+359位0=448位，最后再附上64位用于标识原始信息长度（600）的值。
如果如果原始消息二进制位数除以512后的余数大于448，这时要新增一个512位的块了。首先是在原始消息的最后一个512位块的最后填充一个1，然后再填充若干位0，使得该块的原始消息总长度等于512位；接着再新增一个块，前面448位均填充0，再加上用于标识原始消息长度的64位，形成新的一个512位块。
如有一个1000位的消息，则最终会划分成三个512位的块：第一个块是512位全部为原始消息；第二个块中有488位原始消息，然后进行填充：先在最后填充1位“1”，再填充23位“0”，使得488位原始信息+1位1+23位0=512位；最后是一个新增的块，也要进行填充：先在前面填充448位0，最后再附上64位用于标识原始信息长度（1000）的值。
3、MD5算法的主要应用
MD5除了应用于各种三层VPN通信的数据完整性验证和消息源身份认证外，在我们在日常IT应用中也常见到它的身影，也经常用于数字签名。
如我们常常在某些软件下载站点的某软件信息中看到其MD5值，它的作用就是用于在我们下载该软件后对下载回来的文件用专门的软件（如Windows MD5 Check等）做一次MD5校验，以确保我们获得的文件与该站点提供的文件为同一文件。利用MD5算法来进行文件校验的方案被大量应用到软件下载站、论坛数据库、系统文件安全等方面。
另外，MD5还广泛用于操作系统的登陆验证上，如UNIX、各类BSD系统登录密码、数字签名等诸多方。如在UNIX系统中用户的密码是以MD5（或其他类似的算法）经Hash运算后存储在文件系统中。当用户登录的时候，系统把用户输入的密码进行MD5 Hash运算，然后再去和保存在文件系统中的MD5值进行比较，进而确定输入的密码是否正确。通过这样的步骤，系统在并不知道用户密码的明码的情况下就可以确定用户登录系统的合法性。避免用户的密码被具有系统管理员权限的用户知道。
二、SHA认证算法原理
SHA（Secure Hash Algorithm，安全哈希算法）主要适用于数字签名，也是一种不可逆的MAC算法，但比MD5算法更加安全。目前它有三种主要的版本，即SHA-0、SHA-1、SHA-2和SHA-3。其中SHA-2和SHA-3版本中又有多种不同子分类，如在SHA-2中又根据它们最终所生成的摘要消息长度的不同又包括SHA-224、SHA-256、SHA-384和SHA-512等几种。
1、SHA算法基本认证原理
整个SHA算法的认证原理与前面介绍的MD5算法认证原理极为相似，同样先把原始消息划分成固定长度的块，最后加上用于标识原始消息长度的位（不同SHA版本中用于标识原始消息长度的位数不一样），再结合共享密钥（可以是共同设置的预共享密钥，也可以是对端公钥），利用一系列的逻辑算法生成固定长度的消息摘，用于在接收端进行消息完整性验证和消息源身份认证。
在各种版本SHA算法中（因为SHA-3的算法与其他SHA版本的算法有较大不同，故在此不作介绍），进行散列运算时所涉及的一些参数特性不完全相同，具体如表1所示。从上表可以看出，SHA-0、SHA-1算法与MD5类似，都是把输入原始消息的二进制串划分成512位的块，最后一块的最后64位用于表示原始消息的长度，不足512位时也要进行填充。
表1 主要MAC算法的基本参数特性比较
2、SHA算法消息填充原理
SHA算法中在进行消息分块时也可能要进行填充。其填充的方法与MD5算法一样，也是先加1位“1”，然后填充若干位“0”。如SHA-0和SHA-1最后会把划分和填充后的消息与共享密钥进行80轮的逻辑运算处理，得到一个160位的摘要消息。但SHA-0和SHA-1仍然容易出现碰撞（即有可能多个不同消息运算后得到相同的摘要），所以目前主要是采用SHA-2版本。
下面仅以SHA-512（也有写成SHA2-256的）为例介绍其基本的摘要运算过程。其他SHA版本的基本摘要算法类似。
（1）把包括密钥和初始消息在内的二进制比特串（假设称之为“原始消息”，小于2128），以及在最后新增一个用于记录原始消息二进制长度的128位一起被划分成一个个1024位（32个32位字长）的块；
当采用SHA-512进行运算时，如果原始消息长度大于等于2128时，只取前面2128−1位进行摘要运算。
（2）同样再对以上划分的1024位的块经过系列“与”（And）、“或”（OR）、“非”（NOT）、“异或”（AOR）逻辑算法（具体算法我们可以不做了解）处理后，输出8个64位分组，将这8个64位分组级联后将生成一个512位散列值（消息摘要）。
这里同样涉及“填充”操作，因为大多数原始消息（包括密钥和初始消息），加上128位后可能仍不能恰好被1024整除，也就是原始消息的二进制位数除以1024后的余数不是896（1024-128=896），这时就表明需要对原始信息进行填充处理了。但这里同样有两种情况：一种是余数小于896，另一种就是余数大于896。
如果原始消息二进制位数除以1024后的余数小于896，则先在原始消息的最后一个1024位块的最后填充一个1，然后再填充若干位0，使得该块的原始消息总长度等于896位，然后加上用于标识原始消息长度的128位，正好形成一个1024位的块。
如一个有1500位的消息，则可划分成两个1024位的块：第一个块是1024位全部为原始消息；第二个块中有476位原始消息，然后进行填充：先在最后填充1位“1”，再填充419位“0”，使得476位原始信息+1位，1+419位，0=896位，最后再附上128位用于标识原始信息长度（1500）的值。
如果如果原始消息二进制位数除以1024后的余数大于896，这时要新增一个1024位的块了。首先是在原始消息的最后一个1024位块的最后填充一个1，然后再填充若干位0，使得该块的原始消息总长度等于1024位；接着再新增一个块，前面896位均填充0，再加上用于标识原始消息长度的128位，形成新的一个1024位块。
如有一个1924位的消息，则最终会划分成三个1024位的块：第一个块是1024位全部为原始消息；第二个块中有900位原始消息，然后进行填充：先在最后填充1位“1”，再填充123位“0”，使得900位原始信息+1位，1+123位，0=1024位；最后是一个新增的块，也要进行填充：先在前面填充896位0，最后再附上128位用于标识原始信息长度（1924）的值。
三、SM3认证算法原理
SM3密码杂凑算法是中国国家密码管理局于2010年公布的中国商用密码杂凑算法标准（其实也是哈希算法，或者单向散列算法）。该算法由王小云等人设计，消息分组为512位，经过填充和迭代压缩，生成256位的杂凑值。总体来说，SM3算法的压缩函数与SHA-256的压缩函数具有相似结构，但SM3密码杂凑算法的设计更加复杂。下面简单介绍SM3密码杂凑算法的消息填充和迭代压缩原理。
1、SM3算法消息填充原理
在SM3密码杂凑算法的消息填充方面，原始消息（包括密钥和初始消息）长度（l）也是要小于264位的，填充的方法其实与MD5一样，也是先在原始消息的最后加一位“1”，再添加k个“0”，最终要使l+1+k除以512后的余数为448，取其最小的非负整数。然后用一个64位的比特串标识原始消息的长度l。填充后的消息M正好是512位的倍数。
下面举一个不带密钥的SM3杂凑算法消息填充的示例来帮助大家理解。如一个原始消息（本示例不带密钥，“原始消息”也即前面的“初始消息”）为：01010101111010 1111010100001，一共27位，即l=24。
先在原始的最后加一位“1”，这时一共就有28位了；
再用448−28，得到还需要在再后面添加420位的“0”；
再在最后用64位来表示原始消息长度“27”，得到用于标识原始消息长度的64位值为：000......00（前面一共有59位“0”）11011。
整个填充过程如图2所示。填充后整个用于杂凑运算的消息512位。
图2 SM3密码杂凑算法的填充示例
2、SM3算法消息迭代压缩原理
迭代压缩是SM3杂凑算法的关键，但这里的原理比较复杂，作为网络管理和维护的人员可不深入了解。
迭代压缩的基本原理如下：
首先将第一个512位的消息块利用对应的压缩函数，压缩成某一固定长度的比特串；
然后再将第一个512位消息块压缩后的固定长度比特串（具体长度与整个消息所划分的512位块多少有关），以及第二个512位消息块一起再利用压缩函数，又压缩成某一固定长度的比特串；
然后再将这个比特串再将作为第三个512位消息块压缩运算的输入，连同第三个512位消息块一起利用压缩函数，再压缩成某一固定长度的比特串，以此类推；
直到最后一个512位消息也被压缩成同样固定长度的比特串。最后再将所有这些512位消息块压缩后的固定长度比特串依次串联起来就是最终的杂凑值了。
微信公众号：计算机与网络安全
ID：Computer-network