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 import sun.security.util.math.*;
27
28 import java.math.BigInteger;
29 import java.nio.ByteBuffer;
30
31 /**
32 * Arithmetic in the field of integers modulo a prime value implemented using
33 * BigInteger. This implementation is very versatile, but it is slow and none
34 * of the operations are value-independent. This class is intended for use in
35 * testing and prototyping, and production code should probably use a more
36 * specialized arithmetic implementation.
37 */
38
39 public class BigIntegerModuloP implements IntegerFieldModuloP {
40
41 private final BigInteger p;
42
43 public BigIntegerModuloP(BigInteger p) {
44 this.p = p;
45 }
46
47 @Override
48 public BigInteger getSize() {
49 return p;
50 }
51
52 @Override
53 public ImmutableElement get0() {
54 return new ImmutableElement(BigInteger.ZERO);
55 }
56 @Override
57 public ImmutableElement get1() {
58 return new ImmutableElement(BigInteger.ONE);
59 }
60 @Override
61 public ImmutableElement getElement(BigInteger v) {
62 return new ImmutableElement(v);
63 }
64 @Override
65 public ImmutableElement getElement(byte[] v, int offset, int length,
66 byte highByte) {
67 byte[] bigIntIn = new byte[length + 1];
68 System.arraycopy(v, offset, bigIntIn, 0, length);
69 bigIntIn[length] = highByte;
70 reverse(bigIntIn);
71 return new ImmutableElement(new BigInteger(1, bigIntIn).mod(getSize()));
72 }
73 @Override
74 public SmallValue getSmallValue(int i) {
75 return new SmallElement(i);
76 }
77
78 private abstract class Element implements IntegerModuloP {
79
80 protected BigInteger v;
81
82 protected Element(BigInteger v) {
83 this.v = v;
84 }
85
86 protected Element(boolean v) {
87 this.v = BigInteger.valueOf(v ? 1 : 0);
88 }
89
90 private BigInteger getModulus() {
91 return getField().getSize();
92 }
93
94 @Override
95 public IntegerFieldModuloP getField() {
96 return BigIntegerModuloP.this;
97 }
98
99 @Override
100 public BigInteger asBigInteger() {
101 return v;
102 }
103
104 @Override
105 public MutableElement mutable() {
106 return new MutableElement(v);
107 }
108
109 @Override
110 public ImmutableElement fixed() {
111 return new ImmutableElement(v);
112 }
113
114 @Override
115 public ImmutableElement add(IntegerModuloP b) {
116 return new ImmutableElement(
117 v.add(b.asBigInteger()).mod(getModulus()));
118 }
119
120 @Override
121 public ImmutableElement additiveInverse() {
122 return new ImmutableElement(v.negate().mod(getModulus()));
123 }
124
125 @Override
126 public ImmutableElement multiply(IntegerModuloP b) {
127 return new ImmutableElement(
128 v.multiply(b.asBigInteger()).mod(getModulus()));
129 }
130
131 @Override
132 public void addModPowerTwo(IntegerModuloP arg, byte[] result) {
133 BigInteger biThis = asBigInteger();
134 BigInteger biArg = arg.asBigInteger();
135 bigIntAsByteArray(biThis.add(biArg), result);
136 }
137
138 private void bigIntAsByteArray(BigInteger arg, byte[] result) {
139 byte[] bytes = arg.toByteArray();
140 // bytes is backwards and possibly too big
141 // Copy the low-order bytes into result in reverse
142 int sourceIndex = bytes.length - 1;
143 for (int i = 0; i < result.length; i++) {
144 if (sourceIndex >= 0) {
145 result[i] = bytes[sourceIndex--];
146 } else {
147 result[i] = 0;
148 }
149 }
150 }
151
152 @Override
153 public void asByteArray(byte[] result) {
154 bigIntAsByteArray(v, result);
155 }
156 }
157
158 private class ImmutableElement extends Element
159 implements ImmutableIntegerModuloP {
160
161 private ImmutableElement(BigInteger v) {
162 super(v);
163 }
164 }
165
166 private class MutableElement extends Element
167 implements MutableIntegerModuloP {
168
169 private MutableElement(BigInteger v) {
170 super(v);
171 }
172
173 @Override
174 public void conditionalSwapWith(MutableIntegerModuloP b, int swap) {
175 if (swap == 1) {
176 BigInteger temp = v;
177 v = b.asBigInteger();
178 ((Element) b).v = temp;
179 }
180 }
181
182 @Override
183 public MutableElement setValue(IntegerModuloP v) {
184 this.v = ((Element) v).v;
185
186 return this;
187 }
188
189 @Override
190 public MutableElement setValue(byte[] arr, int offset, int length,
191 byte highByte) {
192 byte[] bigIntIn = new byte[length + 1];
193 System.arraycopy(arr, offset, bigIntIn, 0, length);
194 bigIntIn[length] = highByte;
195 reverse(bigIntIn);
196 v = new BigInteger(bigIntIn).mod(getSize());
197
198 return this;
199 }
200
201 @Override
202 public MutableElement setValue(ByteBuffer buf, int length,
203 byte highByte) {
204 byte[] bigIntIn = new byte[length + 1];
205 buf.get(bigIntIn, 0, length);
206 bigIntIn[length] = highByte;
207 reverse(bigIntIn);
208 v = new BigInteger(bigIntIn).mod(getSize());
209
210 return this;
211 }
212
213 @Override
214 public MutableElement setSquare() {
215 v = v.multiply(v).mod(getSize());
216 return this;
217 }
218
219 @Override
220 public MutableElement setProduct(IntegerModuloP b) {
221 Element other = (Element) b;
222 v = v.multiply(other.v).mod(getSize());
223 return this;
224 }
225
226 @Override
227 public MutableElement setProduct(SmallValue value) {
228 BigInteger bigIntValue = ((SmallElement) value).asBigInteger();
229 v = v.multiply(bigIntValue).mod(getSize());
230 return this;
231 }
232
233 @Override
234 public MutableElement setSum(IntegerModuloP b) {
235 Element other = (Element) b;
236 v = v.add(other.v).mod(getSize());
237 return this;
238 }
239
240 @Override
241 public MutableElement setDifference(IntegerModuloP b) {
242 Element other = (Element) b;
243 v = v.subtract(other.v).mod(getSize());
244 return this;
245 }
246
247 }
248
249 private class SmallElement extends ImmutableElement implements SmallValue {
250
251 public SmallElement(int v) {
252 super(BigInteger.valueOf(v).mod(getSize()));
253 }
254 }
255
256 private static void swap(byte[] arr, int i, int j) {
257 byte tmp = arr[i];
258 arr[i] = arr[j];
259 arr[j] = tmp;
260 }
261
262 private static void reverse(byte [] arr) {
263 int i = 0;
264 int j = arr.length - 1;
265
266 while (i < j) {
267 swap(arr, i, j);
268 i++;
269 j--;
270 }
271 }
272
273 }