Skip to main content

Crate tc_modular

Crate tc_modular 

Source
Expand description

Modular arithmetic for cryptography, over the integers of tc_bigint.

It builds on that crate’s public interface alone: values are read through their limbs and built back from them, and the limb arithmetic it needs is its own.

The Mod* traits take an operand of any size and a modulus that is not zero, as NonZero holds it. The Montgomery parameters and forms take an odd modulus, as Odd holds it, and keep a value as x · R mod m, so that a product takes one Montgomery multiplication rather than a division.

use tc_bigint::{FixedBigUint, Word};
use tc_modular::{FixedMontyForm, FixedMontyParams, ModInverse, NonZero, Odd};

type U256 = FixedBigUint<{ 256 / Word::BITS as usize }>;

let p = U256::from(i128::MAX as u128); // 2^127 - 1, a prime
let params = FixedMontyParams::new(Odd::new(p.clone()).unwrap());
let three = FixedMontyForm::new(&U256::from(3u8), params);
assert_eq!(three.pow(&(&p - 1u32)).retrieve(), U256::from(1u8));
let inverse = U256::from(3u8).mod_inverse(&NonZero::new(p).unwrap());
assert_eq!(inverse, Some(U256::from(u128::MAX / 3)));

§Timing

Over the fixed-width and padded integers, everything is constant time: the running time follows the widths, which are public, and not the values. The one thing a modulus shows is its parity, where it picks the path, as for ModPow and ModInverse; whether an inverse exists shows in the Option that holds it. Over the big integers, which are only for public values, the way in and out is variable time. Every method says which it is.

§Wiping

Over the fixed-width and padded integers, the working values an operation makes and then gives up are wiped through volatile writes: the residues of the operands, the steps of a power, the working values of an inversion, the parameters a single ModPow builds. The values handed back, and those given, are the caller’s to wipe, through Zeroize or Zeroizing. What the compiler copies on its own is beyond reach: a value moved on the stack may leave a copy behind, and a register or a spill may keep a word of it.

Structs§

BigMontyForm
A value modulo the odd modulus of the BigMontyParams it borrows, kept as x · R mod m in as many limbs as the modulus takes, as a BigUint would trim them. Going in and out of the form is variable time, as for BigUint; the arithmetic in between works on those limbs in constant time. Secret values go through PaddedMontyForm. Operations on two forms need the same modulus, and panic otherwise, in every build.
BigMontyParams
What Montgomery arithmetic modulo an odd BigUint m needs worked out once: m itself, R mod m and R² mod m for R = 2^(l · Word::BITS) at the number l of limbs m takes, and -m⁻¹ mod 2^Word::BITS. They are worked out in variable time, for a public modulus; a secret one goes through PaddedMontyParams.
FixedMontyForm
A value modulo the odd modulus of its FixedMontyParams, kept as x · R mod m, so that a product takes one Montgomery multiplication rather than a division. The form holds its own copy of the parameters, on the stack. Operations on two forms need the same modulus, and panic otherwise, in every build.
FixedMontyParams
What Montgomery arithmetic modulo an odd FixedBigUint m needs worked out once: m itself, R mod m and R² mod m for R = 2^(N · Word::BITS), and -m⁻¹ mod 2^Word::BITS.
NonZero
A value known not to be zero, so that code taking one need not check again. There is no DerefMut, which would let the value turn zero.
Odd
A value known to be odd, as a Montgomery modulus must be, so that code taking one need not check again; an odd value is never zero. There is no DerefMut, which would let the value turn even.
PaddedMontyForm
A value modulo the odd modulus of the PaddedMontyParams it borrows, kept as x · R mod m at the width of the modulus, so that a product takes one Montgomery multiplication rather than a division. Operations on two forms need the same modulus at the same width, and panic otherwise, in every build.
PaddedMontyParams
What Montgomery arithmetic modulo an odd PaddedBigUint m needs worked out once: m itself, R mod m and R² mod m for R = 2^(w · Word::BITS) at the width w of m, which every value here takes, and -m⁻¹ mod 2^Word::BITS.

Traits§

ModAdd
Addition reduced modulo modulus. Each implementation states whether it is constant time.
ModInverse
The multiplicative inverse modulo modulus. Each implementation states whether it is constant time.
ModMul
Multiplication reduced modulo modulus, without the caller holding the full product. Each implementation states whether it is constant time.
ModPow
Exponentiation reduced modulo modulus. Each implementation states whether it is constant time, and in which of its operands.
ModSub
Subtraction reduced to the least residue that is not negative. Each implementation states whether it is constant time.