curveforge 0.3.0

Optimised, secure, and generalised algorithms for elliptic curve arithmetic
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

//! Montgomery curve model implementation.
//!
//! See [Curve25519](crate::curves::curve25519::Curve25519) for an example of a curve using this
//! model.
//!
//! The [MontgomeryModel] implements $x$-only arithmetic in projective form.
//! Since Montgomery models are birationally equivalent to [twisted
//! Edwards models](crate::models::twisted_edwards), curve implementations may offer conversion
//! methods, using the [edwards_y](MontgomeryModel::edwards_y) function to compute the Edwards
//! $y$-coordinate.
//!
//! # References
//! * [Costello and Smith, 2017](https://doi.org/10.1007/s13389-017-0157-6) - Montgomery curves and
//!   their arithmetic: The case of large characteristic fields
//! * [Dalek
//! Curve25519](https://github.com/dalek-cryptography/curve25519-dalek/blob/44433757a07c68a2b4f453c25d69469ae2f62986/curve25519-dalek/src/montgomery.rs#L430),
//!   for their implementation of Algorithm 7 from Costello and Smith, 2017.
use crate::prelude::*;

elliptic_curve_model! {
    [attributes]
    name = Montgomery
    // (u, v, z)
    // Bv^2 = u * (u^2 + Au + 1)
    coordinates = (u, w)
    constants = (A, B)

    [functions]
    serialize: (P: Point) -> Bytes
        // We serialize only the u-coordinate, as per RFC 7748.
        u <- P.u * P.w.inv()
        Bytes::from(u.serialize())

    deserialize: (buffer: Bytes) -> Point
        u <- Element::deserialize(buffer)
        Point::new(u, Element::from(1))

    equal: (P: Point, Q: Point) -> Bool
        // Check U1/W1 == U2/W2  <=> U1 * W2 == U2 * W1
        P.u * Q.w = Q.u * P.w

    edwards_y: (P: Point) -> Element
        // Convert to Edwards y-coordinate.
        // u = (1+y)/(1-y)  <=>  y = (u-1)/(u+1)
        y <- P.u - P.w
        z <- P.u + P.w
        y * z.inv()

    // NOTE: in projective space, negation of a point is incomplete
    neg: (P: Point) -> Point
        Point::new(P.u, P.w)

    dbl: (P: Point) -> Point
        // Costello-Smith, 2017, Algorithm 2
        v1 <- P.u + P.w
        v1 <- v1.sqr()
        v2 <- P.u - P.w
        v2 <- v2.sqr()
        u <- v1 * v2

        v1 <- v1 - v2
        v3 <- (A + 2) * 4.inv() * v1
        v3 <- v3 + v2
        w <- v1 * v3

        Point::new(u, w)

    differential_add_and_double: (P: Point, Q: Point, PmQ: Point) -> (Point, Point)
        t0 <- P.u + P.w
        t1 <- P.u - P.w
        t2 <- Q.u + Q.w
        t3 <- Q.u - Q.w

        // (U_P + W_P)^2 = U_P^2 + 2 U_P W_P + W_P^2
        t4 <- t0.sqr()
        // (U_P - W_P)^2 = U_P^2 - 2 U_P W_P + W_P^2
        t5 <- t1.sqr()

        t6 <- t4 - t5 // 4 U_P W_P

        // (U_P + W_P) (U_Q - W_Q) = U_P U_Q + W_P U_Q - U_P W_Q - W_P W_Q
        t7 <- t0 * t3
        // (U_P - W_P) (U_Q + W_Q) = U_P U_Q - W_P U_Q + U_P W_Q - W_P W_Q
        t8 <- t1 * t2

        // 2 (U_P U_Q - W_P W_Q)
        t9 <- t7 + t8
        // 2 (W_P U_Q - U_P W_Q)
        t10 <- t7 - t8

        // 4 (U_P U_Q - W_P W_Q)^2
        t11 <- t9.sqr()
        // 4 (W_P U_Q - U_P W_Q)^2
        t12 <- t10.sqr()

        // (A + 2) U_P U_Q
        t13 <- (A + 2) * 4.inv() * t6
        // ((U_P + W_P)(U_P - W_P))^2 = (U_P^2 - W_P^2)^2
        t14 <- t4 * t5
        // (U_P - W_P)^2 + (A + 2) U_P W_P
        t15 <- t13 + t5
        // 4 (U_P W_P) ((U_P - W_P)^2 + (A + 2) U_P W_P)
        t16 <- t6 * t15

        t17 <- PmQ.u * t12 // U_P * 4 (W_P U_Q - U_P W_Q)^2
        t18 <- PmQ.w * t11 // W_D * 4 (U_P U_Q - W_P W_Q)^2

        P <- Point::new(t14, t16)
        Q <- Point::new(t18, t17)

        (P, Q)
}

// Placeholder impl block, until we can somehow specialize the ScalarMul trait.
impl<__F: FiniteField<BOUND = typenum::U8> + 'static, __C: CurveConstants<__F>> MontgomeryModel<__F, __C>
where
    MontgomeryModel<__F, __C>: EllipticCurvePoint,
    MontgomeryModel<__F, __C>: ConditionallySelectable,
{
    // Direct port of Dalek `mul_bits_be`
    pub fn scalar_mul(self, scalar: impl FiniteFieldElement<<Self as EllipticCurvePoint>::Scalar>) -> Self {
        let mut x0 = Self::identity();
        let mut x1 = self;

        // Dalek works on an affine PmQ point, but it doesn't seem to make a big difference in
        // time.  It's O(n) multiplications versus O(1) inversion (which is in the order of O(n)
        // multiplications anyway).
        // You can test it enabling the line below:
        // ```
        // let affine_u = self.u * self.w.inv();
        // ```
        // Passing `self` directly as PmQ, and altering the `differential_add_and_double` function
        // to multiply by u instead of PmQ.u, and removing the multiplication by w.

        let mut prev_bit = false;
        for cur_bit in scalar.bits_le().rev().skip(1) {
            let choice = prev_bit ^ cur_bit;

            Self::conditional_swap(&mut x0, &mut x1, (choice as u8).into());
            (x0, x1) = Self::differential_add_and_double(x0, x1, self);

            prev_bit = cur_bit;
        }

        Self::conditional_swap(&mut x0, &mut x1, (prev_bit as u8).into());

        x0
    }
}