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 IntModP and IntModN can be replaced with a single IntMod.
67 type IntModP: IntMod<I = Self::Int>;
68 type IntModN: IntMod<I = Self::Int>;
70 type P: PrimeModulus<Self::Int>;
71 type N: PrimeModulus<Self::Int>;
73 // Curve parameters y^2 = x^3 + ax + b
74 const A: Self::IntModP;
75 const B: Self::IntModP;
80 #[derive(Clone, PartialEq, Eq)]
81 pub(super) struct Point<C: Curve + ?Sized> {
87 impl<C: Curve + ?Sized> Point<C> {
88 fn on_curve(x: &C::IntModP, y: &C::IntModP) -> Result<(), ()> {
90 let x_3 = x_2.mul(&x);
91 let v = x_3.add(&C::A.mul(&x)).add(&C::B);
101 #[cfg(debug_assertions)]
102 fn on_curve_z(x: &C::IntModP, y: &C::IntModP, z: &C::IntModP) -> Result<(), ()> {
103 let m = C::IntModP::from_modinv_of(z.clone().into_i())?;
104 let m_2 = m.square();
105 let m_3 = m_2.mul(&m);
106 let x_norm = x.mul(&m_2);
107 let y_norm = y.mul(&m_3);
108 Self::on_curve(&x_norm, &y_norm)
112 fn normalize_x(&self) -> Result<C::IntModP, ()> {
113 let m = C::IntModP::from_modinv_of(self.z.clone().into_i())?;
114 Ok(self.x.mul(&m.square()))
117 fn from_xy(x: C::Int, y: C::Int) -> Result<Self, ()> {
118 let x = C::IntModP::from_i(x);
119 let y = C::IntModP::from_i(y);
120 Self::on_curve(&x, &y)?;
121 Ok(Point { x, y, z: C::IntModP::ONE })
124 pub(super) const fn from_xy_assuming_on_curve(x: C::IntModP, y: C::IntModP) -> Self {
125 Point { x, y, z: C::IntModP::ONE }
128 /// Checks that `expected_x` is equal to our X affine coordinate (without modular inversion).
129 fn eq_x(&self, expected_x: &C::IntModN) -> Result<(), ()> {
130 debug_assert!(expected_x.clone().into_i() < C::P::PRIME, "N is < P");
132 // If x is between N and P the below calculations will fail and we'll spuriously reject a
133 // signature and the wycheproof tests will fail. We should in theory accept such
134 // signatures, but the probability of this happening at random is roughly 1/2^128, i.e. we
135 // really don't need to handle it in practice. Thus, we only bother to do this in tests.
136 #[allow(unused_mut, unused_assignments)]
137 let mut slow_check = None;
139 slow_check = Some(C::IntModN::from_i(self.normalize_x()?.into_i()) == *expected_x);
142 let e: C::IntModP = C::IntModP::from_i(expected_x.clone().into_i());
143 if self.z == C::IntModP::ZERO { return Err(()); }
144 let ezz = e.mul(&self.z).mul(&self.z);
145 if self.x == ezz { Ok(()) } else {
146 if slow_check == Some(true) { Ok(()) } else { Err(()) }
150 fn double(&self) -> Result<Self, ()> {
151 if self.y == C::IntModP::ZERO { return Err(()); }
152 if self.z == C::IntModP::ZERO { return Err(()); }
154 let s = self.x.times_four().mul(&self.y.square());
155 let z_2 = self.z.square();
156 let z_4 = z_2.square();
157 let y_2 = self.y.square();
158 let y_4 = y_2.square();
159 let x_2 = self.x.square();
160 let m = x_2.times_three().add(&C::A.mul(&z_4));
161 let x = m.square().sub(&s.double());
162 let y = m.mul(&s.sub(&x)).sub(&y_4.times_eight());
163 let z = self.y.double().mul(&self.z);
165 #[cfg(debug_assertions)] { assert!(Self::on_curve_z(&x, &y, &z).is_ok()); }
166 Ok(Point { x, y, z })
169 fn add(&self, o: &Self) -> Result<Self, ()> {
170 let o_z_2 = o.z.square();
171 let self_z_2 = self.z.square();
173 let u1 = self.x.mul(&o_z_2);
174 let u2 = o.x.mul(&self_z_2);
175 let s1 = self.y.mul(&o.z.mul(&o_z_2));
176 let s2 = o.y.mul(&self.z.mul(&self_z_2));
178 if s1 != s2 { /* PAI */ return Err(()); }
179 return self.double();
182 let h_2 = h.square();
183 let h_3 = h.mul(&h_2);
185 let x = r.square().sub(&h_3).sub(&u1.double().mul(&h_2));
186 let y = r.mul(&u1.mul(&h_2).sub(&x)).sub(&s1.mul(&h_3));
187 let z = h.mul(&self.z).mul(&o.z);
189 #[cfg(debug_assertions)] { assert!(Self::on_curve_z(&x, &y, &z).is_ok()); }
194 /// Calculates i * I + j * J
195 #[allow(non_snake_case)]
196 fn add_two_mul<C: Curve>(i: C::IntModN, I: &Point<C>, j: C::IntModN, J: &Point<C>) -> Result<Point<C>, ()> {
200 if i == C::Int::ZERO { /* Infinity */ return Err(()); }
201 if j == C::Int::ZERO { /* Infinity */ return Err(()); }
203 let mut res_opt: Result<Point<C>, ()> = Err(());
204 let i_limbs = i.limbs();
205 let j_limbs = j.limbs();
206 let mut skip_limb = 0;
207 let mut limbs_skip_iter = i_limbs.iter().zip(j_limbs.iter());
208 while limbs_skip_iter.next() == Some((&0, &0)) {
211 for (idx, (il, jl)) in i_limbs.iter().zip(j_limbs.iter()).skip(skip_limb).enumerate() {
212 let start_bit = if idx == 0 {
213 core::cmp::min(il.leading_zeros(), jl.leading_zeros())
215 for b in start_bit..64 {
216 let i_bit = (*il & (1 << (63 - b))) != 0;
217 let j_bit = (*jl & (1 << (63 - b))) != 0;
218 if let Ok(res) = res_opt.as_mut() {
219 *res = res.double()?;
222 if let Ok(res) = res_opt.as_mut() {
223 // The wycheproof tests expect to see signatures pass even if we hit PAI on an
224 // intermediate result. While that's fine, I'm too lazy to go figure out if all
225 // our PAI definitions are right and the probability of this happening at
226 // random is, basically, the probability of guessing a private key anyway, so
227 // its not really worth actually handling outside of tests.
229 res_opt = res.add(I);
235 res_opt = Ok(I.clone());
239 if let Ok(res) = res_opt.as_mut() {
240 // The wycheproof tests expect to see signatures pass even if we hit PAI on an
241 // intermediate result. While that's fine, I'm too lazy to go figure out if all
242 // our PAI definitions are right and the probability of this happening at
243 // random is, basically, the probability of guessing a private key anyway, so
244 // its not really worth actually handling outside of tests.
246 res_opt = res.add(J);
252 res_opt = Ok(J.clone());
260 /// Validates the given signature against the given public key and message digest.
261 pub(super) fn validate_ecdsa<C: Curve>(pk: &[u8], sig: &[u8], hash_input: &[u8]) -> Result<(), ()> {
262 #![allow(non_snake_case)]
264 if pk.len() != C::Int::BYTES * 2 { return Err(()); }
265 if sig.len() != C::Int::BYTES * 2 { return Err(()); }
267 let (r_bytes, s_bytes) = sig.split_at(C::Int::BYTES);
268 let (pk_x_bytes, pk_y_bytes) = pk.split_at(C::Int::BYTES);
270 let pk_x = C::Int::from_be_bytes(pk_x_bytes)?;
271 let pk_y = C::Int::from_be_bytes(pk_y_bytes)?;
272 let PK = Point::from_xy(pk_x, pk_y)?;
274 // from_i and from_modinv_of both will simply mod if the value is out of range. While its
275 // perfectly safe to do so, the wycheproof tests expect such signatures to be rejected, so we
277 let r_u256 = C::Int::from_be_bytes(r_bytes)?;
278 if r_u256 > C::N::PRIME { return Err(()); }
279 let s_u256 = C::Int::from_be_bytes(s_bytes)?;
280 if s_u256 > C::N::PRIME { return Err(()); }
282 let r = C::IntModN::from_i(r_u256);
283 let s_inv = C::IntModN::from_modinv_of(s_u256)?;
285 let z = C::IntModN::from_i(C::Int::from_be_bytes(hash_input)?);
287 let u_a = z.mul(&s_inv);
288 let u_b = r.mul(&s_inv);
290 let V = add_two_mul(u_a, &C::G, u_b, &PK)?;