• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 package org.bouncycastle.math.ec;
2 
3 import java.math.BigInteger;
4 
5 /**
6  * Class implementing the WTNAF (Window
7  * <code>&tau;</code>-adic Non-Adjacent Form) algorithm.
8  */
9 public class WTauNafMultiplier extends AbstractECMultiplier
10 {
11     // TODO Create WTauNafUtil class and move various functionality into it
12     static final String PRECOMP_NAME = "bc_wtnaf";
13 
14     /**
15      * Multiplies a {@link org.bouncycastle.math.ec.ECPoint.AbstractF2m ECPoint.AbstractF2m}
16      * by <code>k</code> using the reduced <code>&tau;</code>-adic NAF (RTNAF)
17      * method.
18      * @param point The ECPoint.AbstractF2m to multiply.
19      * @param k The integer by which to multiply <code>k</code>.
20      * @return <code>p</code> multiplied by <code>k</code>.
21      */
multiplyPositive(ECPoint point, BigInteger k)22     protected ECPoint multiplyPositive(ECPoint point, BigInteger k)
23     {
24         if (!(point instanceof ECPoint.AbstractF2m))
25         {
26             throw new IllegalArgumentException("Only ECPoint.AbstractF2m can be " +
27                     "used in WTauNafMultiplier");
28         }
29 
30         ECPoint.AbstractF2m p = (ECPoint.AbstractF2m)point;
31         ECCurve.AbstractF2m curve = (ECCurve.AbstractF2m)p.getCurve();
32         int m = curve.getFieldSize();
33         byte a = curve.getA().toBigInteger().byteValue();
34         byte mu = Tnaf.getMu(a);
35         BigInteger[] s = curve.getSi();
36 
37         ZTauElement rho = Tnaf.partModReduction(k, m, a, s, mu, (byte)10);
38 
39         return multiplyWTnaf(p, rho, curve.getPreCompInfo(p, PRECOMP_NAME), a, mu);
40     }
41 
42     /**
43      * Multiplies a {@link org.bouncycastle.math.ec.ECPoint.AbstractF2m ECPoint.AbstractF2m}
44      * by an element <code>&lambda;</code> of <code><b>Z</b>[&tau;]</code> using
45      * the <code>&tau;</code>-adic NAF (TNAF) method.
46      * @param p The ECPoint.AbstractF2m to multiply.
47      * @param lambda The element <code>&lambda;</code> of
48      * <code><b>Z</b>[&tau;]</code> of which to compute the
49      * <code>[&tau;]</code>-adic NAF.
50      * @return <code>p</code> multiplied by <code>&lambda;</code>.
51      */
multiplyWTnaf(ECPoint.AbstractF2m p, ZTauElement lambda, PreCompInfo preCompInfo, byte a, byte mu)52     private ECPoint.AbstractF2m multiplyWTnaf(ECPoint.AbstractF2m p, ZTauElement lambda,
53             PreCompInfo preCompInfo, byte a, byte mu)
54     {
55         ZTauElement[] alpha = (a == 0) ? Tnaf.alpha0 : Tnaf.alpha1;
56 
57         BigInteger tw = Tnaf.getTw(mu, Tnaf.WIDTH);
58 
59         byte[]u = Tnaf.tauAdicWNaf(mu, lambda, Tnaf.WIDTH,
60             BigInteger.valueOf(Tnaf.POW_2_WIDTH), tw, alpha);
61 
62         return multiplyFromWTnaf(p, u, preCompInfo);
63     }
64 
65     /**
66      * Multiplies a {@link org.bouncycastle.math.ec.ECPoint.AbstractF2m ECPoint.AbstractF2m}
67      * by an element <code>&lambda;</code> of <code><b>Z</b>[&tau;]</code>
68      * using the window <code>&tau;</code>-adic NAF (TNAF) method, given the
69      * WTNAF of <code>&lambda;</code>.
70      * @param p The ECPoint.AbstractF2m to multiply.
71      * @param u The the WTNAF of <code>&lambda;</code>..
72      * @return <code>&lambda; * p</code>
73      */
multiplyFromWTnaf(ECPoint.AbstractF2m p, byte[] u, PreCompInfo preCompInfo)74     private static ECPoint.AbstractF2m multiplyFromWTnaf(ECPoint.AbstractF2m p, byte[] u, PreCompInfo preCompInfo)
75     {
76         ECCurve.AbstractF2m curve = (ECCurve.AbstractF2m)p.getCurve();
77         byte a = curve.getA().toBigInteger().byteValue();
78 
79         ECPoint.AbstractF2m[] pu;
80         if ((preCompInfo == null) || !(preCompInfo instanceof WTauNafPreCompInfo))
81         {
82             pu = Tnaf.getPreComp(p, a);
83 
84             WTauNafPreCompInfo pre = new WTauNafPreCompInfo();
85             pre.setPreComp(pu);
86             curve.setPreCompInfo(p, PRECOMP_NAME, pre);
87         }
88         else
89         {
90             pu = ((WTauNafPreCompInfo)preCompInfo).getPreComp();
91         }
92 
93         // TODO Include negations in precomp (optionally) and use from here
94         ECPoint.AbstractF2m[] puNeg = new ECPoint.AbstractF2m[pu.length];
95         for (int i = 0; i < pu.length; ++i)
96         {
97             puNeg[i] = (ECPoint.AbstractF2m)pu[i].negate();
98         }
99 
100 
101         // q = infinity
102         ECPoint.AbstractF2m q = (ECPoint.AbstractF2m) p.getCurve().getInfinity();
103 
104         int tauCount = 0;
105         for (int i = u.length - 1; i >= 0; i--)
106         {
107             ++tauCount;
108             int ui = u[i];
109             if (ui != 0)
110             {
111                 q = q.tauPow(tauCount);
112                 tauCount = 0;
113 
114                 ECPoint x = ui > 0 ? pu[ui >>> 1] : puNeg[(-ui) >>> 1];
115                 q = (ECPoint.AbstractF2m)q.add(x);
116             }
117         }
118         if (tauCount > 0)
119         {
120             q = q.tauPow(tauCount);
121         }
122         return q;
123     }
124 }
125