65.9K
CodeProject 正在变化。 阅读更多。
Home

海绵结构和 SHA-3 散列函数：C# 实现

phil.o
starIconstarIconstarIconstarIconstarIcon

5.00/5 (7投票s)

2018年1月29日

CPOL

21分钟阅读

viewsIcon

29587

downloadIcon

457

海绵结构和 SHA-3 散列操作的 C# 实现

A bitstring

目录

引言

我喜欢玩位，我真的喜欢。几年前，我正在寻找有关散列算法的通用信息，并找到了 FIPS PUB 202 - SHA-3 标准[^]，当时它还是一个草案。我开始尝试它，本文介绍了由此产生的实现。

以上文档内容不言自明。因此，我鼓励您在阅读本系列文章之前先看一下它。所以，我将尽量不重述它，我只会做得更糟。相反，我将尝试根据该规范对所做的设计选择进行评论和论证。

注释

  • 您至少需要 Visual Studio 2017 Community Edition 才能使用提供的解决方案。对于那些仍然使用旧版本的人，我很抱歉，我不再安装它们了。
  • 您还需要具备一些基本的位操作知识。如果您不理解这个笑话，世界上只有 10 种人：一种是懂二进制的，另一种是不懂二进制的。，那么您可能很难跟上。

静态方法

有三个 static 方法几乎在整个建议的解决方案中都被使用。这些方法被分组在一个 static Bin 类中。

  • Mod 方法是一个取模运算，它的行为与核心 % 取模运算符不同，特别是对于负值。它返回整数 r，其中 0 <= r < mod 且 value - r 是 mod 的倍数。它被海绵结构用于处理其 3D 坐标系。
    % 运算符 -1 % 5 == -1
    Mod 方法 Mod(-1, 5) == 4 
    public static int Mod(int value, int mod) {
   return value - mod * (int)Math.Floor((double)value / mod);
}
  • LowerMask 方法返回一个字节值的指定低位（模 8）的位掩码。此掩码可用于将字节值修剪为指定数量的位，从其最低位开始。例如，假设您有位字符串 "0110 1001"；如果您对其 4 个低位（掩码将是 "0000 1111"）应用掩码，则掩码后的值将是 "0000 1001"。
    public static byte LowerMask(int count) {
   byte value = 0;
   if (count > 0) {
      count %= 8;
      if (count == 0) {
         value = 255;
      }
      else {
         for (int i = 0; i < count; i++) {
            value |= (byte)(1 << i);
         }
      }
   }
   return value;
}
  • Log2 方法返回指定整数的以 2 为底的对数。从位运算角度来看，它对应于数字中最高非零位的偏移量。此实现是 Bit Twiddling Hacks - 在 O(log(N)) 操作中找到 N 位整数的以 2 为底的对数[^] 中提出的实现。
    private static readonly int[] _b = new int[] { 2, 12, 240, 65280, -65536 };
private static readonly int[] _s = new int[] { 1, 2, 4, 8, 16 };

public static int Log2(int value) {
   int log = 0;
   for (int i = 4; i > -1; i--) {
      if ((value & _b[i]) != 0) {
         value >>= _s[i];
         log |= _s[i];
      }
   }
   return log;
}

Bitstring 类

海绵结构上的所有操作都作用于固定长度的位集合，称为 bitstring。一个 bitstring 可以看作是 特定长度的位序列[1]；它也可以定义为 固定长度的块序列，其最后一个块可以更短[1]（当 bitstring 的总长度不是块大小的倍数时）。尽管参考文献专门用 8 位块定义了 bitstring，但我更喜欢一个更通用的定义，最终允许处理底层存储使用更大无符号整数类型的 bitstring。不过，提出的实现使用 byte 值作为底层存储，符合规范。

选择为 Bitstring 类实现两个接口

  • IEquatable<Bitstring> 接口，它将允许我们确定两个 Bitstring 实例是否共享相同的长度和位序列。
  • IEnumerable<bool> 接口，它正式将 Bitstring 定义为位的枚举。

Bitstring 类本身包含两个 private 字段

  • 一个存储 bitstring 位长度的整数字段
  • 一个存储位的 byte 值数组

bitstring 的位从零（bitstring 的最左边位）到 bitstring 的长度减一（bitstring 的最右边位）进行索引。

 位字符串索引

为了将 bitstring 的指定位映射到其内部数组中的相应位，使用以下公式

  • 包含该位的块的索引是 index / 8。
  • 块内位的偏移量是 index % 8。

Bitstring 类被定义为 sealed。出于性能考虑，我希望尽可能避免核心对象（bitstring 和海绵状态）的虚成员。

bitstring 的基本功能包括

  • 能够获取 bitstring 的位长度
  • 能够获取内部数组中的字节数
  • 能够获取或设置 bitstring 中指定索引处的位

所以，这是 Bitstring 类的核心骨架

public sealed class Bitstring : IEquatable<Bitstring>, IEnumerable<bool>
{
   public const int BlockBitSize = 8;
   public const int BlockByteSize = BlockBitSize >> Shift;
   public const int Shift = 3;

   private byte[] _data;
   private int _length;

   public int BlockCount { get { return _data.Length; } }

   public int Length { get { return _length; } }

   public bool this[int index] {
      get {
         if ((index < 0) || (index >= _length)) {
            throw new ArgumentOutOfRangeException(nameof(index));
         }
         int blockIndex = index >> Shift;
         int bitOffset = index % BlockBitSize;
         byte chunk = _data[blockIndex];
         byte mask = (byte)(1 << bitOffset);
         return ((chunk & mask) == mask);
      }
      set {
         if ((index < 0) || (index >= _length)) {
            throw new ArgumentOutOfRangeException(nameof(index));
         }
         int blockIndex = index >> Shift;
         int bitOffset = index % BlockBitSize;
         byte chunk = _data[blockIndex];
         byte mask = (byte)(1 << bitOffset);
         if (value) {
            _data[blockIndex] |= mask;
         }
         else {
            _data[blockIndex] &= (byte)(~mask & 0xFF);
         }
      }
   }
}

您可以看到，这里的数学运算与我们使用位标志枚举时所使用的相同。正式地说：

  • 对于属性**getter**，从平面索引中检索块索引和位偏移量。使用块索引获取相应的字节，并根据位偏移量构造一个位掩码。使用掩码返回字节值是否与指定偏移量处的位匹配。
  • 对于属性**setter**，根据要设置的值（true 或 false），使用与上述相同的掩码过程（通过位或运算）设置指定偏移处的位，或使用掩码的二进制补码（通过位与运算）清除它。

对字节值的操作，特别是位操作，速度相当快。由于 this 项访问器属性将被大量使用（请参阅 步骤映射），因此在此处尽量提高其效率至关重要。

IEquatable<Bitstring> 接口的实现很有趣，因为它是一个引用类型接口的通用实现。

public bool Equals(Bitstring other) {
   if (ReferenceEquals(other, null)) {
      return false;
   }
   if (ReferenceEquals(this, other)) {
      return true;
   }
   return (_length == other._length) && Enumerable.SequenceEqual(_data, other._data);
}

public override bool Equals(object obj) {
   return (obj is Bitstring) && Equals((Bitstring)obj);
}

public override int GetHashCode() {
   // HashCoder<T> class is not described in this article, but source file
   // is provided in solution download.
   return HashCoder<int>.Boost.Compute(_length, HashCoder<byte>.Boost.Compute(_data));
}

public static bool operator ==(Bitstring lhs, Bitstring rhs) {
   return ReferenceEquals(lhs, rhs) || (!ReferenceEquals(lhs, null) && lhs.Equals(rhs));
}

public static bool operator !=(Bitstring lhs, Bitstring rhs) {
   return !ReferenceEquals(lhs, rhs) && (ReferenceEquals(lhs, null) || !lhs.Equals(rhs));
}

IEnumerable<bool> 接口通过一个 private GetBits 方法实现，该方法迭代生成 bitstring 的位并提供所需的枚举器。

public IEnumerator<bool> GetEnumerator() {
   return GetBits().GetEnumerator();
}

IEnumerator IEnumerable.GetEnumerator() {
   return GetEnumerator();
}

private IEnumerable<bool> GetBits() {
   for (int i = 0; i < _length; i++) {
      yield return this[i];
   }
}

Bitstring 类提供了六个构造函数，允许

  1. 创建指定长度的 bitstring
    public Bitstring(int length) {
   if (length < 0) {
      throw new ArgumentOutOfRangeException(nameof(length));
   }
   _length = length;
   _data = new byte[(int)Math.Ceiling((double)_length / BlockBitSize)];
}
  2. 创建一个空 bitstring（长度为零的 bitstring）
    public Bitstring() : this(0) { }
  3. 从现有 bitstring 创建一个 bitstring（复制构造函数）
    public Bitstring(Bitstring bitstring) {
   bitstring = bitstring ?? throw new ArgumentNullException(nameof(bitstring));
   int count = bitstring.BlockCount;
   _data = new byte[count];
   Array.Copy(bitstring._data, 0, _data, 0, count);
   _length = bitstring._length;
}
  4. 从位的枚举创建一个 bitstring
    public Bitstring(IEnumerable<bool> bits) {
   bits = bits ?? throw new ArgumentNullException(nameof(bits));
   _data = Parse(bits, out _length);
}

private static byte[] Parse(IEnumerable<bool> bits, out int length) {
   // 200 bytes -> 1600 bits for most common used Keccak-p permutations
   List<byte> bytes = new List<byte>(200);
   byte value = 0;
   int index = 0;
   bool add = true;
   length = 0;
   foreach (bool bit in bits) {
      length++;
      if (bit) {
         value |= (byte)(1 << index);
      }
      if (++index > 7) {
         index = 0;
         bytes.Add(value);
         value = 0;
         add = false;
      }
      else if (!add) {
         add = true;
      }
   }
   if (add) {
      bytes.Add(value);
   }
   return bytes.ToArray();
}
  5. 从二进制数字字符串和可选长度创建一个 bitstring（解析构造函数）。使用一个只匹配 1、0 和空白字符的正则表达式来验证提供的 string 是否是有效的二进制表示。length 参数是可选的，负值将导致解析所有输入位。
    public Bitstring(string bits, int length = -1) {
   if (ValidateAndSanitize(ref bits, ref length)) {
      int count = (int)Math.Ceiling((double)length / BlockBitSize);
      _data = new byte[count];
      int left = bits.Length;
      int i;
      // Stop the loop either when there is less than 8 bits to parse, 
      // or when desired length
      // exceeds the size of specified string.
      for (i = 0; (left >= BlockBitSize) && ((i << Shift) < length); i++) {
         _data[i] = ParseByte(bits.Substring(i << Shift, BlockBitSize));
         left -= BlockBitSize;
      }
      if (left > 0) {
         _data[i] = ParseByte(bits.Substring(i << Shift, left));
      }
      _length = length;
   }
   else {
      throw new ArgumentException
            ("Invalid bitstring representation.", nameof(bits));
   }
}

// Only 0s, 1s or whitespaces, empty string allowed
private static readonly Regex _bitstringRegex
   = new Regex(
      @"^[01\s]*$",
      RegexOptions.Compiled | RegexOptions.CultureInvariant
);

private static bool ValidateAndSanitize(ref string bits, ref int length) {
   return (ValidateBits(ref bits) && ValidateLength(ref length, bits.Length);
}

private static bool ValidateBits(ref string bits) {
   bool ok = (bits != null);
   if (ok) {
      ok = _bitstringRegex.IsMatch(bits);
      if (ok && bits.Contains(" ")) {
         bits = bits.Replace(" ", "");
      }
   }
   return ok;
}

private static bool ValidateLength(ref int length, int stringLength) {
   if (length < 0) {
      length = stringLength;
   }
   return true;
}

private static byte ParseByte(string chunk) {
   byte result = 0;
   int length = chunk.Length;
   for (int i = 0; i < length; i++) {
      if (chunk[i] == '1') {
         result |= (byte)(1 << i);
      }
   }
   return result;
}
  6. 从 byte 数组和可选长度创建一个 bitstring
    public Bitstring(byte[] data, int length = -1) {
   // Sanity checks
   data = data ?? throw new ArgumentNullException(nameof(data));
   int count = data.Length;
   int bitCount = count << Shift;
   _length = (length < 0) ? bitCount : length;
   if (_length > bitCount) {
      throw new ArgumentOutOfRangeException(nameof(length));
   }
   // If the full range of bits is to be considered, 
   // whole process is a lot simpler.
   if (_length != bitCount) {
      // How many blocks will we need?
      count = (int)Math.Ceiling((double)_length / BlockBitSize);
      Array.Resize(ref data, count);
      // If the last block is not full, 
      // zero the trailing bits which do not belong
      // to the bitstring.
      int remaining = _length % BlockBitSize;
      if (remaining > 0) {
         data[count - 1] &= Bin.LowerMask(remaining);
      }
   }
   _data = data;
}

然后，提供了五个实例方法，允许修改位字符串的内部字节数组。这些方法会**修改**调用它们的实例，并返回该实例，以便它们最终可以链接。

  1. 两个 Append 方法，它们将指定的位或字节数组添加到 bitstring 的末尾。字节数组版本首先检查当前长度是否与字节对齐；如果是，则可以进行简单的数组复制；如果不是，则该方法诉诸于（较慢的）位枚举版本。
    public Bitstring Append(byte[] bytes) {
   if (bytes != null) {
      if ((_length % BlockBitSize) == 0) { // Array copy if aligned data
         int count = bytes.Length;
         int oldCount = BlockCount;
         Array.Resize(ref _data, oldCount + count);
         Array.Copy(bytes, 0, _data, oldCount, count);
         _length += count << Shift;
      }
      else {                               // Enumeration if unaligned data
         return Append(new Bitstring(bytes));
      }
   }
   return this;
}

public Bitstring Append(IEnumerable<bool> bits) {
   int count = bits?.Count() ?? 0;
   if (count > 0) {
      int blockIndex = _length >> Shift;
      int bitOffset = _length % BlockBitSize;
      _length += count;
      int newBlockCount = (int)Math.Ceiling((double)_length / BlockBitSize);
      if (newBlockCount > BlockCount) {
         Array.Resize(ref _data, newBlockCount);
      }
      foreach (bool bit in bits) {
         if (bit) {
            _data[blockIndex] |= (byte)(1 << bitOffset);
         }
         if (++bitOffset > 7) {
            bitOffset = 0;
            blockIndex++;
         }
      }
   }
   return this;
}
  2. 两个 Prepend 方法，它们将指定的位或字节数组插入到 bitstring 的开头。这里字节数组版本非常简单，因为字节数组本质上是字节对齐的。
    public Bitstring Prepend(byte[] bytes) {
   if (bytes != null) {
      int count = bytes.Length;
      int oldCount = BlockCount;
      Array.Resize(ref _data, oldCount + count);
      Array.Copy(_data, 0, _data, count, oldCount);
      Array.Copy(bytes, 0, _data, 0, count);
      _length += count << Shift;
   }
   return this;
}

public Bitstring Prepend(IEnumerable<bool> bits) {
   Bitstring copy = new Bitstring(this);
   int count = bits?.Count() ?? 0;
   if (count > 0) {
      _length += count;
      int newBlockCount = (int)Math.Ceiling((double)_length / BlockBitSize);
      if (newBlockCount > BlockCount) {
         Array.Resize(ref _data, newBlockCount);
      }
      int blockIndex = 0;
      int bitOffset = 0;
      foreach (bool bit in bits) {
         if (bit) {
            _data[blockIndex] |= (byte)(1 << bitOffset);
         }
         else {
            _data[blockIndex] &= (byte)~(1 << bitOffset);
         }
         if (++bitOffset > 7) {
            bitOffset = 0;
            blockIndex++;
         }
      }
      foreach (bool bit in copy) {
         if (bit) {
            _data[blockIndex] |= (byte)(1 << bitOffset);
         }
         else {
            _data[blockIndex] &= (byte)~(1 << bitOffset);
         }
         if (++bitOffset > 7) {
            bitOffset = 0;
            blockIndex++;
         }
      }
   }
   return this;
}
  3. 一个 SwapBits 方法，用于交换指定索引处的位（使用的算法是 这里 指定的算法）
    public Bitstring SwapBits(int lhs, int rhs) {
   if (IsValidIndex(lhs) && IsValidIndex(rhs) && (lhs != rhs)) {
      this[lhs] ^= this[rhs];
      this[rhs] ^= this[lhs];
      this[lhs] ^= this[rhs];
   }
   return this;
}

public bool IsValidIndex(int index) {
   return (index > -1) && (index < _length);
}
  4. 两个 Xor 方法，它们对 bitstring 的位与指定长度相同的 bitstring 或字节数组的位执行按位 XOR 操作。其他位操作也已实现，但此处未显示（实际上在 KECCAK-p 置换的上下文中甚至不需要）。另一方面，每次将输入消息提交到海绵结构时都会使用 Xor 方法。请注意，如果指定位字符串的长度不等于当前实例的长度，则不执行任何操作。
    public Bitstring Xor(byte[] data) {
   int count = BlockCount;
   if ((data != null) && (data.Length == count)) {
      for (int i = 0; i < count; i++) {
         _data[i] ^= data[i];
      }
   }
   return this;
}

public Bitstring Xor(Bitstring other) {
   return (other.Length == _length) ? Xor(other._data) : this;
}

然后，提供了两个实例方法，它们不修改 bitstring 的内部状态，而是返回一个新的 bitstring。

  1. 一个 Substring 方法，允许获取 bitstring 的任何子字符串
    public Bitstring Substring(int index, int length) {
   if (IsValidIndex(index)) {
      if (((index % BlockBitSize) == 0) && ((length % BlockBitSize) == 0)) {
         int count = length >> Shift;
         byte[] data = new byte[count];
         Array.Copy(_data, index >> Shift, data, 0, count);
         return new Bitstring(data);
      }
      else {
         return new Bitstring(this.Skip(index).Take(length));
      }
   }
   else {
      throw new ArgumentOutOfRangeException(nameof(index));
   }
}
  2. 一个 Truncate 方法，允许从 bitstring 的开头获取指定数量的位。
    public Bitstring Truncate(int length) {
   length = Math.Min(_length, Math.Max(0, length));
   int count = (int)Math.Ceiling((double)length / BlockBitSize);
   byte[] data = new byte[count];
   Array.Copy(_data, 0, data, 0, count);
   int left = length % BlockBitSize;
   if (left != 0) {
      data[count - 1] &= Bin.LowerMask(left);
   }
   return new Bitstring(data, length);
}

最后，提供了一些方法来获取 bitstring 的 string 表示，可以是十六进制或二进制形式，以及 static 属性和方法，这些将简化类的使用。我不会在这里展示它们，但它们可以很容易地在本文顶部的建议下载中找到。这里是 Bitstring 类的 public 接口的类图。

位字符串测试

作为整个解决方案中将使用的核心存储对象，在此阶段测试它是否按预期工作非常重要。

所提出的解决方案由三个项目组成

  • 一个包含实现的 DLL 项目
  • 一个用于测试 DLL 的单元测试项目
  • 一个用于快速操作的控制台程序

单元测试项目实际上包含针对 Bin 类的三个测试和针对 Bitstring 类的七十五个测试。

Tests samples for the Bitstring class

我邀请您运行并探索它们，因为它们展示了类的 public 接口用法。

   static void Main(string[] args) {
      Random random = new Random();
      Func<Bitstring> randomBitstring = () => { return Bitstring.Random(random, 42); };
      Console.WriteLine(randomBitstring().ToBinString());             // Binary, 
                                                                      // no spacing
      Console.WriteLine(randomBitstring().ToBinString(4));            // Binary, 
                                                          // spacing every fourth digit
      Console.WriteLine(randomBitstring().ToHexString());             // Hexadecimal, 
                                                          // spacing, uppercase
      Console.WriteLine(randomBitstring().ToHexString(true, false));  // Hexadecimal, 
                                                          // spacing, lowercase
      Console.WriteLine(randomBitstring().ToHexString(false, true));  // Hexadecimal, 
                                                          // no spacing, uppercase
      Console.WriteLine(randomBitstring().ToHexString(false, false)); // Hexadecimal, 
                                                          // no spacing, lowercase
      Bitstring bitstring = new Bitstring("10100101");
      Console.WriteLine(bitstring.ToBinString());
      bitstring.Xor(Bitstring.Ones(8));
      Console.WriteLine(bitstring.ToBinString());
      Console.ReadKey(true);
   }

上述代码片段产生一个随机结果，看起来像这样

A random bitstring under several representations

在我发现海绵结构并开始使用它们的时候——2016年夏天——我不知道 .NET BitArray 类，它大致实现了与 Bitstring 相同的目的。我当时可能用过它。但现在它在这里了。我无法将它扔掉，因为它非常适合手头的任务。就这样吧。

现在我们可以介绍 SpongeState 类，这是海绵结构使用的第二个低级对象。

SpongeState 类

A sponge state with a depth of 8 bits

海绵结构及其所有操作都使用一个名为 state 的内部对象。它将位保存在 bitstring 中，但允许通过 3D 数组坐标访问它们。

您可以在 FIPS PUB 202 - 第 7 页 - 3.1 状态 中找到其主要描述。

一个状态将 bitstring 划分为几个部分，并且应用于状态的置换和转换将能够对这些离散部分执行

  • 一个**位**由其三个固定坐标 x、y 和 z 定义。
    A bit
  • 一个**行**由其 y 和 z 坐标定义（可以看作是 5 位集合）。
    A row
  • 一个**列**由其 x 和 z 坐标定义（可以看作是 5 位集合）。
    A column
  • 一个**道**由其 x 和 y 坐标定义（可以看作是 w 位集合）。
    A lane
  • 一个**平面**由其 y 坐标定义（可以看作是 w 行或 5 道集合）。
    A plane
  • 一个**切片**由其 z 坐标定义（可以看作是 5 行或 5 列集合）。
    A slice
  • 一个**薄片**由其 x 坐标定义（可以看作是 w 列或 5 道集合）。
    A sheet

海绵状态的大小

海绵状态的第一个重要属性是其大小 (b)。形式上，它是它包含的位数（因此，是它使用的 bitstring 的长度）。

还有另外两个量与这个总位数有关

  • 一道中的位数 (w)，它是总位数除以 25，因为一个海绵状态中有 25 道。它也可以看作是海绵状态的深度。
  • w 的以 2 为底的对数 (l)，其用法将很快详细说明。

海绵结构实际上使用了七种尺寸。提供了一个自定义结构来表示海绵状态尺寸，并且七个 static 字段提供了对预定义值的快速访问。

海绵状态的大小 b 必须是 25 的倍数。出于对齐原因，宽度 w 最好是 2 的幂。因此，总而言之，海绵状态的大小应该同时是 25 的倍数和 2 的幂的倍数。SpongeSize 结构的构造函数被设置为内部，阻止外部世界创建不适合状态的奇异大小。

七个尺寸及其对应的 w 和 l 值如下

总位数 (b) 25 50 100 200 400 800 1600
一道中的位数 (w) 1 2 4 8 16 32 64
w 的以 2 为底的对数 (l) 0 1 2 3 4 5 6
海绵状态大小和相关量[^]

SpongeSize 结构定义如下

public struct SpongeSize
{
   private readonly int _b;

   public int B { get { return _b; } }

   public int W { get { return _b / 25; } }

   public int L { get { return Bin.Log2(W); } }

   internal SpongeSize(int b) {
      _b = b;
   }

   public static readonly SpongeSize W01 = new SpongeSize(25);
   public static readonly SpongeSize W02 = new SpongeSize(50);
   public static readonly SpongeSize W04 = new SpongeSize(100);
   public static readonly SpongeSize W08 = new SpongeSize(200);
   public static readonly SpongeSize W16 = new SpongeSize(400);
   public static readonly SpongeSize W32 = new SpongeSize(800);
   public static readonly SpongeSize W64 = new SpongeSize(1600);
}

海绵状态

除了其大小之外，状态还由其速率（或 bitrate）定义。实际上，状态中的总位数 b 分为两部分

  • rate，这是与输入消息进行异或的位数。
  • capacity，这是在与输入消息异或时保持不变的位数。

rate 和 capacity 的用法将在下一部分中详细说明，我将在其中描述海绵结构中发生的过程。

在任何时候，以下等式都成立

SpongeState.Size.B = SpongeState.Rate + SpongeState.Capacity

这是 SpongeState 类的定义。

public sealed class SpongeState
{
   private readonly int _rate;
   private readonly SpongeSize _size;

   private Bitstring _bitstring;

   public SpongeSize Size { get { return _size; } }

   public int Rate { get { return _rate; } }

   public int Capacity { get { return _size.B - _rate; } }
}

海绵状态的核心 3D 地址通过单个方法实现

public int GetIndex(int x, int y, int z) {
   return _size.W * (5 * y + x) + z;
}

该方法允许给定位在状态中的 x、y 和 z 坐标，获取其在 bitstring 中的索引。x 和 y 坐标隐含地取模 5，而 z 坐标隐含地取模 Size.W。

我们可以看到，从一个扁平的 bitstring 开始，它到海绵状态的转换按此顺序进行

  1. z 递增直到达到 w，在这种情况下 z 重置为零。
  2. 当 z 重置时，x 递增直到达到 5，在这种情况下 x 重置为零。
  3. 当 x 重置时，y 递增。

使用此单个方法，我们便能够编写以下属性，这些属性允许使用位字符串中的索引或其 3D 坐标来寻址状态的单个位。

public bool this[int index] {
   get { return _bitstring[index]; }
   set { _bitstring[index] = value; }
}

public bool this[int x, int y, int z] {
   get { return _bitstring[GetIndex(x, y, z)]; }
   set { _bitstring[GetIndex(x, y, z)] = value; }
}

现在，我们希望能够寻址一个特定的道，例如。定义了一个 Lane 结构体，它包含道的 x 和 y 坐标，以及对它所属的状态的引用。

public struct Lane
{
   public readonly SpongeState State;

   public readonly int X;

   public readonly int Y;

   public int Depth { get { return State.Size.W; } }

   internal Lane(SpongeState state, int x, int y) {
      State = state;
      X = x;
      Y = y;
   }

   public IEnumerable<bool> GetBits() {
      int w = State.Size.W;
      for (int z = 0; z < w; z++) {
         yield return State[State.GetIndex(X, Y, z)];
      }
   }
}

这种简单的结构允许以最小的开销表示一个特定的通道。通道的实际位不存储在结构中，而是在需要时枚举。此外，由于结构体的构造函数是内部的，因此只能从 SpongeState 类的 GetLane 方法获取通道

public sealed class SpongeState
{
   // ...

   public Lane GetLane(int x, int y) {
      return new Lane(this, x, y);
   }
}

状态的其他部分（列、行、平面、薄片和切片）也已定义，但我将不在此处展示它们。实际上，除了 GetColumn 方法之外，它们对于实际的 KECCAK-p 置换甚至不需要。海绵结构、双工结构或猴子结构的其他（或未来）用法可能会利用它们。

最后，定义了以下委托，用于对状态的单个位执行操作

private delegate bool OperationDelegate(int x, int y, int z, bool bit);

x、y 和 z 是要设置值的位的坐标，bit 是将对状态中 x、y 和 z 处的位进行的操作的右操作数。

例如，应用于一个道，这是它所允许的

private void LaneOperation(OperationDelegate function, 
                           Lane lane, IEnumerable<bool> bits) {
   int z = 0;
   foreach (bool bit in bits) {
      this[GetIndex(lane.X, lane.Y, z)] = function(lane.X, lane.Y, z, bit);
      z++;
   }
}

public void SetLane(Lane lane, IEnumerable<bool> bits) {
   LaneOperation(
      (x, y, z, bit) => { return bit; },
      lane,
      bits
   );
}

public void XorLane(Lane lane, IEnumerable<bool> bits) {
   LaneOperation(
      (x, y, z, bit) => { return this[x, y, z] ^ bit; },
      lane,
      bits
   );
}

同样的逻辑也适用于状态的其他部分，但是，我将不在此处展示它们。

最后，提供了三个构造函数，它们允许

  1. 创建新的海绵状态，指定其大小和速率
    public SpongeState(SpongeSize size, int rate) {
   int b = size.B;
   if ((rate < 1) || (rate >= b)) {
      throw new ArgumentException($"Invalid rate {rate} for width {b}.", 
                                    nameof(rate));
   }
   _size = size;
   _rate = rate;
   _bitstring = Bitstring.Zeroes(b);
}
  2. 从现有位字符串和速率创建海绵状态
    public SpongeState(Bitstring bitstring, int rate) {
   _bitstring = bitstring ?? throw new ArgumentNullException(nameof(bitstring));
   int length = _bitstring.Length;
   if (length < 1) {
      throw new ArgumentException("Bitstring cannot be empty.", nameof(bitstring));
   }
   _size = new SpongeSize(length);
   if ((rate < 1) || (rate >= _size.B)) {
      throw new ArgumentException($"Invalid rate {rate} for width {_size.B}.", 
                                    nameof(rate));
   }
   _rate = rate;
}
  3. 从现有海绵状态创建海绵状态
    public SpongeState(SpongeState state) {
   _size = state._size;
   _rate = state._rate;
   _bitstring = new Bitstring(state._bitstring);
}

您可以在此处查看 SpongeState 类及其相关成员的图表。如您所见，其 public 接口相当重要，但每个方法本身都非常简单明了。

SpongeState 类有 59 个单元测试，可以快速检查基本操作是否正确处理。

SpongeState tests samples

既然我们有了核心的 Bitstring 和 SpongeState 类，我们就可以愉快地跳入海绵结构的定义了。

海绵结构

The Sponge Construction - from https://commons.wikimedia.org/wiki/File:SpongeConstruction.svg

我基于其实现的海绵结构定义可以在 FIPS PUB 202 - 第 17 页 - 4. 海绵结构 中找到。它具有三个主要特征

  • 作用于固定长度 bitstring 的底层函数（转换或置换）。
  • 一个速率（或 bitrate），实际上是结构正在使用的海绵状态的速率。
  • 一个填充规则，旨在生成固定长度的输入 bitstring 到函数。

另外，海绵结构是无状态的：这意味着在函数调用之间不维护任何状态。对于双工和猴子结构来说，情况并非如此，它们在调用之间维护其内部状态。我可能会在未来的文章中探讨这两种结构。

海绵结构处理消息大致可分为两个不同的阶段

  1. 吸收阶段，消息通过海绵结构被完整处理。
  2. 挤压阶段，根据海绵结构的请求生成尽可能多的输出字节。

在此阶段，我们将定义其接口。

public interface ISpongeConstruction
{
   int Capacity { get; }
   int Rate { get; }
   SpongeSize Size { get; }
   
   byte[] Process(byte[] bytes, int outputLength, int inputLength = -1);
}

Process 方法允许限制要考虑的输入字节数组的位数。当未指定 inputLength 参数时，假定为数组中的位数。

现在我们已经定义了这些元素，我们可以实现接口了

public abstract class SpongeConstruction : ISpongeConstruction
{
   protected readonly SpongeState State;

   public int Capacity { get { return State.Capacity; } }

   public int Rate { get { return State.Rate; } }

   public SpongeSize Size { get { return State.Size; } }

   protected SpongeConstruction(SpongeSize size, int rate)
   {
      State = new SpongeState(size, rate);
   }

   public virtual byte[] Process(byte[] bytes, int outputLength, int inputLength = -1) {
      byte[] result = null;
      if (bytes != null) {
         inputLength = (inputLength > -1) ? 
                        inputLength : bytes.Length << Bitstring.Shift;
         Absorb(bytes, inputLength);
         result = Squeeze(outputLength);
      }
      return result;
   }

   protected virtual void Absorb(byte[] bytes, int length) {
      State.Clear();
      Bitstring message = new Bitstring(bytes, length);
      int rate = State.Rate;
      message.Append(Suffix());
      message.Append(GetPadding(rate, message.Length));
      int n = message.Length / rate;
      Bitstring zeroes = new Bitstring(Capacity);
      Bitstring chunk;
      for (int i = 0; i < n; i++) {
         chunk = message.Substring(rate * i, rate);
         chunk.Append(zeroes);
         State.Bitstring.Xor(chunk);
         Function();
      }
   }

   protected abstract void Function();

   protected abstract Bitstring GetPadding(int r, int m);

   protected virtual byte[] Squeeze(int outputLength) {
      int rate = State.Rate;
      Bitstring q = new Bitstring();
      while (true) {
         q.Append(State.Bitstring.Truncate(rate));
         if (q.Length >= outputLength) {
            return (q.Length == outputLength) ? 
                    q.Bytes : q.Truncate(outputLength).Bytes;
         }
         Function();
      }
   }

   protected virtual Bitstring Suffix() {
      return new Bitstring();
   }
}

关键点在这里

  • 该类是 abstract 的。没有定义默认的置换和填充规则，因此子类将负责实现它们。
  • Absorb、Squeeze 和 Suffix 方法分别提供了吸收、挤压和后缀阶段的默认实现。但是，它们被标记为 virtual，因此子类可以覆盖此行为。

KECCAK-p[b,nr] 置换

KECCAK-p[b,nr] 置换是一族置换函数。它们都使用 pad10*1[2] 填充规则，该规则在输入 bitstring 的末尾添加一个 1，然后根据需要添加任意数量的 0，最后再添加一个 1，使得总长度是海绵结构速率的倍数。它们的正式定义可以在 FIPS PUB 202 - 第 7 页 - 3. KECCAK-p 置换 中找到。

KECCAK-p[b,nr] 置换的特点是

  • 它将置换的位数（bitstring 的长度）(b)。
  • 单次置换的内部迭代次数 (nr)。

在所提出的解决方案中，KECCAK-p[b,nr] 置换在 KeccakPermutation 类中实现，该类继承自 SpongeConstruction 类。

public class KeccakPermutation : SpongeConstruction
{
   private readonly int _roundCount;

   public int RoundCount { get { return _roundCount; } }

   protected KeccakPermutation(SpongeSize size, int rate, int roundCount)
      : base(size, rate) {
      _roundCount = roundCount;
   }

   protected override void Function() {
      int start = 12 + (State.Size.L << 1);
      for (int round = start - _roundCount; round < start; round++) {
         Iota(Khi(Pi(Rho(Theta(State)))), round);
      }
   }
}

步进映射

KECCAK 置换算法[3]是连续应用五个核心置换，称为**步进映射**[4]：**θ** (theta)、**ρ** (rho)、**π** (pi)、**χ** (khi) 和 **ι** (iota)。在这五个步进映射中，只有最后一个（iota）真正关心 round 参数。

θ Theta 对状态的每个位与两个相邻列的奇偶校验进行 XOR 运算[5]。
  
public static SpongeState Theta(SpongeState state) {
   int w = state.Size.W;
   bool[,] c = new bool[5, w];
   for (int x = 0; x < 5; x++) {
      for (int z = 0; z < w; z++) {
         c[x, z] = state.GetColumn(x, z).GetBits()
            .Aggregate((bool lhs, bool rhs) => { return lhs ^ rhs; });
      }
   }
   bool[,] d = new bool[5, w];
   for (int x = 0; x < 5; x++) {
      for (int z = 0; z < w; z++) {
         d[x, z] = c[Bin.Mod(x - 1, 5), z] ^ c[Bin.Mod(x + 1, 5), 
                     Bin.Mod(z - 1, w)];
      }
   }
   for (int x = 0; x < 5; x++) {
      for (int z = 0; z < w; z++) {
         bool bit = d[x, z];
         for (int y = 0; y < 5; y++) {
            state[x, y, z] ^= bit;
         }
      }
   }
   return state;
}
ρ Rho 对状态的二十五个道中的每个道执行旋转，该旋转取决于该道的 x 和 y 坐标[6]。
  
public static SpongeState Rho(SpongeState state) {
   SpongeState newState = new SpongeState(state.Size, state.Rate);
   int w = state.Size.W;
   newState.SetLane(newState.GetLane(0, 0), state.GetLane(0, 0).GetBits());
   int x = 1;
   int y = 0;
   int u, oldX;
   for (int t = 0; t < 24; t++) {
      u = ((t + 1) * (t + 2)) >> 1;
      for (int z = 0; z < w; z++) {
         newState[x, y, z] = state[x, y, Bin.Mod(z - u, w)];
      }
      oldX = x;
      x = y;
      y = Bin.Mod(2 * oldX + 3 * y, 5);
   }
   state.SetBitstring(newState.Bitstring);
   return state;
}
π Pi 重新排列了状态的道[7]。
  
public static SpongeState Pi(SpongeState state) {
   SpongeState newState = new SpongeState(state.Size, state.Rate);
   int w = state.Size.W;
   for (int y = 0; y < 5; y++) {
      for (int x = 0; x < 5; x++) {
         for (int z = 0; z < w; z++) {
            newState[x, y, z] = state[Bin.Mod(x + 3 * y, 5), x, z];
         }
      }
   }
   state.SetBitstring(newState.Bitstring);
   return state;
}
χ Khi 对状态中的每个位与其行中另外两个位的非线性函数进行异或运算[8]。
  
public static SpongeState Khi(SpongeState state) {
   SpongeState newState = new SpongeState(state.Size, state.Rate);
   int w = state.Size.W;
   for (int y = 0; y < 5; y++) {
      for (int x = 0; x < 5; x++) {
         for (int z = 0; z < w; z++) {
            newState[x, y, z] = state[x, y, z]
               ^ ((state[Bin.Mod(x + 1, 5), y, z] ^ true) && 
                   state[Bin.Mod(x + 2, 5), y, z]);
         }
      }
   }
   state.SetBitstring(newState.Bitstring);
   return state;
}
ι Iota 只影响第一个道（即位于海绵结构中心的道），并且根据轮次号以一种依赖于轮次号的方式对其进行修改[9]。RoundConstant 方法的结果仅取决于传入的整数参数，因此可以对其进行缓存。为此使用了一个 Dictionary<int, bool>。此外，此方法包含一个多次调用 RoundConstant 方法的循环，其结果取决于两个参数：传递给 Iota 方法的 round 参数，以及提供给 RoundConstant 方法的 t 参数。为了使用字典，定义了一个私有 RoundT 结构体，快速实现了 IEquatable<RoundT> 接口。
  
public static SpongeState Iota(SpongeState state, int round) {
   int w = state.Size.W;
   int l = state.Size.L;
   Bitstring rc = Bitstring.Zeroes(w);
   RoundT roundT;
   int t;
   int rnd = 7 * round;
   for (int j = 0; j <= l; j++) {
      t = j + rnd;
      roundT = new RoundT(round, t);
      if (!_roundTConstants.ContainsKey(roundT)) {
         _roundTConstants.Add(roundT, RoundConstant(t));
      }
      rc[(1 << j) - 1] = _roundTConstants[roundT];
   }
   state.XorLane(state.GetLane(0, 0), rc.GetBits());
   return state;
}

private static readonly Dictionary<int, bool> _roundConstants = 
                                              new Dictionary<int, bool> {
   { 0, true }
};
private static readonly Dictionary<RoundT, bool> _roundTConstants = 
                                                 new Dictionary<RoundT, bool>();

private struct RoundT : IEquatable<RoundT>
{
   public readonly int Round;
   public readonly int T;

   public RoundT(int round, int t) {
      Round = round;
      T = t;
   }

   public bool Equals(RoundT other) {
      return (Round == other.Round) && (T == other.T);
   }

   public override bool Equals(object obj) {
      return (obj is RoundT) && Equals((RoundT)obj);
   }

   public override int GetHashCode() {
      return HashCoder<int>.Boost.Compute(RoundT, T);
   }

   public static bool operator ==(RoundT lhs, RoundT rhs) {
      return lhs.Equals(rhs);
   }

   public static bool operator !=(RoundT lhs, RoundT rhs) {
      return !lhs.Equals(rhs);
   }
}

private static bool RoundConstant(int t) {
   t = Bin.Mod(t, 255);
   if (_roundConstants.ContainsKey(t)) {
      return _roundConstants[t];
   }
   Bitstring r = new Bitstring("10000000", 8);
   for (int i = 0; i < t; i++) {
      r.Prepend(Bitstring.Zero);
      r[0] ^= r[8];
      r[4] ^= r[8];
      r[5] ^= r[8];
      r[6] ^= r[8];
      r = r.Truncate(8);
   }
   bool bit = r[0];
   _roundConstants.Add(t, bit);
   return bit;
}
KECCAK-p 置换步骤映射的影响

KeccakPermutation 类还重写了 GetPadding 方法并提供了 pad10*1[2] 填充规则。

protected override Bitstring GetPadding(int r, int m) {
   int j = Bin.Mod(-m - 2, r);
   Bitstring pad = new Bitstring(j + 2);
   pad[0] = true;
   pad[pad.Length - 1] = true;
   return pad;
}

KECCAK-f 置换

KECCAK-f 置换是 KECCAK-p 置换的特化，用于单次迭代的轮数 (nr) 等于 12 + 2l[10] 的情况。

形式上，KECCAK-f[b] 置换是一个 KECCAK-p[b, 12 + 2l] 置换。

它在 KeccakFunction 类中实现，作为 KeccakPermutation 类的子类，提供七种可能的尺寸作为 static 方法。

public class KeccakFunction : KeccakPermutation
{
   protected KeccakFunction(SpongeSize size, int rate)
      : base(size, rate, 12 + (size.L << 1)) { }

   public static KeccakFunction F25(int rate) {
      return new KeccakFunction(SpongeSize.W01, rate);
   }

   public static KeccakFunction F50(int rate) {
      return new KeccakFunction(SpongeSize.W02, rate);
   }

   public static KeccakFunction F100(int rate) {
      return new KeccakFunction(SpongeSize.W04, rate);
   }

   public static KeccakFunction F200(int rate) {
      return new KeccakFunction(SpongeSize.W08, rate);
   }

   public static KeccakFunction F400(int rate) {
      return new KeccakFunction(SpongeSize.W16, rate);
   }

   public static KeccakFunction F800(int rate) {
      return new KeccakFunction(SpongeSize.W32, rate);
   }

   public static KeccakFunction F1600(int rate) {
      return new KeccakFunction(SpongeSize.W64, rate);
   }
}

KECCAK[c] 置换

KECCAK[c] 置换是 KECCAK-f 置换的限制，其条件是 b 等于 1600。在这种情况下，置换由 c，即海绵状态的容量定义。因此，KECCAK[c] 置换是一个 KECCAK-p[b,nr] 置换，其中 b 等于 1600，nr = 12 + 2l，速率等于 1600 - c，并且使用 pad10*1 作为填充规则。

它在 Keccak 类中实现，该类继承自 KeccakFunction 类，并提供了四种最常见的实例，用于容量为 448、512、768 和 1024 位的函数。请注意，对于特定函数，容量是所需输出长度的两倍（448 用于 224 位输出，512 用于 256 位输出等）。

public class Keccak : KeccakFunction
{
   protected Keccak(int capacity)
      : base(SpongeSize.W64, 1600 - capacity) { }

   public static Keccak Keccak224() {
      return new Keccak(448);
   }

   public static Keccak Keccak256() {
      return new Keccak(512);
   }

   public static Keccak Keccak384() {
      return new Keccak(768);
   }

   public static Keccak Keccak512() {
      return new Keccak(1024);
   }
}

SHA-3 散列函数和 SHAKE 可扩展输出函数

基于 KECCAK[c] 置换，定义了八个函数

  • 四种 SHA-3 散列函数 SHA3-224、SHA3-256、SHA3-384 和 SHA3-512（分别具有 224、256、384 和 512 位的输出长度）。这些函数使用 "01" 后缀。
    函数 输出长度 容量 速率
    位 字节 位 字节 位 字节
    SHA3-224 224 28 448 56 1152 144
    SHA3-256 256 32 512 64 1088 136
    SHA3-384 384 48 768 96 832 104
    SHA3-512 512 64 1024 128 576 72
    SHA-3 散列函数
    public sealed class Sha3Permutation : Keccak
{
   public int Width {
      get { return Capacity >> 1; }
   }

   private Sha3Permutation(int capacity)
      : base(capacity) { }

   public static Sha3Permutation Sha3_224() {
      return new Sha3Permutation(448);
   }

   public static Sha3Permutation Sha3_256() {
      return new Sha3Permutation(512);
   }

   public static Sha3Permutation Sha3_384() {
      return new Sha3Permutation(768);
   }

   public static Sha3Permutation Sha3_512() {
      return new Sha3Permutation(1024);
   }

   protected override Bitstring Suffix() {
      return new Bitstring("01");
   }
}
  • 四种可扩展输出函数 RawSHAKE128、RawSHAKE256、SHAKE128 和 SHAKE256。可扩展输出函数（XOF）与散列函数不同，它们可以产生无限长度的输出。此功能由 SpongeConstruction.Squeeze 方法管理。
    函数 容量 速率
    位 字节 位 字节
    RawSHAKE128 256 32 1344 168
    RawSHAKE256 512 64 1088 136
    SHAKE128 256 32 1344 168
    SHAKE256 512 64 1088 136
    SHAKE 可扩展输出函数

    SHAKE 和 RawSHAKE XOF 仅在它们在填充输入 bitstring 之前附加的后缀上有所不同：RawSHAKE 使用 "11" 后缀，而 SHAKE 使用 "1111" 后缀。

    public sealed class RawShakePermutation : Keccak
{
   private RawShakePermutation(int capacity)
      : base(capacity) { }

   public static RawShakePermutation RawShake128() {
      return new RawShakePermutation(256);
   }

   public static RawShakePermutation RawShake256() {
      return new RawShakePermutation(512);
   }

   protected override Bitstring Suffix() {
      return new Bitstring("11");
   }
}

public sealed class ShakePermutation : Keccak
{
   private ShakePermutation(int capacity)
      : base(capacity) { }

   public static ShakePermutation Shake128() {
      return new ShakePermutation(256);
   }

   public static ShakePermutation Shake256() {
      return new ShakePermutation(512);
   }

   protected override Bitstring Suffix() {
      return new Bitstring("1111");
   }
}

我们现在有了散列和可扩展输出函数的基本实现。让我们做一些快速测试，看看它们是否按预期工作。

测试函数

为了测试此实现是否符合标准，NIST 提供了大量固定长度位字符串的基本测试，网址为 NIST - 密码学标准和指南 / 带有中间值的示例 / 安全哈希 / FIPS 202 - SHA-3 标准：基于置换的哈希和可扩展输出函数[^]。它们提供了针对四种 SHA-3 哈希函数以及 SHAKE128 和 SHAKE256 XOF 的特定宽度（0、5、30、1600、1605 和 1630 位）消息的预期值。我没有找到 RawSHAKE128 和 RawSHAKE256 XOF 的任何示例文件。

internal class Program
{
   private static readonly Bitstring _message0000 = new Bitstring();

   private static void Main(string[] args) {
      Sha3Test();
      Exit();
   }

   private static void Sha3Test() {
      Sha3Permutation sha3 = Sha3Permutation.Sha3_224;
      Output(sha3, "SHA3-224 sample of 0-bit message", _message0000, 224);
      sha3 = Sha3Permutation.Sha3_256;
      Output(sha3, "SHA3-256 sample of 0-bit message", _message0000, 256);
      sha3 = Sha3Permutation.Sha3_384;
      Output(sha3, "SHA3-384 sample of 0-bit message", _message0000, 384);
      sha3 = Sha3Permutation.Sha3_512;
      Output(sha3, "SHA3-512 sample of 0-bit message", _message0000, 512);
   }

   private void Output(SpongeConstruction sponge, 
           string caption, Bitstring bitstring, int outputLength) {
      Console.WriteLine(caption);
      Stopwatch stopwatch = Stopwatch.StartNew();
      Bitstring b = new Bitstring(sponge.Process
                    (bitstring.Bytes, outputLength, bitstring.Length));
      Console.WriteLine($"{b.ToHexString(false, false)} 
                       ({stopwatch.ElapsedMilliseconds}ms)");
      Console.WriteLine();
   }

   private static void Exit() {
      Console.Write("Press a key to exit...");
      Console.ReadKey(true);
   }
}

我不在这里展示全部三十六个测试。上面这个片段（在发布模式下）生成的内容如下：

所有测试实际上都产生了预期值。

SHA-3 置换作为散列算法

现在，我们对生成的结果有了一定的信心，我们可能希望将此 SHA-3 置换实现集成到 .NET HashAlgorithm 基础设施中，不是吗？这至少需要重写 Initialize、HashCore 和 HashFinal 方法。

public sealed class Sha3HashAlgorithm : HashAlgorithm
{
   public enum Size : byte
   {
      Bits224,
      Bits256,
      Bits384,
      Bits512
   }

   private readonly Sha3Permutation _permutation;

   private Bitstring _hash;

   public Sha3HashAlgorithm(Size size)
      : base() {
      switch (size) {
         case Size.Bits224:
            _permutation = Sha3Permutation.Sha3_224();
            break;
         case Size.Bits256:
            _permutation = Sha3Permutation.Sha3_256();
            break;
         case Size.Bits384:
            _permutation = Sha3Permutation.Sha3_384();
            break;
         case Size.Bits512:
            _permutation = Sha3Permutation.Sha3_512();
            break;
      }
   }

   public override void Initialize() {
      _hash = new Bitstring();
   }

   protected override void HashCore(byte[] array, int ibStart, int cbSize) {
      byte[] data = new byte[cbSize];
      Array.Copy(array, ibStart, data, 0, cbSize);
      _hash.Append(data);
   }

   protected override byte[] HashFinal() {
      _hash = _permutation.Process(_hash, _permutation.Width);
      return _hash?.Bytes ?? new byte[0];
   }
}

实际实现可能未经优化，因为它需要在运行哈希函数之前将所有输入数据加载到内存中。

从性能角度来看，对于短输入（几千位），哈希操作需要几毫秒（参见上图）。但是，对于更大的输入，这可能是一个问题；例如，仍然在发布模式下，我的计算机上对八百万位（8Mb = 1MB）的输入消息进行 SHA3-224 哈希操作大约需要 41 秒。如果您打算对大文件执行 SHA-3 哈希操作，Keccak 团队本身提供了 [^] C 实现，这可能更合适。如果您只是打算哈希小输入（如密码），本文提出的 C# 实现就足够了。无论如何，本文的目标是向您介绍海绵结构，而不是提供一个通用且高度优化的实现。

链接

致谢

  • 海绵结构，以及包括 KECCAK-p 置换在内的所有密码海绵函数，都是 Guido Bertoni、Joan Daemen、Michaël Peeters 和 Gilles Van Assche 的原创和卓越之作。
  • 除海绵结构图外，所有图片均为自制。
  • 海绵结构图来自 common.wikimedia.org。

参考文献

  1. 密码海绵函数 - 第 11 页 - 2.1.1 位字符串
  2. KECCAK 参考 - 第 7 页 - 1.1.2 填充规则
  3. FIPS PUB 202 - 第 16 页 - 3.3 KECCAK-p[b,nr]
  4. FIPS PUB 202 - 第 11 页 - 3.2 步骤映射
  5. FIPS PUB 202 - 第 11 页 - 3.2.1 θ 的规范
  6. FIPS PUB 202 - 第 12 页 - 3.2.2 ρ 的规范
  7. FIPS PUB 202 - 第 14 页 - 3.2.3 π 的规范
  8. FIPS PUB 202 - 第 15 页 - 3.2.4 χ 的规范
  9. FIPS PUB 202 - 第 15 页 - 3.2.5 ι 的规范
  10. FIPS PUB 202 - 第 17 页 - 3.4 与 KECCAK-f 的比较

历史

  • 2018 年 1 月 28 日：版本 1.0.0.0 - 首次发布
© . All rights reserved.