1 package org.bouncycastle.pqc.math.linearalgebra; 2 3 import java.security.SecureRandom; 4 5 import org.bouncycastle.crypto.CryptoServicesRegistrar; 6 7 /** 8 * This class describes operations with elements from the finite field F = 9 * GF(2^m). ( GF(2^m)= GF(2)[A] where A is a root of irreducible polynomial with 10 * degree m, each field element B has a polynomial basis representation, i.e. it 11 * is represented by a different binary polynomial of degree less than m, B = 12 * poly(A) ) All operations are defined only for field with 1< m <32. For the 13 * representation of field elements the map f: F->Z, poly(A)->poly(2) is used, 14 * where integers have the binary representation. For example: A^7+A^3+A+1 -> 15 * (00...0010001011)=139 Also for elements type Integer is used. 16 * 17 * @see PolynomialRingGF2 18 */ 19 public class GF2mField 20 { 21 22 /* 23 * degree - degree of the field polynomial - the field polynomial ring - 24 * polynomial ring over the finite field GF(2) 25 */ 26 27 private int degree = 0; 28 29 private int polynomial; 30 31 /** 32 * create a finite field GF(2^m) 33 * 34 * @param degree the degree of the field 35 */ GF2mField(int degree)36 public GF2mField(int degree) 37 { 38 if (degree >= 32) 39 { 40 throw new IllegalArgumentException( 41 " Error: the degree of field is too large "); 42 } 43 if (degree < 1) 44 { 45 throw new IllegalArgumentException( 46 " Error: the degree of field is non-positive "); 47 } 48 this.degree = degree; 49 polynomial = PolynomialRingGF2.getIrreduciblePolynomial(degree); 50 } 51 52 /** 53 * create a finite field GF(2^m) with the fixed field polynomial 54 * 55 * @param degree the degree of the field 56 * @param poly the field polynomial 57 */ GF2mField(int degree, int poly)58 public GF2mField(int degree, int poly) 59 { 60 if (degree != PolynomialRingGF2.degree(poly)) 61 { 62 throw new IllegalArgumentException( 63 " Error: the degree is not correct"); 64 } 65 if (!PolynomialRingGF2.isIrreducible(poly)) 66 { 67 throw new IllegalArgumentException( 68 " Error: given polynomial is reducible"); 69 } 70 this.degree = degree; 71 polynomial = poly; 72 73 } 74 GF2mField(byte[] enc)75 public GF2mField(byte[] enc) 76 { 77 if (enc.length != 4) 78 { 79 throw new IllegalArgumentException( 80 "byte array is not an encoded finite field"); 81 } 82 polynomial = LittleEndianConversions.OS2IP(enc); 83 if (!PolynomialRingGF2.isIrreducible(polynomial)) 84 { 85 throw new IllegalArgumentException( 86 "byte array is not an encoded finite field"); 87 } 88 89 degree = PolynomialRingGF2.degree(polynomial); 90 } 91 GF2mField(GF2mField field)92 public GF2mField(GF2mField field) 93 { 94 degree = field.degree; 95 polynomial = field.polynomial; 96 } 97 98 /** 99 * return degree of the field 100 * 101 * @return degree of the field 102 */ getDegree()103 public int getDegree() 104 { 105 return degree; 106 } 107 108 /** 109 * return the field polynomial 110 * 111 * @return the field polynomial 112 */ getPolynomial()113 public int getPolynomial() 114 { 115 return polynomial; 116 } 117 118 /** 119 * return the encoded form of this field 120 * 121 * @return the field in byte array form 122 */ getEncoded()123 public byte[] getEncoded() 124 { 125 return LittleEndianConversions.I2OSP(polynomial); 126 } 127 128 /** 129 * Return sum of two elements 130 * 131 * @param a 132 * @param b 133 * @return a+b 134 */ add(int a, int b)135 public int add(int a, int b) 136 { 137 return a ^ b; 138 } 139 140 /** 141 * Return product of two elements 142 * 143 * @param a 144 * @param b 145 * @return a*b 146 */ mult(int a, int b)147 public int mult(int a, int b) 148 { 149 return PolynomialRingGF2.modMultiply(a, b, polynomial); 150 } 151 152 /** 153 * compute exponentiation a^k 154 * 155 * @param a a field element a 156 * @param k k degree 157 * @return a^k 158 */ exp(int a, int k)159 public int exp(int a, int k) 160 { 161 if (k == 0) 162 { 163 return 1; 164 } 165 if (a == 0) 166 { 167 return 0; 168 } 169 if (a == 1) 170 { 171 return 1; 172 } 173 int result = 1; 174 if (k < 0) 175 { 176 a = inverse(a); 177 k = -k; 178 } 179 while (k != 0) 180 { 181 if ((k & 1) == 1) 182 { 183 result = mult(result, a); 184 } 185 a = mult(a, a); 186 k >>>= 1; 187 } 188 return result; 189 } 190 191 /** 192 * compute the multiplicative inverse of a 193 * 194 * @param a a field element a 195 * @return a<sup>-1</sup> 196 */ inverse(int a)197 public int inverse(int a) 198 { 199 int d = (1 << degree) - 2; 200 201 return exp(a, d); 202 } 203 204 /** 205 * compute the square root of an integer 206 * 207 * @param a a field element a 208 * @return a<sup>1/2</sup> 209 */ sqRoot(int a)210 public int sqRoot(int a) 211 { 212 for (int i = 1; i < degree; i++) 213 { 214 a = mult(a, a); 215 } 216 return a; 217 } 218 219 /** 220 * create a random field element using PRNG sr 221 * 222 * @param sr SecureRandom 223 * @return a random element 224 */ getRandomElement(SecureRandom sr)225 public int getRandomElement(SecureRandom sr) 226 { 227 int result = RandUtils.nextInt(sr, 1 << degree); 228 return result; 229 } 230 231 /** 232 * create a random non-zero field element 233 * 234 * @return a random element 235 */ getRandomNonZeroElement()236 public int getRandomNonZeroElement() 237 { 238 return getRandomNonZeroElement(CryptoServicesRegistrar.getSecureRandom()); 239 } 240 241 /** 242 * create a random non-zero field element using PRNG sr 243 * 244 * @param sr SecureRandom 245 * @return a random non-zero element 246 */ getRandomNonZeroElement(SecureRandom sr)247 public int getRandomNonZeroElement(SecureRandom sr) 248 { 249 int controltime = 1 << 20; 250 int count = 0; 251 int result = RandUtils.nextInt(sr, 1 << degree); 252 while ((result == 0) && (count < controltime)) 253 { 254 result = RandUtils.nextInt(sr, 1 << degree); 255 count++; 256 } 257 if (count == controltime) 258 { 259 result = 1; 260 } 261 return result; 262 } 263 264 /** 265 * @return true if e is encoded element of this field and false otherwise 266 */ isElementOfThisField(int e)267 public boolean isElementOfThisField(int e) 268 { 269 // e is encoded element of this field iff 0<= e < |2^m| 270 if (degree == 31) 271 { 272 return e >= 0; 273 } 274 return e >= 0 && e < (1 << degree); 275 } 276 277 /* 278 * help method for visual control 279 */ elementToStr(int a)280 public String elementToStr(int a) 281 { 282 String s = ""; 283 for (int i = 0; i < degree; i++) 284 { 285 if (((byte)a & 0x01) == 0) 286 { 287 s = "0" + s; 288 } 289 else 290 { 291 s = "1" + s; 292 } 293 a >>>= 1; 294 } 295 return s; 296 } 297 298 /** 299 * checks if given object is equal to this field. 300 * <p> 301 * The method returns false whenever the given object is not GF2m. 302 * 303 * @param other object 304 * @return true or false 305 */ equals(Object other)306 public boolean equals(Object other) 307 { 308 if ((other == null) || !(other instanceof GF2mField)) 309 { 310 return false; 311 } 312 313 GF2mField otherField = (GF2mField)other; 314 315 if ((degree == otherField.degree) 316 && (polynomial == otherField.polynomial)) 317 { 318 return true; 319 } 320 321 return false; 322 } 323 hashCode()324 public int hashCode() 325 { 326 return polynomial; 327 } 328 329 /** 330 * Returns a human readable form of this field. 331 * 332 * @return a human readable form of this field. 333 */ toString()334 public String toString() 335 { 336 String str = "Finite Field GF(2^" + degree + ") = " + "GF(2)[X]/<" 337 + polyToString(polynomial) + "> "; 338 return str; 339 } 340 polyToString(int p)341 private static String polyToString(int p) 342 { 343 String str = ""; 344 if (p == 0) 345 { 346 str = "0"; 347 } 348 else 349 { 350 byte b = (byte)(p & 0x01); 351 if (b == 1) 352 { 353 str = "1"; 354 } 355 p >>>= 1; 356 int i = 1; 357 while (p != 0) 358 { 359 b = (byte)(p & 0x01); 360 if (b == 1) 361 { 362 str = str + "+x^" + i; 363 } 364 p >>>= 1; 365 i++; 366 } 367 } 368 return str; 369 } 370 371 } 372