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 || slow_check == Some(true) { Ok(()) } else { Err(()) }
148 fn double(&self) -> Result<Self, ()> {
149 if self.y == C::IntModP::ZERO { return Err(()); }
150 if self.z == C::IntModP::ZERO { return Err(()); }
152 let s = self.x.times_four().mul(&self.y.square());
153 let z_2 = self.z.square();
154 let z_4 = z_2.square();
155 let y_2 = self.y.square();
156 let y_4 = y_2.square();
157 let x_2 = self.x.square();
158 let m = x_2.times_three().add(&C::A.mul(&z_4));
159 let x = m.square().sub(&s.double());
160 let y = m.mul(&s.sub(&x)).sub(&y_4.times_eight());
161 let z = self.y.double().mul(&self.z);
163 #[cfg(debug_assertions)] { assert!(Self::on_curve_z(&x, &y, &z).is_ok()); }
164 Ok(Point { x, y, z })
167 fn add(&self, o: &Self) -> Result<Self, ()> {
168 let o_z_2 = o.z.square();
169 let self_z_2 = self.z.square();
171 let u1 = self.x.mul(&o_z_2);
172 let u2 = o.x.mul(&self_z_2);
173 let s1 = self.y.mul(&o.z.mul(&o_z_2));
174 let s2 = o.y.mul(&self.z.mul(&self_z_2));
176 if s1 != s2 { /* PAI */ return Err(()); }
177 return self.double();
180 let h_2 = h.square();
181 let h_3 = h.mul(&h_2);
183 let x = r.square().sub(&h_3).sub(&u1.double().mul(&h_2));
184 let y = r.mul(&u1.mul(&h_2).sub(&x)).sub(&s1.mul(&h_3));
185 let z = h.mul(&self.z).mul(&o.z);
187 #[cfg(debug_assertions)] { assert!(Self::on_curve_z(&x, &y, &z).is_ok()); }
192 /// Calculates i * I + j * J
193 #[allow(non_snake_case)]
194 fn add_two_mul<C: Curve>(i: C::IntModN, I: &Point<C>, j: C::IntModN, J: &Point<C>) -> Result<Point<C>, ()> {
198 if i == C::Int::ZERO { /* Infinity */ return Err(()); }
199 if j == C::Int::ZERO { /* Infinity */ return Err(()); }
201 let mut res_opt: Result<Point<C>, ()> = Err(());
202 let i_limbs = i.limbs();
203 let j_limbs = j.limbs();
204 let mut skip_limb = 0;
205 let mut limbs_skip_iter = i_limbs.iter().zip(j_limbs.iter());
206 while limbs_skip_iter.next() == Some((&0, &0)) {
209 for (idx, (il, jl)) in i_limbs.iter().zip(j_limbs.iter()).skip(skip_limb).enumerate() {
210 let start_bit = if idx == 0 {
211 core::cmp::min(il.leading_zeros(), jl.leading_zeros())
213 for b in start_bit..64 {
214 let i_bit = (*il & (1 << (63 - b))) != 0;
215 let j_bit = (*jl & (1 << (63 - b))) != 0;
216 if let Ok(res) = res_opt.as_mut() {
217 *res = res.double()?;
220 if let Ok(res) = res_opt.as_mut() {
221 // The wycheproof tests expect to see signatures pass even if we hit PAI on an
222 // intermediate result. While that's fine, I'm too lazy to go figure out if all
223 // our PAI definitions are right and the probability of this happening at
224 // random is, basically, the probability of guessing a private key anyway, so
225 // its not really worth actually handling outside of tests.
227 res_opt = res.add(I);
233 res_opt = Ok(I.clone());
237 if let Ok(res) = res_opt.as_mut() {
238 // The wycheproof tests expect to see signatures pass even if we hit PAI on an
239 // intermediate result. While that's fine, I'm too lazy to go figure out if all
240 // our PAI definitions are right and the probability of this happening at
241 // random is, basically, the probability of guessing a private key anyway, so
242 // its not really worth actually handling outside of tests.
244 res_opt = res.add(J);
250 res_opt = Ok(J.clone());
258 /// Validates the given signature against the given public key and message digest.
259 pub(super) fn validate_ecdsa<C: Curve>(pk: &[u8], sig: &[u8], hash_input: &[u8]) -> Result<(), ()> {
260 #![allow(non_snake_case)]
262 if pk.len() != C::Int::BYTES * 2 { return Err(()); }
263 if sig.len() != C::Int::BYTES * 2 { return Err(()); }
265 let (r_bytes, s_bytes) = sig.split_at(C::Int::BYTES);
266 let (pk_x_bytes, pk_y_bytes) = pk.split_at(C::Int::BYTES);
268 let pk_x = C::Int::from_be_bytes(pk_x_bytes)?;
269 let pk_y = C::Int::from_be_bytes(pk_y_bytes)?;
270 let PK = Point::from_xy(pk_x, pk_y)?;
272 // from_i and from_modinv_of both will simply mod if the value is out of range. While its
273 // perfectly safe to do so, the wycheproof tests expect such signatures to be rejected, so we
275 let r_u256 = C::Int::from_be_bytes(r_bytes)?;
276 if r_u256 > C::N::PRIME { return Err(()); }
277 let s_u256 = C::Int::from_be_bytes(s_bytes)?;
278 if s_u256 > C::N::PRIME { return Err(()); }
280 let r = C::IntModN::from_i(r_u256);
281 let s_inv = C::IntModN::from_modinv_of(s_u256)?;
283 let z = C::IntModN::from_i(C::Int::from_be_bytes(hash_input)?);
285 let u_a = z.mul(&s_inv);
286 let u_b = r.mul(&s_inv);
288 let V = add_two_mul(u_a, &C::G, u_b, &PK)?;