1 //! Simple verification of ECDSA signatures over SECP Random curves
5 pub(super) trait IntMod: Clone + Eq + Sized {
7 fn from_i(v: Self::I) -> Self;
8 fn from_modinv_of(v: Self::I) -> Result<Self, ()>;
13 fn mul(&self, o: &Self) -> Self;
14 fn square(&self) -> Self;
15 fn add(&self, o: &Self) -> Self;
16 fn sub(&self, o: &Self) -> Self;
17 fn double(&self) -> Self;
18 fn times_three(&self) -> Self;
19 fn times_four(&self) -> Self;
20 fn times_eight(&self) -> Self;
22 fn into_i(self) -> Self::I;
24 impl<M: PrimeModulus<U256> + Clone + Eq> IntMod for U256Mod<M> {
26 fn from_i(v: Self::I) -> Self { U256Mod::from_u256(v) }
27 fn from_modinv_of(v: Self::I) -> Result<Self, ()> { U256Mod::from_modinv_of(v) }
29 const ZERO: Self = U256Mod::<M>::from_u256_panicking(U256::zero());
30 const ONE: Self = U256Mod::<M>::from_u256_panicking(U256::one());
32 fn mul(&self, o: &Self) -> Self { self.mul(o) }
33 fn square(&self) -> Self { self.square() }
34 fn add(&self, o: &Self) -> Self { self.add(o) }
35 fn sub(&self, o: &Self) -> Self { self.sub(o) }
36 fn double(&self) -> Self { self.double() }
37 fn times_three(&self) -> Self { self.times_three() }
38 fn times_four(&self) -> Self { self.times_four() }
39 fn times_eight(&self) -> Self { self.times_eight() }
41 fn into_i(self) -> Self::I { self.into_u256() }
43 impl<M: PrimeModulus<U384> + Clone + Eq> IntMod for U384Mod<M> {
45 fn from_i(v: Self::I) -> Self { U384Mod::from_u384(v) }
46 fn from_modinv_of(v: Self::I) -> Result<Self, ()> { U384Mod::from_modinv_of(v) }
48 const ZERO: Self = U384Mod::<M>::from_u384_panicking(U384::zero());
49 const ONE: Self = U384Mod::<M>::from_u384_panicking(U384::one());
51 fn mul(&self, o: &Self) -> Self { self.mul(o) }
52 fn square(&self) -> Self { self.square() }
53 fn add(&self, o: &Self) -> Self { self.add(o) }
54 fn sub(&self, o: &Self) -> Self { self.sub(o) }
55 fn double(&self) -> Self { self.double() }
56 fn times_three(&self) -> Self { self.times_three() }
57 fn times_four(&self) -> Self { self.times_four() }
58 fn times_eight(&self) -> Self { self.times_eight() }
60 fn into_i(self) -> Self::I { self.into_u384() }
63 pub(super) trait Curve : Copy {
66 // With const generics, both CurveField and ScalarField can be replaced with a single IntMod.
67 type CurveField: IntMod<I = Self::Int>;
68 type ScalarField: IntMod<I = Self::Int>;
70 type CurveModulus: PrimeModulus<Self::Int>;
71 type ScalarModulus: PrimeModulus<Self::Int>;
73 // Curve parameters y^2 = x^3 + ax + b
74 const A: Self::CurveField;
75 const B: Self::CurveField;
80 #[derive(Clone, PartialEq, Eq)]
81 pub(super) struct Point<C: Curve + ?Sized> {
87 impl<C: Curve + ?Sized> Point<C> {
88 fn check_curve_conditions() {
89 debug_assert!(C::ScalarModulus::PRIME < C::CurveModulus::PRIME, "N is < P");
92 fn on_curve(x: &C::CurveField, y: &C::CurveField) -> Result<(), ()> {
94 let x_3 = x_2.mul(&x);
95 let v = x_3.add(&C::A.mul(&x)).add(&C::B);
105 #[cfg(debug_assertions)]
106 fn on_curve_z(x: &C::CurveField, y: &C::CurveField, z: &C::CurveField) -> Result<(), ()> {
107 let m = C::CurveField::from_modinv_of(z.clone().into_i())?;
108 let m_2 = m.square();
109 let m_3 = m_2.mul(&m);
110 let x_norm = x.mul(&m_2);
111 let y_norm = y.mul(&m_3);
112 Self::on_curve(&x_norm, &y_norm)
116 fn normalize_x(&self) -> Result<C::CurveField, ()> {
117 let m = C::CurveField::from_modinv_of(self.z.clone().into_i())?;
118 Ok(self.x.mul(&m.square()))
121 fn from_xy(x: C::Int, y: C::Int) -> Result<Self, ()> {
122 Self::check_curve_conditions();
124 let x = C::CurveField::from_i(x);
125 let y = C::CurveField::from_i(y);
126 Self::on_curve(&x, &y)?;
127 Ok(Point { x, y, z: C::CurveField::ONE })
130 pub(super) const fn from_xy_assuming_on_curve(x: C::CurveField, y: C::CurveField) -> Self {
131 Point { x, y, z: C::CurveField::ONE }
134 /// Checks that `expected_x` is equal to our X affine coordinate (without modular inversion).
135 fn eq_x(&self, expected_x: &C::ScalarField) -> Result<(), ()> {
136 // If x is between N and P the below calculations will fail and we'll spuriously reject a
137 // signature and the wycheproof tests will fail. We should in theory accept such
138 // signatures, but the probability of this happening at random is roughly 1/2^128, i.e. we
139 // really don't need to handle it in practice. Thus, we only bother to do this in tests.
140 debug_assert!(expected_x.clone().into_i() < C::CurveModulus::PRIME, "N is < P");
141 debug_assert!(C::ScalarModulus::PRIME < C::CurveModulus::PRIME, "N is < P");
142 #[cfg(debug_assertions)] {
143 // Check the above assertion - ensure the difference between the modulus of the scalar
144 // and curve fields is less than half the bit length of our integers, which are at
145 // least 256 bit long.
146 let scalar_mod_on_curve = C::CurveField::from_i(C::ScalarModulus::PRIME);
147 let diff = C::CurveField::ZERO.sub(&scalar_mod_on_curve);
148 assert!(C::Int::BYTES * 8 / 2 >= 128, "We assume 256-bit ints and longer");
149 assert!(C::CurveModulus::PRIME.limbs()[0] > (1 << 63), "PRIME should have the top bit set");
150 assert!(C::ScalarModulus::PRIME.limbs()[0] > (1 << 63), "PRIME should have the top bit set");
151 let mut half_bitlen = C::CurveField::ONE;
152 for _ in 0..C::Int::BYTES * 8 / 2 {
153 half_bitlen = half_bitlen.double();
155 assert!(diff.into_i() < half_bitlen.into_i());
158 #[allow(unused_mut, unused_assignments)]
159 let mut slow_check = None;
161 slow_check = Some(C::ScalarField::from_i(self.normalize_x()?.into_i()) == *expected_x);
164 let e: C::CurveField = C::CurveField::from_i(expected_x.clone().into_i());
165 if self.z == C::CurveField::ZERO { return Err(()); }
166 let ezz = e.mul(&self.z).mul(&self.z);
167 if self.x == ezz || slow_check == Some(true) { Ok(()) } else { Err(()) }
170 fn double(&self) -> Result<Self, ()> {
171 if self.y == C::CurveField::ZERO { return Err(()); }
172 if self.z == C::CurveField::ZERO { return Err(()); }
174 let s = self.x.times_four().mul(&self.y.square());
175 let z_2 = self.z.square();
176 let z_4 = z_2.square();
177 let y_2 = self.y.square();
178 let y_4 = y_2.square();
179 let x_2 = self.x.square();
180 let m = x_2.times_three().add(&C::A.mul(&z_4));
181 let x = m.square().sub(&s.double());
182 let y = m.mul(&s.sub(&x)).sub(&y_4.times_eight());
183 let z = self.y.double().mul(&self.z);
185 #[cfg(debug_assertions)] { assert!(Self::on_curve_z(&x, &y, &z).is_ok()); }
186 Ok(Point { x, y, z })
189 fn add(&self, o: &Self) -> Result<Self, ()> {
190 let o_z_2 = o.z.square();
191 let self_z_2 = self.z.square();
193 let u1 = self.x.mul(&o_z_2);
194 let u2 = o.x.mul(&self_z_2);
195 let s1 = self.y.mul(&o.z.mul(&o_z_2));
196 let s2 = o.y.mul(&self.z.mul(&self_z_2));
198 if s1 != s2 { /* Point at Infinity */ return Err(()); }
199 return self.double();
202 let h_2 = h.square();
203 let h_3 = h.mul(&h_2);
205 let x = r.square().sub(&h_3).sub(&u1.double().mul(&h_2));
206 let y = r.mul(&u1.mul(&h_2).sub(&x)).sub(&s1.mul(&h_3));
207 let z = h.mul(&self.z).mul(&o.z);
209 #[cfg(debug_assertions)] { assert!(Self::on_curve_z(&x, &y, &z).is_ok()); }
214 /// Calculates i * I + j * J
215 #[allow(non_snake_case)]
216 fn add_two_mul<C: Curve>(i: C::ScalarField, I: &Point<C>, j: C::ScalarField, J: &Point<C>) -> Result<Point<C>, ()> {
220 if i == C::Int::ZERO { /* Infinity */ return Err(()); }
221 if j == C::Int::ZERO { /* Infinity */ return Err(()); }
223 let mut res_opt: Result<Point<C>, ()> = Err(());
224 let i_limbs = i.limbs();
225 let j_limbs = j.limbs();
226 let mut skip_limb = 0;
227 let mut limbs_skip_iter = i_limbs.iter().zip(j_limbs.iter());
228 while limbs_skip_iter.next() == Some((&0, &0)) {
231 for (idx, (il, jl)) in i_limbs.iter().zip(j_limbs.iter()).skip(skip_limb).enumerate() {
232 let start_bit = if idx == 0 {
233 core::cmp::min(il.leading_zeros(), jl.leading_zeros())
235 for b in start_bit..64 {
236 let i_bit = (*il & (1 << (63 - b))) != 0;
237 let j_bit = (*jl & (1 << (63 - b))) != 0;
238 if let Ok(res) = res_opt.as_mut() {
239 *res = res.double()?;
242 if let Ok(res) = res_opt.as_mut() {
243 // The wycheproof tests expect to see signatures pass even if we hit Point at
244 // Infinity (PAI) on an intermediate result. While that's fine, I'm too lazy to
245 // go figure out if all our PAI definitions are right and the probability of
246 // this happening at random is, basically, the probability of guessing a private
247 // key anyway, so its not really worth actually handling outside of tests.
249 res_opt = res.add(I);
255 res_opt = Ok(I.clone());
259 if let Ok(res) = res_opt.as_mut() {
260 // The wycheproof tests expect to see signatures pass even if we hit Point at
261 // Infinity (PAI) on an intermediate result. While that's fine, I'm too lazy to
262 // go figure out if all our PAI definitions are right and the probability of
263 // this happening at random is, basically, the probability of guessing a private
264 // key anyway, so its not really worth actually handling outside of tests.
266 res_opt = res.add(J);
272 res_opt = Ok(J.clone());
280 /// Validates the given signature against the given public key and message digest.
281 pub(super) fn validate_ecdsa<C: Curve>(pk: &[u8], sig: &[u8], hash_input: &[u8]) -> Result<(), ()> {
282 #![allow(non_snake_case)]
284 if pk.len() != C::Int::BYTES * 2 { return Err(()); }
285 if sig.len() != C::Int::BYTES * 2 { return Err(()); }
287 let (r_bytes, s_bytes) = sig.split_at(C::Int::BYTES);
288 let (pk_x_bytes, pk_y_bytes) = pk.split_at(C::Int::BYTES);
290 let pk_x = C::Int::from_be_bytes(pk_x_bytes)?;
291 let pk_y = C::Int::from_be_bytes(pk_y_bytes)?;
292 let PK = Point::from_xy(pk_x, pk_y)?;
294 // from_i and from_modinv_of both will simply mod if the value is out of range. While its
295 // perfectly safe to do so, the wycheproof tests expect such signatures to be rejected, so we
297 let r_u256 = C::Int::from_be_bytes(r_bytes)?;
298 if r_u256 > C::ScalarModulus::PRIME { return Err(()); }
299 let s_u256 = C::Int::from_be_bytes(s_bytes)?;
300 if s_u256 > C::ScalarModulus::PRIME { return Err(()); }
302 let r = C::ScalarField::from_i(r_u256);
303 let s_inv = C::ScalarField::from_modinv_of(s_u256)?;
305 let z = C::ScalarField::from_i(C::Int::from_be_bytes(hash_input)?);
307 let u_a = z.mul(&s_inv);
308 let u_b = r.mul(&s_inv);
310 let V = add_two_mul(u_a, &C::G, u_b, &PK)?;