1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

#![cfg_attr(not(feature = "std"), no_std)]
// All `as` conversions in this code base have been carefully reviewed
// and are safe.
#![allow(clippy::as_conversions)]

mod arith;
mod maybe_std;
mod mpnat;

use maybe_std::Vec;

/// Trait providing the interface for the modexp function.
/// The implementation provided by this crate is `AuroraModExp` below,
/// but other users of Aurora Engine may wish to select a different implementation.
pub trait ModExpAlgorithm: 'static {
    /// Computes `(base ^ exp) % modulus`, where all values are given as big-endian encoded bytes.
    fn modexp(base: &[u8], exp: &[u8], modulus: &[u8]) -> Vec<u8>;
}

pub struct AuroraModExp;

impl ModExpAlgorithm for AuroraModExp {
    fn modexp(base: &[u8], exp: &[u8], modulus: &[u8]) -> Vec<u8> {
        modexp(base, exp, modulus)
    }
}

/// Computes `(base ^ exp) % modulus`, where all values are given as big-endian
/// encoded bytes.
pub fn modexp(base: &[u8], exp: &[u8], modulus: &[u8]) -> Vec<u8> {
    let mut x = mpnat::MPNat::from_big_endian(base);
    let m = mpnat::MPNat::from_big_endian(modulus);
    if m.digits.len() == 1 && m.digits[0] == 0 {
        return Vec::new();
    }
    let result = x.modpow(exp, &m);
    result.to_big_endian()
}

#[cfg(feature = "bench")]
pub fn modexp_ibig(base: &[u8], exp: &[u8], modulus: &[u8]) -> Vec<u8> {
    use num::Zero;

    let base = ibig::UBig::from_be_bytes(base);
    let modulus = ibig::UBig::from_be_bytes(modulus);
    if modulus.is_zero() {
        return Vec::new();
    }
    let exponent = ibig::UBig::from_be_bytes(exp);
    let ring = ibig::modular::ModuloRing::new(&modulus);
    let result = ring.from(base).pow(&exponent);
    result.residue().to_be_bytes()
}

#[cfg(feature = "bench")]
pub fn modexp_num(base: &[u8], exp: &[u8], modulus: &[u8]) -> Vec<u8> {
    use num::Zero;

    let base = num::BigUint::from_bytes_be(base);
    let modulus = num::BigUint::from_bytes_be(modulus);
    if modulus.is_zero() {
        return Vec::new();
    }
    let exponent = num::BigUint::from_bytes_be(exp);
    base.modpow(&exponent, &modulus).to_bytes_be()
}