【botan源码阅读】MD5源码解析

❝

忽如一夜春风来，千树万树梨花开。—【唐】岑参

❞

这是源码分析的第一篇文章，我们先来看个比较简单的，从我们比较熟悉的哈希函数来入手，因为本身哈希函数的构造，不考虑证明的话，所涉及的额外的知识还是相对比较少的，我们来先看下虽然已经不太安全，但是目前来看用的人还不少的MD5在botan当中的实现吧，友情提示，作为第一篇文章将会比较长，希望读者不要反感，后面的同结构的哈希函数只介绍压缩函数的哪一部分应该就会比较短了。

❝

源码位置:src/lib/hash/md5/md5.cpp

❞

我们自底向上来看这个源码，首先来看一下 Buffered_Computation这个类的具体的方法

Buffered_Computation

❝

源码位置:src/lib/base/buf_comp.hThis class represents any kind of computation which uses an internal state, such as hash functions or MACs

❞

这个类实际上是具有内部状态的算法的一个统一类，上面引述一下官方的描述，总感觉我自己翻译出来的东西不得劲，还是官方的看起来舒服，尝试用通俗的语言来解释一下这个类的作用，要想理解，可能需要各位读者回顾一下有关哈希函数以及mac函数的相关知识了，其中我们知道对于这一类函数的计算在中间都维护了一个状态数组，然后每次操作都会去更新这个中间数组，最终的输出也是根据这个中间数组来的，因此呢在 botan源码当中就给抽象了这么一个类出来，这个类来统一的描述这种具有中间状态的密码学函数。

接下来呢，我们分类来看下 Buffered_Computation的相关函数，我个人感觉可以分成5组，纯属我个人的看法，如果讲的不对，也欢迎读者和我交流。

output_length()

这个函数的作用比较单一，其实就记录了一下最终输出的一个结果的长度，我们知道无论是哈希函数还是MAC最终的输出长度都是一个固定的值。

update系列

这里其实包含了一堆函数，其实主要作用呢就是来更新消息内容，这个为了保持接口的通用性这里重载了一系列的函数，让调用者可以比较轻松的传入各种类型的入参。

final系列

这一系列函数呢，实际上是用来输出最终的计算之后的结果，其中根据返回值的不同区分出来的几个不同的函数，用于使调用者可以方便的去按照自己的想法来去拿到返回值。

process系列

这个函数呢，实际上是上面两个函数的一个组合，然后可以直接处理拿到结果。

私有函数系列

至于为什么私有函数都放到一块呢，是因为私有函数其实对于外部调用关系是不大的，而且这两个私有函数的核心作用也都在内部的数据处理上，因为这个类是一个抽象层级比较高的类，因此呢，大部分的实现都是下放到了具体是算法当中，所以说这俩私有函数具体的实现也会在他的子类当中来做。

有关于Buffered_Computation的这个类，个人感觉能聊的东西貌似真的不多，主要原因其实有两点，第一个是这个类的抽象层级算是比较高的，因此里面主要是给下面的子类提供一个高层的抽象方法，其次呢，就是这个类的代码是真的也不多，然后呢，我们接着往上看。

HashFunction

❝

源码位置: src/lib/hash/hash.hThis class represents hash function (message digest) objects

❞

这个类，可以说是整个哈希函数的鼻祖了，在 botan当中所有的哈希函数都是他的一个子类，然后呢有关于这个类，个人感觉可以分成三部分来看

基本信息

class BOTAN_PUBLIC_API(2,0) HashFunction : public Buffered_Computation
   {
   public:
   // ...
   virtual std::string name() const = 0;
   virtual size_t hash_block_size() const { return 0; }
   // ...
}

这两个函数呢，其中一个描述了算法的名字，另一个呢描述了分块的大小

处理相关

class BOTAN_PUBLIC_API(2,0) HashFunction : public Buffered_Computation
   {
   public:
   // ...
   virtual void clear() = 0;
   // ...
}

这部分呢，内容也比较单一，这个是为了重新reset哈希函数的内部状态的一个函数，可以将哈希函数的内部状态重置回初始的状态。

框架相关

class BOTAN_PUBLIC_API(2,0) HashFunction : public Buffered_Computation
   {
   public:
   // ...
   static std::unique_ptr<HashFunction>
      create(const std::string& algo_spec,
             const std::string& provider = "");
   static std::unique_ptr<HashFunction>
      create_or_throw(const std::string& algo_spec,
                      const std::string& provider = "");
   static std::vector<std::string> providers(const std::string& algo_spec);
   virtual std::string provider() const { return "base"; }
   virtual std::unique_ptr<HashFunction> copy_state() const = 0;
   virtual std::unique_ptr<HashFunction> new_object() const = 0;
   HashFunction* clone() const
      {
      return this->new_object().release();
      }
   // ...
}

其他所有的部分都归属于这一块了，这一块的具体作用在本文当中不会过多展开来聊，等着哈希函数相关的库都介绍的差不多了之后再回过头来聊这一块的代码，在这里简单提一下，这一部分的主要作用呢就是可以让我们快速的去初始化一个哈希函数实例，并且提供快速切换的一个方案，通过一段例子来看。

#include <iostream>
#include "../lib/hash/hash.h"
#include "../lib/base/symkey.h"

int main(int argc, char *argv[]) {
    auto hash = Botan::HashFunction::create("MD5");
    auto result = hash->process("");
    std::cout<< Botan::OctetString(result).to_string() << std::endl;
    return 0;
}

我们可以通过字符串直接创建一个哈希函数，如果后面比如说我们不想用MD5这个函数了，我们只需要将里面的那一个字符串MD5给换成其他的哈希算法就可以了，其他的不需要懂，剩余框架相关的这个函数就是用来处理这方面内容的，因此呢，这块和本文的关系是不大的，等将哈希函数给一块介绍完成之后呢，在回来看这一部分的设计问题也不大。

MDx_HashFunction

❝

源码位置: src/lib/hash/mdx_hash/mdx_hash.hBase class for Merkle-Damgård hashes

❞

我们接着向上来看，就来到了这一个类，在我之前的文章当中讲过，对于MD5、SHA1、SHA2等一系列哈希函数都是遵从于Merkle Damgård结构的，因此呢，在这里又多加了一层，针对于这一类结构的哈希函数的一个相关的类，到这个类里面，我们就需要来看一下每个函数的一个具体的实现了。这个可以简单的分为两组，第一组呢是公开函数，第二组呢是非公开函数，我们先看看一下有关于内部的一些变量。

内部变量

class MDx_HashFunction : public HashFunction
   {
   // ...
   private:
      const uint8_t m_pad_char; // 这个是用于padding的字符，这里其实存在两种情况，第一种是我们按照大端序来的话，那么这个值就是0x80, 如果是小端序来的话那，这个值就是0x01了.
      const uint8_t m_counter_size; // 这个是最终保存的消息的长度所占用的字节大小，注意这个的单位是字节，并且这个至少要是8个字节，因为对于哈希函数来说，目前最少的用到的这个长度就是8个字节，这个值如果不传默认是8，也有更大的，比如sha384或者sha512这个的值会是16.
      const uint8_t m_block_bits; // 这个是每个分块的大小，这个的范围是[4, 17) 这个实际上是取对数的分块长度，对于MD5来说这个值是log2(64)，对于其他的哈希函数就根据需要来了.
      const bool m_count_big_endian; // 这个表示是我们记录消息的长度是按照大端还是小端来.

      uint64_t m_count; // 这个值保存了消息的长度，这个保存的是字节的长度，不过通过分析这块代码我发现一些问题，目前我是没想明白，因为这个长度是可能存在保存不开的情况的，但是看到这里面也没给处理，不知道是不是我这理解错了，还是其他的原因，这一块有一点迷，大概率是我的功力不够导致的，如果有读者搞明白了这块，也欢迎和我交流，或者等我再修炼修炼，想明白之后再来填我这个坑。
      secure_vector<uint8_t> m_buffer; // 这是一个缓冲区，是针对每一个分块进行处理的一个buffer.
      size_t m_position; // 这个记录了消息处理的位置，是为了适配update来使用的.
   };

}

我给上面的变量作用加了一个注释，直接看注释应该就可以看明白了，就不在文章当中花费额外的篇幅来再写一遍了。

内部函数

class MDx_HashFunction : public HashFunction
   {
   // ...
   protected:
      void add_data(const uint8_t input[], size_t length) override final;
      void final_result(uint8_t output[]) override final;

      /**
      * Run the hash's compression function over a set of blocks
      * @param blocks the input
      * @param block_n the number of blocks
      */
      virtual void compress_n(const uint8_t blocks[], size_t block_n) = 0;

      void clear() override;

      /**
      * Copy the output to the buffer
      * @param buffer to put the output into
      */
      virtual void copy_out(uint8_t buffer[]) = 0;
      // ...
}

后面的三个函数呢，其实也是需要具体的算法来实现的，然后呢，具体作用注释应该是写的比较详细的，在这里我也不去翻译一下了，看看原汁原味的注释挺好的。然后上面的那俩函数是从Buffered_Computation这里过来的，然后在这里给实现了，我们进去看一下具体的实现。

/*
* Update the hash
*/
void MDx_HashFunction::add_data(const uint8_t input[], size_t length)
   {
   // 获取分块长度，因为当时对于分块的大小是对2取的对数，这里要在搞回去，搞成真实的长度
   const size_t block_len = static_cast<size_t>(1) << m_block_bits;
   
   // 这个比较容易理解，记录一下最终消息的长度
   m_count += length;
   
   // 这块是处理连续add_data之后，如果还有没处理完的消息，然后做进一步的处理，因为对于md结构来说这块处理最小单元是一个block
   if(m_position)
      {
      buffer_insert(m_buffer, m_position, input, length);

      if(m_position + length >= block_len)
         {
         compress_n(m_buffer.data(), 1);
         input += (block_len - m_position);
         length -= (block_len - m_position);
         m_position = 0;
         }
      }

   // Just in case the compiler can't figure out block_len is a power of 2
   const size_t full_blocks = length >> m_block_bits;
   const size_t remaining   = length & (block_len - 1);
   
   // 这里是处理连续的分块，就是满分块的消息内容，这块处理也比较简单，直接做一次compress_n就可以了.
   if(full_blocks > 0)
      {
      compress_n(input, full_blocks);
      }
      
   // 处理填充剩余的分块，将剩余的分块写到m_buffer里面
   buffer_insert(m_buffer, m_position, input + full_blocks * block_len, remaining);
   // 修改m_position的偏移，记录下还没处理的长度，便于后续的final或者下次的add_data.
   m_position += remaining;
   }

/*
* Finalize a hash
*/
void MDx_HashFunction::final_result(uint8_t output[])
   {
   // 和上面一样，获取到分块的长度
   const size_t block_len = static_cast<size_t>(1) << m_block_bits;
   
   // 这里对没用的m_buffer进行一个清0的操作，因为前期会对于m_buffer进行添加内容，因为每次都是满分块然后进行的compree_n，因此不会有问题，到这里是要进行最终的操作了，因此这里需要进行一个清零的操作，要不会出现里面里面不知道剩余内容是什么的情况
   clear_mem(&m_buffer[m_position], block_len - m_position);
   // 对md结构进行padding
   m_buffer[m_position] = m_pad_char;
   
   // 这里padding会出现两种情况，一种是剩余padding的内容恰好可以放到剩余的分组里面，另一种自然就是放不开，首先处理下放不开的情况，这里需要多padding一个分组。
   if(m_position >= block_len - m_counter_size)
      {
      compress_n(m_buffer.data(), 1);
      zeroise(m_buffer);
      }

   BOTAN_ASSERT_NOMSG(m_counter_size <= output_length());
   BOTAN_ASSERT_NOMSG(m_counter_size >= 8);
   
   // 获取消息的长度，这里是比特长度，感觉这块有一些问题，如果要存的长度超过了uint64的话，这里是不能处理的，我没找到在这里处理的情况，这就是上面我疑惑的那一点，如果有读者理解了，欢迎和我交流，在这里感谢各位读者大佬了.
   const uint64_t bit_count = m_count * 8;
   
   // 根据字节序放入消息长度的信息
   if(m_count_big_endian)
      store_be(bit_count, &m_buffer[block_len - 8]);
   else
      store_le(bit_count, &m_buffer[block_len - 8]);
      
   // 最终剩余的内容，进行一次压缩处理
   compress_n(m_buffer.data(), 1);
   // 输出结果
   copy_out(output);
   // 清零状态，做一次reset恢复到初始状态
   clear();
   }
}

最后呢，还剩下一个构造函数，这块同样的比较简单，只是作为一些初始化状态的处理

/*
* MDx_HashFunction Constructor
*/
MDx_HashFunction::MDx_HashFunction(size_t block_len,
                                   bool byte_big_endian,
                                   bool bit_big_endian,
                                   uint8_t cnt_size) :
   // 初始化一些状态
   m_pad_char(bit_big_endian == true ? 0x80 : 0x01),
   m_counter_size(cnt_size),
   m_block_bits(ceil_log2(block_len)),
   m_count_big_endian(byte_big_endian),
   m_count(0),
   m_buffer(block_len),
   m_position(0)
   {
   if(!is_power_of_2(block_len))
      throw Invalid_Argument("MDx_HashFunction block length must be a power of 2");
   if(m_block_bits < 3 || m_block_bits > 16)
      throw Invalid_Argument("MDx_HashFunction block size too large or too small");
   if(m_counter_size < 8 || m_counter_size > block_len)
      throw Invalid_State("MDx_HashFunction invalid counter length");
   }

根据上面的注释，理解md结构的代码应该不难，这里就不在通过文字描述再来复述一遍了，好了，到这里我们就把md整个结构的代码部分给讲完了，这一篇文章的篇幅有一些长，因为前置需要了解的代码有一点点的多，后面再看剩余的同类型的哈希函数，那么我们就只需要来看整个压缩函数的结构就好了，就不重复再来聊一遍整个执行链条了。

MD5

❝

代码路径: src/lib/hash/md5/md5.hMD5

❞

/**
* MD5
*/
class MD5 final : public MDx_HashFunction
   {
   public:
      std::string name() const override { return "MD5"; }
      size_t output_length() const override { return 16; }
      std::unique_ptr<HashFunction> new_object() const override { return std::make_unique<MD5>(); }
      std::unique_ptr<HashFunction> copy_state() const override;

      void clear() override;

      MD5() : MDx_HashFunction(64, false, true), m_M(16), m_digest(4)
         { clear(); }

   private:
      void compress_n(const uint8_t[], size_t blocks) override;
      void copy_out(uint8_t[]) override;

      /**
      * The message buffer
      */
      secure_vector<uint32_t> m_M;

      /**
      * The digest value
      */
      secure_vector<uint32_t> m_digest;
   };

因为前面讲完了它的父类，因此对于具体的md5来说，这块代码就比较好理解了，同样的个人感觉可以分为三个部分，第一部分是算法内部函数，其实也就是那些有关于实际md5计算的函数，然后第二部分是有关于md5的框架函数，其实也就是我之前在前面体积到的框架函数，第三部分是md5的公开调用函数，我们可以不用框架的相关代码，直接实例化md5的实例来调用，有关于具体的代码内容和代码的具体作用，参考原版注释感觉就比较清楚了，这里也不展开来仔细聊了，然后我们把重点放到压缩函数compress_n上，其他的都是套路代码了，没什么好看的。

copy_out

这个代码的内容也比较简单，没啥好说的，为了坚定不移的凑字数，哎，对光明正大的凑字数，我在这里多啰嗦几句，这个代码是完成了一个对于输出结果的一个拷贝。

/*
* Copy out the digest
*/
void MD5::copy_out(uint8_t output[])
   {
   copy_out_vec_le(output, output_length(), m_digest);
   }

clear

这个是状态的一个重置，想到这里，就会有md5的一个特征，也就是存在着4个常量，在这里稍微多聊两句吧，希望那些分析算法的大佬不要顺着网线来揍我，这仅代表我的个人看法，先给大佬们递茶了。

/*
* Clear memory of sensitive data
*/
void MD5::clear()
   {
   MDx_HashFunction::clear();
   zeroise(m_M);
   m_digest[0] = 0x67452301;
   m_digest[1] = 0xEFCDAB89;
   m_digest[2] = 0x98BADCFE;
   m_digest[3] = 0x10325476;
   }

那么我们怎么能够在不改变算法特征的时候取消掉这个常量的特征呢，首先来一个最简单的方案，我们可以在这个值前异或一个值，然后用的时候在异或一个新的值，举个例子，第一个值可以改成

void MD5::clear()
   {
   // ...
   m_digest[0] = 0x3f08cee1 ^ 0x584dede0;
   // ...
   }

这里我们仅仅以第一个值为例，剩下的也可以这么来搞，不过这么搞也有个缺点，就是编译器优化一下，可以把这两个常量给优化没了，因为这个值是可以预计算出来的，这也就导致了我们修改的失效了，那么我们怎么可以来升级下呢，这里看雪的一篇帖子给了思路，在这里感谢34r7hm4n大佬分享的的文章，具体链接放到文末的参考资料了。

这里为了简化，因为我不想去装那些依赖库，然后我也不想手动计算，这里引用原来文章当中的多项式，我就不在去搞一个新的了。

然后把，发现这个只能用 uint_8，可惜了，不能直接借(白)鉴(嫖)了，不过这个mba的表达式还是可以直接用的，然后装一下z3的库吧，我这手动生成一个，哎，偷懒没偷成，最终还是要搞一下z3，为了保证阅读的流畅性，z3以及生成多项式的操作放在附录当中把，如果原本环境配置了，这里实际上就不用再次配置了的，这里直接给出一组表达式。

然后呢，我们得到一个新的表达式，如下:

然后，我们得到了一个新的等价的一个代码

void MD5::clear()
   {
   // ...
   m_digest[0] = (282475249 * (3192616465 * ((0x66198748 ^ 0x12b9bb9) + 2 * (0x66198748 & 0x12b9bb9)) + 3016468969) + 16807);
   // ...
   }

上面这个表达式似乎还是可以被正常的计算出来字面量的值的，那么我们可以搞的更加，我们可以初始化一个其他的值，然后通过变量的方式插入到表达式当中，比如先给m_digest当中的第一个元素安排一个初始值，然后在用这个初始值去安排这个表达式，具体结果如下。

void MD5::clear()
   {
   // ...
   m_digest[0] = 0x66198748;
   m_digest[0] = (282475249 * (3192616465 * ((m_digest[0] ^ 0x12b9bb9) + 2 * (m_digest[0] & 0x12b9bb9)) + 3016468969) + 16807);
   // ...
   }

这种杀伤力感觉还不够，那么将这两个赋值的地方给搞远一些，这样原来的值0x67452301就被完美的隐藏起来了，是不是感受到了满满的友爱~~。

好了，有关怎么来隐藏这个常量就先介绍到这里，希望各位大佬千万不要顺着网线来揍我，先跑为敬。

compress_n

前面这段扯得有点远，咱们再回来，接着来看源码，我们最后还剩下一个函数，也就是几乎所有哈希函数的一个核心，也就是compress_n函数。

/*
* MD5 Compression Function
*/
void MD5::compress_n(const uint8_t input[], size_t blocks)
   {
   // 获取状态，也就是拿到A、B、C、D的值
   uint32_t A = m_digest[0], B = m_digest[1], C = m_digest[2], D = m_digest[3];
   
   // 前文已经提到过，到这个函数里面，这一定是完整的分块了，因此这里只需要遍历分块数，来执行对应每个分块的压缩函数就可以了，内部整个MD5的压缩函数了，有关压缩函数的具体内容，不熟悉的读者可以去参考下我之前所写的文章或者去参考下RFC.
   for(size_t i = 0; i != blocks; ++i)
      {
      // 读取一个分块的数据
      load_le(m_M.data(), input, m_M.size());
      
      // 下面是一组压缩函数的处理过程，这个不详细展开讲了，后文咱们去看下每个函数的实现在讲
      FF< 7>(A,B,C,D,m_M[ 0]+0xD76AA478);   FF<12>(D,A,B,C,m_M[ 1]+0xE8C7B756);
      FF<17>(C,D,A,B,m_M[ 2]+0x242070DB);   FF<22>(B,C,D,A,m_M[ 3]+0xC1BDCEEE);
      FF< 7>(A,B,C,D,m_M[ 4]+0xF57C0FAF);   FF<12>(D,A,B,C,m_M[ 5]+0x4787C62A);
      FF<17>(C,D,A,B,m_M[ 6]+0xA8304613);   FF<22>(B,C,D,A,m_M[ 7]+0xFD469501);
      FF< 7>(A,B,C,D,m_M[ 8]+0x698098D8);   FF<12>(D,A,B,C,m_M[ 9]+0x8B44F7AF);
      FF<17>(C,D,A,B,m_M[10]+0xFFFF5BB1);   FF<22>(B,C,D,A,m_M[11]+0x895CD7BE);
      FF< 7>(A,B,C,D,m_M[12]+0x6B901122);   FF<12>(D,A,B,C,m_M[13]+0xFD987193);
      FF<17>(C,D,A,B,m_M[14]+0xA679438E);   FF<22>(B,C,D,A,m_M[15]+0x49B40821);
      
      GG< 5>(A,B,C,D,m_M[ 1]+0xF61E2562);   GG< 9>(D,A,B,C,m_M[ 6]+0xC040B340);
      GG<14>(C,D,A,B,m_M[11]+0x265E5A51);   GG<20>(B,C,D,A,m_M[ 0]+0xE9B6C7AA);
      GG< 5>(A,B,C,D,m_M[ 5]+0xD62F105D);   GG< 9>(D,A,B,C,m_M[10]+0x02441453);
      GG<14>(C,D,A,B,m_M[15]+0xD8A1E681);   GG<20>(B,C,D,A,m_M[ 4]+0xE7D3FBC8);
      GG< 5>(A,B,C,D,m_M[ 9]+0x21E1CDE6);   GG< 9>(D,A,B,C,m_M[14]+0xC33707D6);
      GG<14>(C,D,A,B,m_M[ 3]+0xF4D50D87);   GG<20>(B,C,D,A,m_M[ 8]+0x455A14ED);
      GG< 5>(A,B,C,D,m_M[13]+0xA9E3E905);   GG< 9>(D,A,B,C,m_M[ 2]+0xFCEFA3F8);
      GG<14>(C,D,A,B,m_M[ 7]+0x676F02D9);   GG<20>(B,C,D,A,m_M[12]+0x8D2A4C8A);

      HH< 4>(A,B,C,D,m_M[ 5]+0xFFFA3942);   HH<11>(D,A,B,C,m_M[ 8]+0x8771F681);
      HH<16>(C,D,A,B,m_M[11]+0x6D9D6122);   HH<23>(B,C,D,A,m_M[14]+0xFDE5380C);
      HH< 4>(A,B,C,D,m_M[ 1]+0xA4BEEA44);   HH<11>(D,A,B,C,m_M[ 4]+0x4BDECFA9);
      HH<16>(C,D,A,B,m_M[ 7]+0xF6BB4B60);   HH<23>(B,C,D,A,m_M[10]+0xBEBFBC70);
      HH< 4>(A,B,C,D,m_M[13]+0x289B7EC6);   HH<11>(D,A,B,C,m_M[ 0]+0xEAA127FA);
      HH<16>(C,D,A,B,m_M[ 3]+0xD4EF3085);   HH<23>(B,C,D,A,m_M[ 6]+0x04881D05);
      HH< 4>(A,B,C,D,m_M[ 9]+0xD9D4D039);   HH<11>(D,A,B,C,m_M[12]+0xE6DB99E5);
      HH<16>(C,D,A,B,m_M[15]+0x1FA27CF8);   HH<23>(B,C,D,A,m_M[ 2]+0xC4AC5665);

      II< 6>(A,B,C,D,m_M[ 0]+0xF4292244);   II<10>(D,A,B,C,m_M[ 7]+0x432AFF97);
      II<15>(C,D,A,B,m_M[14]+0xAB9423A7);   II<21>(B,C,D,A,m_M[ 5]+0xFC93A039);
      II< 6>(A,B,C,D,m_M[12]+0x655B59C3);   II<10>(D,A,B,C,m_M[ 3]+0x8F0CCC92);
      II<15>(C,D,A,B,m_M[10]+0xFFEFF47D);   II<21>(B,C,D,A,m_M[ 1]+0x85845DD1);
      II< 6>(A,B,C,D,m_M[ 8]+0x6FA87E4F);   II<10>(D,A,B,C,m_M[15]+0xFE2CE6E0);
      II<15>(C,D,A,B,m_M[ 6]+0xA3014314);   II<21>(B,C,D,A,m_M[13]+0x4E0811A1);
      II< 6>(A,B,C,D,m_M[ 4]+0xF7537E82);   II<10>(D,A,B,C,m_M[11]+0xBD3AF235);
      II<15>(C,D,A,B,m_M[ 2]+0x2AD7D2BB);   II<21>(B,C,D,A,m_M[ 9]+0xEB86D391);

      // 更新状态
      A = (m_digest[0] += A);
      B = (m_digest[1] += B);
      C = (m_digest[2] += C);
      D = (m_digest[3] += D);

      input += hash_block_size();
      }
   }

从这里来看，整个MD5的核心也不难理解，上面还遗留了一点点小问题，我们来看一下MD5当中的4个关键函数，首先我们先来回顾一下RFC当中的内容。

我们先来看一下原版的四个核心函数

F(X,Y,Z) = XY v not(X) Z
G(X,Y,Z) = XZ v Y not(Z)
H(X,Y,Z) = X xor Y xor Z
I(X,Y,Z) = Y xor (X v not(Z))

// FF
a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s)
// GG
a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s)
// HH
a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s)
// II
a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s)

我们对比来看一下这两个的实现，乍一看，似乎这两个的实现是差异有一点点大的，我们一步一步来去分析一下，先看在每个函数当中都用到的choose子函数

template<typename T>
inline constexpr T choose(T mask, T a, T b)
   {
   //return (mask & a) | (~mask & b);
   return (b ^ (mask & (a ^ b)));
   }

我们先来看被注释掉的表达式，实际上是和RFC当中的表达式是一样的，不过实话说，我没想明白他是怎么变换过去的，验证的话可以直接列一下真值表，这俩的真值表是一样的，然后相比于原始的表达式，第二种用到的操作是更少的，然后就搜索了一通，确实是有这个优化的，具体可以参考文末的参考资料，有关md5的运算加速也不是本篇文章的主要内容，不过这个点确实卡我好久，本来是想尝试通过布尔代数推导一下，但是由于本人能力实在有限，没推出来，不过能想到这个优化的大佬是真的nb，在这里给各位密码学大佬们递茶了。然后下面的那个对于I的优化，也在文末的参考资料里面有，这里也不展开了，不过这么一边换，似乎又增加了找特征的难度，或者不考虑性能，可以完全用一个非常复杂的等价的布尔表达式来做这套处理，溜了，溜了~~

/*
* MD5 FF Function
*/
template<size_t S>
inline void FF(uint32_t& A, uint32_t B, uint32_t C, uint32_t D, uint32_t M)
   {
   A += choose(B, C, D) + M;
   A  = rotl<S>(A) + B;
   }

/*
* MD5 GG Function
*/
template<size_t S>
inline void GG(uint32_t& A, uint32_t B, uint32_t C, uint32_t D, uint32_t M)
   {
   A += choose(D, B, C) + M;
   A  = rotl<S>(A) + B;
   }

/*
* MD5 HH Function
*/
template<size_t S>
inline void HH(uint32_t& A, uint32_t B, uint32_t C, uint32_t D, uint32_t M)
   {
   A += (B ^ C ^ D) + M;
   A  = rotl<S>(A) + B;
   }

/*
* MD5 II Function
*/
template<size_t S>
inline void II(uint32_t& A, uint32_t B, uint32_t C, uint32_t D, uint32_t M)
   {
   // This expr is choose(D, B ^ C, ~C), but that is slower
   A += (C ^ (B | ~D)) + M;
   A  = rotl<S>(A) + B;
   }

}

到这里，实际上有关于md5的源码的介绍就讲完了，本质上还是对于整个md5的实现，然后因为这是第一篇文章，因此前面铺垫的知识有那么一点点多，这篇文章整体也比较长，不过看完这一篇文章，如果对于其他的使用MD结构的哈希函数而言，看起来就比较简单了。

结束语

到这里，本文的分析就结束了，感谢读者可以阅读到这里，咱们下次再见~~

番外

z3生成互逆的一次多项式

首先，编译一下z3这个库，这里我采用cmake的方案，需要其他方案的自行参考文档，这里简单给出我这的方案.

git clean -nx src
git clean -fx src
mkdir build
cd build
cmake -G "Unix Makefiles" -DCMAKE_BUILD_TYPE=Release ../
make -j4 # Replace 4 with an appropriate number
make install

这样就给安排好了，然后呢，我们需要写一个项目，来引入z3的库，对于如何找到互逆的一次多项式，在看雪大佬的帖子里面已经给出了完整的代码，这里简单的放一下我的 CMakeLists.txt的文件。

cmake_minimum_required(VERSION 3.14)
project(demo1)

set(CMAKE_C_STANDARD_REQUIRED ON)
set(CMAKE_CXX_STANDARD 17)
set(CMAKE_C_EXTENSIONS OFF)

find_package(Z3 REQUIRED BUILD_PATH)
message(STATUS "Z3_FOUND: ${Z3_FOUND}")
message(STATUS "Found Z3 ${Z3_VERSION_STRING}")
message(STATUS "Z3_DIR: ${Z3_DIR}")

add_executable(demo1 main.cpp)

option(FORCE_CXX_LINKER "Force linker with C++ linker" OFF)
if (FORCE_CXX_LINKER)
    # This is a hack for avoiding UBSan linking errors
    message(STATUS "Forcing use of C++ linker")
    set_target_properties(demo1
            PROPERTIES
            LINKER_LANGUAGE CXX
            )
endif()

target_include_directories(demo1 PRIVATE ${Z3_C_INCLUDE_DIRS})
target_link_libraries(demo1 PRIVATE ${Z3_LIBRARIES})

然后，完整的c++代码也给贴一下吧，看雪的帖子里面也有

#include "z3++.h"
#include <cstdio>
#include <cstdint>
#include <iostream>

using namespace std;
using namespace z3;

uint32_t inverse(uint32_t n, uint32_t bitWidth) {
    context c;
    solver s(c);
    expr a = c.bv_val(n, bitWidth);
    expr a_inv = c.bv_const("a_inv", bitWidth);
    s.add(a * a_inv == 1);
    s.add(a_inv != 0);
    s.check();
    model m = s.get_model();
    return m.eval(a_inv).get_numeral_uint();
}


void generateUnivariatePoly(uint32_t *a, uint32_t *b, uint32_t bitWidth) {
    uint32_t a0, a1, b0, b1, a1_inv;
    a0 = (uint32_t) rand(), a1 = (uint32_t) rand();

    // Calculate a1_inv
    a1_inv = inverse(a1, bitWidth);

    // Calculate b1
    b1 = a1_inv;

    // Calculate b0
    b0 = -(b1 * a0);

    a[0] = a0, a[1] = a1, b[0] = b0, b[1] = b1;
    printf("%u, %u, %u, %u", a[0], b[0], a[1], b[1]);
}

int main() {
    uint32_t a[2] = {0, 0};
    uint32_t b[2] = {0, 0};
    // 16807, 3016468969, 282475249, 3192616465
    generateUnivariatePoly(a, b, 32);
    return 0;
}

这里我进行了一点点改动，因为我这不需要64位的，我这32位就够了，因此我把类型给改成了32位，然后到这里多项式就生成出来了，不过上面的那个随机函数大概率应该是没啥用，因为种子是一样的，所以生产出来的随机数也是一样的，因为我这里懒得改了，就这么先用一下吧。

参考资料

• https://bbs.pediy.com/thread-271688.htm
• https://bbs.pediy.com/thread-271574.htm
• https://github.com/Z3Prover/z3
• https://www.rfc-editor.org/rfc/rfc1321
• https://github.com/animetosho/md5-optimisation