001: package org.bouncycastle.math.ec;
002:
003: import java.math.BigInteger;
004:
005: /**
006: * Class implementing the WNAF (Window Non-Adjacent Form) multiplication
007: * algorithm.
008: */
009: class WNafMultiplier implements ECMultiplier {
010: /**
011: * Computes the Window NAF (non-adjacent Form) of an integer.
012: * @param width The width <code>w</code> of the Window NAF. The width is
013: * defined as the minimal number <code>w</code>, such that for any
014: * <code>w</code> consecutive digits in the resulting representation, at
015: * most one is non-zero.
016: * @param k The integer of which the Window NAF is computed.
017: * @return The Window NAF of the given width, such that the following holds:
018: * <code>k = ∑<sub>i=0</sub><sup>l-1</sup> k<sub>i</sub>2<sup>i</sup>
019: * </code>, where the <code>k<sub>i</sub></code> denote the elements of the
020: * returned <code>byte[]</code>.
021: */
022: public byte[] windowNaf(byte width, BigInteger k) {
023: // The window NAF is at most 1 element longer than the binary
024: // representation of the integer k. byte can be used instead of short or
025: // int unless the window width is larger than 8. For larger width use
026: // short or int. However, a width of more than 8 is not efficient for
027: // m = log2(q) smaller than 2305 Bits. Note: Values for m larger than
028: // 1000 Bits are currently not used in practice.
029: byte[] wnaf = new byte[k.bitLength() + 1];
030:
031: // 2^width as short and BigInteger
032: short pow2wB = (short) (1 << width);
033: BigInteger pow2wBI = BigInteger.valueOf(pow2wB);
034:
035: int i = 0;
036:
037: // The actual length of the WNAF
038: int length = 0;
039:
040: // while k >= 1
041: while (k.signum() > 0) {
042: // if k is odd
043: if (k.testBit(0)) {
044: // k mod 2^width
045: BigInteger remainder = k.mod(pow2wBI);
046:
047: // if remainder > 2^(width - 1) - 1
048: if (remainder.testBit(width - 1)) {
049: wnaf[i] = (byte) (remainder.intValue() - pow2wB);
050: } else {
051: wnaf[i] = (byte) remainder.intValue();
052: }
053: // wnaf[i] is now in [-2^(width-1), 2^(width-1)-1]
054:
055: k = k.subtract(BigInteger.valueOf(wnaf[i]));
056: length = i;
057: } else {
058: wnaf[i] = 0;
059: }
060:
061: // k = k/2
062: k = k.shiftRight(1);
063: i++;
064: }
065:
066: length++;
067:
068: // Reduce the WNAF array to its actual length
069: byte[] wnafShort = new byte[length];
070: System.arraycopy(wnaf, 0, wnafShort, 0, length);
071: return wnafShort;
072: }
073:
074: /**
075: * Multiplies <code>this</code> by an integer <code>k</code> using the
076: * Window NAF method.
077: * @param k The integer by which <code>this</code> is multiplied.
078: * @return A new <code>ECPoint</code> which equals <code>this</code>
079: * multiplied by <code>k</code>.
080: */
081: public ECPoint multiply(ECPoint p, BigInteger k,
082: PreCompInfo preCompInfo) {
083: WNafPreCompInfo wnafPreCompInfo;
084:
085: if ((preCompInfo != null)
086: && (preCompInfo instanceof WNafPreCompInfo)) {
087: wnafPreCompInfo = (WNafPreCompInfo) preCompInfo;
088: } else {
089: // Ignore empty PreCompInfo or PreCompInfo of incorrect type
090: wnafPreCompInfo = new WNafPreCompInfo();
091: }
092:
093: // floor(log2(k))
094: int m = k.bitLength();
095:
096: // width of the Window NAF
097: byte width;
098:
099: // Required length of precomputation array
100: int reqPreCompLen;
101:
102: // Determine optimal width and corresponding length of precomputation
103: // array based on literature values
104: if (m < 13) {
105: width = 2;
106: reqPreCompLen = 1;
107: } else {
108: if (m < 41) {
109: width = 3;
110: reqPreCompLen = 2;
111: } else {
112: if (m < 121) {
113: width = 4;
114: reqPreCompLen = 4;
115: } else {
116: if (m < 337) {
117: width = 5;
118: reqPreCompLen = 8;
119: } else {
120: if (m < 897) {
121: width = 6;
122: reqPreCompLen = 16;
123: } else {
124: if (m < 2305) {
125: width = 7;
126: reqPreCompLen = 32;
127: } else {
128: width = 8;
129: reqPreCompLen = 127;
130: }
131: }
132: }
133: }
134: }
135: }
136:
137: // The length of the precomputation array
138: int preCompLen = 1;
139:
140: ECPoint[] preComp = wnafPreCompInfo.getPreComp();
141: ECPoint twiceP = wnafPreCompInfo.getTwiceP();
142:
143: // Check if the precomputed ECPoints already exist
144: if (preComp == null) {
145: // Precomputation must be performed from scratch, create an empty
146: // precomputation array of desired length
147: preComp = new ECPoint[] { p };
148: } else {
149: // Take the already precomputed ECPoints to start with
150: preCompLen = preComp.length;
151: }
152:
153: if (twiceP == null) {
154: // Compute twice(p)
155: twiceP = p.twice();
156: }
157:
158: if (preCompLen < reqPreCompLen) {
159: // Precomputation array must be made bigger, copy existing preComp
160: // array into the larger new preComp array
161: ECPoint[] oldPreComp = preComp;
162: preComp = new ECPoint[reqPreCompLen];
163: System.arraycopy(oldPreComp, 0, preComp, 0, preCompLen);
164:
165: for (int i = preCompLen; i < reqPreCompLen; i++) {
166: // Compute the new ECPoints for the precomputation array.
167: // The values 1, 3, 5, ..., 2^(width-1)-1 times p are
168: // computed
169: preComp[i] = twiceP.add(preComp[i - 1]);
170: }
171: }
172:
173: // Compute the Window NAF of the desired width
174: byte[] wnaf = windowNaf(width, k);
175: int l = wnaf.length;
176:
177: // Apply the Window NAF to p using the precomputed ECPoint values.
178: ECPoint q = p.getCurve().getInfinity();
179: for (int i = l - 1; i >= 0; i--) {
180: q = q.twice();
181:
182: if (wnaf[i] != 0) {
183: if (wnaf[i] > 0) {
184: q = q.add(preComp[(wnaf[i] - 1) / 2]);
185: } else {
186: // wnaf[i] < 0
187: q = q.subtract(preComp[(-wnaf[i] - 1) / 2]);
188: }
189: }
190: }
191:
192: // Set PreCompInfo in ECPoint, such that it is available for next
193: // multiplication.
194: wnafPreCompInfo.setPreComp(preComp);
195: wnafPreCompInfo.setTwiceP(twiceP);
196: p.setPreCompInfo(wnafPreCompInfo);
197: return q;
198: }
199:
200: }
|