diff options
Diffstat (limited to 'tests/src/JIT/Performance/CodeQuality/V8/Crypto/Crypto.cs')
-rw-r--r-- | tests/src/JIT/Performance/CodeQuality/V8/Crypto/Crypto.cs | 2111 |
1 files changed, 2111 insertions, 0 deletions
diff --git a/tests/src/JIT/Performance/CodeQuality/V8/Crypto/Crypto.cs b/tests/src/JIT/Performance/CodeQuality/V8/Crypto/Crypto.cs new file mode 100644 index 0000000000..23eab8db5b --- /dev/null +++ b/tests/src/JIT/Performance/CodeQuality/V8/Crypto/Crypto.cs @@ -0,0 +1,2111 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. +/* + * Copyright (c) 2003-2005 Tom Wu + * All Rights Reserved. + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND, + * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY + * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. + * + * IN NO EVENT SHALL TOM WU BE LIABLE FOR ANY SPECIAL, INCIDENTAL, + * INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND, OR ANY DAMAGES WHATSOEVER + * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER OR NOT ADVISED OF + * THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF LIABILITY, ARISING OUT + * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + * In addition, the following condition applies: + * + * All redistributions must retain an intact copy of this copyright notice + * and disclaimer. + */ + +// Comment this out to use a fixed random number seed. + +// #define USE_RANDOM_SEED + +// The code has been adapted for use as a benchmark by Microsoft. + +using Microsoft.Xunit.Performance; +using System; +using System.Collections.Generic; +using System.Globalization; + +[assembly: OptimizeForBenchmarks] +[assembly: MeasureInstructionsRetired] + +namespace Crypto +{ + public class Support + { + private const string INPUT = "The quick brown fox jumped over the extremely lazy frogs!"; + + public static int Main(String[] args) + { + int n = 1; + + if (args.Length > 0) + { + n = Int32.Parse(args[0]); + } + + bool verbose = false; + + if (args.Length > 1) + { + switch (args[1]) + { + case "verbose": + verbose = true; + break; + default: + Console.WriteLine("Bad arg: '{0}'.\n", args[1]); + return -1; + } + } + + Measure(n, verbose); + + bool result = s_TEXT.Equals(INPUT); + + return (result ? 100 : -1); + } + + [Benchmark] + public static void Bench() + { + const int Iterations = 10; + const int n = 8; + foreach (var iteration in Benchmark.Iterations) + { + using (iteration.StartMeasurement()) + { + for (int i = 0; i < Iterations; i++) + { + Measure(n, false); + } + } + } + } + + public static void Measure(int n, bool verbose) + { + DateTime start = DateTime.Now; + Setup(); + for (int i = 0; i < n; i++) + { + runEncrypt(verbose); + runDecrypt(verbose); + } + DateTime end = DateTime.Now; + TimeSpan dur = end - start; + if (verbose) + { + Console.WriteLine("Doing {0} iters of Crytpo takes {1} ms; {2} usec/iter.", + n, dur.TotalMilliseconds, dur.TotalMilliseconds * 1000 / n); + } + } + + private static RSAKey s_RSA; + private static String s_TEXT; + + private static void Setup() + { + String nValue = "a5261939975948bb7a58dffe5ff54e65f0498f9175f5a09288810b8975871e99af3b5dd94057b0fc07535f5f97444504fa35169d461d0d30cf0192e307727c065168c788771c561a9400fb49175e9e6aa4e23fe11af69e9412dd23b0cb6684c4c2429bce139e848ab26d0829073351f4acd36074eafd036a5eb83359d2a698d3"; + String eValue = "10001"; + String dValue = "8e9912f6d3645894e8d38cb58c0db81ff516cf4c7e5a14c7f1eddb1459d2cded4d8d293fc97aee6aefb861859c8b6a3d1dfe710463e1f9ddc72048c09751971c4a580aa51eb523357a3cc48d31cfad1d4a165066ed92d4748fb6571211da5cb14bc11b6e2df7c1a559e6d5ac1cd5c94703a22891464fba23d0d965086277a161"; + String pValue = "d090ce58a92c75233a6486cb0a9209bf3583b64f540c76f5294bb97d285eed33aec220bde14b2417951178ac152ceab6da7090905b478195498b352048f15e7d"; + String qValue = "cab575dc652bb66df15a0359609d51d1db184750c00c6698b90ef3465c99655103edbf0d54c56aec0ce3c4d22592338092a126a0cc49f65a4a30d222b411e58f"; + String dmp1Value = "1a24bca8e273df2f0e47c199bbf678604e7df7215480c77c8db39f49b000ce2cf7500038acfff5433b7d582a01f1826e6f4d42e1c57f5e1fef7b12aabc59fd25"; + String dmq1Value = "3d06982efbbe47339e1f6d36b1216b8a741d410b0c662f54f7118b27b9a4ec9d914337eb39841d8666f3034408cf94f5b62f11c402fc994fe15a05493150d9fd"; + String coeffValue = "3a3e731acd8960b7ff9eb81a7ff93bd1cfa74cbd56987db58b4594fb09c09084db1734c8143f98b602b981aaa9243ca28deb69b5b280ee8dcee0fd2625e53250"; + + BigInteger.setupEngine(new BigInteger.AMSig(BigInteger.am3), 28); + + s_RSA = new RSAKey(); + s_RSA.setPublic(nValue, eValue); + s_RSA.setPrivateEx(nValue, eValue, dValue, pValue, qValue, dmp1Value, dmq1Value, coeffValue); + + s_TEXT = INPUT; + } + + public static void runEncrypt(bool verbose) + { + var res = s_RSA.encrypt(s_TEXT); + if (verbose) Console.WriteLine("encrypt '{0}' is '{1}'", s_TEXT, res); + s_TEXT = res; + } + public static void runDecrypt(bool verbose) + { + var res = s_RSA.decrypt(s_TEXT); + if (verbose) Console.WriteLine("decrypt '{0}' is '{1}'", s_TEXT, res); + s_TEXT = res; + } + } + + internal class ListX<T> : List<T> + { + public ListX() : base() { } + public ListX(int cap) : base(cap) { } + + public new T this[int index] + { + get { return base[index]; } + set + { + if (index < Count) + { + base[index] = value; + } + else + { + for (int j = Count; j < index; j++) + { + base.Add(default(T)); + } + base.Add(value); + } + } + } + } + + // Basic JavaScript BN library - subset useful for RSA encryption. + + internal class BigInteger + { + private ListX<int> _array; + private int _t; + private int _s; + + // Bits per digit + private static int s_dbits; + private static int s_BI_DB; + private static int s_BI_DM; + private static int s_BI_DV; + + private static int s_BI_FP; + private static ulong s_BI_FV; + private static int s_BI_F1; + private static int s_BI_F2; + + // JavaScript engine analysis + private const long canary = 0xdeadbeefcafe; + private const bool j_lm = ((canary & 0xffffff) == 0xefcafe); + + // (public) Constructor + public BigInteger(int a, int b, SecureRandom c) + { + _array = new ListX<int>(); + this.fromNumber(a, b, c); + } + + public BigInteger() + { + _array = new ListX<int>(); + } + + public BigInteger(String a) + { + _array = new ListX<int>(); + this.fromString(a, 256); + } + public BigInteger(byte[] ba) + { + _array = new ListX<int>(); + this.fromByteArray(ba); + } + public BigInteger(String a, int b) + { + _array = new ListX<int>(); + this.fromString(a, b); + } + + // return new, unset BigInteger + private static BigInteger nbi() { return new BigInteger(); } + + public delegate int AMSig(BigInteger bi, int i, int x, BigInteger w, int j, int c, int n); + + private static AMSig s_am; + + // am: Compute w_j += (x*this_i), propagate carries, + // c is initial carry, returns final carry. + // c < 3*dvalue, x < 2*dvalue, this_i < dvalue + // We need to select the fastest one that works in this environment. + + // These appear to be unused +#if false + // am1: use a single mult and divide to get the high bits, + // max digit bits should be 26 because + // max internal value = 2*dvalue^2-2*dvalue (< 2^53) + function am1(i,x,w,j,c,n) { + var this_array = this.array; + var w_array = w.array; + while(--n >= 0) { + var v = x*this_array[i++]+w_array[j]+c; + c = Math.floor(v/0x4000000); + w_array[j++] = v&0x3ffffff; + } + return c; + } + + // am2 avoids a big mult-and-extract completely. + // Max digit bits should be <= 30 because we do bitwise ops + // on values up to 2*hdvalue^2-hdvalue-1 (< 2^31) + function am2(i,x,w,j,c,n) { + var this_array = this.array; + var w_array = w.array; + var xl = x&0x7fff, xh = x>>15; + while(--n >= 0) { + var l = this_array[i]&0x7fff; + var h = this_array[i++]>>15; + var m = xh*l+h*xl; + l = xl*l+((m&0x7fff)<<15)+w_array[j]+(c&0x3fffffff); + c = (l>>>30)+(m>>>15)+xh*h+(c>>>30); + w_array[j++] = l&0x3fffffff; + } + return c; + } +#endif + + // Alternately, set max digit bits to 28 since some + // browsers slow down when dealing with 32-bit numbers. + public static int am3(BigInteger bi, int i, int x, BigInteger w, int j, int c, int n) + { + var this_array = bi._array; + var w_array = w._array; + + var xl = x & 0x3fff; var xh = x >> 14; + while (--n >= 0) + { + var l = this_array[i] & 0x3fff; + var h = this_array[i++] >> 14; + var m = xh * l + h * xl; + l = xl * l + ((m & 0x3fff) << 14) + w_array[j] + c; + c = (l >> 28) + (m >> 14) + xh * h; + w_array[j++] = l & 0xfffffff; + } + return c; + } + + +#if false + // This is tailored to VMs with 2-bit tagging. It makes sure + // that all the computations stay within the 29 bits available. + function am4(i,x,w,j,c,n) { + var this_array = this.array; + var w_array = w.array; + + var xl = x&0x1fff, xh = x>>13; + while(--n >= 0) { + var l = this_array[i]&0x1fff; + var h = this_array[i++]>>13; + var m = xh*l+h*xl; + l = xl*l+((m&0x1fff)<<13)+w_array[j]+c; + c = (l>>26)+(m>>13)+xh*h; + w_array[j++] = l&0x3ffffff; + } + return c; + } +#endif + + // Digit conversions + private const String BI_RM = "0123456789abcdefghijklmnopqrstuvwxyz"; + private static int[] s_BI_RC; + + // am3/28 is best for SM, Rhino, but am4/26 is best for v8. + // Kestrel (Opera 9.5) gets its best result with am4/26. + // IE7 does 9% better with am3/28 than with am4/26. + // Firefox (SM) gets 10% faster with am3/28 than with am4/26. + + + public static void setupEngine(AMSig fn, int bits) + { + BigInteger.s_am = fn; + s_dbits = bits; + + s_BI_DB = s_dbits; + s_BI_DM = ((((int)1) << (int)s_dbits) - 1); + s_BI_DV = (((int)1) << (int)s_dbits); + + s_BI_FP = 52; + // The RHS had been Math.Pow(2,BI_FP); + s_BI_FV = (((ulong)1) << (int)s_BI_FP); + s_BI_F1 = s_BI_FP - s_dbits; + s_BI_F2 = 2 * s_dbits - s_BI_FP; + + s_BI_RC = new int[256]; + + // char rr = "0".charCodeAt(0); + char rr = '0'; + for (int vv = 0; vv <= 9; ++vv) s_BI_RC[rr++] = vv; + // rr = 'a".charCodeAt(0); + rr = 'a'; + for (int vv = 10; vv < 36; ++vv) s_BI_RC[rr++] = vv; + // rr = "A".charCodeAt(0); + rr = 'A'; + for (int vv = 10; vv < 36; ++vv) s_BI_RC[rr++] = vv; + } + + private static char int2char(int n) { return BI_RM[(int)n]; } + private static int intAt(String s, int i) + { + // int c = (int)BI_RC[s[(int)i]]; + // return (c==null)?-1:c; + if (i > s_BI_RC.Length) return -1; + else return (int)s_BI_RC[s[(int)i]]; + } + + // (protected) copy this to r + private void copyTo(BigInteger r) + { + var this_array = _array; + var r_array = r._array; + + for (var i = _t - 1; i >= 0; --i) r_array[i] = this_array[i]; + r._t = _t; + r._s = _s; + } + + // (protected) set from integer value x, -DV <= x < DV + private void fromInt(int x) + { + var this_array = _array; + _t = 1; + _s = (x < 0) ? -1 : 0; + if (this_array.Count == 0) + { + if (x > 0) + this_array.Add(x); + else if (x < -1) + this_array.Add(x + s_BI_DV); + else + _t = 0; + } + else + { + if (x > 0) this_array[0] = (int)x; + else if (x < -1) this_array[0] = (int)(x + s_BI_DV); + else _t = 0; + } + } + + // return bigint initialized to value + private static BigInteger nbv(int i) { var r = nbi(); r.fromInt(i); return r; } + + // (protected) set from string and radix + private void fromString(String s, int b) + { + var this_array = _array; + int k; + if (b == 16) k = 4; + else if (b == 8) k = 3; + else if (b == 256) k = 8; // byte array + else if (b == 2) k = 1; + else if (b == 32) k = 5; + else if (b == 4) k = 2; + else { this.fromRadix(s, b); return; } + _t = 0; + _s = 0; + int i = s.Length; bool mi = false; var sh = 0; + while (--i >= 0) + { + int x = (k == 8) ? (s[i] & 0xff) : intAt(s, (int)i); + if (x < 0) + { + if (s[i] == '-') mi = true; + continue; + } + mi = false; + if (sh == 0) + this_array[_t++] = (int)x; + else if (sh + k > s_BI_DB) + { + this_array[_t - 1] |= ((int)x & ((((int)1) << (s_BI_DB - sh)) - 1)) << sh; + this_array[_t++] = ((int)x >> (s_BI_DB - sh)); + } + else + this_array[_t - 1] |= ((int)x) << sh; + sh += (int)k; + if (sh >= s_BI_DB) sh -= s_BI_DB; + } + if (k == 8 && (s[0] & 0x80) != 0) + { + _s = -1; + if (sh > 0) this_array[_t - 1] |= ((((int)1) << (s_BI_DB - sh)) - 1) << sh; + } + this.clamp(); + if (mi) BigInteger.ZERO.subTo(this, this); + } + + private void fromByteArray(byte[] ba) + { + var this_array = _array; + _t = 0; + _s = 0; + int i = ba.Length; bool mi = false; var sh = 0; + while (--i >= 0) + { + int x = ba[i] & 0xff; + mi = false; + if (sh == 0) + this_array[_t++] = (int)x; + else if (sh + 8 > s_BI_DB) + { + this_array[_t - 1] |= ((int)x & ((((int)1) << (s_BI_DB - sh)) - 1)) << sh; + this_array[_t++] = ((int)x >> (s_BI_DB - sh)); + } + else + this_array[_t - 1] |= ((int)x) << sh; + sh += 8; + if (sh >= s_BI_DB) sh -= s_BI_DB; + } + if ((ba[0] & 0x80) != 0) + { + _s = -1; + if (sh > 0) this_array[_t - 1] |= ((((int)1) << (s_BI_DB - sh)) - 1) << sh; + } + this.clamp(); + if (mi) BigInteger.ZERO.subTo(this, this); + } + + // (protected) clamp off excess high words + private void clamp() + { + var this_array = _array; + var c = _s & s_BI_DM; + while (_t > 0 && this_array[_t - 1] == c) --_t; + } + + // (public) return string representation in given radix + public String toString(int b) + { + var this_array = _array; + if (_s < 0) return "-" + this.negate().toString(b); + int k; + if (b == 16) k = 4; + else if (b == 8) k = 3; + else if (b == 2) k = 1; + else if (b == 32) k = 5; + else if (b == 4) k = 2; + else return this.toRadix(b); + int km = ((int)1 << k) - 1; + int d; bool m = false; var r = ""; int i = (int)_t; + int p = (s_BI_DB - (i * s_BI_DB) % k); + if (i-- > 0) + { + if (p < s_BI_DB && (d = this_array[i] >> p) > 0) { m = true; r = new String(int2char(d), 1); } + while (i >= 0) + { + if (p < k) + { + d = (this_array[i] & ((((int)1) << p) - 1)) << (k - p); + d |= this_array[--i] >> (p += (int)(s_BI_DB - k)); + } + else + { + d = (this_array[i] >> (p -= k)) & km; + if (p <= 0) { p += (int)s_BI_DB; --i; } + } + if (d > 0) m = true; + if (m) r += int2char(d); + } + } + return m ? r : "0"; + } + + // (public) -this + public BigInteger negate() { var r = nbi(); BigInteger.ZERO.subTo(this, r); return r; } + + // (public) |this| + public BigInteger abs() { return (_s < 0) ? this.negate() : this; } + + // (public) return + if this > a, - if this < a, 0 if equal + public int compareTo(BigInteger a) + { + var this_array = _array; + var a_array = a._array; + + var r = _s - a._s; + if (r != 0) return r; + int i = (int)_t; + r = i - (int)a._t; + if (r != 0) return r; + while (--i >= 0) if ((r = (int)(this_array[i] - a_array[i])) != 0) return r; + return 0; + } + + // returns bit length of the integer x + public int nbits(int x) + { + int r = 1; + int t; + if ((t = x >> 16) != 0) { x = t; r += 16; } + if ((t = x >> 8) != 0) { x = t; r += 8; } + if ((t = x >> 4) != 0) { x = t; r += 4; } + if ((t = x >> 2) != 0) { x = t; r += 2; } + if ((t = x >> 1) != 0) { x = t; r += 1; } + return r; + } + + // (public) return the number of bits in "this" + public int bitLength() + { + var this_array = _array; + if (_t <= 0) return 0; + return ((int)s_BI_DB) * (_t - 1) + nbits(this_array[_t - 1] ^ (int)(_s & s_BI_DM)); + } + + // (protected) r = this << n*DB + private void dLShiftTo(int n, BigInteger r) + { + var this_array = _array; + var r_array = r._array; + for (int i = (int)_t - 1; i >= 0; --i) r_array[i + n] = this_array[i]; + for (int i = (int)n - 1; i >= 0; --i) r_array[i] = 0; + r._t = _t + (int)n; + r._s = _s; + } + + // (protected) r = this >> n*DB + private void dRShiftTo(int n, BigInteger r) + { + var this_array = _array; + var r_array = r._array; + for (var i = n; i < _t; ++i) r_array[i - n] = this_array[i]; + r._t = (int)Math.Max(_t - n, 0); + r._s = _s; + } + + // (protected) r = this << n + private void lShiftTo(int n, BigInteger r) + { + var this_array = _array; + var r_array = r._array; + int bs = (int)(n % s_BI_DB); + int cbs = (int)(s_BI_DB - bs); + var bm = ((int)1 << cbs) - 1; + int ds = n / s_BI_DB; int c = ((int)_s << bs) & s_BI_DM; + for (int i = (int)_t - 1; i >= 0; --i) + { + r_array[i + ds + 1] = (this_array[i] >> cbs) | c; + c = (this_array[i] & bm) << bs; +#if TRACING + Console.WriteLine(" i = {0}, this_array[i] = {3}, r_array[i + ds + 1] = {1}; c = {2}.", i, r_array[i + ds + 1], c, this_array[i]); +#endif + } + for (int i = (int)ds - 1; i >= 0; --i) r_array[i] = 0; + r_array[ds] = c; + r._t = _t + (int)ds + 1; + r._s = _s; + r.clamp(); + } + + // (protected) r = this >> n + private void rShiftTo(int n, BigInteger r) + { + var this_array = _array; + var r_array = r._array; + r._s = _s; + var ds = n / s_BI_DB; + if (ds >= _t) { r._t = 0; return; } + int bs = (int)(n % s_BI_DB); + int cbs = (int)(s_BI_DB - bs); + int bm = ((int)1 << bs) - 1; + r_array[0] = this_array[ds] >> bs; + for (int i = ds + 1; i < _t; ++i) + { + r_array[i - ds - 1] |= (this_array[i] & bm) << cbs; + r_array[i - ds] = this_array[i] >> bs; + } + if (bs > 0) r_array[(int)_t - ds - 1] |= ((int)_s & bm) << cbs; + r._t = _t - (int)ds; + r.clamp(); + } + + // (protected) r = this - a + private void subTo(BigInteger a, BigInteger r) + { + var this_array = _array; + var r_array = r._array; + var a_array = a._array; + int i = 0; int c = 0; var m = Math.Min(a._t, _t); + while (i < m) + { + c += (int)this_array[i] - (int)a_array[i]; + r_array[i++] = (int)c & s_BI_DM; + c >>= (int)s_BI_DB; + } + if (a._t < _t) + { + c -= a._s; + while (i < _t) + { + c += (int)this_array[i]; + r_array[i++] = (int)c & s_BI_DM; + c >>= (int)s_BI_DB; + } + c += _s; + } + else + { + c += _s; + while (i < a._t) + { + c -= (int)a_array[i]; + r_array[i++] = (int)c & s_BI_DM; + c >>= (int)s_BI_DB; + } + c -= a._s; + } + r._s = (c < 0) ? -1 : 0; + if (c < -1) r_array[i++] = (int)((int)s_BI_DV + c); + else if (c > 0) r_array[i++] = (int)c; + r._t = i; + r.clamp(); + } + + // (protected) r = this * a, r != this,a (HAC 14.12) + // "this" should be the larger one if appropriate. + private void multiplyTo(BigInteger a, BigInteger r) + { + var this_array = _array; + var r_array = r._array; + var x = this.abs(); var y = a.abs(); + var y_array = y._array; + + int i = (int)x._t; + r._t = (int)i + y._t; + while (--i >= 0) r_array[i] = 0; + for (i = 0; i < y._t; ++i) r_array[i + (int)x._t] = s_am(x, 0, y_array[i], r, (int)i, 0, (int)x._t); + r._s = 0; + r.clamp(); + if (_s != a._s) BigInteger.ZERO.subTo(r, r); + } + + // (protected) r = this^2, r != this (HAC 14.16) + private void squareTo(BigInteger r) + { + var x = this.abs(); + var x_array = x._array; + var r_array = r._array; + + int i = (int)(2 * x._t); + r._t = (int)i; + while (--i >= 0) r_array[i] = 0; + for (i = 0; i < x._t - 1; ++i) + { + var c = s_am(x, (int)i, x_array[i], r, (int)(2 * i), 0, 1); + if ((r_array[(int)i + x._t] += s_am(x, (int)(i + 1), 2 * x_array[i], r, (int)(2 * i + 1), c, (int)x._t - i - 1)) >= s_BI_DV) + { + r_array[(int)i + x._t] -= s_BI_DV; + r_array[(int)i + x._t + 1] = 1; + } + } + if (r._t > 0) r_array[r._t - 1] += s_am(x, (int)i, x_array[i], r, (int)(2 * i), 0, 1); + r._s = 0; + r.clamp(); + } + + // (protected) divide this by m, quotient and remainder to q, r (HAC 14.20) + // r != q, this != m. q or r may be null. + private void divRemTo(BigInteger m, BigInteger q, BigInteger r) + { +#if TRACING + this.PrintArray("this"); +#endif + var pm = m.abs(); + if (pm._t <= 0) return; + var pt = this.abs(); +#if TRACING + pt.PrintArray("pt"); +#endif + if (pt._t < pm._t) + { + if (q != null) q.fromInt(0); + if (r != null) this.copyTo(r); + return; + } + if (r == null) r = nbi(); + var y = nbi(); var ts = _s; var ms = m._s; + var pm_array = pm._array; + int nsh = s_BI_DB - (int)nbits(pm_array[pm._t - 1]); // normalize modulus + if (nsh > 0) { pm.lShiftTo(nsh, y); pt.lShiftTo(nsh, r); } + else { pm.copyTo(y); pt.copyTo(r); } + int ys = y._t; + + var y_array = y._array; + double y0 = (double)y_array[ys - 1]; + if (y0 == 0) return; + double yt = (y0 * (double)((int)1 << s_BI_F1) + ((ys > 1) ? y_array[ys - 2] >> s_BI_F2 : 0)); + double d1 = ((double)s_BI_FV) / yt; + double d2 = ((double)(1 << s_BI_F1)) / yt; + var e = 1 << s_BI_F2; + int i = (int)r._t; int j = i - (int)ys; var t = (q == null) ? nbi() : q; + y.dLShiftTo(j, t); + +#if TRACING + Console.WriteLine("y is"); + for (int kk = 0; kk < y.array.Count; kk++) + Console.WriteLine("{0}", y.array[kk]); +#endif + + var r_array = r._array; + if (r.compareTo(t) >= 0) + { + r_array[r._t++] = 1; + r.subTo(t, r); + } + BigInteger.ONE.dLShiftTo((int)ys, t); + t.subTo(y, y); // "negative" y so we can replace sub with am later + while (y._t < ys) y_array[y._t++] = 0; + while (--j >= 0) + { + // Estimate quotient digit + int qd = (r_array[--i] == y0) ? s_BI_DM : + (int)Math.Floor((double)r_array[i] * d1 + ((double)(r_array[i - 1] + e)) * d2); + if ((r_array[i] += s_am(y, 0, qd, r, (int)j, 0, (int)ys)) < qd) + { // Try it out + y.dLShiftTo(j, t); + r.subTo(t, r); + while (r_array[i] < --qd) r.subTo(t, r); + } + } + if (q != null) + { + r.dRShiftTo((int)ys, q); + if (ts != ms) BigInteger.ZERO.subTo(q, q); + } + r._t = (int)ys; + r.clamp(); + if (nsh > 0) r.rShiftTo(nsh, r); // Denormalize remainder + if (ts < 0) BigInteger.ZERO.subTo(r, r); + } + + // (public) this mod a + public BigInteger mod(BigInteger a) + { + var r = nbi(); + this.abs().divRemTo(a, null, r); + if (_s < 0 && r.compareTo(BigInteger.ZERO) > 0) a.subTo(r, r); + return r; + } + + // Modular reduction using "classic" algorithm + public class ClassicReducer : Reducer + { + private BigInteger _m; + + public ClassicReducer(BigInteger m) { _m = m; } + + public void reduce(BigInteger x) { x.divRemTo(_m, null, x); } + + public override BigInteger convert(BigInteger x) + { + if (x._s < 0 || x.compareTo(_m) >= 0) return x.mod(_m); + else return x; + } + + public override BigInteger revert(BigInteger x) { return x; } + public override void mulTo(BigInteger x, BigInteger y, BigInteger r) { x.multiplyTo(y, r); this.reduce(r); } + public override void sqrTo(BigInteger x, BigInteger r) { x.squareTo(r); this.reduce(r); } + } + + // (protected) return "-1/this % 2^DB"; useful for Mont. reduction + // justification: + // xy == 1 (mod m) + // xy = 1+km + // xy(2-xy) = (1+km)(1-km) + // x[y(2-xy)] = 1-k^2m^2 + // x[y(2-xy)] == 1 (mod m^2) + // if y is 1/x mod m, then y(2-xy) is 1/x mod m^2 + // should reduce x and y(2-xy) by m^2 at each step to keep size bounded. + // JS multiply "overflows" differently from C/C++, so care is needed here. + private int invDigit() + { + var this_array = _array; + if (_t < 1) return 0; + int x = (int)this_array[0]; + if ((x & 1) == 0) return 0; + int y = x & 3; // y == 1/x mod 2^2 + y = (y * (2 - (x & 0xf) * y)) & 0xf; // y == 1/x mod 2^4 + y = (y * (2 - (x & 0xff) * y)) & 0xff; // y == 1/x mod 2^8 + y = (y * (2 - (((x & 0xffff) * y) & 0xffff))) & 0xffff; // y == 1/x mod 2^16 + // last step - calculate inverse mod DV directly; + // assumes 16 < DB <= 32 and assumes ability to handle 48-bit ints + y = (y * (2 - x * y % (int)s_BI_DV)) % (int)s_BI_DV; // y == 1/x mod 2^dbits + // we really want the negative inverse, and -DV < y < DV + return (y > 0) ? (int)s_BI_DV - y : -y; + } + + public abstract class Reducer + { + abstract public BigInteger convert(BigInteger x); + abstract public BigInteger revert(BigInteger x); + // DELETEME + // abstract public void reduce(BigInteger x); + abstract public void sqrTo(BigInteger x, BigInteger r); + abstract public void mulTo(BigInteger x, BigInteger y, BigInteger r); + }; + + private class MontgomeryReducer : Reducer + { + private BigInteger _m; + private int _mp; + private int _mpl; + private int _mph; + private int _um; + private int _mt2; + + public MontgomeryReducer(BigInteger m) + { + _m = m; + _mp = m.invDigit(); + _mpl = _mp & 0x7fff; + _mph = _mp >> 15; + _um = (1 << (s_BI_DB - 15)) - 1; + _mt2 = 2 * m._t; + } + + // xR mod m + public override BigInteger convert(BigInteger x) + { + var r = nbi(); + x.abs().dLShiftTo(_m._t, r); + r.divRemTo(_m, null, r); + if (x._s < 0 && r.compareTo(BigInteger.ZERO) > 0) _m.subTo(r, r); + return r; + } + + public override BigInteger revert(BigInteger x) + { + var r = nbi(); + x.copyTo(r); + this.reduce(r); + return r; + } + + // x = x/R mod m (HAC 14.32) + public void reduce(BigInteger x) + { + var x_array = x._array; + while (x._t <= _mt2) // pad x so am has enough room later + x_array[x._t++] = 0; + for (var i = 0; i < _m._t; ++i) + { + // faster way of calculating u0 = x[i]*mp mod DV + var j = x_array[i] & 0x7fff; + var u0 = (j * _mpl + (((j * _mph + (x_array[i] >> 15) * _mpl) & _um) << 15)) & s_BI_DM; + // use am to combine the multiply-shift-add into one call + j = i + _m._t; + x_array[j] += s_am(_m, 0, u0, x, i, 0, _m._t); + // propagate carry + while (x_array[j] >= s_BI_DV) { x_array[j] -= s_BI_DV; x_array[++j]++; } + } + x.clamp(); + x.dRShiftTo(_m._t, x); + if (x.compareTo(_m) >= 0) x.subTo(_m, x); + } + + // r = "x^2/R mod m"; x != r + public override void sqrTo(BigInteger x, BigInteger r) { x.squareTo(r); this.reduce(r); } + + // r = "xy/R mod m"; x,y != r + public override void mulTo(BigInteger x, BigInteger y, BigInteger r) + { + x.multiplyTo(y, r); this.reduce(r); + } + } + + + // (protected) true iff this is even + private bool isEven() + { + var this_array = _array; + return ((_t > 0) ? (int)(this_array[0] & 1) : _s) == 0; + } + + // (protected) this^e, e < 2^32, doing sqr and mul with "z" (HAC 14.79) + private BigInteger exp(uint e, Reducer z) + { + if (e > 0xffffffff || e < 1) return BigInteger.ONE; + var r = nbi(); var r2 = nbi(); var g = z.convert(this); int i = (int)nbits((int)e) - 1; + g.copyTo(r); + while (--i >= 0) + { + z.sqrTo(r, r2); + if ((e & (1 << i)) > 0) z.mulTo(r2, g, r); + else { var t = r; r = r2; r2 = t; } + } + return z.revert(r); + } + + // (public) this^e % m, 0 <= e < 2^32 + public BigInteger modPowInt(uint e, BigInteger m) + { + Reducer z; + if (e < 256 || m.isEven()) z = new ClassicReducer(m); else z = new MontgomeryReducer(m); + return this.exp(e, z); + } + + // "constants" + public static BigInteger ZERO = nbv(0); + public static BigInteger ONE = nbv(1); + + // Copyright (c) 2005 Tom Wu + // All Rights Reserved. + // See "LICENSE" for details. + + // Extended JavaScript BN functions, required for RSA private ops. + + // (public) + public BigInteger clone() { var r = nbi(); this.copyTo(r); return r; } + + // (public) return value as integer + public int intValue() + { + var this_array = _array; + if (_s < 0) + { + if (_t == 1) return (int)this_array[0] - (int)s_BI_DV; + else if (_t == 0) return -1; + } + else if (_t == 1) return (int)this_array[0]; + else if (_t == 0) return 0; + // assumes 16 < DB < 32 + // return ((this_array[1]&((1<<(32-BI_DB))-1))<<BI_DB)|this_array[0]; + var x = (this_array[1] & ((1 << (32 - s_BI_DB)) - 1)); + return (int)((int)(x << s_BI_DB) | this_array[0]); + } + + // (public) return value as byte + public byte byteValue() + { + var this_array = _array; + return (_t == 0) ? (byte)_s : (byte)((this_array[0] << 24) >> 24); + } + + // (public) return value as short (assumes DB>=16) + public ushort shortValue() + { + var this_array = _array; + return (_t == 0) ? (ushort)_s : (ushort)((this_array[0] << 16) >> 16); + } + + private static double s_LN2 = Math.Log(2.0); + + // (protected) return x s.t. r^x < DV + private int chunkSize(int r) { return (int)Math.Floor(s_LN2 * (double)s_BI_DB / Math.Log(r)); } + + // (public) 0 if this == 0, 1 if this > 0 + public int signum() + { + var this_array = _array; + if (_s < 0) return -1; + else if (_t <= 0 || (_t == 1 && this_array[0] <= 0)) return 0; + else return 1; + } + + private static String s_sdigits = "0123456789abcdefghijklmnopqrstuvwxyz"; + + private static String IntToString(int i, int radix) + { + if (radix == 10) + { + return i.ToString(); + } + else if (radix == 16) + { + return i.ToString("X"); + } + else + { + bool neg = false; + if (i < 0) + { + neg = true; i = -i; + } + String res = ""; + while (i != 0) + { + int digit = i % radix; + res = s_sdigits.Substring(digit, 1) + res; + i = i / radix; + } + if (neg) res = "-" + res; + return res; + } + } + + // (protected) convert to radix string + public String toRadix(int b) + { + // if (b == null) b = 10; + if (this.signum() == 0 || b < 2 || b > 36) return "0"; + var cs = this.chunkSize(b); + var a = (int)Math.Pow((double)b, (double)cs); + Console.WriteLine("a = {0}.", a); + var d = nbv(a); var y = nbi(); var z = nbi(); var r = ""; + Console.WriteLine("d.intValue = {0}.", d.intValue()); + this.divRemTo(d, y, z); + Console.WriteLine("y.signum = {0}", y.signum()); + Console.WriteLine("z.intValue = " + z.intValue()); + while (y.signum() > 0) + { + r = IntToString(a + z.intValue(), (int)b).Substring(1) + r; + y.divRemTo(d, y, z); + Console.WriteLine("y.signum = {0}", y.signum()); + Console.WriteLine("z.intValue = " + z.intValue()); + } + return IntToString(z.intValue(), (int)b) + r; + } + + private static int IntPow(int n, int p) + { + int res = 1; + for (int k = 1; k < p; k++) + { + res *= n; + } + return res; + } + + // (protected) convert from radix string + private void fromRadix(String s, int b) + { + this.fromInt(0); + var cs = this.chunkSize(b); + var d = IntPow(b, cs); bool mi = false; int j = 0; int w = 0; + for (int i = 0; i < s.Length; ++i) + { + int x = intAt(s, i); + if (x < 0) + { + if (s[(int)i] == '-' && this.signum() == 0) mi = true; + continue; + } + w = b * w + (int)x; + if (++j >= cs) + { + this.dMultiply(d); + this.dAddOffset(w, 0); + j = 0; + w = 0; + } + } + if (j > 0) + { + this.dMultiply(IntPow(b, j)); + this.dAddOffset(w, 0); + } + if (mi) BigInteger.ZERO.subTo(this, this); + } + + // (protected) alternate constructor + private void fromNumber(int a, int b, SecureRandom c) + { + if (a < 2) this.fromInt(1); + else + { + this.fromNumber(a, c); + if (!this.testBit(a - 1)) // force MSB set + this.bitwiseTo(BigInteger.ONE.shiftLeft((int)a - 1), op_or, this); + if (this.isEven()) this.dAddOffset(1, 0); // force odd + while (!this.isProbablePrime(b)) + { + this.dAddOffset(2, 0); + if (this.bitLength() > a) this.subTo(BigInteger.ONE.shiftLeft((int)a - 1), this); + } + } + } + + private void fromNumber(int a, SecureRandom b) + { + // new BigInteger(int,RNG) + byte[] x = new byte[(a >> 3) + 1]; + int t = (int)a & 7; + b.nextBytes(x); + if (t > 0) + x[0] &= (byte)((1 << (int)t) - 1); + else + x[0] = 0; + this.fromByteArray(x); + } + + // (public) convert to bigendian byte array + public byte[] toByteArray() + { + var this_array = _array; + int i = (int)_t; var r = new ListX<byte>(); + r[0] = (byte)_s; + int p = (int)s_BI_DB - (i * (int)s_BI_DB) % 8; + int d; int k = 0; + if (i-- > 0) + { + if (p < s_BI_DB && (d = this_array[i] >> p) != (_s & s_BI_DM) >> p) + r[k++] = (byte)(d | ((int)_s << (int)(s_BI_DB - p))); + while (i >= 0) + { + if (p < 8) + { + d = (this_array[i] & (((int)1 << p) - 1)) << (8 - p); + d |= this_array[--i] >> (p += s_BI_DB - 8); + } + else + { + d = (this_array[i] >> (p -= 8)) & 0xff; + if (p <= 0) { p += s_BI_DB; --i; } + } + if ((d & 0x80) != 0) d = (int)((int)d | -256); + if (k == 0 && (_s & 0x80) != (d & 0x80)) ++k; + if (k > 0 || d != _s) r[k++] = (byte)d; + } + } + return r.ToArray(); + } + + public bool Equals(BigInteger a) { return (this.compareTo(a) == 0); } + public BigInteger min(BigInteger a) { return (this.compareTo(a) < 0) ? this : a; } + public BigInteger max(BigInteger a) { return (this.compareTo(a) > 0) ? this : a; } + + // (protected) r = this op a (bitwise) + public delegate int BinOpInt(int x1, int x2); + + private void bitwiseTo(BigInteger a, BinOpInt op, BigInteger r) + { + var this_array = _array; + var a_array = a._array; + var r_array = r._array; + var m = Math.Min(a._t, _t); + for (int i = 0; i < m; ++i) r_array[i] = op(this_array[i], a_array[i]); + int f; + if (a._t < _t) + { + f = (int)a._s & s_BI_DM; + for (int i = m; i < _t; ++i) r_array[i] = op(this_array[i], f); + r._t = _t; + } + else + { + f = (int)_s & s_BI_DM; + for (int i = m; i < a._t; ++i) r_array[i] = op(f, a_array[i]); + r._t = a._t; + } + r._s = (int)op((int)_s, (int)a._s); + r.clamp(); + } + + // (public) this & a + private static int op_and(int x, int y) { return x & y; } + public BigInteger and(BigInteger a) { var r = nbi(); this.bitwiseTo(a, op_and, r); return r; } + + // (public) this | a + private static int op_or(int x, int y) { return x | y; } + public BigInteger or(BigInteger a) { var r = nbi(); this.bitwiseTo(a, op_or, r); return r; } + + // (public) this ^ a + private static int op_xor(int x, int y) { return x ^ y; } + public BigInteger xor(BigInteger a) { var r = nbi(); this.bitwiseTo(a, op_xor, r); return r; } + + // (public) this & ~a + private static int op_andnot(int x, int y) { return x & ~y; } + public BigInteger andNot(BigInteger a) { var r = nbi(); this.bitwiseTo(a, op_andnot, r); return r; } + + // (public) ~this + public BigInteger not() + { + var this_array = _array; + var r = nbi(); + var r_array = r._array; + + for (var i = 0; i < _t; ++i) r_array[i] = s_BI_DM & ~this_array[i]; + r._t = _t; + r._s = ~_s; + return r; + } + + // (public) this << n + public BigInteger shiftLeft(int n) + { + var r = nbi(); + if (n < 0) this.rShiftTo(-n, r); else this.lShiftTo(n, r); + return r; + } + + // (public) this >> n + public BigInteger shiftRight(int n) + { + var r = nbi(); + if (n < 0) this.lShiftTo(-n, r); else this.rShiftTo(n, r); + return r; + } + + // return index of lowest 1-bit in x, x < 2^31 (-1 for no set bits) + public static int lbit(int x) + { + if (x == 0) return -1; + int r = 0; + if ((x & 0xffff) == 0) { x >>= 16; r += 16; } + if ((x & 0xff) == 0) { x >>= 8; r += 8; } + if ((x & 0xf) == 0) { x >>= 4; r += 4; } + if ((x & 3) == 0) { x >>= 2; r += 2; } + if ((x & 1) == 0) ++r; + return r; + } + + // (public) returns index of lowest 1-bit (or -1 if none) + public int getLowestSetBit() + { + var this_array = _array; + for (var i = 0; i < _t; ++i) + if (this_array[i] != 0) return i * s_BI_DB + lbit(this_array[i]); + if (_s < 0) return (int)_t * s_BI_DB; + return -1; + } + + // return number of 1 bits in x + private static int cbit(int x) + { + int r = 0; + while (x != 0) { x &= x - 1; ++r; } + return r; + } + + // (public) return number of set bits + public int bitCount() + { + int r = 0; + int x = (int)_s & s_BI_DM; + for (int i = 0; i < _t; ++i) r += cbit(_array[i] ^ x); + return r; + } + + // (public) true iff nth bit is set + public bool testBit(int n) + { + var this_array = _array; + int j = n / (int)s_BI_DB; + if (j >= _t) return (_s != 0); + return ((this_array[j] & ((int)1 << (int)(n % s_BI_DB))) != 0); + } + + // (protected) this op (1<<n) + private BigInteger changeBit(int n, BinOpInt op) + { + var r = ONE.shiftLeft((int)n); + this.bitwiseTo(r, op, r); + return r; + } + + // (public) this | (1<<n) + public BigInteger setBit(int n) { return this.changeBit(n, op_or); } + + // (public) this & ~(1<<n) + public BigInteger clearBit(int n) { return this.changeBit(n, op_andnot); } + + // (public) this ^ (1<<n) + public BigInteger flipBit(int n) { return this.changeBit(n, op_xor); } + + // (protected) r = this + a + private void addTo(BigInteger a, BigInteger r) + { + var this_array = _array; + var a_array = a._array; + var r_array = r._array; + int i = 0; int c = 0; int m = Math.Min(a._t, _t); + while (i < m) + { + c += this_array[i] + a_array[i]; + r_array[i++] = c & s_BI_DM; + c >>= s_BI_DB; + } + if (a._t < _t) + { + c += (int)a._s; + while (i < _t) + { + c += this_array[i]; + r_array[i++] = c & s_BI_DM; + c >>= s_BI_DB; + } + c += (int)_s; + } + else + { + c += (int)_s; + while (i < a._t) + { + c += a_array[i]; + r_array[i++] = c & s_BI_DM; + c >>= s_BI_DB; + } + c += (int)a._s; + } + r._s = (c < 0) ? -1 : 0; + if (c > 0) r_array[i++] = c; + else if (c < -1) r_array[i++] = s_BI_DV + c; + r._t = i; + r.clamp(); + } + + // (public) this + a + public BigInteger add(BigInteger a) { var r = nbi(); this.addTo(a, r); return r; } + + // (public) this - a + public BigInteger subtract(BigInteger a) { var r = nbi(); this.subTo(a, r); return r; } + + // (public) this * a + public BigInteger multiply(BigInteger a) { var r = nbi(); this.multiplyTo(a, r); return r; } + + // (public) this / a + public BigInteger divide(BigInteger a) { var r = nbi(); this.divRemTo(a, r, null); return r; } + + // (public) this % a + public BigInteger remainder(BigInteger a) { var r = nbi(); this.divRemTo(a, null, r); return r; } + + public struct BigIntPair + { + public BigInteger p1; + public BigInteger p2; + public BigIntPair(BigInteger p1, BigInteger p2) { this.p1 = p1; this.p2 = p2; } + } + // (public) [this/a,this%a] + public BigIntPair divideAndRemainder(BigInteger a) + { + var q = nbi(); var r = nbi(); + this.divRemTo(a, q, r); + return new BigIntPair(q, r); + } + + // (protected) this *= n, this >= 0, 1 < n < DV + private void dMultiply(int n) + { + var this_array = _array; + this_array[_t] = s_am(this, 0, n - 1, this, 0, 0, _t); + ++_t; + this.clamp(); + } + + // (protected) this += n << w words, this >= 0 + private void dAddOffset(int n, int w) + { + var this_array = _array; + while (_t <= w) this_array[_t++] = 0; + this_array[w] += n; + while (this_array[w] >= s_BI_DV) + { + this_array[w] -= s_BI_DV; + if (++w >= _t) this_array[_t++] = 0; + ++this_array[w]; + } + } + + private class NullReducer : Reducer + { + public NullReducer() { } + + + public override BigInteger convert(BigInteger x) { return x; } + public override BigInteger revert(BigInteger x) { return x; } + public override void mulTo(BigInteger x, BigInteger y, BigInteger r) { x.multiplyTo(y, r); } + public override void sqrTo(BigInteger x, BigInteger r) { x.squareTo(r); } + } + + // (public) this^e + // public BigInteger pow(BigInteger e) { return this.exp(e,new NullReducer()); } + + // (protected) r = lower n words of "this * a", a.t <= n + // "this" should be the larger one if appropriate. + private void multiplyLowerTo(BigInteger a, int n, BigInteger r) + { + var r_array = r._array; + var a_array = a._array; + var i = Math.Min(_t + a._t, n); + r._s = 0; // assumes a,this >= 0 + r._t = i; + while (i > 0) r_array[--i] = 0; + for (int j = r._t - _t; i < j; ++i) r_array[i + _t] = s_am(this, 0, a_array[i], r, i, 0, _t); + for (int j = Math.Min(a._t, n); i < j; ++i) s_am(this, 0, a_array[i], r, i, 0, n - i); + r.clamp(); + } + + // (protected) r = "this * a" without lower n words, n > 0 + // "this" should be the larger one if appropriate. + public void multiplyUpperTo(BigInteger a, int n, BigInteger r) + { + var r_array = r._array; + var a_array = a._array; + --n; + int i = r._t = _t + a._t - n; + r._s = 0; // assumes a,this >= 0 + while (--i >= 0) r_array[i] = 0; + for (i = Math.Max(n - _t, 0); i < a._t; ++i) + r_array[_t + i - n] = s_am(this, n - i, a_array[i], r, 0, 0, _t + i - n); + r.clamp(); + r.dRShiftTo(1, r); + } + + // Barrett modular reduction + public class BarrettReducer : Reducer + { + private BigInteger _r2; + private BigInteger _q3; + private BigInteger _mu; + private BigInteger _m; + + public BarrettReducer(BigInteger m) + { + // setup Barrett + _r2 = nbi(); + _q3 = nbi(); + BigInteger.ONE.dLShiftTo(2 * m._t, _r2); + _mu = _r2.divide(m); + _m = m; + } + + public override BigInteger convert(BigInteger x) + { + if (x._s < 0 || x._t > 2 * _m._t) return x.mod(_m); + else if (x.compareTo(_m) < 0) return x; + else { var r = nbi(); x.copyTo(r); this.reduce(r); return r; } + } + + public override BigInteger revert(BigInteger x) { return x; } + + // x = x mod m (HAC 14.42) + public void reduce(BigInteger x) + { + x.dRShiftTo(_m._t - 1, _r2); + if (x._t > _m._t + 1) { x._t = _m._t + 1; x.clamp(); } + _mu.multiplyUpperTo(_r2, _m._t + 1, _q3); + _m.multiplyLowerTo(_q3, _m._t + 1, _r2); + while (x.compareTo(_r2) < 0) x.dAddOffset(1, _m._t + 1); + x.subTo(_r2, x); + while (x.compareTo(_m) >= 0) x.subTo(_m, x); + } + + // r = x^2 mod m; x != r + public override void sqrTo(BigInteger x, BigInteger r) { x.squareTo(r); this.reduce(r); } + + // r = x*y mod m; x,y != r + public override void mulTo(BigInteger x, BigInteger y, BigInteger r) { x.multiplyTo(y, r); this.reduce(r); } + } + + // (public) this^e % m (HAC 14.85) + public BigInteger modPow(BigInteger e, BigInteger m) + { + var e_array = e._array; + var i = e.bitLength(); int k; BigInteger r = nbv(1); Reducer z; + if (i <= 0) return r; + else if (i < 18) k = 1; + else if (i < 48) k = 3; + else if (i < 144) k = 4; + else if (i < 768) k = 5; + else k = 6; + if (i < 8) + z = new ClassicReducer(m); + else if (m.isEven()) + z = new BarrettReducer(m); + else + z = new MontgomeryReducer(m); + + // precomputation + var g = new ListX<BigInteger>(); + int n = 3; + int k1 = k - 1; + int km = (1 << k) - 1; + g[1] = z.convert(this); + if (k > 1) + { + var g2 = nbi(); + z.sqrTo(g[1], g2); + while (n <= km) + { + g[n] = nbi(); + z.mulTo(g2, g[n - 2], g[n]); + n += 2; + } + } + + int j = e._t - 1; int w; bool is1 = true; BigInteger r2 = nbi(); BigInteger t; + i = nbits(e_array[j]) - 1; + while (j >= 0) + { + if (i >= k1) w = (e_array[j] >> (i - k1)) & km; + else + { + w = (e_array[j] & ((1 << (i + 1)) - 1)) << (k1 - i); + if (j > 0) w |= e_array[j - 1] >> (s_BI_DB + i - k1); + } + + n = k; + while ((w & 1) == 0) { w >>= 1; --n; } + if ((i -= n) < 0) { i += s_BI_DB; --j; } + if (is1) + { // ret == 1, don't bother squaring or multiplying it + g[w].copyTo(r); + is1 = false; + } + else + { + while (n > 1) { z.sqrTo(r, r2); z.sqrTo(r2, r); n -= 2; } + if (n > 0) z.sqrTo(r, r2); else { t = r; r = r2; r2 = t; } + z.mulTo(r2, g[w], r); + } + + while (j >= 0 && (e_array[j] & (1 << i)) == 0) + { + z.sqrTo(r, r2); t = r; r = r2; r2 = t; + if (--i < 0) { i = s_BI_DB - 1; --j; } + } + } + return z.revert(r); + } + + // (public) gcd(this,a) (HAC 14.54) + public BigInteger gcd(BigInteger a) + { + var x = (_s < 0) ? this.negate() : this.clone(); + var y = (a._s < 0) ? a.negate() : a.clone(); + if (x.compareTo(y) < 0) { var t = x; x = y; y = t; } + var i = x.getLowestSetBit(); var g = y.getLowestSetBit(); + if (g < 0) return x; + if (i < g) g = i; + if (g > 0) + { + x.rShiftTo(g, x); + y.rShiftTo(g, y); + } + while (x.signum() > 0) + { + if ((i = x.getLowestSetBit()) > 0) x.rShiftTo(i, x); + if ((i = y.getLowestSetBit()) > 0) y.rShiftTo(i, y); + if (x.compareTo(y) >= 0) + { + x.subTo(y, x); + x.rShiftTo(1, x); + } + else + { + y.subTo(x, y); + y.rShiftTo(1, y); + } + } + if (g > 0) y.lShiftTo(g, y); + return y; + } + + // (protected) this % n, n < 2^26 + private int modInt(int n) + { + var this_array = _array; + if (n <= 0) return 0; + var d = s_BI_DV % n; int r = (_s < 0) ? n - 1 : 0; + if (_t > 0) + if (d == 0) r = this_array[0] % n; + else for (var i = _t - 1; i >= 0; --i) r = (d * r + this_array[i]) % n; + return r; + } + + // (public) 1/this % m (HAC 14.61) + public BigInteger modInverse(BigInteger m) + { + var ac = m.isEven(); + if ((this.isEven() && ac) || m.signum() == 0) return BigInteger.ZERO; + var u = m.clone(); var v = this.clone(); + var a = nbv(1); var b = nbv(0); var c = nbv(0); var d = nbv(1); + while (u.signum() != 0) + { + while (u.isEven()) + { + u.rShiftTo(1, u); + if (ac) + { + if (!a.isEven() || !b.isEven()) { a.addTo(this, a); b.subTo(m, b); } + a.rShiftTo(1, a); + } + else if (!b.isEven()) b.subTo(m, b); + b.rShiftTo(1, b); + } + while (v.isEven()) + { + v.rShiftTo(1, v); + if (ac) + { + if (!c.isEven() || !d.isEven()) { c.addTo(this, c); d.subTo(m, d); } + c.rShiftTo(1, c); + } + else if (!d.isEven()) d.subTo(m, d); + d.rShiftTo(1, d); + } + if (u.compareTo(v) >= 0) + { + u.subTo(v, u); + if (ac) a.subTo(c, a); + b.subTo(d, b); + } + else + { + v.subTo(u, v); + if (ac) c.subTo(a, c); + d.subTo(b, d); + } + } + if (v.compareTo(BigInteger.ONE) != 0) return BigInteger.ZERO; + if (d.compareTo(m) >= 0) return d.subtract(m); + if (d.signum() < 0) d.addTo(m, d); else return d; + if (d.signum() < 0) return d.add(m); else return d; + } + + private static int[] s_lowprimes = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509 }; + private static int s_lplim = (1 << 26) / s_lowprimes[s_lowprimes.Length - 1]; + + // (public) test primality with certainty >= 1-.5^t + public bool isProbablePrime(int t) + { + int i; var x = this.abs(); + var x_array = x._array; + if (x._t == 1 && x_array[0] <= s_lowprimes[s_lowprimes.Length - 1]) + { + for (i = 0; i < s_lowprimes.Length; ++i) + if (x_array[0] == s_lowprimes[i]) return true; + return false; + } + if (x.isEven()) return false; + i = 1; + while (i < s_lowprimes.Length) + { + var m = s_lowprimes[i]; var j = i + 1; + while (j < s_lowprimes.Length && m < s_lplim) m *= s_lowprimes[j++]; + m = x.modInt(m); + while (i < j) if (m % s_lowprimes[i++] == 0) return false; + } + return x.millerRabin(t); + } + + // (protected) true if probably prime (HAC 4.24, Miller-Rabin) + private bool millerRabin(int t) + { + var n1 = this.subtract(BigInteger.ONE); + var k = n1.getLowestSetBit(); + if (k <= 0) return false; + var r = n1.shiftRight(k); + t = (t + 1) >> 1; + if (t > s_lowprimes.Length) t = s_lowprimes.Length; + var a = nbi(); + for (var i = 0; i < t; ++i) + { + a.fromInt(s_lowprimes[i]); + var y = a.modPow(r, this); + if (y.compareTo(BigInteger.ONE) != 0 && y.compareTo(n1) != 0) + { + var j = 1; + while (j++ < k && y.compareTo(n1) != 0) + { + y = y.modPowInt(2, this); + if (y.compareTo(BigInteger.ONE) == 0) return false; + } + if (y.compareTo(n1) != 0) return false; + } + } + return true; + } + + public void PrintArray(String nm) + { + for (int kk = 0; kk < _array.Count; kk++) Console.WriteLine(" {0}.array[{1}] = {2}", nm, kk, _array[kk]); + } + + // BigInteger interfaces not implemented in jsbn: + + // BigInteger(int signum, byte[] magnitude) + // double doubleValue() + // float floatValue() + // int hashCode() + // long longValue() + // static BigInteger valueOf(long val) + // prng4.js - uses Arcfour as a PRNG + } + + internal abstract class RNG + { + abstract public void init(int[] key); + abstract public int next(); + } + + internal class Arcfour : RNG + { + private int _i; + private int _j; + private int[] _S; + + public Arcfour() + { + _i = 0; + _j = 0; + _S = new int[256]; + } + + // Initialize arcfour context from key, an array of ints, each from [0..255] + public override void init(int[] key) + { + for (int i = 0; i < 256; ++i) + _S[i] = i; + int j = 0; + for (int i = 0; i < 256; ++i) + { + j = (j + _S[i] + key[i % key.Length]) & 255; + int t = _S[i]; + _S[i] = _S[j]; + _S[j] = t; + } + _i = 0; + _j = 0; + } + + public override int next() + { + _i = (_i + 1) & 255; + _j = (_j + _S[_i]) & 255; + int t = _S[_i]; + _S[_i] = _S[_j]; + _S[_j] = t; + return _S[(t + _S[_i]) & 255]; + } + } + + internal class SecureRandom + { + // Pool size must be a multiple of 4 and greater than 32. + // An array of bytes the size of the pool will be passed to init() + private const int rng_psize = 256; + + // Random number generator - requires a PRNG backend, e.g. prng4.js + + // For best results, put code like + // <body onClick='rng_seed_time();' onKeyPress='rng_seed_time();'> + // in your main HTML document. + + private RNG _rng_state; + private int[] _rng_pool; + private int _rng_pptr; + + public SecureRandom() + { + _rng_pool = new int[rng_psize]; + _rng_pptr = 0; +#if USE_RANDOM_SEED + Random rnd = new Random(); +#endif + while (_rng_pptr < rng_psize) + { // extract some randomness from Math.random() +#if USE_RANDOM_SEED + int t = (int)Math.Floor(65536.0 * rnd.NextDouble()); +#else + int t = 1000; +#endif + _rng_pool[_rng_pptr++] = (int)((uint)t >> 8); + _rng_pool[_rng_pptr++] = t & 255; + } + _rng_pptr = 0; + rng_seed_time(); + } + + // Mix in a 32-bit integer into the pool + private void rng_seed_int(int x) + { + _rng_pool[_rng_pptr++] ^= x & 255; + _rng_pool[_rng_pptr++] ^= (x >> 8) & 255; + _rng_pool[_rng_pptr++] ^= (x >> 16) & 255; + _rng_pool[_rng_pptr++] ^= (x >> 24) & 255; + if (_rng_pptr >= rng_psize) _rng_pptr -= rng_psize; + } + + // Mix in the current time (w/milliseconds) into the pool + private void rng_seed_time() + { +#if USE_RANDOM_SEED + rng_seed_int((int)(new DateTime().Ticks)); +#endif + } + + + // Plug in your RNG constructor here + private RNG prng_newstate() + { + return new Arcfour(); + } + + private byte rng_get_byte() + { + if (_rng_state == null) + { + rng_seed_time(); + _rng_state = prng_newstate(); + _rng_state.init(_rng_pool); + for (_rng_pptr = 0; _rng_pptr < _rng_pool.Length; ++_rng_pptr) + _rng_pool[_rng_pptr] = 0; + _rng_pptr = 0; + //rng_pool = null; + } + // TODO: allow reseeding after first request + return (byte)_rng_state.next(); + } + + public void nextBytes(byte[] ba) + { + for (int i = 0; i < ba.Length; ++i) ba[i] = rng_get_byte(); + } + } + + internal class RSAKey + { + private BigInteger _n; + private int _e; + private BigInteger _d; + private BigInteger _p; + private BigInteger _q; + private BigInteger _dmp1; + private BigInteger _dmq1; + private BigInteger _coeff; + + // "empty" RSA key constructor + public RSAKey() + { + _n = null; + _e = 0; + _d = null; + _p = null; + _q = null; + _dmp1 = null; + _dmq1 = null; + _coeff = null; + } + + // convert a (hex) string to a bignum object + private static BigInteger parseBigInt(String str, int r) + { + return new BigInteger(str, r); + } + + private static String linebrk(String s, int n) + { + var ret = ""; + var i = 0; + while (i + n < s.Length) + { + ret += s.Substring(i, i + n) + "\n"; + i += n; + } + return ret + s.Substring(i, s.Length); + } + + private static String byte2Hex(byte b) + { + if (b < 0x10) + return "0" + b.ToString("X"); + else + return b.ToString("X"); + } + + // PKCS#1 (type 2, random) pad input string s to n bytes, and return a bigint + private static BigInteger pkcs1pad2(String s, int n) + { + if (n < s.Length + 11) + { + throw new ArgumentException("Message too long for RSA"); + } + var ba = new byte[n]; + var i = s.Length - 1; + while (i >= 0 && n > 0) ba[--n] = (byte)s[i--]; + ba[--n] = 0; + var rng = new SecureRandom(); + byte[] x = new byte[1]; + while (n > 2) + { // random non-zero pad + x[0] = 0; + while (x[0] == 0) rng.nextBytes(x); + ba[--n] = x[0]; + } + ba[--n] = 2; + ba[--n] = 0; + // for (int k = 0; k < ba.Length; k++) Console.WriteLine("ba[{0}] = {1}", k, (int)ba[k]); + return new BigInteger(ba); + } + + // Set the public key fields N and e from hex strings + public void setPublic(String N, String E) + { + if (N != null && E != null && N.Length > 0 && E.Length > 0) + { + _n = parseBigInt(N, 16); + _e = Int32.Parse(E, NumberStyles.HexNumber); + } + else + throw new ArgumentException("Invalid RSA public key"); + } + + // Perform raw public operation on "x": return x^e (mod n) + private BigInteger doPublic(BigInteger x) + { + return x.modPowInt((uint)_e, _n); + } + + // Return the PKCS#1 RSA encryption of "text" as an even-length hex string + public String encrypt(String text) + { + var m = pkcs1pad2(text, (_n.bitLength() + 7) >> 3); +#if TRACING + m.PrintArray("m"); + Console.WriteLine(m.toString(10)); +#endif + if (m == null) return null; + var c = this.doPublic(m); + if (c == null) return null; + var h = c.toString(16); + if ((h.Length & 1) == 0) return h; else return "0" + h; + } + + // Return the PKCS#1 RSA encryption of "text" as a Base64-encoded string + //function RSAEncryptB64(text) { + // var h = this.encrypt(text); + // if(h) return hex2b64(h); else return null; + //} + + // Undo PKCS#1 (type 2, random) padding and, if valid, return the plaintext + private String pkcs1unpad2(BigInteger d, int n) + { + var b = d.toByteArray(); + var i = 0; + while (i < b.Length && b[i] == 0) ++i; + if (b.Length - i != n - 1 || b[i] != 2) + return null; + ++i; + while (b[i] != 0) + if (++i >= b.Length) return null; + var ret = ""; + char[] oneChar = new char[1]; + while (++i < b.Length) + { + oneChar[0] = (char)b[i]; + ret += new String(oneChar); + } + return ret; + } + + // Set the private key fields N, e, and d from hex strings + private void setPrivate(String N, String E, String D) + { + if (N != null && E != null && N.Length > 0 && E.Length > 0) + { + _n = parseBigInt(N, 16); + _e = Int32.Parse(E, NumberStyles.HexNumber); + _d = parseBigInt(D, 16); + } + else + throw new ArgumentException("Invalid RSA private key"); + } + + // Set the private key fields N, e, d and CRT params from hex strings + public void setPrivateEx(String N, + String E, + String D, + String P, + String Q, + String DP, + String DQ, + String C) + { + if (N != null && E != null && N.Length > 0 && E.Length > 0) + { + _n = parseBigInt(N, 16); + _e = Int32.Parse(E, NumberStyles.HexNumber); + _d = parseBigInt(D, 16); + _p = parseBigInt(P, 16); + _q = parseBigInt(Q, 16); + _dmp1 = parseBigInt(DP, 16); + _dmq1 = parseBigInt(DQ, 16); + _coeff = parseBigInt(C, 16); + } + else + throw new ArgumentException("Invalid RSA private key"); + } + + // Generate a new random private key B bits long, using public expt E + private void generate(int B, String E) + { + var rng = new SecureRandom(); + var qs = B >> 1; + _e = Int32.Parse(E, NumberStyles.HexNumber); + var ee = new BigInteger(E, 16); + for (; ;) + { + for (; ;) + { + _p = new BigInteger(B - qs, 1, rng); + if (_p.subtract(BigInteger.ONE).gcd(ee).compareTo(BigInteger.ONE) == 0 && _p.isProbablePrime(10)) break; + } + for (; ;) + { + _q = new BigInteger(qs, 1, rng); + if (_q.subtract(BigInteger.ONE).gcd(ee).compareTo(BigInteger.ONE) == 0 && _q.isProbablePrime(10)) break; + } + if (_p.compareTo(_q) <= 0) + { + var t = _p; + _p = _q; + _q = t; + } + var p1 = _p.subtract(BigInteger.ONE); + var q1 = _q.subtract(BigInteger.ONE); + var phi = p1.multiply(q1); + if (phi.gcd(ee).compareTo(BigInteger.ONE) == 0) + { + _n = _p.multiply(_q); + _d = ee.modInverse(phi); + _dmp1 = _d.mod(p1); + _dmq1 = _d.mod(q1); + _coeff = _q.modInverse(_p); + break; + } + } + } + + // Perform raw private operation on "x": return x^d (mod n) + private BigInteger doPrivate(BigInteger x) + { + if (_p == null || _q == null) + return x.modPow(_d, _n); + + // TODO: re-calculate any missing CRT params + var xp = x.mod(_p).modPow(_dmp1, _p); + var xq = x.mod(_q).modPow(_dmq1, _q); + + while (xp.compareTo(xq) < 0) + xp = xp.add(_p); + return xp.subtract(xq).multiply(_coeff).mod(_p).multiply(_q).add(xq); + } + + // Return the PKCS#1 RSA decryption of "ctext". + // "ctext" is an even-length hex string and the output is a plain string. + public String decrypt(String ctext) + { + var c = parseBigInt(ctext, 16); + var m = this.doPrivate(c); + if (m == null) return null; + return pkcs1unpad2(m, (_n.bitLength() + 7) >> 3); + } + } +} + |