Package org.gudy.bouncycastle.math.ec
Class Tnaf
java.lang.Object
org.gudy.bouncycastle.math.ec.Tnaf
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
FieldsModifier and TypeFieldDescriptionstatic final ZTauElement[]
Theαu
's fora=0
as an array ofZTauElement
s.static final byte[][]
Theαu
's fora=0
as an array of TNAFs.static final ZTauElement[]
Theαu
's fora=1
as an array ofZTauElement
s.static final byte[][]
Theαu
's fora=1
as an array of TNAFs.private static final BigInteger
private static final BigInteger
private static final BigInteger
static final byte
24static final byte
The window width of WTNAF. -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionstatic SimpleBigDecimal
approximateDivisionByN
(BigInteger k, BigInteger s, BigInteger vm, byte a, int m, int c) Approximate division byn
.static BigInteger[]
getLucas
(byte mu, int k, boolean doV) Calculates the Lucas Sequence elementsUk-1
andUk
orVk-1
andVk
.static byte
getMu
(ECCurve.F2m curve) Returns the parameterμ
of the elliptic curve.static ECPoint.F2m[]
getPreComp
(ECPoint.F2m p, byte a) Does the precomputation for WTNAF multiplication.static BigInteger[]
getSi
(ECCurve.F2m curve) Computes the auxiliary valuess0
ands1
used for partial modular reduction.static BigInteger
getTw
(byte mu, int w) Computes the auxiliary valuetw
.static ECPoint.F2m
multiplyFromTnaf
(ECPoint.F2m p, byte[] u) Multiplies aECPoint.F2m
by an elementλ
ofZ[τ]
using theτ
-adic NAF (TNAF) method, given the TNAF ofλ
.static ECPoint.F2m
static ECPoint.F2m
multiplyTnaf
(ECPoint.F2m p, ZTauElement lambda) static SimpleBigDecimal
norm
(byte mu, SimpleBigDecimal u, SimpleBigDecimal v) Computes the norm of an elementλ
ofR[τ]
, whereλ = u + vτ
andu
andu
are real numbers (elements ofR
).static BigInteger
norm
(byte mu, ZTauElement lambda) Computes the norm of an elementλ
ofZ[τ]
.static ZTauElement
partModReduction
(BigInteger k, int m, byte a, BigInteger[] s, byte mu, byte c) Partial modular reduction modulo(τm - 1)/(τ - 1)
.static ZTauElement
round
(SimpleBigDecimal lambda0, SimpleBigDecimal lambda1, byte mu) Rounds an elementλ
ofR[τ]
to an element ofZ[τ]
, such that their difference has minimal norm.static ECPoint.F2m
tau
(ECPoint.F2m p) Applies the operationτ()
to anECPoint.F2m
.static byte[]
tauAdicNaf
(byte mu, ZTauElement lambda) Computes theτ
-adic NAF (non-adjacent form) of an elementλ
ofZ[τ]
.static byte[]
tauAdicWNaf
(byte mu, ZTauElement lambda, byte width, BigInteger pow2w, BigInteger tw, ZTauElement[] alpha) Computes the[τ]
-adic window NAF of an elementλ
ofZ[τ]
.
-
Field Details
-
MINUS_ONE
-
MINUS_TWO
-
MINUS_THREE
-
WIDTH
public static final byte WIDTHThe 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- See Also:
-
POW_2_WIDTH
public static final byte POW_2_WIDTH24- See Also:
-
alpha0
Theαu
's fora=0
as an array ofZTauElement
s. -
alpha0Tnaf
public static final byte[][] alpha0TnafTheαu
's fora=0
as an array of TNAFs. -
alpha1
Theαu
's fora=1
as an array ofZTauElement
s. -
alpha1Tnaf
public static final byte[][] alpha1TnafTheαu
's fora=1
as an array of TNAFs.
-
-
Constructor Details
-
Tnaf
Tnaf()
-
-
Method Details
-
norm
Computes the norm of an elementλ
ofZ[τ]
.- Parameters:
mu
- The parameterμ
of the elliptic curve.lambda
- The elementλ
ofZ[τ]
.- Returns:
- The norm of
λ
.
-
norm
Computes the norm of an elementλ
ofR[τ]
, whereλ = u + vτ
andu
andu
are real numbers (elements ofR
).- Parameters:
mu
- The parameterμ
of the elliptic curve.u
- The real part of the elementλ
ofR[τ]
.v
- Theτ
-adic part of the elementλ
ofR[τ]
.- Returns:
- The norm of
λ
.
-
round
Rounds an elementλ
ofR[τ]
to an element ofZ[τ]
, such that their difference has minimal norm.λ
is given asλ = λ0 + λ1τ
.- Parameters:
lambda0
- The componentλ0
.lambda1
- The componentλ1
.mu
- The parameterμ
of the elliptic curve. Must equal 1 or -1.- Returns:
- The rounded element of
Z[τ]
. - Throws:
IllegalArgumentException
- iflambda0
andlambda1
do not have same scale.
-
approximateDivisionByN
public static SimpleBigDecimal approximateDivisionByN(BigInteger k, BigInteger s, BigInteger vm, byte a, int m, int c) Approximate division byn
. For an integerk
, the valueλ = s k / n
is computed toc
bits of accuracy.- Parameters:
k
- The parameterk
.s
- The curve parameters0
ors1
.vm
- The Lucas Sequence elementVm
.a
- The parametera
of the elliptic curve.m
- The bit length of the finite fieldFm
.c
- The number of bits of accuracy, i.e. the scale of the returnedSimpleBigDecimal
.- Returns:
- The value
λ = s k / n
computed toc
bits of accuracy.
-
tauAdicNaf
Computes theτ
-adic NAF (non-adjacent form) of an elementλ
ofZ[τ]
.- Parameters:
mu
- The parameterμ
of the elliptic curve.lambda
- The elementλ
ofZ[τ]
.- Returns:
- The
τ
-adic NAF ofλ
.
-
tau
Applies the operationτ()
to anECPoint.F2m
.- Parameters:
p
- The ECPoint.F2m to whichτ()
is applied.- Returns:
τ(p)
-
getMu
Returns the parameterμ
of the elliptic curve.- Parameters:
curve
- The elliptic curve from which to obtainμ
. The curve must be a Koblitz curve, i.e.a
equals0
or1
andb
equals1
.- Returns:
μ
of the elliptic curve.- Throws:
IllegalArgumentException
- if the given ECCurve is not a Koblitz curve.
-
getLucas
Calculates the Lucas Sequence elementsUk-1
andUk
orVk-1
andVk
.- Parameters:
mu
- The parameterμ
of the elliptic curve.k
- The index of the second element of the Lucas Sequence to be returned.doV
- If set to true, computesVk-1
andVk
, otherwiseUk-1
andUk
.- Returns:
- An array with 2 elements, containing
Uk-1
andUk
orVk-1
andVk
.
-
getTw
Computes the auxiliary valuetw
. If the width is 4, then formu = 1
,tw = 6
and formu = -1
,tw = 10
- Parameters:
mu
- The parameterμ
of the elliptic curve.w
- The window width of the WTNAF.- Returns:
- the auxiliary value
tw
-
getSi
Computes the auxiliary valuess0
ands1
used for partial modular reduction.- Parameters:
curve
- The elliptic curve for which to computes0
ands1
.- Throws:
IllegalArgumentException
- ifcurve
is not a Koblitz curve (Anomalous Binary Curve, ABC).
-
partModReduction
public static ZTauElement partModReduction(BigInteger k, int m, byte a, BigInteger[] s, byte mu, byte c) Partial modular reduction modulo(τm - 1)/(τ - 1)
.- Parameters:
k
- The integer to be reduced.m
- The bitlength of the underlying finite field.a
- The parametera
of the elliptic curve.s
- The auxiliary valuess0
ands1
.mu
- The parameter μ of the elliptic curve.c
- The precision (number of bits of accuracy) of the partial modular reduction.- Returns:
ρ := k partmod (τm - 1)/(τ - 1)
-
multiplyRTnaf
- Parameters:
p
- The ECPoint.F2m to multiply.k
- TheBigInteger
by which to multiplyp
.- Returns:
k * p
-
multiplyTnaf
- Parameters:
p
- The ECPoint.F2m to multiply.lambda
- The elementλ
ofZ[τ]
.- Returns:
λ * p
-
multiplyFromTnaf
Multiplies aECPoint.F2m
by an elementλ
ofZ[τ]
using theτ
-adic NAF (TNAF) method, given the TNAF ofλ
.- Parameters:
p
- The ECPoint.F2m to multiply.u
- The the TNAF ofλ
..- Returns:
λ * p
-
tauAdicWNaf
public static byte[] tauAdicWNaf(byte mu, ZTauElement lambda, byte width, BigInteger pow2w, BigInteger tw, ZTauElement[] alpha) Computes the[τ]
-adic window NAF of an elementλ
ofZ[τ]
.- Parameters:
mu
- The parameter μ of the elliptic curve.lambda
- The elementλ
ofZ[τ]
of which to compute the[τ]
-adic NAF.width
- The window width of the resulting WNAF.pow2w
- 2width.tw
- The auxiliary valuetw
.alpha
- Theαu
's for the window width.- Returns:
- The
[τ]
-adic window NAF ofλ
.
-
getPreComp
Does the precomputation for WTNAF multiplication.- Parameters:
p
- TheECPoint
for which to do the precomputation.a
- The parametera
of the elliptic curve.- Returns:
- The precomputation array for
p
.
-