3 releases (breaking)
0.3.0  May 9, 2022 

0.2.0  Dec 17, 2021 
0.1.0  Nov 8, 2021 
#429 in Algorithms
364 downloads per month
Used in msecret
615KB
11K
SLoC
gf256
A Rust library containing Galoisfield types and utilities, leveraging hardware instructions when available.
This project started as a learning project to learn more about these "Galoisfield thingies" after seeing them pop up in far too many subjects. So this crate may be more educational than practical.
use ::gf256::*;
let a = gf256(0xfd);
let b = gf256(0xfe);
let c = gf256(0xff);
assert_eq!(a*(b+c), a*b + a*c);
If you, like me, are interested in learning more about the fascinating utility of Galoisfields, take a look at the documentation of gf256's modules. I've tried to comprehensively capture what I've learned, hopefully provided a decent entry point into learning more about this useful field of math.
I also want to point out that the Rust examples in each module are completely functional and tested in CI thanks to Rust's doctest runner. Feel free to copy and tweak them to see what happens.
 p  Polynomial types
 gf  Galoisfield types
 lfsr  LFSR structs
 crc  CRC functions
 shamir  Shamir secretsharing functions
 raid  RAIDparity functions
 rs  ReedSolomon errorcorrection functions
ReedSolomon errorcorrection using gf256
..:::::::::::... .:::....:::.:.:.'':.'.:.'::: : :' '' '''
.:::::::::::::::::::.. :::::::::::: .:....'.. '.:... :' :'':': .'
.::::::::::::::::::::::::. ::::::::::' . :..:..:' : '.'::: :.':'' ' :
.:::::::::::::::::::::::::::. . :::::::::: :: '::' .: '' ''. : :: .:..::. '
.:::::::::::::::::::::::::::::: ... :: :'::::::' ::':. ':' .: '.:'::'::: ': '...:
:::::::::::::::::::::::::::::'' .. '::: ' ''' ''..:.:'.''::. .:.' .'': '. .:
:::::::::::::::::::::::::::''..::::: ' : .: .'. : :::.'.:':.:':: .. :
:::::::::::::::::::::::'' ..:::::'' ' :... .': ::.''':' .''. . ' ..
:::::::::::::::::::'' ..:::::'' . : :..':::.:. : .:' :. .':'.':
..: ::::::::::::::''' ..:::::'' ..::: :' . :.' .'.'::. ' ::' ': .:.
..:::' :::::::::'' ..::::::'' ..::::::: :' . '.'::'.: : .:'' .:.'.:::'
:::' ':::'' ...::::::''...:::::::::: '' ' .'::...' :':...':.. . .' :
::' ...::::::'' ..:::::::::::::' . .. ' .:::.'':::. .':''':::...
....:::::::'' ..:::::::::::::::::' : '.' .': :. .:.': . .' . ::'
'::::::::''' :::::::::::::::::::'' '.. .: ::: ': ::'::. ' '.': : '
'':::::::::::''' .:.':.. '''. : : ':'':.': '.:':
What are Galoisfields?
Galoisfields, also called finitefields, are a finite set of "numbers" (for some definition of number), that you can do "math" on (for some definition of math).
More specifically, Galoisfields support addition, subtraction, multiplication, and division, which follow a set of rules called "field axioms":

Subtraction is the inverse of addition, and division is the inverse of multiplication:
# assert_eq!((a+b)b, a); assert_eq!((a*b)/b, a);
Except for
0
, over which division is undefined:# assert_eq!(a.checked_div(gf256(0)), None);

There exists an element
0
that is the identity of addition, and an element1
that is the identity of multiplication:# assert_eq!(a + gf256(0), a); assert_eq!(a * gf256(1), a);

Addition and multiplication are associative:
# assert_eq!(a+(b+c), (a+b)+c); assert_eq!(a*(b*c), (a*b)*c);

Addition and multiplication are commutative:
# assert_eq!(a+b, b+a); assert_eq!(a*b, b*a);

Multiplication is distributive over addition:
# assert_eq!(a*(b+c), a*b + a*c);
Keep in mind these aren't your normal integer operations! The operations defined in a Galoisfield types satisfy the above rules, but they may have unintuitive results:
#
assert_eq!(gf256(1) + gf256(1), gf256(0));
This also means not all of math works in a Galoisfield:
#
assert_ne!(a + a, gf256(2)*a);
Finitefields can be very useful for applying highlevel math onto machine
words, since machine words (u8
, u16
, u32
, etc) are inherently finite.
Normally we just ignore this until an integer overflow occurs and then we just
wave our hands around wailing that math has failed us.
In Rust this has the fun sideeffect that the Galoisfield types are incapable of overflowing, so Galoisfield types don't need the set of overflowing operations normally found in other Rust types:
#
let a = (u8::MAX).checked_add(1); // overflows :(
let b = gf256(u8::MAX) + gf256(1); // does not overflow :)
For more information on Galoisfields and how we construct them, see the
relevant documentation in gf
's modulelevel documentation.
Included in gf256
gf256 contains a bit more than the Galoisfield types. It also contains a number of other utilities that rely on the math around finitefields:

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 structs (requires feature
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 functions (requires feature
crc
)use gf256::crc::crc32c; assert_eq!(crc32c(b"Hello World!", 0), 0xfe6cf1dc);

Shamir secretsharing functions (requires features
shamir
andthreadrng
)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!");

RAIDparity functions (requires feature
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!");

ReedSolomon errorcorrection functions (requires feature
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!");
Since this math depends on some rather arbitrary constants, each of these
utilities is available as both a normal Rust API, defined using reasonable
defaults, and as a highly configurable proc_macro
:
use gf256::gf::gf;
#[gf(polynomial=0x11b, generator=0x3)]
type gf256_rijndael;
let a = gf256_rijndael(0xfd);
let b = gf256_rijndael(0xfe);
let c = gf256_rijndael(0xff);
assert_eq!(a*(b+c), a*b + a*c);
Hardware support
Most modern 64bit hardware contains instructions for accelerating this sort of math. This usually comes in the form of a carryless multiplication instruction.
Carryless multiplication, also called polynomial multiplication and xor multiplication, is the multiplication analog for xor. Where traditional multiplication can be implemented as a series of shifts and adds, carryless multiplication can be implemented as a series of shifts and xors:
Multiplication:
1011 * 1101 = 1011
+ 1011
+ 1011

= 10001111
Carryless multiplication:
1011 * 1101 = 1011
^ 1011
^ 1011

= 01111111
64bit carryless multiplication is available on x86_64 with the
pclmulqdq
, and on aarch64 with the slightly less wordy
pmull
instruction.
gf256 takes advantage of these instructions when possible. However, at the time
of writing, pmull
support in Rust is only available on nightly.
#
// uses carryless multiplication instructions if available
let a = p32(0b1011);
let b = p32(0b1101);
assert_eq!(a * b, p32(0b01111111));
gf256 also exposes the flag HAS_XMUL
, which can be used to choose
algorithms based on whether or not hardware accelerated carryless
multiplication is available:
#
let a = p32(0b1011);
let b = if gf256::HAS_XMUL {
a * p32(0b11)
} else {
(a << 1) ^ a
};
gf256 also leverages the hardware accelerated carryless addition instructions, sometimes called polynomial addition, or simply xor. But this is much less notable.
const fn
support
Due to the use of traits and intrinsics, it's not possible to use the
polynomial/Galoisfield operators in const fns
.
As an alternative, gf256 provides a set of "naive" functions, which provide less efficient, well, naive, implementations that can be used in const fns.
These are very useful for calculating complex constants at compiletime, which is common in these sort of algorithms:
#
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
support
gf256 is just a pile of math, so it is mostly no_std
compatible.
The exceptions are the extra utilities rs
and shamir
, which
currently require alloc
.
Constanttime
gf256 provides "besteffort" constanttime implementations for certain useful operations. Though it should be emphasized this was primarily an educational project, so the constanttime properties should be externally evaluated before use, and you use this library at your own risk.

Polynomial multiplication
Polynomial multiplication in gf256 should always be constanttime.
The assumption is that any hardware accelerated carryless multiplication instructions complete in a fixed number of cycles, which is generally true.
If carryless multiplication instructions are not available, a branchless loop implementation of carryless multiplication is used.

Galoisfield operations
Galoisfield types in
barret
mode rely only on carryless multiplication and xors, and should always execute in constant time.The other Galoisfield implementations are NOT constanttime due to the use of lookup tables, which may be susceptible to cachetiming attacks. Note that the default Galoisfield types likely use a tablebased implementation.
You will need to declare a custom Galoisfield type using
barret
mode if you want constanttime finitefield operations:use gf256::gf::gf; #[gf(polynomial=0x11b, generator=0x3, barret)] type gf256_rijndael; #

Shamir secretsharing
The default Shamir secretsharing implementation internally uses a custom Galoisfield type in
barret
mode and should (keyword should) be constanttime.
Features

noxmul
 Disables carryless multiplication instructions, forcing the use of naive bitwise implementationsThis is mostly available for testing/benchmarking purposes.

notables
 Disables lookup tables, relying only on hardware instructions or naive implementationsThis may be useful on memory constrained devices

smalltables
 Limits lookup tables to "small tables", tables with <=16 elementsThis provides a compromise between full 256byte tables and notables, which may be useful on memory constrained devices

threadrng
 Enables features that depend on ThreadRngNote this requires
std
This is used to provide a default Rng implementation for Shamir's secretsharing implementations

lfsr
 Makes LFSR structs and macros available 
crc
 Makes CRC functions and macros available 
shamir
 Makes Shamir secretsharing functions and macros availableNote this requires
alloc
andrand
You may also want to enable the
threadrng
feature, which is required for a default rng 
raid
 Makes RAIDparity functions and macros available 
rs
 Makes ReedSolomon functions and macros availableNote this requires
alloc
Testing
gf256 comes with a number of tests implemented in Rust's test runner, these can be run with make:
make test
Additionally all of the code samples in these docs can be ran with Rust's doctest runner:
make docs
Benchmarking
gf256 also has a number of benchmarks implemented in Criterion. These were used to determine the best default implementations, and can be ran with make:
make bench
A full summary of the benchmark results can be found in BENCHMARKS.md.
Dependencies
~2MB
~43K SLoC