2021SC@SDUSC

有限域Galois Field

定義有限域的秩p以及模p運算

trait curve {
   fn p() ->BigInt ;
   //這里的p就是有限域的秩p
   }
   
struct Field<C: Curve >(BigInt);

impl<C: Curve> Field<C>{
   //將一個元素放入到有限域中，要進行mod p運算
   fn new( v: BigInt ) -> Self{
   Self( v.mod_floor (C::p()))
   }
}

橢圓曲線Elliptic Curves

定義橢圓曲線的三個引數：

//有限域橢圓曲線方程的三個引數a、b、p
use num_bigint::BigInt;
pub trait Curve {
   fn p() -> BigInt ;
   fn a() -> BigInt ;
   fn b() -> BigInt ;
}

具體到secp256k1橢圓曲線的三個引數值：

//定義secp256k1的三個引數a、b、p的值
struct P256K1Curve;

impl Curve for P256K1Curve {
      fn p() -> BigInt {
      BigInt::from_str_radix("FFFFFFFFFFFFFFFF
                              FFFFFFFFFFFFFFFF
                              FFFFFFFFFFFFFFFF
                              FFFFFFFEFFFFFC2F" ,16).unwrap()
      }//定義p取值為以上256位二進制數
      fn a() -> BigInt { BigInt::zero() }//定義a為0
      fn b() -> BigInt { BigInt::from(7u32) }//定義b為7，u32表示無符號int基本整數型別
}

定義橢圓曲線上的點，要么是一個無窮遠點，要么就具有x值和y值：

pub enum PointValue {
  Infinity ,  //無窮遠點
  Value {
  x: BigInt ,
  y: BigInt ,
  } //定義橫縱坐標x和y
}

pub struct Point<C:Curve> {
  pub value: PointValue,
  _marker: PhantomData<C>,
  }

判斷任意一個點是不是在橢圓曲線上：

impl<C:Curve> Point<C>{
   pub fn is_valid(&self) -> bool {
   match self.value {
    PointValue::Infinity => true, //如果是一個無窮遠點，那么在橢圓曲線上
    PointValue::Value { ref x, ref y } => {
    (y * y - (x * x * x + &C::a() * x + &C::b()))
     .mod_floor(&C::p()) == BigInt::zero() },//如果不是無窮遠點，就將該點的橫縱坐標代入有限域下橢圓曲線方程檢驗
   } 
 }
}

橢圓曲線幾何加法

進行橢圓曲線P和Q的幾何加法主要分幾種情況討論：
P或Q中有一個是無窮遠點；
P和Q是同一個點，橫縱坐標一致；
P和Q是相反的點，即在影像上關于直線y=p/2對稱；
P和Q是除上面三種情況外的一般點

如果其中一個P或者Q是無窮遠點,將不是無窮遠點的點的橫縱坐標回傳

impl<C: Curve> Add for Point<C> {
   fn add (self, other: Point<C>) -> Point <C> {
     let (ox, oy) = match other.value {
        PointValue::Infinity => return self ,
        PointValue::Value { ref x, ref y } => (x.clone(), y.clone()),};
     let (sx, sy) = match self.value {
        PointValue::Infinity => return other ,
        PointValue::Value { ref x, ref y } => (x.clone(), y.clone()),};
        ......
   }
}

P和Q橫坐標一致時：
如果P和Q是相反的點，那么兩點的縱坐標之和等于p，模p的結果為0，可以直接回傳結果為無窮遠點；
如果P和Q是相同的點，那么兩點的縱坐標之和模p的結果一定不為0，就對自身（P或Q）取二倍，

impl<C: Curve> Add for Point <C> {
  fn add(self, other: Point<C>) -> Point <C> {
    ...
    if sx == ox {
       return if (sy + oy ).mod_floor(&C::p()) == BigInt::zero() {
         Point::infinity ()
         }else {
         self.double ()
         }
    }
    ...
  }
}

如果P和Q是一般點
先求斜率l，P點縱坐標減Q點縱坐標再乘以P點橫坐標減Q點橫坐標模p的乘法逆元，最后結果再對p取模，即( ( yP - yQ) ( xP - xQ )^ -1 ) mod p
再分別求出R的橫縱坐標
xR = ( m^2 - xP - xQ ) mod p
yR = ( m (xP - xR) - yP ) mod p

impl<C: Curve > Add for Point<C> {
  type Output = Point <C>;
  fn add(self, other: Point <C>) -> Point<C> {
    ...
    let l = ((&oy - &sy) * utils::inverse_mod(&ox -&sx, C::p())).mod_floor (&C::p());
    let x3 = (&l * &l - &sx - &ox).mod_floor ( &C::p());
    let y3 = (&l *(&sx - &×3) - &sy ) .mod_floor ( &C::p());
    Self::from(PointValue::Value { x: x3, y: y3 })
    }
}

橢圓曲線標量乘法

對橢圓曲線上一點計算標量乘法，如果該點乘的系數n為0，那么回傳結果直接就為無窮遠點；否則讓該點不斷與自己做幾何加法運算，直到n次結束，

impl<C: Curve> Mul<BigInt> for Point <C> {
  fn mul(self, n: BigInt) -> Point<C> {
    if n == 0 {
      Self::infinity ()
    }else {
     let mut ret = self.clone();
     for _ in 1 ... n {
        ret = ret + self.clone ();
        }
        ret
     }
  }
}

在secp256k1中被計算標量乘法的（也就是橢圓曲線群的生成元）基準點G的橫縱坐標，

let g = Point::<P256K1Curve>::from(PointValue::Value {
  x: BigInt::from_str_radix(
  "79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798",16).unwrap(),
  y: BigInt::from_str_radix(
  "483ADA7726A3C4655DA4FBFCOE1108A8FD17B448A68554199C47D08FFB1004B8",16).unwrap()
});

基準點G進行標量乘法（系數n=3，即三次幾何加法運算）得到新的點：

assert.eq!(
  g.clone() *BigInt::from(3u32),
  Point::<P256K1Curve>::from(PointValue::Value {
    x: BigInt::from_str_radix(
  "F9308A019258C31049344F85F89D5229B531C845836F99B08601F113BCE036F9",16).unwrap(),
    y: BigInt::from_str_radix(
  "388F7B0F632DE8140FE337E62A37F3566500A99934C2231B6CB9FD7584B8E672",16).unwrap()
  })
);