Package org.gudy.bouncycastle.math.ec
Class Tnaf
- java.lang.Object
-
- org.gudy.bouncycastle.math.ec.Tnaf
-
class Tnaf extends java.lang.Object
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
Fields Modifier and Type Field Description static ZTauElement[]
alpha0
Theαu
's fora=0
as an array ofZTauElement
s.static byte[][]
alpha0Tnaf
Theαu
's fora=0
as an array of TNAFs.static ZTauElement[]
alpha1
Theαu
's fora=1
as an array ofZTauElement
s.static byte[][]
alpha1Tnaf
Theαu
's fora=1
as an array of TNAFs.private static java.math.BigInteger
MINUS_ONE
private static java.math.BigInteger
MINUS_THREE
private static java.math.BigInteger
MINUS_TWO
static byte
POW_2_WIDTH
24static byte
WIDTH
The window width of WTNAF.
-
Constructor Summary
Constructors Constructor Description Tnaf()
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description static SimpleBigDecimal
approximateDivisionByN(java.math.BigInteger k, java.math.BigInteger s, java.math.BigInteger vm, byte a, int m, int c)
Approximate division byn
.static java.math.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 java.math.BigInteger[]
getSi(ECCurve.F2m curve)
Computes the auxiliary valuess0
ands1
used for partial modular reduction.static java.math.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
multiplyRTnaf(ECPoint.F2m p, java.math.BigInteger k)
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 java.math.BigInteger
norm(byte mu, ZTauElement lambda)
Computes the norm of an elementλ
ofZ[τ]
.static ZTauElement
partModReduction(java.math.BigInteger k, int m, byte a, java.math.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, java.math.BigInteger pow2w, java.math.BigInteger tw, ZTauElement[] alpha)
Computes the[τ]
-adic window NAF of an elementλ
ofZ[τ]
.
-
-
-
Field Detail
-
MINUS_ONE
private static final java.math.BigInteger MINUS_ONE
-
MINUS_TWO
private static final java.math.BigInteger MINUS_TWO
-
MINUS_THREE
private static final java.math.BigInteger MINUS_THREE
-
WIDTH
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- See Also:
- Constant Field Values
-
POW_2_WIDTH
public static final byte POW_2_WIDTH
24- See Also:
- Constant Field Values
-
alpha0
public static final ZTauElement[] alpha0
Theαu
's fora=0
as an array ofZTauElement
s.
-
alpha0Tnaf
public static final byte[][] alpha0Tnaf
Theαu
's fora=0
as an array of TNAFs.
-
alpha1
public static final ZTauElement[] alpha1
Theαu
's fora=1
as an array ofZTauElement
s.
-
alpha1Tnaf
public static final byte[][] alpha1Tnaf
Theαu
's fora=1
as an array of TNAFs.
-
-
Method Detail
-
norm
public static java.math.BigInteger norm(byte mu, ZTauElement lambda)
Computes the norm of an elementλ
ofZ[τ]
.- Parameters:
mu
- The parameterμ
of the elliptic curve.lambda
- The elementλ
ofZ[τ]
.- Returns:
- The norm of
λ
.
-
norm
public 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
).- 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
public static ZTauElement round(SimpleBigDecimal lambda0, SimpleBigDecimal lambda1, byte mu)
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:
java.lang.IllegalArgumentException
- iflambda0
andlambda1
do not have same scale.
-
approximateDivisionByN
public static SimpleBigDecimal approximateDivisionByN(java.math.BigInteger k, java.math.BigInteger s, java.math.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
public static byte[] tauAdicNaf(byte mu, ZTauElement lambda)
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
public static ECPoint.F2m tau(ECPoint.F2m p)
Applies the operationτ()
to anECPoint.F2m
.- Parameters:
p
- The ECPoint.F2m to whichτ()
is applied.- Returns:
τ(p)
-
getMu
public static byte getMu(ECCurve.F2m curve)
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:
java.lang.IllegalArgumentException
- if the given ECCurve is not a Koblitz curve.
-
getLucas
public static java.math.BigInteger[] getLucas(byte mu, int k, boolean doV)
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
public static java.math.BigInteger getTw(byte mu, int w)
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
public static java.math.BigInteger[] getSi(ECCurve.F2m curve)
Computes the auxiliary valuess0
ands1
used for partial modular reduction.- Parameters:
curve
- The elliptic curve for which to computes0
ands1
.- Throws:
java.lang.IllegalArgumentException
- ifcurve
is not a Koblitz curve (Anomalous Binary Curve, ABC).
-
partModReduction
public static ZTauElement partModReduction(java.math.BigInteger k, int m, byte a, java.math.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
public static ECPoint.F2m multiplyRTnaf(ECPoint.F2m p, java.math.BigInteger k)
- Parameters:
p
- The ECPoint.F2m to multiply.k
- TheBigInteger
by which to multiplyp
.- Returns:
k * p
-
multiplyTnaf
public static ECPoint.F2m multiplyTnaf(ECPoint.F2m p, ZTauElement lambda)
- Parameters:
p
- The ECPoint.F2m to multiply.lambda
- The elementλ
ofZ[τ]
.- Returns:
λ * p
-
multiplyFromTnaf
public 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λ
.- 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, java.math.BigInteger pow2w, java.math.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
public static ECPoint.F2m[] getPreComp(ECPoint.F2m p, byte a)
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
.
-
-