| /* |
| 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. |
| */ |
| |
| /* Finite Field arithmetic */ |
| /* AMCL mod p functions */ |
| |
| var FP = function(ctx) { |
| "use strict"; |
| |
| /** |
| * Creates an instance of FP. |
| * |
| * @constructor |
| * @this {FP} |
| * @param x FP / BIG instance |
| */ |
| var FP = function(x) { |
| if (x instanceof FP) { |
| this.f = new ctx.BIG(x.f); |
| this.XES = x.XES; |
| } else { |
| this.f = new ctx.BIG(x); |
| this.XES = 1; |
| if (!this.f.iszilch()) |
| this.nres(); |
| } |
| }; |
| |
| FP.NOT_SPECIAL = 0; |
| FP.PSEUDO_MERSENNE = 1; |
| FP.GENERALISED_MERSENNE = 2; |
| FP.MONTGOMERY_FRIENDLY = 3; |
| |
| FP.ZERO = 0; |
| FP.ONE = 1; |
| FP.SPARSER = 2; |
| FP.SPARSE = 3; |
| FP.DENSE= 4; |
| |
| FP.MODBITS = ctx.config["@NBT"]; |
| FP.MOD8 = ctx.config["@M8"]; |
| FP.MODTYPE = ctx.config["@MT"]; |
| |
| FP.FEXCESS = ((1 << ctx.config["@SH"])-1); // 2^(BASEBITS*NLEN-MODBITS)-1 |
| FP.OMASK = (-1) << FP.TBITS; |
| FP.TBITS = FP.MODBITS % ctx.BIG.BASEBITS; |
| FP.TMASK = (1 << FP.TBITS) - 1; |
| |
| FP.prototype = { |
| |
| /** |
| * Set FP to zero |
| * |
| * @this {FP} |
| */ |
| zero: function() { |
| this.XES = 1; |
| this.f.zero(); |
| }, |
| |
| /** |
| * copy from a ctx.BIG in ROM |
| * |
| * @this {FP} |
| * @param x FP instance to be copied |
| */ |
| rcopy: function(y) { |
| this.f.rcopy(y); |
| this.nres(); |
| }, |
| |
| /** |
| * copy from another ctx.BIG |
| * |
| * @this {FP} |
| * @param x FP instance to be copied |
| */ |
| bcopy: function(y) { |
| this.f.copy(y); |
| this.nres(); |
| }, |
| |
| /** |
| * Copy FP to another FP |
| * |
| * @this {FP} |
| * @param x FP instance to be copied |
| */ |
| copy: function(y) { |
| this.XES = y.XES; |
| this.f.copy(y.f); |
| }, |
| |
| /** |
| * Conditional constant time swap of two FP numbers |
| * |
| * @this {BIG} |
| * @parameter b FP number |
| * @parameter d Integer |
| */ |
| cswap: function(b, d) { |
| this.f.cswap(b.f, d); |
| var t, c = d; |
| c = ~(c - 1); |
| t = c & (this.XES ^ b.XES); |
| this.XES ^= t; |
| b.XES ^= t; |
| }, |
| |
| /** |
| * Conditional copy of FP number |
| * |
| * @this {FP} |
| * @param g FP instance |
| * @param d copy depends on this value |
| */ |
| cmove: function(b, d) { |
| var c = d; |
| |
| c = ~(c - 1); |
| |
| this.f.cmove(b.f, d); |
| this.XES ^= (this.XES ^ b.XES) & c; |
| }, |
| |
| /** |
| * Converts from BIG integer to residue form mod Modulus |
| * |
| * @this {FP} |
| */ |
| nres: function() { |
| var r, d; |
| |
| if (FP.MODTYPE != FP.PSEUDO_MERSENNE && FP.MODTYPE != FP.GENERALISED_MERSENNE) { |
| r = new ctx.BIG(); |
| r.rcopy(ctx.ROM_FIELD.R2modp); |
| |
| d = ctx.BIG.mul(this.f, r); |
| this.f.copy(FP.mod(d)); |
| this.XES = 2; |
| } else { |
| this.XES = 1; |
| } |
| |
| return this; |
| }, |
| |
| /** |
| * Converts from residue form back to BIG integer form |
| * |
| * @this {FP} |
| */ |
| redc: function() { |
| var r = new ctx.BIG(0), |
| d, w; |
| |
| r.copy(this.f); |
| |
| if (FP.MODTYPE != FP.PSEUDO_MERSENNE && FP.MODTYPE != FP.GENERALISED_MERSENNE) { |
| d = new ctx.DBIG(0); |
| d.hcopy(this.f); |
| w = FP.mod(d); |
| r.copy(w); |
| } |
| |
| return r; |
| }, |
| |
| /** |
| * convert to hex string |
| * |
| * @this {FP} |
| */ |
| toString: function() { |
| var s = this.redc().toString(); |
| return s; |
| }, |
| |
| /** |
| * Tests for FP equal to zero |
| * |
| * @this {FP} |
| */ |
| iszilch: function() { |
| var c=new FP(0); c.copy(this); |
| c.reduce(); |
| return c.f.iszilch(); |
| }, |
| |
| /** |
| * Reduces all components of possibly unreduced FP mod Modulus |
| * |
| * @this {FP} |
| */ |
| reduce: function() { |
| var q,carry,sr,sb,m = new ctx.BIG(0); |
| m.rcopy(ctx.ROM_FIELD.Modulus); |
| var r = new ctx.BIG(0); |
| r.rcopy(ctx.ROM_FIELD.Modulus); |
| this.f.norm(); |
| |
| if (this.XES>16) |
| { |
| q=FP.quo(this.f,m); |
| carry=r.pmul(q); |
| r.w[ctx.BIG.NLEN-1]+=(carry<<ctx.BIG.BASEBITS); // correction - put any carry out back in again |
| this.f.sub(r); |
| this.f.norm(); |
| sb=2; |
| } |
| else { |
| sb=FP.logb2(this.XES-1); |
| } |
| m.fshl(sb); |
| |
| while (sb>0) |
| { |
| // constant time... |
| sr=ctx.BIG.ssn(r,this.f,m); // optimized combined shift, subtract and norm |
| this.f.cmove(r,1-sr); |
| sb--; |
| } |
| |
| this.XES = 1; |
| }, |
| |
| /** |
| * Set FP to unity |
| * |
| * @this {FP} |
| */ |
| one: function() { |
| this.f.one(); |
| this.nres(); |
| }, |
| |
| /** |
| * Normalises the components of an FP |
| * |
| * @this {FP} |
| */ |
| norm: function() { |
| return this.f.norm(); |
| }, |
| |
| /** |
| * Fast Modular multiplication of two FPs, mod Modulus |
| * |
| * @this {FP} |
| * @param b FP number, the multiplier |
| */ |
| mul: function(b) { |
| var d; |
| |
| if (this.XES * b.XES > FP.FEXCESS) { |
| this.reduce(); |
| } |
| |
| d = ctx.BIG.mul(this.f, b.f); |
| this.f.copy(FP.mod(d)); |
| this.XES = 2; |
| |
| return this; |
| }, |
| |
| /** |
| * Multiplication of an FP by a small integer |
| * |
| * @this {FP} |
| * @param s integer |
| */ |
| imul: function(c) { |
| var s = false, |
| d, n; |
| |
| if (c < 0) { |
| c = -c; |
| s = true; |
| } |
| |
| if (FP.MODTYPE == FP.PSEUDO_MERSENNE || FP.MODTYPE == FP.GENERALISED_MERSENNE) { |
| d = this.f.pxmul(c); |
| this.f.copy(FP.mod(d)); |
| this.XES = 2; |
| } else { |
| if (this.XES * c <= FP.FEXCESS) { |
| this.f.pmul(c); |
| this.XES *= c; |
| } else { |
| n = new FP(c); |
| this.mul(n); |
| } |
| } |
| |
| if (s) { |
| this.neg(); |
| this.norm(); |
| } |
| return this; |
| }, |
| |
| /** |
| * Fast Squaring of an FP |
| * |
| * @this {FP} |
| */ |
| sqr: function() { |
| var d, t; |
| |
| if (this.XES * this.XES > FP.FEXCESS) { |
| this.reduce(); |
| } |
| |
| d = ctx.BIG.sqr(this.f); |
| t = FP.mod(d); |
| this.f.copy(t); |
| this.XES = 2; |
| |
| return this; |
| }, |
| |
| /* this+=b */ |
| add: function(b) { |
| this.f.add(b.f); |
| this.XES += b.XES; |
| |
| if (this.XES > FP.FEXCESS) { |
| this.reduce(); |
| } |
| |
| return this; |
| }, |
| |
| /** |
| * negate this |
| * |
| * @this {FP} |
| * @param x FP instance to be set to one |
| */ |
| neg: function() { |
| var m = new ctx.BIG(0), |
| sb; |
| |
| m.rcopy(ctx.ROM_FIELD.Modulus); |
| |
| sb = FP.logb2(this.XES - 1); |
| |
| m.fshl(sb); |
| this.XES = (1 << sb)+1; |
| this.f.rsub(m); |
| |
| if (this.XES > FP.FEXCESS) { |
| this.reduce(); |
| } |
| |
| return this; |
| }, |
| |
| /** |
| * subtraction of two FPs |
| * |
| * @this {FP} |
| * @param x FP instance |
| */ |
| sub: function(b) { |
| var n = new FP(0); |
| |
| n.copy(b); |
| n.neg(); |
| this.add(n); |
| |
| return this; |
| }, |
| |
| rsub: function(b) { |
| var n = new FP(0); |
| |
| n.copy(this); |
| n.neg(); |
| this.copy(b); |
| this.add(n); |
| }, |
| |
| /** |
| * Divide an FP by 2 |
| * |
| * @this {FP} |
| */ |
| div2: function() { |
| var p; |
| |
| if (this.f.parity() === 0) { |
| this.f.fshr(1); |
| } else { |
| p = new ctx.BIG(0); |
| p.rcopy(ctx.ROM_FIELD.Modulus); |
| |
| this.f.add(p); |
| this.f.norm(); |
| this.f.fshr(1); |
| } |
| |
| return this; |
| }, |
| |
| // return this^(p-3)/4 or this^(p-5)/8 |
| // See https://eprint.iacr.org/2018/1038 |
| |
| /** |
| * return this^(p-3)/4 or this^(p-5)/8 |
| * |
| * @this {FP} |
| */ |
| fpow: function() { |
| var i,j,k,bw,w,c,nw,lo,m,n; |
| var xp=[]; |
| var ac=[1,2,3,6,12,15,30,60,120,240,255]; |
| // phase 1 |
| |
| xp[0]=new FP(this); // 1 |
| xp[1]=new FP(this); xp[1].sqr(); // 2 |
| xp[2]=new FP(xp[1]); xp[2].mul(this); //3 |
| xp[3]=new FP(xp[2]); xp[3].sqr(); // 6 |
| xp[4]=new FP(xp[3]); xp[4].sqr(); // 12 |
| xp[5]=new FP(xp[4]); xp[5].mul(xp[2]); // 15 |
| xp[6]=new FP(xp[5]); xp[6].sqr(); // 30 |
| xp[7]=new FP(xp[6]); xp[7].sqr(); // 60 |
| xp[8]=new FP(xp[7]); xp[8].sqr(); // 120 |
| xp[9]=new FP(xp[8]); xp[9].sqr(); // 240 |
| xp[10]=new FP(xp[9]); xp[10].mul(xp[5]); // 255 |
| |
| |
| n=FP.MODBITS; |
| if (FP.MODTYPE == FP.GENERALISED_MERSENNE) // Goldilocks ONLY |
| n/=2; |
| if (FP.MOD8==5) |
| { |
| n-=3; |
| c=(ctx.ROM_FIELD.MConst+5)/8; |
| } else { |
| n-=2; |
| c=(ctx.ROM_FIELD.MConst+3)/4; |
| } |
| |
| bw=0; w=1; while (w<c) {w*=2; bw+=1;} |
| k=w-c; |
| |
| i=10; var key=new FP(0); |
| if (k!=0) |
| { |
| while (ac[i]>k) i--; |
| key.copy(xp[i]); |
| k-=ac[i]; |
| } |
| while (k!=0) |
| { |
| i--; |
| if (ac[i]>k) continue; |
| key.mul(xp[i]); |
| k-=ac[i]; |
| } |
| |
| // phase 2 |
| xp[1].copy(xp[2]); |
| xp[2].copy(xp[5]); |
| xp[3].copy(xp[10]); |
| |
| j=3; m=8; |
| nw=n-bw; |
| var t=new FP(0); |
| while (2*m<nw) |
| { |
| t.copy(xp[j++]); |
| for (i=0;i<m;i++) |
| t.sqr(); |
| xp[j].copy(xp[j-1]); |
| xp[j].mul(t); |
| m*=2; |
| } |
| lo=nw-m; |
| var r=new FP(xp[j]); |
| |
| while (lo!=0) |
| { |
| m/=2; j--; |
| if (lo<m) continue; |
| lo-=m; |
| t.copy(r); |
| for (i=0;i<m;i++) |
| t.sqr(); |
| r.copy(t); |
| r.mul(xp[j]); |
| } |
| |
| // phase 3 |
| if (bw!=0) |
| { |
| for (i=0;i<bw;i++ ) |
| r.sqr(); |
| r.mul(key); |
| } |
| |
| if (FP.MODTYPE == FP.GENERALISED_MERSENNE) // Goldilocks ONLY |
| { |
| key.copy(r); |
| r.sqr(); |
| r.mul(this); |
| for (i=0;i<n+1;i++) |
| r.sqr(); |
| r.mul(key); |
| } |
| return r; |
| }, |
| |
| /** |
| * Inverting an FP |
| * |
| * @this {FP} |
| */ |
| inverse: function() { |
| |
| if (FP.MODTYPE == FP.PSEUDO_MERSENNE || FP.MODTYPE == FP.GENERALISED_MERSENNE) |
| { |
| var y=this.fpow(); |
| if (FP.MOD8==5) |
| { |
| var t=new FP(this); |
| t.sqr(); |
| this.mul(t); |
| y.sqr(); |
| |
| } |
| y.sqr(); |
| y.sqr(); |
| this.mul(y); |
| return this; |
| } else { |
| var m2=new ctx.BIG(0); |
| m2.rcopy(ctx.ROM_FIELD.Modulus); |
| m2.dec(2); m2.norm(); |
| this.copy(this.pow(m2)); |
| return this; |
| } |
| }, |
| |
| /** |
| * Tests for equality of two FP instances |
| * |
| * @this {FP} |
| * @param x FP instance to compare |
| */ |
| equals: function(a) { |
| var ft=new FP(0); ft.copy(this); |
| var sd=new FP(0); sd.copy(a); |
| ft.reduce(); |
| sd.reduce(); |
| |
| if (ctx.BIG.comp(ft.f, sd.f) === 0) { |
| return true; |
| } |
| |
| return false; |
| }, |
| |
| /** |
| * Raises an FP to the power of a BIG |
| * |
| * @this {FP} |
| * @param e BIG instance exponent |
| */ |
| pow: function(e) { |
| var i,w=[], |
| tb=[], |
| t=new ctx.BIG(e), |
| nb, lsbs, r; |
| this.norm(); |
| t.norm(); |
| nb= 1 + Math.floor((t.nbits() + 3) / 4); |
| |
| for (i=0;i<nb;i++) { |
| lsbs=t.lastbits(4); |
| t.dec(lsbs); |
| t.norm(); |
| w[i]=lsbs; |
| t.fshr(4); |
| } |
| tb[0]=new FP(1); |
| tb[1]=new FP(this); |
| for (i=2;i<16;i++) { |
| tb[i]=new FP(tb[i-1]); |
| tb[i].mul(this); |
| } |
| r=new FP(tb[w[nb-1]]); |
| for (i=nb-2;i>=0;i--) { |
| r.sqr(); |
| r.sqr(); |
| r.sqr(); |
| r.sqr(); |
| r.mul(tb[w[i]]); |
| } |
| r.reduce(); |
| return r; |
| }, |
| |
| /** |
| * return jacobi symbol (this/Modulus) |
| * |
| * @this {FP} |
| */ |
| jacobi: function() { |
| var p = new ctx.BIG(0), |
| w = this.redc(); |
| |
| p.rcopy(ctx.ROM_FIELD.Modulus); |
| |
| return w.jacobi(p); |
| }, |
| |
| /** |
| * Fast Modular square root of a an FP, mod Modulus |
| * |
| * @this {FP} |
| */ |
| sqrt: function() { |
| var i, v, r; |
| |
| this.reduce(); |
| if (FP.MOD8 == 5) { |
| i = new FP(0); |
| i.copy(this); |
| i.f.shl(1); |
| if (FP.MODTYPE == FP.PSEUDO_MERSENNE || FP.MODTYPE == FP.GENERALISED_MERSENNE) { |
| v=i.fpow(); |
| } else { |
| var b = new ctx.BIG(0); |
| b.rcopy(ctx.ROM_FIELD.Modulus); |
| b.dec(5); |
| b.norm(); |
| b.shr(3); |
| v = i.pow(b); |
| } |
| i.mul(v); |
| i.mul(v); |
| i.f.dec(1); |
| r = new FP(0); |
| r.copy(this); |
| r.mul(v); |
| r.mul(i); |
| r.reduce(); |
| |
| return r; |
| } else { |
| if (FP.MODTYPE == FP.PSEUDO_MERSENNE || FP.MODTYPE == FP.GENERALISED_MERSENNE) { |
| var r=this.fpow(); |
| r.mul(this); |
| return r; |
| } else { |
| var b = new ctx.BIG(0); |
| b.rcopy(ctx.ROM_FIELD.Modulus); |
| b.inc(1); |
| b.norm(); |
| b.shr(2); |
| return this.pow(b); |
| } |
| } |
| } |
| |
| }; |
| |
| FP.logb2 = function(v) { |
| var r; |
| |
| v |= v >>> 1; |
| v |= v >>> 2; |
| v |= v >>> 4; |
| v |= v >>> 8; |
| v |= v >>> 16; |
| |
| v = v - ((v >>> 1) & 0x55555555); |
| v = (v & 0x33333333) + ((v >>> 2) & 0x33333333); |
| r = ((v + (v >>> 4) & 0xF0F0F0F) * 0x1010101) >>> 24; |
| |
| return r; |
| }; |
| |
| FP.quo = function(n,m) { |
| var num,den,hb=ctx.BIG.CHUNK>>1; |
| if (FP.TBITS<hb) |
| { |
| var sh=hb-FP.TBITS; |
| num=(n.w[ctx.BIG.NLEN-1]<<sh)|(n.w[ctx.BIG.NLEN-2]>>(ctx.BIG.BASEBITS-sh)); |
| den=(m.w[ctx.BIG.NLEN-1]<<sh)|(m.w[ctx.BIG.NLEN-2]>>(ctx.BIG.BASEBITS-sh)); |
| } else { |
| num=n.w[ctx.BIG.NLEN-1]; |
| den=m.w[ctx.BIG.NLEN-1]; |
| } |
| return Math.floor(num/(den+1)) |
| }; |
| |
| /** |
| * reduce a ctx.DBIG to a ctx.BIG using a "special" modulus |
| * |
| * @this {FP} |
| */ |
| FP.mod = function(d) { |
| var b = new ctx.BIG(0), |
| i, t, v, tw, tt, lo, carry, m, dd; |
| |
| if (FP.MODTYPE == FP.PSEUDO_MERSENNE) { |
| t = d.split(FP.MODBITS); |
| b.hcopy(d); |
| |
| if (ctx.ROM_FIELD.MConst != 1) { |
| v = t.pmul(ctx.ROM_FIELD.MConst); |
| } else { |
| v = 0; |
| } |
| |
| t.add(b); |
| t.norm(); |
| |
| tw = t.w[ctx.BIG.NLEN - 1]; |
| t.w[ctx.BIG.NLEN - 1] &= FP.TMASK; |
| t.inc(ctx.ROM_FIELD.MConst * ((tw >> FP.TBITS) + (v << (ctx.BIG.BASEBITS - FP.TBITS)))); |
| // b.add(t); |
| t.norm(); |
| |
| return t; |
| } |
| |
| if (FP.MODTYPE == FP.MONTGOMERY_FRIENDLY) { |
| for (i = 0; i < ctx.BIG.NLEN; i++) { |
| d.w[ctx.BIG.NLEN + i] += d.muladd(d.w[i], ctx.ROM_FIELD.MConst - 1, d.w[i], ctx.BIG.NLEN + i - 1); |
| } |
| |
| for (i = 0; i < ctx.BIG.NLEN; i++) { |
| b.w[i] = d.w[ctx.BIG.NLEN + i]; |
| } |
| |
| b.norm(); |
| } |
| |
| if (FP.MODTYPE == FP.GENERALISED_MERSENNE) { // GoldiLocks Only |
| t = d.split(FP.MODBITS); |
| b.hcopy(d); |
| b.add(t); |
| dd = new ctx.DBIG(0); |
| dd.hcopy(t); |
| dd.shl(FP.MODBITS / 2); |
| |
| tt = dd.split(FP.MODBITS); |
| lo = new ctx.BIG(); |
| lo.hcopy(dd); |
| |
| b.add(tt); |
| b.add(lo); |
| //b.norm(); |
| tt.shl(FP.MODBITS / 2); |
| b.add(tt); |
| |
| carry = b.w[ctx.BIG.NLEN - 1] >> FP.TBITS; |
| b.w[ctx.BIG.NLEN - 1] &= FP.TMASK; |
| b.w[0] += carry; |
| |
| b.w[Math.floor(224 / ctx.BIG.BASEBITS)] += carry << (224 % ctx.BIG.BASEBITS); |
| b.norm(); |
| } |
| |
| if (FP.MODTYPE == FP.NOT_SPECIAL) { |
| m = new ctx.BIG(0); |
| m.rcopy(ctx.ROM_FIELD.Modulus); |
| |
| b.copy(ctx.BIG.monty(m, ctx.ROM_FIELD.MConst, d)); |
| } |
| |
| return b; |
| }; |
| |
| return FP; |
| }; |
| |
| if (typeof module !== "undefined" && typeof module.exports !== "undefined") { |
| module.exports = { |
| FP: FP |
| }; |
| } |
