Digital Signature — C# source

// Digital Signature — Ed25519 / ECDSA P-256 message signing and verification.
// C# 12 / .NET 8 — ported from src/lib/digital-signature.ts (the canonical
// TypeScript implementation). Display source for CosmoDev's polyglot pages.
//
// Key encoding: keys are exchanged as hex of the standard DER structures -
// SPKI (SubjectPublicKeyInfo) for public keys, PKCS8 for private keys - so
// they interoperate with OpenSSL, SSH, JOSE tooling and the TS/Web Crypto
// reference. Signatures are hex of the raw signature bytes: 64 bytes for both
// algorithms (Ed25519 R||S; ECDSA P-256 in IEEE P1363 r||s layout, NOT
// ASN.1 DER — DSASignatureFormat.IeeeP1363FixedFieldConcatenation produces
// exactly that). ECDSA signs the SHA-256 digest of the message.
//
// ECDSA P-256 rides System.Security.Cryptography end-to-end. .NET 8 has no
// Ed25519 in the BCL, so that half is a self-contained RFC 8032
// implementation over System.Numerics.BigInteger — keygen, sign and verify,
// with the same SPKI/PKCS8 wrappers every Ed25519 deployment uses. Like the
// TS reference's BigInt math, it is deterministic and dependency-free, and
// not constant-time (fine for keys generated per session, as this tool does).

using System.Numerics;
using System.Security.Cryptography;
using System.Text;
using System.Text.RegularExpressions;

public enum SignAlgorithm
{
    Ed25519,
    EcdsaP256,
}

/// <summary>A signing key pair, both halves hex-encoded DER.</summary>
public sealed record KeyPair(string PublicKey, string PrivateKey);

public static class DigitalSignature
{
    private static readonly Regex HexRegex = new(@"^(?:[0-9a-fA-F]{2})+$", RegexOptions.Compiled);

    private static void AssertAlgorithm(SignAlgorithm algorithm)
    {
        if (algorithm is not (SignAlgorithm.Ed25519 or SignAlgorithm.EcdsaP256))
        {
            throw new ArgumentException("Unknown algorithm. Use \"ed25519\" or \"ecdsa-p256\".");
        }
    }

    private static string Label(SignAlgorithm algorithm) =>
        algorithm == SignAlgorithm.Ed25519 ? "Ed25519" : "ECDSA P-256";

    private static byte[] HexToBytes(string hex, string what)
    {
        if (hex.Length == 0 || !HexRegex.IsMatch(hex))
        {
            throw new FormatException($"{what} must be a non-empty hex string (pairs of 0-9 / a-f digits).");
        }
        var output = new byte[hex.Length / 2];
        for (var i = 0; i < output.Length; i++)
        {
            output[i] = Convert.ToByte(hex.Substring(i * 2, 2), 16);
        }
        return output;
    }

    private static string ToHex(byte[] bytes) => Convert.ToHexString(bytes).ToLowerInvariant();

    /// <summary>Generate a fresh signing key pair, exported as hex SPKI / PKCS8 keys.</summary>
    public static KeyPair GenerateKeyPair(SignAlgorithm algorithm)
    {
        AssertAlgorithm(algorithm);
        if (algorithm == SignAlgorithm.Ed25519)
        {
            var seed = RandomNumberGenerator.GetBytes(32);
            return new KeyPair(ToHex(Ed25519.WrapSpki(Ed25519.PublicFromSeed(seed))), ToHex(Ed25519.WrapPkcs8(seed)));
        }
        using var ecdsa = ECDsa.Create(ECCurve.NamedCurves.nistP256);
        return new KeyPair(
            ToHex(ecdsa.ExportSubjectPublicKeyInfo()),
            ToHex(ecdsa.ExportPkcs8PrivateKey()));
    }

    private static byte[] MessageBytes(string message) => Encoding.UTF8.GetBytes(message);

    /// <summary>Sign <paramref name="message"/> with a hex PKCS8 private key. Returns the hex signature.</summary>
    public static string SignMessage(string message, string privateKeyHex, SignAlgorithm algorithm)
    {
        AssertAlgorithm(algorithm);
        if (message.Length == 0)
        {
            throw new ArgumentException("Message must not be empty.");
        }
        if (algorithm == SignAlgorithm.Ed25519)
        {
            return ToHex(Ed25519.Sign(MessageBytes(message), HexToBytes(privateKeyHex, "Private key")));
        }
        using var key = ECDsa.Create();
        try
        {
            key.ImportPkcs8PrivateKey(HexToBytes(privateKeyHex, "Private key"), out _);
        }
        catch (CryptographicException)
        {
            throw new FormatException($"Invalid private key for {Label(algorithm)} (expected hex PKCS8).");
        }
        var signature = key.SignData(
            MessageBytes(message), HashAlgorithmName.SHA256,
            DSASignatureFormat.IeeeP1363FixedFieldConcatenation);
        return ToHex(signature);
    }

    /// <summary>
    /// Verify <paramref name="signatureHex"/> against <paramref name="message"/>
    /// with a hex SPKI public key. Returns false when the signature, message or
    /// key simply do not match; throws only for malformed input (non-hex /
    /// wrong key type).
    /// </summary>
    public static bool VerifySignature(string message, string signatureHex, string publicKeyHex, SignAlgorithm algorithm)
    {
        AssertAlgorithm(algorithm);
        var signature = HexToBytes(signatureHex, "Signature");
        if (algorithm == SignAlgorithm.Ed25519)
        {
            return Ed25519.Verify(MessageBytes(message), signature, HexToBytes(publicKeyHex, "Public key"));
        }
        using var key = ECDsa.Create();
        try
        {
            key.ImportSubjectPublicKeyInfo(HexToBytes(publicKeyHex, "Public key"), out _);
        }
        catch (CryptographicException)
        {
            throw new FormatException($"Invalid public key for {Label(algorithm)} (expected hex SPKI).");
        }
        return key.VerifyData(
            MessageBytes(message), signature, HashAlgorithmName.SHA256,
            DSASignatureFormat.IeeeP1363FixedFieldConcatenation);
    }
}

/// <summary>
/// Self-contained RFC 8032 Ed25519 over BigInteger. Points live in extended
/// homogeneous coordinates (X:Y:Z:T); the group order is L = 2^252 + ... and
/// the field is GF(2^255 - 19). Public keys travel as 12-byte-prefix SPKI,
/// private keys as 16-byte-prefix PKCS8 — the universal Ed25519 DER wrappers.
/// </summary>
internal static class Ed25519
{
    private static readonly BigInteger P = BigInteger.Pow(2, 255) - 19;
    private static readonly BigInteger L =
        BigInteger.Parse("7237005577332262213973186563042994240857116359379907606001950938285454250989");
    private static readonly BigInteger D = ModP(-121665 * ModInverse(121666));
    /// <summary>sqrt(-1) mod p — used to lift a non-residue during decompression.</summary>
    private static readonly BigInteger SqrtNeg1 = BigInteger.ModPow(2, (P - 1) / 4, P);

    // SPKI: SEQUENCE { AlgorithmIdentifier(ed25519), BIT STRING(publicKey) }
    private static readonly byte[] SpkiPrefix = Convert.FromHexString("302a300506032b6570032100");
    // PKCS8: SEQUENCE { INTEGER 0, AlgorithmIdentifier(ed25519), OCTET STRING(seed) }
    private static readonly byte[] Pkcs8Prefix = Convert.FromHexString("302e020100300506032b657043220420");

    private readonly record struct Point(BigInteger X, BigInteger Y, BigInteger Z, BigInteger T);

    // The standard base point (x, 4/5), identity point, and helpers.
    private static readonly Point B = new(
        BigInteger.Parse("15112221349535400772501151409588531511454012693041857206046113283949847762202"),
        BigInteger.Parse("46316835694926478169428394003475163141307993866256225615783033603165251855960"),
        BigInteger.One,
        BigInteger.Parse("46827403850823179245072216630277796619892889022238973642481194999929277104191"));

    private static readonly Point Identity = new(BigInteger.Zero, BigInteger.One, BigInteger.One, BigInteger.Zero);

    private static BigInteger ModP(BigInteger a)
    {
        var r = a % P;
        return r.Sign >= 0 ? r : r + P;
    }

    private static BigInteger ModInverse(BigInteger a) => BigInteger.ModPow(ModP(a), P - 2, P);

    /// <summary>Twisted-Edwards point addition in extended coordinates (RFC 8032 §5.1.4).</summary>
    private static Point Add(Point p1, Point p2)
    {
        var a = ModP((p1.Y - p1.X) * (p2.Y - p2.X));
        var b = ModP((p1.Y + p1.X) * (p2.Y + p2.X));
        var c = ModP(2 * D * p1.T * p2.T);
        var d = ModP(2 * p1.Z * p2.Z);
        var e = b - a;
        var f = d - c;
        var g = d + c;
        var h = b + a;
        return new Point(ModP(e * f), ModP(g * h), ModP(f * g), ModP(e * h));
    }

    /// <summary>Double-and-add scalar multiplication (MSB first).</summary>
    private static Point ScalarMult(BigInteger k, Point point)
    {
        var result = Identity;
        var add = point;
        while (k.Sign > 0)
        {
            if (!k.IsEven) result = Add(result, add);
            add = Add(add, add);
            k >>= 1;
        }
        return result;
    }

    private static byte[] ToLittleEndian(BigInteger n, int length)
    {
        var bytes = new byte[length];
        var i = 0;
        while (n.Sign > 0 && i < length)
        {
            bytes[i++] = (byte)(n & 0xff);
            n >>= 8;
        }
        return bytes;
    }

    private static BigInteger FromLittleEndian(byte[] bytes)
    {
        BigInteger n = 0;
        for (var i = bytes.Length - 1; i >= 0; i--)
        {
            n = (n << 8) | bytes[i];
        }
        return n;
    }

    /// <summary>Compress a point: 32 LE bytes of y, with x's low bit stored in bit 255.</summary>
    private static byte[] EncodePoint(Point point)
    {
        var zInv = ModInverse(point.Z);
        var x = ModP(point.X * zInv);
        var y = ModP(point.Y * zInv);
        var bytes = ToLittleEndian(y, 32);
        if (!x.IsEven) bytes[31] |= 0x80;
        return bytes;
    }

    /// <summary>Decompress an encoded point, recovering x from y (RFC 8032 §5.1.3).</summary>
    private static Point DecodePoint(byte[] encoded)
    {
        var sign = (encoded[31] & 0x80) != 0;
        var y = FromLittleEndian(encoded) & ((BigInteger.One << 255) - 1);
        if (y >= P) throw new FormatException("Invalid Ed25519 point encoding.");
        var u = ModP(y * y - 1);
        var v = ModP(D * y * y + 1);
        // x = u * v^3 * (u * v^7)^((p-5)/8)
        var v3 = ModP(v * v * v);
        var v7 = ModP(v3 * v3 * v);
        var x = ModP(u * v3 * BigInteger.ModPow(u * v7, (P - 5) / 8, P));
        var vxx = ModP(v * x * x);
        if (vxx == u)
        {
            // ok
        }
        else if (vxx == P - u)
        {
            x = ModP(x * SqrtNeg1);
        }
        else
        {
            throw new FormatException("Invalid Ed25519 point encoding.");
        }
        if (x.IsZero && sign) throw new FormatException("Invalid Ed25519 point encoding.");
        if (x.IsEven == sign) x = P - x; // match the stored sign bit
        return new Point(x, y, BigInteger.One, ModP(x * y));
    }

    // SHA-512 of concatenated spans.
    private static byte[] Sha512(params byte[][] parts)
    {
        using var sha = SHA512.Create();
        var stream = new MemoryStream();
        foreach (var part in parts)
        {
            stream.Write(part, 0, part.Length);
        }
        stream.Position = 0;
        return sha.ComputeHash(stream);
    }

    /// <summary>Expand the 32-byte seed into the clamped scalar + nonce prefix.</summary>
    private static (BigInteger A, byte[] Prefix) ExpandSeed(byte[] seed)
    {
        if (seed.Length != 32) throw new FormatException("Invalid private key for Ed25519 (expected hex PKCS8).");
        var h = Sha512(seed);
        h[0] &= 248; // a multiple of the cofactor
        h[31] &= 127;
        h[31] |= 64; // a 255-bit scalar
        return (FromLittleEndian(h[..32]), h[32..]);
    }

    internal static byte[] PublicFromSeed(byte[] seed)
    {
        var (a, _) = ExpandSeed(seed);
        return EncodePoint(ScalarMult(a, B));
    }

    internal static byte[] WrapSpki(byte[] publicKey)
    {
        if (publicKey.Length != 32) throw new FormatException("Invalid public key for Ed25519 (expected hex SPKI).");
        return [.. SpkiPrefix, .. publicKey];
    }

    internal static byte[] WrapPkcs8(byte[] seed)
    {
        if (seed.Length != 32) throw new FormatException("Invalid private key for Ed25519 (expected hex PKCS8).");
        return [.. Pkcs8Prefix, .. seed];
    }

    private static byte[] Unwrap(byte[] der, byte[] prefix, string what)
    {
        if (der.Length != prefix.Length + 32 || !der[..prefix.Length].SequenceEqual(prefix))
        {
            throw new FormatException(what);
        }
        return der[prefix.Length..];
    }

    /// <summary>RFC 8032 signing: R = rB, k = H(R‖A‖M), S = (r + k·a) mod L.</summary>
    internal static byte[] Sign(byte[] message, byte[] pkcs8)
    {
        var seed = Unwrap(pkcs8, Pkcs8Prefix, "Invalid private key for Ed25519 (expected hex PKCS8).");
        var (a, prefix) = ExpandSeed(seed);
        var publicKey = EncodePoint(ScalarMult(a, B));

        var r = Mod(FromLittleEndian(Sha512(prefix, message)));
        var rEncoded = EncodePoint(ScalarMult(r, B));
        var k = Mod(FromLittleEndian(Sha512(rEncoded, publicKey, message)));
        var s = Mod(r + k * a);
        return [.. rEncoded, .. ToLittleEndian(s, 32)];

        BigInteger Mod(BigInteger n)
        {
            var r2 = n % L;
            return r2.Sign >= 0 ? r2 : r2 + L;
        }
    }

    /// <summary>RFC 8032 verification: R + k·A == S·B (cofactorless variant).</summary>
    internal static bool Verify(byte[] message, byte[] signature, byte[] spki)
    {
        var publicKey = Unwrap(spki, SpkiPrefix, "Invalid public key for Ed25519 (expected hex SPKI).");
        if (signature.Length != 64) return false;
        try
        {
            var a = DecodePoint(publicKey);
            var r = DecodePoint(signature[..32]);
            var s = FromLittleEndian(signature[32..]);
            if (s >= L) return false; // non-canonical S
            var k = FromLittleEndian(Sha512(signature[..32], publicKey, message));
            // Compare canonical encodings of both sides.
            var left = EncodePoint(Add(r, ScalarMult(k, a)));
            var right = EncodePoint(ScalarMult(s, B));
            return left.SequenceEqual(right);
        }
        catch (FormatException)
        {
            return false; // malformed point encodings simply do not verify
        }
    }
}