|
1 /* |
|
2 * Copyright (c) 2018, Oracle and/or its affiliates. All rights reserved. |
|
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
|
4 * |
|
5 * This code is free software; you can redistribute it and/or modify it |
|
6 * under the terms of the GNU General Public License version 2 only, as |
|
7 * published by the Free Software Foundation. Oracle designates this |
|
8 * particular file as subject to the "Classpath" exception as provided |
|
9 * by Oracle in the LICENSE file that accompanied this code. |
|
10 * |
|
11 * This code is distributed in the hope that it will be useful, but WITHOUT |
|
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
|
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
|
14 * version 2 for more details (a copy is included in the LICENSE file that |
|
15 * accompanied this code). |
|
16 * |
|
17 * You should have received a copy of the GNU General Public License version |
|
18 * 2 along with this work; if not, write to the Free Software Foundation, |
|
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
|
20 * |
|
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
22 * or visit www.oracle.com if you need additional information or have any |
|
23 * questions. |
|
24 */ |
|
25 |
|
26 package sun.security.util.math.intpoly; |
|
27 |
|
28 import java.math.BigInteger; |
|
29 |
|
30 public class IntegerPolynomial25519 extends IntegerPolynomial { |
|
31 |
|
32 private static final int POWER = 255; |
|
33 private static final int SUBTRAHEND = 19; |
|
34 private static final int NUM_LIMBS = 10; |
|
35 private static final int BITS_PER_LIMB = 26; |
|
36 public static final BigInteger MODULUS |
|
37 = TWO.pow(POWER).subtract(BigInteger.valueOf(SUBTRAHEND)); |
|
38 |
|
39 // BITS_PER_LIMB does not divide POWER, so reduction is a bit complicated |
|
40 // The constants below help split up values during reduction |
|
41 private static final int BIT_OFFSET = NUM_LIMBS * BITS_PER_LIMB - POWER; |
|
42 private static final int LIMB_MASK = -1 >>> (64 - BITS_PER_LIMB); |
|
43 private static final int RIGHT_BIT_OFFSET = BITS_PER_LIMB - BIT_OFFSET; |
|
44 |
|
45 public IntegerPolynomial25519() { |
|
46 super(BITS_PER_LIMB, NUM_LIMBS, MODULUS); |
|
47 } |
|
48 |
|
49 @Override |
|
50 protected void mult(long[] a, long[] b, long[] r) { |
|
51 |
|
52 // Use grade-school multiplication into primitives to avoid the |
|
53 // temporary array allocation. This is equivalent to the following |
|
54 // code: |
|
55 // long[] c = new long[2 * NUM_LIMBS - 1]; |
|
56 // for(int i = 0; i < NUM_LIMBS; i++) { |
|
57 // for(int j - 0; j < NUM_LIMBS; j++) { |
|
58 // c[i + j] += a[i] * b[j] |
|
59 // } |
|
60 // } |
|
61 |
|
62 long c0 = (a[0] * b[0]); |
|
63 long c1 = (a[0] * b[1]) + (a[1] * b[0]); |
|
64 long c2 = (a[0] * b[2]) + (a[1] * b[1]) + (a[2] * b[0]); |
|
65 long c3 = (a[0] * b[3]) + (a[1] * b[2]) + (a[2] * b[1]) + (a[3] * b[0]); |
|
66 long c4 = (a[0] * b[4]) + (a[1] * b[3]) + (a[2] * b[2]) + (a[3] * b[1]) + (a[4] * b[0]); |
|
67 long c5 = (a[0] * b[5]) + (a[1] * b[4]) + (a[2] * b[3]) + (a[3] * b[2]) + (a[4] * b[1]) + (a[5] * b[0]); |
|
68 long c6 = (a[0] * b[6]) + (a[1] * b[5]) + (a[2] * b[4]) + (a[3] * b[3]) + (a[4] * b[2]) + (a[5] * b[1]) + (a[6] * b[0]); |
|
69 long c7 = (a[0] * b[7]) + (a[1] * b[6]) + (a[2] * b[5]) + (a[3] * b[4]) + (a[4] * b[3]) + (a[5] * b[2]) + (a[6] * b[1]) + (a[7] * b[0]); |
|
70 long c8 = (a[0] * b[8]) + (a[1] * b[7]) + (a[2] * b[6]) + (a[3] * b[5]) + (a[4] * b[4]) + (a[5] * b[3]) + (a[6] * b[2]) + (a[7] * b[1]) + (a[8] * b[0]); |
|
71 long c9 = (a[0] * b[9]) + (a[1] * b[8]) + (a[2] * b[7]) + (a[3] * b[6]) + (a[4] * b[5]) + (a[5] * b[4]) + (a[6] * b[3]) + (a[7] * b[2]) + (a[8] * b[1]) + (a[9] * b[0]); |
|
72 long c10 = (a[1] * b[9]) + (a[2] * b[8]) + (a[3] * b[7]) + (a[4] * b[6]) + (a[5] * b[5]) + (a[6] * b[4]) + (a[7] * b[3]) + (a[8] * b[2]) + (a[9] * b[1]); |
|
73 long c11 = (a[2] * b[9]) + (a[3] * b[8]) + (a[4] * b[7]) + (a[5] * b[6]) + (a[6] * b[5]) + (a[7] * b[4]) + (a[8] * b[3]) + (a[9] * b[2]); |
|
74 long c12 = (a[3] * b[9]) + (a[4] * b[8]) + (a[5] * b[7]) + (a[6] * b[6]) + (a[7] * b[5]) + (a[8] * b[4]) + (a[9] * b[3]); |
|
75 long c13 = (a[4] * b[9]) + (a[5] * b[8]) + (a[6] * b[7]) + (a[7] * b[6]) + (a[8] * b[5]) + (a[9] * b[4]); |
|
76 long c14 = (a[5] * b[9]) + (a[6] * b[8]) + (a[7] * b[7]) + (a[8] * b[6]) + (a[9] * b[5]); |
|
77 long c15 = (a[6] * b[9]) + (a[7] * b[8]) + (a[8] * b[7]) + (a[9] * b[6]); |
|
78 long c16 = (a[7] * b[9]) + (a[8] * b[8]) + (a[9] * b[7]); |
|
79 long c17 = (a[8] * b[9]) + (a[9] * b[8]); |
|
80 long c18 = a[9] * b[9]; |
|
81 |
|
82 carryReduce(r, c0, c1, c2, c3, c4, c5, c6, c7, c8, |
|
83 c9, c10, c11, c12, c13, c14, c15, c16, c17, c18); |
|
84 |
|
85 } |
|
86 |
|
87 private void carryReduce(long[] r, long c0, long c1, long c2, |
|
88 long c3, long c4, long c5, long c6, |
|
89 long c7, long c8, long c9, long c10, |
|
90 long c11, long c12, long c13, long c14, |
|
91 long c15, long c16, long c17, long c18) { |
|
92 // reduce(7,2) |
|
93 long reducedValue17 = (c17 * SUBTRAHEND); |
|
94 c7 += (reducedValue17 << BIT_OFFSET) & LIMB_MASK; |
|
95 c8 += reducedValue17 >> RIGHT_BIT_OFFSET; |
|
96 |
|
97 long reducedValue18 = (c18 * SUBTRAHEND); |
|
98 c8 += (reducedValue18 << BIT_OFFSET) & LIMB_MASK; |
|
99 c9 += reducedValue18 >> RIGHT_BIT_OFFSET; |
|
100 |
|
101 // carry(8,2) |
|
102 long carry8 = carryValue(c8); |
|
103 r[8] = c8 - (carry8 << BITS_PER_LIMB); |
|
104 c9 += carry8; |
|
105 |
|
106 long carry9 = carryValue(c9); |
|
107 r[9] = c9 - (carry9 << BITS_PER_LIMB); |
|
108 c10 += carry9; |
|
109 |
|
110 // reduce(0,7) |
|
111 long reducedValue10 = (c10 * SUBTRAHEND); |
|
112 r[0] = c0 + ((reducedValue10 << BIT_OFFSET) & LIMB_MASK); |
|
113 c1 += reducedValue10 >> RIGHT_BIT_OFFSET; |
|
114 |
|
115 long reducedValue11 = (c11 * SUBTRAHEND); |
|
116 r[1] = c1 + ((reducedValue11 << BIT_OFFSET) & LIMB_MASK); |
|
117 c2 += reducedValue11 >> RIGHT_BIT_OFFSET; |
|
118 |
|
119 long reducedValue12 = (c12 * SUBTRAHEND); |
|
120 r[2] = c2 + ((reducedValue12 << BIT_OFFSET) & LIMB_MASK); |
|
121 c3 += reducedValue12 >> RIGHT_BIT_OFFSET; |
|
122 |
|
123 long reducedValue13 = (c13 * SUBTRAHEND); |
|
124 r[3] = c3 + ((reducedValue13 << BIT_OFFSET) & LIMB_MASK); |
|
125 c4 += reducedValue13 >> RIGHT_BIT_OFFSET; |
|
126 |
|
127 long reducedValue14 = (c14 * SUBTRAHEND); |
|
128 r[4] = c4 + ((reducedValue14 << BIT_OFFSET) & LIMB_MASK); |
|
129 c5 += reducedValue14 >> RIGHT_BIT_OFFSET; |
|
130 |
|
131 long reducedValue15 = (c15 * SUBTRAHEND); |
|
132 r[5] = c5 + ((reducedValue15 << BIT_OFFSET) & LIMB_MASK); |
|
133 c6 += reducedValue15 >> RIGHT_BIT_OFFSET; |
|
134 |
|
135 long reducedValue16 = (c16 * SUBTRAHEND); |
|
136 r[6] = c6 + ((reducedValue16 << BIT_OFFSET) & LIMB_MASK); |
|
137 r[7] = c7 + (reducedValue16 >> RIGHT_BIT_OFFSET); |
|
138 |
|
139 // carry(0,9) |
|
140 carry(r, 0, 9); |
|
141 } |
|
142 |
|
143 protected void multByInt(long[] a, long b, long[] r) { |
|
144 for (int i = 0; i < a.length; i++) { |
|
145 r[i] = a[i] * b; |
|
146 } |
|
147 |
|
148 // carry(8, 2) |
|
149 long carry8 = carryValue(r[8]); |
|
150 r[8] -= (carry8 << BITS_PER_LIMB); |
|
151 r[9] += carry8; |
|
152 |
|
153 long carry9 = carryValue(r[9]); |
|
154 r[9] -= (carry9 << BITS_PER_LIMB); |
|
155 |
|
156 // reduce(0, 1) |
|
157 long reducedValue10 = (carry9 * SUBTRAHEND); |
|
158 r[0] += ((reducedValue10 << BIT_OFFSET) & LIMB_MASK); |
|
159 r[1] += reducedValue10 >> RIGHT_BIT_OFFSET; |
|
160 |
|
161 // carry(0, 9) |
|
162 carry(r, 0, 9); |
|
163 } |
|
164 |
|
165 @Override |
|
166 protected void square(long[] a, long[] r) { |
|
167 |
|
168 // Use grade-school multiplication with a simple squaring optimization. |
|
169 // Multiply into primitives to avoid the temporary array allocation. |
|
170 // This is equivalent to the following code: |
|
171 // long[] c = new long[2 * NUM_LIMBS - 1]; |
|
172 // for(int i = 0; i < NUM_LIMBS; i++) { |
|
173 // c[2 * i] = a[i] * a[i]; |
|
174 // for(int j = i + 1; j < NUM_LIMBS; j++) { |
|
175 // c[i + j] += 2 * a[i] * a[j] |
|
176 // } |
|
177 // } |
|
178 |
|
179 long c0 = a[0] * a[0]; |
|
180 long c1 = 2 * a[0] * a[1]; |
|
181 long c2 = a[1] * a[1] + 2 * a[0] * a[2]; |
|
182 long c3 = 2 * (a[0] * a[3] + a[1] * a[2]); |
|
183 long c4 = a[2] * a[2] + 2 * (a[0] * a[4] + a[1] * a[3]); |
|
184 long c5 = 2 * (a[0] * a[5] + a[1] * a[4] + a[2] * a[3]); |
|
185 long c6 = a[3] * a[3] + 2 * (a[0] * a[6] + a[1] * a[5] + a[2] * a[4]); |
|
186 long c7 = 2 * (a[0] * a[7] + a[1] * a[6] + a[2] * a[5] + a[3] * a[4]); |
|
187 long c8 = a[4] * a[4] + 2 * (a[0] * a[8] + a[1] * a[7] + a[2] * a[6] + a[3] * a[5]); |
|
188 long c9 = 2 * (a[0] * a[9] + a[1] * a[8] + a[2] * a[7] + a[3] * a[6] + a[4] * a[5]); |
|
189 long c10 = a[5] * a[5] + 2 * (a[1] * a[9] + a[2] * a[8] + a[3] * a[7] + a[4] * a[6]); |
|
190 long c11 = 2 * (a[2] * a[9] + a[3] * a[8] + a[4] * a[7] + a[5] * a[6]); |
|
191 long c12 = a[6] * a[6] + 2 * (a[3] * a[9] + a[4] * a[8] + a[5] * a[7]); |
|
192 long c13 = 2 * (a[4] * a[9] + a[5] * a[8] + a[6] * a[7]); |
|
193 long c14 = a[7] * a[7] + 2 * (a[5] * a[9] + a[6] * a[8]); |
|
194 long c15 = 2 * (a[6] * a[9] + a[7] * a[8]); |
|
195 long c16 = a[8] * a[8] + 2 * a[7] * a[9]; |
|
196 long c17 = 2 * a[8] * a[9]; |
|
197 long c18 = a[9] * a[9]; |
|
198 |
|
199 carryReduce(r, c0, c1, c2, c3, c4, c5, c6, c7, c8, |
|
200 c9, c10, c11, c12, c13, c14, c15, c16, c17, c18); |
|
201 } |
|
202 |
|
203 |
|
204 } |