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§
- BigMonty
Form - A value modulo the odd modulus of the
BigMontyParamsit borrows, kept asx · R mod min as many limbs as the modulus takes, as aBigUintwould trim them. Going in and out of the form is variable time, as forBigUint; the arithmetic in between works on those limbs in constant time. Secret values go throughPaddedMontyForm. Operations on two forms need the same modulus, and panic otherwise, in every build. - BigMonty
Params - What Montgomery arithmetic modulo an odd
BigUintmneeds worked out once:mitself,R mod mandR² mod mforR = 2^(l · Word::BITS)at the numberlof limbsmtakes, and-m⁻¹ mod 2^Word::BITS. They are worked out in variable time, for a public modulus; a secret one goes throughPaddedMontyParams. - Fixed
Monty Form - A value modulo the odd modulus of its
FixedMontyParams, kept asx · 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. - Fixed
Monty Params - What Montgomery arithmetic modulo an odd
FixedBigUintmneeds worked out once:mitself,R mod mandR² mod mforR = 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. - Padded
Monty Form - A value modulo the odd modulus of the
PaddedMontyParamsit borrows, kept asx · R mod mat 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. - Padded
Monty Params - What Montgomery arithmetic modulo an odd
PaddedBigUintmneeds worked out once:mitself,R mod mandR² mod mforR = 2^(w · Word::BITS)at the widthwofm, 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.