用 dart 語言簡單驗證 ECDSA 演算法

dart 語言支援大數(BigInt)的四則運算,且又能將運算元重新定義運算規則(operator overload),而且 dart 在 2.7 版以後支援了 extension 語法, 可以自行添加方法到 BigInt 上, 簡直如虎添翼,因此驗證 ECC(橢圓曲線密碼學) 的數位簽證演算法(ECDSA)就容易多了:
// main.dart to verify ECDSA
import 'dart:math';
BigInt random(BigInt  m) {
        BigInt temp = BigInt.from(0);
        int bits = m.bitLength;
        while (bits > 0) {
            temp = temp << 8 |  BigInt.from(Random(DateTime.now( ).microsecondsSinceEpoch).nextInt(255));
            bits -= 8;
        }
        return temp % m;
}
extension Divider4ECDSA on BigInt {  // a method .__ to operate / % m
  BigInt __(BigInt divisor, BigInt m) => this * divisor.modInverse(m) % m;
}
class ModField {
  BigInt _value;
  BigInt get value => _value;
  int get mostbits => _value.bitLength - 1;
  static BigInt _prime;
  BigInt get p {
    if(_prime == null) _prime = BigInt.parse("115792089237316195423570985008687907853269984665640564039457584007908834671663");
    return _prime;
  }
  static BigInt parse(var temp) =>
      temp is ModField ? temp._value   :
      temp is String   ? BigInt.parse(temp):
      temp is num     ? BigInt.from(temp) :
      temp is BigInt  ? temp : BigInt.zero;
  bool testbit(int k) => _value >> k & BigInt.one == BigInt.one;
  bool operator ==(var other) => _value == parse(other)
  bool operator < (var other) => _value < parse(other);
  bool operator > (var other) => _value > parse(other);
  ModField operator ^ (int exponent) => ModField(_value.pow(exponent));
  ModField operator + (var other) => ModField(_value + parse(other));
  ModField operator - (var other) => ModField(_value - parse(other));
  ModField operator * (var other) => ModField(_value * parse(other));
  ModField operator %(var other) => ModField(_value % parse(other));
  ModField operator / (var other) => ModField(_value*parse(other).modInverse(p));
  ModField (var temp) {
        _value = parse(temp) % p;
        if (_value < BigInt.zero) _value =  _value + p;
  }
}
class Secp256k1 { // y^2 = x^3 + 7 mod p, ECC order number= GFn
  ModField n, x, y;
  bool get isPoint => y^2 == (x^3) + 7;
  Secp256k1(var temp) {
        if (temp is Secp256k1) { // copy constructor
            n = temp.n;
            x = temp.x;
            y = temp.y;
        } else {
            n = ModField(temp);
            x = ModField("55066263022277343669578718895168534326250603453777594175500187360389116729240");
            y = ModField("32670510020758816978083085130507043184471273380659243275938904335757337482424");
            if(n > 1) {
                 _selfMul(n);// 1 Gn(x, y)
                 n = ModField(1);
            }
        }
  }
  Secp256k1._point(gx, gy) {
        n = ModField(1);
        x = ModField(gx);
        y = ModField(gy);
  }
  factory Secp256k1.G([var gx=0, var gy = 0]) {
       if(gy == 0)  return  Secp256k1(1);
       final temp = Secp256k1._point(gx, gy);
       return temp.isPoint ?  temp :  Secp256k1(1);
  }
  Secp256k1 get _selfX2 { // point doubler
       final px = x;
       final s = (x^2) * 3 / (y*2); // s = 3*x*x / 2y
       x = (s^2) - x*2; // x = s*s - 2x
       y = s * (px - x) - y; // y = s * (px - x) - py
       return this;
  }
  Secp256k1 _selfAdd(ModField gx, ModField gy, {gn = 1}) { // point adder
      if (x == gx)  n = ModField(0);
      else if (n == 0) {
                x = gx;
                y = gy;
                n = ModField(gn);
      } else {
              final s = (y - gy) / (x - gx);
              x = (s^2)  - x - gx; // s*s - x - gx
              y = s*(gx - x) - gy; // s(gx -x) - gy
      }   
      return this;
  }
  Secp256k1 _selfMul(ModField multiplier) {// point scale by DAA
      if (multiplier > 1) {
            var bits =  multiplier.mostbits;
            final gx = x;
            final gy = y;
            while (bits-- > 0) {
                _selfX2;
                if (multiplier.testbit(bits))  _selfAdd(gx, gy);
            }
      }
      return this;
  }
  get dump => print("${n.value} G(${x.value},${y.value})");
  static BigInt _order;
  get GFn {
    if(_order == null) _order = BigInt.parse("115792089237316195423570985008687907852837564279074904382605163141518161494337"); 
    return _order;
  }
  operator + (Secp256k1 Q) => Secp256k1.G(x, y)._selfAdd(Q.x, Q.y);
  operator * (var scale)   => Secp256k1.G(x, y)._selfMul(ModField(scale));
  List<BigInt> signECDSA(BigInt d, BigInt z) { // use key d to sign z, % use GFn 
        final BigInt k = random(GFn);
        final BigInt r = Secp256k1(k).x.value; // r = G.x
        final BigInt s = (z + r * d) .__ (k, GFn); // s = (z + r * d)/k % GFn
        return [z, r, s];
  }
  bool checkECDSA(List<BigInt> signature) {
        if(signature.length < 3) return false;
        final BigInt z = signature[0];
        final BigInt r = signature[1];
        final BigInt s = signature[2];
        final BigInt u  = z .__ (s, GFn); // u = z/s % GFn;
        final BigInt v  = r .__ (s, GFn);  // v = z/s % GFn;
        final Secp256k1 R = Secp256k1.G( )*u + Secp256k1.G(x, y)*v;
        return R.x == r;
  }
}
main( ){
  final text = BigInt.from(123);// 待簽字
  final secret =  BigInt.from(123456789);  // 私鑰
  final qPublic = Secp256k1(secret); // 公鑰
  final signature  = qPublic.signECDSA(secret, text);// 用 ECDSA 簽證文字產生特徵碼
  qPublic.dump;
  print( qPublic.isPoint);
  print(qPublic.checkECDSA(signature) ? "OK": "Fake!");// 用公鑰驗證特徵碼
}
執行 dart main.dart 看結果:
1 G(4051293998585674784991639592782214972820158391371785981004352359465450369227 ,
    88166831356626186178414913298033275054086243781277878360288998796587140930350)
true
OK