MontgomeryCurve.cs

using System;
using System.Numerics;
 
namespace Waher.Security.EllipticCurves
{
    public abstract class MontgomeryCurve : PrimeFieldCurve
    {
        private EdwardsCurveBase pair = null;
        private BigInteger a;
 
        public MontgomeryCurve(BigInteger Prime, PointOnCurve BasePoint, BigInteger A,
            BigInteger Order, int Cofactor)
            : base(Prime, BasePoint, Order, Cofactor)
        {
            this.a = A;
        }
 
        public MontgomeryCurve(BigInteger Prime, PointOnCurve BasePoint, BigInteger A,
            BigInteger Order, int Cofactor, byte[] Secret)
            : base(Prime, BasePoint, Order, Cofactor, Secret)
        {
            this.a = A;
        }
 
        public BigInteger A => this.a;
 
        public abstract PointOnCurve ToXY(PointOnCurve UV);
 
        public abstract PointOnCurve ToUV(PointOnCurve XY);
 
        public override void AddTo(ref PointOnCurve P, PointOnCurve Q)
        {
            this.Double(ref P);
        }
 
        public override void Double(ref PointOnCurve P)
        {
            throw new NotSupportedException("Scalar  multiplication is performed using a Montgomery ladder.");
        }
 
        public BigInteger ScalarMultiplication(BigInteger N, BigInteger U)
        {
            return this.ScalarMultiplication(N.ToByteArray(), U);
        }
 
        public abstract BigInteger ScalarMultiplication(byte[] N, BigInteger U);
 
        public override PointOnCurve ScalarMultiplication(byte[] N, PointOnCurve P, bool Normalize)
        {
            return new PointOnCurve(this.ScalarMultiplication(N, P.X), BigInteger.Zero);
        }
 
        public static BigInteger XFunction(byte[] N, BigInteger U,
            BigInteger A24, BigInteger p, int Bits)
        {
            BigInteger x1 = U;
            BigInteger x2 = BigInteger.One;
            BigInteger z2 = BigInteger.Zero;
            BigInteger x3 = U;
            BigInteger z3 = BigInteger.One;
            BigInteger A, AA, B, BB, E, C, D, DA, CB;
            int kt;
            int swap = 0;
 
            kt = (Bits + 7) >> 3;
            if (N.Length < kt)
                Array.Resize(ref N, kt);
 
            while (--Bits >= 0)
            {
                kt = (N[Bits >> 3] >> (Bits & 7)) & 1;
                swap ^= kt;
                ConditionalSwap(swap, ref x2, ref x3);
                ConditionalSwap(swap, ref z2, ref z3);
                swap = kt;
 
                A = BigInteger.Remainder(x2 + z2, p);
                AA = BigInteger.Remainder(A * A, p);
                B = BigInteger.Remainder(x2 - z2, p);
                BB = BigInteger.Remainder(B * B, p);
                E = BigInteger.Remainder(AA - BB, p);
                C = BigInteger.Remainder(x3 + z3, p);
                D = BigInteger.Remainder(x3 - z3, p);
                DA = BigInteger.Remainder(D * A, p);
                CB = BigInteger.Remainder(C * B, p);
 
                x3 = DA + CB;
                x3 = BigInteger.Remainder(x3 * x3, p);
                z3 = DA - CB;
                z3 = BigInteger.Remainder(x1 * BigInteger.Remainder(z3 * z3, p), p);
                x2 = BigInteger.Remainder(AA * BB, p);
                z2 = BigInteger.Remainder(E * (AA + BigInteger.Remainder(A24 * E, p)), p);
            }
 
            ConditionalSwap(swap, ref x2, ref x3);
            ConditionalSwap(swap, ref z2, ref z3);
 
            BigInteger Result = BigInteger.Remainder(x2 * BigInteger.ModPow(z2, p - Two, p), p);
            if (Result.Sign < 0)
                Result += p;
 
            return Result;
        }
 
        private static void ConditionalSwap(int swap, ref BigInteger I2, ref BigInteger I3)
        {
            byte[] x2 = I2.ToByteArray();
            byte[] x3 = I3.ToByteArray();
            int i, c = x2.Length, d = x3.Length;
            byte Dummy;
            byte Mask;
            bool Sign;
 
            if (c < d)
            {
                Sign = (x2[c - 1] & 0x80) != 0;
                Array.Resize(ref x2, d);
 
                if (Sign)
                {
                    while (c < d)
                        x2[c++] = 0xff;
                }
                else
                    c = d;
            }
            else if (d < c)
            {
                Sign = (x3[d - 1] & 0x80) != 0;
                Array.Resize(ref x3, c);
 
                if (Sign)
                {
                    while (d < c)
                        x3[d++] = 0xff;
                }
                //else
                //  d = c;
            }
 
            Mask = (byte)(0xff * swap);
 
            for (i = 0; i < c; i++)
            {
                Dummy = (byte)(Mask & (x2[i] ^ x3[i]));
                x2[i] ^= Dummy;
                x3[i] ^= Dummy;
            }
 
            I2 = new BigInteger(x2);
            I3 = new BigInteger(x3);
        }
 
        public EdwardsCurveBase Pair
        {
            get
            {
                if (this.pair is null)
                    this.pair = this.CreatePair();
 
                return this.pair;
            }
        }
 
        public abstract EdwardsCurveBase CreatePair();
 
        public override PointOnCurve PublicKeyPoint
        {
            get
            {
                PointOnCurve PublicKey = base.PublicKeyPoint;
 
                if (PublicKey.Y.IsZero)
                {
                    PublicKey.Y = this.CalcV(PublicKey.X);
                    this.PublicKeyPoint = PublicKey;
                }
 
                return PublicKey;
            }
        }
 
        public BigInteger CalcV(BigInteger U)
        {
            BigInteger U2 = this.modP.Multiply(U, U);
            BigInteger U3 = this.modP.Multiply(U, U2);
            BigInteger V2 = BigInteger.Remainder(U3 + this.modP.Multiply(this.a, U2) + U, this.Prime);
 
            BigInteger V1 = this.modP.Sqrt(V2);
            if (V1.Sign < 0)
                V1 += this.Prime;
 
            BigInteger V = this.Prime - V1;
            if (V1 < V)
                V = V1;
 
            return V;
        }
 
        public override byte[] Encode(PointOnCurve Point, bool BigEndian)
        {
            byte[] Bin = Point.X.ToByteArray();     // Little-endian
 
            if (Bin.Length != this.orderBytes)
                Array.Resize(ref Bin, this.orderBytes);
 
            if (BigEndian)
                Array.Reverse(Bin);                 // Big-endian
 
            return Bin;
        }
 
        public override PointOnCurve Decode(byte[] Point, bool BigEndian)
        {
            BigInteger U = ToInt(Point, BigEndian);
            PointOnCurve P = new PointOnCurve(U, this.CalcV(U));
 
            return P;
        }
 
        public override void SetPrivateKey(byte[] Secret)
        {
            base.SetPrivateKey(Secret);
            this.pair = null;
        }
 
        public override bool IsPoint(PointOnCurve Point)
        {
            // Check if point matches y²=x³+Ax²+x=x(x²+Ax+1)=x(x(x+A)+1)
 
            BigInteger Left = this.modP.Multiply(Point.Y, Point.Y);
 
            BigInteger Right = this.modP.Multiply(
                Point.X,
                this.modP.Add(
                    1,
                    this.modP.Multiply(
                        Point.X,
                        this.modP.Add(
                            Point.X,
                            this.a))));
 
            return Left == Right;
        }
    }
}