include "bigint.s7i";
include "bytedata.s7i";
const type: ecPoint is new struct
var bigInteger: x is 0_;
var bigInteger: y is 0_;
var boolean: isNeutralElement is FALSE;
end struct;
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 <& "_)";
const func ecPoint: getNeutralEcPoint is func
result
var ecPoint: point is ecPoint.value;
begin
point.isNeutralElement := TRUE;
end func;
const ecPoint: neutralEcPoint is getNeutralEcPoint;
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;
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;
const type: ellipticCurve is new struct
var integer: bits is 0;
var string: name is "";
var bigInteger: p is 0_;
var bigInteger: a is 0_;
var bigInteger: b is 0_;
var ecPoint: g is ecPoint.value;
var bigInteger: n is 0_;
end struct;
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;
const ellipticCurve: secp192k1 is ellipticCurve(
192, "secp192k1",
16#fffffffffffffffffffffffffffffffffffffffeffffee37_, 0_, 3_,
ecPoint(16#db4ff10ec057e9ae26b07d0280b7f4341da5d1b1eae06c7d_,
16#9b2f2f6d9c5628a7844163d015be86344082aa88d95e2f9d_),
16#fffffffffffffffffffffffe26f2fc170f69466a74defd8d_);
const ellipticCurve: secp192r1 is ellipticCurve(
192, "secp192r1",
16#fffffffffffffffffffffffffffffffeffffffffffffffff_, -3_,
16#64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1_,
ecPoint(16#188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012_,
16#07192b95ffc8da78631011ed6b24cdd573f977a11e794811_),
16#ffffffffffffffffffffffff99def836146bc9b1b4d22831_);
const ellipticCurve: secp224k1 is ellipticCurve(
224, "secp224k1",
16#fffffffffffffffffffffffffffffffffffffffffffffffeffffe56d_, 0_, 5_,
ecPoint(16#a1455b334df099df30fc28a169a467e9e47075a90f7e650eb6b7a45c_,
16#7e089fed7fba344282cafbd6f7e319f7c0b0bd59e2ca4bdb556d61a5_),
16#0000000000000000000000000001dce8d2ec6184caf0a971769fb1f7_);
const ellipticCurve: secp224r1 is ellipticCurve(
224, "secp224r1",
16#ffffffffffffffffffffffffffffffff000000000000000000000001_, -3_,
16#b4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4_,
ecPoint(16#b70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21_,
16#bd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34_),
16#ffffffffffffffffffffffffffff16a2e0b8f03e13dd29455c5c2a3d_);
const ellipticCurve: secp256k1 is ellipticCurve(
256, "secp256k1",
16#fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f_, 0_, 7_,
ecPoint(16#79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798_,
16#483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8_),
16#fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141_);
const ellipticCurve: secp256r1 is ellipticCurve(
256, "secp256r1",
16#ffffffff00000001000000000000000000000000ffffffffffffffffffffffff_, -3_,
16#5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b_,
ecPoint(16#6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296_,
16#4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5_),
16#ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551_);
const ellipticCurve: secp384r1 is ellipticCurve(
384, "secp384r1",
16#fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000ffffffff_, -3_,
16#b3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef_,
ecPoint(16#aa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7_,
16#3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f_),
16#ffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf581a0db248b0a77aecec196accc52973_);
const ellipticCurve: secp521r1 is ellipticCurve(
521, "secp521r1",
16#1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff_, -3_,
16#051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00_,
ecPoint(16#0c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66_,
16#11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650_),
16#1fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffa51868783bf2f966b7fcc0148f709a5d03bb5c9b8899c47aebb6fb71e91386409_);
const func integer: getSizeInBytes (in ellipticCurve: curve) is
return succ(pred(curve.bits) mdiv 8);
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;
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 := ((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;
sum.y := curve.p - (p.y + slope * (sum.x - p.x)) mod curve.p;
else
sum.isNeutralElement := TRUE;
end if;
end if;
end func;
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;
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 := ((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;
sum.y := curve.p - (p1.y + slope * (sum.x - p1.x)) mod curve.p;
else
sum.isNeutralElement := TRUE;
end if;
end if;
end func;
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;
const type: jacobianPoint is new struct
var bigInteger: xProj is 0_;
var bigInteger: yProj is 0_;
var bigInteger: z is 0_;
var bigInteger: zSquare is 0_;
var bigInteger: zCube is 0_;
var boolean: isNeutralElement is FALSE;
end struct;
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;
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;
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;
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;
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;
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);
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);
const func string: ecPointCompress (in ellipticCurve: curve, in ecPoint: point) is
return str(chr(2 + ord(odd(point.y)))) & bytes(point.x, UNSIGNED, BE, getSizeInBytes(curve));
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));
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;
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_));
const func bigInteger: genPrivateKey (in ellipticCurve: curve) is
return rand(1_, pred(curve.n));
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;
const func boolean: verifyKeyPair (in ellipticCurve: curve, in eccKeyPair: keyPair) is
return keyPair.publicKey = multFast(curve, curve.g, keyPair.privateKey);
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;
const type: ecdsaSignatureType is new struct
var bigInteger: r is 0_;
var bigInteger: s is 0_;
end struct;
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;
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;