ed448-goldilocks 0.9.0

A pure-Rust implementation of Ed448 and Curve448 and Decaf
Documentation 
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

#[cfg(feature = "fiat_u64_backend")]
pub mod fiat_u64;

#[cfg(feature = "u32_backend")]
pub mod u32;

// XXX: Currently we only have one implementation for Scalar
mod scalar;
pub use crate::field::scalar::Scalar;

#[cfg(feature = "u32_backend")]
pub type FieldElement = crate::field::u32::FieldElement28;

#[cfg(feature = "fiat_u64_backend")]
pub type FieldElement = crate::field::fiat_u64::FieldElement56;

use subtle::{Choice, ConstantTimeEq};
impl ConstantTimeEq for FieldElement {
    fn ct_eq(&self, other: &Self) -> Choice {
        self.to_bytes().ct_eq(&other.to_bytes())
    }
}

impl PartialEq for FieldElement {
    fn eq(&self, other: &FieldElement) -> bool {
        self.ct_eq(&other).into()
    }
}
impl Eq for FieldElement {}

impl FieldElement {
    /// Checks if a field element is zero
    pub(crate) fn is_zero(&self) -> Choice {
        self.ct_eq(&FieldElement::zero())
    }
    /// Inverts a field element
    /// Previous chain length: 462, new length 460
    pub fn invert(&self) -> FieldElement {
        // Addition chain taken from https://github.com/mmcloughlin/addchain
        let _1 = self;
        let _10 = _1.square();
        let _11 = *_1 * _10;
        let _110 = _11.square();
        let _111 = *_1 * _110;
        let _111000 = _111.square_n(3);
        let _111111 = _111 * _111000;

        let x12 = _111111.square_n(6) * _111111;
        let x24 = x12.square_n(12) * x12;
        let i34 = x24.square_n(6);
        let x30 = _111111 * i34;
        let x48 = i34.square_n(18) * x24;
        let x96 = x48.square_n(48) * x48;
        let x192 = x96.square_n(96) * x96;
        let x222 = x192.square_n(30) * x30;
        let x223 = x222.square() * _1;

        (x223.square_n(223) * x222).square_n(2) * _1
    }
    /// Squares a field element  `n` times
    fn square_n(&self, mut n: u32) -> FieldElement {
        let mut result = self.square();

        // Decrease value by 1 since we just did a squaring
        n = n - 1;

        for _ in 0..n {
            result = result.square();
        }

        result
    }

    /// Computes the inverse square root of a field element
    /// Returns the result and a boolean to indicate whether self
    /// was a Quadratic residue
    pub(crate) fn inverse_square_root(&self) -> (FieldElement, Choice) {
        let (mut l0, mut l1, mut l2) = (
            FieldElement::zero(),
            FieldElement::zero(),
            FieldElement::zero(),
        );

        l1 = self.square();
        l2 = l1 * self;
        l1 = l2.square();
        l2 = l1 * self;
        l1 = l2.square_n(3);
        l0 = l2 * l1;
        l1 = l0.square_n(3);
        l0 = l2 * l1;
        l2 = l0.square_n(9);
        l1 = l0 * l2;
        l0 = l1 * l1;
        l2 = l0 * self;
        l0 = l2.square_n(18);
        l2 = l1 * l0;
        l0 = l2.square_n(37);
        l1 = l2 * l0;
        l0 = l1.square_n(37);
        l1 = l2 * l0;
        l0 = l1.square_n(111);
        l2 = l1 * l0;
        l0 = l2.square();
        l1 = l0 * self;
        l0 = l1.square_n(223);
        l1 = l2 * l0;
        l2 = l1.square();
        l0 = l2 * self;

        let is_residue = l0.ct_eq(&FieldElement::one());
        (l1, is_residue)
    }

    /// Computes the square root ratio of two elements
    pub(crate) fn sqrt_ratio(u: &FieldElement, v: &FieldElement) -> (FieldElement, Choice) {
        // Compute sqrt(1/(uv))
        let x = *u * v;
        let (inv_sqrt_x, is_res) = x.inverse_square_root();
        // Return u * sqrt(1/(uv)) == sqrt(u/v). However, since this trick only works
        // for u != 0, check for that case explicitly (when u == 0 then inv_sqrt_x
        // will be zero, which is what we want, but is_res will be 0)
        let zero_u = u.ct_eq(&FieldElement::zero());
        (inv_sqrt_x * u, zero_u | is_res)
    }
}