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