short_weierstrass/
projective.rs

1use core::{hint::black_box, borrow::Borrow, ops::*, iter::Sum};
2
3use subtle::{Choice, ConstantTimeEq, ConditionallySelectable, ConditionallyNegatable};
4use zeroize::{Zeroize, DefaultIsZeroes};
5
6use rand_core::RngCore;
7
8use group::{
9  ff::{Field, PrimeFieldBits},
10  Group,
11};
12
13use crate::{ShortWeierstrass, Affine};
14
15/// A point represented with projective coordinates.
16#[derive(Debug)]
17pub struct Projective<C: ShortWeierstrass> {
18  pub(crate) x: C::FieldElement,
19  pub(crate) y: C::FieldElement,
20  pub(crate) z: C::FieldElement,
21}
22impl<C: ShortWeierstrass> Clone for Projective<C> {
23  fn clone(&self) -> Self {
24    *self
25  }
26}
27impl<C: ShortWeierstrass> Copy for Projective<C> {}
28
29impl<C: ShortWeierstrass> From<Affine<C>> for Projective<C> {
30  fn from(affine: Affine<C>) -> Self {
31    Self { x: affine.x, y: affine.y, z: C::FieldElement::ONE }
32  }
33}
34
35impl<C: ShortWeierstrass> Default for Projective<C> {
36  fn default() -> Self {
37    Self::IDENTITY
38  }
39}
40impl<C: ShortWeierstrass> DefaultIsZeroes for Projective<C> {}
41
42impl<C: ShortWeierstrass> ConstantTimeEq for Projective<C> {
43  fn ct_eq(&self, other: &Self) -> Choice {
44    let c1 = (self.x * other.z).ct_eq(&(other.x * self.z));
45    let c2 = (self.y * other.z).ct_eq(&(other.y * self.z));
46    c1 & c2
47  }
48}
49impl<C: ShortWeierstrass> PartialEq for Projective<C> {
50  fn eq(&self, other: &Self) -> bool {
51    self.ct_eq(other).into()
52  }
53}
54impl<C: ShortWeierstrass> Eq for Projective<C> {}
55
56impl<C: ShortWeierstrass> ConditionallySelectable for Projective<C> {
57  fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
58    let x = C::FieldElement::conditional_select(&a.x, &b.x, choice);
59    let y = C::FieldElement::conditional_select(&a.y, &b.y, choice);
60    let z = C::FieldElement::conditional_select(&a.z, &b.z, choice);
61    Projective { x, y, z }
62  }
63}
64
65impl<C: ShortWeierstrass> Neg for Projective<C> {
66  type Output = Self;
67  fn neg(mut self) -> Self::Output {
68    self.y = -self.y;
69    self
70  }
71}
72
73impl<C: ShortWeierstrass> ConditionallyNegatable for Projective<C> {
74  fn conditional_negate(&mut self, negate: Choice) {
75    self.y = <_>::conditional_select(&self.y, &-self.y, negate);
76  }
77}
78
79impl<C: ShortWeierstrass> Add for Projective<C> {
80  type Output = Self;
81  // add-1998-cmo-2
82  /*
83    We don't use the complete formulas from 2015 as they require the curve is prime order, when we
84    do not.
85  */
86  fn add(self, p2: Self) -> Self {
87    let Self { x: X1, y: Y1, z: Z1 } = self;
88    let Self { x: X2, y: Y2, z: Z2 } = p2;
89
90    let Y1Z2 = Y1 * Z2;
91    let X1Z2 = X1 * Z2;
92    let Z1Z2 = Z1 * Z2;
93    let u = (Y2 * Z1) - Y1Z2;
94    let uu = u.square();
95    let v = (X2 * Z1) - X1Z2;
96    let vv = v.square();
97    let vvv = v * vv;
98    let R = vv * X1Z2;
99    let A = (uu * Z1Z2) - vvv - R.double();
100    let X3 = v * A;
101    let Y3 = (u * (R - A)) - (vvv * Y1Z2);
102    let Z3 = vvv * Z1Z2;
103
104    let res = Self { x: X3, y: Y3, z: Z3 };
105
106    let same_x_coordinate = (self.x * p2.z).ct_eq(&(p2.x * self.z));
107    let same_y_coordinate = (self.y * p2.z).ct_eq(&(p2.y * self.z));
108    let res = <_>::conditional_select(
109      &res,
110      &Self::IDENTITY,
111      (self.is_identity_internal() & p2.is_identity_internal()) |
112        (same_x_coordinate & (!same_y_coordinate)),
113    );
114    let res =
115      <_>::conditional_select(&res, &self.double_internal(), same_x_coordinate & same_y_coordinate);
116    let res = <_>::conditional_select(&res, &p2, self.is_identity_internal());
117    <_>::conditional_select(&res, &self, p2.is_identity_internal())
118  }
119}
120impl<C: ShortWeierstrass> Sub for Projective<C> {
121  type Output = Self;
122  fn sub(self, p2: Self) -> Self {
123    self + -p2
124  }
125}
126impl<C: ShortWeierstrass> AddAssign for Projective<C> {
127  fn add_assign(&mut self, p2: Self) {
128    *self = *self + p2;
129  }
130}
131impl<C: ShortWeierstrass> SubAssign for Projective<C> {
132  fn sub_assign(&mut self, p2: Self) {
133    *self = *self - p2;
134  }
135}
136impl<C: ShortWeierstrass> Add<&Self> for Projective<C> {
137  type Output = Self;
138  fn add(self, p2: &Self) -> Self {
139    self + *p2
140  }
141}
142impl<C: ShortWeierstrass> Sub<&Self> for Projective<C> {
143  type Output = Self;
144  fn sub(self, p2: &Self) -> Self {
145    self - *p2
146  }
147}
148impl<C: ShortWeierstrass> AddAssign<&Self> for Projective<C> {
149  fn add_assign(&mut self, p2: &Self) {
150    *self = *self + p2;
151  }
152}
153impl<C: ShortWeierstrass> SubAssign<&Self> for Projective<C> {
154  fn sub_assign(&mut self, p2: &Self) {
155    *self = *self - p2;
156  }
157}
158
159impl<C: ShortWeierstrass> Projective<C> {
160  /// The additive identity, or point at infinity.
161  pub const IDENTITY: Self =
162    Projective { x: C::FieldElement::ZERO, y: C::FieldElement::ONE, z: C::FieldElement::ZERO };
163  /// A generator of this elliptic curve.
164  pub const GENERATOR: Self =
165    Projective { x: C::GENERATOR.x, y: C::GENERATOR.y, z: C::FieldElement::ONE };
166
167  fn is_identity_internal(&self) -> Choice {
168    self.z.ct_eq(&C::FieldElement::ZERO)
169  }
170
171  // dbl-1998-cmo-2
172  fn double_internal(&self) -> Self {
173    let Self { x: X1, y: Y1, z: Z1 } = *self;
174
175    let X1X1 = X1.square();
176    let w = (C::A * Z1.square()) + X1X1.double() + X1X1;
177    let s = Y1 * Z1;
178    let ss = s.square();
179    let sss = s * ss;
180    let R = Y1 * s;
181    let B = X1 * R;
182    let B4 = B.double().double();
183    let h = w.square() - B4.double();
184    let X3 = (h * s).double();
185    let Y3 = w * (B4 - h) - R.square().double().double().double();
186    let Z3 = sss.double().double().double();
187
188    let res = Self { x: X3, y: Y3, z: Z3 };
189    <_>::conditional_select(&res, &Self::IDENTITY, self.is_identity_internal())
190  }
191}
192
193impl<C: ShortWeierstrass> Sum for Projective<C> {
194  fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
195    let mut res = Self::IDENTITY;
196    for item in iter {
197      res += item;
198    }
199    res
200  }
201}
202
203impl<'a, C: ShortWeierstrass> Sum<&'a Self> for Projective<C> {
204  fn sum<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
205    let mut res = Self::IDENTITY;
206    for item in iter {
207      res += item;
208    }
209    res
210  }
211}
212
213impl<C: ShortWeierstrass<Scalar = ()>> Projective<C> {
214  /// Sample a random on-curve point with an unknown discrete logarithm w.r.t. any other points.
215  pub fn random(rng: impl RngCore) -> Self {
216    Self::from(Affine::random(rng))
217  }
218  /// If this point is the additive identity.
219  pub fn is_identity(&self) -> Choice {
220    self.is_identity_internal()
221  }
222  /// The sum of this point with itself.
223  pub fn double(&self) -> Self {
224    self.double_internal()
225  }
226}
227
228impl<C: ShortWeierstrass<Scalar: PrimeFieldBits>, S: Borrow<C::Scalar>> Mul<S> for Projective<C> {
229  type Output = Self;
230  fn mul(self, scalar: S) -> Self {
231    let mut table = [Self::IDENTITY; 16];
232    table[1] = self;
233    for i in 2 .. 16 {
234      table[i] = table[i - 1] + self;
235    }
236
237    let mut res = Self::identity();
238    let mut bits = 0;
239    for (i, mut bit) in scalar.borrow().to_le_bits().iter_mut().rev().enumerate() {
240      fn u8_from_bool(bit_ref: &mut bool) -> u8 {
241        let bit_ref = black_box(bit_ref);
242
243        let mut bit = black_box(*bit_ref);
244        let res = black_box(u8::from(bit));
245        bit.zeroize();
246        debug_assert!((res | 1) == 1);
247
248        bit_ref.zeroize();
249        res
250      }
251
252      bits <<= 1;
253      let mut bit = u8_from_bool(bit.deref_mut());
254      bits |= bit;
255      bit.zeroize();
256
257      if ((i + 1) % 4) == 0 {
258        if i != 3 {
259          for _ in 0 .. 4 {
260            res = res.double();
261          }
262        }
263
264        let mut term = table[0];
265        for (j, candidate) in table[1 ..].iter().enumerate() {
266          let j = j + 1;
267          term = Self::conditional_select(&term, candidate, usize::from(bits).ct_eq(&j));
268        }
269        res += term;
270        bits = 0;
271      }
272    }
273    res
274  }
275}
276impl<C: ShortWeierstrass<Scalar: PrimeFieldBits>, S: Borrow<C::Scalar>> MulAssign<S>
277  for Projective<C>
278{
279  fn mul_assign(&mut self, scalar: S) {
280    *self = *self * scalar.borrow();
281  }
282}
283/*
284impl<C: ShortWeierstrass<Scalar: PrimeFieldBits>> Mul<&C::Scalar> for Projective<C> {
285  type Output = Self;
286  fn mul(self, scalar: &C::Scalar) -> Self {
287    self * *scalar
288  }
289}
290impl<C: ShortWeierstrass<Scalar: PrimeFieldBits>> MulAssign<&C::Scalar> for Projective<C> {
291  fn mul_assign(&mut self, scalar: &C::Scalar) {
292    *self *= *scalar;
293  }
294}
295*/
296impl<C: ShortWeierstrass<Scalar: PrimeFieldBits>> Group for Projective<C> {
297  type Scalar = C::Scalar;
298  fn random(rng: impl RngCore) -> Self {
299    Self::from(Affine::<C>::random(rng))
300  }
301  fn identity() -> Self {
302    Self::IDENTITY
303  }
304  fn generator() -> Self {
305    C::GENERATOR.into()
306  }
307  fn is_identity(&self) -> Choice {
308    self.is_identity_internal()
309  }
310  fn double(&self) -> Self {
311    self.double_internal()
312  }
313}
short_weierstrass/projective.rs

short_weierstrass/
projective.rs
