silk.crypto.modular.

When to use#

Use it to build public-key cryptography that works on large numbers, such as RSA and finite field Diffie-Hellman. silk.crypto.rsa uses it. For a fixed curve, use that curve's module, such as silk.crypto.p256, which is faster.

Details#

A Natural holds a value below 2^8192 in 32-bit words. It also has a length in words, which Natural.fromBytes takes from the number of input bytes, not from the value. A Modulus holds an odd number of 3 or more and the constants for Montgomery multiplication modulo it.

Every operation takes the same time for all values of the same lengths: it has no branch and no memory access that depends on a value. The time depends only on the word lengths of the inputs and the bit length of the modulus. Modulus.powerPublic is the one exception: its time depends on the exponent, so use it only for a public exponent.

Errors#

• ModularError for a value that does not fit, a subtraction below zero, or a modulus that is even or below 3.

Gotchas#

The operations of a Modulus need inputs that are less than the modulus. Reduce a value with Modulus.reduce first if it may be larger. The values stay in memory after use; nothing erases them.

Examples#

Compute a power modulo a prime#

import silk.core.ownership { Copy }
import silk.core.result { Result }
import silk.crypto.modular { ModularError, Modulus, Natural }

pub fn main() -> i32 {
  let modulus = match Modulus.make(&Natural.fromU64(1000003)) {
    Result<Modulus, ModularError>.Success { value } => move value
    Result<Modulus, ModularError>.Failure { error: _ } => {
      return 1
    }
  }
  // 2^1000002 is 1 modulo the prime 1000003.
  let result = modulus.power(&Natural.fromU64(2), &Natural.fromU64(1000002))
  let mut bytes: [u8; 4] = [0; 4]
  match result.writeBytes(&mut bytes) {
    Result<(), ModularError>.Success { value: _ } => {}
    Result<(), ModularError>.Failure { error: _ } => {
      return 2
    }
  }
  if bytes[0] != 0 || bytes[1] != 0 || bytes[2] != 0 || bytes[3] != 1 {
    return 3
  }
  return 0
}

Import as Modulus with import silk.crypto.modular { Modulus }.

Public declarations: 4.

NATURAL_WORDS#

pub const NATURAL_WORDS: usize

The number of 32-bit words in a Natural: 256 words hold 8192 bits.

ModularError#

pub enum ModularError

The reason that a modular operation failed.

TooLarge#

TooLarge

A value does not fit in 8192 bits, or in the output.

Negative#

Negative

A subtraction would give a value below zero.

InvalidModulus#

InvalidModulus

A modulus is even or below 3.

Implementation Debug for ModularError#

impl Debug for ModularError

Operation debug#

effect fn debug(self: &Self, formatter: &mut Formatter) -> ()
    ! WriterError
    ? &mut Writer

Writes the name of the variant, such as TooLarge.

Natural#

pub struct Natural

An unsigned integer below 2^8192 with a length in 32-bit words.

When to use#

Use it for the values of public-key cryptography: keys, messages, and signatures as numbers.

Details#

The length sets how many words the operations read, and so how long they take. It comes from the size of the input, not from the value: Natural.fromBytes with 256 bytes gives 64 words even when the value is small. Results of arithmetic have the length that holds any result of inputs of those lengths.

Gotchas#

It is a fixed-size value of about 1 KiB. Pass it by reference.

Implementation Copy for Natural#

impl Copy for Natural

Modulus#

pub struct Modulus

An odd modulus of 3 or more, with the constants for Montgomery multiplication modulo it.

When to use#

Make one with Modulus.make for each modulus, such as an RSA modulus, an RSA prime, or a Diffie-Hellman prime, and keep it for all the operations with that modulus.

Details#

Making a modulus of k words computes 2^(64 * k) modulo it, which takes about as long as two multiplications of k-word numbers per bit of the modulus. The operations then take inputs below the modulus and return results below it, with the word length of the modulus.

Gotchas#

It is a fixed-size value of about 2 KiB. Pass it by reference.

Implementation Copy for Modulus#

impl Copy for Modulus

Implementation Natural#

impl Natural

Associated function zero#

pub fn zero() -> Natural

Returns 0 with a length of 0 words.

Associated function fromU64#

pub fn fromU64(value: u64) -> Natural

Returns value with a length of 2 words.

Associated function fromBytes#

pub fn fromBytes(bytes: &[u8]) -> Result<Natural, ModularError>

Returns the big-endian bytes as a number with a length of bytes.length / 4 words, rounded up.

Leading zero bytes are allowed. The time depends only on bytes.length.

Errors#

• TooLarge if the value is 2^8192 or more.

Method writeBytes#

pub fn writeBytes(self: &Natural, output: &mut [u8]) -> Result<(), ModularError>

Writes the value big-endian to all of output, with leading zero bytes as needed.

The time depends only on output.length and the length of the value.

Errors#

• TooLarge if the value does not fit in output.length bytes. output may then hold part of the value.

Method wordLength#

pub fn wordLength(self: &Natural) -> usize

Returns the length in 32-bit words, which sets the time of the operations.

Method bitLength#

pub fn bitLength(self: &Natural) -> usize

Returns the number of significant bits: 0 for 0, and n for a value from 2^(n - 1) to 2^n - 1. The time depends only on the length.

Method bit#

pub fn bit(self: &Natural, index: usize) -> u32

Returns bit index, counted from the least significant bit, as 0 or 1. Bits at or above the length are 0.

Method isZero#

pub fn isZero(self: &Natural) -> bool

Returns whether the value is 0. The time depends only on the length.

Method equals#

pub fn equals(self: &Natural, other: &Natural) -> bool

Returns whether the two values are equal. The time depends only on the lengths.

Method lessThan#

pub fn lessThan(self: &Natural, other: &Natural) -> bool

Returns whether this value is less than other. The time depends only on the lengths.

Method remainder#

pub fn remainder(self: &Natural, divisor: &Natural) -> Result<Natural, ModularError>

Returns the value modulo divisor, with the length of divisor.

The divisor can be even. The time depends only on the two lengths.

Errors#

• InvalidModulus if divisor is 0.

Method resize#

pub fn resize(self: &Natural, length: usize) -> Result<Natural, ModularError>

Returns the value with a length of length words.

Errors#

• TooLarge if length is above 256 or the value does not fit in length words.

Method shiftRight#

pub fn shiftRight(self: &Natural, count: usize) -> Natural

Returns the value divided by 2^count, rounded down, with the same length. The time depends only on count and the length.

Method divideWord#

pub fn divideWord(self: &Natural, divisor: u32) -> Natural

Returns the value divided by divisor, rounded down, with the same length. The time depends only on the length.

Gotchas#

The program traps if divisor is 0.

Method remainderWord#

pub fn remainderWord(self: &Natural, divisor: u32) -> u32

Returns the remainder of the value divided by divisor. The time depends only on the length.

Gotchas#

The program traps if divisor is 0.

Method add#

pub fn add(self: &Natural, other: &Natural) -> Result<Natural, ModularError>

Returns the sum, with a length of one word more than the longer input, up to 256 words.

Errors#

• TooLarge if the sum is 2^8192 or more.

Method subtract#

pub fn subtract(self: &Natural, other: &Natural) -> Result<Natural, ModularError>

Returns this value minus other, with the length of the longer input.

Errors#

• Negative if other is larger.

Method multiply#

pub fn multiply(self: &Natural, other: &Natural) -> Result<Natural, ModularError>

Returns the product, with the sum of the input lengths, up to 256 words.

Errors#

• TooLarge if the product is 2^8192 or more.

Implementation Modulus#

impl Modulus

Associated function make#

pub fn make(value: &Natural) -> Result<Modulus, ModularError>

Returns the modulus value, which must be odd and 3 or more.

The word length of the modulus is that of its value without leading zero words, so the time of this call and of later operations depends on the bit length of the value, but not on its other bits.

Errors#

• InvalidModulus if value is even or below 3.

Method natural#

pub fn natural(self: &Modulus) -> Natural

Returns a copy of the modulus as a number, with the word length of the modulus.

Method bitLength#

pub fn bitLength(self: &Modulus) -> usize

Returns the number of significant bits of the modulus.

Method wordLength#

pub fn wordLength(self: &Modulus) -> usize

Returns the word length of the modulus and of the results of its operations.

Method reduce#

pub fn reduce(self: &Modulus, value: &Natural) -> Natural

Returns value modulo the modulus, for any value. The time depends on the length of value.

Method add#

pub fn add(self: &Modulus, left: &Natural, right: &Natural) -> Natural

Returns left + right modulo the modulus. Both must be less than the modulus.

Method subtract#

pub fn subtract(self: &Modulus, left: &Natural, right: &Natural) -> Natural

Returns left - right modulo the modulus. Both must be less than the modulus.

Method multiply#

pub fn multiply(self: &Modulus, left: &Natural, right: &Natural) -> Natural

Returns left * right modulo the modulus. Both must be less than the modulus.

Method power#

pub fn power(self: &Modulus, base: &Natural, exponent: &Natural) -> Natural

Returns base to the power exponent modulo the modulus. base must be less than the modulus; exponent can be any value.

The time depends only on the bit length of the modulus and the length of exponent, so the base and the exponent can be secret. A zero exponent gives 1.

Method powerPublic#

pub fn powerPublic(self: &Modulus, base: &Natural, exponent: &Natural) -> Natural

Returns base to the power exponent modulo the modulus, faster than Modulus.power for a short exponent. base must be less than the modulus.

Gotchas#

Its time depends on the bits of exponent, so use it only for a public exponent, such as an RSA public exponent. The time does not depend on base.

Method invertPrime#

pub fn invertPrime(self: &Modulus, value: &Natural) -> Natural

Returns the inverse of value modulo the modulus, which must be prime: the number that gives 1 when multiplied by value. value must be less than the modulus. 0 gives 0.

It computes value to the power modulus - 2, in the time of Modulus.power.

Category: Cryptography.

Profiles: aarch64-apple-darwin, aarch64-unknown-linux-gnu, aarch64-unknown-linux-gnu-no-libc, x86_64-unknown-linux-gnu, x86_64-unknown-linux-gnu-no-libc, wasm32-unknown-unknown, wasm32-wasip1, wasm32-wasip2, x86_64-pc-windows-msvc, wasm64-unknown-unknown.