ML_DSA.cs

using System;
using System.IO;
using Waher.Security.SHA3;
 
namespace Waher.Security.PQC
{
    public class ML_DSA : ML_Common
    {
        public static readonly ML_DSA ML_DSA_44 = new ML_DSA(39, 128, 1 << 17, (q - 1) / 88, 4, 4, 2, 80, 2560, 1312, 2420);
 
        public static readonly ML_DSA ML_DSA_65 = new ML_DSA(49, 192, 1 << 19, (q - 1) / 32, 6, 5, 4, 55, 4032, 1952, 3309);
 
        public static readonly ML_DSA ML_DSA_87 = new ML_DSA(60, 256, 1 << 19, (q - 1) / 32, 8, 7, 2, 75, 4896, 2592, 4627);
 
        public static ML_DSA GetModel(string Name)
        {
            switch (Name.ToUpper())
            {
                case "ML-DSA-44":
                    return ML_DSA_44;
 
                case "ML-DSA-65":
                    return ML_DSA_65;
 
                case "ML-DSA-87":
                    return ML_DSA_87;
 
                default:
                    throw new ArgumentException("Unknown model name: " + Name, nameof(Name));
            }
        }
 
        private const int n = 256;
        private const int q = 8380417;
        private const int ζ = 1753;                     // 512th root of unity in ℤ𝑞
        private const int d = 13;                       // #dropped bits from t
        private const uint dBitMask = 0x1fff;           // & dBitMask corresponds to mod 2^d.
        private const short twoDHalf = 1 << (d - 1);    // 2^(d-1)
        private const short twoD = 1 << d;              // 2^d
 
        private readonly int τ;                         // # of ±1’s in polynomial c
        private readonly int λ;                         // collision strength of c
        private readonly uint γ1;                       // coefficient range of y 
        private readonly uint γ2;                       // low-order rounding range 
        private readonly byte k;                        // Rows of matrix A
        private readonly byte l;                        // Columns of matrix A
        private readonly byte η;                        // private key range
        private readonly int β;                         // τ*η
        private readonly int ω;                         // max # of 1’s in the hint h
 
        private readonly int twoγ2;                     // 2*γ2
 
        private readonly int privateKeySize;
        private readonly int publicKeySize;
        private readonly int signatureSize;
 
        public ML_DSA(int τ, int λ, uint γ1, uint γ2, byte k, byte l, byte η, int ω,
            int PrivateKeySize, int PublicKeySize, int SignatureSize)
        {
            if (η != 2 && η != 4)
                throw new ArgumentException("η must be 2 or 4.", nameof(η));
 
            this.τ = τ;
            this.λ = λ;
            this.γ1 = γ1;
            this.γ2 = γ2;
            this.k = k;
            this.l = l;
            this.η = η;
            this.β = τ * η;
            this.ω = ω;
 
            this.twoγ2 = (int)(this.γ2 << 1);
 
            this.privateKeySize = PrivateKeySize;
            this.publicKeySize = PublicKeySize;
            this.signatureSize = SignatureSize;
        }
 
        public override int PublicKeyLength => this.publicKeySize;
 
        public override int PrivateKeyLength => this.privateKeySize;
 
        public ML_DSA_Keys KeyGen()
        {
            return this.KeyGen(false);
        }
 
        public ML_DSA_Keys KeyGen(bool ReturnSeed)
        {
            byte[] ξ = CreateSeed();
 
            ML_DSA_Keys Result = this.KeyGen_Internal(ξ, ReturnSeed);
 
            if (!ReturnSeed)
                Clear(ξ);
 
            return Result;
        }
 
        public byte[] Sign(byte[] PrivateKey, byte[] Message, out int RejectionCount)
        {
            return this.Sign(ML_DSA_Keys.FromPrivateKey(PrivateKey), Message,
                out RejectionCount);
        }
 
        public byte[] Sign(ML_DSA_Keys Keys, byte[] Message, out int RejectionCount)
        {
            return this.Sign(Keys, Message, (byte[])null, out RejectionCount);
        }
 
        public byte[] Sign(byte[] PrivateKey, byte[] Message, byte[] Context,
            out int RejectionCount)
        {
            return this.Sign(ML_DSA_Keys.FromPrivateKey(PrivateKey), Message, Context,
                out RejectionCount);
        }
 
        public byte[] Sign(ML_DSA_Keys Keys, byte[] Message, byte[] Context,
            out int RejectionCount)
        {
            byte[] ξ = CreateSeed();
            byte[] Result = this.Sign(Keys, Message, Context, ξ, out RejectionCount);
            Clear(ξ);
 
            return Result;
        }
 
        public byte[] Sign(byte[] PrivateKey, byte[] Message, byte[] Context, byte[] Seed,
            out int RejectionCount)
        {
            return this.Sign(ML_DSA_Keys.FromPrivateKey(PrivateKey), Message, Context,
                Seed, out RejectionCount);
        }
 
        public byte[] Sign(ML_DSA_Keys Keys, byte[] Message, byte[] Context, byte[] Seed,
            out int RejectionCount)
        {
            int MessageLen = Message.Length;
            int ContextLen;
 
            if (Context is null)
            {
                Context = Array.Empty<byte>();
                ContextLen = 0;
            }
            else if ((ContextLen = Context.Length) > 255)
                throw new ArgumentException("Context must be 255 bytes or less.", nameof(Context));
 
            if (Seed is null)
                Seed = new byte[32];
            else if (Seed.Length != 32)
                throw new ArgumentException("Seed must be 32 bytes long.", nameof(Seed));
 
            byte[] Bin = new byte[2 + ContextLen + MessageLen];
            Bin[0] = 0;
            Bin[1] = (byte)ContextLen;
 
            if (ContextLen > 0)
                Buffer.BlockCopy(Context, 0, Bin, 2, ContextLen);
 
            Buffer.BlockCopy(Message, 0, Bin, 2 + ContextLen, MessageLen);
 
            return this.Sign_Internal(Keys, Bin, false, Seed, out RejectionCount);
        }
 
        public bool Verify(byte[] PublicKey, byte[] Message, byte[] Signature)
        {
            return this.Verify(ML_DSA_Keys.FromPublicKey(PublicKey), Message, Signature);
        }
 
        public bool Verify(ML_DSA_Keys Keys, byte[] Message, byte[] Signature)
        {
            return this.Verify(Keys, Message, Signature, null);
        }
 
        public bool Verify(byte[] PublicKey, byte[] Message, byte[] Signature, byte[] Context)
        {
            return this.Verify(ML_DSA_Keys.FromPublicKey(PublicKey), Message, Signature,
                Context);
        }
 
        public bool Verify(ML_DSA_Keys Keys, byte[] Message, byte[] Signature, byte[] Context)
        {
            int MessageLen = Message.Length;
            int ContextLen;
 
            if (Context is null)
            {
                Context = Array.Empty<byte>();
                ContextLen = 0;
            }
            else if ((ContextLen = Context.Length) > 255)
                return false;
 
            byte[] Bin = new byte[2 + ContextLen + MessageLen];
            Bin[0] = 0;
            Bin[1] = (byte)ContextLen;
 
            if (ContextLen > 0)
                Buffer.BlockCopy(Context, 0, Bin, 2, ContextLen);
 
            Buffer.BlockCopy(Message, 0, Bin, 2 + ContextLen, MessageLen);
 
            return this.Verify_Internal(Keys, Bin, false, Signature);
        }
 
        public byte[] Sign(byte[] PrivateKey, byte[] Message, string HashAlgorithm,
            out int RejectionCount)
        {
            return this.Sign(ML_DSA_Keys.FromPrivateKey(PrivateKey), Message,
                HashAlgorithm, out RejectionCount);
        }
 
        public byte[] Sign(ML_DSA_Keys Keys, byte[] Message, string HashAlgorithm,
            out int RejectionCount)
        {
            return this.Sign(Keys, Message, null, HashAlgorithm, out RejectionCount);
        }
 
        public byte[] Sign(byte[] PrivateKey, byte[] Message, byte[] Context,
            string HashAlgorithm, out int RejectionCount)
        {
            return this.Sign(ML_DSA_Keys.FromPrivateKey(PrivateKey), Message, Context,
                HashAlgorithm, out RejectionCount);
        }
 
        public byte[] Sign(ML_DSA_Keys Keys, byte[] Message, byte[] Context,
            string HashAlgorithm, out int RejectionCount)
        {
            byte[] ξ = CreateSeed();
            byte[] Result = this.Sign(Keys, Message, Context, ξ, HashAlgorithm,
                out RejectionCount);
 
            Clear(ξ);
 
            return Result;
        }
 
        public byte[] Sign(byte[] PrivateKey, byte[] Message, byte[] Context, byte[] Seed,
            string HashAlgorithm, out int RejectionCount)
        {
            return this.Sign(ML_DSA_Keys.FromPrivateKey(PrivateKey), Message, Context,
                Seed, HashAlgorithm, out RejectionCount);
        }
 
        public byte[] Sign(ML_DSA_Keys Keys, byte[] Message, byte[] Context, byte[] Seed,
            string HashAlgorithm, out int RejectionCount)
        {
            int ContextLen;
 
            if (Context is null)
            {
                Context = Array.Empty<byte>();
                ContextLen = 0;
            }
            else if ((ContextLen = Context.Length) > 255)
                throw new ArgumentException("Context must be 255 bytes or less.", nameof(Context));
 
            if (Seed is null)
                Seed = new byte[32];
            else if (Seed.Length != 32)
                throw new ArgumentException("Seed must be 32 bytes long.", nameof(Seed));
 
            if (!TryGetHashFunction(HashAlgorithm, out HashFunctionArray H, out byte[] Oid))
                throw new ArgumentException("Unsupported hash algorithm: " + HashAlgorithm, nameof(HashAlgorithm));
 
            Message = H(Message);
 
            int MessageLen = Message.Length;
            int OidLen = Oid.Length;
            int Pos;
 
            byte[] Bin = new byte[2 + ContextLen + OidLen + MessageLen];
            Bin[0] = 1;
            Bin[1] = (byte)ContextLen;
 
            if (ContextLen > 0)
                Buffer.BlockCopy(Context, 0, Bin, 2, ContextLen);
 
            Buffer.BlockCopy(Oid, 0, Bin, Pos = 2 + ContextLen, OidLen);
            Pos += OidLen;
 
            Buffer.BlockCopy(Message, 0, Bin, Pos, MessageLen);
 
            return this.Sign_Internal(Keys, Bin, false, Seed, out RejectionCount);
        }
 
        public byte[] Sign(byte[] PrivateKey, Stream Message, byte[] Context,
            string HashAlgorithm, out int RejectionCount)
        {
            return this.Sign(ML_DSA_Keys.FromPrivateKey(PrivateKey), Message, Context,
                HashAlgorithm, out RejectionCount);
        }
 
        public byte[] Sign(ML_DSA_Keys Keys, Stream Message, byte[] Context,
            string HashAlgorithm, out int RejectionCount)
        {
            byte[] ξ = CreateSeed();
            byte[] Result = this.Sign(Keys, Message, Context, ξ, HashAlgorithm,
                out RejectionCount);
 
            Clear(ξ);
 
            return Result;
        }
 
        public byte[] Sign(byte[] PrivateKey, Stream Message, byte[] Context, byte[] Seed,
            string HashAlgorithm, out int RejectionCount)
        {
            return this.Sign(ML_DSA_Keys.FromPrivateKey(PrivateKey), Message, Context,
                Seed, HashAlgorithm, out RejectionCount);
        }
 
        public byte[] Sign(ML_DSA_Keys Keys, Stream Message, byte[] Context, byte[] Seed,
            string HashAlgorithm, out int RejectionCount)
        {
            int ContextLen;
 
            if (Context is null)
            {
                Context = Array.Empty<byte>();
                ContextLen = 0;
            }
            else if ((ContextLen = Context.Length) > 255)
                throw new ArgumentException("Context must be 255 bytes or less.", nameof(Context));
 
            if (Seed is null)
                Seed = new byte[32];
            else if (Seed.Length != 32)
                throw new ArgumentException("Seed must be 32 bytes long.", nameof(Seed));
 
            if (!TryGetHashFunction(HashAlgorithm, out HashFunctionStream H, out byte[] Oid))
                throw new ArgumentException("Unsupported hash algorithm: " + HashAlgorithm, nameof(HashAlgorithm));
 
            Message.Position = 0;
            byte[] Message2 = H(Message);
 
            int Message2Len = Message2.Length;
            int OidLen = Oid.Length;
            int Pos;
 
            byte[] Bin = new byte[2 + ContextLen + OidLen + Message2Len];
            Bin[0] = 1;
            Bin[1] = (byte)ContextLen;
 
            if (ContextLen > 0)
                Buffer.BlockCopy(Context, 0, Bin, 2, ContextLen);
 
            Buffer.BlockCopy(Oid, 0, Bin, Pos = 2 + ContextLen, OidLen);
            Pos += OidLen;
 
            Buffer.BlockCopy(Message2, 0, Bin, Pos, Message2Len);
 
            return this.Sign_Internal(Keys, Bin, false, Seed, out RejectionCount);
        }
 
        private static bool TryGetHashFunction(string Name, out HashFunctionArray H, out byte[] Oid)
        {
            switch (Name.ToUpper())
            {
                case "SHA256":
                case "SHA-256":
                case "SHA2-256":
                    Oid = oidSha256;
                    H = Hashes.ComputeSHA256Hash;
                    return true;
 
                case "SHA384":
                case "SHA-384":
                case "SHA2-384":
                    Oid = oidSha384;
                    H = Hashes.ComputeSHA384Hash;
                    return true;
 
                case "SHA512":
                case "SHA-512":
                case "SHA2-512":
                    Oid = oidSha512;
                    H = Hashes.ComputeSHA512Hash;
                    return true;
 
                case "SHA3-224":
                    Oid = oidSha3_224;
                    H = new SHA3_224().ComputeVariable;
                    return true;
 
                case "SHA3-256":
                    Oid = oidSha3_256;
                    H = new SHA3_256().ComputeVariable;
                    return true;
 
                case "SHA3-384":
                    Oid = oidSha3_384;
                    H = new SHA3_384().ComputeVariable;
                    return true;
 
                case "SHA3-512":
                    Oid = oidSha3_512;
                    H = new SHA3_512().ComputeVariable;
                    return true;
 
                case "SHAKE128":
                case "SHAKE-128":
                    Oid = oidShake128;
                    H = new SHAKE128(256).ComputeVariable;
                    return true;
 
                case "SHAKE256":
                case "SHAKE-256":
                    Oid = oidShake256;
                    H = new SHAKE256(512).ComputeVariable;
                    return true;
 
                default:
                    Oid = null;
                    H = null;
                    return false;
            }
        }
 
        private static bool TryGetHashFunction(string Name, out HashFunctionStream H, out byte[] Oid)
        {
            switch (Name.ToUpper())
            {
                case "SHA256":
                case "SHA-256":
                case "SHA2-256":
                    Oid = oidSha256;
                    H = Hashes.ComputeSHA256Hash;
                    return true;
 
                case "SHA384":
                case "SHA-384":
                case "SHA2-384":
                    Oid = oidSha384;
                    H = Hashes.ComputeSHA384Hash;
                    return true;
 
                case "SHA512":
                case "SHA-512":
                case "SHA2-512":
                    Oid = oidSha512;
                    H = Hashes.ComputeSHA512Hash;
                    return true;
 
                case "SHA3-224":
                    Oid = oidSha3_224;
                    H = new SHA3_224().ComputeVariable;
                    return true;
 
                case "SHA3-256":
                    Oid = oidSha3_256;
                    H = new SHA3_256().ComputeVariable;
                    return true;
 
                case "SHA3-384":
                    Oid = oidSha3_384;
                    H = new SHA3_384().ComputeVariable;
                    return true;
 
                case "SHA3-512":
                    Oid = oidSha3_512;
                    H = new SHA3_512().ComputeVariable;
                    return true;
 
                case "SHAKE128":
                case "SHAKE-128":
                    Oid = oidShake128;
                    H = new SHAKE128(256).ComputeVariable;
                    return true;
 
                case "SHAKE256":
                case "SHAKE-256":
                    Oid = oidShake256;
                    H = new SHAKE256(512).ComputeVariable;
                    return true;
 
                default:
                    Oid = null;
                    H = null;
                    return false;
            }
        }
 
        private static readonly byte[] oidSha256 = new byte[]
        {
            0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x01
        };
 
        private static readonly byte[] oidSha384 = new byte[]
        {
            0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x02
        };
 
        private static readonly byte[] oidSha512 = new byte[]
        {
            0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x03
        };
 
        private static readonly byte[] oidSha3_224 = new byte[]
        {
            0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x07
        };
        private static readonly byte[] oidSha3_256 = new byte[]
        {
            0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x08
        };
 
        private static readonly byte[] oidSha3_384 = new byte[]
        {
            0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x09
        };
 
        private static readonly byte[] oidSha3_512 = new byte[]
        {
            0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x0a
        };
 
        private static readonly byte[] oidShake128 = new byte[]
        {
            0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x0b
        };
 
        private static readonly byte[] oidShake256 = new byte[]
        {
            0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x0c
        };
 
        public bool Verify(byte[] PublicKey, byte[] Message, byte[] Signature, byte[] Context,
            string HashAlgorithm)
        {
            return this.Verify(ML_DSA_Keys.FromPublicKey(PublicKey), Message, Signature,
                Context, HashAlgorithm);
        }
 
        public bool Verify(ML_DSA_Keys Keys, byte[] Message, byte[] Signature, byte[] Context,
            string HashAlgorithm)
        {
            int ContextLen;
 
            if (Context is null)
            {
                Context = Array.Empty<byte>();
                ContextLen = 0;
            }
            else if ((ContextLen = Context.Length) > 255)
                return false;
 
            if (!TryGetHashFunction(HashAlgorithm, out HashFunctionArray H, out byte[] Oid))
                throw new ArgumentException("Unsupported hash algorithm: " + HashAlgorithm, nameof(HashAlgorithm));
 
            Message = H(Message);
 
            int MessageLen = Message.Length;
            int OidLen = Oid.Length;
            int Pos;
 
            byte[] Bin = new byte[2 + ContextLen + OidLen + MessageLen];
            Bin[0] = 1;
            Bin[1] = (byte)ContextLen;
 
            if (ContextLen > 0)
                Buffer.BlockCopy(Context, 0, Bin, 2, ContextLen);
 
            Buffer.BlockCopy(Oid, 0, Bin, Pos = 2 + ContextLen, OidLen);
            Pos += OidLen;
 
            Buffer.BlockCopy(Message, 0, Bin, Pos, MessageLen);
 
            return this.Verify_Internal(Keys, Bin, false, Signature);
        }
 
        public bool Verify(byte[] PublicKey, Stream Message, byte[] Signature, byte[] Context,
            string HashAlgorithm)
        {
            return this.Verify(ML_DSA_Keys.FromPublicKey(PublicKey), Message, Signature,
                Context, HashAlgorithm);
        }
 
        public bool Verify(ML_DSA_Keys Keys, Stream Message, byte[] Signature, byte[] Context,
            string HashAlgorithm)
        {
            int ContextLen;
 
            if (Context is null)
            {
                Context = Array.Empty<byte>();
                ContextLen = 0;
            }
            else if ((ContextLen = Context.Length) > 255)
                return false;
 
            if (!TryGetHashFunction(HashAlgorithm, out HashFunctionStream H, out byte[] Oid))
                throw new ArgumentException("Unsupported hash algorithm: " + HashAlgorithm, nameof(HashAlgorithm));
 
            Message.Position = 0;
            byte[] Message2 = H(Message);
 
            int Message2Len = Message2.Length;
            int OidLen = Oid.Length;
            int Pos;
 
            byte[] Bin = new byte[2 + ContextLen + OidLen + Message2Len];
            Bin[0] = 1;
            Bin[1] = (byte)ContextLen;
 
            if (ContextLen > 0)
                Buffer.BlockCopy(Context, 0, Bin, 2, ContextLen);
 
            Buffer.BlockCopy(Oid, 0, Bin, Pos = 2 + ContextLen, OidLen);
            Pos += OidLen;
 
            Buffer.BlockCopy(Message2, 0, Bin, Pos, Message2Len);
 
            return this.Verify_Internal(Keys, Bin, false, Signature);
        }
 
        public ML_DSA_Keys KeyGen_Internal(byte[] ξ)
        {
            return this.KeyGen_Internal(ξ, false);
        }
 
        public ML_DSA_Keys KeyGen_Internal(byte[] ξ, bool ReturnSeed)
        {
            if (ξ.Length != 32)
                throw new ArgumentException("Seed must be 32 bytes long.", nameof(ξ));
 
            byte[] Bin = new byte[34];
            Buffer.BlockCopy(ξ, 0, Bin, 0, 32);
            Bin[32] = this.k;
            Bin[33] = this.l;
 
            byte[] Bin2 = H(Bin, 128);
            Clear(Bin);
 
            byte[] ρ = new byte[32];
            Buffer.BlockCopy(Bin2, 0, ρ, 0, 32);
 
            byte[] K = new byte[32];
            Buffer.BlockCopy(Bin2, 96, K, 0, 32);
 
            uint[,][] Â = this.ExpandÂ(ρ);
 
            byte[] B = new byte[66];            // ρ´ || 2 index bytes
            Buffer.BlockCopy(Bin2, 32, B, 0, 64);
 
            short[][] s1 = this.ExpandS(B, this.l);
            short[][] s2 = this.ExpandS(B, this.k);
 
            Clear(B);
 
            uint[][] NTTs1 = NTT(s1);
 
            uint[][] t = new uint[this.k][];
            uint[] f;
            int i, j;
 
            for (i = 0; i < this.k; i++)
            {
                t[i] = f = new uint[n];
 
                for (j = 0; j < this.l; j++)
                    MultiplyNTTsAndAdd(Â[i, j], NTTs1[j], f);
            }
 
            InverseNTT(t);
            AddTo(t, s2);
 
            // Power2Round, decomposes t into two arrays t1, t0, where t=t1*2^d+t0 mod q
            // (Algorithm 35, §7.4)
 
            short[][] t0 = new short[this.k][];
            short[][] t1 = new short[this.k][];
            short[] f0, f1;
            short r0, r1;
            uint r;
 
            for (i = 0; i < this.k; i++)
            {
                f = t[i];
                t0[i] = f0 = new short[n];
                t1[i] = f1 = new short[n];
 
                for (j = 0; j < n; j++)
                {
                    r = f[j];
                    r0 = (short)(r & dBitMask);
 
                    if (r0 > twoDHalf)
                        r0 -= twoD;
 
                    f0[j] = r0;
 
                    r1 = (short)((r - r0) >> d);
 
                    f1[j] = r1;
                }
            }
 
            byte[] PublicKey = this.PublicKeyEncode(ρ, t1);
            byte[] tr = H(PublicKey, 64);
            byte[] PrivateKey = this.PrivateKeyEncode(ρ, K, tr, s1, s2, t0);
 
            Clear(Bin2);
            Clear(t);
            Clear(ρ);
            Clear(K);
            Clear(s1);
            Clear(s2);
            Clear(t0);
 
            return new ML_DSA_Keys(Â, PublicKey, PrivateKey, ReturnSeed ? ξ : null);
        }
 
        private uint[,][] ExpandÂ(byte[] ρ)
        {
            if (ρ.Length != 32)
                throw new ArgumentException("Seed must be 32 bytes long.", nameof(ρ));
 
            uint[,][] Â = new uint[this.k, this.l][];
            byte r, c;
 
            byte[] B = new byte[34];
            Buffer.BlockCopy(ρ, 0, B, 0, 32);
 
            for (r = 0; r < this.k; r++)
            {
                B[33] = r;
 
                for (c = 0; c < this.l; c++)
                {
                    B[32] = c;
                    Â[r, c] = RejNttPoly(B);
                }
            }
 
            Clear(B);
 
            return Â;
        }
 
        private short[][] ExpandS(byte[] Seed, int Nr)
        {
            short[][] s = new short[Nr][];
            byte r = 0;
 
            while (Nr-- > 0)
            {
                s[r++] = this.RejBoundedPoly(Seed);
                Seed[64]++;
            }
 
            return s;
        }
 
        private byte[] PublicKeyEncode(byte[] ρ, short[][] t1)
        {
            if (ρ.Length != 32)
                throw new ArgumentException("Seed must be 32 bytes long.", nameof(ρ));
 
            if (t1.Length != this.k)
                throw new ArgumentException("Invalid polynomial size.", nameof(t1));
 
            byte[] PublicKey = new byte[this.publicKeySize];
            int Pos = 32;
 
            Buffer.BlockCopy(ρ, 0, PublicKey, 0, 32);
 
            for (int i = 0; i < this.k; i++)
                Pos += SimpleBitPack(t1[i], 10, PublicKey, Pos);
 
            return PublicKey;
        }
 
        private byte[] PrivateKeyEncode(byte[] ρ, byte[] K, byte[] tr, short[][] s1, short[][] s2, short[][] t0)
        {
            if (ρ.Length != 32)
                throw new ArgumentException("Seed must be 32 bytes long.", nameof(ρ));
 
            if (K.Length != 32)
                throw new ArgumentException("K must be 32 bytes long.", nameof(K));
 
            if (tr.Length != 64)
                throw new ArgumentException("tr must be 32 bytes long.", nameof(tr));
 
            if (s1.Length != this.l)
                throw new ArgumentException("s1 must be " + this.l + " polynomials long.", nameof(s1));
 
            if (s2.Length != this.k)
                throw new ArgumentException("s2 must be " + this.k + " polynomials long.", nameof(s2));
 
            if (t0.Length != this.k)
                throw new ArgumentException("t0 must be " + this.k + " polynomials long.", nameof(t0));
 
            byte[] PrivateKey = new byte[this.privateKeySize];
            int Pos = 128;
            int i;
 
            Buffer.BlockCopy(ρ, 0, PrivateKey, 0, 32);
            Buffer.BlockCopy(K, 0, PrivateKey, 32, 32);
            Buffer.BlockCopy(tr, 0, PrivateKey, 64, 64);
 
            for (i = 0; i < this.l; i++)
                Pos += BitPack(s1[i], PrivateKey, Pos, this.η, this.η);
 
            for (i = 0; i < this.k; i++)
                Pos += BitPack(s2[i], PrivateKey, Pos, this.η, this.η);
 
            uint b = 1 << (d - 1);
            uint a = b - 1;
 
            for (i = 0; i < this.k; i++)
                Pos += BitPack(t0[i], PrivateKey, Pos, a, b);
 
            return PrivateKey;
        }
 
        private bool TryDecodePrivateKey(byte[] PrivateKey, out byte[] ρ, out byte[] K,
            out byte[] tr, out short[][] s1, out short[][] s2, out short[][] t0)
        {
            if (PrivateKey is null || PrivateKey.Length != this.privateKeySize)
            {
                ρ = null;
                K = null;
                tr = null;
                s1 = null;
                s2 = null;
                t0 = null;
 
                return false;
            }
 
            int Pos = 128;
            int i;
 
            ρ = new byte[32];
            K = new byte[32];
            tr = new byte[64];
            s1 = new short[this.l][];
            s2 = new short[this.k][];
            t0 = new short[this.k][];
 
            Buffer.BlockCopy(PrivateKey, 0, ρ, 0, 32);
            Buffer.BlockCopy(PrivateKey, 32, K, 0, 32);
            Buffer.BlockCopy(PrivateKey, 64, tr, 0, 64);
 
            for (i = 0; i < this.l; i++)
            {
                s1[i] = new short[n];
                Pos += BitUnpack(s1[i], PrivateKey, Pos, this.η, this.η);
            }
 
            for (i = 0; i < this.k; i++)
            {
                s2[i] = new short[n];
                Pos += BitUnpack(s2[i], PrivateKey, Pos, this.η, this.η);
            }
 
            uint b = 1 << (d - 1);
            uint a = b - 1;
 
            for (i = 0; i < this.k; i++)
            {
                t0[i] = new short[n];
                Pos += BitUnpack(t0[i], PrivateKey, Pos, a, b);
            }
 
            return Pos == this.privateKeySize;
        }
 
        private static uint[] RejNttPoly(byte[] Seed)
        {
            SHAKE128 HashFunction = new SHAKE128(0);
            Keccak1600.Context Context = HashFunction.Absorb(Seed);
            uint[] Result = new uint[n];
            int Pos = 0;
 
            while (Pos < n)
            {
                byte[] C = Context.Squeeze(3);
 
                // CoeffFromThreeBytes, Algorithm 14, §7.1
 
                uint i = (uint)(C[2] & 0x7f);
                i <<= 8;
                i |= C[1];
                i <<= 8;
                i |= C[0];
 
                if (i < q)
                    Result[Pos++] = i;
            }
 
            return Result;
        }
 
        public short[] RejBoundedPoly(byte[] Seed)
        {
            SHAKE256 HashFunction = new SHAKE256(0);
            Keccak1600.Context Context = HashFunction.Absorb(Seed);
            short[] Result = new short[n];
            int Pos = 0;
 
            if (this.η == 2)
            {
                while (Pos < n)
                {
                    byte z = Context.Squeeze1();
                    byte b1 = (byte)(z & 0x0f);
                    byte b2 = (byte)(z >> 4);
 
                    // CoeffFromHalfByte, Algorithm 15, §7.1
 
                    if (b1 < 15)
                        Result[Pos++] = (short)(2 - (b1 % 5));
 
                    if (Pos < n && b2 < 15)
                        Result[Pos++] = (short)(2 - (b2 % 5));
                }
            }
            else if (this.η == 4)
            {
                while (Pos < n)
                {
                    byte z = Context.Squeeze1();
                    byte b1 = (byte)(z & 0x0f);
                    byte b2 = (byte)(z >> 4);
 
                    // CoeffFromHalfByte, Algorithm 15, §7.1
 
                    if (b1 < 9)
                        Result[Pos++] = (short)(4 - b1);
 
                    if (Pos < n && b2 < 9)
                        Result[Pos++] = (short)(4 - b2);
                }
            }
            else
                throw new InvalidOperationException("Invalid η.");
 
            return Result;
        }
 
        public static void NTT(uint[] f)
        {
            if (f.Length != n)
                throw new ArgumentException("Polynomial must have " + n + " coefficients.", nameof(f));
 
            int j;
            int Len;
            int Start;
            int m = 0;
            ulong ζ;
            uint t;
 
            for (Len = n >> 1; Len >= 1; Len >>= 1)
            {
                for (Start = 0; Start < n; Start += Len << 1)
                {
                    ζ = nttTransformZeta[++m];
 
                    for (j = Start; j < Start + Len; j++)
                    {
                        t = (uint)(ζ * f[j + Len] % q);
                        f[j + Len] = (f[j] + q - t) % q;
                        f[j] = (f[j] + t) % q;
                    }
                }
            }
        }
 
        public static void NTT(uint[][] f)
        {
            int i, c = f.Length;
 
            for (i = 0; i < c; i++)
                NTT(f[i]);
        }
 
        public static uint[] NTT(short[] f)
        {
            uint[] f0 = ToUIntVector(f);
            NTT(f0);
            return f0;
        }
 
        private static uint[] ToUIntVector(short[] f)
        {
            int i, c = f.Length;
            uint[] f0 = new uint[n];
            short v;
 
            for (i = 0; i < c; i++)
            {
                v = f[i];
                f0[i] = (uint)(v < 0 ? q + v : v);
            }
 
            return f0;
        }
 
        public static uint[][] NTT(short[][] f)
        {
            int i, c = f.Length;
            uint[][] Result = new uint[c][];
 
            for (i = 0; i < c; i++)
                Result[i] = NTT(f[i]);
 
            return Result;
        }
 
        public static void InverseNTT(uint[] f)
        {
            if (f.Length != n)
                throw new ArgumentException("Polynomial must have " + n + " coefficients.", nameof(f));
 
            int j;
            int Len;
            int Len2;
            int StartLen;
            int Start;
            int m = 256;
            ulong ζ;
            uint t;
 
            for (Len = 1; Len < n; Len <<= 1)
            {
                Len2 = Len << 1;
 
                for (Start = 0; Start < n; Start += Len2)
                {
                    ζ = nttTransformZeta[--m];
 
                    StartLen = Start + Len;
                    for (j = Start; j < StartLen; j++)
                    {
                        t = f[j];
                        f[j] = (t + f[j + Len]) % q;
                        f[j + Len] = (uint)(ζ * (f[j + Len] + q - t) % q);
                    }
                }
            }
 
            for (j = 0; j < n; j++)
                f[j] = (uint)(8347681ul * f[j] % q);   // 8347681 = 256^-1 mod q
        }
 
        public static void InverseNTT(uint[][] f)
        {
            int i, c = f.Length;
 
            for (i = 0; i < c; i++)
                InverseNTT(f[i]);
        }
 
        public static void MultiplyNTTsAndAdd(uint[] f, uint[] g, uint[] Result)
        {
            if (f.Length != n || g.Length != n)
                throw new ArgumentException("Polynomials must have " + n + " coefficients.", nameof(f));
 
            int i;
 
            for (i = 0; i < n; i++)
                Result[i] = (uint)((Result[i] + (ulong)f[i] * g[i]) % q);
        }
 
        public static void MultiplyNTTsAndAdd(uint[] f, short[] g, uint[] Result)
        {
            if (f.Length != n || g.Length != n)
                throw new ArgumentException("Polynomials must have " + n + " coefficients.", nameof(f));
 
            int i;
            short v;
 
            for (i = 0; i < n; i++)
            {
                v = g[i];
 
                if (v < 0)
                    Result[i] = (uint)((Result[i] + (ulong)f[i] * (uint)(q + v)) % q);
                else
                    Result[i] = (uint)((Result[i] + (ulong)f[i] * (uint)v) % q);
            }
        }
 
        public static void AddTo(int[] f, short[] g)
        {
            int i;
 
            for (i = 0; i < n; i++)
                f[i] += g[i];
        }
 
        public static void AddTo(int[][] f, short[][] g)
        {
            int i, c = f.Length;
            if (g.Length != c)
                throw new ArgumentException("Vectors must have the same number of polynomials.", nameof(g));
 
            for (i = 0; i < c; i++)
                AddTo(f[i], g[i]);
        }
 
        public static void AddTo(uint[] f, short[] g)
        {
            int i;
            short v;
 
            for (i = 0; i < n; i++)
            {
                v = g[i];
 
                if (v < 0)
                    f[i] = (uint)((f[i] + q + v) % q);
                else
                    f[i] = (uint)((f[i] + v) % q);
            }
        }
 
        public static void AddTo(uint[][] f, short[][] g)
        {
            int i, c = f.Length;
            if (g.Length != c)
                throw new ArgumentException("Vectors must have the same number of polynomials.", nameof(g));
 
            for (i = 0; i < c; i++)
                AddTo(f[i], g[i]);
        }
 
        public static void AddTo(uint[] f, uint[] g)
        {
            int i;
 
            for (i = 0; i < n; i++)
                f[i] = (f[i] + g[i]) % q;
        }
 
        public static void AddTo(uint[][] f, uint[][] g)
        {
            int i, c = f.Length;
            if (g.Length != c)
                throw new ArgumentException("Vectors must have the same number of polynomials.", nameof(g));
 
            for (i = 0; i < c; i++)
                AddTo(f[i], g[i]);
        }
 
        public static void SubtractFrom(uint[] f, short[] g)
        {
            int i;
            short v;
 
            for (i = 0; i < n; i++)
            {
                v = g[i];
 
                if (v < 0)
                    f[i] = (uint)((f[i] - v) % q);
                else
                    f[i] = (uint)((f[i] + q - v) % q);
            }
        }
 
        public static void SubtractFrom(uint[][] f, short[][] g)
        {
            int i, c = f.Length;
            if (g.Length != c)
                throw new ArgumentException("Vectors must have the same number of polynomials.", nameof(g));
 
            for (i = 0; i < c; i++)
                SubtractFrom(f[i], g[i]);
        }
 
        public static void SubtractFrom(uint[] f, uint[] g)
        {
            int i;
 
            for (i = 0; i < n; i++)
                f[i] = (f[i] + q - g[i]) % q;
        }
 
        public static void SubtractFrom(uint[][] f, uint[][] g)
        {
            int i, c = f.Length;
            if (g.Length != c)
                throw new ArgumentException("Vectors must have the same number of polynomials.", nameof(g));
 
            for (i = 0; i < c; i++)
                SubtractFrom(f[i], g[i]);
        }
 
        public static void Negate(uint[] f)
        {
            int i, c = f.Length;
 
            for (i = 0; i < c; i++)
                f[i] = (q - f[i]) % q;   // To avoid different CPU instructions to execute based on if bit is 0 or 1.
        }
 
        public static void Negate(uint[][] f)
        {
            int i, c = f.Length;
 
            for (i = 0; i < c; i++)
                Negate(f[i]);
        }
 
        public static uint[] DotProductNTT(uint[][] v1, uint[][] v2)
        {
            int i, c = v1.Length;
 
            if (v2.Length != c)
                throw new ArgumentException("Vectors must have the same number of polynomials.", nameof(v2));
 
            uint[] Result = new uint[n];
 
            for (i = 0; i < c; i++)
                MultiplyNTTsAndAdd(v1[i], v2[i], Result);
 
            return Result;
        }
 
        public static uint[][] ScalarProductNTT(uint[] c, uint[][] s)
        {
            if (c.Length != n)
                throw new ArgumentException("Polynomials must have " + n + " coefficients.", nameof(c));
 
            int i, j, k = s.Length;
            uint[][] Result = new uint[k][];
            uint[] f;
            uint[] si;
 
            for (i = 0; i < k; i++)
            {
                Result[i] = f = new uint[n];
                si = s[i];
 
                if (si.Length != n)
                    throw new ArgumentException("Polynomials must have " + n + " coefficients.", nameof(s));
 
                for (j = 0; j < n; j++)
                    f[j] = (uint)((long)c[j] * si[j] % q);
            }
 
            return Result;
        }
 
        public static void ShiftLeft(uint[] f, int d)
        {
            int i, c = f.Length;
 
            for (i = 0; i < c; i++)
                f[i] = (uint)(((ulong)f[i] << d) % q);
        }
 
        public static void ShiftLeft(uint[][] f, int d)
        {
            int i, c = f.Length;
 
            for (i = 0; i < c; i++)
                ShiftLeft(f[i], d);
        }
 
        public static int SimpleBitPack(short[] Values, int d, byte[] Output, int Index)
        {
            if (d < 1 || d > 15)
                throw new ArgumentOutOfRangeException(nameof(d), "d must be between 1 and 15.");
 
            int i, c = Values.Length;
            int BitOffset = 0;
            int Index0 = Index;
 
            for (i = 0; i < c; i++)
            {
                ushort Value = (ushort)Values[i];
 
                Value &= ushortBitMask[d];
                Output[Index] |= (byte)(Value << BitOffset);
                BitOffset += d;
                if (BitOffset >= 8)
                {
                    Index++;
                    BitOffset -= 8;
 
                    if (BitOffset > 0)
                    {
                        Output[Index] = (byte)(Value >> (d - BitOffset));
 
                        if (BitOffset >= 8)
                        {
                            BitOffset -= 8;
                            Index++;
 
                            if (BitOffset > 0)
                                Output[Index] = (byte)(Value >> (d - BitOffset));
                        }
                    }
                }
            }
 
            return Index - Index0;
        }
 
        public static int SimpleBitUnpack(short[] Values, byte[] Input, int Index, int d)
        {
            if (d < 1 || d > 15)
                throw new ArgumentOutOfRangeException(nameof(d), "Bitlength of a+b must be between 1 and 15.");
 
            int c = Values.Length;
            int BitOffset = 0;
            int Index0 = Index;
            int i, j;
            int Value;
 
            for (i = 0; i < c; i++)
            {
                Value = Input[Index] >> BitOffset;
                BitOffset += d;
 
                while (BitOffset >= 8)
                {
                    Index++;
                    BitOffset -= 8;
 
                    if (BitOffset > 0)
                    {
                        j = d - BitOffset;
                        Value &= ushortBitMask[j];
                        Value |= Input[Index] << j;
                    }
                }
 
                Values[i] = (short)(Value & ushortBitMask[d]);
            }
 
            return Index - Index0;
        }
 
        public static int BitPack(short[] Values, byte[] Output, int Index, uint a, uint b)
        {
            int d = BitLen(b + a);
            if (d < 1 || d > 15)
                throw new ArgumentOutOfRangeException(nameof(b), "d must be between 1 and 15.");
 
            int c = Values.Length;
            int BitOffset = 0;
            int Index0 = Index;
            int Value;
            int i;
 
            for (i = 0; i < c; i++)
            {
                Value = (int)(b - Values[i]);
                if (Value < 0)
                    Value += q;
 
                Value &= ushortBitMask[d];
                Output[Index] |= (byte)(Value << BitOffset);
                BitOffset += d;
 
                while (BitOffset >= 8)
                {
                    Index++;
                    BitOffset -= 8;
 
                    if (BitOffset > 0)
                        Output[Index] = (byte)(Value >> (d - BitOffset));
                }
            }
 
            return Index - Index0;
        }
 
        public static int BitPack(uint[] Values, byte[] Output, int Index, uint a, uint b, bool MakeSigned)
        {
            int d = BitLen(b + a);
            if (d < 1 || d > 30)
                throw new ArgumentOutOfRangeException(nameof(b), "d must be between 1 and 30.");
 
            int c = Values.Length;
            int BitOffset = 0;
            int BitsLeft;
            int Index0 = Index;
            int Value;
            int i, j;
 
            for (i = 0; i < c; i++)
            {
                Value = (int)Values[i];
 
                if (MakeSigned)
                {
                    Value %= q;
                    if (Value < 0)
                        Value += q;
 
                    if (q - Value < Value)
                        Value -= q;
                }
 
                Value = (int)(b - Value);
 
                Value &= intBitMask[d];
                BitsLeft = d;
 
                if (BitOffset > 0)
                {
                    Output[Index] |= (byte)(Value << BitOffset);
                    j = 8 - BitOffset;
 
                    if (BitsLeft >= j)
                    {
                        BitsLeft -= j;
                        Value >>= j;
                        BitOffset = 0;
                        Index++;
                    }
                    else
                    {
                        BitOffset += BitsLeft;
                        continue;
                    }
                }
 
                while (BitsLeft >= 8)
                {
                    Output[Index++] = (byte)Value;
                    Value >>= 8;
                    BitsLeft -= 8;
                }
 
                if (BitsLeft > 0)
                {
                    Output[Index] = (byte)Value;
                    BitOffset += BitsLeft;
                }
            }
 
            if (BitOffset > 0)
                Index++;
 
            return Index - Index0;
        }
 
        private static int BitLen(uint i)
        {
            int d = 0;
 
            while (i > 0)
            {
                i >>= 1;
                d++;
            }
 
            return d;
        }
 
        public static int BitUnpack(short[] Values, byte[] Input, int Index, uint a, uint b)
        {
            int d = BitLen(b + a);
            if (d < 1 || d > 15)
                throw new ArgumentOutOfRangeException(nameof(b), "Bitlength of a+b must be between 1 and 15.");
 
            int c = Values.Length;
            int BitOffset = 0;
            int Index0 = Index;
            int i, j;
            int Value;
 
            for (i = 0; i < c; i++)
            {
                Value = Input[Index] >> BitOffset;
                BitOffset += d;
 
                while (BitOffset >= 8)
                {
                    Index++;
                    BitOffset -= 8;
 
                    if (BitOffset > 0)
                    {
                        j = d - BitOffset;
                        Value &= ushortBitMask[j];
                        Value |= Input[Index] << j;
                    }
                }
 
                Value &= ushortBitMask[d];
                Values[i] = (short)(b - Value);
            }
 
            return Index - Index0;
        }
 
        public static int BitUnpack(uint[] Values, byte[] Input, int Index, uint a, uint b, bool MakeUnsigned)
        {
            int d = BitLen(b + a);
            if (d < 1 || d > 30)
                throw new ArgumentOutOfRangeException(nameof(b), "Bitlength of a+b must be between 1 and 30.");
 
            int c = Values.Length;
            int BitOffset = 0;
            int Index0 = Index;
            int i, j;
            int Value;
 
            for (i = 0; i < c; i++)
            {
                Value = Input[Index] >> BitOffset;
                BitOffset += d;
 
                while (BitOffset >= 8)
                {
                    Index++;
                    BitOffset -= 8;
 
                    if (BitOffset > 0)
                    {
                        j = d - BitOffset;
                        Value &= intBitMask[j];
                        Value |= Input[Index] << j;
                    }
                }
 
                Value &= intBitMask[d];
                j = Mod((int)(b - Value), q);
                if (MakeUnsigned)
                {
                    if (j < 0)
                        j += q;
                }
                else
                {
                    if (q - j < j)
                        j -= q;
                }
 
                Values[i] = (uint)j;
            }
 
            if (BitOffset > 0)
                Index++;
 
            return Index - Index0;
        }
 
        public static byte[] H(byte[] Data, int l)
        {
            return new SHAKE256(l << 3).ComputeVariable(Data);
        }
 
        public static byte[] G(byte[] Data, int l)
        {
            return new SHAKE128(l << 3).ComputeVariable(Data);
        }
 
        private static readonly uint[] nttTransformZeta = new uint[256]
        {
            0, 4808194, 3765607, 3761513, 5178923, 5496691, 5234739, 5178987,
            7778734, 3542485, 2682288, 2129892, 3764867, 7375178, 557458, 7159240,
            5010068, 4317364, 2663378, 6705802, 4855975, 7946292, 676590, 7044481,
            5152541, 1714295, 2453983, 1460718, 7737789, 4795319, 2815639, 2283733,
            3602218, 3182878, 2740543, 4793971, 5269599, 2101410, 3704823, 1159875,
            394148, 928749, 1095468, 4874037, 2071829, 4361428, 3241972, 2156050,
            3415069, 1759347, 7562881, 4805951, 3756790, 6444618, 6663429, 4430364,
            5483103, 3192354, 556856, 3870317, 2917338, 1853806, 3345963, 1858416,
            3073009, 1277625, 5744944, 3852015, 4183372, 5157610, 5258977, 8106357,
            2508980, 2028118, 1937570, 4564692, 2811291, 5396636, 7270901, 4158088,
            1528066, 482649, 1148858, 5418153, 7814814, 169688, 2462444, 5046034,
            4213992, 4892034, 1987814, 5183169, 1736313, 235407, 5130263, 3258457,
            5801164, 1787943, 5989328, 6125690, 3482206, 4197502, 7080401, 6018354,
            7062739, 2461387, 3035980, 621164, 3901472, 7153756, 2925816, 3374250,
            1356448, 5604662, 2683270, 5601629, 4912752, 2312838, 7727142, 7921254,
            348812, 8052569, 1011223, 6026202, 4561790, 6458164, 6143691, 1744507,
            ζ, 6444997, 5720892, 6924527, 2660408, 6600190, 8321269, 2772600,
            1182243, 87208, 636927, 4415111, 4423672, 6084020, 5095502, 4663471,
            8352605, 822541, 1009365, 5926272, 6400920, 1596822, 4423473, 4620952,
            6695264, 4969849, 2678278, 4611469, 4829411, 635956, 8129971, 5925040,
            4234153, 6607829, 2192938, 6653329, 2387513, 4768667, 8111961, 5199961,
            3747250, 2296099, 1239911, 4541938, 3195676, 2642980, 1254190, 8368000,
            2998219, 141835, 8291116, 2513018, 7025525, 613238, 7070156, 6161950,
            7921677, 6458423, 4040196, 4908348, 2039144, 6500539, 7561656, 6201452,
            6757063, 2105286, 6006015, 6346610, 586241, 7200804, 527981, 5637006,
            6903432, 1994046, 2491325, 6987258, 507927, 7192532, 7655613, 6545891,
            5346675, 8041997, 2647994, 3009748, 5767564, 4148469, 749577, 4357667,
            3980599, 2569011, 6764887, 1723229, 1665318, 2028038, 1163598, 5011144,
            3994671, 8368538, 7009900, 3020393, 3363542, 214880, 545376, 7609976,
            3105558, 7277073, 508145, 7826699, 860144, 3430436, 140244, 6866265,
            6195333, 3123762, 2358373, 6187330, 5365997, 6663603, 2926054, 7987710,
            8077412, 3531229, 4405932, 4606686, 1900052, 7598542, 1054478, 7648983
        };
 
        public byte[] Sign_Internal(byte[] PrivateKey, byte[] Message, bool μPrecomputed,
            byte[] Seed, out int RejectionCount)
        {
            return this.Sign_Internal(ML_DSA_Keys.FromPrivateKey(PrivateKey), Message,
                μPrecomputed, Seed, out RejectionCount);
        }
 
        public byte[] Sign_Internal(ML_DSA_Keys Keys, byte[] Message, bool μPrecomputed,
            byte[] Seed, out int RejectionCount)
        {
            if (Keys.PrivateKey is null ||
                !this.TryDecodePrivateKey(Keys.PrivateKey, out byte[] ρ, out byte[] K,
                out byte[] tr, out short[][] s1, out short[][] s2, out short[][] t0))
            {
                throw new ArgumentException("Invalid private key.", nameof(Keys));
            }
 
            if (Seed is null)
                Seed = new byte[32];
            else if (Seed.Length != 32)
                throw new ArgumentException("Seed must be 32 bytes long.", nameof(Seed));
 
            RejectionCount = 0;
 
            uint[][] NTTs1 = NTT(s1);
            uint[][] NTTs2 = NTT(s2);
            uint[][] NTTt0 = NTT(t0);
 
            uint[,][] Â = Keys.Â;
 
            if (Â is null)
                Keys. =  = this.ExpandÂ(ρ);
            else if (Â.GetLength(0) != this.k || Â.GetLength(1) != this.l)
                throw new ArgumentException("Matrix  must be " + this.k + "x" + this.l + ".", nameof(Â));
 
            byte[] μ;
            byte[] Bin;
            bool Clearμ;
 
            if (μPrecomputed)
            {
                μ = Message;
                Clearμ = false;
            }
            else
            {
                int MessageLen = Message.Length;
                Bin = new byte[64 + MessageLen];
 
                Buffer.BlockCopy(tr, 0, Bin, 0, 64);
                Buffer.BlockCopy(Message, 0, Bin, 64, MessageLen);
 
                μ = H(Bin, 64);
                Clear(Bin);
                Clearμ = true;
            }
 
            Bin = new byte[128];
            Buffer.BlockCopy(K, 0, Bin, 0, 32);
            Buffer.BlockCopy(Seed, 0, Bin, 32, 32);
            Buffer.BlockCopy(μ, 0, Bin, 64, 64);
 
            byte[] ρ2 = H(Bin, 64);
            Clear(Bin);
 
            uint κ = 0;
            byte[] h = null;
            byte[] cSeed = null;
            uint[][] z = null;
            bool Found = false;
            int IterationLimit = 10000;
 
            while (!Found)
            {
                if (--IterationLimit <= 0 || κ > ushort.MaxValue)
                    throw new InvalidOperationException("Unable to calculate signature.");
 
                uint[][] y = this.ExpandMask(ρ2, (ushort)κ);
 
                if (!(z is null))
                    Clear(z);
 
                z = Clone(y);
                NTT(y);
 
                uint[][] w = new uint[this.k][];
                uint[] f;
                int i, j;
 
                for (i = 0; i < this.k; i++)
                {
                    w[i] = f = new uint[n];
 
                    for (j = 0; j < this.l; j++)
                        MultiplyNTTsAndAdd(Â[i, j], y[j], f);
                }
 
                InverseNTT(w);
 
                short[][] w1 = this.HighBits(w);
 
                // w1Encode, Algorithm 28, §7.2
 
                int w1Len = BitLen((uint)((q - 1) / this.twoγ2 - 1));
 
                Bin = new byte[64 + this.k * (w1Len << 5)];
                Buffer.BlockCopy(μ, 0, Bin, 0, 64);
 
                int Pos = 64;
 
                for (i = 0; i < this.k; i++)
                    Pos += SimpleBitPack(w1[i], w1Len, Bin, Pos);
 
                cSeed = H(Bin, this.λ >> 2);
                Clear(Bin);
 
                short[] c = this.SampleInBall(cSeed);
                uint[] NTTc = NTT(c);
 
                uint[][] cs1 = ScalarProductNTT(NTTc, NTTs1);
                InverseNTT(cs1);
 
                uint[][] cs2 = ScalarProductNTT(NTTc, NTTs2);
                InverseNTT(cs2);
 
                AddTo(z, cs1);
 
                if (InfinityNorm(z) < this.γ1 - this.β)
                {
                    SubtractFrom(w, cs2);
                    int[][] r0 = this.LowBits(w);
 
                    if (InfinityNorm(r0) < this.γ2 - this.β)
                    {
                        uint[][] ct0 = ScalarProductNTT(NTTc, NTTt0);
                        InverseNTT(ct0);
 
                        AddTo(w, ct0);
                        Negate(ct0);
 
                        if (InfinityNorm(ct0) < this.γ2)
                            Found = true;
                        else
                            RejectionCount++;
 
                        h = this.MakeAndEncodeHint(ct0, w); // Alters ct0
                        if (h is null)
                        {
                            Found = false;
                            RejectionCount++;
                        }
 
                        Clear(ct0);
                    }
                    else
                        RejectionCount++;
 
                    Clear(r0);
                }
                else
                    RejectionCount++;
 
                Clear(y);
                Clear(w);
                Clear(cs1);
                Clear(cs2);
 
                κ += this.l;
            }
 
            if (Clearμ)
                Clear(μ);
 
            Clear(tr);
            Clear(ρ);
            Clear(K);
            Clear(NTTs1);
            Clear(NTTs2);
            Clear(NTTt0);
 
            return this.EncodeSignature(cSeed, z, h);
        }
 
        private static uint[][] Clone(uint[][] v)
        {
            int i, c = v.Length;
            uint[][] Result = new uint[c][];
 
            for (i = 0; i < c; i++)
                Result[i] = (uint[])v[i].Clone();
 
            return Result;
        }
 
        private static uint InfinityNorm(uint[] f)
        {
            uint Result = 0;
            int i, c = f.Length;
            uint v, w;
 
            for (i = 0; i < c; i++)
            {
                v = f[i];
 
                w = q - v;
                if (w < v)
                    v = w;
 
                if (v > Result)
                    Result = v;
            }
 
            return Result;
        }
 
        private static uint InfinityNorm(uint[][] f)
        {
            uint Result = 0;
            int i, c = f.Length;
            uint v;
 
            for (i = 0; i < c; i++)
            {
                v = InfinityNorm(f[i]);
                if (v > Result)
                    Result = v;
            }
 
            return Result;
        }
 
        private static int InfinityNorm(int[] f)
        {
            int Result = 0;
            int i, c = f.Length;
            int v, w;
 
            for (i = 0; i < c; i++)
            {
                v = f[i];
 
                if (v < 0)
                    v = -v;
                else
                {
                    w = q - v;
                    if (w < v)
                        v = w;
                }
 
                if (v > Result)
                    Result = v;
            }
 
            return Result;
        }
 
        private static int InfinityNorm(int[][] f)
        {
            int Result = 0;
            int i, c = f.Length;
            int v;
 
            for (i = 0; i < c; i++)
            {
                v = InfinityNorm(f[i]);
                if (v > Result)
                    Result = v;
            }
 
            return Result;
        }
 
        private uint[][] ExpandMask(byte[] ρ, ushort μ)
        {
            uint[][] y = new uint[this.l][];
            int c = BitLen(this.γ1 - 1) + 1;
            int r;
            byte[] v;
 
            byte[] ρ1 = new byte[66];
            Buffer.BlockCopy(ρ, 0, ρ1, 0, 64);
 
            for (r = 0; r < this.l; r++)
            {
                ρ1[64] = (byte)μ;
                ρ1[65] = (byte)(μ >> 8);
                μ++;
 
                v = H(ρ1, c << 5);
 
                y[r] = new uint[n];
                BitUnpack(y[r], v, 0, this.γ1 - 1, this.γ1, true);
            }
 
            return y;
        }
 
        private short[][] HighBits(uint[][] w)
        {
            this.Decompose(w, out _, out short[][] Result);
            return Result;
        }
 
        private int[][] LowBits(uint[][] w)
        {
            this.Decompose(w, out int[][] Result, out _);
            return Result;
        }
 
        private void Decompose(uint[][] w, out int[][] w0, out short[][] w1)
        {
            w0 = new int[this.k][]; // LowBits
            w1 = new short[this.k][]; // HighBits
 
            int[] f0;
            short[] f1;
            uint[] f;
            int r0, r1;
            int r;
            int i, j;
 
            for (i = 0; i < this.k; i++)
            {
                f = w[i];
                w0[i] = f0 = new int[n];
                w1[i] = f1 = new short[n];
 
                for (j = 0; j < n; j++)
                {
                    r = (int)f[j];
                    r0 = r % this.twoγ2;
 
                    if (r0 > this.γ2)
                        r0 -= this.twoγ2;
 
                    r1 = r - r0;
                    if (r1 == q - 1)
                    {
                        r1 = 0;
                        r0--;
                    }
                    else
                        r1 /= this.twoγ2;
 
                    f0[j] = r0;
                    f1[j] = (short)r1;
                }
            }
        }
 
        private short[] SampleInBall(byte[] Seed)
        {
            short[] c = new short[n];
            SHAKE256 HashFunction = new SHAKE256(0);
            Keccak1600.Context Context = HashFunction.Absorb(Seed);
            byte[] s = Context.Squeeze(8);
            int i, k;
            byte j;
            byte Bit;
 
            for (i = n - this.τ, k = 0, Bit = 1; i < n; i++)
            {
                j = Context.Squeeze1();
                while (j > i)
                    j = Context.Squeeze1();
 
                c[i] = c[j];
                c[j] = (s[k] & Bit) == 0 ? (short)1 : (short)-1;
 
                Bit <<= 1;
                if (Bit == 0)
                {
                    k++;
                    Bit = 1;
                }
            }
 
            return c;
        }
 
        private byte[] MakeAndEncodeHint(uint[][] z, uint[][] r)
        {
            // MakeHint, (Algorithm 39, §7.4)
 
            short[][] r1 = this.HighBits(r);
 
            AddTo(r, z);
 
            short[][] v1 = this.HighBits(r);
 
            // HintBitPack, (Algorithm 20, §7.1)
 
            byte[] y = new byte[this.ω + this.k];
            byte Index = 0;
            int i, j;
            short[] f, g;
 
            for (i = 0; i < this.k; i++)
            {
                f = r1[i];
                g = v1[i];
 
                for (j = 0; j < n; j++)
                {
                    if (f[j] != g[j])
                    {
                        if (Index >= this.ω)
                            return null;        // ???
 
                        y[Index++] = (byte)j;
                    }
                }
 
                y[this.ω + i] = Index;
            }
 
            return y;
        }
 
        private byte[] EncodeSignature(byte[] c, uint[][] z, byte[] h)
        {
            int l1 = c.Length;
            int l2 = this.l * ((1 + BitLen(this.γ1 - 1)) << 5);
            int l3 = h.Length;
            int Len = l1 + l2 + l3;
            int i;
            byte[] Result = new byte[Len];
 
            Buffer.BlockCopy(c, 0, Result, 0, l1);
 
            for (i = 0; i < this.l; i++)
                l1 += BitPack(z[i], Result, l1, this.γ1 - 1, this.γ1, true);
 
            Buffer.BlockCopy(h, 0, Result, l1, l3);
 
            return Result;
        }
 
        public bool Verify_Internal(byte[] PublicKey, byte[] Message, bool μPrecomputed,
            byte[] Signature)
        {
            return this.Verify_Internal(ML_DSA_Keys.FromPublicKey(PublicKey), Message,
                μPrecomputed, Signature);
        }
 
        public bool Verify_Internal(ML_DSA_Keys Keys, byte[] Message, bool μPrecomputed,
            byte[] Signature)
        {
            if (Keys.PublicKey is null ||
                !this.TryDecodePublicKey(Keys.PublicKey, out byte[] ρ, out short[][] t1))
            {
                return false;
            }
 
            if (!this.TryDecodeSignature(Signature, out byte[] cSeed, out uint[][] z,
                out bool[][] h))
            {
                return false;
            }
 
            if (InfinityNorm(z) >= this.γ1 - this.β)
                return false;
 
            uint[,][] Â = Keys.Â;
 
            if (Â is null)
                Keys. =  = this.ExpandÂ(ρ);
            else if (Â.GetLength(0) != this.k || Â.GetLength(1) != this.l)
                throw new ArgumentException("Matrix  must be " + this.k + "x" + this.l + ".", nameof(Â));
 
            byte[] tr = H(Keys.PublicKey, 64);
            byte[] μ;
            byte[] Bin;
 
            if (μPrecomputed)
                μ = Message;
            else
            {
                int MessageLen = Message.Length;
                Bin = new byte[64 + MessageLen];
 
                Buffer.BlockCopy(tr, 0, Bin, 0, 64);
                Buffer.BlockCopy(Message, 0, Bin, 64, MessageLen);
 
                μ = H(Bin, 64);
            }
 
            short[] c = this.SampleInBall(cSeed);
 
            NTT(z);
 
            uint[] NTTc = NTT(c);
            uint[][] NTTt1 = NTT(t1);
 
            ShiftLeft(NTTt1, d);
            uint[][] w = ScalarProductNTT(NTTc, NTTt1);
            uint[] f;
            int i, j;
 
            Negate(w);
 
            for (i = 0; i < this.k; i++)
            {
                f = w[i];
 
                for (j = 0; j < this.l; j++)
                    MultiplyNTTsAndAdd(Â[i, j], z[j], f);
            }
 
            InverseNTT(w);
 
            short[][] w1 = this.UseHint(h, w);
 
            // w1Encode, Algorithm 28, §7.2
 
            int w1Len = BitLen((uint)((q - 1) / this.twoγ2 - 1));
 
            Bin = new byte[64 + this.k * (w1Len << 5)];
            Buffer.BlockCopy(μ, 0, Bin, 0, 64);
 
            int Pos = 64;
 
            for (i = 0; i < this.k; i++)
                Pos += SimpleBitPack(w1[i], w1Len, Bin, Pos);
 
            int cLen = this.λ >> 2;
            byte[] cSeed2 = H(Bin, cLen);
 
            for (i = 0; i < cLen; i++)
            {
                if (cSeed[i] != cSeed2[i])
                    return false;
            }
 
            return true;
        }
 
        private short[][] UseHint(bool[][] h, uint[][] r)
        {
            short[][] Result = new short[this.k][];
            short[] f;
            int[] r0v2;
            short[] r1v2;
            bool[] h2;
            int i, j;
            int m = (q - 1) / this.twoγ2;
            int r0;
            short r1;
 
            this.Decompose(r, out int[][] r0v, out short[][] r1v);
 
            for (i = 0; i < this.k; i++)
            {
                Result[i] = f = new short[n];
                r0v2 = r0v[i];
                r1v2 = r1v[i];
                h2 = h[i];
 
                for (j = 0; j < n; j++)
                {
                    r0 = r0v2[j];
                    r1 = r1v2[j];
 
                    if (h2[j])
                    {
                        if (r0 > 0)
                            f[j] = (short)((r1 + 1) % m);
                        else
                            f[j] = (short)((r1 + m - 1) % m);
                    }
                    else
                        f[j] = r1;
                }
            }
 
            return Result;
        }
 
        private bool TryDecodePublicKey(byte[] PublicKey, out byte[] ρ, out short[][] t1)
        {
            ρ = null;
            t1 = null;
 
            if (PublicKey is null || PublicKey.Length != this.publicKeySize)
                return false;
 
            ρ = new byte[32];
            Buffer.BlockCopy(PublicKey, 0, ρ, 0, 32);
 
            int Pos = 32;
            short[] f;
 
            t1 = new short[this.k][];
 
            for (int i = 0; i < this.k; i++)
            {
                t1[i] = f = new short[n];
                Pos += SimpleBitUnpack(f, PublicKey, Pos, 10);
            }
 
            return Pos == this.publicKeySize;
        }
 
 
        private bool TryDecodeSignature(byte[] Signature, out byte[] c, out uint[][] z,
            out bool[][] h)
        {
            c = null;
            z = null;
            h = null;
 
            if (Signature is null || Signature.Length != this.signatureSize)
                return false;
 
            int l1 = this.λ >> 2;
            c = new byte[l1];
 
            Buffer.BlockCopy(Signature, 0, c, 0, l1);
 
            uint[] f;
            int i;
 
            z = new uint[this.l][];
 
            for (i = 0; i < this.l; i++)
            {
                z[i] = f = new uint[n];
                l1 += BitUnpack(f, Signature, l1, this.γ1 - 1, this.γ1, true);
            }
 
            int l3 = Signature.Length - l1;
            if (l3 != this.ω + this.k)
                return false;
 
            h = this.HintBitUnpack(Signature, l1);
            if (h is null)
                return false;
 
            return true;
        }
 
        private bool[][] HintBitUnpack(byte[] Input, int Pos)
        {
            bool[][] h = new bool[this.k][];
            bool[] f;
            int Index = 0;
            bool First;
            int i, j;
            byte b, b1, b2;
 
            for (i = 0, j = this.ω; i < this.k; i++, j++)
            {
                h[i] = f = new bool[n];
 
                b = Input[j + Pos];
                if (b < Index || b > this.ω)
                    return null;
 
                First = true;
 
                b2 = b1 = Input[Index + Pos];
 
                while (Index < b)
                {
                    if (First)
                        First = false;
                    else if (b2 >= (b1 = Input[Index + Pos]))
                        return null;
 
                    f[b1] = true;
                    b2 = b1;
                    Index++;
                }
            }
 
            while (Index < this.ω)
            {
                if (Input[Index++ + Pos] != 0)
                    return null;
            }
 
            return h;
        }
 
        private static int Mod(int x, int y)
        {
            x %= y;
            if (x < 0)
                x += y;
            return x;
        }
    }
}