silk.crypto.prime.

When to use#

Use Prime.isProbablePrime to check a number, as Node.js crypto.checkPrime does, and Prime.generate for a new random prime, as Node.js crypto.generatePrime does. RSA key generation in silk.crypto.rsa and the group check in silk.crypto.dh use the same test.

Details#

The test is trial division by the odd primes below 4096, then Miller-Rabin with random bases from the ambient Random. With r rounds, a composite passes with probability at most 4^-r. Prime.recommendedRounds gives the rounds that OpenSSL uses. Numbers are silk.crypto.modular values of up to 8192 bits. Nothing allocates.

Errors#

• PrimeError for a bit length or a constraint that no prime can meet.

Gotchas#

Trial division and the number of Miller-Rabin rounds that run depend on the candidate, but the exponentiations take the same time for every candidate of a length. A rejected candidate tells nothing about the prime that is kept, so generated primes can be secret.

Examples#

Test and generate primes#

import silk.core.effect { Effect }
import silk.core.option { Option }
import silk.core.result { Result }
import silk.crypto.modular { Natural }
import silk.crypto.prime { Prime, PrimeError, PrimeOptions }
import silk.num.u64
import silk.system.random { Random }

// A predictable generator for the example. Real programs use a secure `Random` provider.
struct Counter {
  state: u64,
}

impl Random for Counter {
  effect fn fillBytes(self: &mut Self, output: &mut [u8]) -> () {
    let mut index: usize = 0
    while index < output.length {
      self.state = u64.wrappingAdd(u64.wrappingMultiply(self.state, 6364136223846793005), 1)
      output[index] = u64.toU8(u64.shiftRight(self.state, 56))
      index = index + 1
    }
  }
}

effect fn check() -> i32 ? &mut Random {
  // 2^61 - 1 is prime, and 2^61 + 1 is divisible by 3.
  if !run Prime.isProbablePrime(&Natural.fromU64(2305843009213693951), 64) {
    return 1
  }
  if run Prime.isProbablePrime(&Natural.fromU64(2305843009213693953), 64) {
    return 1
  }
  let options = PrimeOptions { safe: true, add: Option<Natural>.none(), remainder: Option<Natural>.none() }
  return match run Prime.generate(64, &options) {
    Result<Natural, PrimeError>.Success { value } => {
      if value.bitLength() == 64 {
        return 0
      }
      return 1
    }
    Result<Natural, PrimeError>.Failure {..} => 1
  }
}

pub fn main() -> i32 {
  let mut random = Counter { state: 7 }
  return run check() |> Effect.provideMut<Random>(&mut random)
}

Import as Prime with import silk.crypto.prime { Prime }.

Public declarations: 3.

PrimeError#

pub enum PrimeError

The reason that Prime.generate cannot make a prime.

InvalidBits#

InvalidBits

The bit length is below 2, below 3 for a safe prime, or above 8192.

InvalidConstraint#

InvalidConstraint

add is 0 or longer than the prime, remainder is not below add, or no prime of the form add * k + remainder exists, such as when they share a factor.

Implementation Debug for PrimeError#

impl Debug for PrimeError

Operation debug#

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

Writes the name of the variant, such as InvalidBits.

PrimeOptions#

pub struct PrimeOptions

What Prime.generate asks of the prime, as in Node.js crypto.generatePrime.

Field safe#

pub safe: bool

Whether (p - 1) / 2 must also be prime.

Field add#

pub add: Option<Natural>

If set, the prime has the remainder PrimeOptions.remainder when divided by this value.

Field remainder#

pub remainder: Option<Natural>

The remainder modulo add. It is ignored without add. Without it, the remainder is 3 for a safe prime and 1 for another prime, as in OpenSSL.

Prime#

pub struct Prime

Functions that test numbers for primality and generate primes.

When to use#

Use it for Node.js crypto.checkPrime and crypto.generatePrime, or to check a Diffie-Hellman group that a peer sent.

Details#

Both functions read random bytes from the ambient Random, which must be cryptographically secure for a prime that must be secret.

Implementation Prime#

impl Prime

Associated function recommendedRounds#

pub fn recommendedRounds(bits: usize) -> usize

Returns the Miller-Rabin rounds that OpenSSL uses for a number of bits bits: 64, or 128 above 2048 bits. A composite passes with probability at most 2^-128 or 2^-256.

Associated function isProbablePrime#

pub effect fn isProbablePrime(candidate: &Natural, rounds: usize) -> bool
    ? &mut Random

Returns whether candidate is probably prime, after trial division and rounds rounds of Miller-Rabin with random bases.

The answer is exact below 2^24. A prime always passes. A composite passes with probability at most 4^-rounds, so 0 rounds gives trial division only.

Associated function generate#

pub effect fn generate(bits: usize, options: &PrimeOptions) -> Result<Natural, PrimeError>
    ? &mut Random

Returns a random prime of exactly bits bits that meets options.

The candidates are random odd numbers of bits bits with the top bit set, stepped by add (or 2, or 4 for a safe prime) until one passes trial division and Prime.recommendedRounds of Miller-Rabin. For a safe prime, (p - 1) / 2 passes too.

Errors#

• InvalidBits if bits is below 2, below 3 for a safe prime, or above 8192.

• InvalidConstraint if add is 0 or has more than bits bits, remainder is not below add, they share a factor, or for a safe prime add and remainder - 1 share a factor other than 2.

Gotchas#

A constraint can still leave no prime of bits bits, such as add of bits bits with a remainder too small; then the call does not return.

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.