| Both lambda and beta are primitive cube roots
| of unity.
|
| That is lamba^3 == 1 mod n and beta^3 == 1 mod
| p, where n is the curve order and p is the
| field order.
|
| Futhermore, because (X^3 - 1) = (X - 1)(X^2
| + X + 1), the primitive cube roots of unity are
| roots of X^2 + X + 1.
|
| Therefore lambda^2 + lamba == -1 mod n and
| beta^2 + beta == -1 mod p.
|
| (The other primitive cube roots of unity are
| lambda^2 and beta^2 respectively.)
|
| Let l = -1/2 + isqrt(3)/2,
| the complex root of X^2 + X + 1.
|
| We can define a ring homomorphism phi : Z[l] ->
| Z_n where phi(a + bl) == a + blambda mod n.
|
| The kernel of phi is a lattice over Z[l]
| (considering Z[l] as a Z-module).
|
| This lattice is generated by a reduced basis
| {a1 + b1l, a2 + b2l} where
|
| - a1 = {0x30,0x86,0xd2,0x21,0xa7,0xd4,0x6b,0xcd,0xe8,0x6c,0x90,0xe4,0x92,0x84,0xeb,0x15}
| - b1 = -{0xe4,0x43,0x7e,0xd6,0x01,0x0e,0x88,0x28,0x6f,0x54,0x7f,0xa9,0x0a,0xbf,0xe4,0xc3}
| - a2 = {0x01,0x14,0xca,0x50,0xf7,0xa8,0xe2,0xf3,0xf6,0x57,0xc1,0x10,0x8d,0x9d,0x44,0xcf,0xd8}
| - b2 = {0x30,0x86,0xd2,0x21,0xa7,0xd4,0x6b,0xcd,0xe8,0x6c,0x90,0xe4,0x92,0x84,0xeb,0x15}
|
| “Guide to Elliptic Curve Cryptography”
| (Hankerson, Menezes, Vanstone) gives an
| algorithm (algorithm 3.74) to find k1 and k2
| given k, such that k1 + k2 * lambda == k mod n,
| and k1 and k2 are small in absolute value.
|
| The algorithm computes
| c1 = round(b2 * k / n) and
| c2 = round((-b1) * k / n), and gives
| k1 = k - (c1a1 + c2a2) and
| k2 = -(c1b1 + c2b2).
|
| Instead, we use modular arithmetic, and compute
| r2 = k2 mod n, and
| r1 = k1 mod n = (k - r2 * lambda) mod n,
| avoiding the need for the constants a1 and a2.
|
| g1, g2 are precomputed constants used to
| replace division with a rounded multiplication
| when decomposing the scalar for an
| endomorphism-based point multiplication.
|
| The possibility of using precomputed estimates
| is mentioned in “Guide to Elliptic Curve
| Cryptography” (Hankerson, Menezes, Vanstone) in
| section 3.5.
|
| The derivation is described in the paper
| “Efficient Software Implementation of
| Public-Key Cryptography on Sensor Networks
| Using the MSP430X Microcontroller” (Gouvea,
| Oliveira, Lopez), Section 4.3 (here we use
| a somewhat higher-precision estimate):
|
| d = a1b2 - b1*a2
| g1 = round(2^384 * b2/d)
| g2 = round(2^384 * (-b1)/d)
|
| (Note that d is also equal to the curve order,
| n, here because [a1,b1] and [a2,b2] can be
| found as outputs of the Extended Euclidean
| Algorithm on inputs n and lambda).
|
| The function below splits k into r1 and r2, such that
|
| - r1 + lambda * r2 == k (mod n)
| - either r1 < 2^128 or -r1 mod n < 2^128
| - either r2 < 2^128 or -r2 mod n < 2^128
|
| See proof below.