_ Git - dnssec-prover/blob - src/crypto/ec.rs

   1 //! Simple verification of ECDSA signatures over SECP Random curves
   2
   3 use super::bigint::*;
   4
   5 pub(super) trait IntMod: Clone + Eq + Sized {
   6         type I: Int;
   7         fn from_i(v: Self::I) -> Self;
   8         fn from_modinv_of(v: Self::I) -> Result<Self, ()>;
   9
  10         const ZERO: Self;
  11         const ONE: Self;
  12
  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;
  21
  22         fn into_i(self) -> Self::I;
  23 }
  24 impl<M: PrimeModulus<U256> + Clone + Eq> IntMod for U256Mod<M> {
  25         type I = U256;
  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) }
  28
  29         const ZERO: Self = U256Mod::<M>::from_u256_panicking(U256::zero());
  30         const ONE: Self = U256Mod::<M>::from_u256_panicking(U256::one());
  31
  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() }
  40
  41         fn into_i(self) -> Self::I { self.into_u256() }
  42 }
  43 impl<M: PrimeModulus<U384> + Clone + Eq> IntMod for U384Mod<M> {
  44         type I = U384;
  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) }
  47
  48         const ZERO: Self = U384Mod::<M>::from_u384_panicking(U384::zero());
  49         const ONE: Self = U384Mod::<M>::from_u384_panicking(U384::one());
  50
  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() }
  59
  60         fn into_i(self) -> Self::I { self.into_u384() }
  61 }
  62
  63 pub(super) trait Curve : Copy {
  64         type Int: Int;
  65
  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>;
  69
  70         type CurveModulus: PrimeModulus<Self::Int>;
  71         type ScalarModulus: PrimeModulus<Self::Int>;
  72
  73         // Curve parameters y^2 = x^3 + ax + b
  74         const A: Self::CurveField;
  75         const B: Self::CurveField;
  76
  77         const G: Point<Self>;
  78 }
  79
  80 #[derive(Clone, PartialEq, Eq)]
  81 pub(super) struct Point<C: Curve + ?Sized> {
  82         x: C::CurveField,
  83         y: C::CurveField,
  84         z: C::CurveField,
  85 }
  86
  87 impl<C: Curve + ?Sized> Point<C> {
  88         fn check_curve_conditions() {
  89                 debug_assert!(C::ScalarModulus::PRIME < C::CurveModulus::PRIME, "N is < P");
  90         }
  91
  92         fn on_curve(x: &C::CurveField, y: &C::CurveField) -> Result<(), ()> {
  93                 let x_2 = x.square();
  94                 let x_3 = x_2.mul(&x);
  95                 let v = x_3.add(&C::A.mul(&x)).add(&C::B);
  96
  97                 let y_2 = y.square();
  98                 if y_2 != v {
  99                         Err(())
 100                 } else {
 101                         Ok(())
 102                 }
 103         }
 104
 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)
 113         }
 114
 115         #[cfg(test)]
 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()))
 119         }
 120
 121         fn from_xy(x: C::Int, y: C::Int) -> Result<Self, ()> {
 122                 Self::check_curve_conditions();
 123
 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 })
 128         }
 129
 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 }
 132         }
 133
 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();
 154                         }
 155                         assert!(diff.into_i() < half_bitlen.into_i());
 156                 }
 157
 158                 #[allow(unused_mut, unused_assignments)]
 159                 let mut slow_check = None;
 160                 #[cfg(test)] {
 161                         slow_check = Some(C::ScalarField::from_i(self.normalize_x()?.into_i()) == *expected_x);
 162                 }
 163
 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(()) }
 168         }
 169
 170         fn double(&self) -> Result<Self, ()> {
 171                 if self.y == C::CurveField::ZERO { return Err(()); }
 172                 if self.z == C::CurveField::ZERO { return Err(()); }
 173
 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);
 184
 185                 #[cfg(debug_assertions)] { assert!(Self::on_curve_z(&x, &y, &z).is_ok()); }
 186                 Ok(Point { x, y, z })
 187         }
 188
 189         fn add(&self, o: &Self) -> Result<Self, ()> {
 190                 let o_z_2 = o.z.square();
 191                 let self_z_2 = self.z.square();
 192
 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));
 197                 if u1 == u2 {
 198                         if s1 != s2 { /* Point at Infinity */ return Err(()); }
 199                         return self.double();
 200                 }
 201                 let h = u2.sub(&u1);
 202                 let h_2 = h.square();
 203                 let h_3 = h.mul(&h_2);
 204                 let r = s2.sub(&s1);
 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);
 208
 209                 #[cfg(debug_assertions)] { assert!(Self::on_curve_z(&x, &y, &z).is_ok()); }
 210                 Ok(Point { x, y, z})
 211         }
 212 }
 213
 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>, ()> {
 217         let i = i.into_i();
 218         let j = j.into_i();
 219
 220         if i == C::Int::ZERO { /* Infinity */ return Err(()); }
 221         if j == C::Int::ZERO { /* Infinity */ return Err(()); }
 222
 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)) {
 229                 skip_limb += 1;
 230         }
 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())
 234                 } else { 0 };
 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()?;
 240                         }
 241                         if i_bit {
 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.
 248                                         #[cfg(test)] {
 249                                                 res_opt = res.add(I);
 250                                         }
 251                                         #[cfg(not(test))] {
 252                                                 *res = res.add(I)?;
 253                                         }
 254                                 } else {
 255                                         res_opt = Ok(I.clone());
 256                                 }
 257                         }
 258                         if j_bit {
 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.
 265                                         #[cfg(test)] {
 266                                                 res_opt = res.add(J);
 267                                         }
 268                                         #[cfg(not(test))] {
 269                                                 *res = res.add(J)?;
 270                                         }
 271                                 } else {
 272                                         res_opt = Ok(J.clone());
 273                                 }
 274                         }
 275                 }
 276         }
 277         res_opt
 278 }
 279
 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)]
 283
 284         if pk.len() != C::Int::BYTES * 2 { return Err(()); }
 285         if sig.len() != C::Int::BYTES * 2 { return Err(()); }
 286
 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);
 289
 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)?;
 293
 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
 296         // do so here.
 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(()); }
 301
 302         let r = C::ScalarField::from_i(r_u256);
 303         let s_inv = C::ScalarField::from_modinv_of(s_u256)?;
 304
 305         let z = C::ScalarField::from_i(C::Int::from_be_bytes(hash_input)?);
 306
 307         let u_a = z.mul(&s_inv);
 308         let u_b = r.mul(&s_inv);
 309
 310         let V = add_two_mul(u_a, &C::G, u_b, &PK)?;
 311         V.eq_x(&r)
 312 }