Top Description Fields Constructors Methods
org.bouncycastle.math.ec

pack-priv Class Tnaf

extends Object
Class Inheritance
Imports
java.math.BigInteger, org.bouncycastle.util.BigIntegers
Class holding methods for point multiplication based on the window τ-adic nonadjacent form (WTNAF). The algorithms are based on the paper "Improved Algorithms for Arithmetic on Anomalous Binary Curves" by Jerome A. Solinas. The paper first appeared in the Proceedings of Crypto 1997.

Field Summary

Modifier and TypeField and Description
public static final ZTauElement[]
alpha0

The αu's for a=0 as an array of ZTauElements.

public static final byte[][]
alpha0Tnaf

The αu's for a=0 as an array of TNAFs.

public static final ZTauElement[]
alpha1

The αu's for a=1 as an array of ZTauElements.

public static final byte[][]
alpha1Tnaf

The αu's for a=1 as an array of TNAFs.

private static final BigInteger
MINUS_ONE

private static final BigInteger
MINUS_THREE

private static final BigInteger
MINUS_TWO

public static final byte
WIDTH

The window width of WTNAF.

Constructor Summary

AccessConstructor and Description
pack-priv
Tnaf()

Method Summary

Modifier and TypeMethod and Description
public static SimpleBigDecimal

Returns:

The value λ = s k / n computed to c bits of accuracy.
approximateDivisionByN(BigInteger
The parameter k.
k, BigInteger
The curve parameter s0 or s1.
s, BigInteger
The Lucas Sequence element Vm.
vm, byte
The parameter a of the elliptic curve.
a, int
The bit length of the finite field Fm.
m, int
The number of bits of accuracy, i.e. the scale of the returned SimpleBigDecimal.
c)

Approximate division by n.

public static BigInteger[]

Returns:

An array with 2 elements, containing Uk-1 and Uk or Vk-1 and Vk.
getLucas(byte
The parameter μ of the elliptic curve.
mu, int
The index of the second element of the Lucas Sequence to be returned.
k, boolean
If set to true, computes Vk-1 and Vk, otherwise Uk-1 and Uk.
doV)

Calculates the Lucas Sequence elements Uk-1 and Uk or Vk-1 and Vk.

public static byte

Returns:

μ of the elliptic curve.
getMu(ECCurve.AbstractF2m
The elliptic curve from which to obtain μ. The curve must be a Koblitz curve, i.e. a equals 0 or 1 and b equals 1.
curve)

Returns the parameter μ of the elliptic curve.

public static byte
getMu(ECFieldElement curveA)

public static byte
getMu(int curveA)

public static ECPoint.AbstractF2m[]

Returns:

The precomputation array for p.
getPreComp(ECPoint.AbstractF2m
The ECPoint for which to do the precomputation.
p, byte
The parameter a of the elliptic curve.
a)

Does the precomputation for WTNAF multiplication.

protected static int
getShiftsForCofactor(BigInteger h)

public static BigInteger[]
getSi(ECCurve.AbstractF2m
The elliptic curve for which to compute s0 and s1.
curve)

Computes the auxiliary values s0 and s1 used for partial modular reduction.

public static BigInteger[]
getSi(int fieldSize, int curveA, BigInteger cofactor)

public static BigInteger

Returns:

the auxiliary value tw
getTw(byte
The parameter μ of the elliptic curve.
mu, int
The window width of the WTNAF.
w)

Computes the auxiliary value tw.

public static ECPoint.AbstractF2m

Returns:

λ * p
multiplyFromTnaf(ECPoint.AbstractF2m
The ECPoint.AbstractF2m to multiply.
p, ECPoint.AbstractF2m pNeg, byte[]
The the TNAF of λ..
u)

Multiplies a ECPoint.AbstractF2m by an element λ of Z[τ] using the τ-adic NAF (TNAF) method, given the TNAF of λ.

public static ECPoint.AbstractF2m

Returns:

k * p
multiplyRTnaf(ECPoint.AbstractF2m
The ECPoint.AbstractF2m to multiply.
p, BigInteger
The BigInteger by which to multiply p.
k)

Multiplies a ECPoint.AbstractF2m by a BigInteger using the reduced τ-adic NAF (RTNAF) method.

public static ECPoint.AbstractF2m

Returns:

λ * p
multiplyTnaf(ECPoint.AbstractF2m
The ECPoint.AbstractF2m to multiply.
p, ZTauElement
The element λ of Z[τ].
lambda)

Multiplies a ECPoint.AbstractF2m by an element λ of Z[τ] using the τ-adic NAF (TNAF) method.

public static BigInteger

Returns:

The norm of λ.
norm(final byte
The parameter μ of the elliptic curve.
mu, ZTauElement
The element λ of Z[τ].
lambda)

Computes the norm of an element λ of Z[τ].

public static SimpleBigDecimal

Returns:

The norm of λ.
norm(final byte
The parameter μ of the elliptic curve.
mu, SimpleBigDecimal
The real part of the element λ of R[τ].
u, SimpleBigDecimal
The τ-adic part of the element λ of R[τ].
v)

Computes the norm of an element λ of R[τ], where λ = u + vτ and u and u are real numbers (elements of R).

public static ZTauElement

Returns:

ρ := k partmod (τm - 1)/(τ - 1)
partModReduction(ECCurve.AbstractF2m curve, BigInteger
The integer to be reduced.
k, byte
The parameter a of the elliptic curve.
a, byte
The parameter μ of the elliptic curve.
mu, byte
The precision (number of bits of accuracy) of the partial modular reduction.
c)

Partial modular reduction modulo (τm - 1)/(τ - 1).

public static ZTauElement

Returns:

The rounded element of Z[τ].
round(SimpleBigDecimal
The component λ0.
lambda0, SimpleBigDecimal
The component λ1.
lambda1, byte
The parameter μ of the elliptic curve. Must equal 1 or -1.
mu)

Rounds an element λ of R[τ] to an element of Z[τ], such that their difference has minimal norm.

public static ECPoint.AbstractF2m

Returns:

τ(p)
tau(ECPoint.AbstractF2m
The ECPoint.AbstractF2m to which τ() is applied.
p)

Applies the operation τ() to an ECPoint.AbstractF2m.

public static byte[]

Returns:

The τ-adic NAF of λ.
tauAdicNaf(byte
The parameter μ of the elliptic curve.
mu, ZTauElement
The element λ of Z[τ].
lambda)

Computes the τ-adic NAF (non-adjacent form) of an element λ of Z[τ].

public static byte[]

Returns:

The [τ]-adic window NAF of λ.
tauAdicWNaf(byte
The parameter μ of the elliptic curve.
mu, ZTauElement
The element λ of Z[τ] of which to compute the [τ]-adic NAF.
lambda, int
The window width of the resulting WNAF.
width, int
The auxiliary value tw.
tw, ZTauElement[]
The αu's for the window width.
alpha)

Computes the [τ]-adic window NAF of an element λ of Z[τ].

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

alpha0back to summary
public static final ZTauElement[] alpha0

The αu's for a=0 as an array of ZTauElements.

alpha0Tnafback to summary
public static final byte[][] alpha0Tnaf

The αu's for a=0 as an array of TNAFs.

alpha1back to summary
public static final ZTauElement[] alpha1

The αu's for a=1 as an array of ZTauElements.

alpha1Tnafback to summary
public static final byte[][] alpha1Tnaf

The αu's for a=1 as an array of TNAFs.

MINUS_ONEback to summary
private static final BigInteger MINUS_ONE
MINUS_THREEback to summary
private static final BigInteger MINUS_THREE
MINUS_TWOback to summary
private static final BigInteger MINUS_TWO
WIDTHback to summary
public static final byte WIDTH

The window width of WTNAF. The standard value of 4 is slightly less than optimal for running time, but keeps space requirements for precomputation low. For typical curves, a value of 5 or 6 results in a better running time. When changing this value, the αu's must be computed differently, see e.g. "Guide to Elliptic Curve Cryptography", Darrel Hankerson, Alfred Menezes, Scott Vanstone, Springer-Verlag New York Inc., 2004, p. 121-122

Constructor Detail

Tnafback to summary
pack-priv Tnaf()

Method Detail

approximateDivisionByNback to summary
public static SimpleBigDecimal approximateDivisionByN(BigInteger k, BigInteger s, BigInteger vm, byte a, int m, int c)

Approximate division by n. For an integer k, the value λ = s k / n is computed to c bits of accuracy.

Parameters
k:BigInteger

The parameter k.

s:BigInteger

The curve parameter s0 or s1.

vm:BigInteger

The Lucas Sequence element Vm.

a:byte

The parameter a of the elliptic curve.

m:int

The bit length of the finite field Fm.

c:int

The number of bits of accuracy, i.e. the scale of the returned SimpleBigDecimal.

Returns:SimpleBigDecimal

The value λ = s k / n computed to c bits of accuracy.

getLucasback to summary
public static BigInteger[] getLucas(byte mu, int k, boolean doV)

Calculates the Lucas Sequence elements Uk-1 and Uk or Vk-1 and Vk.

Parameters
mu:byte

The parameter μ of the elliptic curve.

k:int

The index of the second element of the Lucas Sequence to be returned.

doV:boolean

If set to true, computes Vk-1 and Vk, otherwise Uk-1 and Uk.

Returns:BigInteger[]

An array with 2 elements, containing Uk-1 and Uk or Vk-1 and Vk.

getMuback to summary
public static byte getMu(ECCurve.AbstractF2m curve)

Returns the parameter μ of the elliptic curve.

Parameters
curve:ECCurve.AbstractF2m

The elliptic curve from which to obtain μ. The curve must be a Koblitz curve, i.e. a equals 0 or 1 and b equals 1.

Returns:byte

μ of the elliptic curve.

Exceptions
IllegalArgumentException:
if the given ECCurve is not a Koblitz curve.
getMuback to summary
public static byte getMu(ECFieldElement curveA)
getMuback to summary
public static byte getMu(int curveA)
getPreCompback to summary
public static ECPoint.AbstractF2m[] getPreComp(ECPoint.AbstractF2m p, byte a)

Does the precomputation for WTNAF multiplication.

Parameters
p:ECPoint.AbstractF2m

The ECPoint for which to do the precomputation.

a:byte

The parameter a of the elliptic curve.

Returns:ECPoint.AbstractF2m[]

The precomputation array for p.

getShiftsForCofactorback to summary
protected static int getShiftsForCofactor(BigInteger h)
getSiback to summary
public static BigInteger[] getSi(ECCurve.AbstractF2m curve)

Computes the auxiliary values s0 and s1 used for partial modular reduction.

Parameters
curve:ECCurve.AbstractF2m

The elliptic curve for which to compute s0 and s1.

Exceptions
IllegalArgumentException:
if curve is not a Koblitz curve (Anomalous Binary Curve, ABC).
getSiback to summary
public static BigInteger[] getSi(int fieldSize, int curveA, BigInteger cofactor)
getTwback to summary
public static BigInteger getTw(byte mu, int w)

Computes the auxiliary value tw. If the width is 4, then for mu = 1, tw = 6 and for mu = -1, tw = 10

Parameters
mu:byte

The parameter μ of the elliptic curve.

w:int

The window width of the WTNAF.

Returns:BigInteger

the auxiliary value tw

multiplyFromTnafback to summary
public static ECPoint.AbstractF2m multiplyFromTnaf(ECPoint.AbstractF2m p, ECPoint.AbstractF2m pNeg, byte[] u)

Multiplies a ECPoint.AbstractF2m by an element λ of Z[τ] using the τ-adic NAF (TNAF) method, given the TNAF of λ.

Parameters
p:ECPoint.AbstractF2m

The ECPoint.AbstractF2m to multiply.

u:byte[]

The the TNAF of λ..

Returns:ECPoint.AbstractF2m

λ * p

multiplyRTnafback to summary
public static ECPoint.AbstractF2m multiplyRTnaf(ECPoint.AbstractF2m p, BigInteger k)

Multiplies a ECPoint.AbstractF2m by a BigInteger using the reduced τ-adic NAF (RTNAF) method.

Parameters
p:ECPoint.AbstractF2m

The ECPoint.AbstractF2m to multiply.

k:BigInteger

The BigInteger by which to multiply p.

Returns:ECPoint.AbstractF2m

k * p

multiplyTnafback to summary
public static ECPoint.AbstractF2m multiplyTnaf(ECPoint.AbstractF2m p, ZTauElement lambda)

Multiplies a ECPoint.AbstractF2m by an element λ of Z[τ] using the τ-adic NAF (TNAF) method.

Parameters
p:ECPoint.AbstractF2m

The ECPoint.AbstractF2m to multiply.

lambda:ZTauElement

The element λ of Z[τ].

Returns:ECPoint.AbstractF2m

λ * p

normback to summary
public static BigInteger norm(final byte mu, ZTauElement lambda)

Computes the norm of an element λ of Z[τ].

Parameters
mu:byte

The parameter μ of the elliptic curve.

lambda:ZTauElement

The element λ of Z[τ].

Returns:BigInteger

The norm of λ.

normback to summary
public static SimpleBigDecimal norm(final byte mu, SimpleBigDecimal u, SimpleBigDecimal v)

Computes the norm of an element λ of R[τ], where λ = u + vτ and u and u are real numbers (elements of R).

Parameters
mu:byte

The parameter μ of the elliptic curve.

u:SimpleBigDecimal

The real part of the element λ of R[τ].

v:SimpleBigDecimal

The τ-adic part of the element λ of R[τ].

Returns:SimpleBigDecimal

The norm of λ.

partModReductionback to summary
public static ZTauElement partModReduction(ECCurve.AbstractF2m curve, BigInteger k, byte a, byte mu, byte c)

Partial modular reduction modulo (τm - 1)/(τ - 1).

Parameters
k:BigInteger

The integer to be reduced.

a:byte

The parameter a of the elliptic curve.

mu:byte

The parameter μ of the elliptic curve.

c:byte

The precision (number of bits of accuracy) of the partial modular reduction.

Returns:ZTauElement

ρ := k partmod (τm - 1)/(τ - 1)

roundback to summary
public static ZTauElement round(SimpleBigDecimal lambda0, SimpleBigDecimal lambda1, byte mu)

Rounds an element λ of R[τ] to an element of Z[τ], such that their difference has minimal norm. λ is given as λ = λ0 + λ1τ.

Parameters
lambda0:SimpleBigDecimal

The component λ0.

lambda1:SimpleBigDecimal

The component λ1.

mu:byte

The parameter μ of the elliptic curve. Must equal 1 or -1.

Returns:ZTauElement

The rounded element of Z[τ].

Exceptions
IllegalArgumentException:
if lambda0 and lambda1 do not have same scale.
tauback to summary
public static ECPoint.AbstractF2m tau(ECPoint.AbstractF2m p)

Applies the operation τ() to an ECPoint.AbstractF2m.

Parameters
p:ECPoint.AbstractF2m

The ECPoint.AbstractF2m to which τ() is applied.

Returns:ECPoint.AbstractF2m

τ(p)

tauAdicNafback to summary
public static byte[] tauAdicNaf(byte mu, ZTauElement lambda)

Computes the τ-adic NAF (non-adjacent form) of an element λ of Z[τ].

Parameters
mu:byte

The parameter μ of the elliptic curve.

lambda:ZTauElement

The element λ of Z[τ].

Returns:byte[]

The τ-adic NAF of λ.

tauAdicWNafback to summary
public static byte[] tauAdicWNaf(byte mu, ZTauElement lambda, int width, int tw, ZTauElement[] alpha)

Computes the [τ]-adic window NAF of an element λ of Z[τ].

Parameters
mu:byte

The parameter μ of the elliptic curve.

lambda:ZTauElement

The element λ of Z[τ] of which to compute the [τ]-adic NAF.

width:int

The window width of the resulting WNAF.

tw:int

The auxiliary value tw.

alpha:ZTauElement[]

The αu's for the window width.

Returns:byte[]

The [τ]-adic window NAF of λ.