_ 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 IntModP and IntModN can be replaced with a single IntMod.
  67         type IntModP: IntMod<I = Self::Int>;
  68         type IntModN: IntMod<I = Self::Int>;
  69
  70         type P: PrimeModulus<Self::Int>;
  71         type N: PrimeModulus<Self::Int>;
  72
  73         // Curve parameters y^2 = x^3 + ax + b
  74         const A: Self::IntModP;
  75         const B: Self::IntModP;
  76
  77         const G: Point<Self>;
  78 }
  79
  80 #[derive(Clone, PartialEq, Eq)]
  81 pub(super) struct Point<C: Curve + ?Sized> {
  82         x: C::IntModP,
  83         y: C::IntModP,
  84         z: C::IntModP,
  85 }
  86
  87 impl<C: Curve + ?Sized> Point<C> {
  88         fn on_curve(x: &C::IntModP, y: &C::IntModP) -> Result<(), ()> {
  89                 let x_2 = x.square();
  90                 let x_3 = x_2.mul(&x);
  91                 let v = x_3.add(&C::A.mul(&x)).add(&C::B);
  92
  93                 let y_2 = y.square();
  94                 if y_2 != v {
  95                         Err(())
  96                 } else {
  97                         Ok(())
  98                 }
  99         }
 100
 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)
 109         }
 110
 111         #[cfg(test)]
 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()))
 115         }
 116
 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 })
 122         }
 123
 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 }
 126         }
 127
 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");
 131
 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;
 138                 #[cfg(test)] {
 139                         slow_check = Some(C::IntModN::from_i(self.normalize_x()?.into_i()) == *expected_x);
 140                 }
 141
 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(()) }
 146         }
 147
 148         fn double(&self) -> Result<Self, ()> {
 149                 if self.y == C::IntModP::ZERO { return Err(()); }
 150                 if self.z == C::IntModP::ZERO { return Err(()); }
 151
 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);
 162
 163                 #[cfg(debug_assertions)] { assert!(Self::on_curve_z(&x, &y, &z).is_ok()); }
 164                 Ok(Point { x, y, z })
 165         }
 166
 167         fn add(&self, o: &Self) -> Result<Self, ()> {
 168                 let o_z_2 = o.z.square();
 169                 let self_z_2 = self.z.square();
 170
 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));
 175                 if u1 == u2 {
 176                         if s1 != s2 { /* PAI */ return Err(()); }
 177                         return self.double();
 178                 }
 179                 let h = u2.sub(&u1);
 180                 let h_2 = h.square();
 181                 let h_3 = h.mul(&h_2);
 182                 let r = s2.sub(&s1);
 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);
 186
 187                 #[cfg(debug_assertions)] { assert!(Self::on_curve_z(&x, &y, &z).is_ok()); }
 188                 Ok(Point { x, y, z})
 189         }
 190 }
 191
 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>, ()> {
 195         let i = i.into_i();
 196         let j = j.into_i();
 197
 198         if i == C::Int::ZERO { /* Infinity */ return Err(()); }
 199         if j == C::Int::ZERO { /* Infinity */ return Err(()); }
 200
 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)) {
 207                 skip_limb += 1;
 208         }
 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())
 212                 } else { 0 };
 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()?;
 218                         }
 219                         if i_bit {
 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.
 226                                         #[cfg(test)] {
 227                                                 res_opt = res.add(I);
 228                                         }
 229                                         #[cfg(not(test))] {
 230                                                 *res = res.add(I)?;
 231                                         }
 232                                 } else {
 233                                         res_opt = Ok(I.clone());
 234                                 }
 235                         }
 236                         if j_bit {
 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.
 243                                         #[cfg(test)] {
 244                                                 res_opt = res.add(J);
 245                                         }
 246                                         #[cfg(not(test))] {
 247                                                 *res = res.add(J)?;
 248                                         }
 249                                 } else {
 250                                         res_opt = Ok(J.clone());
 251                                 }
 252                         }
 253                 }
 254         }
 255         res_opt
 256 }
 257
 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)]
 261
 262         if pk.len() != C::Int::BYTES * 2 { return Err(()); }
 263         if sig.len() != C::Int::BYTES * 2 { return Err(()); }
 264
 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);
 267
 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)?;
 271
 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
 274         // do so here.
 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(()); }
 279
 280         let r = C::IntModN::from_i(r_u256);
 281         let s_inv = C::IntModN::from_modinv_of(s_u256)?;
 282
 283         let z = C::IntModN::from_i(C::Int::from_be_bytes(hash_input)?);
 284
 285         let u_a = z.mul(&s_inv);
 286         let u_b = r.mul(&s_inv);
 287
 288         let V = add_two_mul(u_a, &C::G, u_b, &PK)?;
 289         V.eq_x(&r)
 290 }