elliptic.s7i

(********************************************************************)
(*                                                                  *)
(*  elliptic.s7i  Support for elliptic curve cryptography (ECC).    *)
(*  Copyright (C) 2019  Thomas Mertes                               *)
(*                                                                  *)
(*  This file is part of the Seed7 Runtime Library.                 *)
(*                                                                  *)
(*  The Seed7 Runtime Library is free software; you can             *)
(*  redistribute it and/or modify it under the terms of the GNU     *)
(*  Lesser General Public License as published by the Free Software *)
(*  Foundation; either version 2.1 of the License, or (at your      *)
(*  option) any later version.                                      *)
(*                                                                  *)
(*  The Seed7 Runtime Library is distributed in the hope that it    *)
(*  will be useful, but WITHOUT ANY WARRANTY; without even the      *)
(*  implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR *)
(*  PURPOSE.  See the GNU Lesser General Public License for more    *)
(*  details.                                                        *)
(*                                                                  *)
(*  You should have received a copy of the GNU Lesser General       *)
(*  Public License along with this program; if not, write to the    *)
(*  Free Software Foundation, Inc., 51 Franklin Street,             *)
(*  Fifth Floor, Boston, MA  02110-1301, USA.                       *)
(*                                                                  *)
(********************************************************************)


include "bigint.s7i";
include "bytedata.s7i";


(**
 *  Type to describe a point at an elliptic curve.
 *  A point is either the neutral element or it is defined by x and y.
 *)
const type: ecPoint is new struct
    var bigInteger: x is 0_;
    var bigInteger: y is 0_;
    var boolean: isNeutralElement is FALSE;
  end struct;


(**
 *  Create an elliptic curve point from the given coordinates x and y.
 *)
const func ecPoint: ecPoint (in bigInteger: x, in bigInteger: y) is func
  result
    var ecPoint: point is ecPoint.value;
  begin
    point.x := x;
    point.y := y;
  end func;


const func string: literal (in ecPoint: aKey) is
  return "ecPoint(" <& aKey.x <& "_, " <&
                       aKey.y <& "_)";


#
#  Create the neutral elliptic curve point.
#
const func ecPoint: getNeutralEcPoint is func
  result
    var ecPoint: point is ecPoint.value;
  begin
    point.isNeutralElement := TRUE;
  end func;


(**
 *  The neutral point of an elliptic curve.
 *)
const ecPoint: neutralEcPoint is getNeutralEcPoint;


(**
 *  Check if two elliptic curve points are equal.
 *  @return TRUE if the two points are equal,
 *          FALSE otherwise.
 *)
const func boolean: (in ecPoint: point1) = (in ecPoint: point2) is
  return point1.isNeutralElement = point2.isNeutralElement and
         point1.x = point2.x and point1.y = point2.y;


(**
 *  Check if two elliptic curve points are not equal.
 *  @return FALSE if both numbers are equal,
 *          TRUE otherwise.
 *)
const func boolean: (in ecPoint: point1) <> (in ecPoint: point2) is
  return point1.isNeutralElement <> point2.isNeutralElement or
         point1.x <> point2.x or point1.y <> point2.y;


(**
 *  Type to describe the elliptic curve y**2 = x**3 + a*x + b  (mod p).
 *  The value p defines the finite field F.
 *  The values a and b specify the elliptic curve.
 *)
const type: ellipticCurve is new struct
    var integer: bits is 0;
    var string: name is "";
    var bigInteger: p is 0_;          # In the finite field F all computations are (mod p).
    var bigInteger: a is 0_;
    var bigInteger: b is 0_;
    var ecPoint: g is ecPoint.value;  # Base point of the elliptic curve.
    var bigInteger: n is 0_;          # Order of g (mult(g, n) = neutralEcPoint).
  end struct;


(**
 *  Create an elliptic curve from the given parameters.
 *  Creates the elliptic curve y**2 = x**3 + a*x + b  (mod p).
 *  @param bits Number of bits in the elliptic curve.
 *  @param name Name of the elliptic curve.
 *  @param p In the finite field F all computations are (mod p).
 *  @param a Possible negative factor from the curve formula.
 *  @param b Possible negative constant from the curve formula.
 *  @param g Base point of the elliptic curve.
 *  @param n Order of g (mult(g, n) = neutralEcPoint).
 *)
const func ellipticCurve: ellipticCurve (in integer: bits, in string: name, in bigInteger: p,
    in bigInteger: a, in bigInteger: b, in ecPoint: g, in bigInteger: n) is func
  result
    var ellipticCurve: curve is ellipticCurve.value;
  begin
    curve.bits := bits;
    curve.name := name;
    curve.p := p;
    curve.a := a mod p;
    curve.b := b mod p;
    curve.g := g;
    curve.n := n;
  end func;


(**
 *  The elliptical curve secp192k1.
 *)
const ellipticCurve: secp192k1 is ellipticCurve(
    192, "secp192k1",
    16#fffffffffffffffffffffffffffffffffffffffeffffee37_, 0_, 3_,
    ecPoint(16#db4ff10ec057e9ae26b07d0280b7f4341da5d1b1eae06c7d_,
            16#9b2f2f6d9c5628a7844163d015be86344082aa88d95e2f9d_),
    16#fffffffffffffffffffffffe26f2fc170f69466a74defd8d_);

(**
 *  The elliptical curve secp192r1.
 *)
const ellipticCurve: secp192r1 is ellipticCurve(
    192, "secp192r1",
    16#fffffffffffffffffffffffffffffffeffffffffffffffff_, -3_,
    16#64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1_,
    ecPoint(16#188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012_,
            16#07192b95ffc8da78631011ed6b24cdd573f977a11e794811_),
    16#ffffffffffffffffffffffff99def836146bc9b1b4d22831_);

(**
 *  The elliptical curve secp224k1.
 *)
const ellipticCurve: secp224k1 is ellipticCurve(
    224, "secp224k1",
    16#fffffffffffffffffffffffffffffffffffffffffffffffeffffe56d_, 0_, 5_,
    ecPoint(16#a1455b334df099df30fc28a169a467e9e47075a90f7e650eb6b7a45c_,
            16#7e089fed7fba344282cafbd6f7e319f7c0b0bd59e2ca4bdb556d61a5_),
    16#0000000000000000000000000001dce8d2ec6184caf0a971769fb1f7_);

(**
 *  The elliptical curve secp224r1.
 *)
const ellipticCurve: secp224r1 is ellipticCurve(
    224, "secp224r1",
    16#ffffffffffffffffffffffffffffffff000000000000000000000001_, -3_,
    16#b4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4_,
    ecPoint(16#b70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21_,
            16#bd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34_),
    16#ffffffffffffffffffffffffffff16a2e0b8f03e13dd29455c5c2a3d_);

(**
 *  The elliptical curve secp256k1.
 *)
const ellipticCurve: secp256k1 is ellipticCurve(
    256, "secp256k1",
    16#fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f_, 0_, 7_,
    ecPoint(16#79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798_,
            16#483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8_),
    16#fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141_);

(**
 *  The elliptical curve secp256r1.
 *)
const ellipticCurve: secp256r1 is ellipticCurve(
    256, "secp256r1",
    16#ffffffff00000001000000000000000000000000ffffffffffffffffffffffff_, -3_,
    16#5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b_,
    ecPoint(16#6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296_,
            16#4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5_),
    16#ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551_);

(**
 *  The elliptical curve secp384r1.
 *)
const ellipticCurve: secp384r1 is ellipticCurve(
    384, "secp384r1",
    16#fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000ffffffff_, -3_,
    16#b3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef_,
    ecPoint(16#aa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7_,
            16#3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f_),
    16#ffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf581a0db248b0a77aecec196accc52973_);

(**
 *  The elliptical curve secp521r1.
 *)
const ellipticCurve: secp521r1 is ellipticCurve(
    521, "secp521r1",
    16#1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff_, -3_,
    16#051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00_,
    ecPoint(16#0c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66_,
            16#11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650_),
    16#1fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffa51868783bf2f966b7fcc0148f709a5d03bb5c9b8899c47aebb6fb71e91386409_);


(**
 *  Get the size of an elliptic curve in bytes.
 *  This is the number of bytes necessary to represent the x or y
 *  coordinate of an ecPoint.
 *)
const func integer: getSizeInBytes (in ellipticCurve: curve) is
  return succ(pred(curve.bits) mdiv 8);


(**
 *  Test, whether 'point' is on the given elliptic curve.
 *)
const func boolean: element (in ecPoint: point, in ellipticCurve: curve) is
  return point.isNeutralElement or
      (point.x ** 3 + curve.a * point.x + curve.b) mod curve.p = point.y ** 2 mod curve.p;


(**
 *  Double the point p over given curve.
 *  Double point in y**2 = x**3 + a*x + b  (mod p).
 *)
const func ecPoint: double (in ellipticCurve: curve, in ecPoint: p) is func
  result
    var ecPoint: sum is ecPoint.value;
  local
    var bigInteger: slope is 0_;
  begin
    if p.isNeutralElement then
      sum.isNeutralElement := TRUE;
    else
      if p.y ** 2 mod curve.p <> 0_ then          # slope calculated by derivation
        slope := ((3_ * p.x ** 2 + curve.a) * modInverse(2_ * p.y, curve.p)) mod curve.p;
        sum.x := (slope ** 2 - 2_ * p.x) mod curve.p;    # intersection with curve
        sum.y := curve.p - (p.y + slope * (sum.x - p.x)) mod curve.p;
      else
        sum.isNeutralElement := TRUE;
      end if;
    end if;
  end func;


(**
 *  Add the points p1 and p2 over given curve.
 *  Addition of points in y**2 = x**3 + a*x + b  (mod p).
 *)
const func ecPoint: add (in ellipticCurve: curve, in ecPoint: p1, in ecPoint: p2) is func
  result
    var ecPoint: sum is ecPoint.value;
  local
    var bigInteger: slope is 0_;
  begin
    if p1.isNeutralElement then
      sum := p2;
    elsif p2.isNeutralElement then
      sum := p1;
    else
      if (p1.x - p2.x) mod curve.p <> 0_ then
        slope := ((p1.y - p2.y) * modInverse(p1.x - p2.x, curve.p)) mod curve.p;
        sum.x := (slope ** 2 - p1.x - p2.x) mod curve.p;  # intersection with curve
        sum.y := curve.p - (p1.y + slope * (sum.x - p1.x)) mod curve.p;
      elsif (p1.y + p2.y) mod curve.p <> 0_ then          # slope calculated by derivation
        slope := ((3_ * p1.x ** 2 + curve.a) * modInverse(2_ * p1.y, curve.p)) mod curve.p;
        sum.x := (slope ** 2 - 2_ * p1.x) mod curve.p;    # intersection with curve
        sum.y := curve.p - (p1.y + slope * (sum.x - p1.x)) mod curve.p;
      else
        sum.isNeutralElement := TRUE;
      end if;
    end if;
  end func;


(**
 *  Multiply point p1 by scalar c over given curve.
 *  Scalar multiplication p1 * c = p1 + p1 + ... + p1 (c times).
 *)
const func ecPoint: mult (in ellipticCurve: curve, in var ecPoint: p1, in var bigInteger: c) is func
  result
    var ecPoint: product is ecPoint.value;
  begin
    product.isNeutralElement := TRUE;
    while c > 0_ do
      if odd(c) then
        product := add(curve, product, p1);
      end if;
      c >>:= 1;
      p1 := double(curve, p1);
    end while;
  end func;


(**
 *  Alternate type to describe a point at an elliptic curve.
 *  The curve points are on the elliptic curve y**2 = x**3 + a*x + b  (mod p).
 *  This coordinates eliminate the need for expensive inversions mod p.
 *)
const type: jacobianPoint is new struct
    var bigInteger: xProj is 0_;  # x = xProj / z ** 2
    var bigInteger: yProj is 0_;  # y = yProj / z ** 3
    var bigInteger: z is 0_;
    var bigInteger: zSquare is 0_;  # zSquare = z ** 2
    var bigInteger: zCube   is 0_;  # zCube   = z ** 3
    var boolean: isNeutralElement is FALSE;
  end struct;


(**
 *  Transform point p given as (x, y) to jacobian coordinates.
 *)
const func jacobianPoint: toJacobian (in ecPoint: p) is func
  result
    var jacobianPoint: point is jacobianPoint.value;
  begin
    if p.isNeutralElement then
      point.isNeutralElement := TRUE;
    else
      point.xProj := p.x;
      point.yProj := p.y;
      point.z := 1_;
      point.zSquare := 1_;
      point.zCube := 1_;
    end if;
  end func;


(**
 *  Transform a point from jacobian coordinates to (x, y) mod n.
 *)
const func ecPoint: fromJacobian (in jacobianPoint: jp, in bigInteger: n) is func
  result
    var ecPoint: point is ecPoint.value;
  begin
    if jp.isNeutralElement then
      point.isNeutralElement := TRUE;
    else
      point.x := (jp.xProj * modInverse(jp.zSquare, n)) mod n;
      point.y := (jp.yProj * modInverse(jp.zCube, n)) mod n;
    end if;
  end func;


(**
 *  Double the point jp in jacobian coordinates over given curve.
 *  Double point in y**2 = x**3 + a*x + b  (mod p).
 *)
const func jacobianPoint: double (in ellipticCurve: curve, in jacobianPoint: jp) is func
  result
    var jacobianPoint: sum is jacobianPoint.value;
  local
    var bigInteger: yProjSquare is 0_;
    var bigInteger: a is 0_;
    var bigInteger: b is 0_;
  begin
    if jp.isNeutralElement then
      sum.isNeutralElement := TRUE;
    else
      yProjSquare := (jp.yProj * jp.yProj) mod curve.p;
      a := (4_ * jp.xProj * yProjSquare) mod curve.p;
      b := (3_ * jp.xProj * jp.xProj + curve.a * jp.zCube * jp.z) mod curve.p;
      sum.xProj := (b ** 2 - 2_ * a) mod curve.p;
      sum.yProj := (b * (a - sum.xProj) - 8_ * yProjSquare ** 2) mod curve.p;
      sum.z := (2_ * jp.yProj * jp.z) mod curve.p;
      sum.zSquare := (sum.z ** 2) mod curve.p;
      sum.zCube := (sum.zSquare * sum.z) mod curve.p;
    end if;
  end func;


(**
 *  Add the points jp1 and jp2 in jacobian coordinates over given curve.
 *  Addition of points in y**2 = x**3 + a*x + b  (mod p).
 *)
const func jacobianPoint: add (in ellipticCurve: curve, in jacobianPoint: jp1, in jacobianPoint: jp2) is func
  result
    var jacobianPoint: sum is jacobianPoint.value;
  local
    var bigInteger: s1 is 0_;
    var bigInteger: s2 is 0_;
    var bigInteger: u1 is 0_;
    var bigInteger: u2 is 0_;
    var bigInteger: h is 0_;
    var bigInteger: hSquare is 0_;
    var bigInteger: hCube is 0_;
    var bigInteger: r is 0_;
  begin
    if jp1.isNeutralElement then
      sum := jp2;
    elsif jp2.isNeutralElement then
      sum := jp1;
    else
      s1 := (jp1.yProj * jp2.zCube) mod curve.p;
      s2 := (jp2.yProj * jp1.zCube) mod curve.p;
      u1 := (jp1.xProj * jp2.zSquare) mod curve.p;
      u2 := (jp2.xProj * jp1.zSquare) mod curve.p;
      if (u1 - u2) mod curve.p <> 0_ then
        h := (u2 - u1) mod curve.p;
        r := (s2 - s1) mod curve.p;
        hSquare := (h ** 2) mod curve.p;
        hCube := (hSquare * h) mod curve.p;
        sum.xProj := (-hCube - 2_ * u1 * hSquare + r ** 2) mod curve.p;
        sum.yProj := (-s1 * hCube + r * (u1 * hSquare - sum.xProj)) mod curve.p;
        sum.z := (jp1.z * jp2.z * h) mod curve.p;
        sum.zSquare := (sum.z ** 2) mod curve.p;
        sum.zCube := (sum.zSquare * sum.z) mod curve.p;
      elsif (s1 + s2) mod curve.p <> 0_ then
        sum := double(curve, jp1);
      else
        sum.isNeutralElement := TRUE;
      end if;
    end if;
  end func;


(**
 *  Multiply point jp1 by scalar c in jacobian coordinates over given curve.
 *  Scalar multiplication jp1 * c = jp1 + jp1 + ... + jp1 (c times).
 *)
const func jacobianPoint: mult (in ellipticCurve: curve, in var jacobianPoint: jp1, in var bigInteger: c) is func
  result
    var jacobianPoint: product is jacobianPoint.value;
  begin
    product.isNeutralElement := TRUE;
    while c > 0_ do
      if odd(c) then
        product := add(curve, product, jp1);
      end if;
      c >>:= 1;
      jp1 := double(curve, jp1);
    end while;
  end func;


(**
 *  Multiply point p1 by scalar c over given curve.
 *  Scalar multiplication p1 * c = p1 + p1 + ... + p1 (c times).
 *  Encapsulates the multiplication that is done with jacobian coordinates.
 *)
const func ecPoint: multFast (in ellipticCurve: curve, in var ecPoint: p1, in var bigInteger: c) is
    return fromJacobian(mult(curve, toJacobian(p1), c), curve.p);


(**
 *  Compute the sum of two products (ecPoint times scalar).
 *  Encapsulates the computation that is done with jacobian coordinates.
 *)
const func ecPoint: multAddFast (in ellipticCurve: curve, in var ecPoint: p1, in var bigInteger: c1,
                                 in var ecPoint: p2, in var bigInteger: c2) is
    return fromJacobian(add(curve, mult(curve, toJacobian(p1), c1),
                                   mult(curve, toJacobian(p2), c2)), curve.p);


(**
 *  Encode an ecPoint in compressed form.
 *)
const func string: ecPointCompress (in ellipticCurve: curve, in ecPoint: point) is
  return str(char(2 + ord(odd(point.y)))) & bytes(point.x, UNSIGNED, BE, getSizeInBytes(curve));


(**
 *  Encode an ecPoint in uncompressed form.
 *)
const func string: ecPointEncode (in ellipticCurve: curve, in ecPoint: point) is
  return "\4;" & bytes(point.x, UNSIGNED, BE, getSizeInBytes(curve)) &
                 bytes(point.y, UNSIGNED, BE, getSizeInBytes(curve));


(**
 * Decode an ecPoint, which can be compressed or uncompressed.
 *)
const func ecPoint: ecPointDecode (in ellipticCurve: curve, in string: encoded) is func
  result
    var ecPoint: point is ecPoint.value;
  local
    var integer: dataSize is 0;
    var boolean: signY is FALSE;
  begin
    dataSize := getSizeInBytes(curve);
    if encoded[1] = '\4;' then
      point.x := bytes2BigInt(encoded[2            fixLen dataSize], UNSIGNED, BE);
      point.y := bytes2BigInt(encoded[2 + dataSize fixLen dataSize], UNSIGNED, BE);
    elsif encoded[1] in {'\2;', '\3;'} then
      signY := encoded[1] = '\3;';
      point.x := bytes2BigInt(encoded[2 fixLen dataSize], UNSIGNED, BE);
      point.y := modPow((point.x ** 3 + curve.a * point.x + curve.b) mod curve.p,
                        succ(curve.p) div 4_, curve.p);
      if odd(point.y) <> signY then
        point.y := curve.p - point.y;
      end if;
    else
      raise RANGE_ERROR;
    end if;
  end func;


(**
 *  Type to describe a pair of ECC keys (private key and public key).
 *)
const type: eccKeyPair is new struct
    var ellipticCurve: curve is ellipticCurve.value;
    var bigInteger: privateKey is 0_;
    var ecPoint: publicKey is ecPoint.value;
  end struct;


const func eccKeyPair: eccKeyPair (in ellipticCurve: curve,
    in bigInteger: privateKey, in ecPoint: publicKey) is func
  result
    var eccKeyPair: keyPair is eccKeyPair.value;
  begin
    keyPair.curve := curve;
    keyPair.privateKey := privateKey;
    keyPair.publicKey := publicKey;
  end func;


const eccKeyPair: stdEccKeyPair is eccKeyPair(
    secp256r1,
    74624382696344922655307391993066343569456111979064004675311073248448678904789_,
    ecPoint(88877469563668185112995971247814023116402020168635356824775921814423688893259_,
            29134039813344649890715104713898999575368238414646407541580162911271978616303_));


(**
 *  Generate a private key for elliptic curve cryptography (ECC).
 *)
const func bigInteger: genPrivateKey (in ellipticCurve: curve) is
  return rand(1_, pred(curve.n));


(**
 *  Generate a new ECC keyPair (private key and public key).
 *)
const func eccKeyPair: genEccKeyPair (in ellipticCurve: curve) is func
  result
    var eccKeyPair: keyPair is eccKeyPair.value;
  begin
    keyPair.curve := curve;
    keyPair.privateKey := genPrivateKey(curve);
    keyPair.publicKey := multFast(curve, curve.g, keyPair.privateKey);
  end func;


(**
 *  Verify that public and private key of an ECC keyPair fit together.
 *)
const func boolean: verifyKeyPair (in ellipticCurve: curve, in eccKeyPair: keyPair) is
  return keyPair.publicKey = multFast(curve, curve.g, keyPair.privateKey);


#
#  Truncate a message to the bit size of msgMax.
#
const func bigInteger: truncate (in bigInteger: message, in bigInteger: msgMax) is func
  result
    var bigInteger: truncated is 0_;
  begin
    truncated := message;
    while truncated > msgMax do
      truncated >>:= 1;
    end while;
  end func;


(**
 *  Structure to hold an ECDSA signature.
 *  ECDSA is the Elliptic Curve Digital Signature Algorithm.
 *)
const type: ecdsaSignatureType is new struct
    var bigInteger: r is 0_;
    var bigInteger: s is 0_;
  end struct;


(**
 *  Compute the ECDSA signature of 'message'.
 *  ECDSA is the Elliptic Curve Digital Signature Algorithm.
 *)
const func ecdsaSignatureType: sign (in ellipticCurve: curve, in var bigInteger: message,
    in bigInteger: privateKey) is func
  result
    var ecdsaSignatureType: signature is ecdsaSignatureType.value;
  local
    var bigInteger: k is 0_;
    var bigInteger: kinv is 0_;
    var ecPoint: kg is ecPoint.value;
  begin
    message := truncate(message, curve.p);
    while signature.r = 0_ or signature.s = 0_ do
      k := genPrivateKey(curve);
      kinv := modInverse(k, curve.n);
      kg := multFast(curve, curve.g, k);
      signature.r := kg.x mod curve.n;
      if signature.r <> 0_ then
        signature.s := (kinv * (message + signature.r * privateKey)) mod curve.n;
      end if;
    end while;
  end func;


(**
 *  Verify that 'signature' is a valid ECDSA signature of 'message'.
 *  ECDSA is the Elliptic Curve Digital Signature Algorithm.
 *)
const func boolean: verify (in ellipticCurve: curve, in var bigInteger: message,
    in ecdsaSignatureType: signature, in ecPoint: publicKey) is func
  result
    var boolean: okay is FALSE;
  local
    var bigInteger: w is 0_;
    var bigInteger: u1 is 0_;
    var bigInteger: u2 is 0_;
    var ecPoint: point is ecPoint.value;
  begin
    message := truncate(message, curve.p);
    if publicKey.x <> 0_ and publicKey.y <> 0_ and
        0_ < signature.r and signature.r < curve.n and
        0_ < signature.s and signature.s < curve.n then
      w := modInverse(signature.s, curve.n);
      u1 := (message * w) mod curve.n;
      u2 := (signature.r * w) mod curve.n;
      point := multAddFast(curve, curve.g, u1, publicKey, u2);
      okay := signature.r mod curve.n = point.x mod curve.n;
    end if;
  end func;