JSDoc: Namespace: li

Utility classes and functions.

Provides the core large integer arithmetic routines needed to implement multiplicative groups and elliptic curve groups over prime order fields. No additional functionality is provided. Although the main goal of this module is to be well-documented and clearly structured with proper encapsulation and without hidden assumptions, this is quite hard in a few routines.

WARNING! This module must be used with care due to the assumptions made by routines on inputs, but these assumptions are stated explicitly for each function, so the code is easy to follow.

Integers are represented as arrays of numbers constrained to WORDSIZE bits, where WORDSIZE is any even number between 4 and 30 and there are hardcoded constants derived from this when the script is generated, so do not attempt to change the wordsize in the generated code. These wordsizes are natural since JavaScript only allows bit operations on 32-bit signed integers. To see this, note that although we can do arithmetic on floating point numbers, e.g., by setting WORDSIZE = 24 we could do multiplications directly, it is expensive to recover parts of the result. Bit operations on 32-bit integers are provided in Javascript, but they are implemented on top of the native "number" datatype, i.e., numbers are cast to 32-bit signed integers, the bit operation is applied, and the result is cast back to a "number".

Using small wordsizes exposes certain types of arithmetic bugs, so providing this is not merely for educational purposes, it is also to lower the risk of structural bugs.

Functions are only implemented for unsigned integers and when called from external functions they assume that any result parameter is of a given length. All arithmetic functions guarantee that any leading unused words are set to zero.

A "limb" is an element of an array that may or may not store any single-precision integer. A word is a limb containing data, which may be zero if there are limbs at higher indices holding data. Thus, the number of limbs is the length of an array and the number of words is the index of the most significant word in the array plus one.

The workhorse routine is muladd_loop() which is generated for a given fixed wordsize. This routine determines the speed of multiplication and squaring. To a large extent it also determines the speed of division, but here div3by2() also plays an important role. These routines are generated from M4 macro code to allow using hard coded wordsize dependent constants for increased speed. The square_naive() routine also contains some generated code.

JavaScript is inherently difficult to optimize, since the JavaScript engines are moving targets, but it seems that the built-in arrays in Javascript are faster than the new typed arrays if they are handled properly. A first version of the library was based on Uint32Array for which, e.g., allocation of a fixed-size array is slower than a builtin array.

One notable observation is that it sometimes makes sense to inform the interpreter that a JavaScript "number" / float is really a 32-bit integer by saying, e.g., (x | 0) even if we are guaranteed that x is a 32-bit integer. This is important when accessing elements from arrays and it seems to prevent the interpreter from converting to and from floats.

We avoid dynamic memory allocation almost entirely by keeping scratch space as static variables of the functions. This is implemented using immediate function evaluation in JavaScript, but it is encapsulated to reduce complexity, i.e., calling functions remain unaware of this. This approach works well in our applications, since higher level routines work with integers of fixed bit length;

Handbook of Cryptography (HAC), Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone gives a straightforward introduction to the basic algorithms used and we try to follow their notation for easy reference. Division exploits the techniques of Improved division by invariant integers, Niels Moller and Torbjorn Granlund (MG). This is needed to implement div3by2() efficiently.

Reference	Operation	Comment
HAC 14.7.	Addition
HAC 14.9.	Subtraction
HAC 14.12.	Multiplication	Uses Karatsuba.
HAC 14.16.	Squaring	Uses Karatsuba.
HAC 14.20 and MG.	Division.	Uses reciprocals for invariant moduli.
HAC 14.83.	Modular exponentiation	Left-to-right k-ary.

Source:

vjsc-1.1.1.js, line 994

Methods

(static) add(w, x, y)

Sets w = x + y.

ASSUMES: x and y are positive and have B and B' bits and w can store (B + B' + 1) bits. A natural choice in general is to let w have (L + L' + 1) limbs if x and y have L and L' limbs, but the number of limbs can be arbitrary.

References: HAC 14.7.

Parameters:

Name	Type	Description
`w`		Array holding the result.
`x`		Left term.
`y`		Right term.

Source:

vjsc-1.1.1.js, line 1545

(static) cmp(x, x)

Returns -1, 0, or 1 depending on if x < y, x == y, or x > y.

ASSUMES: x and y are positive.

Parameters:

Name	Type	Description
`x`		Left array.
`x`		Right array.

Source:

vjsc-1.1.1.js, line 1389

Returns:

Sign of comparison relation.

(static) copyarray(x, len)

Returns a copy of the given array.

Parameters:

Name	Type	Description
`x`		Original array.
`len`		Maximal length of copy.

Source:

vjsc-1.1.1.js, line 1185

Returns:

Copy of original array.

(static) div3by2(r, u, d, neg_d, v)

Computes q and r such that u = q * d + r, where d has two limbs/words, d has three limbs/words, and 0 <= r < d.

ASSUMES: most significant bit of d is set, i.e., we have 2^(2 * 28)/2 <= d < 2^(2*28).

References: Algorithm DIV3BY2 in MG.

Parameters:

Name	Type	Description
`r`		Two-word integer that ends up holding the remainder.
`u`		Three-word dividend.
`d`		Normalized divisor.
`neg_d`		Negative of d in two's complement.
`v`		3by2 reciprocal of d.

Source:

vjsc-1.1.1.js, line 2520

Returns:

Integer quotient q = u / d.

(static) div_qr(q, x, y)

Sets q and r such that x = qy + r, except that r is computed in place of x, so at the end of the execution x is identified with r. WARNING! y is cached in its normalized form along with its negation and reciprocal. This is pointer based, i.e., it is assumed that the contents of y do not change. High level routines must accomodate.

ASSUMES: x and y are positive, x has L words and at least L + 2 limbs (i.e., two leading unused zero words), y has L' limbs, and q has at least L'' = max{L - L', 0} + 1 limbs and will finally hold a result with at most L'' words and a leading zero limb.

References: HAC 14.20.

Parameters:

Name	Type	Description
`q`		Holder of quotient.
`x`		Divident and holder of remainder at end of computation.
`y`		Divisor.

Source:

vjsc-1.1.1.js, line 2611

(static) getbit(x, index)

Returns 1 or 0 depending on if the given bit is set or not. Accessing a bit outside the number of limbs returns zero.

Parameters:

Name	Type	Description
`x`		Array containing bit.
`index`		Index of bit.

Source:

vjsc-1.1.1.js, line 1349

Returns:

Bit as a "number" at the given position.

(static) getuh(uh, x, i, wordsize)

Extracts the ith block of wordsize bits w from x (padding with zeros from the left) and sets uh such that: w = uh[0] * 2^uh[1], with uh[0] odd and with uh[0] = uh[1] = 0 when w = 0.

Parameters:

Name	Type	Description
`uh`		Holds the representation of word.
`x`		Contains bits.
`i`		Index of block of bits.
`wordsize`		Number of bits in each block.

Source:

vjsc-1.1.1.js, line 2917

(static) hex(x)

Returns a hexadecimal representation of this input array by content, i.e., unused bits of each limb are dropped before conversion

Parameters:

Name	Type	Description
`x`		Array of words.

Source:

vjsc-1.1.1.js, line 3270

Returns:

Hexadecimal string representation of the array.

(static) iszero(x)

Checks if the input represents the zero integer.

Parameters:

Name	Type	Description
`x`		Array to inspect.

Source:

vjsc-1.1.1.js, line 1373

Returns:

True or false depending on if x represents zero or not.

(static) karatsuba_split(l, h, x)

Splits x into two parts l and h of equal and predetermined size, i.e., the lengths of the lists l and h determines how x is split.

Parameters:

Name	Type	Description
`l`		Array holding most significant words of x.
`h`		Array holding most significant words of x.
`x`		Original array.

Source:

vjsc-1.1.1.js, line 1942

(static) lsbit(Array)

Returns the lowest index of a set bit in the input or zero if the input is zero.

Parameters:

Name	Type	Description
`Array`		containing bit.

Source:

vjsc-1.1.1.js, line 1304

Returns:

An index i such that 0 <= i < x.length * 28.

(static) modpow(w, b, e, m)

Sets w = b^e mod m.

ASSUMES: b >= 0, e >= 0, and m > 1, and w, b and m have L limbs.

References: HAC 14.83.

Parameters:

Name	Type	Description
`w`		Array holding the result.
`b`		Basis integer.
`e`		Exponent.
`m`		Modulus.

Source:

vjsc-1.1.1.js, line 2950

(static) modpow_naive(w, b, e, m)

Sets w = b^e mod m.

ASSUMES: b >= 0, e >= 0, and m > 1, and w, b and m have L limbs.

References: HAC 14.82.

Parameters:

Name	Type	Description
`w`		Array holding the result.
`b`		Basis integer.
`e`		Exponent.
`m`		Modulus.

Source:

vjsc-1.1.1.js, line 2846

(static) msbit(x)

Returns the index of the most significant bit in x.

Parameters:

Name	Type	Description
`x`		Array containing bit.

Source:

vjsc-1.1.1.js, line 1273

Returns:

An index i such that 0 <= i < x.length * 28.

(static) msword(x)

Returns the array index of the most significant word.

Parameters:

Name	Type	Description
`x`		Array containing word.

Source:

vjsc-1.1.1.js, line 1333

Returns:

An index i such that 0 <= i < x.length.

(static) mul(w, x, y, len)

Sets w = x * y.

ASSUMES: x and y are both non-negative with L and L' limbs respectively, and that w has at least L + L' limbs.

Parameters:

Name	Type	Description
`w`		Array holding the result.
`x`		Left factor.
`y`		Right factor.
`len`		Actual lengths of inputs. Useful when stored in longer arrays.

Source:

vjsc-1.1.1.js, line 2334

(static) mul_karatsuba(w, x, y, depth, len)

Sets w = x * y. The depth parameter determines the recursive depth of function calls and must be less than 3.

ASSUMES: x and y are both non-negative, with L and L' limbs respectively, and that w has at least L + L' limbs.

References: HAC 14.2, https://en.wikipedia.org/wiki/Karatsuba_algorithm

Parameters:

Name	Type	Description
`w`		Array holding the result.
`x`		Left factor.
`y`		Right factor.
`depth`		Recursion depth of the Karatsuba algorithm.
`len`		Actual lengths of inputs. Useful when stored in longer arrays.

Source:

vjsc-1.1.1.js, line 2194

(static) mul_naive(w, x, y)

Sets w = x * y.

ASSUMES: x and y are both non-negative with L and L' limbs respectively, and that w has at least L + L' limbs.

References: HAC 14.12.

Parameters:

Name	Type	Description
`w`		Array holding the result.
`x`		Left factor.
`y`		Right factor.

Source:

vjsc-1.1.1.js, line 2165

(static) muladd_loop(w, x, start, end, Y, i, c)

Specialized implementation of muladd_loop() for 28-bit words. This is essentially a naive double-precision multiplication computation done in a loop. This code is quite sensitive to replacing the constants with variables, which explains why it is generated from source with macros. Using two's complement for temporary values this can be used as a "mulsub_loop" as well.

Computes (pseudo-code) that due to limited precision and 32-bit bound bit operations does not work in JavaScript:

for (var j = start; j < end; j++) {
    tmp = x[j] * Y + w[i + j] + c;
    w[i + j] = tmp & 0xfffffff;
    c = tmp >>> 28;
}
return c;

Note that if Y < 2^(28 + 1), then the output carry c is only guaranteed to be smaller than 2^(28 + 1), which does not fit into a word.

ASSUMES: Y < 2^(28 + 1).

Parameters:

Name	Type	Description
`w`		Array holding additive terms as input and the output.
`x`		Array to be scaled.
`start`		Start index into x.
`end`		End index into x.
`Y`		Scalar.
`i`		Index into w.
`c`		Input carry.

Source:

vjsc-1.1.1.js, line 1717

Returns:

Finally carry.

(static) neg(w, x)

Sets w to the negative of x in two's complement representation using L * 28 bits, where L is the number of limbs in w.

ASSUMES: w has at least as many limbs as x.

Parameters:

Name	Type	Description
`w`		Array holding the result.
`x`		Integer.

Source:

vjsc-1.1.1.js, line 1610

(static) newarray(len)

Allocates new array of the given length where all elements are zero.

Parameters:

Name	Type	Description
`len`		Length of array.

Source:

vjsc-1.1.1.js, line 1170

Returns:

Array of the given length where all elements are zero.

(static) normalize(x, mask_top)

Truncates the input to the shortest possible array that represents the same absolute value in two's complement, i.e., there is always a leading zero bit.

Parameters:

Name	Type	Description
`x`		Array to truncate.
`mask_top`		Mask for a given wordsize with only most significant bit set.

Source:

vjsc-1.1.1.js, line 1220

(static) reciprocal_word(d)

Computes the 2-by-1 reciprocal of a word d.

ASSUMES: most significant bit of d is set, i.e., we have 2^28/2 <= d < 2^28.

References: Functionally equivalent to RECIPROCAL_WORD in MG.

Parameters:

Name	Type	Description
`d`		Normalized divisor.

Source:

vjsc-1.1.1.js, line 2370

Returns:

2-by-1 reciprocal of d.

(static) reciprocal_word_3by2(d)

Computes the 3-by-2 reciprocal of d, where d has two limbs/words.

ASSUMES: most significant bit of d is set, i.e., we have 2^(2 * 28)/2 <= d < 2^(2*28).

References: Algorithm RECIPROCAL_WORD_3BY2 in MG.

Parameters:

Name	Type	Description
`d`		Normalized divisor.

Source:

vjsc-1.1.1.js, line 2455

Returns:

3-by-2 reciprocal of d.

(static) resize(x, len)

Resizes the array to the given number of limbs, either by truncating or by adding leading zero words.

Parameters:

Name	Type	Description
`x`		Original array.
`len`		New length.

Source:

vjsc-1.1.1.js, line 1202

(static) set(w, x)

Sets w = x and truncates or pads with zeros as needed depending on the number of limbs in w. The x parameter can be an array or a "number" < 2^28.

Parameters:

Name	Type	Description
`w`		Array or "number" holding result.
`x`		Array holding value.

Source:

vjsc-1.1.1.js, line 1144

(static) setone(x)

Sets x = 1.

Parameters:

Name	Type	Description
`x`		Array to modify.

Source:

vjsc-1.1.1.js, line 1262

(static) setzero(x)

Sets x = 0.

Parameters:

Name	Type	Description
`x`		Array to modify.

Source:

vjsc-1.1.1.js, line 1132

(static) shiftleft(x, offset)

Shifts the given number of bits within the array, i.e., the allocated space is not expanded.

ASSUMES: offset >= 0.

Parameters:

Name	Type	Description
`x`		Array to be shifted.
`offset`		Number of bit positions to shift.

Source:

vjsc-1.1.1.js, line 1435

(static) shiftright(x, offset)

Shifts the given number of bits to the right within the allocated space, i.e., the space is not reduced.

ASSUMES: offset >= 0.

Parameters:

Name	Type	Description
`x`		Array to be shifted.
`offset`		Number of bit positions to shift.

Source:

vjsc-1.1.1.js, line 1490

(static) square(w, x, len)

Sets w = x * x.

ASSUMES: x is non-negative with L and L' limbs respectively, and that w has at least L + L' limbs.

References: HAC 14.16.

Parameters:

Name	Type	Description
`w`		Array holding the result.
`x`		Factor.
`len`		Actual lengths of inputs. Useful when stored in longer arrays.

Source:

vjsc-1.1.1.js, line 2136

(static) square_karatsuba(w, x, depth)

Sets w = x * x. The depth parameter determines the recursive depth of function calls and must be less than 3.

ASSUMES: x is non-negative and has L limbs and w has at least 2 * L limbs.

References: HAC 14.2, https://en.wikipedia.org/wiki/Karatsuba_algorithm

Parameters:

Name	Type	Description
`w`		Array holding the result.
`x`		Factor.
`depth`		Recursion depth of the Karatsuba algorithm.

Source:

vjsc-1.1.1.js, line 1977

(static) square_naive(w, x)

Sets w = x * x.

ASSUMES: x is non-negative with L and L' limbs respectively, and that w has at least L + L' limbs.

References: HAC 14.16.

Parameters:

Name	Type	Description
`w`		Array holding the result.
`x`		Factor.

Source:

vjsc-1.1.1.js, line 1876

(static) sub(w, x, y)

Sets w = x - y if x >= y and otherwise it simply propagates -1, i.e., 0xfffffff, through the remaining words of w.

ASSUMES: for normal use x >= y, and x and y have B and B' bits and w can store B bits. A natural choice is to use L >= L' limbs for x and y respectively and L limbs for w, but the number of limbs can be arbitrary.

References: HAC 14.9.

Parameters:

Name	Type	Description
`w`		Array holding the result.
`x`		Left term.
`y`		Right term.

Source:

vjsc-1.1.1.js, line 1647

Returns:

Finally carry.

(static) word_mul(w, x, y)

Sets w = x * y, where w has two limbs and x and y are words. This is specialized similarly to muladd_loop and generated using the same macro.

Parameters:

Name	Type	Description
`w`		Destination long.
`x`		Single word factor.
`y`		Single word factor.

Source:

vjsc-1.1.1.js, line 1813