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, c, cpu, 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> { |
41 | fn zero() -> Self { |
42 | Self { |
43 | limbs: Default::default(), |
44 | encoding: PhantomData, |
45 | } |
46 | } |
47 | } |
48 | |
49 | impl Elem<T> { |
50 | fn negate(&mut self) { |
51 | unsafe { |
52 | 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 { |
76 | // Returns the result of multiplying the base point by the scalar in constant time. |
77 | pub(super) fn from_scalarmult_base_consttime(scalar: &Scalar, cpu: cpu::Features) -> Self { |
78 | let mut r = Self { |
79 | x: Elem::zero(), |
80 | y: Elem::zero(), |
81 | z: Elem::zero(), |
82 | t: Elem::zero(), |
83 | }; |
84 | prefixed_extern! { |
85 | fn x25519_ge_scalarmult_base(h: &mut ExtPoint, a: &Scalar, has_fe25519_adx: c::int); |
86 | } |
87 | unsafe { |
88 | x25519_ge_scalarmult_base(&mut r, scalar, has_fe25519_adx(cpu).into()); |
89 | } |
90 | r |
91 | } |
92 | |
93 | pub fn from_encoded_point_vartime(encoded: &EncodedPoint) -> Result<Self, error::Unspecified> { |
94 | let mut point = Self { |
95 | x: Elem::zero(), |
96 | y: Elem::zero(), |
97 | z: Elem::zero(), |
98 | t: Elem::zero(), |
99 | }; |
100 | |
101 | Result::from(unsafe { x25519_ge_frombytes_vartime(&mut point, encoded) }).map(|()| point) |
102 | } |
103 | |
104 | pub fn into_encoded_point(self) -> EncodedPoint { |
105 | encode_point(self.x, self.y, self.z) |
106 | } |
107 | |
108 | pub fn invert_vartime(&mut self) { |
109 | self.x.negate(); |
110 | self.t.negate(); |
111 | } |
112 | } |
113 | |
114 | // Keep this in sync with `ge_p2` in curve25519/internal.h. |
115 | #[repr (C)] |
116 | pub struct Point { |
117 | x: Elem<T>, |
118 | y: Elem<T>, |
119 | z: Elem<T>, |
120 | } |
121 | |
122 | impl Point { |
123 | pub fn new_at_infinity() -> Self { |
124 | Self { |
125 | x: Elem::zero(), |
126 | y: Elem::zero(), |
127 | z: Elem::zero(), |
128 | } |
129 | } |
130 | |
131 | pub fn into_encoded_point(self) -> EncodedPoint { |
132 | encode_point(self.x, self.y, self.z) |
133 | } |
134 | } |
135 | |
136 | fn encode_point(x: Elem<T>, y: Elem<T>, z: Elem<T>) -> EncodedPoint { |
137 | let mut bytes: [u8; 32] = [0; ELEM_LEN]; |
138 | |
139 | let sign_bit: u8 = unsafe { |
140 | let mut recip: Elem = Elem::zero(); |
141 | x25519_fe_invert(&mut recip, &z); |
142 | |
143 | let mut x_over_z: Elem = Elem::zero(); |
144 | x25519_fe_mul_ttt(&mut x_over_z, &x, &recip); |
145 | |
146 | let mut y_over_z: Elem = Elem::zero(); |
147 | x25519_fe_mul_ttt(&mut y_over_z, &y, &recip); |
148 | x25519_fe_tobytes(&mut bytes, &y_over_z); |
149 | |
150 | x25519_fe_isnegative(&x_over_z) |
151 | }; |
152 | |
153 | // The preceding computations must execute in constant time, but this |
154 | // doesn't need to. |
155 | bytes[ELEM_LEN - 1] ^= sign_bit << 7; |
156 | |
157 | bytes |
158 | } |
159 | |
160 | cfg_if::cfg_if! { |
161 | if #[cfg(all(target_arch = "x86_64" , not(target_os = "windows" )))] { |
162 | #[inline (always)] |
163 | pub(super) fn has_fe25519_adx(cpu: cpu::Features) -> bool { |
164 | cpu::intel::ADX.available(cpu) |
165 | && cpu::intel::BMI1.available(cpu) |
166 | && cpu::intel::BMI2.available(cpu) |
167 | } |
168 | } else { |
169 | #[inline (always)] |
170 | pub (super) fn has_fe25519_adx(_cpu: cpu::Features) -> bool { |
171 | false |
172 | } |
173 | } |
174 | } |
175 | |
176 | prefixed_extern! { |
177 | fn x25519_fe_invert(out: &mut Elem<T>, z: &Elem<T>); |
178 | fn x25519_fe_isnegative(elem: &Elem<T>) -> u8; |
179 | fn x25519_fe_mul_ttt(h: &mut Elem<T>, f: &Elem<T>, g: &Elem<T>); |
180 | fn x25519_fe_neg(f: &mut Elem<T>); |
181 | fn x25519_fe_tobytes(bytes: &mut EncodedPoint, elem: &Elem<T>); |
182 | fn x25519_ge_frombytes_vartime(h: &mut ExtPoint, s: &EncodedPoint) -> bssl::Result; |
183 | } |
184 | |