p256/arithmetic/
projective.rs

1//! Projective points
2
3#![allow(clippy::op_ref)]
4
5use super::{AffinePoint, FieldElement, Scalar, CURVE_EQUATION_B};
6use crate::{CompressedPoint, EncodedPoint, NistP256, PublicKey};
7use core::{
8    iter::Sum,
9    ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign},
10};
11use elliptic_curve::{
12    group::{
13        ff::Field,
14        prime::{PrimeCurve, PrimeCurveAffine, PrimeGroup},
15        Curve, Group, GroupEncoding,
16    },
17    ops::LinearCombination,
18    rand_core::RngCore,
19    sec1::{FromEncodedPoint, ToEncodedPoint},
20    subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption},
21    weierstrass,
22    zeroize::DefaultIsZeroes,
23    Error, PrimeCurveArithmetic, ProjectiveArithmetic, Result,
24};
25
26impl ProjectiveArithmetic for NistP256 {
27    type ProjectivePoint = ProjectivePoint;
28}
29
30impl PrimeCurveArithmetic for NistP256 {
31    type CurveGroup = ProjectivePoint;
32}
33
34/// A point on the secp256r1 curve in projective coordinates.
35#[derive(Clone, Copy, Debug)]
36#[cfg_attr(docsrs, doc(cfg(feature = "arithmetic")))]
37pub struct ProjectivePoint {
38    x: FieldElement,
39    y: FieldElement,
40    z: FieldElement,
41}
42
43impl ProjectivePoint {
44    /// Additive identity of the group: the point at infinity.
45    pub const IDENTITY: Self = Self {
46        x: FieldElement::ZERO,
47        y: FieldElement::ONE,
48        z: FieldElement::ZERO,
49    };
50
51    /// Base point of P-256.
52    pub const GENERATOR: Self = Self {
53        x: AffinePoint::GENERATOR.x,
54        y: AffinePoint::GENERATOR.y,
55        z: FieldElement::ONE,
56    };
57
58    /// Returns the additive identity of P-256, also known as the "neutral element" or
59    /// "point at infinity".
60    #[deprecated(since = "0.10.1", note = "use `ProjectivePoint::IDENTITY` instead")]
61    pub const fn identity() -> ProjectivePoint {
62        Self::IDENTITY
63    }
64
65    /// Returns the base point of P-256.
66    #[deprecated(since = "0.10.1", note = "use `ProjectivePoint::GENERATOR` instead")]
67    pub fn generator() -> ProjectivePoint {
68        Self::GENERATOR
69    }
70
71    /// Returns the affine representation of this point, or `None` if it is the identity.
72    pub fn to_affine(&self) -> AffinePoint {
73        self.z
74            .invert()
75            .map(|zinv| AffinePoint {
76                x: self.x * &zinv,
77                y: self.y * &zinv,
78                infinity: 0,
79            })
80            .unwrap_or(AffinePoint::IDENTITY)
81    }
82
83    /// Returns `-self`.
84    fn neg(&self) -> ProjectivePoint {
85        ProjectivePoint {
86            x: self.x,
87            y: self.y.neg(),
88            z: self.z,
89        }
90    }
91
92    /// Returns `self + other`.
93    fn add(&self, other: &ProjectivePoint) -> ProjectivePoint {
94        weierstrass::add(
95            (self.x, self.y, self.z),
96            (other.x, other.y, other.z),
97            CURVE_EQUATION_B,
98        )
99        .into()
100    }
101
102    /// Returns `self + other`.
103    fn add_mixed(&self, other: &AffinePoint) -> ProjectivePoint {
104        let ret = Self::from(weierstrass::add_mixed(
105            (self.x, self.y, self.z),
106            (other.x, other.y),
107            CURVE_EQUATION_B,
108        ));
109
110        Self::conditional_select(&ret, self, other.is_identity())
111    }
112
113    /// Doubles this point.
114    pub fn double(&self) -> ProjectivePoint {
115        weierstrass::double((self.x, self.y, self.z), CURVE_EQUATION_B).into()
116    }
117
118    /// Returns `self - other`.
119    fn sub(&self, other: &ProjectivePoint) -> ProjectivePoint {
120        self.add(&other.neg())
121    }
122
123    /// Returns `self - other`.
124    fn sub_mixed(&self, other: &AffinePoint) -> ProjectivePoint {
125        self.add_mixed(&other.neg())
126    }
127
128    /// Returns `[k] self`.
129    fn mul(&self, k: &Scalar) -> ProjectivePoint {
130        let mut pc = [ProjectivePoint::default(); 16];
131        pc[0] = ProjectivePoint::IDENTITY;
132        pc[1] = *self;
133        for i in 2..16 {
134            pc[i] = if i % 2 == 0 {
135                pc[i / 2].double()
136            } else {
137                pc[i - 1].add(self)
138            };
139        }
140        let mut q = ProjectivePoint::IDENTITY;
141        let k = k.to_bytes();
142        let mut pos = 256 - 4;
143        loop {
144            let slot = (k[31 - (pos >> 3) as usize] >> (pos & 7)) & 0xf;
145            let mut t = ProjectivePoint::IDENTITY;
146            for (i, pci) in pc.iter().enumerate().skip(1) {
147                t.conditional_assign(
148                    pci,
149                    Choice::from(((slot as usize ^ i).wrapping_sub(1) >> 8) as u8 & 1),
150                );
151            }
152            q = q.add(&t);
153            if pos == 0 {
154                break;
155            }
156            q = q.double().double().double().double();
157            pos -= 4;
158        }
159        q
160    }
161}
162
163impl Group for ProjectivePoint {
164    type Scalar = Scalar;
165
166    fn random(mut rng: impl RngCore) -> Self {
167        Self::GENERATOR * Scalar::random(&mut rng)
168    }
169
170    fn identity() -> Self {
171        Self::IDENTITY
172    }
173
174    fn generator() -> Self {
175        Self::GENERATOR
176    }
177
178    fn is_identity(&self) -> Choice {
179        self.ct_eq(&Self::IDENTITY)
180    }
181
182    #[must_use]
183    fn double(&self) -> Self {
184        ProjectivePoint::double(self)
185    }
186}
187
188impl GroupEncoding for ProjectivePoint {
189    type Repr = CompressedPoint;
190
191    fn from_bytes(bytes: &Self::Repr) -> CtOption<Self> {
192        <AffinePoint as GroupEncoding>::from_bytes(bytes).map(Into::into)
193    }
194
195    fn from_bytes_unchecked(bytes: &Self::Repr) -> CtOption<Self> {
196        // No unchecked conversion possible for compressed points
197        Self::from_bytes(bytes)
198    }
199
200    fn to_bytes(&self) -> Self::Repr {
201        self.to_affine().to_bytes()
202    }
203}
204
205impl PrimeGroup for ProjectivePoint {}
206
207impl Curve for ProjectivePoint {
208    type AffineRepr = AffinePoint;
209
210    fn to_affine(&self) -> AffinePoint {
211        ProjectivePoint::to_affine(self)
212    }
213}
214
215impl PrimeCurve for ProjectivePoint {
216    type Affine = AffinePoint;
217}
218
219impl LinearCombination for ProjectivePoint {}
220
221impl From<AffinePoint> for ProjectivePoint {
222    fn from(p: AffinePoint) -> Self {
223        let projective = ProjectivePoint {
224            x: p.x,
225            y: p.y,
226            z: FieldElement::ONE,
227        };
228        Self::conditional_select(&projective, &Self::IDENTITY, p.is_identity())
229    }
230}
231
232impl From<&AffinePoint> for ProjectivePoint {
233    fn from(p: &AffinePoint) -> Self {
234        Self::from(*p)
235    }
236}
237
238impl From<ProjectivePoint> for AffinePoint {
239    fn from(p: ProjectivePoint) -> AffinePoint {
240        p.to_affine()
241    }
242}
243
244impl From<&ProjectivePoint> for AffinePoint {
245    fn from(p: &ProjectivePoint) -> AffinePoint {
246        p.to_affine()
247    }
248}
249
250impl From<weierstrass::ProjectivePoint<FieldElement>> for ProjectivePoint {
251    #[inline]
252    fn from((x, y, z): weierstrass::ProjectivePoint<FieldElement>) -> ProjectivePoint {
253        Self { x, y, z }
254    }
255}
256
257impl FromEncodedPoint<NistP256> for ProjectivePoint {
258    fn from_encoded_point(p: &EncodedPoint) -> CtOption<Self> {
259        AffinePoint::from_encoded_point(p).map(ProjectivePoint::from)
260    }
261}
262
263impl ToEncodedPoint<NistP256> for ProjectivePoint {
264    fn to_encoded_point(&self, compress: bool) -> EncodedPoint {
265        self.to_affine().to_encoded_point(compress)
266    }
267}
268
269impl ConditionallySelectable for ProjectivePoint {
270    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
271        ProjectivePoint {
272            x: FieldElement::conditional_select(&a.x, &b.x, choice),
273            y: FieldElement::conditional_select(&a.y, &b.y, choice),
274            z: FieldElement::conditional_select(&a.z, &b.z, choice),
275        }
276    }
277}
278
279impl ConstantTimeEq for ProjectivePoint {
280    fn ct_eq(&self, other: &Self) -> Choice {
281        self.to_affine().ct_eq(&other.to_affine())
282    }
283}
284
285impl DefaultIsZeroes for ProjectivePoint {}
286
287impl Eq for ProjectivePoint {}
288
289impl PartialEq for ProjectivePoint {
290    fn eq(&self, other: &Self) -> bool {
291        self.ct_eq(other).into()
292    }
293}
294
295impl Default for ProjectivePoint {
296    fn default() -> Self {
297        Self::IDENTITY
298    }
299}
300
301impl Add<ProjectivePoint> for ProjectivePoint {
302    type Output = ProjectivePoint;
303
304    fn add(self, other: ProjectivePoint) -> ProjectivePoint {
305        ProjectivePoint::add(&self, &other)
306    }
307}
308
309impl Add<&ProjectivePoint> for &ProjectivePoint {
310    type Output = ProjectivePoint;
311
312    fn add(self, other: &ProjectivePoint) -> ProjectivePoint {
313        ProjectivePoint::add(self, other)
314    }
315}
316
317impl Add<&ProjectivePoint> for ProjectivePoint {
318    type Output = ProjectivePoint;
319
320    fn add(self, other: &ProjectivePoint) -> ProjectivePoint {
321        ProjectivePoint::add(&self, other)
322    }
323}
324
325impl AddAssign<ProjectivePoint> for ProjectivePoint {
326    fn add_assign(&mut self, rhs: ProjectivePoint) {
327        *self = ProjectivePoint::add(self, &rhs);
328    }
329}
330
331impl AddAssign<&ProjectivePoint> for ProjectivePoint {
332    fn add_assign(&mut self, rhs: &ProjectivePoint) {
333        *self = ProjectivePoint::add(self, rhs);
334    }
335}
336
337impl Add<AffinePoint> for ProjectivePoint {
338    type Output = ProjectivePoint;
339
340    fn add(self, other: AffinePoint) -> ProjectivePoint {
341        ProjectivePoint::add_mixed(&self, &other)
342    }
343}
344
345impl Add<&AffinePoint> for &ProjectivePoint {
346    type Output = ProjectivePoint;
347
348    fn add(self, other: &AffinePoint) -> ProjectivePoint {
349        ProjectivePoint::add_mixed(self, other)
350    }
351}
352
353impl Add<&AffinePoint> for ProjectivePoint {
354    type Output = ProjectivePoint;
355
356    fn add(self, other: &AffinePoint) -> ProjectivePoint {
357        ProjectivePoint::add_mixed(&self, other)
358    }
359}
360
361impl AddAssign<AffinePoint> for ProjectivePoint {
362    fn add_assign(&mut self, rhs: AffinePoint) {
363        *self = ProjectivePoint::add_mixed(self, &rhs);
364    }
365}
366
367impl AddAssign<&AffinePoint> for ProjectivePoint {
368    fn add_assign(&mut self, rhs: &AffinePoint) {
369        *self = ProjectivePoint::add_mixed(self, rhs);
370    }
371}
372
373impl Sum for ProjectivePoint {
374    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
375        iter.fold(ProjectivePoint::IDENTITY, |a, b| a + b)
376    }
377}
378
379impl<'a> Sum<&'a ProjectivePoint> for ProjectivePoint {
380    fn sum<I: Iterator<Item = &'a ProjectivePoint>>(iter: I) -> Self {
381        iter.cloned().sum()
382    }
383}
384
385impl Sub<ProjectivePoint> for ProjectivePoint {
386    type Output = ProjectivePoint;
387
388    fn sub(self, other: ProjectivePoint) -> ProjectivePoint {
389        ProjectivePoint::sub(&self, &other)
390    }
391}
392
393impl Sub<&ProjectivePoint> for &ProjectivePoint {
394    type Output = ProjectivePoint;
395
396    fn sub(self, other: &ProjectivePoint) -> ProjectivePoint {
397        ProjectivePoint::sub(self, other)
398    }
399}
400
401impl Sub<&ProjectivePoint> for ProjectivePoint {
402    type Output = ProjectivePoint;
403
404    fn sub(self, other: &ProjectivePoint) -> ProjectivePoint {
405        ProjectivePoint::sub(&self, other)
406    }
407}
408
409impl SubAssign<ProjectivePoint> for ProjectivePoint {
410    fn sub_assign(&mut self, rhs: ProjectivePoint) {
411        *self = ProjectivePoint::sub(self, &rhs);
412    }
413}
414
415impl SubAssign<&ProjectivePoint> for ProjectivePoint {
416    fn sub_assign(&mut self, rhs: &ProjectivePoint) {
417        *self = ProjectivePoint::sub(self, rhs);
418    }
419}
420
421impl Sub<AffinePoint> for ProjectivePoint {
422    type Output = ProjectivePoint;
423
424    fn sub(self, other: AffinePoint) -> ProjectivePoint {
425        ProjectivePoint::sub_mixed(&self, &other)
426    }
427}
428
429impl Sub<&AffinePoint> for &ProjectivePoint {
430    type Output = ProjectivePoint;
431
432    fn sub(self, other: &AffinePoint) -> ProjectivePoint {
433        ProjectivePoint::sub_mixed(self, other)
434    }
435}
436
437impl Sub<&AffinePoint> for ProjectivePoint {
438    type Output = ProjectivePoint;
439
440    fn sub(self, other: &AffinePoint) -> ProjectivePoint {
441        ProjectivePoint::sub_mixed(&self, other)
442    }
443}
444
445impl SubAssign<AffinePoint> for ProjectivePoint {
446    fn sub_assign(&mut self, rhs: AffinePoint) {
447        *self = ProjectivePoint::sub_mixed(self, &rhs);
448    }
449}
450
451impl SubAssign<&AffinePoint> for ProjectivePoint {
452    fn sub_assign(&mut self, rhs: &AffinePoint) {
453        *self = ProjectivePoint::sub_mixed(self, rhs);
454    }
455}
456
457impl Mul<Scalar> for ProjectivePoint {
458    type Output = ProjectivePoint;
459
460    fn mul(self, other: Scalar) -> ProjectivePoint {
461        ProjectivePoint::mul(&self, &other)
462    }
463}
464
465impl Mul<&Scalar> for &ProjectivePoint {
466    type Output = ProjectivePoint;
467
468    fn mul(self, other: &Scalar) -> ProjectivePoint {
469        ProjectivePoint::mul(self, other)
470    }
471}
472
473impl Mul<&Scalar> for ProjectivePoint {
474    type Output = ProjectivePoint;
475
476    fn mul(self, other: &Scalar) -> ProjectivePoint {
477        ProjectivePoint::mul(&self, other)
478    }
479}
480
481impl MulAssign<Scalar> for ProjectivePoint {
482    fn mul_assign(&mut self, rhs: Scalar) {
483        *self = ProjectivePoint::mul(self, &rhs);
484    }
485}
486
487impl MulAssign<&Scalar> for ProjectivePoint {
488    fn mul_assign(&mut self, rhs: &Scalar) {
489        *self = ProjectivePoint::mul(self, rhs);
490    }
491}
492
493impl Neg for ProjectivePoint {
494    type Output = ProjectivePoint;
495
496    fn neg(self) -> ProjectivePoint {
497        ProjectivePoint::neg(&self)
498    }
499}
500
501impl<'a> Neg for &'a ProjectivePoint {
502    type Output = ProjectivePoint;
503
504    fn neg(self) -> ProjectivePoint {
505        ProjectivePoint::neg(self)
506    }
507}
508
509impl From<PublicKey> for ProjectivePoint {
510    fn from(public_key: PublicKey) -> ProjectivePoint {
511        AffinePoint::from(public_key).into()
512    }
513}
514
515impl From<&PublicKey> for ProjectivePoint {
516    fn from(public_key: &PublicKey) -> ProjectivePoint {
517        AffinePoint::from(public_key).into()
518    }
519}
520
521impl TryFrom<ProjectivePoint> for PublicKey {
522    type Error = Error;
523
524    fn try_from(point: ProjectivePoint) -> Result<PublicKey> {
525        AffinePoint::from(point).try_into()
526    }
527}
528
529impl TryFrom<&ProjectivePoint> for PublicKey {
530    type Error = Error;
531
532    fn try_from(point: &ProjectivePoint) -> Result<PublicKey> {
533        AffinePoint::from(point).try_into()
534    }
535}
536
537#[cfg(test)]
538mod tests {
539    use super::{AffinePoint, ProjectivePoint, Scalar};
540    use crate::test_vectors::group::{ADD_TEST_VECTORS, MUL_TEST_VECTORS};
541    use elliptic_curve::group::{ff::PrimeField, prime::PrimeCurveAffine, GroupEncoding};
542
543    #[test]
544    fn affine_to_projective() {
545        let basepoint_affine = AffinePoint::GENERATOR;
546        let basepoint_projective = ProjectivePoint::GENERATOR;
547
548        assert_eq!(
549            ProjectivePoint::from(basepoint_affine),
550            basepoint_projective,
551        );
552        assert_eq!(basepoint_projective.to_affine(), basepoint_affine);
553        assert!(!bool::from(basepoint_projective.to_affine().is_identity()));
554
555        assert!(bool::from(
556            ProjectivePoint::IDENTITY.to_affine().is_identity()
557        ));
558    }
559
560    #[test]
561    fn projective_identity_addition() {
562        let identity = ProjectivePoint::IDENTITY;
563        let generator = ProjectivePoint::GENERATOR;
564
565        assert_eq!(identity + &generator, generator);
566        assert_eq!(generator + &identity, generator);
567    }
568
569    #[test]
570    fn projective_mixed_addition() {
571        let identity = ProjectivePoint::IDENTITY;
572        let basepoint_affine = AffinePoint::GENERATOR;
573        let basepoint_projective = ProjectivePoint::GENERATOR;
574
575        assert_eq!(identity + &basepoint_affine, basepoint_projective);
576        assert_eq!(
577            basepoint_projective + &basepoint_affine,
578            basepoint_projective + &basepoint_projective
579        );
580    }
581
582    #[test]
583    fn test_vector_repeated_add() {
584        let generator = ProjectivePoint::GENERATOR;
585        let mut p = generator;
586
587        for i in 0..ADD_TEST_VECTORS.len() {
588            let affine = p.to_affine();
589
590            let (expected_x, expected_y) = ADD_TEST_VECTORS[i];
591            assert_eq!(affine.x.to_bytes(), expected_x.into());
592            assert_eq!(affine.y.to_bytes(), expected_y.into());
593
594            p += &generator;
595        }
596    }
597
598    #[test]
599    fn test_vector_repeated_add_mixed() {
600        let generator = AffinePoint::GENERATOR;
601        let mut p = ProjectivePoint::GENERATOR;
602
603        for i in 0..ADD_TEST_VECTORS.len() {
604            let affine = p.to_affine();
605
606            let (expected_x, expected_y) = ADD_TEST_VECTORS[i];
607            assert_eq!(affine.x.to_bytes(), expected_x.into());
608            assert_eq!(affine.y.to_bytes(), expected_y.into());
609
610            p += &generator;
611        }
612    }
613
614    #[test]
615    fn test_vector_add_mixed_identity() {
616        let generator = ProjectivePoint::GENERATOR;
617        let p0 = generator + ProjectivePoint::IDENTITY;
618        let p1 = generator + AffinePoint::IDENTITY;
619        assert_eq!(p0, p1);
620    }
621
622    #[test]
623    fn test_vector_double_generator() {
624        let generator = ProjectivePoint::GENERATOR;
625        let mut p = generator;
626
627        for i in 0..2 {
628            let affine = p.to_affine();
629
630            let (expected_x, expected_y) = ADD_TEST_VECTORS[i];
631            assert_eq!(affine.x.to_bytes(), expected_x.into());
632            assert_eq!(affine.y.to_bytes(), expected_y.into());
633
634            p = p.double();
635        }
636    }
637
638    #[test]
639    fn projective_add_vs_double() {
640        let generator = ProjectivePoint::GENERATOR;
641        assert_eq!(generator + &generator, generator.double());
642    }
643
644    #[test]
645    fn projective_add_and_sub() {
646        let basepoint_affine = AffinePoint::GENERATOR;
647        let basepoint_projective = ProjectivePoint::GENERATOR;
648
649        assert_eq!(
650            (basepoint_projective + &basepoint_projective) - &basepoint_projective,
651            basepoint_projective
652        );
653        assert_eq!(
654            (basepoint_projective + &basepoint_affine) - &basepoint_affine,
655            basepoint_projective
656        );
657    }
658
659    #[test]
660    fn projective_double_and_sub() {
661        let generator = ProjectivePoint::GENERATOR;
662        assert_eq!(generator.double() - &generator, generator);
663    }
664
665    #[test]
666    fn test_vector_scalar_mult() {
667        let generator = ProjectivePoint::GENERATOR;
668
669        for (k, coords) in ADD_TEST_VECTORS
670            .iter()
671            .enumerate()
672            .map(|(k, coords)| (Scalar::from(k as u64 + 1), *coords))
673            .chain(
674                MUL_TEST_VECTORS
675                    .iter()
676                    .cloned()
677                    .map(|(k, x, y)| (Scalar::from_repr(k.into()).unwrap(), (x, y))),
678            )
679        {
680            let res = (generator * &k).to_affine();
681            assert_eq!(res.x.to_bytes(), coords.0.into());
682            assert_eq!(res.y.to_bytes(), coords.1.into());
683        }
684    }
685
686    #[test]
687    fn projective_identity_to_bytes() {
688        // This is technically an invalid SEC1 encoding, but is preferable to panicking.
689        assert_eq!([0; 33], ProjectivePoint::IDENTITY.to_bytes().as_slice());
690    }
691}
p256/arithmetic/projective.rs

p256/arithmetic/
projective.rs
