1 // Copyright 2015-2017 Brian Smith.
2 //
3 // Permission to use, copy, modify, and/or distribute this software for any
4 // purpose with or without fee is hereby granted, provided that the above
5 // copyright notice and this permission notice appear in all copies.
6 //
7 // THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHORS DISCLAIM ALL WARRANTIES
8 // WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
9 // MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY
10 // SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
11 // WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
12 // OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
13 // CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
14
15 //! Elliptic curve operations on the birationally equivalent curves Curve25519
16 //! and Edwards25519.
17
18 pub use super::scalar::{MaskedScalar, Scalar, SCALAR_LEN};
19 use crate::{
20 bssl, error,
21 limb::{Limb, LIMB_BITS},
22 };
23 use core::marker::PhantomData;
24
25 // Elem<T>` is `fe` in curve25519/internal.h.
26 // Elem<L> is `fe_loose` in curve25519/internal.h.
27 // Keep this in sync with curve25519/internal.h.
28 #[repr(C)]
29 pub struct Elem<E: Encoding> {
30 limbs: [Limb; ELEM_LIMBS], // This is called `v` in the C code.
31 encoding: PhantomData<E>,
32 }
33
34 pub trait Encoding {}
35 pub struct T;
36 impl Encoding for T {}
37
38 const ELEM_LIMBS: usize = 5 * 64 / LIMB_BITS;
39
40 impl<E: Encoding> Elem<E> {
zero() -> Self41 fn zero() -> Self {
42 Self {
43 limbs: Default::default(),
44 encoding: PhantomData,
45 }
46 }
47 }
48
49 impl Elem<T> {
negate(&mut self)50 fn negate(&mut self) {
51 unsafe {
52 GFp_x25519_fe_neg(self);
53 }
54 }
55 }
56
57 // An encoding of a curve point. If on Curve25519, it should be encoded as
58 // described in Section 5 of [RFC 7748]. If on Edwards25519, it should be
59 // encoded as described in section 5.1.2 of [RFC 8032].
60 //
61 // [RFC 7748] https://tools.ietf.org/html/rfc7748#section-5
62 // [RFC 8032] https://tools.ietf.org/html/rfc8032#section-5.1.2
63 pub type EncodedPoint = [u8; ELEM_LEN];
64 pub const ELEM_LEN: usize = 32;
65
66 // Keep this in sync with `ge_p3` in curve25519/internal.h.
67 #[repr(C)]
68 pub struct ExtPoint {
69 x: Elem<T>,
70 y: Elem<T>,
71 z: Elem<T>,
72 t: Elem<T>,
73 }
74
75 impl ExtPoint {
new_at_infinity() -> Self76 pub fn new_at_infinity() -> Self {
77 Self {
78 x: Elem::zero(),
79 y: Elem::zero(),
80 z: Elem::zero(),
81 t: Elem::zero(),
82 }
83 }
84
from_encoded_point_vartime(encoded: &EncodedPoint) -> Result<Self, error::Unspecified>85 pub fn from_encoded_point_vartime(encoded: &EncodedPoint) -> Result<Self, error::Unspecified> {
86 let mut point = Self::new_at_infinity();
87
88 Result::from(unsafe { GFp_x25519_ge_frombytes_vartime(&mut point, encoded) })
89 .map(|()| point)
90 }
91
into_encoded_point(self) -> EncodedPoint92 pub fn into_encoded_point(self) -> EncodedPoint {
93 encode_point(self.x, self.y, self.z)
94 }
95
invert_vartime(&mut self)96 pub fn invert_vartime(&mut self) {
97 self.x.negate();
98 self.t.negate();
99 }
100 }
101
102 // Keep this in sync with `ge_p2` in curve25519/internal.h.
103 #[repr(C)]
104 pub struct Point {
105 x: Elem<T>,
106 y: Elem<T>,
107 z: Elem<T>,
108 }
109
110 impl Point {
new_at_infinity() -> Self111 pub fn new_at_infinity() -> Self {
112 Self {
113 x: Elem::zero(),
114 y: Elem::zero(),
115 z: Elem::zero(),
116 }
117 }
118
into_encoded_point(self) -> EncodedPoint119 pub fn into_encoded_point(self) -> EncodedPoint {
120 encode_point(self.x, self.y, self.z)
121 }
122 }
123
encode_point(x: Elem<T>, y: Elem<T>, z: Elem<T>) -> EncodedPoint124 fn encode_point(x: Elem<T>, y: Elem<T>, z: Elem<T>) -> EncodedPoint {
125 let mut bytes = [0; ELEM_LEN];
126
127 let sign_bit: u8 = unsafe {
128 let mut recip = Elem::zero();
129 GFp_x25519_fe_invert(&mut recip, &z);
130
131 let mut x_over_z = Elem::zero();
132 GFp_x25519_fe_mul_ttt(&mut x_over_z, &x, &recip);
133
134 let mut y_over_z = Elem::zero();
135 GFp_x25519_fe_mul_ttt(&mut y_over_z, &y, &recip);
136 GFp_x25519_fe_tobytes(&mut bytes, &y_over_z);
137
138 GFp_x25519_fe_isnegative(&x_over_z)
139 };
140
141 // The preceding computations must execute in constant time, but this
142 // doesn't need to.
143 bytes[ELEM_LEN - 1] ^= sign_bit << 7;
144
145 bytes
146 }
147
148 extern "C" {
GFp_x25519_fe_invert(out: &mut Elem<T>, z: &Elem<T>)149 fn GFp_x25519_fe_invert(out: &mut Elem<T>, z: &Elem<T>);
GFp_x25519_fe_isnegative(elem: &Elem<T>) -> u8150 fn GFp_x25519_fe_isnegative(elem: &Elem<T>) -> u8;
GFp_x25519_fe_mul_ttt(h: &mut Elem<T>, f: &Elem<T>, g: &Elem<T>)151 fn GFp_x25519_fe_mul_ttt(h: &mut Elem<T>, f: &Elem<T>, g: &Elem<T>);
GFp_x25519_fe_neg(f: &mut Elem<T>)152 fn GFp_x25519_fe_neg(f: &mut Elem<T>);
GFp_x25519_fe_tobytes(bytes: &mut EncodedPoint, elem: &Elem<T>)153 fn GFp_x25519_fe_tobytes(bytes: &mut EncodedPoint, elem: &Elem<T>);
GFp_x25519_ge_frombytes_vartime(h: &mut ExtPoint, s: &EncodedPoint) -> bssl::Result154 fn GFp_x25519_ge_frombytes_vartime(h: &mut ExtPoint, s: &EncodedPoint) -> bssl::Result;
155 }
156