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 /** 31 * An IntegerFieldModuloP designed for use with the Curve448. 32 * The representation uses 16 signed long values. 33 */ 34 35 public class IntegerPolynomial448 extends IntegerPolynomial { 36 37 private static final int POWER = 448; 38 private static final int NUM_LIMBS = 16; 39 private static final int BITS_PER_LIMB = 28; 40 public static final BigInteger MODULUS 41 = TWO.pow(POWER).subtract(TWO.pow(POWER / 2)) 42 .subtract(BigInteger.valueOf(1)); 43 IntegerPolynomial448()44 public IntegerPolynomial448() { 45 super(BITS_PER_LIMB, NUM_LIMBS, 1, MODULUS); 46 } 47 modReduceIn(long[] limbs, int index, long x)48 private void modReduceIn(long[] limbs, int index, long x) { 49 limbs[index - NUM_LIMBS] += x; 50 limbs[index - NUM_LIMBS / 2] += x; 51 } 52 53 @Override finalCarryReduceLast(long[] limbs)54 protected void finalCarryReduceLast(long[] limbs) { 55 long carry = limbs[numLimbs - 1] >> bitsPerLimb; 56 limbs[numLimbs - 1] -= carry << bitsPerLimb; 57 modReduceIn(limbs, numLimbs, carry); 58 } 59 60 @Override reduce(long[] a)61 protected void reduce(long[] a) { 62 63 // carry(14, 2) 64 long carry14 = carryValue(a[14]); 65 a[14] -= (carry14 << BITS_PER_LIMB); 66 a[15] += carry14; 67 68 long carry15 = carryValue(a[15]); 69 a[15] -= (carry15 << BITS_PER_LIMB); 70 71 // reduce(0, 1) 72 a[0] += carry15; 73 a[8] += carry15; 74 75 // carry(0, 15) 76 carry(a, 0, 15); 77 } 78 79 @Override mult(long[] a, long[] b, long[] r)80 protected void mult(long[] a, long[] b, long[] r) { 81 82 // Use grade-school multiplication into primitives to avoid the 83 // temporary array allocation. This is equivalent to the following 84 // code: 85 // long[] c = new long[2 * NUM_LIMBS - 1]; 86 // for(int i = 0; i < NUM_LIMBS; i++) { 87 // for(int j - 0; j < NUM_LIMBS; j++) { 88 // c[i + j] += a[i] * b[j] 89 // } 90 // } 91 92 long c0 = (a[0] * b[0]); 93 long c1 = (a[0] * b[1]) + (a[1] * b[0]); 94 long c2 = (a[0] * b[2]) + (a[1] * b[1]) + (a[2] * b[0]); 95 long c3 = (a[0] * b[3]) + (a[1] * b[2]) + (a[2] * b[1]) + (a[3] * b[0]); 96 long c4 = (a[0] * b[4]) + (a[1] * b[3]) + (a[2] * b[2]) + (a[3] * b[1]) + (a[4] * b[0]); 97 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]); 98 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]); 99 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]); 100 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]); 101 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]); 102 long c10 = (a[0] * b[10]) + (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]) + (a[10] * b[0]); 103 long c11 = (a[0] * b[11]) + (a[1] * b[10]) + (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]) + (a[10] * b[1]) + (a[11] * b[0]); 104 long c12 = (a[0] * b[12]) + (a[1] * b[11]) + (a[2] * b[10]) + (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]) + (a[10] * b[2]) + (a[11] * b[1]) + (a[12] * b[0]); 105 long c13 = (a[0] * b[13]) + (a[1] * b[12]) + (a[2] * b[11]) + (a[3] * b[10]) + (a[4] * b[9]) + (a[5] * b[8]) + (a[6] * b[7]) + (a[7] * b[6]) + (a[8] * b[5]) + (a[9] * b[4]) + (a[10] * b[3]) + (a[11] * b[2]) + (a[12] * b[1]) + (a[13] * b[0]); 106 long c14 = (a[0] * b[14]) + (a[1] * b[13]) + (a[2] * b[12]) + (a[3] * b[11]) + (a[4] * b[10]) + (a[5] * b[9]) + (a[6] * b[8]) + (a[7] * b[7]) + (a[8] * b[6]) + (a[9] * b[5]) + (a[10] * b[4]) + (a[11] * b[3]) + (a[12] * b[2]) + (a[13] * b[1]) + (a[14] * b[0]); 107 long c15 = (a[0] * b[15]) + (a[1] * b[14]) + (a[2] * b[13]) + (a[3] * b[12]) + (a[4] * b[11]) + (a[5] * b[10]) + (a[6] * b[9]) + (a[7] * b[8]) + (a[8] * b[7]) + (a[9] * b[6]) + (a[10] * b[5]) + (a[11] * b[4]) + (a[12] * b[3]) + (a[13] * b[2]) + (a[14] * b[1]) + (a[15] * b[0]); 108 long c16 = (a[1] * b[15]) + (a[2] * b[14]) + (a[3] * b[13]) + (a[4] * b[12]) + (a[5] * b[11]) + (a[6] * b[10]) + (a[7] * b[9]) + (a[8] * b[8]) + (a[9] * b[7]) + (a[10] * b[6]) + (a[11] * b[5]) + (a[12] * b[4]) + (a[13] * b[3]) + (a[14] * b[2]) + (a[15] * b[1]); 109 long c17 = (a[2] * b[15]) + (a[3] * b[14]) + (a[4] * b[13]) + (a[5] * b[12]) + (a[6] * b[11]) + (a[7] * b[10]) + (a[8] * b[9]) + (a[9] * b[8]) + (a[10] * b[7]) + (a[11] * b[6]) + (a[12] * b[5]) + (a[13] * b[4]) + (a[14] * b[3]) + (a[15] * b[2]); 110 long c18 = (a[3] * b[15]) + (a[4] * b[14]) + (a[5] * b[13]) + (a[6] * b[12]) + (a[7] * b[11]) + (a[8] * b[10]) + (a[9] * b[9]) + (a[10] * b[8]) + (a[11] * b[7]) + (a[12] * b[6]) + (a[13] * b[5]) + (a[14] * b[4]) + (a[15] * b[3]); 111 long c19 = (a[4] * b[15]) + (a[5] * b[14]) + (a[6] * b[13]) + (a[7] * b[12]) + (a[8] * b[11]) + (a[9] * b[10]) + (a[10] * b[9]) + (a[11] * b[8]) + (a[12] * b[7]) + (a[13] * b[6]) + (a[14] * b[5]) + (a[15] * b[4]); 112 long c20 = (a[5] * b[15]) + (a[6] * b[14]) + (a[7] * b[13]) + (a[8] * b[12]) + (a[9] * b[11]) + (a[10] * b[10]) + (a[11] * b[9]) + (a[12] * b[8]) + (a[13] * b[7]) + (a[14] * b[6]) + (a[15] * b[5]); 113 long c21 = (a[6] * b[15]) + (a[7] * b[14]) + (a[8] * b[13]) + (a[9] * b[12]) + (a[10] * b[11]) + (a[11] * b[10]) + (a[12] * b[9]) + (a[13] * b[8]) + (a[14] * b[7]) + (a[15] * b[6]); 114 long c22 = (a[7] * b[15]) + (a[8] * b[14]) + (a[9] * b[13]) + (a[10] * b[12]) + (a[11] * b[11]) + (a[12] * b[10]) + (a[13] * b[9]) + (a[14] * b[8]) + (a[15] * b[7]); 115 long c23 = (a[8] * b[15]) + (a[9] * b[14]) + (a[10] * b[13]) + (a[11] * b[12]) + (a[12] * b[11]) + (a[13] * b[10]) + (a[14] * b[9]) + (a[15] * b[8]); 116 long c24 = (a[9] * b[15]) + (a[10] * b[14]) + (a[11] * b[13]) + (a[12] * b[12]) + (a[13] * b[11]) + (a[14] * b[10]) + (a[15] * b[9]); 117 long c25 = (a[10] * b[15]) + (a[11] * b[14]) + (a[12] * b[13]) + (a[13] * b[12]) + (a[14] * b[11]) + (a[15] * b[10]); 118 long c26 = (a[11] * b[15]) + (a[12] * b[14]) + (a[13] * b[13]) + (a[14] * b[12]) + (a[15] * b[11]); 119 long c27 = (a[12] * b[15]) + (a[13] * b[14]) + (a[14] * b[13]) + (a[15] * b[12]); 120 long c28 = (a[13] * b[15]) + (a[14] * b[14]) + (a[15] * b[13]); 121 long c29 = (a[14] * b[15]) + (a[15] * b[14]); 122 long c30 = (a[15] * b[15]); 123 124 carryReduce(r, c0, c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12, 125 c13, c14, c15, c16, c17, c18, c19, c20, c21, c22, c23, c24, c25, 126 c26, c27, c28, c29, c30); 127 } 128 carryReduce(long[] r, long c0, long c1, long c2, long c3, long c4, long c5, long c6, long c7, long c8, long c9, long c10, long c11, long c12, long c13, long c14, long c15, long c16, long c17, long c18, long c19, long c20, long c21, long c22, long c23, long c24, long c25, long c26, long c27, long c28, long c29, long c30)129 private void carryReduce(long[] r, long c0, long c1, long c2, long c3, 130 long c4, long c5, long c6, long c7, long c8, 131 long c9, long c10, long c11, long c12, long c13, 132 long c14, long c15, long c16, long c17, long c18, 133 long c19, long c20, long c21, long c22, long c23, 134 long c24, long c25, long c26, long c27, long c28, 135 long c29, long c30) { 136 137 // reduce(8, 7) 138 c8 += c24; 139 c16 += c24; 140 141 c9 += c25; 142 c17 += c25; 143 144 c10 += c26; 145 c18 += c26; 146 147 c11 += c27; 148 c19 += c27; 149 150 c12 += c28; 151 c20 += c28; 152 153 c13 += c29; 154 c21 += c29; 155 156 c14 += c30; 157 c22 += c30; 158 159 // reduce(4, 4) 160 r[4] = c4 + c20; 161 r[12] = c12 + c20; 162 163 r[5] = c5 + c21; 164 r[13] = c13 + c21; 165 166 r[6] = c6 + c22; 167 c14 += c22; 168 169 r[7] = c7 + c23; 170 c15 += c23; 171 172 //carry(14, 2) 173 long carry14 = carryValue(c14); 174 r[14] = c14 - (carry14 << BITS_PER_LIMB); 175 c15 += carry14; 176 177 long carry15 = carryValue(c15); 178 r[15] = c15 - (carry15 << BITS_PER_LIMB); 179 c16 += carry15; 180 181 // reduce(0, 4) 182 r[0] = c0 + c16; 183 r[8] = c8 + c16; 184 185 r[1] = c1 + c17; 186 r[9] = c9 + c17; 187 188 r[2] = c2 + c18; 189 r[10] = c10 + c18; 190 191 r[3] = c3 + c19; 192 r[11] = c11 + c19; 193 194 // carry(0, 15) 195 carry(r, 0, 15); 196 } 197 198 @Override square(long[] a, long[] r)199 protected void square(long[] a, long[] r) { 200 201 // Use grade-school multiplication with a simple squaring optimization. 202 // Multiply into primitives to avoid the temporary array allocation. 203 // This is equivalent to the following code: 204 // long[] c = new long[2 * NUM_LIMBS - 1]; 205 // for(int i = 0; i < NUM_LIMBS; i++) { 206 // c[2 * i] = a[i] * a[i]; 207 // for(int j = i + 1; j < NUM_LIMBS; j++) { 208 // c[i + j] += 2 * a[i] * a[j] 209 // } 210 // } 211 212 long c0 = a[0] * a[0]; 213 long c1 = 2 * a[0] * a[1]; 214 long c2 = a[1] * a[1] + 2 * a[0] * a[2]; 215 long c3 = 2 * (a[0] * a[3] + a[1] * a[2]); 216 long c4 = a[2] * a[2] + 2 * (a[0] * a[4] + a[1] * a[3]); 217 long c5 = 2 * (a[0] * a[5] + a[1] * a[4] + a[2] * a[3]); 218 long c6 = a[3] * a[3] + 2 * (a[0] * a[6] + a[1] * a[5] + a[2] * a[4]); 219 long c7 = 2 * (a[0] * a[7] + a[1] * a[6] + a[2] * a[5] + a[3] * a[4]); 220 long c8 = a[4] * a[4] + 2 * (a[0] * a[8] + a[1] * a[7] + a[2] * a[6] + a[3] * a[5]); 221 long c9 = 2 * (a[0] * a[9] + a[1] * a[8] + a[2] * a[7] + a[3] * a[6] + a[4] * a[5]); 222 long c10 = a[5] * a[5] + 2 * (a[0] * a[10] + a[1] * a[9] + a[2] * a[8] + a[3] * a[7] + a[4] * a[6]); 223 long c11 = 2 * (a[0] * a[11] + a[1] * a[10] + a[2] * a[9] + a[3] * a[8] + a[4] * a[7] + a[5] * a[6]); 224 long c12 = a[6] * a[6] + 2 * (a[0] * a[12] + a[1] * a[11] + a[2] * a[10] + a[3] * a[9] + a[4] * a[8] + a[5] * a[7]); 225 long c13 = 2 * (a[0] * a[13] + a[1] * a[12] + a[2] * a[11] + a[3] * a[10] + a[4] * a[9] + a[5] * a[8] + a[6] * a[7]); 226 long c14 = a[7] * a[7] + 2 * (a[0] * a[14] + a[1] * a[13] + a[2] * a[12] + a[3] * a[11] + a[4] * a[10] + a[5] * a[9] + a[6] * a[8]); 227 long c15 = 2 * (a[0] * a[15] + a[1] * a[14] + a[2] * a[13] + a[3] * a[12] + a[4] * a[11] + a[5] * a[10] + a[6] * a[9] + a[7] * a[8]); 228 long c16 = a[8] * a[8] + 2 * (a[1] * a[15] + a[2] * a[14] + a[3] * a[13] + a[4] * a[12] + a[5] * a[11] + a[6] * a[10] + a[7] * a[9]); 229 long c17 = 2 * (a[2] * a[15] + a[3] * a[14] + a[4] * a[13] + a[5] * a[12] + a[6] * a[11] + a[7] * a[10] + a[8] * a[9]); 230 long c18 = a[9] * a[9] + 2 * (a[3] * a[15] + a[4] * a[14] + a[5] * a[13] + a[6] * a[12] + a[7] * a[11] + a[8] * a[10]); 231 long c19 = 2 * (a[4] * a[15] + a[5] * a[14] + a[6] * a[13] + a[7] * a[12] + a[8] * a[11] + a[9] * a[10]); 232 long c20 = a[10] * a[10] + 2 * (a[5] * a[15] + a[6] * a[14] + a[7] * a[13] + a[8] * a[12] + a[9] * a[11]); 233 long c21 = 2 * (a[6] * a[15] + a[7] * a[14] + a[8] * a[13] + a[9] * a[12] + a[10] * a[11]); 234 long c22 = a[11] * a[11] + 2 * (a[7] * a[15] + a[8] * a[14] + a[9] * a[13] + a[10] * a[12]); 235 long c23 = 2 * (a[8] * a[15] + a[9] * a[14] + a[10] * a[13] + a[11] * a[12]); 236 long c24 = a[12] * a[12] + 2 * (a[9] * a[15] + a[10] * a[14] + a[11] * a[13]); 237 long c25 = 2 * (a[10] * a[15] + a[11] * a[14] + a[12] * a[13]); 238 long c26 = a[13] * a[13] + 2 * (a[11] * a[15] + a[12] * a[14]); 239 long c27 = 2 * (a[12] * a[15] + a[13] * a[14]); 240 long c28 = a[14] * a[14] + 2 * a[13] * a[15]; 241 long c29 = 2 * a[14] * a[15]; 242 long c30 = a[15] * a[15]; 243 244 carryReduce(r, c0, c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12, 245 c13, c14, c15, c16, c17, c18, c19, c20, c21, c22, c23, c24, c25, 246 c26, c27, c28, c29, c30); 247 248 } 249 250 251 } 252