dymokomi/luce-crypto
Source of release 0.6.1
## Fixed-capacity unsigned integers for RSA public-key operations: big-endian
## byte conversion, comparison and Montgomery modular exponentiation (CIOS)
## modulo an odd modulus of up to 8192 bits. Everything here handles public
## values (moduli, exponents, signatures), so loops and branches may depend on
## the data; this is not a constant-time private-key implementation.
import sha2
## The largest supported operand, in 32-bit limbs (8192 bits).
pub let max_limbs: usize = 256
## A natural number in little-endian 32-bit limbs; `size` limbs are in use.
pub struct Natural:
var limbs: u32[256]
var size: usize
## The number with big-endian bytes `bytes`, using exactly enough limbs
## for that many bytes (leading zero bytes still count toward `size`).
pub static func from_bytes(bytes: const u8[]) -> Natural!:
if bytes.length == 0 or bytes.length > max_limbs * 4:
error(sha2.invalid, "integer must be 1 to 1024 bytes")
var value = Natural(size = (bytes.length + 3) // 4)
for i in 0..<bytes.length:
let position = bytes.length - 1 - i
value.limbs[i // 4] |= (u32)bytes[position] << (u32)(8 * (i % 4))
return value
## Write the value as exactly `out.length` big-endian bytes; fails when it
## does not fit.
pub func to_bytes(out: u8[]) -> !:
for i in 0..<out.length:
out[i] = 0
for i in 0..<self.size * 4:
let byte = (u8)((self.limbs[i // 4] >> (u32)(8 * (i % 4))) & 0xff)
if i >= out.length:
if byte != 0:
error(sha2.invalid, "integer does not fit the output")
else:
out[out.length - 1 - i] = byte
## The number of significant bits.
pub func bit_length() -> usize:
var i = self.size
while i > 0:
let limb = self.limbs[i - 1]
if limb != 0:
var bits: usize = 32
while (limb >> (u32)(bits - 1)) == 0:
bits -= 1
return (i - 1) * 32 + bits
i -= 1
return 0
## Whether the value is zero.
pub func is_zero() -> bool:
return self.bit_length() == 0
## -1, 0 or 1 as a < b, a == b, a > b, over the larger of the two sizes.
pub func compare(a: const Natural*, b: const Natural*) -> i32:
var i = a.size if a.size > b.size else b.size
while i > 0:
let x = a.limbs[i - 1] if i <= a.size else 0
let y = b.limbs[i - 1] if i <= b.size else 0
if x != y:
return 1 if x > y else -1
i -= 1
return 0
## Montgomery arithmetic modulo an odd `modulus` with R = 2^(32·size). Create
## it once per modulus and reuse it for every exponentiation.
pub struct Montgomery:
var modulus: Natural
var n0: u32
var r2: Natural
## Precompute -n^-1 mod 2^32 and R^2 mod n.
pub static func create(modulus: const Natural*) -> Montgomery!:
if (modulus.limbs[0] & 1) == 0 or modulus.bit_length() < 2:
error(sha2.invalid, "Montgomery modulus must be odd and greater than one")
var context = Montgomery(modulus = *modulus)
context.modulus.size = (modulus.bit_length() + 31) // 32
# Newton iteration for the inverse of n modulo 2^32.
let n = modulus.limbs[0]
var inverse: u32 = 1
for _ in 0..<(usize)5:
inverse = inverse *% (2 -% n *% inverse)
context.n0 = 0 -% inverse
# R mod n: start below n at 2^(bits-1) and double up to 2^(32·size).
let size = context.modulus.size
let bits = context.modulus.bit_length()
var value = Natural(size = size)
value.limbs[(bits - 1) // 32] = (u32)1 << (u32)((bits - 1) % 32)
for _ in 0..<32 * size - (bits - 1):
double_mod(&value, &context.modulus)
# With 32·size = c·2^j (c odd): c more doublings give 2^c·R, the
# Montgomery form of 2^c, and j Montgomery squarings raise it to
# 2^(32·size) = R, whose Montgomery form is R^2 mod n.
var odd = 32 * size
var squarings: usize = 0
while odd % 2 == 0:
odd = odd // 2
squarings += 1
for _ in 0..<odd:
double_mod(&value, &context.modulus)
for _ in 0..<squarings:
context.multiply(&value, &value, &value)
context.r2 = value
return context
## out = a·b·R^-1 mod n for a, b < n (CIOS).
func multiply(out: Natural*, a: const Natural*, b: const Natural*):
let size = self.modulus.size
var t: u32[258]
for i in 0..<size:
var carry: u64 = 0
let bi = (u64)b.limbs[i]
for j in 0..<size:
let sum = (u64)t[j] + (u64)a.limbs[j] * bi + carry
t[j] = (u32)(sum & 0xffffffff)
carry = sum >> 32
var sum = (u64)t[size] + carry
t[size] = (u32)(sum & 0xffffffff)
t[size + 1] = (u32)(sum >> 32)
let m = (u64)(t[0] *% self.n0)
sum = (u64)t[0] + m * (u64)self.modulus.limbs[0]
carry = sum >> 32
for j in 1..<size:
sum = (u64)t[j] + m * (u64)self.modulus.limbs[j] + carry
t[j - 1] = (u32)(sum & 0xffffffff)
carry = sum >> 32
sum = (u64)t[size] + carry
t[size - 1] = (u32)(sum & 0xffffffff)
t[size] = t[size + 1] + (u32)(sum >> 32)
var result = Natural(size = size)
for i in 0..<size:
result.limbs[i] = t[i]
if t[size] != 0 or compare(&result, &self.modulus) >= 0:
subtract(&result, &self.modulus)
*out = result
## a = 2a mod n for a < n.
func double_mod(a: Natural*, modulus: const Natural*):
var carry: u32 = 0
for j in 0..<a.size:
let next = a.limbs[j] >> 31
a.limbs[j] = (a.limbs[j] << 1) | carry
carry = next
if carry != 0 or compare(a, modulus) >= 0:
subtract(a, modulus)
## a -= b, assuming a >= b (or that the borrow cancels a carry out of `a`).
func subtract(a: Natural*, b: const Natural*):
var borrow: u64 = 0
for i in 0..<a.size:
let x = (u64)a.limbs[i]
let y = (u64)(b.limbs[i] if i < b.size else 0) + borrow
if x >= y:
a.limbs[i] = (u32)(x - y)
borrow = 0
else:
a.limbs[i] = (u32)(x + 0x100000000 - y)
borrow = 1
## base^exponent mod modulus for a public big-endian `exponent`. `base` must
## be below the odd modulus. The result has the modulus's limb count.
pub func modular_power(base: const Natural*, exponent: const u8[], modulus: const Natural*) -> Natural!:
let context = try Montgomery.create(modulus)
return try power(&context, base, exponent)
## base^exponent modulo the context's modulus, by left-to-right square and
## multiply from the exponent's leading one bit (public exponents only).
pub func power(context: const Montgomery*, base: const Natural*, exponent: const u8[]) -> Natural!:
if compare(base, &context.modulus) >= 0:
error(sha2.invalid, "base must be below the modulus")
var reduced = *base
reduced.size = context.modulus.size
var factor = Natural(size = context.modulus.size)
context.multiply(&factor, &reduced, &context.r2)
var one = Natural(size = context.modulus.size)
one.limbs[0] = 1
var result = Natural()
context.multiply(&result, &one, &context.r2)
var started = false
for i in 0..<exponent.length:
var bit: i32 = 7
while bit >= 0:
let set = ((exponent[i] >> (u8)bit) & 1) != 0
if started:
context.multiply(&result, &result, &result)
if set:
context.multiply(&result, &result, &factor)
started = true
bit -= 1
context.multiply(&result, &result, &one)
return result