// Copyright 2026 Leo Cheng
// SPDX-License-Identifier: Apache-2.0
///|
/// The first primes, for trial division before Miller-Rabin. A composite that a
/// small prime divides costs a division to reject instead of an exponentiation,
/// and most candidates fall here.
let small_primes : FixedArray[Int32] = [
3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257,
263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353,
359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449,
457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
]
///|
/// `a^{-1} mod m` by the extended Euclidean algorithm. `m` need not be prime,
/// which is what rules out the Fermat inverse — RSA's `phi` is even and so never
/// prime.
fn modinv(a : BigInt, m : BigInt) -> BigInt {
let mut old_r = a
let mut r = m
let mut old_s = (1 : BigInt)
let mut s = (0 : BigInt)
while r != (0 : BigInt) {
let q = old_r / r
let nr = old_r - q * r
old_r = r
r = nr
let ns = old_s - q * s
old_s = s
s = ns
}
if old_r != (1 : BigInt) {
abort(
"rsa: the exponent is not invertible modulo phi, which means a bad prime",
)
}
let d = old_s % m
if d < (0 : BigInt) {
d + m
} else {
d
}
}
///|
/// The Miller-Rabin test (FIPS 186-5 B.3.1), with the bases drawn uniformly from
/// the source. Forty rounds make the error below 4^-40, and the small-prime pass
/// rejects the common composites before the first exponentiation.
fn[S : @moonseed.Source] is_probable_prime(
n : BigInt,
source : S,
) -> Bool raise @moonseed.Unavailable {
for p in small_primes {
let bp = BigInt::from_int(p)
if n % bp == (0 : BigInt) {
return n == bp
}
}
let n1 = n - (1 : BigInt)
let mut d = n1
let mut s = 0
while d % (2 : BigInt) == (0 : BigInt) {
d = d >> 1
s = s + 1
}
// A base in [2, n - 2]: `below` draws [0, n - 3), so adding two shifts up.
let span = n - (3 : BigInt)
for _ in 0..<40 {
let a = BigInt::from_octets(@moonseed.below(span.to_octets()[:], source)) +
(2 : BigInt)
let mut x = a.pow(d, modulus=n)
let mut pass = x == (1 : BigInt) || x == n1
if !pass {
for _ in 1.. BigInt raise @moonseed.Unavailable {
let nbytes = (bits + 7) / 8
let excess = nbytes * 8 - bits
while true {
let buf = FixedArray::make(nbytes, b'\x00')
source.fill(buf)
buf[0] = (buf[0].to_int() | 0xC0).to_byte()
if excess > 0 {
buf[0] = (buf[0].to_int() & (0xFF >> excess)).to_byte()
}
buf[nbytes - 1] = (buf[nbytes - 1].to_int() | 1).to_byte()
let candidate = BigInt::from_octets(buf.unsafe_reinterpret_as_bytes()[:])
if is_probable_prime(candidate, source) {
return candidate
}
}
abort("rsa: unreachable")
}
///|
/// Generate a fresh RSA signing key (FIPS 186-5 A.1.1): two random primes `p` and
/// `q`, the modulus `n = p·q`, the public exponent 65537, and the private
/// exponent `d = e^{-1} mod phi(n)`.
///
/// The primes are drawn from `source`, so a seeded [`@moonseed.Source`] makes the
/// key reproducible and the platform's entropy makes it secret. `bits` is the
/// modulus width, at least 512 and a multiple of 8; 2048 is the default every
/// certificate and TLS stack accepts.
pub fn[S : @moonseed.Source] PrivateKey::generate(
source : S,
bits~ : Int32 = 2048,
digest~ : Digest = Sha256,
scheme~ : Scheme = Pkcs1,
) -> PrivateKey raise @moonseed.Unavailable {
guard bits >= 512 && bits % 8 == 0 else {
abort("rsa: a modulus of \{bits} bits is not a multiple of 8 at least 512")
}
let e = BigInt::from_int(65537)
while true {
let p = random_prime(bits / 2, source)
let q = random_prime(bits / 2, source)
if p == q {
continue
}
let n = p * q
if octets(n) != bits / 8 {
continue
}
let phi = (p - 1) * (q - 1)
// 65537 is prime, so it divides `phi` only when it divides a factor.
if phi % e == (0 : BigInt) {
continue
}
let d = modinv(e, phi)
// The factors are held, so the key signs through the two halves rather than
// the one: the primes the generator just found are exactly what a CRT needs.
return {
n,
e,
d,
size: octets(n),
digest,
scheme,
crt: Some(Crt::fitted([p, q], d)),
}
}
abort("rsa: unreachable")
}