Lib.rs

gf256

包含伽罗瓦域类型和工具的Rust库，当可用时利用硬件指令。

这个项目最初是一个学习项目，旨在在看到伽罗瓦域在各种主题中频繁出现后，更多地了解这些“伽罗瓦域事物”。因此，这个crate可能更具有教育意义，而不是实用性。

use ::gf256::*;

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

如果您像我一样，对了解伽罗瓦域的迷人功能感兴趣，请查看gf256模块的文档。我已经尽力全面地记录我所学到的知识，希望为更深入地了解这个有用的数学领域提供良好的切入点。

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

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

使用gf256进行Reed-Solomon错误校正

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

什么是伽罗瓦域？

伽罗瓦域，也称为有限域，是一组“数”（对于某种数的定义），您可以在其上进行“数学”运算（对于某种数学的定义）的有限集。

更具体地说，伽罗瓦域支持加法、减法、乘法和除法，这些运算遵循一组称为“域公理”的规则

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

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

   除法在除以0时未定义（除了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中找到。