< Summary

Information
Class: Renci.SshNet.Security.Org.BouncyCastle.Math.EC.Abc.Tnaf
Assembly: Renci.SshNet
File(s): \home\appveyor\projects\ssh-net\src\Renci.SshNet\Security\BouncyCastle\math\ec\abc\Tnaf.cs
Line coverage
0%
Covered lines: 0
Uncovered lines: 424
Coverable lines: 424
Total lines: 845
Line coverage: 0%
Branch coverage
0%
Covered branches: 0
Total branches: 118
Branch coverage: 0%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.cctor()100%10%
Norm(...)0%40%
Norm(...)0%40%
Round(...)0%220%
ApproximateDivisionByN(...)0%20%
TauAdicNaf(...)0%160%
Tau(...)100%10%
GetMu(...)0%40%
GetMu(...)0%20%
GetMu(...)0%20%
GetLucas(...)0%100%
GetTw(...)0%40%
GetSi(...)0%40%
GetSi(...)0%20%
GetShiftsForCofactor(...)0%80%
PartModReduction(...)0%20%
MultiplyRTnaf(...)100%10%
MultiplyTnaf(...)100%10%
MultiplyFromTnaf(...)0%80%
TauAdicWNaf(...)0%200%
GetPreComp(...)0%40%

File(s)

\home\appveyor\projects\ssh-net\src\Renci.SshNet\Security\BouncyCastle\math\ec\abc\Tnaf.cs

#LineLine coverage
 1using System;
 2
 3namespace Renci.SshNet.Security.Org.BouncyCastle.Math.EC.Abc
 4{
 5    /**
 6    * Class holding methods for point multiplication based on the window
 7    * &#964;-adic nonadjacent form (WTNAF). The algorithms are based on the
 8    * paper "Improved Algorithms for Arithmetic on Anomalous Binary Curves"
 9    * by Jerome A. Solinas. The paper first appeared in the Proceedings of
 10    * Crypto 1997.
 11    */
 12    internal class Tnaf
 13    {
 014        private static readonly BigInteger MinusOne = BigInteger.One.Negate();
 015        private static readonly BigInteger MinusTwo = BigInteger.Two.Negate();
 016        private static readonly BigInteger MinusThree = BigInteger.Three.Negate();
 017        private static readonly BigInteger Four = BigInteger.ValueOf(4);
 18
 19        /**
 20        * The window width of WTNAF. The standard value of 4 is slightly less
 21        * than optimal for running time, but keeps space requirements for
 22        * precomputation low. For typical curves, a value of 5 or 6 results in
 23        * a better running time. When changing this value, the
 24        * <code>&#945;<sub>u</sub></code>'s must be computed differently, see
 25        * e.g. "Guide to Elliptic Curve Cryptography", Darrel Hankerson,
 26        * Alfred Menezes, Scott Vanstone, Springer-Verlag New York Inc., 2004,
 27        * p. 121-122
 28        */
 29        public const sbyte Width = 4;
 30
 31        /**
 32        * 2<sup>4</sup>
 33        */
 34        public const sbyte Pow2Width = 16;
 35
 36        /**
 37        * The <code>&#945;<sub>u</sub></code>'s for <code>a=0</code> as an array
 38        * of <code>ZTauElement</code>s.
 39        */
 040        public static readonly ZTauElement[] Alpha0 =
 041        {
 042            null,
 043            new ZTauElement(BigInteger.One, BigInteger.Zero), null,
 044            new ZTauElement(MinusThree, MinusOne), null,
 045            new ZTauElement(MinusOne, MinusOne), null,
 046            new ZTauElement(BigInteger.One, MinusOne), null
 047        };
 48
 49        /**
 50        * The <code>&#945;<sub>u</sub></code>'s for <code>a=0</code> as an array
 51        * of TNAFs.
 52        */
 053        public static readonly sbyte[][] Alpha0Tnaf =
 054        {
 055            null, new sbyte[]{1}, null, new sbyte[]{-1, 0, 1}, null, new sbyte[]{1, 0, 1}, null, new sbyte[]{-1, 0, 0, 1
 056        };
 57
 58        /**
 59        * The <code>&#945;<sub>u</sub></code>'s for <code>a=1</code> as an array
 60        * of <code>ZTauElement</code>s.
 61        */
 062        public static readonly ZTauElement[] Alpha1 =
 063        {
 064            null,
 065            new ZTauElement(BigInteger.One, BigInteger.Zero), null,
 066            new ZTauElement(MinusThree, BigInteger.One), null,
 067            new ZTauElement(MinusOne, BigInteger.One), null,
 068            new ZTauElement(BigInteger.One, BigInteger.One), null
 069        };
 70
 71        /**
 72        * The <code>&#945;<sub>u</sub></code>'s for <code>a=1</code> as an array
 73        * of TNAFs.
 74        */
 075        public static readonly sbyte[][] Alpha1Tnaf =
 076        {
 077            null, new sbyte[]{1}, null, new sbyte[]{-1, 0, 1}, null, new sbyte[]{1, 0, 1}, null, new sbyte[]{-1, 0, 0, -
 078        };
 79
 80        /**
 81        * Computes the norm of an element <code>&#955;</code> of
 82        * <code><b>Z</b>[&#964;]</code>.
 83        * @param mu The parameter <code>&#956;</code> of the elliptic curve.
 84        * @param lambda The element <code>&#955;</code> of
 85        * <code><b>Z</b>[&#964;]</code>.
 86        * @return The norm of <code>&#955;</code>.
 87        */
 88        public static BigInteger Norm(sbyte mu, ZTauElement lambda)
 089        {
 90            BigInteger norm;
 91
 92            // s1 = u^2
 093            BigInteger s1 = lambda.u.Multiply(lambda.u);
 94
 95            // s2 = u * v
 096            BigInteger s2 = lambda.u.Multiply(lambda.v);
 97
 98            // s3 = 2 * v^2
 099            BigInteger s3 = lambda.v.Multiply(lambda.v).ShiftLeft(1);
 100
 0101            if (mu == 1)
 0102            {
 0103                norm = s1.Add(s2).Add(s3);
 0104            }
 0105            else if (mu == -1)
 0106            {
 0107                norm = s1.Subtract(s2).Add(s3);
 0108            }
 109            else
 0110            {
 0111                throw new ArgumentException("mu must be 1 or -1");
 112            }
 113
 0114            return norm;
 0115        }
 116
 117        /**
 118        * Computes the norm of an element <code>&#955;</code> of
 119        * <code><b>R</b>[&#964;]</code>, where <code>&#955; = u + v&#964;</code>
 120        * and <code>u</code> and <code>u</code> are real numbers (elements of
 121        * <code><b>R</b></code>).
 122        * @param mu The parameter <code>&#956;</code> of the elliptic curve.
 123        * @param u The real part of the element <code>&#955;</code> of
 124        * <code><b>R</b>[&#964;]</code>.
 125        * @param v The <code>&#964;</code>-adic part of the element
 126        * <code>&#955;</code> of <code><b>R</b>[&#964;]</code>.
 127        * @return The norm of <code>&#955;</code>.
 128        */
 129        public static SimpleBigDecimal Norm(sbyte mu, SimpleBigDecimal u, SimpleBigDecimal v)
 0130        {
 131            SimpleBigDecimal norm;
 132
 133            // s1 = u^2
 0134            SimpleBigDecimal s1 = u.Multiply(u);
 135
 136            // s2 = u * v
 0137            SimpleBigDecimal s2 = u.Multiply(v);
 138
 139            // s3 = 2 * v^2
 0140            SimpleBigDecimal s3 = v.Multiply(v).ShiftLeft(1);
 141
 0142            if (mu == 1)
 0143            {
 0144                norm = s1.Add(s2).Add(s3);
 0145            }
 0146            else if (mu == -1)
 0147            {
 0148                norm = s1.Subtract(s2).Add(s3);
 0149            }
 150            else
 0151            {
 0152                throw new ArgumentException("mu must be 1 or -1");
 153            }
 154
 0155            return norm;
 0156        }
 157
 158        /**
 159        * Rounds an element <code>&#955;</code> of <code><b>R</b>[&#964;]</code>
 160        * to an element of <code><b>Z</b>[&#964;]</code>, such that their difference
 161        * has minimal norm. <code>&#955;</code> is given as
 162        * <code>&#955; = &#955;<sub>0</sub> + &#955;<sub>1</sub>&#964;</code>.
 163        * @param lambda0 The component <code>&#955;<sub>0</sub></code>.
 164        * @param lambda1 The component <code>&#955;<sub>1</sub></code>.
 165        * @param mu The parameter <code>&#956;</code> of the elliptic curve. Must
 166        * equal 1 or -1.
 167        * @return The rounded element of <code><b>Z</b>[&#964;]</code>.
 168        * @throws ArgumentException if <code>lambda0</code> and
 169        * <code>lambda1</code> do not have same scale.
 170        */
 171        public static ZTauElement Round(SimpleBigDecimal lambda0,
 172            SimpleBigDecimal lambda1, sbyte mu)
 0173        {
 0174            int scale = lambda0.Scale;
 0175            if (lambda1.Scale != scale)
 0176                throw new ArgumentException("lambda0 and lambda1 do not have same scale");
 177
 0178            if (!((mu == 1) || (mu == -1)))
 0179                throw new ArgumentException("mu must be 1 or -1");
 180
 0181            BigInteger f0 = lambda0.Round();
 0182            BigInteger f1 = lambda1.Round();
 183
 0184            SimpleBigDecimal eta0 = lambda0.Subtract(f0);
 0185            SimpleBigDecimal eta1 = lambda1.Subtract(f1);
 186
 187            // eta = 2*eta0 + mu*eta1
 0188            SimpleBigDecimal eta = eta0.Add(eta0);
 0189            if (mu == 1)
 0190            {
 0191                eta = eta.Add(eta1);
 0192            }
 193            else
 0194            {
 195                // mu == -1
 0196                eta = eta.Subtract(eta1);
 0197            }
 198
 199            // check1 = eta0 - 3*mu*eta1
 200            // check2 = eta0 + 4*mu*eta1
 0201            SimpleBigDecimal threeEta1 = eta1.Add(eta1).Add(eta1);
 0202            SimpleBigDecimal fourEta1 = threeEta1.Add(eta1);
 203            SimpleBigDecimal check1;
 204            SimpleBigDecimal check2;
 0205            if (mu == 1)
 0206            {
 0207                check1 = eta0.Subtract(threeEta1);
 0208                check2 = eta0.Add(fourEta1);
 0209            }
 210            else
 0211            {
 212                // mu == -1
 0213                check1 = eta0.Add(threeEta1);
 0214                check2 = eta0.Subtract(fourEta1);
 0215            }
 216
 0217            sbyte h0 = 0;
 0218            sbyte h1 = 0;
 219
 220            // if eta >= 1
 0221            if (eta.CompareTo(BigInteger.One) >= 0)
 0222            {
 0223                if (check1.CompareTo(MinusOne) < 0)
 0224                {
 0225                    h1 = mu;
 0226                }
 227                else
 0228                {
 0229                    h0 = 1;
 0230                }
 0231            }
 232            else
 0233            {
 234                // eta < 1
 0235                if (check2.CompareTo(BigInteger.Two) >= 0)
 0236                {
 0237                    h1 = mu;
 0238                }
 0239            }
 240
 241            // if eta < -1
 0242            if (eta.CompareTo(MinusOne) < 0)
 0243            {
 0244                if (check1.CompareTo(BigInteger.One) >= 0)
 0245                {
 0246                    h1 = (sbyte)-mu;
 0247                }
 248                else
 0249                {
 0250                    h0 = -1;
 0251                }
 0252            }
 253            else
 0254            {
 255                // eta >= -1
 0256                if (check2.CompareTo(MinusTwo) < 0)
 0257                {
 0258                    h1 = (sbyte)-mu;
 0259                }
 0260            }
 261
 0262            BigInteger q0 = f0.Add(BigInteger.ValueOf(h0));
 0263            BigInteger q1 = f1.Add(BigInteger.ValueOf(h1));
 0264            return new ZTauElement(q0, q1);
 0265        }
 266
 267        /**
 268        * Approximate division by <code>n</code>. For an integer
 269        * <code>k</code>, the value <code>&#955; = s k / n</code> is
 270        * computed to <code>c</code> bits of accuracy.
 271        * @param k The parameter <code>k</code>.
 272        * @param s The curve parameter <code>s<sub>0</sub></code> or
 273        * <code>s<sub>1</sub></code>.
 274        * @param vm The Lucas Sequence element <code>V<sub>m</sub></code>.
 275        * @param a The parameter <code>a</code> of the elliptic curve.
 276        * @param m The bit length of the finite field
 277        * <code><b>F</b><sub>m</sub></code>.
 278        * @param c The number of bits of accuracy, i.e. the scale of the returned
 279        * <code>SimpleBigDecimal</code>.
 280        * @return The value <code>&#955; = s k / n</code> computed to
 281        * <code>c</code> bits of accuracy.
 282        */
 283        public static SimpleBigDecimal ApproximateDivisionByN(BigInteger k,
 284            BigInteger s, BigInteger vm, sbyte a, int m, int c)
 0285        {
 0286            int _k = (m + 5)/2 + c;
 0287            BigInteger ns = k.ShiftRight(m - _k - 2 + a);
 288
 0289            BigInteger gs = s.Multiply(ns);
 290
 0291            BigInteger hs = gs.ShiftRight(m);
 292
 0293            BigInteger js = vm.Multiply(hs);
 294
 0295            BigInteger gsPlusJs = gs.Add(js);
 0296            BigInteger ls = gsPlusJs.ShiftRight(_k-c);
 0297            if (gsPlusJs.TestBit(_k-c-1))
 0298            {
 299                // round up
 0300                ls = ls.Add(BigInteger.One);
 0301            }
 302
 0303            return new SimpleBigDecimal(ls, c);
 0304        }
 305
 306        /**
 307        * Computes the <code>&#964;</code>-adic NAF (non-adjacent form) of an
 308        * element <code>&#955;</code> of <code><b>Z</b>[&#964;]</code>.
 309        * @param mu The parameter <code>&#956;</code> of the elliptic curve.
 310        * @param lambda The element <code>&#955;</code> of
 311        * <code><b>Z</b>[&#964;]</code>.
 312        * @return The <code>&#964;</code>-adic NAF of <code>&#955;</code>.
 313        */
 314        public static sbyte[] TauAdicNaf(sbyte mu, ZTauElement lambda)
 0315        {
 0316            if (!((mu == 1) || (mu == -1)))
 0317                throw new ArgumentException("mu must be 1 or -1");
 318
 0319            BigInteger norm = Norm(mu, lambda);
 320
 321            // Ceiling of log2 of the norm
 0322            int log2Norm = norm.BitLength;
 323
 324            // If length(TNAF) > 30, then length(TNAF) < log2Norm + 3.52
 0325            int maxLength = log2Norm > 30 ? log2Norm + 4 : 34;
 326
 327            // The array holding the TNAF
 0328            sbyte[] u = new sbyte[maxLength];
 0329            int i = 0;
 330
 331            // The actual length of the TNAF
 0332            int length = 0;
 333
 0334            BigInteger r0 = lambda.u;
 0335            BigInteger r1 = lambda.v;
 336
 0337            while(!((r0.Equals(BigInteger.Zero)) && (r1.Equals(BigInteger.Zero))))
 0338            {
 339                // If r0 is odd
 0340                if (r0.TestBit(0))
 0341                {
 0342                    u[i] = (sbyte) BigInteger.Two.Subtract((r0.Subtract(r1.ShiftLeft(1))).Mod(Four)).IntValue;
 343
 344                    // r0 = r0 - u[i]
 0345                    if (u[i] == 1)
 0346                    {
 0347                        r0 = r0.ClearBit(0);
 0348                    }
 349                    else
 0350                    {
 351                        // u[i] == -1
 0352                        r0 = r0.Add(BigInteger.One);
 0353                    }
 0354                    length = i;
 0355                }
 356                else
 0357                {
 0358                    u[i] = 0;
 0359                }
 360
 0361                BigInteger t = r0;
 0362                BigInteger s = r0.ShiftRight(1);
 0363                if (mu == 1)
 0364                {
 0365                    r0 = r1.Add(s);
 0366                }
 367                else
 0368                {
 369                    // mu == -1
 0370                    r0 = r1.Subtract(s);
 0371                }
 372
 0373                r1 = t.ShiftRight(1).Negate();
 0374                i++;
 0375            }
 376
 0377            length++;
 378
 379            // Reduce the TNAF array to its actual length
 0380            sbyte[] tnaf = new sbyte[length];
 0381            Array.Copy(u, 0, tnaf, 0, length);
 0382            return tnaf;
 0383        }
 384
 385        /**
 386        * Applies the operation <code>&#964;()</code> to an
 387        * <code>AbstractF2mPoint</code>.
 388        * @param p The AbstractF2mPoint to which <code>&#964;()</code> is applied.
 389        * @return <code>&#964;(p)</code>
 390        */
 391        public static AbstractF2mPoint Tau(AbstractF2mPoint p)
 0392        {
 0393            return p.Tau();
 0394        }
 395
 396        /**
 397        * Returns the parameter <code>&#956;</code> of the elliptic curve.
 398        * @param curve The elliptic curve from which to obtain <code>&#956;</code>.
 399        * The curve must be a Koblitz curve, i.e. <code>a</code> Equals
 400        * <code>0</code> or <code>1</code> and <code>b</code> Equals
 401        * <code>1</code>.
 402        * @return <code>&#956;</code> of the elliptic curve.
 403        * @throws ArgumentException if the given ECCurve is not a Koblitz
 404        * curve.
 405        */
 406        public static sbyte GetMu(AbstractF2mCurve curve)
 0407        {
 0408            BigInteger a = curve.A.ToBigInteger();
 409
 410            sbyte mu;
 0411            if (a.SignValue == 0)
 0412            {
 0413                mu = -1;
 0414            }
 0415            else if (a.Equals(BigInteger.One))
 0416            {
 0417                mu = 1;
 0418            }
 419            else
 0420            {
 0421                throw new ArgumentException("No Koblitz curve (ABC), TNAF multiplication not possible");
 422            }
 0423            return mu;
 0424        }
 425
 426        public static sbyte GetMu(ECFieldElement curveA)
 0427        {
 0428            return (sbyte)(curveA.IsZero ? -1 : 1);
 0429        }
 430
 431        public static sbyte GetMu(int curveA)
 0432        {
 0433            return (sbyte)(curveA == 0 ? -1 : 1);
 0434        }
 435
 436        /**
 437        * Calculates the Lucas Sequence elements <code>U<sub>k-1</sub></code> and
 438        * <code>U<sub>k</sub></code> or <code>V<sub>k-1</sub></code> and
 439        * <code>V<sub>k</sub></code>.
 440        * @param mu The parameter <code>&#956;</code> of the elliptic curve.
 441        * @param k The index of the second element of the Lucas Sequence to be
 442        * returned.
 443        * @param doV If set to true, computes <code>V<sub>k-1</sub></code> and
 444        * <code>V<sub>k</sub></code>, otherwise <code>U<sub>k-1</sub></code> and
 445        * <code>U<sub>k</sub></code>.
 446        * @return An array with 2 elements, containing <code>U<sub>k-1</sub></code>
 447        * and <code>U<sub>k</sub></code> or <code>V<sub>k-1</sub></code>
 448        * and <code>V<sub>k</sub></code>.
 449        */
 450        public static BigInteger[] GetLucas(sbyte mu, int k, bool doV)
 0451        {
 0452            if (!(mu == 1 || mu == -1))
 0453                throw new ArgumentException("mu must be 1 or -1");
 454
 455            BigInteger u0;
 456            BigInteger u1;
 457            BigInteger u2;
 458
 0459            if (doV)
 0460            {
 0461                u0 = BigInteger.Two;
 0462                u1 = BigInteger.ValueOf(mu);
 0463            }
 464            else
 0465            {
 0466                u0 = BigInteger.Zero;
 0467                u1 = BigInteger.One;
 0468            }
 469
 0470            for (int i = 1; i < k; i++)
 0471            {
 472                // u2 = mu*u1 - 2*u0;
 0473                BigInteger s = null;
 0474                if (mu == 1)
 0475                {
 0476                    s = u1;
 0477                }
 478                else
 0479                {
 480                    // mu == -1
 0481                    s = u1.Negate();
 0482                }
 483
 0484                u2 = s.Subtract(u0.ShiftLeft(1));
 0485                u0 = u1;
 0486                u1 = u2;
 487                //            System.out.println(i + ": " + u2);
 488                //            System.out.println();
 0489            }
 490
 0491            BigInteger[] retVal = {u0, u1};
 0492            return retVal;
 0493        }
 494
 495        /**
 496        * Computes the auxiliary value <code>t<sub>w</sub></code>. If the width is
 497        * 4, then for <code>mu = 1</code>, <code>t<sub>w</sub> = 6</code> and for
 498        * <code>mu = -1</code>, <code>t<sub>w</sub> = 10</code>
 499        * @param mu The parameter <code>&#956;</code> of the elliptic curve.
 500        * @param w The window width of the WTNAF.
 501        * @return the auxiliary value <code>t<sub>w</sub></code>
 502        */
 503        public static BigInteger GetTw(sbyte mu, int w)
 0504        {
 0505            if (w == 4)
 0506            {
 0507                if (mu == 1)
 0508                {
 0509                    return BigInteger.ValueOf(6);
 510                }
 511                else
 0512                {
 513                    // mu == -1
 0514                    return BigInteger.ValueOf(10);
 515                }
 516            }
 517            else
 0518            {
 519                // For w <> 4, the values must be computed
 0520                BigInteger[] us = GetLucas(mu, w, false);
 0521                BigInteger twoToW = BigInteger.Zero.SetBit(w);
 0522                BigInteger u1invert = us[1].ModInverse(twoToW);
 523                BigInteger tw;
 0524                tw = BigInteger.Two.Multiply(us[0]).Multiply(u1invert).Mod(twoToW);
 525                //System.out.println("mu = " + mu);
 526                //System.out.println("tw = " + tw);
 0527                return tw;
 528            }
 0529        }
 530
 531        /**
 532        * Computes the auxiliary values <code>s<sub>0</sub></code> and
 533        * <code>s<sub>1</sub></code> used for partial modular reduction.
 534        * @param curve The elliptic curve for which to compute
 535        * <code>s<sub>0</sub></code> and <code>s<sub>1</sub></code>.
 536        * @throws ArgumentException if <code>curve</code> is not a
 537        * Koblitz curve (Anomalous Binary Curve, ABC).
 538        */
 539        public static BigInteger[] GetSi(AbstractF2mCurve curve)
 0540        {
 0541            if (!curve.IsKoblitz)
 0542                throw new ArgumentException("si is defined for Koblitz curves only");
 543
 0544            int m = curve.FieldSize;
 0545            int a = curve.A.ToBigInteger().IntValue;
 0546            sbyte mu = GetMu(a);
 0547            int shifts = GetShiftsForCofactor(curve.Cofactor);
 0548            int index = m + 3 - a;
 0549            BigInteger[] ui = GetLucas(mu, index, false);
 550
 0551            if (mu == 1)
 0552            {
 0553                ui[0] = ui[0].Negate();
 0554                ui[1] = ui[1].Negate();
 0555            }
 556
 0557            BigInteger dividend0 = BigInteger.One.Add(ui[1]).ShiftRight(shifts);
 0558            BigInteger dividend1 = BigInteger.One.Add(ui[0]).ShiftRight(shifts).Negate();
 559
 0560            return new BigInteger[] { dividend0, dividend1 };
 0561        }
 562
 563        public static BigInteger[] GetSi(int fieldSize, int curveA, BigInteger cofactor)
 0564        {
 0565            sbyte mu = GetMu(curveA);
 0566            int shifts = GetShiftsForCofactor(cofactor);
 0567            int index = fieldSize + 3 - curveA;
 0568            BigInteger[] ui = GetLucas(mu, index, false);
 0569            if (mu == 1)
 0570            {
 0571                ui[0] = ui[0].Negate();
 0572                ui[1] = ui[1].Negate();
 0573            }
 574
 0575            BigInteger dividend0 = BigInteger.One.Add(ui[1]).ShiftRight(shifts);
 0576            BigInteger dividend1 = BigInteger.One.Add(ui[0]).ShiftRight(shifts).Negate();
 577
 0578            return new BigInteger[] { dividend0, dividend1 };
 0579        }
 580
 581        protected static int GetShiftsForCofactor(BigInteger h)
 0582        {
 0583            if (h != null && h.BitLength < 4)
 0584            {
 0585                int hi = h.IntValue;
 0586                if (hi == 2)
 0587                    return 1;
 0588                if (hi == 4)
 0589                    return 2;
 0590            }
 591
 0592            throw new ArgumentException("h (Cofactor) must be 2 or 4");
 0593        }
 594
 595        /**
 596        * Partial modular reduction modulo
 597        * <code>(&#964;<sup>m</sup> - 1)/(&#964; - 1)</code>.
 598        * @param k The integer to be reduced.
 599        * @param m The bitlength of the underlying finite field.
 600        * @param a The parameter <code>a</code> of the elliptic curve.
 601        * @param s The auxiliary values <code>s<sub>0</sub></code> and
 602        * <code>s<sub>1</sub></code>.
 603        * @param mu The parameter &#956; of the elliptic curve.
 604        * @param c The precision (number of bits of accuracy) of the partial
 605        * modular reduction.
 606        * @return <code>&#961; := k partmod (&#964;<sup>m</sup> - 1)/(&#964; - 1)</code>
 607        */
 608        public static ZTauElement PartModReduction(BigInteger k, int m, sbyte a,
 609            BigInteger[] s, sbyte mu, sbyte c)
 0610        {
 611            // d0 = s[0] + mu*s[1]; mu is either 1 or -1
 612            BigInteger d0;
 0613            if (mu == 1)
 0614            {
 0615                d0 = s[0].Add(s[1]);
 0616            }
 617            else
 0618            {
 0619                d0 = s[0].Subtract(s[1]);
 0620            }
 621
 0622            BigInteger[] v = GetLucas(mu, m, true);
 0623            BigInteger vm = v[1];
 624
 0625            SimpleBigDecimal lambda0 = ApproximateDivisionByN(
 0626                k, s[0], vm, a, m, c);
 627
 0628            SimpleBigDecimal lambda1 = ApproximateDivisionByN(
 0629                k, s[1], vm, a, m, c);
 630
 0631            ZTauElement q = Round(lambda0, lambda1, mu);
 632
 633            // r0 = n - d0*q0 - 2*s1*q1
 0634            BigInteger r0 = k.Subtract(d0.Multiply(q.u)).Subtract(
 0635                BigInteger.ValueOf(2).Multiply(s[1]).Multiply(q.v));
 636
 637            // r1 = s1*q0 - s0*q1
 0638            BigInteger r1 = s[1].Multiply(q.u).Subtract(s[0].Multiply(q.v));
 639
 0640            return new ZTauElement(r0, r1);
 0641        }
 642
 643        /**
 644        * Multiplies a {@link org.bouncycastle.math.ec.AbstractF2mPoint AbstractF2mPoint}
 645        * by a <code>BigInteger</code> using the reduced <code>&#964;</code>-adic
 646        * NAF (RTNAF) method.
 647        * @param p The AbstractF2mPoint to Multiply.
 648        * @param k The <code>BigInteger</code> by which to Multiply <code>p</code>.
 649        * @return <code>k * p</code>
 650        */
 651        public static AbstractF2mPoint MultiplyRTnaf(AbstractF2mPoint p, BigInteger k)
 0652        {
 0653            AbstractF2mCurve curve = (AbstractF2mCurve)p.Curve;
 0654            int m = curve.FieldSize;
 0655            int a = curve.A.ToBigInteger().IntValue;
 0656            sbyte mu = GetMu(a);
 0657            BigInteger[] s = curve.GetSi();
 0658            ZTauElement rho = PartModReduction(k, m, (sbyte)a, s, mu, (sbyte)10);
 659
 0660            return MultiplyTnaf(p, rho);
 0661        }
 662
 663        /**
 664        * Multiplies a {@link org.bouncycastle.math.ec.AbstractF2mPoint AbstractF2mPoint}
 665        * by an element <code>&#955;</code> of <code><b>Z</b>[&#964;]</code>
 666        * using the <code>&#964;</code>-adic NAF (TNAF) method.
 667        * @param p The AbstractF2mPoint to Multiply.
 668        * @param lambda The element <code>&#955;</code> of
 669        * <code><b>Z</b>[&#964;]</code>.
 670        * @return <code>&#955; * p</code>
 671        */
 672        public static AbstractF2mPoint MultiplyTnaf(AbstractF2mPoint p, ZTauElement lambda)
 0673        {
 0674            AbstractF2mCurve curve = (AbstractF2mCurve)p.Curve;
 0675            sbyte mu = GetMu(curve.A);
 0676            sbyte[] u = TauAdicNaf(mu, lambda);
 677
 0678            AbstractF2mPoint q = MultiplyFromTnaf(p, u);
 679
 0680            return q;
 0681        }
 682
 683        /**
 684        * Multiplies a {@link org.bouncycastle.math.ec.AbstractF2mPoint AbstractF2mPoint}
 685        * by an element <code>&#955;</code> of <code><b>Z</b>[&#964;]</code>
 686        * using the <code>&#964;</code>-adic NAF (TNAF) method, given the TNAF
 687        * of <code>&#955;</code>.
 688        * @param p The AbstractF2mPoint to Multiply.
 689        * @param u The the TNAF of <code>&#955;</code>..
 690        * @return <code>&#955; * p</code>
 691        */
 692        public static AbstractF2mPoint MultiplyFromTnaf(AbstractF2mPoint p, sbyte[] u)
 0693        {
 0694            ECCurve curve = p.Curve;
 0695            AbstractF2mPoint q = (AbstractF2mPoint)curve.Infinity;
 0696            AbstractF2mPoint pNeg = (AbstractF2mPoint)p.Negate();
 0697            int tauCount = 0;
 0698            for (int i = u.Length - 1; i >= 0; i--)
 0699            {
 0700                ++tauCount;
 0701                sbyte ui = u[i];
 0702                if (ui != 0)
 0703                {
 0704                    q = q.TauPow(tauCount);
 0705                    tauCount = 0;
 706
 0707                    ECPoint x = ui > 0 ? p : pNeg;
 0708                    q = (AbstractF2mPoint)q.Add(x);
 0709                }
 0710            }
 0711            if (tauCount > 0)
 0712            {
 0713                q = q.TauPow(tauCount);
 0714            }
 0715            return q;
 0716        }
 717
 718        /**
 719        * Computes the <code>[&#964;]</code>-adic window NAF of an element
 720        * <code>&#955;</code> of <code><b>Z</b>[&#964;]</code>.
 721        * @param mu The parameter &#956; of the elliptic curve.
 722        * @param lambda The element <code>&#955;</code> of
 723        * <code><b>Z</b>[&#964;]</code> of which to compute the
 724        * <code>[&#964;]</code>-adic NAF.
 725        * @param width The window width of the resulting WNAF.
 726        * @param pow2w 2<sup>width</sup>.
 727        * @param tw The auxiliary value <code>t<sub>w</sub></code>.
 728        * @param alpha The <code>&#945;<sub>u</sub></code>'s for the window width.
 729        * @return The <code>[&#964;]</code>-adic window NAF of
 730        * <code>&#955;</code>.
 731        */
 732        public static sbyte[] TauAdicWNaf(sbyte mu, ZTauElement lambda,
 733            sbyte width, BigInteger pow2w, BigInteger tw, ZTauElement[] alpha)
 0734        {
 0735            if (!((mu == 1) || (mu == -1)))
 0736                throw new ArgumentException("mu must be 1 or -1");
 737
 0738            BigInteger norm = Norm(mu, lambda);
 739
 740            // Ceiling of log2 of the norm
 0741            int log2Norm = norm.BitLength;
 742
 743            // If length(TNAF) > 30, then length(TNAF) < log2Norm + 3.52
 0744            int maxLength = log2Norm > 30 ? log2Norm + 4 + width : 34 + width;
 745
 746            // The array holding the TNAF
 0747            sbyte[] u = new sbyte[maxLength];
 748
 749            // 2^(width - 1)
 0750            BigInteger pow2wMin1 = pow2w.ShiftRight(1);
 751
 752            // Split lambda into two BigIntegers to simplify calculations
 0753            BigInteger r0 = lambda.u;
 0754            BigInteger r1 = lambda.v;
 0755            int i = 0;
 756
 757            // while lambda <> (0, 0)
 0758            while (!((r0.Equals(BigInteger.Zero))&&(r1.Equals(BigInteger.Zero))))
 0759            {
 760                // if r0 is odd
 0761                if (r0.TestBit(0))
 0762                {
 763                    // uUnMod = r0 + r1*tw Mod 2^width
 0764                    BigInteger uUnMod
 0765                        = r0.Add(r1.Multiply(tw)).Mod(pow2w);
 766
 767                    sbyte uLocal;
 768                    // if uUnMod >= 2^(width - 1)
 0769                    if (uUnMod.CompareTo(pow2wMin1) >= 0)
 0770                    {
 0771                        uLocal = (sbyte) uUnMod.Subtract(pow2w).IntValue;
 0772                    }
 773                    else
 0774                    {
 0775                        uLocal = (sbyte) uUnMod.IntValue;
 0776                    }
 777                    // uLocal is now in [-2^(width-1), 2^(width-1)-1]
 778
 0779                    u[i] = uLocal;
 0780                    bool s = true;
 0781                    if (uLocal < 0)
 0782                    {
 0783                        s = false;
 0784                        uLocal = (sbyte)-uLocal;
 0785                    }
 786                    // uLocal is now >= 0
 787
 0788                    if (s)
 0789                    {
 0790                        r0 = r0.Subtract(alpha[uLocal].u);
 0791                        r1 = r1.Subtract(alpha[uLocal].v);
 0792                    }
 793                    else
 0794                    {
 0795                        r0 = r0.Add(alpha[uLocal].u);
 0796                        r1 = r1.Add(alpha[uLocal].v);
 0797                    }
 0798                }
 799                else
 0800                {
 0801                    u[i] = 0;
 0802                }
 803
 0804                BigInteger t = r0;
 805
 0806                if (mu == 1)
 0807                {
 0808                    r0 = r1.Add(r0.ShiftRight(1));
 0809                }
 810                else
 0811                {
 812                    // mu == -1
 0813                    r0 = r1.Subtract(r0.ShiftRight(1));
 0814                }
 0815                r1 = t.ShiftRight(1).Negate();
 0816                i++;
 0817            }
 0818            return u;
 0819        }
 820
 821        /**
 822        * Does the precomputation for WTNAF multiplication.
 823        * @param p The <code>ECPoint</code> for which to do the precomputation.
 824        * @param a The parameter <code>a</code> of the elliptic curve.
 825        * @return The precomputation array for <code>p</code>.
 826        */
 827        public static AbstractF2mPoint[] GetPreComp(AbstractF2mPoint p, sbyte a)
 0828        {
 0829            sbyte[][] alphaTnaf = (a == 0) ? Tnaf.Alpha0Tnaf : Tnaf.Alpha1Tnaf;
 830
 0831            AbstractF2mPoint[] pu = new AbstractF2mPoint[(uint)(alphaTnaf.Length + 1) >> 1];
 0832            pu[0] = p;
 833
 0834            uint precompLen = (uint)alphaTnaf.Length;
 0835            for (uint i = 3; i < precompLen; i += 2)
 0836            {
 0837                pu[i >> 1] = Tnaf.MultiplyFromTnaf(p, alphaTnaf[i]);
 0838            }
 839
 0840            p.Curve.NormalizeAll(pu);
 841
 0842            return pu;
 0843        }
 844    }
 845}
Generated by: ReportGenerator 5.2.0.0
11/29/2023 - 11:22:39 AM
GitHub | reportgenerator.io

Methods/Properties

.cctor()
Norm(System.SByte,Renci.SshNet.Security.Org.BouncyCastle.Math.EC.Abc.ZTauElement)
Norm(System.SByte,Renci.SshNet.Security.Org.BouncyCastle.Math.EC.Abc.SimpleBigDecimal,Renci.SshNet.Security.Org.BouncyCastle.Math.EC.Abc.SimpleBigDecimal)
Round(Renci.SshNet.Security.Org.BouncyCastle.Math.EC.Abc.SimpleBigDecimal,Renci.SshNet.Security.Org.BouncyCastle.Math.EC.Abc.SimpleBigDecimal,System.SByte)
ApproximateDivisionByN(Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger,Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger,Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger,System.SByte,System.Int32,System.Int32)
TauAdicNaf(System.SByte,Renci.SshNet.Security.Org.BouncyCastle.Math.EC.Abc.ZTauElement)
Tau(Renci.SshNet.Security.Org.BouncyCastle.Math.EC.AbstractF2mPoint)
GetMu(Renci.SshNet.Security.Org.BouncyCastle.Math.EC.AbstractF2mCurve)
GetMu(Renci.SshNet.Security.Org.BouncyCastle.Math.EC.ECFieldElement)
GetMu(System.Int32)
GetLucas(System.SByte,System.Int32,System.Boolean)
GetTw(System.SByte,System.Int32)
GetSi(Renci.SshNet.Security.Org.BouncyCastle.Math.EC.AbstractF2mCurve)
GetSi(System.Int32,System.Int32,Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger)
GetShiftsForCofactor(Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger)
PartModReduction(Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger,System.Int32,System.SByte,Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger[],System.SByte,System.SByte)
MultiplyRTnaf(Renci.SshNet.Security.Org.BouncyCastle.Math.EC.AbstractF2mPoint,Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger)
MultiplyTnaf(Renci.SshNet.Security.Org.BouncyCastle.Math.EC.AbstractF2mPoint,Renci.SshNet.Security.Org.BouncyCastle.Math.EC.Abc.ZTauElement)
MultiplyFromTnaf(Renci.SshNet.Security.Org.BouncyCastle.Math.EC.AbstractF2mPoint,System.SByte[])
TauAdicWNaf(System.SByte,Renci.SshNet.Security.Org.BouncyCastle.Math.EC.Abc.ZTauElement,System.SByte,Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger,Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger,Renci.SshNet.Security.Org.BouncyCastle.Math.EC.Abc.ZTauElement[])
GetPreComp(Renci.SshNet.Security.Org.BouncyCastle.Math.EC.AbstractF2mPoint,System.SByte)