357 lines
9.4 KiB
JavaScript
357 lines
9.4 KiB
JavaScript
class EllipticCurveDigitalSignatureAlgorithm {
|
|
static main() {
|
|
// Test parameters for elliptic curve digital signature algorithm,
|
|
// using the short Weierstrass model: y^2 = x^3 + ax + b (mod N).
|
|
//
|
|
// Parameter: a, b, modulus N, base point G, order of G in the elliptic curve.
|
|
|
|
const parameters = [
|
|
new Parameter(355, 671, 1073741789, new Point(13693, 10088), 1073807281),
|
|
new Parameter(0, 7, 67096021, new Point(6580, 779), 16769911),
|
|
new Parameter(-3, 1, 877073, new Point(0, 1), 878159),
|
|
new Parameter(0, 14, 22651, new Point(63, 30), 151),
|
|
new Parameter(3, 2, 5, new Point(2, 1), 5),
|
|
];
|
|
|
|
// Parameters which cause failure of the algorithm for the given reasons
|
|
// the base point is of composite order
|
|
// new Parameter( 0, 7, 67096021, new Point( 2402, 6067), 33539822 ),
|
|
// the given order is of composite order
|
|
// new Parameter( 0, 7, 67096021, new Point( 6580, 779), 67079644 ),
|
|
// the modulus is not prime (deceptive example)
|
|
// new Parameter( 0, 7, 877069, new Point( 3, 97123), 877069 ),
|
|
// fails if the modulus divides the discriminant
|
|
// new Parameter( 39, 387, 22651, new Point( 95, 27), 22651 ) );
|
|
|
|
const f = 0x789abcde; // The message's digital signature hash which is to be verified
|
|
const d = 0; // Set d > 0 to simulate corrupted data
|
|
|
|
for (const parameter of parameters) {
|
|
const ellipticCurve = new EllipticCurve(parameter);
|
|
EllipticCurveDigitalSignatureAlgorithm.ecdsa(ellipticCurve, f, d);
|
|
}
|
|
}
|
|
|
|
// Build the digital signature for a message using the hash aF with error bit aD
|
|
static ecdsa(aCurve, aF, aD) {
|
|
let point = aCurve.multiply(aCurve.g, aCurve.r);
|
|
|
|
if (
|
|
aCurve.discriminant() == 0 ||
|
|
aCurve.g.isZero() ||
|
|
!point.isZero() ||
|
|
!aCurve.contains(aCurve.g)
|
|
) {
|
|
//throw new Error("Invalid parameter in method ecdsa");
|
|
}
|
|
|
|
console.log("\nkey generation");
|
|
const s = 1 + Math.floor(Math.random() * (aCurve.r - 1));
|
|
point = aCurve.multiply(aCurve.g, s);
|
|
console.log("private key s = " + s);
|
|
aCurve.printPointWithPrefix(point, "public key W = sG");
|
|
|
|
// Find the next highest power of two minus one.
|
|
let t = aCurve.r;
|
|
let i = 1;
|
|
while (i < 64) {
|
|
t |= t >> i;
|
|
i <<= 1;
|
|
}
|
|
let f = aF;
|
|
while (f > t) {
|
|
f >>= 1;
|
|
}
|
|
console.log("\naligned hash " + f.toString(16).padStart(8, '0'));
|
|
|
|
const signature = EllipticCurveDigitalSignatureAlgorithm.signature(
|
|
aCurve,
|
|
s,
|
|
f
|
|
);
|
|
console.log("signature c, d = " + signature.a + ", " + signature.b);
|
|
|
|
let d = aD;
|
|
if (d > 0) {
|
|
while (d > t) {
|
|
d >>= 1;
|
|
}
|
|
f ^= d;
|
|
console.log("\ncorrupted hash " + f.toString(16).padStart(8, '0'));
|
|
}
|
|
|
|
console.log(
|
|
EllipticCurveDigitalSignatureAlgorithm.verify(aCurve, point, f, signature)
|
|
? "Valid"
|
|
: "Invalid"
|
|
);
|
|
console.log("-----------------");
|
|
}
|
|
|
|
static verify(aCurve, aPoint, aF, aSignature) {
|
|
if (
|
|
aSignature.a < 1 ||
|
|
aSignature.a >= aCurve.r ||
|
|
aSignature.b < 1 ||
|
|
aSignature.b >= aCurve.r
|
|
) {
|
|
return false;
|
|
}
|
|
|
|
console.log("\nsignature verification");
|
|
const h = EllipticCurveDigitalSignatureAlgorithm.extendedGCD(
|
|
aSignature.b,
|
|
aCurve.r
|
|
);
|
|
const h1 = EllipticCurveDigitalSignatureAlgorithm.floorMod(aF * h, aCurve.r);
|
|
const h2 = EllipticCurveDigitalSignatureAlgorithm.floorMod(aSignature.a * h, aCurve.r);
|
|
console.log("h1, h2 = " + h1 + ", " + h2);
|
|
let v = aCurve.multiply(aCurve.g, h1);
|
|
let v2 = aCurve.multiply(aPoint, h2);
|
|
aCurve.printPointWithPrefix(v, "h1G");
|
|
aCurve.printPointWithPrefix(v2, "h2W");
|
|
v = aCurve.add(v, v2);
|
|
aCurve.printPointWithPrefix(v, "+ =");
|
|
|
|
if (v.isZero()) {
|
|
return false;
|
|
}
|
|
const c1 = EllipticCurveDigitalSignatureAlgorithm.floorMod(v.x, aCurve.r);
|
|
console.log("c' = " + c1);
|
|
return c1 == aSignature.a;
|
|
}
|
|
|
|
static signature(aCurve, aS, aF) {
|
|
let c = 0;
|
|
let d = 0;
|
|
let u;
|
|
let v;
|
|
console.log("Signature computation");
|
|
|
|
while (true) {
|
|
while (true) {
|
|
u = 1 + Math.floor(Math.random() * (aCurve.r - 1));
|
|
v = aCurve.multiply(aCurve.g, u);
|
|
c = EllipticCurveDigitalSignatureAlgorithm.floorMod(v.x, aCurve.r);
|
|
if (c != 0) {
|
|
break;
|
|
}
|
|
}
|
|
|
|
d = EllipticCurveDigitalSignatureAlgorithm.floorMod(
|
|
EllipticCurveDigitalSignatureAlgorithm.extendedGCD(u, aCurve.r) *
|
|
EllipticCurveDigitalSignatureAlgorithm.floorMod(aF + aS * c, aCurve.r),
|
|
aCurve.r
|
|
);
|
|
if (d != 0) {
|
|
break;
|
|
}
|
|
}
|
|
|
|
console.log("one-time u = " + u);
|
|
aCurve.printPointWithPrefix(v, "V = uG");
|
|
return new Pair(c, d);
|
|
}
|
|
|
|
// Return 1 / aV modulus aU
|
|
static extendedGCD(aV, aU) {
|
|
if (aV < 0) {
|
|
aV += aU;
|
|
}
|
|
|
|
let result = 0;
|
|
let s = 1;
|
|
while (aV != 0) {
|
|
const quotient = Math.floor(aU / aV);
|
|
aU = EllipticCurveDigitalSignatureAlgorithm.floorMod(aU, aV);
|
|
let temp = aU;
|
|
aU = aV;
|
|
aV = temp;
|
|
result -= quotient * s;
|
|
temp = result;
|
|
result = s;
|
|
s = temp;
|
|
}
|
|
|
|
if (aU != 1) {
|
|
throw new Error("Cannot inverse modulo N, gcd = " + aU);
|
|
}
|
|
return result;
|
|
}
|
|
|
|
static floorMod(x, y) {
|
|
return ((x % y) + y) % y;
|
|
}
|
|
|
|
// static random() {
|
|
// return Math.random();
|
|
// }
|
|
}
|
|
|
|
class EllipticCurve {
|
|
constructor(aParameter) {
|
|
this.n = aParameter.n;
|
|
if (this.n < 5 || this.n > EllipticCurveDigitalSignatureAlgorithm.MAX_MODULUS) {
|
|
throw new Error("Invalid value for modulus: " + this.n);
|
|
}
|
|
|
|
this.a = EllipticCurveDigitalSignatureAlgorithm.floorMod(aParameter.a, this.n);
|
|
this.b = EllipticCurveDigitalSignatureAlgorithm.floorMod(aParameter.b, this.n);
|
|
this.g = aParameter.g;
|
|
this.r = aParameter.r;
|
|
|
|
if (this.r < 5 || this.r > EllipticCurveDigitalSignatureAlgorithm.MAX_ORDER_G) {
|
|
throw new Error("Invalid value for the order of g: " + this.r);
|
|
}
|
|
|
|
console.log();
|
|
console.log(
|
|
"Elliptic curve: y^2 = x^3 + " +
|
|
this.a +
|
|
"x + " +
|
|
this.b +
|
|
" (mod " +
|
|
this.n +
|
|
")"
|
|
);
|
|
this.printPointWithPrefix(this.g, "base point G");
|
|
console.log("order(G, E) = " + this.r);
|
|
}
|
|
|
|
add(aP, aQ) {
|
|
if (aP.isZero()) {
|
|
return aQ;
|
|
}
|
|
if (aQ.isZero()) {
|
|
return aP;
|
|
}
|
|
|
|
let la;
|
|
if (aP.x != aQ.x) {
|
|
la = EllipticCurveDigitalSignatureAlgorithm.floorMod(
|
|
(aP.y - aQ.y) *
|
|
EllipticCurveDigitalSignatureAlgorithm.extendedGCD(aP.x - aQ.x, this.n),
|
|
this.n
|
|
);
|
|
} else if (aP.y == aQ.y && aP.y != 0) {
|
|
la = EllipticCurveDigitalSignatureAlgorithm.floorMod(
|
|
EllipticCurveDigitalSignatureAlgorithm.floorMod(
|
|
EllipticCurveDigitalSignatureAlgorithm.floorMod(aP.x * aP.x, this.n) * 3 +
|
|
this.a,
|
|
this.n
|
|
) * EllipticCurveDigitalSignatureAlgorithm.extendedGCD(2 * aP.y, this.n),
|
|
this.n
|
|
);
|
|
} else {
|
|
return Point.ZERO;
|
|
}
|
|
|
|
const xCoordinate = EllipticCurveDigitalSignatureAlgorithm.floorMod(
|
|
la * la - aP.x - aQ.x,
|
|
this.n
|
|
);
|
|
const yCoordinate = EllipticCurveDigitalSignatureAlgorithm.floorMod(
|
|
la * (aP.x - xCoordinate) - aP.y,
|
|
this.n
|
|
);
|
|
return new Point(xCoordinate, yCoordinate);
|
|
}
|
|
|
|
multiply(aPoint, aK) {
|
|
let result = Point.ZERO;
|
|
|
|
while (aK != 0) {
|
|
if ((aK & 1) == 1) {
|
|
result = this.add(result, aPoint);
|
|
}
|
|
aPoint = this.add(aPoint, aPoint);
|
|
aK >>= 1;
|
|
}
|
|
return result;
|
|
}
|
|
|
|
contains(aPoint) {
|
|
if (aPoint.isZero()) {
|
|
return true;
|
|
}
|
|
|
|
const r = EllipticCurveDigitalSignatureAlgorithm.floorMod(
|
|
EllipticCurveDigitalSignatureAlgorithm.floorMod(
|
|
this.a + aPoint.x * aPoint.x,
|
|
this.n
|
|
) * aPoint.x + this.b,
|
|
this.n
|
|
);
|
|
const s = EllipticCurveDigitalSignatureAlgorithm.floorMod(aPoint.y * aPoint.y, this.n);
|
|
return r == s;
|
|
}
|
|
|
|
discriminant() {
|
|
const constant =
|
|
4 *
|
|
EllipticCurveDigitalSignatureAlgorithm.floorMod(
|
|
this.a * this.a,
|
|
this.n
|
|
) *
|
|
EllipticCurveDigitalSignatureAlgorithm.floorMod(this.a, this.n);
|
|
return EllipticCurveDigitalSignatureAlgorithm.floorMod(
|
|
-16 *
|
|
(EllipticCurveDigitalSignatureAlgorithm.floorMod(this.b * this.b, this.n) *
|
|
27 +
|
|
constant),
|
|
this.n
|
|
);
|
|
}
|
|
|
|
printPointWithPrefix(aPoint, aPrefix) {
|
|
let y = aPoint.y;
|
|
if (aPoint.isZero()) {
|
|
console.log(aPrefix + " (0)");
|
|
} else {
|
|
if (y > this.n - y) {
|
|
y -= this.n;
|
|
}
|
|
console.log(aPrefix + " (" + aPoint.x + ", " + y + ")");
|
|
}
|
|
}
|
|
}
|
|
|
|
class Point {
|
|
constructor(aX, aY) {
|
|
this.x = aX;
|
|
this.y = aY;
|
|
}
|
|
|
|
isZero() {
|
|
return this.x == Point.INFINITY && this.y == 0;
|
|
}
|
|
}
|
|
|
|
class Pair {
|
|
constructor(a, b) {
|
|
this.a = a;
|
|
this.b = b;
|
|
}
|
|
}
|
|
|
|
class Parameter {
|
|
constructor(a, b, n, g, r) {
|
|
this.a = a;
|
|
this.b = b;
|
|
this.n = n;
|
|
this.g = g;
|
|
this.r = r;
|
|
}
|
|
}
|
|
|
|
Point.INFINITY = Number.MAX_SAFE_INTEGER;
|
|
Point.ZERO = new Point(Point.INFINITY, 0);
|
|
|
|
EllipticCurveDigitalSignatureAlgorithm.MAX_MODULUS = 1073741789;
|
|
EllipticCurveDigitalSignatureAlgorithm.MAX_ORDER_G =
|
|
EllipticCurveDigitalSignatureAlgorithm.MAX_MODULUS + 65536;
|
|
|
|
// EllipticCurveDigitalSignatureAlgorithm.RANDOM = Math.random();
|
|
|
|
EllipticCurveDigitalSignatureAlgorithm.main();
|