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

//! Implementation of twisted Edwards curves in extended coordinates.
//!
//! # References
//! * [Hisil et al., 2008](https://eprint.iacr.org/2008/522) - Twisted Edwards Curves Revisited
//! * [EFD](https://www.hyperelliptic.org/EFD/g1p/auto-twisted-extended.html) -
//!   Explicit Formula Database - Extended coordinates for twisted Edwards curves

use crate::prelude::*;

elliptic_curve_model! {
    [attributes]
    name = TwistedEdwards
    coordinates = (x, y, z, t)
    constants = (a, d)

    [functions]
    // Hisil et al., 2008, general formula
    // https://www.hyperelliptic.org/EFD/g1p/auto-twisted-extended.html#addition-add-2008-hwcd
    // There is a faster formula in case a = -1. https://gitlab.com/etrovub/smartnets/glycos/curveforge/-/issues/27
    #[inline(always)]
    add: (P: Point, Q: Point) -> Point
        // A = X1*X2
        // B = Y1*Y2
        // C = T1*d*T2
        // D = Z1*Z2
        xx <- P.x * Q.x // A
        yy <- P.y * Q.y // B
        tt <- P.t * Q.t * d // C
        zz <- P.z * Q.z // D

        // E = (X1+Y1)*(X2+Y2)-A-B
        // F = D-C
        // G = D+C
        // H = B-a*A
        xyxy <- (P.x + P.y) * (Q.x + Q.y) - xx - yy // E
        zzd <- zz - tt // F
        zzp <- zz + tt // G
        yahx <- yy - a * xx // H
                            //
        // X3 = E*F
        // Y3 = G*H
        // T3 = E*H
        // Z3 = F*G
        x <- xyxy * zzd
        y <- zzp * yahx
        t <- xyxy * yahx
        z <- zzd * zzp

        Point::new(x, y, z, t)

    // Hisil et al., 2008, general formula
    // https://www.hyperelliptic.org/EFD/g1p/auto-twisted-extended.html#doubling-dbl-2008-hwcd
    // In case Z1 = 1 (i.e., the point is in affine coordinates), the formula can be simplified,
    // which would benefit a var-time implementation.
    #[inline(always)]
    dbl: (P: Point) -> Point
        // A = X1^2
        // B = Y1^2
        // C = 2*Z1^2
        // D = a*A
        xx <- P.x.sqr() // A
        yy <- P.y.sqr() // B
        zz <- P.z.sqr().dbl() // C
        d <- a * xx // D
        // E = (X1+Y1)^2-A-B
        xyxy <- (P.x + P.y).sqr() - xx - yy // E
        // G = D+B
        // F = G-C
        // H = D-B
        g <- d + yy // G
        f <- g - zz // F
        h <- d - yy // H
        // X3 = E*F
        // Y3 = G*H
        // T3 = E*H
        // Z3 = F*G
        x <- xyxy * f
        y <- g * h
        t <- xyxy * h
        z <- f * g
        Point::new(x, y, z, t)

    #[inline(always)]
    montgomery_u: (P: Point) -> Element
        u <- P.z + P.y
        w <- P.z - P.y
        u * w.inv()

    #[inline(always)]
    serialize: (P: Point) -> Bytes
        z_inv <- P.z.inv()
        x <- P.x * z_inv
        y <- P.y * z_inv

        flag <- x.is_even() ? 0 : 1

        Bytes::from(y.serialize_with_flags(flag))

    #[inline(always)]
    deserialize: (bytes: Bytes) -> Point
        (y, flags) <- Element::deserialize_with_flags(bytes)
        flag <- flags.get(0)

        y2 <- y.sqr()
        u <- 1 - y2
        v <- a - d * y2
        x2 <- u * v.inv()
        x <- x2.sqrt()
        x <- flag ? x.neg() : x

        Point::new(x, y, Element::from(1), x * y)

    #[inline(always)]
    equal: (P: Point, Q: Point) -> Bool
        // Check X1*Z2 == X2*Z1 and Y1*Z2 == Y2*Z1
        x_equal <- P.x * Q.z = Q.x * P.z
        y_equal <- P.y * Q.z = Q.y * P.z
        x_equal & y_equal

    #[inline(always)]
    neg: (P: Point) -> Point
        Point::new(-(P.x), P.y, P.z, -(P.t))
}