369 lines
10 KiB
C#
369 lines
10 KiB
C#
using System;
|
|
using System.Collections.Generic;
|
|
|
|
public sealed class EllipticCurveDigitalSignatureAlgorithm
|
|
{
|
|
public static void Main(string[] args)
|
|
{
|
|
// 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.
|
|
|
|
List<Parameter> parameters = new List<Parameter>
|
|
{
|
|
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 long f = 0x789abcde; // The message's digital signature hash which is to be verified
|
|
const int d = 0; // Set d > 0 to simulate corrupted data
|
|
|
|
foreach (Parameter parameter in parameters)
|
|
{
|
|
EllipticCurve ellipticCurve = new EllipticCurve(parameter);
|
|
Ecdsa(ellipticCurve, f, d);
|
|
}
|
|
}
|
|
|
|
// Build the digital signature for a message using the hash aF with error bit aD
|
|
private static void Ecdsa(EllipticCurve aCurve, long aF, int aD)
|
|
{
|
|
Point point = aCurve.Multiply(aCurve.G, aCurve.R);
|
|
|
|
if (aCurve.Discriminant() == 0 || aCurve.G.IsZero() || !point.IsZero() || !aCurve.Contains(aCurve.G))
|
|
{
|
|
throw new InvalidOperationException("Invalid parameter in method ecdsa");
|
|
}
|
|
|
|
Console.WriteLine(Environment.NewLine + "key generation");
|
|
long s = 1 + (long)(Random() * (double)(aCurve.R - 1));
|
|
point = aCurve.Multiply(aCurve.G, s);
|
|
Console.WriteLine("private key s = " + s);
|
|
aCurve.PrintPointWithPrefix(point, "public key W = sG");
|
|
|
|
// Find the next highest power of two minus one.
|
|
long t = aCurve.R;
|
|
long i = 1;
|
|
while (i < 64)
|
|
{
|
|
t |= t >> (int)i;
|
|
i <<= 1;
|
|
}
|
|
long f = aF;
|
|
while (f > t)
|
|
{
|
|
f >>= 1;
|
|
}
|
|
Console.WriteLine(Environment.NewLine + "aligned hash " + $"{f:x8}");
|
|
|
|
Pair signature = Signature(aCurve, s, f);
|
|
Console.WriteLine("signature c, d = " + signature.A + ", " + signature.B);
|
|
|
|
long d = aD;
|
|
if (d > 0)
|
|
{
|
|
while (d > t)
|
|
{
|
|
d >>= 1;
|
|
}
|
|
f ^= d;
|
|
Console.WriteLine(Environment.NewLine + "corrupted hash " + $"{f:x8}");
|
|
}
|
|
|
|
Console.WriteLine(Verify(aCurve, point, f, signature) ? "Valid" : "Invalid");
|
|
Console.WriteLine("-----------------");
|
|
}
|
|
|
|
private static bool Verify(EllipticCurve aCurve, Point aPoint, long aF, Pair aSignature)
|
|
{
|
|
if (aSignature.A < 1 || aSignature.A >= aCurve.R || aSignature.B < 1 || aSignature.B >= aCurve.R)
|
|
{
|
|
return false;
|
|
}
|
|
|
|
Console.WriteLine(Environment.NewLine + "signature verification");
|
|
long h = ExtendedGCD(aSignature.B, aCurve.R);
|
|
long h1 = FloorMod(aF * h, aCurve.R);
|
|
long h2 = FloorMod(aSignature.A * h, aCurve.R);
|
|
Console.WriteLine("h1, h2 = " + h1 + ", " + h2);
|
|
Point v = aCurve.Multiply(aCurve.G, h1);
|
|
Point 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;
|
|
}
|
|
long c1 = FloorMod(v.X, aCurve.R);
|
|
Console.WriteLine("c' = " + c1);
|
|
return c1 == aSignature.A;
|
|
}
|
|
|
|
private static Pair Signature(EllipticCurve aCurve, long aS, long aF)
|
|
{
|
|
long c = 0;
|
|
long d = 0;
|
|
long u;
|
|
Point v;
|
|
Console.WriteLine("Signature computation");
|
|
|
|
while (true)
|
|
{
|
|
while (true)
|
|
{
|
|
u = 1 + (long)(Random() * (double)(aCurve.R - 1));
|
|
v = aCurve.Multiply(aCurve.G, u);
|
|
c = FloorMod(v.X, aCurve.R);
|
|
if (c != 0)
|
|
{
|
|
break;
|
|
}
|
|
}
|
|
|
|
d = FloorMod(ExtendedGCD(u, aCurve.R) * FloorMod(aF + aS * c, aCurve.R), aCurve.R);
|
|
if (d != 0)
|
|
{
|
|
break;
|
|
}
|
|
}
|
|
|
|
Console.WriteLine("one-time u = " + u);
|
|
aCurve.PrintPointWithPrefix(v, "V = uG");
|
|
return new Pair(c, d);
|
|
}
|
|
|
|
// Return 1 / aV modulus aU
|
|
private static long ExtendedGCD(long aV, long aU)
|
|
{
|
|
if (aV < 0)
|
|
{
|
|
aV += aU;
|
|
}
|
|
|
|
long result = 0;
|
|
long s = 1;
|
|
while (aV != 0)
|
|
{
|
|
long quotient = FloorDiv(aU, aV);
|
|
aU = FloorMod(aU, aV);
|
|
long temp = aU; aU = aV; aV = temp;
|
|
result -= quotient * s;
|
|
temp = result; result = s; s = temp;
|
|
}
|
|
|
|
if (aU != 1)
|
|
{
|
|
throw new InvalidOperationException("Cannot inverse modulo N, gcd = " + aU);
|
|
}
|
|
return result;
|
|
}
|
|
|
|
private static double Random()
|
|
{
|
|
return _random.NextDouble();
|
|
}
|
|
|
|
// C# implementation of Java's Math.floorMod
|
|
private static long FloorMod(long x, long y)
|
|
{
|
|
return ((x % y) + y) % y;
|
|
}
|
|
|
|
// C# implementation of Java's Math.floorDiv
|
|
private static long FloorDiv(long x, long y)
|
|
{
|
|
long r = x / y;
|
|
if ((x ^ y) < 0 && (r * y != x))
|
|
{
|
|
r--;
|
|
}
|
|
return r;
|
|
}
|
|
|
|
private class EllipticCurve
|
|
{
|
|
public long A { get; }
|
|
public long B { get; }
|
|
public long N { get; }
|
|
public long R { get; }
|
|
public Point G { get; }
|
|
|
|
public EllipticCurve(Parameter aParameter)
|
|
{
|
|
N = aParameter.N;
|
|
if (N < 5 || N > MAX_MODULUS)
|
|
{
|
|
throw new InvalidOperationException("Invalid value for modulus: " + N);
|
|
}
|
|
|
|
A = FloorMod(aParameter.A, N);
|
|
B = FloorMod(aParameter.B, N);
|
|
G = aParameter.G;
|
|
R = aParameter.R;
|
|
|
|
if (R < 5 || R > MAX_ORDER_G)
|
|
{
|
|
throw new InvalidOperationException("Invalid value for the order of g: " + R);
|
|
}
|
|
|
|
Console.WriteLine();
|
|
Console.WriteLine("Elliptic curve: y^2 = x^3 + " + A + "x + " + B + " (mod " + N + ")");
|
|
PrintPointWithPrefix(G, "base point G");
|
|
Console.WriteLine("order(G, E) = " + R);
|
|
}
|
|
|
|
public Point Add(Point aP, Point aQ)
|
|
{
|
|
if (aP.IsZero())
|
|
{
|
|
return aQ;
|
|
}
|
|
if (aQ.IsZero())
|
|
{
|
|
return aP;
|
|
}
|
|
|
|
long la;
|
|
if (aP.X != aQ.X)
|
|
{
|
|
la = FloorMod((aP.Y - aQ.Y) * ExtendedGCD(aP.X - aQ.X, N), N);
|
|
}
|
|
else if (aP.Y == aQ.Y && aP.Y != 0)
|
|
{
|
|
la = FloorMod(FloorMod(FloorMod(
|
|
aP.X * aP.X, N) * 3 + A, N) * ExtendedGCD(2 * aP.Y, N), N);
|
|
}
|
|
else
|
|
{
|
|
return Point.ZERO;
|
|
}
|
|
|
|
long xCoordinate = FloorMod(la * la - aP.X - aQ.X, N);
|
|
long yCoordinate = FloorMod(la * (aP.X - xCoordinate) - aP.Y, N);
|
|
return new Point(xCoordinate, yCoordinate);
|
|
}
|
|
|
|
public Point Multiply(Point aPoint, long aK)
|
|
{
|
|
Point result = Point.ZERO;
|
|
|
|
while (aK != 0)
|
|
{
|
|
if ((aK & 1) == 1)
|
|
{
|
|
result = Add(result, aPoint);
|
|
}
|
|
aPoint = Add(aPoint, aPoint);
|
|
aK >>= 1;
|
|
}
|
|
return result;
|
|
}
|
|
|
|
public bool Contains(Point aPoint)
|
|
{
|
|
if (aPoint.IsZero())
|
|
{
|
|
return true;
|
|
}
|
|
|
|
long r = FloorMod(FloorMod(A + aPoint.X * aPoint.X, N) * aPoint.X + B, N);
|
|
long s = FloorMod(aPoint.Y * aPoint.Y, N);
|
|
return r == s;
|
|
}
|
|
|
|
public long Discriminant()
|
|
{
|
|
long constant = 4 * FloorMod(A * A, N) * FloorMod(A, N);
|
|
return FloorMod(-16 * (FloorMod(B * B, N) * 27 + constant), N);
|
|
}
|
|
|
|
public void PrintPointWithPrefix(Point aPoint, string aPrefix)
|
|
{
|
|
long y = aPoint.Y;
|
|
if (aPoint.IsZero())
|
|
{
|
|
Console.WriteLine(aPrefix + " (0)");
|
|
}
|
|
else
|
|
{
|
|
if (y > N - y)
|
|
{
|
|
y -= N;
|
|
}
|
|
Console.WriteLine(aPrefix + " (" + aPoint.X + ", " + y + ")");
|
|
}
|
|
}
|
|
}
|
|
|
|
private class Point
|
|
{
|
|
public long X { get; }
|
|
public long Y { get; }
|
|
|
|
public Point(long aX, long aY)
|
|
{
|
|
X = aX;
|
|
Y = aY;
|
|
}
|
|
|
|
public bool IsZero()
|
|
{
|
|
return X == INFINITY && Y == 0;
|
|
}
|
|
|
|
private const long INFINITY = long.MaxValue;
|
|
public static readonly Point ZERO = new Point(INFINITY, 0);
|
|
}
|
|
|
|
private class Pair
|
|
{
|
|
public long A { get; }
|
|
public long B { get; }
|
|
|
|
public Pair(long a, long b)
|
|
{
|
|
A = a;
|
|
B = b;
|
|
}
|
|
}
|
|
|
|
private class Parameter
|
|
{
|
|
public long A { get; }
|
|
public long B { get; }
|
|
public long N { get; }
|
|
public Point G { get; }
|
|
public long R { get; }
|
|
|
|
public Parameter(long a, long b, long n, Point g, long r)
|
|
{
|
|
A = a;
|
|
B = b;
|
|
N = n;
|
|
G = g;
|
|
R = r;
|
|
}
|
|
}
|
|
|
|
private const int MAX_MODULUS = 1073741789;
|
|
private const int MAX_ORDER_G = MAX_MODULUS + 65536;
|
|
|
|
private static readonly Random _random = new Random();
|
|
}
|