Arithmetic

(This page is written at a slightly higher level than the rest of the wiki.)

Underlying SJCL's ECC module are fully functional big number and elliptic curve arithmetic libraries which can implement tons of other cryptosystems from textbook RSA to elliptic curve ElGamal encryption. This page is intended to be an introduction to using the libraries and an overview of what they're capable of.

The big number library has to be enabled with the --with-bn option.

Big Numbers

The big number library in SJCL is fairly intuitive if you've ever worked with big numbers in other languages: they have to be initialized with either a javascript Number, a hexadecimal string, or another sjcl.bn object. Alternatively, you can call .toString() on a sjcl.bn object and get the number in hexadecimal.

var a = new sjcl.bn(100)
var b = new sjcl.bn("0x64")

a.toString() // 0x64

They can also work a bit like codecs in that you can call .toBits() on a sjcl.bn object and get a bit array which is compatible with the sjcl.bn.fromBits function. (The .toString() method isn't compatible with sjcl.bn.fromBits, even through the hex codec.)

Along with a few notes, the rest of the library is fairly easy to figure out from the technical documentation.

1. All methods return their output. Methods that end with an M don't copy this to a separate variable, so it will change to the value that's returned. The same function without the M ensures that this remains the same after it's called.
2. 'Normalizing' means propagating carries. You only need to call the .normalize() or .cnormalize() after doing a batch of addition or subtraction.
3. Call .trim() on a number to remove any zeroes before the first significant digit. Trimming will save space when calling .toString() or .toBits().

And as another little sanity test, here's part of a toy CRT implementation:

// Define parameters.
var p = new sjcl.bn(6307),
    q = new sjcl.bn(7919),
    N = p.mul(q)

var e = new sjcl.bn(3)

// Chinese Remainder Theorem
// Calculate d, the inverse of e mod N=pq
// by combining inverses mod p and mod q
var a = e.inverseMod(p),
    b = e.inverseMod(q)

var r = a.sub(b).normalize().mul(q.inverseMod(p)),
    d = b.add(q.mul(r)).normalize().mod(N)

console.log("Calculated d:", d.toString())

// Verify
var one  = new sjcl.bn(1),
    test = e.mulmod(d, N)

console.log("Inverses? ", test.equals(one))
// Output:
//   Calculated d: 0xfe08ba
//   Inverses?  true

Fields

The normal big number library operates in the ring of integers, so to abstract away from calling the mod method every other line, SJCL implements specific fields which look similar to normal big numbers, but instead perform field operations.

In a field, there's no need to call mod (mulmod, powermod, or inverseMod) because, as mentioned, operations are already in the field. Fields implement a new method called .inverse() which returns the multiplicative inverse of the element. They also implement .reduce() and .fullReduce()--both simply marshal the stored value back into the field in case addition or subtraction has pushed it out. The former is approximate but fast, the latter is exact but expensive.

Currently, only fields for supported elliptic curves are implemented, in addition to p127 (unknown origin), and p25519 (for Curve25519). All of them have large prime characteristic.

var a = new sjcl.bn.prime.p256(2)
a.power(5000).toString()
// Value: 0x92b7b8427b64df31da69a98bbc8660dcf282d78b409492bac1c27ba5780830ca
// Running time:  Very fast

// As opposed to:
var b = new sjcl.bn(2)
b.power(10000).toString()
// Which will freeze Node for a second.

Elliptic Curves

The simplest way to define a point on a curve is to manually specify the curve and coordinates.

P = new sjcl.ecc.point( // (curve, x, y)
    sjcl.ecc.curves.c256,
    new sjcl.bn.prime.p256("0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296"),
    new sjcl.bn.prime.p256("0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5")
) // Coordinates ARE field elements!

However, for most purposes, it's easier to express a point as a multiple of the curve's base point, or to use the curve's .fromBits() method.

P = sjcl.ecc.curves.c256.G.mult(10)

enc = P.toBits() // [ -822710933, 708483390, ...
Q = sjcl.ecc.curves.c256.fromBits(enc)

The .fromBits() function automatically verifies that the point is on the curve, but if you're creating the point manually (the first example), then you need to call .isValid(), which will return true if the point is on the curve or thrown an error.

SJCL swaps between the affine (2d) and the Jacobian (3d) coordinate system because almost universally, elliptic curve-based cryptosystems are expected to take inputs and output in the affine coordinate system, but internally computations are done on some faster coordinate system (in our case, the Jacobian one). In the above examples, affine coordinates were implicitly chosen. Affine coordinates can be converted to the Jacobian system by calling .toJac() on a point, or .toAffine() vice versa.

Elliptic curve groups have the same structure as a vector space, so the first natural thing to do would be add two points:

// P must be in Jacobian coordinates and Q must be in affine coordinates
P.add(Q) // same as Q.toJac().add(P.toAffine())

Multiplication being the next natural step, given a point P in affine coordinates, it can be multiplied by a Number or big number k (not a field element!):

P.mult(k) // Outputs affine
P.toJac().mult(k, P) // Outputs Jacobian

Multiplication on affine coordinates only requires the point and the multiplier k, but multiplication on Jacobian coordinates requires the point, the multiplier, and the point's affine conversion, meaning you can chain multiplication on affine points but not on Jacobian points. (For example, calculating k * j * G, is just G.mult(j).mult(k).)

SJCL has also implemented a few efficiency-conscious functions on Jacobian coordinates like P.doubl(), which calculates 2P faster than multiplying by 2, and .mult2(...), which calculates kP + jQ faster than 2 multiplications and 1 addition:

// P and Q must both be in affine coordinates
// Same as P.mult(2) but faster
P.toJac().doubl() // Outputs Jacobian

// Same as P.mult(k).toJac().add(Q.mult(j)) but faster
P.mult2(k, j, Q) // Outputs affine
P.toJac().mult2(k, P, j, Q) // Outputs Jacobian

More Algebra

It was mentioned in passing earlier that elliptic curve groups have the same structure as a vector space. Following that, the cyclic subgroup generated by the curve's base point is a subspace of order r, meaning the field that acts on it is Z/rZ.

The most direct application of this is inverting a private key:

var r = sjcl.ecc.curves.c256.r,
    k = sjcl.bn.random(r, 10),
    kInv = k.inverseMod(r)

var K = sjcl.ecc.curves.c256.G.mult(k),
    G = K.mult(kInv) // k^-1(kG) = (k^-1 * k)G = G