src/fp.js (522 lines of code) (raw):
/*
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
};
}