| /* |
| Licensed to the Apache Software Foundation (ASF) under one |
| or more contributor license agreements. See the NOTICE file |
| distributed with this work for additional information |
| regarding copyright ownership. The ASF licenses this file |
| to you under the Apache License, Version 2.0 (the |
| "License"); you may not use this file except in compliance |
| with the License. You may obtain a copy of the License at |
| |
| http://www.apache.org/licenses/LICENSE-2.0 |
| |
| Unless required by applicable law or agreed to in writing, |
| software distributed under the License is distributed on an |
| "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| KIND, either express or implied. See the License for the |
| specific language governing permissions and limitations |
| under the License. |
| */ |
| |
| /* AMCL FF number class */ |
| |
| var FF = function(ctx) { |
| "use strict"; |
| |
| /** |
| * Creates an instance of FF. |
| * |
| * @constructor |
| * @this {FF} |
| */ |
| var FF = function(n) { |
| this.v = new Array(n); |
| this.length = n; |
| for (var i = 0; i < n; i++) { |
| this.v[i] = new ctx.BIG(0); |
| } |
| }; |
| |
| FF.FFLEN = ctx.config["@ML"]; |
| FF.P_MBITS = ctx.BIG.MODBYTES * 8; |
| FF.P_OMASK = ((-1) << (FF.P_MBITS % ctx.BIG.BASEBITS)); |
| FF.P_FEXCESS = (1 << (ctx.BIG.BASEBITS * ctx.BIG.NLEN - FF.P_MBITS - 1)); |
| FF.P_TBITS = (FF.P_MBITS % ctx.BIG.BASEBITS); |
| FF.FF_BITS = (ctx.BIG.BIGBITS * FF.FFLEN); |
| FF.HFLEN = (FF.FFLEN / 2); /* Useful for half-size RSA private key operations */ |
| |
| FF.prototype = { |
| /* set to zero */ |
| |
| P_EXCESS: function() { |
| return ((this.v[this.length - 1].get(ctx.BIG.NLEN - 1) & FF.P_OMASK) >> (FF.P_TBITS)) + 1; |
| }, |
| |
| zero: function() { |
| for (var i = 0; i < this.length; i++) { |
| this.v[i].zero(); |
| } |
| |
| return this; |
| }, |
| |
| getlen: function() { |
| return this.length; |
| }, |
| |
| /** |
| * set to integer |
| * |
| * @this {FF} |
| * @param m Integer value to be set to |
| */ |
| set: function(m) { |
| this.zero(); |
| this.v[0].set(0, (m & ctx.BIG.BMASK)); |
| this.v[0].set(1, (m >> ctx.BIG.BASEBITS)); |
| }, |
| |
| /** |
| * copy from FF b |
| * |
| * @this {FF} |
| * @param b FF element to copy from |
| */ |
| copy: function(b) { |
| for (var i = 0; i < this.length; i++) { |
| this.v[i].copy(b.v[i]); |
| } |
| }, |
| |
| /** |
| * copy from FF b |
| * |
| * @this {FF} |
| * @param b FF element to copy from |
| */ |
| rcopy: function(b) { |
| for (var i = 0; i < this.length; i++) { |
| this.v[i].rcopy(b[i]); |
| } |
| }, |
| |
| /** |
| * x=y<<n |
| * |
| * @this {FF} |
| */ |
| dsucopy: function(b) { |
| for (var i = 0; i < b.length; i++) { |
| this.v[b.length + i].copy(b.v[i]); |
| this.v[i].zero(); |
| } |
| }, |
| |
| /** |
| * x=y |
| * |
| * @this {FF} |
| */ |
| dscopy: function(b) { |
| for (var i = 0; i < b.length; i++) { |
| this.v[i].copy(b.v[i]); |
| this.v[b.length + i].zero(); |
| } |
| }, |
| |
| /** |
| * x=y>>n |
| * |
| * @this {FF} |
| */ |
| sducopy: function(b) { |
| for (var i = 0; i < this.length; i++) { |
| this.v[i].copy(b.v[this.length + i]); |
| } |
| }, |
| |
| one: function() { |
| this.v[0].one(); |
| for (var i = 1; i < this.length; i++) { |
| this.v[i].zero(); |
| } |
| }, |
| |
| /** |
| * test equals 0 |
| * |
| * @this {FF} |
| */ |
| iszilch: function() { |
| for (var i = 0; i < this.length; i++) { |
| if (!this.v[i].iszilch()) { |
| return false; |
| } |
| } |
| |
| return true; |
| }, |
| |
| /** |
| * shift right by BIGBITS-bit words |
| * |
| * @this {FF} |
| */ |
| shrw: function(n) { |
| for (var i = 0; i < n; i++) { |
| this.v[i].copy(this.v[i + n]); |
| this.v[i + n].zero(); |
| } |
| }, |
| |
| /** |
| * shift left by BIGBITS-bit words |
| * |
| * @this {FF} |
| */ |
| shlw: function(n) { |
| for (var i = 0; i < n; i++) { |
| this.v[n + i].copy(this.v[i]); |
| this.v[i].zero(); |
| } |
| }, |
| |
| /** |
| * extract last bit |
| * |
| * @this {FF} |
| */ |
| parity: function() { |
| return this.v[0].parity(); |
| }, |
| |
| lastbits: function(m) { |
| return this.v[0].lastbits(m); |
| }, |
| |
| /** |
| * recursive add |
| * |
| * @this {FF} |
| */ |
| radd: function(vp, x, xp, y, yp, n) { |
| for (var i = 0; i < n; i++) { |
| this.v[vp + i].copy(x.v[xp + i]); |
| this.v[vp + i].add(y.v[yp + i]); |
| } |
| }, |
| |
| /** |
| * recursive inc |
| * |
| * @this {FF} |
| */ |
| rinc: function(vp, y, yp, n) { |
| for (var i = 0; i < n; i++) { |
| this.v[vp + i].add(y.v[yp + i]); |
| } |
| }, |
| |
| /** |
| * recursive sub |
| * |
| * @this {FF} |
| */ |
| rsub: function(vp, x, xp, y, yp, n) { |
| for (var i = 0; i < n; i++) { |
| this.v[vp + i].copy(x.v[xp + i]); |
| this.v[vp + i].sub(y.v[yp + i]); |
| } |
| }, |
| |
| /** |
| * recursive dec |
| * |
| * @this {FF} |
| */ |
| rdec: function(vp, y, yp, n) { |
| for (var i = 0; i < n; i++) { |
| this.v[vp + i].sub(y.v[yp + i]); |
| } |
| }, |
| |
| /** |
| * simple add |
| * |
| * @this {FF} |
| */ |
| add: function(b) { |
| for (var i = 0; i < this.length; i++) { |
| this.v[i].add(b.v[i]); |
| } |
| }, |
| |
| /** |
| * simple sub |
| * |
| * @this {FF} |
| */ |
| sub: function(b) { |
| for (var i = 0; i < this.length; i++) { |
| this.v[i].sub(b.v[i]); |
| } |
| }, |
| |
| /** |
| * reverse sub |
| * |
| * @this {FF} |
| */ |
| revsub: function(b) { |
| for (var i = 0; i < this.length; i++) { |
| this.v[i].rsub(b.v[i]); |
| } |
| }, |
| |
| /** |
| * increment/decrement by a small integer |
| * |
| * @this {FF} |
| */ |
| inc: function(m) { |
| this.v[0].inc(m); |
| this.norm(); |
| }, |
| |
| dec: function(m) { |
| this.v[0].dec(m); |
| this.norm(); |
| }, |
| |
| /** |
| * normalise - but hold any overflow in top part unless n<0 |
| * |
| * @this {FF} |
| */ |
| rnorm: function(vp, n) { |
| var trunc = false, |
| i, carry; |
| |
| if (n < 0) { /* -v n signals to do truncation */ |
| n = -n; |
| trunc = true; |
| } |
| |
| for (i = 0; i < n - 1; i++) { |
| carry = this.v[vp + i].norm(); |
| this.v[vp + i].xortop(carry << FF.P_TBITS); |
| this.v[vp + i + 1].inc(carry); |
| } |
| carry = this.v[vp + n - 1].norm(); |
| |
| if (trunc) { |
| this.v[vp + n - 1].xortop(carry << FF.P_TBITS); |
| } |
| |
| return this; |
| }, |
| |
| norm: function() { |
| this.rnorm(0, this.length); |
| }, |
| |
| /** |
| * shift left by one bit |
| * |
| * @this {FF} |
| */ |
| shl: function() { |
| var delay_carry = 0, |
| i, carry; |
| |
| for (i = 0; i < this.length - 1; i++) { |
| carry = this.v[i].fshl(1); |
| this.v[i].inc(delay_carry); |
| this.v[i].xortop(carry << FF.P_TBITS); |
| delay_carry = carry; |
| } |
| |
| this.v[this.length - 1].fshl(1); |
| this.v[this.length - 1].inc(delay_carry); |
| }, |
| |
| /** |
| * shift right by one bit |
| * |
| * @this {FF} |
| */ |
| shr: function() { |
| var i, carry; |
| |
| for (i = this.length - 1; i > 0; i--) { |
| carry = this.v[i].fshr(1); |
| this.v[i - 1].ortop(carry << FF.P_TBITS); |
| } |
| |
| this.v[0].fshr(1); |
| }, |
| |
| /** |
| * Convert to Hex String |
| * |
| * @this {FF} |
| */ |
| toString: function() { |
| var s = "", |
| i; |
| |
| this.norm(); |
| |
| for (i = this.length - 1; i >= 0; i--) { |
| s += this.v[i].toString(); |
| } |
| |
| return s; |
| }, |
| |
| /** |
| * Convert FFs to/from byte arrays |
| * |
| * @this {FF} |
| */ |
| toBytes: function(b) { |
| var i; |
| |
| for (i = 0; i < this.length; i++) { |
| this.v[i].tobytearray(b, (this.length - i - 1) * ctx.BIG.MODBYTES); |
| } |
| }, |
| |
| /** |
| * z=x*y, t is workspace |
| * |
| * @this {FF} |
| */ |
| karmul: function(vp, x, xp, y, yp, t, tp, n) { |
| var nd2, d; |
| |
| if (n === 1) { |
| x.v[xp].norm(); |
| y.v[yp].norm(); |
| d = ctx.BIG.mul(x.v[xp], y.v[yp]); |
| this.v[vp + 1] = d.split(8 * ctx.BIG.MODBYTES); |
| this.v[vp].copy(d); |
| |
| return; |
| } |
| |
| nd2 = n / 2; |
| this.radd(vp, x, xp, x, xp + nd2, nd2); |
| this.rnorm(vp, nd2); /* Important - required for 32-bit build */ |
| this.radd(vp + nd2, y, yp, y, yp + nd2, nd2); |
| this.rnorm(vp + nd2, nd2); /* Important - required for 32-bit build */ |
| t.karmul(tp, this, vp, this, vp + nd2, t, tp + n, nd2); |
| this.karmul(vp, x, xp, y, yp, t, tp + n, nd2); |
| this.karmul(vp + n, x, xp + nd2, y, yp + nd2, t, tp + n, nd2); |
| t.rdec(tp, this, vp, n); |
| t.rdec(tp, this, vp + n, n); |
| this.rinc(vp + nd2, t, tp, n); |
| this.rnorm(vp, 2 * n); |
| }, |
| |
| karsqr: function(vp, x, xp, t, tp, n) { |
| var nd2, d; |
| |
| if (n === 1) { |
| x.v[xp].norm(); |
| d = ctx.BIG.sqr(x.v[xp]); |
| this.v[vp + 1].copy(d.split(8 * ctx.BIG.MODBYTES)); |
| this.v[vp].copy(d); |
| |
| return; |
| } |
| |
| nd2 = n / 2; |
| this.karsqr(vp, x, xp, t, tp + n, nd2); |
| this.karsqr(vp + n, x, xp + nd2, t, tp + n, nd2); |
| t.karmul(tp, x, xp, x, xp + nd2, t, tp + n, nd2); |
| this.rinc(vp + nd2, t, tp, n); |
| this.rinc(vp + nd2, t, tp, n); |
| this.rnorm(vp + nd2, n); |
| }, |
| |
| karmul_lower: function(vp, x, xp, y, yp, t, tp, n) { /* Calculates Least Significant bottom half of x*y */ |
| var nd2; |
| |
| if (n === 1) { /* only calculate bottom half of product */ |
| this.v[vp].copy(ctx.BIG.smul(x.v[xp], y.v[yp])); |
| |
| return; |
| } |
| |
| nd2 = n / 2; |
| |
| this.karmul(vp, x, xp, y, yp, t, tp + n, nd2); |
| t.karmul_lower(tp, x, xp + nd2, y, yp, t, tp + n, nd2); |
| this.rinc(vp + nd2, t, tp, nd2); |
| t.karmul_lower(tp, x, xp, y, yp + nd2, t, tp + n, nd2); |
| |
| this.rinc(vp + nd2, t, tp, nd2); |
| this.rnorm(vp + nd2, -nd2); /* truncate it */ |
| }, |
| |
| karmul_upper: function(x, y, t, n) { /* Calculates Most Significant upper half of x*y, given lower part */ |
| var nd2; |
| |
| nd2 = n / 2; |
| this.radd(n, x, 0, x, nd2, nd2); |
| this.radd(n + nd2, y, 0, y, nd2, nd2); |
| this.rnorm(n, nd2); |
| this.rnorm(n + nd2, nd2); |
| |
| t.karmul(0, this, n + nd2, this, n, t, n, nd2); /* t = (a0+a1)(b0+b1) */ |
| this.karmul(n, x, nd2, y, nd2, t, n, nd2); /* z[n]= a1*b1 */ |
| /* z[0-nd2]=l(a0b0) z[nd2-n]= h(a0b0)+l(t)-l(a0b0)-l(a1b1) */ |
| t.rdec(0, this, n, n); /* t=t-a1b1 */ |
| this.rinc(nd2, this, 0, nd2); /* z[nd2-n]+=l(a0b0) = h(a0b0)+l(t)-l(a1b1) */ |
| this.rdec(nd2, t, 0, nd2); /* z[nd2-n]=h(a0b0)+l(t)-l(a1b1)-l(t-a1b1)=h(a0b0) */ |
| this.rnorm(0, -n); /* a0b0 now in z - truncate it */ |
| t.rdec(0, this, 0, n); /* (a0+a1)(b0+b1) - a0b0 */ |
| this.rinc(nd2, t, 0, n); |
| |
| this.rnorm(nd2, n); |
| }, |
| |
| /** |
| * return low part of product this*y |
| * |
| * @this {FF} |
| */ |
| lmul: function(y) { |
| var n = this.length, |
| t = new FF(2 * n), |
| x = new FF(n); |
| |
| x.copy(this); |
| this.karmul_lower(0, x, 0, y, 0, t, 0, n); |
| }, |
| |
| /** |
| * Set b=b mod c |
| * |
| * @this {FF} |
| */ |
| mod: function(c) { |
| var k = 0; |
| |
| this.norm(); |
| if (FF.comp(this, c) < 0) { |
| return; |
| } |
| |
| do { |
| c.shl(); |
| k++; |
| } while (FF.comp(this, c) >= 0); |
| |
| while (k > 0) { |
| c.shr(); |
| |
| if (FF.comp(this, c) >= 0) { |
| this.sub(c); |
| this.norm(); |
| } |
| |
| k--; |
| } |
| }, |
| |
| /** |
| * return this mod modulus |
| * |
| * @this {FF} |
| * @param N Mmodulus |
| * @param ND Montgomery Constant |
| * @return this mod N |
| */ |
| reduce: function(N, ND) { /* fast karatsuba Montgomery reduction */ |
| var n = N.length, |
| t = new FF(2 * n), |
| r = new FF(n), |
| m = new FF(n); |
| |
| r.sducopy(this); |
| m.karmul_lower(0, this, 0, ND, 0, t, 0, n); |
| this.karmul_upper(N, m, t, n); |
| m.sducopy(this); |
| |
| r.add(N); |
| r.sub(m); |
| r.norm(); |
| |
| return r; |
| }, |
| |
| /* Set r=this mod b */ |
| /* this is of length - 2*n */ |
| /* r,b is of length - n */ |
| |
| /** |
| * Reduces a double-length FF with respect to a given modulus |
| * |
| * @this {FF} |
| * @param b Mmodulus |
| * @return this mod N |
| */ |
| dmod: function(b) { |
| var n = b.length, |
| m = new FF(2 * n), |
| x = new FF(2 * n), |
| r = new FF(n), |
| k; |
| |
| x.copy(this); |
| x.norm(); |
| m.dsucopy(b); |
| k = ctx.BIG.BIGBITS * n; |
| |
| while (FF.comp(x, m) >= 0) { |
| x.sub(m); |
| x.norm(); |
| } |
| |
| while (k > 0) { |
| m.shr(); |
| |
| if (FF.comp(x, m) >= 0) { |
| x.sub(m); |
| x.norm(); |
| } |
| |
| k--; |
| } |
| |
| r.copy(x); |
| r.mod(b); |
| |
| return r; |
| }, |
| |
| /** |
| * Set return=1/this mod p. Binary method - a<p on entry |
| * |
| * @this {FF} |
| */ |
| invmodp: function(p) { |
| var n = p.length, |
| u = new FF(n), |
| v = new FF(n), |
| x1 = new FF(n), |
| x2 = new FF(n), |
| t = new FF(n), |
| one = new FF(n); |
| |
| one.one(); |
| u.copy(this); |
| v.copy(p); |
| x1.copy(one); |
| x2.zero(); |
| |
| // reduce n in here as well! |
| while (FF.comp(u, one) !== 0 && FF.comp(v, one) !== 0) { |
| while (u.parity() === 0) { |
| u.shr(); |
| if (x1.parity() !== 0) { |
| x1.add(p); |
| x1.norm(); |
| } |
| x1.shr(); |
| } |
| |
| while (v.parity() === 0) { |
| v.shr(); |
| if (x2.parity() !== 0) { |
| x2.add(p); |
| x2.norm(); |
| } |
| x2.shr(); |
| } |
| |
| if (FF.comp(u, v) >= 0) { |
| u.sub(v); |
| u.norm(); |
| |
| if (FF.comp(x1, x2) >= 0) { |
| x1.sub(x2); |
| } else { |
| t.copy(p); |
| t.sub(x2); |
| x1.add(t); |
| } |
| |
| x1.norm(); |
| } else { |
| v.sub(u); |
| v.norm(); |
| |
| if (FF.comp(x2, x1) >= 0) { |
| x2.sub(x1); |
| } else { |
| t.copy(p); |
| t.sub(x1); |
| x2.add(t); |
| } |
| |
| x2.norm(); |
| } |
| } |
| |
| if (FF.comp(u, one) === 0) { |
| this.copy(x1); |
| } else { |
| this.copy(x2); |
| } |
| }, |
| |
| /** |
| * nresidue mod m |
| * |
| * @this {FF} |
| */ |
| nres: function(m) { |
| var n = m.length, |
| d; |
| |
| if (n === 1) { |
| d = new ctx.DBIG(0); |
| d.hcopy(this.v[0]); |
| d.shl(ctx.BIG.NLEN * ctx.BIG.BASEBITS); |
| this.v[0].copy(d.mod(m.v[0])); |
| } else { |
| d = new FF(2 * n); |
| d.dsucopy(this); |
| this.copy(d.dmod(m)); |
| } |
| }, |
| |
| redc: function(m, ND) { |
| var n = m.length, |
| d; |
| |
| if (n === 1) { |
| d = new ctx.DBIG(0); |
| d.hcopy(this.v[0]); |
| this.v[0].copy(ctx.BIG.monty(m.v[0], (1 << ctx.BIG.BASEBITS) - ND.v[0].w[0], d)); |
| } else { |
| d = new FF(2 * n); |
| this.mod(m); |
| d.dscopy(this); |
| this.copy(d.reduce(m, ND)); |
| this.mod(m); |
| } |
| }, |
| |
| mod2m: function(m) { |
| for (var i = m; i < this.length; i++) { |
| this.v[i].zero(); |
| } |
| }, |
| |
| /** |
| * U=1/a mod 2^m - Arazi & Qi |
| * |
| * @this {FF} |
| */ |
| invmod2m: function() { |
| var n = this.length, |
| b = new FF(n), |
| c = new FF(n), |
| U = new FF(n), |
| t, i; |
| |
| U.zero(); |
| U.v[0].copy(this.v[0]); |
| U.v[0].invmod2m(); |
| |
| for (i = 1; i < n; i <<= 1) { |
| b.copy(this); |
| b.mod2m(i); |
| t = FF.mul(U, b); |
| t.shrw(i); |
| b.copy(t); |
| c.copy(this); |
| c.shrw(i); |
| c.mod2m(i); |
| c.lmul(U); |
| c.mod2m(i); |
| |
| b.add(c); |
| b.norm(); |
| b.lmul(U); |
| b.mod2m(i); |
| |
| c.one(); |
| c.shlw(i); |
| b.revsub(c); |
| b.norm(); |
| b.shlw(i); |
| U.add(b); |
| } |
| U.norm(); |
| |
| return U; |
| }, |
| |
| random: function(rng) { |
| var n = this.length, |
| i; |
| |
| for (i = 0; i < n; i++) { |
| this.v[i].copy(ctx.BIG.random(rng)); |
| } |
| |
| /* make sure top bit is 1 */ |
| while (this.v[n - 1].nbits() < ctx.BIG.MODBYTES * 8) { |
| this.v[n - 1].copy(ctx.BIG.random(rng)); |
| } |
| }, |
| |
| /** |
| * generate random x |
| * |
| * @this {FF} |
| */ |
| randomnum: function(p, rng) { |
| var n = this.length, |
| d = new FF(2 * n), |
| i; |
| |
| for (i = 0; i < 2 * n; i++) { |
| d.v[i].copy(ctx.BIG.random(rng)); |
| } |
| |
| this.copy(d.dmod(p)); |
| }, |
| |
| /** |
| * this*=y mod p |
| * |
| * @this {FF} |
| */ |
| modmul: function(y, p, nd) { |
| var ex = this.P_EXCESS(), |
| ey = y.P_EXCESS(), |
| n = p.length, |
| d; |
| |
| if ((ex + 1) >= Math.floor((FF.P_FEXCESS - 1) / (ey + 1))) { |
| this.mod(p); |
| } |
| |
| if (n === 1) { |
| d = ctx.BIG.mul(this.v[0], y.v[0]); |
| this.v[0].copy(ctx.BIG.monty(p.v[0], (1 << ctx.BIG.BASEBITS) - nd.v[0].w[0], d)); |
| } else { |
| d = FF.mul(this, y); |
| this.copy(d.reduce(p, nd)); |
| } |
| }, |
| |
| /** |
| * this*=y mod p |
| * |
| * @this {FF} |
| */ |
| modsqr: function(p, nd) { |
| var ex = this.P_EXCESS(), |
| n, d; |
| |
| if ((ex + 1) >= Math.floor((FF.P_FEXCESS - 1) / (ex + 1))) { |
| this.mod(p); |
| } |
| n = p.length; |
| |
| if (n === 1) { |
| d = ctx.BIG.sqr(this.v[0]); |
| this.v[0].copy(ctx.BIG.monty(p.v[0], (1 << ctx.BIG.BASEBITS) - nd.v[0].w[0], d)); |
| } else { |
| d = FF.sqr(this); |
| this.copy(d.reduce(p, nd)); |
| } |
| }, |
| |
| /** |
| * this=this^e mod p using side-channel resistant Montgomery Ladder, for large e |
| * |
| * @this {FF} |
| * @param e exponent |
| * @param p modulus |
| */ |
| skpow: function(e, p) { |
| var n = p.length, |
| R0 = new FF(n), |
| R1 = new FF(n), |
| ND = p.invmod2m(), |
| i, b; |
| |
| this.mod(p); |
| R0.one(); |
| R1.copy(this); |
| R0.nres(p); |
| R1.nres(p); |
| |
| for (i = 8 * ctx.BIG.MODBYTES * n - 1; i >= 0; i--) { |
| b = e.v[Math.floor(i / ctx.BIG.BIGBITS)].bit(i % ctx.BIG.BIGBITS); |
| |
| this.copy(R0); |
| this.modmul(R1, p, ND); |
| |
| FF.cswap(R0, R1, b); |
| R0.modsqr(p, ND); |
| |
| R1.copy(this); |
| FF.cswap(R0, R1, b); |
| } |
| |
| this.copy(R0); |
| this.redc(p, ND); |
| }, |
| |
| /** |
| * this=this^e mod p using side-channel resistant Montgomery Ladder, for short e |
| * |
| * @this {FF} |
| * @param e exponent |
| * @param p modulus |
| */ |
| skspow: function(e, p) { |
| var n = p.length, |
| R0 = new FF(n), |
| R1 = new FF(n), |
| ND = p.invmod2m(), |
| i, b; |
| |
| this.mod(p); |
| R0.one(); |
| R1.copy(this); |
| R0.nres(p); |
| R1.nres(p); |
| |
| for (i = 8 * ctx.BIG.MODBYTES - 1; i >= 0; i--) { |
| b = e.bit(i); |
| this.copy(R0); |
| this.modmul(R1, p, ND); |
| |
| FF.cswap(R0, R1, b); |
| R0.modsqr(p, ND); |
| |
| R1.copy(this); |
| FF.cswap(R0, R1, b); |
| } |
| this.copy(R0); |
| this.redc(p, ND); |
| }, |
| |
| /** |
| * raise to an integer power - right-to-left method |
| * |
| * @this {FF} |
| * @param e exponent |
| * @param p modulus |
| */ |
| power: function(e, p) { |
| var n = p.length, |
| f = true, |
| w = new FF(n), |
| ND = p.invmod2m(); |
| |
| w.copy(this); |
| w.nres(p); |
| |
| if (e == 2) { |
| this.copy(w); |
| this.modsqr(p, ND); |
| } else { |
| for (;;) { |
| if (e % 2 == 1) { |
| if (f) { |
| this.copy(w); |
| } else { |
| this.modmul(w, p, ND); |
| } |
| f = false; |
| } |
| e >>= 1; |
| if (e === 0) { |
| break; |
| } |
| w.modsqr(p, ND); |
| } |
| } |
| |
| this.redc(p, ND); |
| }, |
| |
| /** |
| * this=this^e mod p, faster but not side channel resistant |
| * |
| * @this {FF} |
| * @param e exponent |
| * @param p modulus |
| */ |
| pow: function(e, p) { |
| var n = p.length, |
| w = new FF(n), |
| ND = p.invmod2m(), |
| i, b; |
| |
| w.copy(this); |
| this.one(); |
| this.nres(p); |
| w.nres(p); |
| |
| for (i = 8 * ctx.BIG.MODBYTES * n - 1; i >= 0; i--) { |
| this.modsqr(p, ND); |
| b = e.v[Math.floor(i / ctx.BIG.BIGBITS)].bit(i % ctx.BIG.BIGBITS); |
| if (b === 1) { |
| this.modmul(w, p, ND); |
| } |
| } |
| |
| this.redc(p, ND); |
| }, |
| |
| /** |
| * double exponentiation r=x^e.y^f mod p |
| * |
| * @this {FF} |
| * @param e exponent |
| * @param y FF instance |
| * @param f exponent |
| * @param p modulus |
| */ |
| pow2: function(e, y, f, p) { |
| var n = p.length, |
| xn = new FF(n), |
| yn = new FF(n), |
| xy = new FF(n), |
| ND = p.invmod2m(), |
| i, eb, fb; |
| |
| xn.copy(this); |
| yn.copy(y); |
| xn.nres(p); |
| yn.nres(p); |
| xy.copy(xn); |
| xy.modmul(yn, p, ND); |
| this.one(); |
| this.nres(p); |
| |
| for (i = 8 * ctx.BIG.MODBYTES - 1; i >= 0; i--) { |
| eb = e.bit(i); |
| fb = f.bit(i); |
| this.modsqr(p, ND); |
| |
| if (eb == 1) { |
| if (fb == 1) { |
| this.modmul(xy, p, ND); |
| } else { |
| this.modmul(xn, p, ND); |
| } |
| } else { |
| if (fb == 1) { |
| this.modmul(yn, p, ND); |
| } |
| } |
| } |
| this.redc(p, ND); |
| }, |
| |
| /** |
| * Test if an FF has factor in common with integer s |
| * |
| * @this {FF} |
| * @param s integerexponent |
| * @return true or false |
| */ |
| cfactor: function(s) { |
| var n = this.length, |
| x = new FF(n), |
| y = new FF(n), |
| r, g; |
| |
| y.set(s); |
| |
| x.copy(this); |
| x.norm(); |
| |
| do { |
| x.sub(y); |
| x.norm(); |
| while (!x.iszilch() && x.parity() === 0) { |
| x.shr(); |
| } |
| } while (FF.comp(x, y) > 0); |
| |
| g = x.v[0].get(0); |
| r = FF.igcd(s, g); |
| if (r > 1) { |
| return true; |
| } |
| |
| return false; |
| } |
| }; |
| |
| /** |
| * compare a and b - must be normalised, and of same length |
| * |
| * @this {FF} |
| * @param a FF number |
| * @param b FF number |
| * @return zero of error codetrue or false |
| */ |
| FF.comp = function(a, b) { |
| var i, j; |
| |
| for (i = a.length - 1; i >= 0; i--) { |
| j = ctx.BIG.comp(a.v[i], b.v[i]); |
| if (j !== 0) { |
| return j; |
| } |
| } |
| |
| return 0; |
| }; |
| |
| FF.fromBytes = function(x, b) { |
| var i; |
| |
| for (i = 0; i < x.length; i++) { |
| x.v[i] = ctx.BIG.frombytearray(b, (x.length - i - 1) * ctx.BIG.MODBYTES); |
| } |
| }; |
| |
| /** |
| * in-place swapping using xor - side channel resistant - lengths must be the same |
| * |
| * @this {FF} |
| */ |
| FF.cswap = function(a, b, d) { |
| var i; |
| |
| for (i = 0; i < a.length; i++) { |
| a.v[i].cswap(b.v[i], d); |
| } |
| }; |
| |
| /** |
| * z=x*y. Assumes x and y are of same length. |
| * |
| * @this {FF} |
| */ |
| FF.mul = function(x, y) { |
| var n = x.length, |
| z = new FF(2 * n), |
| t = new FF(2 * n); |
| |
| z.karmul(0, x, 0, y, 0, t, 0, n); |
| |
| return z; |
| }; |
| |
| /** |
| * z=x^2 |
| * |
| * @this {FF} |
| */ |
| FF.sqr = function(x) { |
| var n = x.length, |
| z = new FF(2 * n), |
| t = new FF(2 * n); |
| |
| z.karsqr(0, x, 0, t, 0, n); |
| |
| return z; |
| }; |
| |
| FF.igcd = function(x, y) { /* integer GCD, returns GCD of x and y */ |
| var r; |
| |
| if (y === 0) { |
| return x; |
| } |
| |
| while ((r = x % y) !== 0) { |
| x = y; |
| y = r; |
| } |
| |
| return y; |
| }; |
| |
| /** |
| * Miller-Rabin test for primality. |
| * |
| * @this {FF} |
| * @param p FF instance to be tested |
| * @param rmg an instance of a Cryptographically Secure Random Number Generator |
| */ |
| FF.prime = function(p, rng) { |
| var n = p.length, |
| s = 0, |
| loop, |
| d = new FF(n), |
| x = new FF(n), |
| unity = new FF(n), |
| nm1 = new FF(n), |
| sf = 4849845, /* 3*5*.. *19 */ |
| i, j; |
| |
| p.norm(); |
| |
| if (p.cfactor(sf)) { |
| return false; |
| } |
| |
| unity.one(); |
| nm1.copy(p); |
| nm1.sub(unity); |
| nm1.norm(); |
| d.copy(nm1); |
| |
| while (d.parity() === 0) { |
| d.shr(); |
| s++; |
| } |
| |
| if (s === 0) { |
| return false; |
| } |
| |
| for (i = 0; i < 10; i++) { |
| x.randomnum(p, rng); |
| x.pow(d, p); |
| |
| if (FF.comp(x, unity) === 0 || FF.comp(x, nm1) === 0) { |
| continue; |
| } |
| |
| loop = false; |
| |
| for (j = 1; j < s; j++) { |
| x.power(2, p); |
| |
| if (FF.comp(x, unity) === 0) { |
| return false; |
| } |
| |
| if (FF.comp(x, nm1) === 0) { |
| loop = true; |
| break; |
| } |
| } |
| if (loop) { |
| continue; |
| } |
| |
| return false; |
| } |
| |
| return true; |
| }; |
| |
| return FF; |
| }; |
| |
| |
| if (typeof module !== "undefined" && typeof module.exports !== "undefined") { |
| module.exports = { |
| FF: FF |
| }; |
| } |