Lib.rs

gf256

一个包含Galois-field类型和工具的Rust库，当可用时利用硬件指令。

这个项目最初是一个学习项目，目的是在看到Galois-field东西在太多主题中出现后，更多地了解这些内容。所以这个crate可能更具有教育意义而不是实用性。

use ::gf256::*;

let a = gf256(0xfd);
let b = gf256(0xfe);
let c = gf256(0xff);
assert_eq!(a*(b+c), a*b + a*c);

如果你，像我一样，对学习更多关于Galois-field迷人功能的细节感兴趣，请查看gf256模块的文档。我已经尝试全面地捕捉我所学的知识，希望为更深入地了解这个有用的数学领域提供了一个不错的入门点。

我还想指出，每个模块中的Rust示例都是完全功能性的，并在CI中通过Rust的doctest runner进行了测试。请随意复制并修改它们以查看会发生什么。

• p - 多项式类型
• gf - Galois-field类型
• lfsr - LFSR结构
• crc - CRC函数
• shamir - Shamir秘密共享函数
• raid - RAID奇偶校验函数
• rs - Reed-Solomon错误纠正函数

使用gf256的Reed-Solomon错误纠正

                      ..:::::::::::...                  .:::....:::.:.:.'':.'.:.'::: :   :' ''  '''
                   .:::::::::::::::::::..               ::::::::::::  .:....'.. '.:...  :' :'':': .'
                 .::::::::::::::::::::::::.             ::::::::::' . :..:..:' : '.':::  :.':'' '  :
               .:::::::::::::::::::::::::::.         . ::::::::::   :: '::' .: '' ''. : :: .:..::. '
              .::::::::::::::::::::::::::::::    ... :: :'::::::'   ::':. ':' .: '.:'::'::: ': '...:
              :::::::::::::::::::::::::::::'' .. '::: '     '''     ''..:.:'.''::.   .:.' .'': '. .:
             :::::::::::::::::::::::::::''..::::: '                  : .: .'. :  :::.'.:':.:':: .. :
             :::::::::::::::::::::::'' ..:::::''                    ' :... .': ::.''':' .''. . '  ..
             :::::::::::::::::::'' ..:::::'' .                       : :..':::.:. : .:' :.   .':'.':
         ..: ::::::::::::::''' ..:::::'' ..:::                      :' . :.' .'.'::. ' ::' ':  .:.
      ..:::'  :::::::::'' ..::::::'' ..:::::::                      :' .  '.'::'.:  : .:'' .:.'.:::'
     :::'     ':::'' ...::::::''...::::::::::                        '' ' .'::...' :':...':.. . .' :
    ::'         ...::::::'' ..:::::::::::::'                        . .. ' .:::.'':::.  .':''':::...
         ....:::::::'' ..:::::::::::::::::'                         : '.'  .': :. .:.': . .'  .  ::'
    '::::::::'''    :::::::::::::::::::''                            '.. .: ::: ': ::'::. ' '.': : '
                      '':::::::::::'''                              .:.':.. '''.  : : ':'':.': '.:':

什么是Galois-field？

Galois-field，也称为有限域，是一组“数字”（对于某些数字的定义），可以在其上进行“数学”操作（对于某些数学的定义）的有限集合。

更具体地说，Galois-field支持加法、减法、乘法和除法，这些操作遵循一组称为“域公理”的规则

1. 减法是加法的逆运算，除法是乘法的逆运算

   # use ::gf256::*;
   #
   # let a = gf256(1);
   # let b = gf256(2);
   assert_eq!((a+b)-b, a);
   assert_eq!((a*b)/b, a);
   

   除数不是 0 时，除法是未定义的

   # use ::gf256::*;
   #
   # let a = gf256(1);
   assert_eq!(a.checked_div(gf256(0)), None);
   

2. 存在一个元素 0，它是加法的单位元，还有一个元素 1，它是乘法的单位元。

   # use ::gf256::*;
   #
   # let a = gf256(1);
   assert_eq!(a + gf256(0), a);
   assert_eq!(a * gf256(1), a);
   

3. 加法和乘法具有结合性。

   # use ::gf256::*;
   #
   # let a = gf256(1);
   # let b = gf256(2);
   # let c = gf256(3);
   assert_eq!(a+(b+c), (a+b)+c);
   assert_eq!(a*(b*c), (a*b)*c);
   

4. 加法和乘法具有交换性。

   # use ::gf256::*;
   #
   # let a = gf256(1);
   # let b = gf256(2);
   assert_eq!(a+b, b+a);
   assert_eq!(a*b, b*a);
   

5. 乘法对加法具有分配性。

   # use ::gf256::*;
   #
   # let a = gf256(1);
   # let b = gf256(2);
   # let c = gf256(3);
   assert_eq!(a*(b+c), a*b + a*c);
   

请注意，这并不是您平常的整数运算！在伽罗瓦域中定义的运算满足上述规则，但它们可能会有不直观的结果。

# use ::gf256::*;
#
assert_eq!(gf256(1) + gf256(1), gf256(0));

这也意味着并非所有的数学在伽罗瓦域中都能工作。

# use ::gf256::*;
#
# let a = gf256(1);
assert_ne!(a + a, gf256(2)*a);

有限域可以非常有助于将高级数学应用于机器字，因为机器字（如 u8、u16、u32 等）本质上是有限的。通常我们只是忽略这一点，直到发生整数溢出，然后我们只是挥舞着双手，哭喊着说数学失败了。

在 Rust 中，这有一个有趣的影响，即伽罗瓦域类型无法溢出，因此伽罗瓦域类型不需要其他 Rust 类型中通常找到的溢出操作集。

# use ::gf256::*;
#
let a = (u8::MAX).checked_add(1);  // overflows          :(
let b = gf256(u8::MAX) + gf256(1); // does not overflow  :)

有关伽罗瓦域及其构建方法的更多信息，请参阅 gf 的模块级文档。

包含在 gf256 中

gf256 包含的不仅仅是伽罗瓦域类型。它还包含许多依赖于有限域数学的其他实用工具。

• 多项式类型

  use ::gf256::*;
  
  let a = p32(0x1234);
  let b = p32(0x5678);
  assert_eq!(a+b, p32(0x444c));
  assert_eq!(a*b, p32(0x05c58160));
  

• 伽罗瓦域类型

  use ::gf256::*;
  
  let a = gf256(0xfd);
  let b = gf256(0xfe);
  let c = gf256(0xff);
  assert_eq!(a*(b+c), a*b + a*c);
  

• LFSR 结构（需要特性 lfsr）

  use gf256::lfsr::Lfsr16;
  
  let mut lfsr = Lfsr16::new(1);
  assert_eq!(lfsr.next(16), 0x0001);
  assert_eq!(lfsr.next(16), 0x002d);
  assert_eq!(lfsr.next(16), 0x0451);
  assert_eq!(lfsr.next(16), 0xbdad);
  assert_eq!(lfsr.prev(16), 0xbdad);
  assert_eq!(lfsr.prev(16), 0x0451);
  assert_eq!(lfsr.prev(16), 0x002d);
  assert_eq!(lfsr.prev(16), 0x0001);
  

• CRC 函数（需要特性 crc）

  use gf256::crc::crc32c;
  
  assert_eq!(crc32c(b"Hello World!", 0), 0xfe6cf1dc);
  

• Shamir 秘密共享函数（需要特性 shamir 和 thread-rng）

  use gf256::shamir::shamir;
  
  // generate shares
  let shares = shamir::generate(b"secret secret secret!", 5, 4);
  
  // <4 can't reconstruct secret
  assert_ne!(shamir::reconstruct(&shares[..1]), b"secret secret secret!");
  assert_ne!(shamir::reconstruct(&shares[..2]), b"secret secret secret!");
  assert_ne!(shamir::reconstruct(&shares[..3]), b"secret secret secret!");
  
  // >=4 can reconstruct secret
  assert_eq!(shamir::reconstruct(&shares[..4]), b"secret secret secret!");
  assert_eq!(shamir::reconstruct(&shares[..5]), b"secret secret secret!");
  

• RAID 奇偶校验函数（需要特性 raid）

  use gf256::raid::raid7;
  
  // format
  let mut buf = b"Hello World!".to_vec();
  let mut parity1 = vec![0u8; 4];
  let mut parity2 = vec![0u8; 4];
  let mut parity3 = vec![0u8; 4];
  let slices = buf.chunks(4).collect::<Vec<_>>();
  raid7::format(&slices, &mut parity1, &mut parity2, &mut parity3);
  
  // corrupt
  buf[0..8].fill(b'x');
  
  // repair
  let mut slices = buf.chunks_mut(4).collect::<Vec<_>>();
  raid7::repair(&mut slices, &mut parity1, &mut parity2, &mut parity3, &[0, 1]);
  assert_eq!(&buf, b"Hello World!");
  

• Reed-Solomon 错误纠正函数（需要特性 rs）

  use gf256::rs::rs255w223;
  
  // encode
  let mut buf = b"Hello World!".to_vec();
  buf.resize(buf.len()+32, 0u8);
  rs255w223::encode(&mut buf);
  
  // corrupt
  buf[0..16].fill(b'x');
  
  // correct
  rs255w223::correct_errors(&mut buf)?;
  assert_eq!(&buf[0..12], b"Hello World!");
  # Ok::<(), rs255w223::Error>(())
  

由于这种数学依赖于一些相当任意的常数，因此这些实用工具都既作为正常 Rust API 提供，使用合理的默认值定义，也作为高度可配置的 proc_macro 提供。

# pub use ::gf256::*;
use gf256::gf::gf;

#[gf(polynomial=0x11b, generator=0x3)]
type gf256_rijndael;

# fn main() {
let a = gf256_rijndael(0xfd);
let b = gf256_rijndael(0xfe);
let c = gf256_rijndael(0xff);
assert_eq!(a*(b+c), a*b + a*c);
# }

硬件支持

大多数现代 64 位硬件都包含加速此类数学的指令。这通常以 无进位乘法 指令的形式出现。

无进位乘法，也称为多项式乘法和异或乘法，是异或的乘法类似物。在传统乘法中，可以通过一系列移位和加法来实现，而无进位乘法可以通过一系列移位和异或来实现。

Multiplication:

1011 * 1101 =  1011
            +   1011
            +     1011
            ----------
            = 10001111

Carry-less multiplication:

1011 * 1101 =  1011
            ^   1011
            ^     1011
            ----------
            = 01111111

在 x86_64 上，64 位无进位乘法可通过 pclmulqdq 指令获得，在 aarch64 上，可通过稍微简短的 pmull 指令获得。

gf256 在可能的情况下会利用这些指令。但是，在撰写本文时，Rust 中的 pmull 支持仅在 nightly 版本中可用。

# use ::gf256::*;
#
// uses carry-less multiplication instructions if available
let a = p32(0b1011);
let b = p32(0b1101);
assert_eq!(a * b, p32(0b01111111));

gf256 还公开了 HAS_XMUL 标志，可以根据是否可用硬件加速的无进位乘法来选择算法。

# use gf256::p::p32;
#
let a = p32(0b1011);
let b = if gf256::HAS_XMUL {
    a * p32(0b11)
} else {
    (a << 1) ^ a
};

gf256 也利用了硬件加速的无进位加法指令，有时称为多项式加法，或简单地称为异或。但这并不那么引人注目。

const fn 支持

由于使用了特性和内建函数，无法在 const fns 中使用多项式/伽罗瓦域算子。

作为一种替代方案，gf256 提供了一组“原始”函数，它们提供了效率较低、更原始的实现，可以在 const fns 中使用。

这对于在编译时计算复杂的常量非常有用，这在这类算法中很常见。

# use ::gf256::*;
#
const POLYNOMIAL: p64 = p64(0x104c11db7);
const CRC_TABLE: [u32; 256] = {
    let mut table = [0; 256];
    let mut i = 0;
    while i < table.len() {
        let x = (i as u32).reverse_bits();
        let x = p64((x as u64) << 8).naive_rem(POLYNOMIAL).0 as u32;
        table[i] = x.reverse_bits();
        i += 1;
    }
    table
};

no_std 支持

gf256 只是一堆数学，所以它主要是 no_std 兼容的。

例外的是额外的工具 rs 和 shamir，它们目前需要 alloc。

恒等时间

gf256 为某些有用的操作提供了“尽力而为”的恒等时间实现。尽管如此，应该强调这是一个主要的教育项目，因此在使用之前，应该外部评估恒等时间属性，并且您使用此库存在风险。

• 多项式乘法

  gf256 中的多项式乘法应该是恒等时间的。

  假设任何硬件加速的无进位乘法指令在固定数量的周期内完成，这通常是正确的。

  如果无进位乘法指令不可用，则使用无分支循环实现的无进位乘法。

• 伽罗瓦域操作

  在 barret 模式下，barret 中的伽罗瓦域类型仅依赖于无进位乘法和异或，并且应该始终在恒等时间内执行。

  由于使用了查找表，其他伽罗瓦域实现不是恒等时间的，这可能容易受到缓存时间攻击。请注意，默认的伽罗瓦域类型可能使用基于表的实施方式。

  如果您想进行恒等时间的有限域操作，则需要使用 barret 模式声明自定义伽罗瓦域类型。

  # pub use ::gf256::*;
  use gf256::gf::gf;
  
  #[gf(polynomial=0x11b, generator=0x3, barret)]
  type gf256_rijndael;
  #
  # fn main() {}
  

• Shamir 秘密共享

  默认的 Shamir 秘密共享实现内部使用 barret 模式下的自定义伽罗瓦域类型，并且应该是恒等时间的（关键词 应该）。

特性

• no-xmul - 禁用无进位乘法指令，强制使用原始位操作实现

  这主要用于测试/基准测试目的。

• no-tables - 禁用查找表，仅依赖于硬件指令或原始实现

  这可能有助于内存受限的设备。

• small-tables - 将查找表限制为“小表”，具有 <=16 个元素的表

  这提供了在完整 256 字节表和无表之间的折衷方案，可能在内存受限的设备上很有用。

• thread-rng - 启用依赖于 ThreadRng 的功能

  请注意，这需要 std

  这用于为 Shamir 的秘密共享实现提供默认的 Rng 实现

• lfsr - 使 LFSR 结构和宏可用

• crc - 使 CRC 函数和宏可用

• shamir - 使 Shamir 秘密共享函数和宏可用

  请注意，这需要 alloc 和 rand

  您还可以启用 thread-rng 特性，这对于默认 rng 是必需的

• raid - 使 RAID-奇偶校验函数和宏可用

• rs - 使 Reed-Solomon 函数和宏可用

  注意，这需要 alloc

测试

gf256 包含了一些用 Rust 的 测试运行器 实现的测试，可以使用 make 运行

make test

此外，这些文档中的所有代码示例都可以使用 Rust 的 doctest 运行器 运行

make docs

基准测试

gf256 还包含了一些在 Criterion 中实现的基准测试。这些用于确定最佳默认实现，并可以使用 make 运行

make bench

基准测试结果的完整总结可以在 BENCHMARKS.md 中找到。