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 /// A Point, stored in Jacobian coordinates
82 pub(super) struct Point<C: Curve + ?Sized> {
88 impl<C: Curve + ?Sized> Point<C> {
89 fn check_curve_conditions() {
90 debug_assert!(C::ScalarModulus::PRIME < C::CurveModulus::PRIME, "N is < P");
93 fn on_curve(x: &C::CurveField, y: &C::CurveField) -> Result<(), ()> {
95 let x_3 = x_2.mul(&x);
96 let v = x_3.add(&C::A.mul(&x)).add(&C::B);
106 #[cfg(debug_assertions)]
107 fn on_curve_z(x: &C::CurveField, y: &C::CurveField, z: &C::CurveField) -> Result<(), ()> {
112 let m = C::CurveField::from_modinv_of(z.clone().into_i())?;
113 let m_2 = m.square();
114 let m_3 = m_2.mul(&m);
115 let x_norm = x.mul(&m_2);
116 let y_norm = y.mul(&m_3);
117 Self::on_curve(&x_norm, &y_norm)
121 fn normalize_x(&self) -> Result<C::CurveField, ()> {
122 let m = C::CurveField::from_modinv_of(self.z.clone().into_i())?;
123 Ok(self.x.mul(&m.square()))
126 fn from_xy(x: C::Int, y: C::Int) -> Result<Self, ()> {
127 Self::check_curve_conditions();
129 let x = C::CurveField::from_i(x);
130 let y = C::CurveField::from_i(y);
131 Self::on_curve(&x, &y)?;
132 Ok(Point { x, y, z: C::CurveField::ONE })
135 pub(super) const fn from_xy_assuming_on_curve(x: C::CurveField, y: C::CurveField) -> Self {
136 Point { x, y, z: C::CurveField::ONE }
139 /// Checks that `expected_x` is equal to our X affine coordinate (without modular inversion).
140 fn eq_x(&self, expected_x: &C::ScalarField) -> Result<(), ()> {
141 // If x is between N and P the below calculations will fail and we'll spuriously reject a
142 // signature and the wycheproof tests will fail. We should in theory accept such
143 // signatures, but the probability of this happening at random is roughly 1/2^128, i.e. we
144 // really don't need to handle it in practice. Thus, we only bother to do this in tests.
145 debug_assert!(expected_x.clone().into_i() < C::CurveModulus::PRIME, "N is < P");
146 debug_assert!(C::ScalarModulus::PRIME < C::CurveModulus::PRIME, "N is < P");
147 #[cfg(debug_assertions)] {
148 // Check the above assertion - ensure the difference between the modulus of the scalar
149 // and curve fields is less than half the bit length of our integers, which are at
150 // least 256 bit long.
151 let scalar_mod_on_curve = C::CurveField::from_i(C::ScalarModulus::PRIME);
152 let diff = C::CurveField::ZERO.sub(&scalar_mod_on_curve);
153 assert!(C::Int::BYTES * 8 / 2 >= 128, "We assume 256-bit ints and longer");
154 assert!(C::CurveModulus::PRIME.limbs()[0] > (1 << 63), "PRIME should have the top bit set");
155 assert!(C::ScalarModulus::PRIME.limbs()[0] > (1 << 63), "PRIME should have the top bit set");
156 let mut half_bitlen = C::CurveField::ONE;
157 for _ in 0..C::Int::BYTES * 8 / 2 {
158 half_bitlen = half_bitlen.double();
160 assert!(diff.into_i() < half_bitlen.into_i());
163 #[allow(unused_mut, unused_assignments)]
164 let mut slow_check = None;
166 slow_check = Some(C::ScalarField::from_i(self.normalize_x()?.into_i()) == *expected_x);
169 let e: C::CurveField = C::CurveField::from_i(expected_x.clone().into_i());
170 if self.z == C::CurveField::ZERO { return Err(()); }
171 let ezz = e.mul(&self.z).mul(&self.z);
172 if self.x == ezz || slow_check == Some(true) { Ok(()) } else { Err(()) }
175 fn double(&self) -> Result<Self, ()> {
176 if self.y == C::CurveField::ZERO { return Err(()); }
177 if self.z == C::CurveField::ZERO { return Err(()); }
179 // https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-2001-b
183 // alpha = 3*(X1-delta)*(X1+delta)
184 // X3 = alpha^2-8*beta
185 // Z3 = (Y1+Z1)^2-gamma-delta
186 // Y3 = alpha*(4*beta-X3)-8*gamma^2
188 let delta = self.z.square();
189 let gamma = self.y.square();
190 let beta = self.x.mul(&gamma);
191 let alpha = self.x.sub(&delta).times_three().mul(&self.x.add(&delta));
192 let x = alpha.square().sub(&beta.times_eight());
193 let y = alpha.mul(&beta.times_four().sub(&x)).sub(&gamma.square().times_eight());
194 let z = self.y.add(&self.z).square().sub(&gamma).sub(&delta);
196 #[cfg(debug_assertions)] { assert!(Self::on_curve_z(&x, &y, &z).is_ok()); }
197 Ok(Point { x, y, z })
200 fn add(&self, o: &Self) -> Result<Self, ()> {
201 // https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-2007-bl
214 // Y3 = r*(V-X3)-2*S1*J
215 // Z3 = ((Z1+Z2)^2-Z1Z1-Z2Z2)*H
217 let o_z_2 = o.z.square();
218 let self_z_2 = self.z.square();
220 let u1 = self.x.mul(&o_z_2);
221 let u2 = o.x.mul(&self_z_2);
222 let s1 = self.y.mul(&o.z.mul(&o_z_2));
223 let s2 = o.y.mul(&self.z.mul(&self_z_2));
225 if s1 != s2 { /* Point at Infinity */ return Err(()); }
226 return self.double();
229 let i = h.double().square();
231 let r = s2.sub(&s1).double();
233 let x = r.square().sub(&j).sub(&v.double());
234 let y = r.mul(&v.sub(&x)).sub(&s1.double().mul(&j));
235 let z = self.z.add(&o.z).square().sub(&self_z_2).sub(&o_z_2).mul(&h);
237 #[cfg(debug_assertions)] { assert!(Self::on_curve_z(&x, &y, &z).is_ok()); }
242 /// Calculates i * I + j * J
243 #[allow(non_snake_case)]
244 fn add_two_mul<C: Curve>(i: C::ScalarField, I: &Point<C>, j: C::ScalarField, J: &Point<C>) -> Result<Point<C>, ()> {
248 if i == C::Int::ZERO { /* Infinity */ return Err(()); }
249 if j == C::Int::ZERO { /* Infinity */ return Err(()); }
251 let mut res_opt: Result<Point<C>, ()> = Err(());
252 let i_limbs = i.limbs();
253 let j_limbs = j.limbs();
254 let mut skip_limb = 0;
255 let mut limbs_skip_iter = i_limbs.iter().zip(j_limbs.iter());
256 while limbs_skip_iter.next() == Some((&0, &0)) {
259 for (idx, (il, jl)) in i_limbs.iter().zip(j_limbs.iter()).skip(skip_limb).enumerate() {
260 let start_bit = if idx == 0 {
261 core::cmp::min(il.leading_zeros(), jl.leading_zeros())
263 for b in start_bit..64 {
264 let i_bit = (*il & (1 << (63 - b))) != 0;
265 let j_bit = (*jl & (1 << (63 - b))) != 0;
266 if let Ok(res) = res_opt.as_mut() {
267 *res = res.double()?;
270 if let Ok(res) = res_opt.as_mut() {
271 // The wycheproof tests expect to see signatures pass even if we hit Point at
272 // Infinity (PAI) on an intermediate result. While that's fine, I'm too lazy to
273 // go figure out if all our PAI definitions are right and the probability of
274 // this happening at random is, basically, the probability of guessing a private
275 // key anyway, so its not really worth actually handling outside of tests.
277 res_opt = res.add(I);
283 res_opt = Ok(I.clone());
287 if let Ok(res) = res_opt.as_mut() {
288 // The wycheproof tests expect to see signatures pass even if we hit Point at
289 // Infinity (PAI) on an intermediate result. While that's fine, I'm too lazy to
290 // go figure out if all our PAI definitions are right and the probability of
291 // this happening at random is, basically, the probability of guessing a private
292 // key anyway, so its not really worth actually handling outside of tests.
294 res_opt = res.add(J);
300 res_opt = Ok(J.clone());
308 /// Validates the given signature against the given public key and message digest.
309 pub(super) fn validate_ecdsa<C: Curve>(pk: &[u8], sig: &[u8], hash_input: &[u8]) -> Result<(), ()> {
310 #![allow(non_snake_case)]
312 if pk.len() != C::Int::BYTES * 2 { return Err(()); }
313 if sig.len() != C::Int::BYTES * 2 { return Err(()); }
315 let (r_bytes, s_bytes) = sig.split_at(C::Int::BYTES);
316 let (pk_x_bytes, pk_y_bytes) = pk.split_at(C::Int::BYTES);
318 let pk_x = C::Int::from_be_bytes(pk_x_bytes)?;
319 let pk_y = C::Int::from_be_bytes(pk_y_bytes)?;
320 let PK = Point::from_xy(pk_x, pk_y)?;
322 // from_i and from_modinv_of both will simply mod if the value is out of range. While its
323 // perfectly safe to do so, the wycheproof tests expect such signatures to be rejected, so we
325 let r_u256 = C::Int::from_be_bytes(r_bytes)?;
326 if r_u256 > C::ScalarModulus::PRIME { return Err(()); }
327 let s_u256 = C::Int::from_be_bytes(s_bytes)?;
328 if s_u256 > C::ScalarModulus::PRIME { return Err(()); }
330 let r = C::ScalarField::from_i(r_u256);
331 let s_inv = C::ScalarField::from_modinv_of(s_u256)?;
333 let z = C::ScalarField::from_i(C::Int::from_be_bytes(hash_input)?);
335 let u_a = z.mul(&s_inv);
336 let u_b = r.mul(&s_inv);
338 let V = add_two_mul(u_a, &C::G, u_b, &PK)?;