001: package org.bouncycastle.math.ec;
002:
003: import java.math.BigInteger;
004:
005: /**
006: * Class holding methods for point multiplication based on the window
007: * τ-adic nonadjacent form (WTNAF). The algorithms are based on the
008: * paper "Improved Algorithms for Arithmetic on Anomalous Binary Curves"
009: * by Jerome A. Solinas. The paper first appeared in the Proceedings of
010: * Crypto 1997.
011: */
012: class Tnaf {
013: private static final BigInteger MINUS_ONE = ECConstants.ONE
014: .negate();
015: private static final BigInteger MINUS_TWO = ECConstants.TWO
016: .negate();
017: private static final BigInteger MINUS_THREE = ECConstants.THREE
018: .negate();
019:
020: /**
021: * The window width of WTNAF. The standard value of 4 is slightly less
022: * than optimal for running time, but keeps space requirements for
023: * precomputation low. For typical curves, a value of 5 or 6 results in
024: * a better running time. When changing this value, the
025: * <code>α<sub>u</sub></code>'s must be computed differently, see
026: * e.g. "Guide to Elliptic Curve Cryptography", Darrel Hankerson,
027: * Alfred Menezes, Scott Vanstone, Springer-Verlag New York Inc., 2004,
028: * p. 121-122
029: */
030: public static final byte WIDTH = 4;
031:
032: /**
033: * 2<sup>4</sup>
034: */
035: public static final byte POW_2_WIDTH = 16;
036:
037: /**
038: * The <code>α<sub>u</sub></code>'s for <code>a=0</code> as an array
039: * of <code>ZTauElement</code>s.
040: */
041: public static final ZTauElement[] alpha0 = { null,
042: new ZTauElement(ECConstants.ONE, ECConstants.ZERO), null,
043: new ZTauElement(MINUS_THREE, MINUS_ONE), null,
044: new ZTauElement(MINUS_ONE, MINUS_ONE), null,
045: new ZTauElement(ECConstants.ONE, MINUS_ONE), null };
046:
047: /**
048: * The <code>α<sub>u</sub></code>'s for <code>a=0</code> as an array
049: * of TNAFs.
050: */
051: public static final byte[][] alpha0Tnaf = { null, { 1 }, null,
052: { -1, 0, 1 }, null, { 1, 0, 1 }, null, { -1, 0, 0, 1 } };
053:
054: /**
055: * The <code>α<sub>u</sub></code>'s for <code>a=1</code> as an array
056: * of <code>ZTauElement</code>s.
057: */
058: public static final ZTauElement[] alpha1 = { null,
059: new ZTauElement(ECConstants.ONE, ECConstants.ZERO), null,
060: new ZTauElement(MINUS_THREE, ECConstants.ONE), null,
061: new ZTauElement(MINUS_ONE, ECConstants.ONE), null,
062: new ZTauElement(ECConstants.ONE, ECConstants.ONE), null };
063:
064: /**
065: * The <code>α<sub>u</sub></code>'s for <code>a=1</code> as an array
066: * of TNAFs.
067: */
068: public static final byte[][] alpha1Tnaf = { null, { 1 }, null,
069: { -1, 0, 1 }, null, { 1, 0, 1 }, null, { -1, 0, 0, -1 } };
070:
071: /**
072: * Computes the norm of an element <code>λ</code> of
073: * <code><b>Z</b>[τ]</code>.
074: * @param mu The parameter <code>μ</code> of the elliptic curve.
075: * @param lambda The element <code>λ</code> of
076: * <code><b>Z</b>[τ]</code>.
077: * @return The norm of <code>λ</code>.
078: */
079: public static BigInteger norm(final byte mu, ZTauElement lambda) {
080: BigInteger norm;
081:
082: // s1 = u^2
083: BigInteger s1 = lambda.u.multiply(lambda.u);
084:
085: // s2 = u * v
086: BigInteger s2 = lambda.u.multiply(lambda.v);
087:
088: // s3 = 2 * v^2
089: BigInteger s3 = lambda.v.multiply(lambda.v).shiftLeft(1);
090:
091: if (mu == 1) {
092: norm = s1.add(s2).add(s3);
093: } else if (mu == -1) {
094: norm = s1.subtract(s2).add(s3);
095: } else {
096: throw new IllegalArgumentException("mu must be 1 or -1");
097: }
098:
099: return norm;
100: }
101:
102: /**
103: * Computes the norm of an element <code>λ</code> of
104: * <code><b>R</b>[τ]</code>, where <code>λ = u + vτ</code>
105: * and <code>u</code> and <code>u</code> are real numbers (elements of
106: * <code><b>R</b></code>).
107: * @param mu The parameter <code>μ</code> of the elliptic curve.
108: * @param u The real part of the element <code>λ</code> of
109: * <code><b>R</b>[τ]</code>.
110: * @param v The <code>τ</code>-adic part of the element
111: * <code>λ</code> of <code><b>R</b>[τ]</code>.
112: * @return The norm of <code>λ</code>.
113: */
114: public static SimpleBigDecimal norm(final byte mu,
115: SimpleBigDecimal u, SimpleBigDecimal v) {
116: SimpleBigDecimal norm;
117:
118: // s1 = u^2
119: SimpleBigDecimal s1 = u.multiply(u);
120:
121: // s2 = u * v
122: SimpleBigDecimal s2 = u.multiply(v);
123:
124: // s3 = 2 * v^2
125: SimpleBigDecimal s3 = v.multiply(v).shiftLeft(1);
126:
127: if (mu == 1) {
128: norm = s1.add(s2).add(s3);
129: } else if (mu == -1) {
130: norm = s1.subtract(s2).add(s3);
131: } else {
132: throw new IllegalArgumentException("mu must be 1 or -1");
133: }
134:
135: return norm;
136: }
137:
138: /**
139: * Rounds an element <code>λ</code> of <code><b>R</b>[τ]</code>
140: * to an element of <code><b>Z</b>[τ]</code>, such that their difference
141: * has minimal norm. <code>λ</code> is given as
142: * <code>λ = λ<sub>0</sub> + λ<sub>1</sub>τ</code>.
143: * @param lambda0 The component <code>λ<sub>0</sub></code>.
144: * @param lambda1 The component <code>λ<sub>1</sub></code>.
145: * @param mu The parameter <code>μ</code> of the elliptic curve. Must
146: * equal 1 or -1.
147: * @return The rounded element of <code><b>Z</b>[τ]</code>.
148: * @throws IllegalArgumentException if <code>lambda0</code> and
149: * <code>lambda1</code> do not have same scale.
150: */
151: public static ZTauElement round(SimpleBigDecimal lambda0,
152: SimpleBigDecimal lambda1, byte mu) {
153: int scale = lambda0.getScale();
154: if (lambda1.getScale() != scale) {
155: throw new IllegalArgumentException(
156: "lambda0 and lambda1 do not " + "have same scale");
157: }
158:
159: if (!((mu == 1) || (mu == -1))) {
160: throw new IllegalArgumentException("mu must be 1 or -1");
161: }
162:
163: BigInteger f0 = lambda0.round();
164: BigInteger f1 = lambda1.round();
165:
166: SimpleBigDecimal eta0 = lambda0.subtract(f0);
167: SimpleBigDecimal eta1 = lambda1.subtract(f1);
168:
169: // eta = 2*eta0 + mu*eta1
170: SimpleBigDecimal eta = eta0.add(eta0);
171: if (mu == 1) {
172: eta = eta.add(eta1);
173: } else {
174: // mu == -1
175: eta = eta.subtract(eta1);
176: }
177:
178: // check1 = eta0 - 3*mu*eta1
179: // check2 = eta0 + 4*mu*eta1
180: SimpleBigDecimal threeEta1 = eta1.add(eta1).add(eta1);
181: SimpleBigDecimal fourEta1 = threeEta1.add(eta1);
182: SimpleBigDecimal check1;
183: SimpleBigDecimal check2;
184: if (mu == 1) {
185: check1 = eta0.subtract(threeEta1);
186: check2 = eta0.add(fourEta1);
187: } else {
188: // mu == -1
189: check1 = eta0.add(threeEta1);
190: check2 = eta0.subtract(fourEta1);
191: }
192:
193: byte h0 = 0;
194: byte h1 = 0;
195:
196: // if eta >= 1
197: if (eta.compareTo(ECConstants.ONE) >= 0) {
198: if (check1.compareTo(MINUS_ONE) < 0) {
199: h1 = mu;
200: } else {
201: h0 = 1;
202: }
203: } else {
204: // eta < 1
205: if (check2.compareTo(ECConstants.TWO) >= 0) {
206: h1 = mu;
207: }
208: }
209:
210: // if eta < -1
211: if (eta.compareTo(MINUS_ONE) < 0) {
212: if (check1.compareTo(ECConstants.ONE) >= 0) {
213: h1 = (byte) -mu;
214: } else {
215: h0 = -1;
216: }
217: } else {
218: // eta >= -1
219: if (check2.compareTo(MINUS_TWO) < 0) {
220: h1 = (byte) -mu;
221: }
222: }
223:
224: BigInteger q0 = f0.add(BigInteger.valueOf(h0));
225: BigInteger q1 = f1.add(BigInteger.valueOf(h1));
226: return new ZTauElement(q0, q1);
227: }
228:
229: /**
230: * Approximate division by <code>n</code>. For an integer
231: * <code>k</code>, the value <code>λ = s k / n</code> is
232: * computed to <code>c</code> bits of accuracy.
233: * @param k The parameter <code>k</code>.
234: * @param s The curve parameter <code>s<sub>0</sub></code> or
235: * <code>s<sub>1</sub></code>.
236: * @param vm The Lucas Sequence element <code>V<sub>m</sub></code>.
237: * @param a The parameter <code>a</code> of the elliptic curve.
238: * @param m The bit length of the finite field
239: * <code><b>F</b><sub>m</sub></code>.
240: * @param c The number of bits of accuracy, i.e. the scale of the returned
241: * <code>SimpleBigDecimal</code>.
242: * @return The value <code>λ = s k / n</code> computed to
243: * <code>c</code> bits of accuracy.
244: */
245: public static SimpleBigDecimal approximateDivisionByN(BigInteger k,
246: BigInteger s, BigInteger vm, byte a, int m, int c) {
247: int _k = (m + 5) / 2 + c;
248: BigInteger ns = k.shiftRight(m - _k - 2 + a);
249:
250: BigInteger gs = s.multiply(ns);
251:
252: BigInteger hs = gs.shiftRight(m);
253:
254: BigInteger js = vm.multiply(hs);
255:
256: BigInteger gsPlusJs = gs.add(js);
257: BigInteger ls = gsPlusJs.shiftRight(_k - c);
258: if (gsPlusJs.testBit(_k - c - 1)) {
259: // round up
260: ls = ls.add(ECConstants.ONE);
261: }
262:
263: return new SimpleBigDecimal(ls, c);
264: }
265:
266: /**
267: * Computes the <code>τ</code>-adic NAF (non-adjacent form) of an
268: * element <code>λ</code> of <code><b>Z</b>[τ]</code>.
269: * @param mu The parameter <code>μ</code> of the elliptic curve.
270: * @param lambda The element <code>λ</code> of
271: * <code><b>Z</b>[τ]</code>.
272: * @return The <code>τ</code>-adic NAF of <code>λ</code>.
273: */
274: public static byte[] tauAdicNaf(byte mu, ZTauElement lambda) {
275: if (!((mu == 1) || (mu == -1))) {
276: throw new IllegalArgumentException("mu must be 1 or -1");
277: }
278:
279: BigInteger norm = norm(mu, lambda);
280:
281: // Ceiling of log2 of the norm
282: int log2Norm = norm.bitLength();
283:
284: // If length(TNAF) > 30, then length(TNAF) < log2Norm + 3.52
285: int maxLength = log2Norm > 30 ? log2Norm + 4 : 34;
286:
287: // The array holding the TNAF
288: byte[] u = new byte[maxLength];
289: int i = 0;
290:
291: // The actual length of the TNAF
292: int length = 0;
293:
294: BigInteger r0 = lambda.u;
295: BigInteger r1 = lambda.v;
296:
297: while (!((r0.equals(ECConstants.ZERO)) && (r1
298: .equals(ECConstants.ZERO)))) {
299: // If r0 is odd
300: if (r0.testBit(0)) {
301: u[i] = (byte) ECConstants.TWO.subtract(
302: (r0.subtract(r1.shiftLeft(1)))
303: .mod(ECConstants.FOUR)).intValue();
304:
305: // r0 = r0 - u[i]
306: if (u[i] == 1) {
307: r0 = r0.clearBit(0);
308: } else {
309: // u[i] == -1
310: r0 = r0.add(ECConstants.ONE);
311: }
312: length = i;
313: } else {
314: u[i] = 0;
315: }
316:
317: BigInteger t = r0;
318: BigInteger s = r0.shiftRight(1);
319: if (mu == 1) {
320: r0 = r1.add(s);
321: } else {
322: // mu == -1
323: r0 = r1.subtract(s);
324: }
325:
326: r1 = t.shiftRight(1).negate();
327: i++;
328: }
329:
330: length++;
331:
332: // Reduce the TNAF array to its actual length
333: byte[] tnaf = new byte[length];
334: System.arraycopy(u, 0, tnaf, 0, length);
335: return tnaf;
336: }
337:
338: /**
339: * Applies the operation <code>τ()</code> to an
340: * <code>ECPoint.F2m</code>.
341: * @param p The ECPoint.F2m to which <code>τ()</code> is applied.
342: * @return <code>τ(p)</code>
343: */
344: public static ECPoint.F2m tau(ECPoint.F2m p) {
345: if (p.isInfinity()) {
346: return p;
347: }
348:
349: ECFieldElement x = p.getX();
350: ECFieldElement y = p.getY();
351:
352: return new ECPoint.F2m(p.getCurve(), x.square(), y.square(), p
353: .isCompressed());
354: }
355:
356: /**
357: * Returns the parameter <code>μ</code> of the elliptic curve.
358: * @param curve The elliptic curve from which to obtain <code>μ</code>.
359: * The curve must be a Koblitz curve, i.e. <code>a</code> equals
360: * <code>0</code> or <code>1</code> and <code>b</code> equals
361: * <code>1</code>.
362: * @return <code>μ</code> of the elliptic curve.
363: * @throws IllegalArgumentException if the given ECCurve is not a Koblitz
364: * curve.
365: */
366: public static byte getMu(ECCurve.F2m curve) {
367: BigInteger a = curve.getA().toBigInteger();
368: byte mu;
369:
370: if (a.equals(ECConstants.ZERO)) {
371: mu = -1;
372: } else if (a.equals(ECConstants.ONE)) {
373: mu = 1;
374: } else {
375: throw new IllegalArgumentException(
376: "No Koblitz curve (ABC), "
377: + "TNAF multiplication not possible");
378: }
379: return mu;
380: }
381:
382: /**
383: * Calculates the Lucas Sequence elements <code>U<sub>k-1</sub></code> and
384: * <code>U<sub>k</sub></code> or <code>V<sub>k-1</sub></code> and
385: * <code>V<sub>k</sub></code>.
386: * @param mu The parameter <code>μ</code> of the elliptic curve.
387: * @param k The index of the second element of the Lucas Sequence to be
388: * returned.
389: * @param doV If set to true, computes <code>V<sub>k-1</sub></code> and
390: * <code>V<sub>k</sub></code>, otherwise <code>U<sub>k-1</sub></code> and
391: * <code>U<sub>k</sub></code>.
392: * @return An array with 2 elements, containing <code>U<sub>k-1</sub></code>
393: * and <code>U<sub>k</sub></code> or <code>V<sub>k-1</sub></code>
394: * and <code>V<sub>k</sub></code>.
395: */
396: public static BigInteger[] getLucas(byte mu, int k, boolean doV) {
397: if (!((mu == 1) || (mu == -1))) {
398: throw new IllegalArgumentException("mu must be 1 or -1");
399: }
400:
401: BigInteger u0;
402: BigInteger u1;
403: BigInteger u2;
404:
405: if (doV) {
406: u0 = ECConstants.TWO;
407: u1 = BigInteger.valueOf(mu);
408: } else {
409: u0 = ECConstants.ZERO;
410: u1 = ECConstants.ONE;
411: }
412:
413: for (int i = 1; i < k; i++) {
414: // u2 = mu*u1 - 2*u0;
415: BigInteger s = null;
416: if (mu == 1) {
417: s = u1;
418: } else {
419: // mu == -1
420: s = u1.negate();
421: }
422:
423: u2 = s.subtract(u0.shiftLeft(1));
424: u0 = u1;
425: u1 = u2;
426: // System.out.println(i + ": " + u2);
427: // System.out.println();
428: }
429:
430: BigInteger[] retVal = { u0, u1 };
431: return retVal;
432: }
433:
434: /**
435: * Computes the auxiliary value <code>t<sub>w</sub></code>. If the width is
436: * 4, then for <code>mu = 1</code>, <code>t<sub>w</sub> = 6</code> and for
437: * <code>mu = -1</code>, <code>t<sub>w</sub> = 10</code>
438: * @param mu The parameter <code>μ</code> of the elliptic curve.
439: * @param w The window width of the WTNAF.
440: * @return the auxiliary value <code>t<sub>w</sub></code>
441: */
442: public static BigInteger getTw(byte mu, int w) {
443: if (w == 4) {
444: if (mu == 1) {
445: return BigInteger.valueOf(6);
446: } else {
447: // mu == -1
448: return BigInteger.valueOf(10);
449: }
450: } else {
451: // For w <> 4, the values must be computed
452: BigInteger[] us = getLucas(mu, w, false);
453: BigInteger twoToW = ECConstants.ZERO.setBit(w);
454: BigInteger u1invert = us[1].modInverse(twoToW);
455: BigInteger tw;
456: tw = ECConstants.TWO.multiply(us[0]).multiply(u1invert)
457: .mod(twoToW);
458: // System.out.println("mu = " + mu);
459: // System.out.println("tw = " + tw);
460: return tw;
461: }
462: }
463:
464: /**
465: * Computes the auxiliary values <code>s<sub>0</sub></code> and
466: * <code>s<sub>1</sub></code> used for partial modular reduction.
467: * @param curve The elliptic curve for which to compute
468: * <code>s<sub>0</sub></code> and <code>s<sub>1</sub></code>.
469: * @throws IllegalArgumentException if <code>curve</code> is not a
470: * Koblitz curve (Anomalous Binary Curve, ABC).
471: */
472: public static BigInteger[] getSi(ECCurve.F2m curve) {
473: if (!curve.isKoblitz()) {
474: throw new IllegalArgumentException(
475: "si is defined for Koblitz curves only");
476: }
477:
478: int m = curve.getM();
479: int a = curve.getA().toBigInteger().intValue();
480: byte mu = curve.getMu();
481: int h = curve.getH().intValue();
482: int index = m + 3 - a;
483: BigInteger[] ui = getLucas(mu, index, false);
484:
485: BigInteger dividend0;
486: BigInteger dividend1;
487: if (mu == 1) {
488: dividend0 = ECConstants.ONE.subtract(ui[1]);
489: dividend1 = ECConstants.ONE.subtract(ui[0]);
490: } else if (mu == -1) {
491: dividend0 = ECConstants.ONE.add(ui[1]);
492: dividend1 = ECConstants.ONE.add(ui[0]);
493: } else {
494: throw new IllegalArgumentException("mu must be 1 or -1");
495: }
496:
497: BigInteger[] si = new BigInteger[2];
498:
499: if (h == 2) {
500: si[0] = dividend0.shiftRight(1);
501: si[1] = dividend1.shiftRight(1).negate();
502: } else if (h == 4) {
503: si[0] = dividend0.shiftRight(2);
504: si[1] = dividend1.shiftRight(2).negate();
505: } else {
506: throw new IllegalArgumentException(
507: "h (Cofactor) must be 2 or 4");
508: }
509:
510: return si;
511: }
512:
513: /**
514: * Partial modular reduction modulo
515: * <code>(τ<sup>m</sup> - 1)/(τ - 1)</code>.
516: * @param k The integer to be reduced.
517: * @param m The bitlength of the underlying finite field.
518: * @param a The parameter <code>a</code> of the elliptic curve.
519: * @param s The auxiliary values <code>s<sub>0</sub></code> and
520: * <code>s<sub>1</sub></code>.
521: * @param mu The parameter μ of the elliptic curve.
522: * @param c The precision (number of bits of accuracy) of the partial
523: * modular reduction.
524: * @return <code>ρ := k partmod (τ<sup>m</sup> - 1)/(τ - 1)</code>
525: */
526: public static ZTauElement partModReduction(BigInteger k, int m,
527: byte a, BigInteger[] s, byte mu, byte c) {
528: // d0 = s[0] + mu*s[1]; mu is either 1 or -1
529: BigInteger d0;
530: if (mu == 1) {
531: d0 = s[0].add(s[1]);
532: } else {
533: d0 = s[0].subtract(s[1]);
534: }
535:
536: BigInteger[] v = getLucas(mu, m, true);
537: BigInteger vm = v[1];
538:
539: SimpleBigDecimal lambda0 = approximateDivisionByN(k, s[0], vm,
540: a, m, c);
541:
542: SimpleBigDecimal lambda1 = approximateDivisionByN(k, s[1], vm,
543: a, m, c);
544:
545: ZTauElement q = round(lambda0, lambda1, mu);
546:
547: // r0 = n - d0*q0 - 2*s1*q1
548: BigInteger r0 = k.subtract(d0.multiply(q.u)).subtract(
549: BigInteger.valueOf(2).multiply(s[1]).multiply(q.v));
550:
551: // r1 = s1*q0 - s0*q1
552: BigInteger r1 = s[1].multiply(q.u).subtract(s[0].multiply(q.v));
553:
554: return new ZTauElement(r0, r1);
555: }
556:
557: /**
558: * Multiplies a {@link org.bouncycastle.math.ec.ECPoint.F2m ECPoint.F2m}
559: * by a <code>BigInteger</code> using the reduced <code>τ</code>-adic
560: * NAF (RTNAF) method.
561: * @param p The ECPoint.F2m to multiply.
562: * @param k The <code>BigInteger</code> by which to multiply <code>p</code>.
563: * @return <code>k * p</code>
564: */
565: public static ECPoint.F2m multiplyRTnaf(ECPoint.F2m p, BigInteger k) {
566: ECCurve.F2m curve = (ECCurve.F2m) p.getCurve();
567: int m = curve.getM();
568: byte a = (byte) curve.getA().toBigInteger().intValue();
569: byte mu = curve.getMu();
570: BigInteger[] s = curve.getSi();
571: ZTauElement rho = partModReduction(k, m, a, s, mu, (byte) 10);
572:
573: return multiplyTnaf(p, rho);
574: }
575:
576: /**
577: * Multiplies a {@link org.bouncycastle.math.ec.ECPoint.F2m ECPoint.F2m}
578: * by an element <code>λ</code> of <code><b>Z</b>[τ]</code>
579: * using the <code>τ</code>-adic NAF (TNAF) method.
580: * @param p The ECPoint.F2m to multiply.
581: * @param lambda The element <code>λ</code> of
582: * <code><b>Z</b>[τ]</code>.
583: * @return <code>λ * p</code>
584: */
585: public static ECPoint.F2m multiplyTnaf(ECPoint.F2m p,
586: ZTauElement lambda) {
587: ECCurve.F2m curve = (ECCurve.F2m) p.getCurve();
588: byte mu = curve.getMu();
589: byte[] u = tauAdicNaf(mu, lambda);
590:
591: ECPoint.F2m q = multiplyFromTnaf(p, u);
592:
593: return q;
594: }
595:
596: /**
597: * Multiplies a {@link org.bouncycastle.math.ec.ECPoint.F2m ECPoint.F2m}
598: * by an element <code>λ</code> of <code><b>Z</b>[τ]</code>
599: * using the <code>τ</code>-adic NAF (TNAF) method, given the TNAF
600: * of <code>λ</code>.
601: * @param p The ECPoint.F2m to multiply.
602: * @param u The the TNAF of <code>λ</code>..
603: * @return <code>λ * p</code>
604: */
605: public static ECPoint.F2m multiplyFromTnaf(ECPoint.F2m p, byte[] u) {
606: ECCurve.F2m curve = (ECCurve.F2m) p.getCurve();
607: ECPoint.F2m q = (ECPoint.F2m) curve.getInfinity();
608: for (int i = u.length - 1; i >= 0; i--) {
609: q = tau(q);
610: if (u[i] == 1) {
611: q = (ECPoint.F2m) q.addSimple(p);
612: } else if (u[i] == -1) {
613: q = (ECPoint.F2m) q.subtractSimple(p);
614: }
615: }
616: return q;
617: }
618:
619: /**
620: * Computes the <code>[τ]</code>-adic window NAF of an element
621: * <code>λ</code> of <code><b>Z</b>[τ]</code>.
622: * @param mu The parameter μ of the elliptic curve.
623: * @param lambda The element <code>λ</code> of
624: * <code><b>Z</b>[τ]</code> of which to compute the
625: * <code>[τ]</code>-adic NAF.
626: * @param width The window width of the resulting WNAF.
627: * @param pow2w 2<sup>width</sup>.
628: * @param tw The auxiliary value <code>t<sub>w</sub></code>.
629: * @param alpha The <code>α<sub>u</sub></code>'s for the window width.
630: * @return The <code>[τ]</code>-adic window NAF of
631: * <code>λ</code>.
632: */
633: public static byte[] tauAdicWNaf(byte mu, ZTauElement lambda,
634: byte width, BigInteger pow2w, BigInteger tw,
635: ZTauElement[] alpha) {
636: if (!((mu == 1) || (mu == -1))) {
637: throw new IllegalArgumentException("mu must be 1 or -1");
638: }
639:
640: BigInteger norm = norm(mu, lambda);
641:
642: // Ceiling of log2 of the norm
643: int log2Norm = norm.bitLength();
644:
645: // If length(TNAF) > 30, then length(TNAF) < log2Norm + 3.52
646: int maxLength = log2Norm > 30 ? log2Norm + 4 + width
647: : 34 + width;
648:
649: // The array holding the TNAF
650: byte[] u = new byte[maxLength];
651:
652: // 2^(width - 1)
653: BigInteger pow2wMin1 = pow2w.shiftRight(1);
654:
655: // Split lambda into two BigIntegers to simplify calculations
656: BigInteger r0 = lambda.u;
657: BigInteger r1 = lambda.v;
658: int i = 0;
659:
660: // while lambda <> (0, 0)
661: while (!((r0.equals(ECConstants.ZERO)) && (r1
662: .equals(ECConstants.ZERO)))) {
663: // if r0 is odd
664: if (r0.testBit(0)) {
665: // uUnMod = r0 + r1*tw mod 2^width
666: BigInteger uUnMod = r0.add(r1.multiply(tw)).mod(pow2w);
667:
668: byte uLocal;
669: // if uUnMod >= 2^(width - 1)
670: if (uUnMod.compareTo(pow2wMin1) >= 0) {
671: uLocal = (byte) uUnMod.subtract(pow2w).intValue();
672: } else {
673: uLocal = (byte) uUnMod.intValue();
674: }
675: // uLocal is now in [-2^(width-1), 2^(width-1)-1]
676:
677: u[i] = uLocal;
678: boolean s = true;
679: if (uLocal < 0) {
680: s = false;
681: uLocal = (byte) -uLocal;
682: }
683: // uLocal is now >= 0
684:
685: if (s) {
686: r0 = r0.subtract(alpha[uLocal].u);
687: r1 = r1.subtract(alpha[uLocal].v);
688: } else {
689: r0 = r0.add(alpha[uLocal].u);
690: r1 = r1.add(alpha[uLocal].v);
691: }
692: } else {
693: u[i] = 0;
694: }
695:
696: BigInteger t = r0;
697:
698: if (mu == 1) {
699: r0 = r1.add(r0.shiftRight(1));
700: } else {
701: // mu == -1
702: r0 = r1.subtract(r0.shiftRight(1));
703: }
704: r1 = t.shiftRight(1).negate();
705: i++;
706: }
707: return u;
708: }
709:
710: /**
711: * Does the precomputation for WTNAF multiplication.
712: * @param p The <code>ECPoint</code> for which to do the precomputation.
713: * @param a The parameter <code>a</code> of the elliptic curve.
714: * @return The precomputation array for <code>p</code>.
715: */
716: public static ECPoint.F2m[] getPreComp(ECPoint.F2m p, byte a) {
717: ECPoint.F2m[] pu;
718: pu = new ECPoint.F2m[16];
719: pu[1] = p;
720: byte[][] alphaTnaf;
721: if (a == 0) {
722: alphaTnaf = Tnaf.alpha0Tnaf;
723: } else {
724: // a == 1
725: alphaTnaf = Tnaf.alpha1Tnaf;
726: }
727:
728: int precompLen = alphaTnaf.length;
729: for (int i = 3; i < precompLen; i = i + 2) {
730: pu[i] = Tnaf.multiplyFromTnaf(p, alphaTnaf[i]);
731: }
732:
733: return pu;
734: }
735: }
|