elliptic_curve/hash2curve/
osswu.rs

1//! Optimized simplified Shallue-van de Woestijne-Ulas methods.
2//!
3//! <https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-16.html#straightline-sswu>
4
5use ff::Field;
6use subtle::Choice;
7use subtle::ConditionallySelectable;
8use subtle::ConstantTimeEq;
9
10/// The Optimized Simplified Shallue-van de Woestijne-Ulas parameters
11pub struct OsswuMapParams<F>
12where
13    F: Field,
14{
15    /// The first constant term
16    pub c1: &'static [u64],
17    /// The second constant term
18    pub c2: F,
19    /// The ISO A variable or Curve A variable
20    pub map_a: F,
21    /// The ISO A variable or Curve A variable
22    pub map_b: F,
23    /// The Z parameter
24    pub z: F,
25}
26
27/// Trait for determining the parity of the field
28pub trait Sgn0 {
29    /// Return the parity of the field
30    /// 1 == negative
31    /// 0 == non-negative
32    fn sgn0(&self) -> Choice;
33}
34
35/// The optimized simplified Shallue-van de Woestijne-Ulas method
36/// for mapping elliptic curve scalars to affine points.
37pub trait OsswuMap: Field + Sgn0 {
38    /// The OSSWU parameters for mapping the field to affine points.
39    /// For Weierstrass curves having A==0 or B==0, the parameters
40    /// should be for isogeny where A≠0 and B≠0.
41    const PARAMS: OsswuMapParams<Self>;
42
43    /// Optimized sqrt_ratio for q = 3 mod 4.
44    fn sqrt_ratio_3mod4(u: Self, v: Self) -> (Choice, Self) {
45        // 1. tv1 = v^2
46        let tv1 = v.square();
47        // 2. tv2 = u * v
48        let tv2 = u * v;
49        // 3. tv1 = tv1 * tv2
50        let tv1 = tv1 * tv2;
51        // 4. y1 = tv1^c1
52        let y1 = tv1.pow_vartime(Self::PARAMS.c1);
53        // 5. y1 = y1 * tv2
54        let y1 = y1 * tv2;
55        // 6. y2 = y1 * c2
56        let y2 = y1 * Self::PARAMS.c2;
57        // 7. tv3 = y1^2
58        let tv3 = y1.square();
59        // 8. tv3 = tv3 * v
60        let tv3 = tv3 * v;
61        // 9. isQR = tv3 == u
62        let is_qr = tv3.ct_eq(&u);
63        // 10. y = CMOV(y2, y1, isQR)
64        let y = ConditionallySelectable::conditional_select(&y2, &y1, is_qr);
65        // 11. return (isQR, y)
66        (is_qr, y)
67    }
68
69    /// Convert this field element into an affine point on the elliptic curve
70    /// returning (X, Y). For Weierstrass curves having A==0 or B==0
71    /// the result is a point on an isogeny.
72    fn osswu(&self) -> (Self, Self) {
73        // 1.  tv1 = u^2
74        let tv1 = self.square();
75        // 2.  tv1 = Z * tv1
76        let tv1 = Self::PARAMS.z * tv1;
77        // 3.  tv2 = tv1^2
78        let tv2 = tv1.square();
79        // 4.  tv2 = tv2 + tv1
80        let tv2 = tv2 + tv1;
81        // 5.  tv3 = tv2 + 1
82        let tv3 = tv2 + Self::ONE;
83        // 6.  tv3 = B * tv3
84        let tv3 = Self::PARAMS.map_b * tv3;
85        // 7.  tv4 = CMOV(Z, -tv2, tv2 != 0)
86        let tv4 = ConditionallySelectable::conditional_select(
87            &Self::PARAMS.z,
88            &-tv2,
89            !Field::is_zero(&tv2),
90        );
91        // 8.  tv4 = A * tv4
92        let tv4 = Self::PARAMS.map_a * tv4;
93        // 9.  tv2 = tv3^2
94        let tv2 = tv3.square();
95        // 10. tv6 = tv4^2
96        let tv6 = tv4.square();
97        // 11. tv5 = A * tv6
98        let tv5 = Self::PARAMS.map_a * tv6;
99        // 12. tv2 = tv2 + tv5
100        let tv2 = tv2 + tv5;
101        // 13. tv2 = tv2 * tv3
102        let tv2 = tv2 * tv3;
103        // 14. tv6 = tv6 * tv4
104        let tv6 = tv6 * tv4;
105        // 15. tv5 = B * tv6
106        let tv5 = Self::PARAMS.map_b * tv6;
107        // 16. tv2 = tv2 + tv5
108        let tv2 = tv2 + tv5;
109        // 17.   x = tv1 * tv3
110        let x = tv1 * tv3;
111        // 18. (is_gx1_square, y1) = sqrt_ratio(tv2, tv6)
112        let (is_gx1_square, y1) = Self::sqrt_ratio_3mod4(tv2, tv6);
113        // 19.   y = tv1 * u
114        let y = tv1 * self;
115        // 20.   y = y * y1
116        let y = y * y1;
117        // 21.   x = CMOV(x, tv3, is_gx1_square)
118        let x = ConditionallySelectable::conditional_select(&x, &tv3, is_gx1_square);
119        // 22.   y = CMOV(y, y1, is_gx1_square)
120        let y = ConditionallySelectable::conditional_select(&y, &y1, is_gx1_square);
121        // 23.  e1 = sgn0(u) == sgn0(y)
122        let e1 = self.sgn0().ct_eq(&y.sgn0());
123        // 24.   y = CMOV(-y, y, e1)
124        let y = ConditionallySelectable::conditional_select(&-y, &y, e1);
125        // 25.   x = x / tv4
126        let x = x * tv4.invert().unwrap();
127        // 26. return (x, y)
128        (x, y)
129    }
130}
elliptic_curve/hash2curve/osswu.rs

elliptic_curve/hash2curve/
osswu.rs
