_ Git - BoarSSL/blob - Crypto/BigInt.cs

   1 /*
   2  * Copyright (c) 2017 Thomas Pornin <pornin@bolet.org>
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining
   5  * a copy of this software and associated documentation files (the
   6  * "Software"), to deal in the Software without restriction, including
   7  * without limitation the rights to use, copy, modify, merge, publish,
   8  * distribute, sublicense, and/or sell copies of the Software, and to
   9  * permit persons to whom the Software is furnished to do so, subject to
  10  * the following conditions:
  11  *
  12  * The above copyright notice and this permission notice shall be
  13  * included in all copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  16  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  17  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  18  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  19  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  20  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  21  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  22  * SOFTWARE.
  23  */
  24
  25 using System;
  26
  27 namespace Crypto {
  28
  29 /*
  30  * Helper methods for handling big integers.
  31  */
  32
  33 static class BigInt {
  34
  35         /*
  36          * Normalize a big integer to its minimal size encoding
  37          * (unsigned big-endian). This function always returns
  38          * a new, fresh array.
  39          */
  40         internal static byte[] NormalizeBE(byte[] val)
  41         {
  42                 return NormalizeBE(val, false);
  43         }
  44
  45         /*
  46          * Normalize a big integer to its minimal size encoding
  47          * (big-endian). If 'signed' is true, then room for a sign
  48          * bit (of value 0) is kept. Note that even if 'signed' is
  49          * true, the source array is assumed positive (i.e. unsigned).
  50          * This function always returns a new, fresh array.
  51          */
  52         internal static byte[] NormalizeBE(byte[] val, bool signed)
  53         {
  54                 int n = val.Length;
  55                 int i = 0;
  56                 while (i < n && val[i] == 0) {
  57                         i ++;
  58                 }
  59                 if (signed && (i == n || val[i] >= 0x80)) {
  60                         i --;
  61                 }
  62                 byte[] nval = new byte[n - i];
  63                 if (i < 0) {
  64                         Array.Copy(val, 0, nval, 1, n);
  65                 } else {
  66                         Array.Copy(val, i, nval, 0, n - i);
  67                 }
  68                 return nval;
  69         }
  70
  71         /*
  72          * Compute the exact bit length of an integer (unsigned big-endian
  73          * encoding).
  74          */
  75         internal static int BitLength(byte[] val)
  76         {
  77                 return BitLength(val, 0, val.Length);
  78         }
  79
  80         /*
  81          * Compute the exact bit length of an integer (unsigned big-endian
  82          * encoding).
  83          */
  84         internal static int BitLength(byte[] val, int off, int len)
  85         {
  86                 int tlen = 0;
  87                 uint hb = 0;
  88                 uint nf = ~(uint)0;
  89                 for (int i = 0; i < len; i ++) {
  90                         int b = (int)(val[off + i] & nf);
  91                         uint bnz = nf & (uint)((b | -b) >> 31);
  92                         tlen |= (int)bnz & (len - i);
  93                         hb |= bnz & (uint)b;
  94                         nf &= ~bnz;
  95                 }
  96                 return (tlen << 3) - 8 + BitLength(hb);
  97         }
  98
  99         /*
 100          * Compute the exact bit length of an integer (in a 32-bit word).
 101          */
 102         internal static int BitLength(uint w)
 103         {
 104                 int bitLen = 0;
 105                 for (int f = 16; f > 0; f >>= 1) {
 106                         uint nw = w >> f;
 107                         int x = (int)nw;
 108                         uint ctl = (uint)((x | -x) >> 31);
 109                         w = (w & ~ctl) | (nw & ctl);
 110                         bitLen += f & (int)ctl;
 111                 }
 112                 return bitLen + (int)w;
 113         }
 114
 115         /*
 116          * Compute a simple hashcode on an integer. The returned value
 117          * depends on the numerical value (assuming that the array is
 118          * in unsigned big-endian representation) but not on the presence
 119          * of leading zeros. The memory access pattern of this method
 120          * depends only on the length of the array x.
 121          */
 122         public static uint HashInt(byte[] x)
 123         {
 124                 /*
 125                  * We simply compute x modulo 4294967291 (0xFFFFFFFB),
 126                  * which is a prime number. The value is injected byte
 127                  * by byte, and we keep the running state on two words
 128                  * (16 bits per word, but we allow a few extra bits of
 129                  * carry).
 130                  *
 131                  * For all iterations, "hi" contains at most 16 bits,
 132                  * and "lo" is less than 16*2^16 (i.e. it fits on 20 bits).
 133                  */
 134                 uint hi = 0, lo = 0;
 135                 for (int i = 0; i < x.Length; i ++) {
 136                         hi = (hi << 8) + (lo >> 8);
 137                         lo = (lo & 0xFF) << 8;
 138                         lo += (uint)5 * (hi >> 16) + (uint)x[i];
 139                         hi &= 0xFFFF;
 140                 }
 141
 142                 /*
 143                  * Final reduction. We first propagate the extra bits
 144                  * from the low word, which may induce one extra bit
 145                  * on the high word, which we propagate back.
 146                  */
 147                 hi += (lo >> 16);
 148                 lo &= 0xFFFF;
 149                 lo += (uint)5 * (hi >> 16);
 150                 hi &= 0xFFFF;
 151
 152                 /*
 153                  * If we have extra bits at that point, then this means
 154                  * that adding a 4-bits-or-less value to "hi" implied
 155                  * a carry, so now "hi" is small and the addition below
 156                  * won't imply a carry.
 157                  */
 158                 hi += (lo >> 16);
 159                 lo &= 0xFFFF;
 160
 161                 /*
 162                  * At that point, value is on 32 bits. We want to do a
 163                  * final reduction for 0xFFFFFFFB..0xFFFFFFFF. Value is
 164                  * in this range if and only if 'hi' is 0xFFFF and 'lo'
 165                  * is at least 0xFFFB.
 166                  */
 167                 int z = (int)(((hi + 1) >> 16) | ((lo + 5) >> 16));
 168                 return (hi << 16) + lo + ((uint)5 & (uint)((z | -z) >> 31));
 169         }
 170
 171         /*
 172          * Add two integers together. The two operands a[] and b[]
 173          * use big-endian encoding. The returned product array is newly
 174          * allocated and normalized. The operands are not modified. The
 175          * operands need not be normalized and may be the same array.
 176          */
 177         public static byte[] Add(byte[] a, byte[] b)
 178         {
 179                 int aLen = a.Length;
 180                 int bLen = b.Length;
 181                 int xLen = Math.Max(aLen, bLen) + 1;
 182                 byte[] x = new byte[xLen];
 183                 int cc = 0;
 184                 for (int i = 0; i < xLen; i ++) {
 185                         int wa = (i < aLen) ? (int)a[aLen - 1 - i] : 0;
 186                         int wb = (i < bLen) ? (int)b[bLen - 1 - i] : 0;
 187                         int wx = wa + wb + cc;
 188                         x[xLen - 1 - i] = (byte)wx;
 189                         cc = wx >> 8;
 190                 }
 191                 return NormalizeBE(x);
 192         }
 193
 194         /*
 195          * Subtract integer b[] from integer a[]. Both operands use
 196          * big-endian encoding. If b[] turns out to be greater than a[],
 197          * then this method returns null.
 198          */
 199         public static byte[] Sub(byte[] a, byte[] b)
 200         {
 201                 int aLen = a.Length;
 202                 int bLen = b.Length;
 203                 int xLen = Math.Max(aLen, bLen);
 204                 byte[] x = new byte[aLen];
 205                 int cc = 0;
 206                 for (int i = 0; i < xLen; i ++) {
 207                         int wa = (i < aLen) ? (int)a[aLen - 1 - i] : 0;
 208                         int wb = (i < bLen) ? (int)b[bLen - 1 - i] : 0;
 209                         int wx = wa - wb - cc;
 210                         x[xLen - 1 - i] = (byte)wx;
 211                         cc = (wx >> 8) & 1;
 212                 }
 213                 if (cc != 0) {
 214                         return null;
 215                 }
 216                 return NormalizeBE(x);
 217         }
 218
 219         /*
 220          * Multiply two integers together. The two operands a[] and b[]
 221          * use big-endian encoding. The returned product array is newly
 222          * allocated and normalized. The operands are not modified. The
 223          * operands need not be normalized and may be the same array.
 224          *
 225          * The two source operands MUST NOT have length larger than
 226          * 32767 bytes.
 227          */
 228         public static byte[] Mul(byte[] a, byte[] b)
 229         {
 230                 a = NormalizeBE(a);
 231                 b = NormalizeBE(b);
 232                 if (a.Length > 32767 || b.Length > 32767) {
 233                         throw new CryptoException(
 234                                 "Operands too large for multiplication");
 235                 }
 236                 int aLen = a.Length;
 237                 int bLen = b.Length;
 238                 int xLen = aLen + bLen;
 239                 uint[] x = new uint[xLen];
 240                 for (int i = 0; i < aLen; i ++) {
 241                         uint u = (uint)a[aLen - 1 - i];
 242                         for (int j = 0; j < bLen; j ++) {
 243                                 x[i + j] += u * (uint)b[bLen - 1 - j];
 244                         }
 245                 }
 246                 byte[] y = new byte[xLen];
 247                 uint cc = 0;
 248                 for (int i = 0; i < xLen; i ++) {
 249                         uint w = x[i] + cc;
 250                         y[xLen - 1 - i] = (byte)w;
 251                         cc = w >> 8;
 252                 }
 253                 if (cc != 0) {
 254                         throw new CryptoException(
 255                                 "Multiplication: internal error");
 256                 }
 257                 return NormalizeBE(y);
 258         }
 259
 260         /*
 261          * Compare two integers (unsigned, big-endian). Returned value
 262          * is -1, 0 or 1, depending on whether a[] is lower than, equal
 263          * to, or greater then b[]. a[] and b[] may have distinct sizes.
 264          *
 265          * Memory access pattern depends on the most significant index
 266          * (i.e. lowest index, since we use big-endian convention) for
 267          * which the two values differ.
 268          */
 269         public static int Compare(byte[] a, byte[] b)
 270         {
 271                 int na = a.Length;
 272                 int nb = b.Length;
 273                 for (int i = Math.Max(a.Length, b.Length); i > 0; i --) {
 274                         byte xa = (i > na) ? (byte)0x00 : a[na - i];
 275                         byte xb = (i > nb) ? (byte)0x00 : b[nb - i];
 276                         if (xa != xb) {
 277                                 return xa < xb ? -1 : 1;
 278                         }
 279                 }
 280                 return 0;
 281         }
 282
 283         /*
 284          * Compare two integers (unsigned, big-endian). Returned value
 285          * is -1, 0 or 1, depending on whether a[] is lower than, equal
 286          * to, or greater then b[]. a[] and b[] may have distinct sizes.
 287          *
 288          * This method's memory access pattern is independent of the
 289          * contents of the a[] and b[] arrays.
 290          */
 291         public static int CompareCT(byte[] a, byte[] b)
 292         {
 293                 int na = a.Length;
 294                 int nb = b.Length;
 295                 uint lt = 0;
 296                 uint gt = 0;
 297                 for (int i = Math.Max(a.Length, b.Length); i > 0; i --) {
 298                         int xa = (i > na) ? 0 : a[na - i];
 299                         int xb = (i > nb) ? 0 : b[nb - i];
 300                         lt |= (uint)((xa - xb) >> 31) & ~(lt | gt);
 301                         gt |= (uint)((xb - xa) >> 31) & ~(lt | gt);
 302                 }
 303                 return (int)lt | -(int)gt;
 304         }
 305
 306         /*
 307          * Check whether an integer (unsigned, big-endian) is zero.
 308          */
 309         public static bool IsZero(byte[] x)
 310         {
 311                 return IsZeroCT(x) != 0;
 312         }
 313
 314         /*
 315          * Check whether an integer (unsigned, big-endian) is zero.
 316          * Memory access pattern depends only on the length of x[].
 317          * Returned value is 0xFFFFFFFF is the value is zero, 0x00000000
 318          * otherwise.
 319          */
 320         public static uint IsZeroCT(byte[] x)
 321         {
 322                 int z = 0;
 323                 for (int i = 0; i < x.Length; i ++) {
 324                         z |= x[i];
 325                 }
 326                 return ~(uint)((z | -z) >> 31);
 327         }
 328
 329         /*
 330          * Check whether an integer (unsigned, big-endian) is one.
 331          */
 332         public static bool IsOne(byte[] x)
 333         {
 334                 return IsOneCT(x) != 0;
 335         }
 336
 337         /*
 338          * Check whether an integer (unsigned, big-endian) is one.
 339          * Memory access pattern depends only on the length of x[].
 340          * Returned value is 0xFFFFFFFF is the value is one, 0x00000000
 341          * otherwise.
 342          */
 343         public static uint IsOneCT(byte[] x)
 344         {
 345                 int n = x.Length;
 346                 if (n == 0) {
 347                         return 0x00000000;
 348                 }
 349                 int z = 0;
 350                 for (int i = 0; i < n - 1; i ++) {
 351                         z |= x[i];
 352                 }
 353                 z |= x[n - 1] - 1;
 354                 return ~(uint)((z | -z) >> 31);
 355         }
 356
 357         /*
 358          * Check whether the provided integer is odd (the source integer
 359          * is in unsigned big-endian notation).
 360          */
 361         public static bool IsOdd(byte[] x)
 362         {
 363                 return x.Length > 0 && (x[x.Length - 1] & 0x01) != 0;
 364         }
 365
 366         /*
 367          * Compute a modular exponentiation (x^e mod n). Conditions:
 368          * -- x[], e[] and n[] use big-endian encoding.
 369          * -- x[] must be numerically smaller than n[].
 370          * -- n[] must be odd.
 371          * Result is returned as a newly allocated array of bytes of
 372          * the same length as n[].
 373          */
 374         public static byte[] ModPow(byte[] x, byte[] e, byte[] n)
 375         {
 376                 ModInt mx = new ModInt(n);
 377                 mx.Decode(x);
 378                 mx.Pow(e);
 379                 return mx.Encode();
 380         }
 381
 382         /*
 383          * Create a new random integer, chosen uniformly among integers
 384          * modulo the provided max[].
 385          */
 386         public static byte[] RandInt(byte[] max)
 387         {
 388                 return RandInt(max, false);
 389         }
 390
 391         /*
 392          * Create a new random integer, chosen uniformly among non-zero
 393          * integers modulo the provided max[].
 394          */
 395         public static byte[] RandIntNZ(byte[] max)
 396         {
 397                 return RandInt(max, true);
 398         }
 399
 400         static byte[] RandInt(byte[] max, bool notZero)
 401         {
 402                 int mlen = BitLength(max);
 403                 if (mlen == 0 || (notZero && mlen == 1)) {
 404                         throw new CryptoException(
 405                                 "Null maximum for random generation");
 406                 }
 407                 byte[] x = new byte[(mlen + 7) >> 3];
 408                 byte hm = (byte)(0xFF >> ((8 - mlen) & 7));
 409                 for (;;) {
 410                         RNG.GetBytes(x);
 411                         x[0] &= hm;
 412                         if (notZero && IsZero(x)) {
 413                                 continue;
 414                         }
 415                         if (CompareCT(x, max) >= 0) {
 416                                 continue;
 417                         }
 418                         return x;
 419                 }
 420         }
 421
 422         /*
 423          * Create a new random prime with a specific length (in bits). The
 424          * returned prime will have its two top bits set, _and_ its two
 425          * least significant bits set as well. The size parameter must be
 426          * greater than or equal to 9 (that is, the unsigned encoding of
 427          * the prime will need at least two bytes).
 428          */
 429         public static byte[] RandPrime(int size)
 430         {
 431                 if (size < 9) {
 432                         throw new CryptoException(
 433                                 "Invalid size for prime generation");
 434                 }
 435                 int len = (size + 7) >> 3;
 436                 byte[] buf = new byte[len];
 437                 int hm1 = 0xFFFF >> ((len << 3) - size);
 438                 int hm2 = 0xC000 >> ((len << 3) - size);
 439                 for (;;) {
 440                         RNG.GetBytes(buf);
 441                         buf[len - 1] |= (byte)0x03;
 442                         int x = (buf[0] << 8) | buf[1];
 443                         x &= hm1;
 444                         x |= hm2;
 445                         buf[0] = (byte)(x >> 8);
 446                         buf[1] = (byte)x;
 447                         if (IsPrime(buf)) {
 448                                 return buf;
 449                         }
 450                 }
 451         }
 452
 453         /*
 454          * A bit-field for primes in the 0..255 range.
 455          */
 456         static uint[] SMALL_PRIMES_BF = {
 457                 0xA08A28AC, 0x28208A20, 0x02088288, 0x800228A2,
 458                 0x20A00A08, 0x80282088, 0x800800A2, 0x08028228
 459         };
 460
 461         static bool IsSmallPrime(int x)
 462         {
 463                 if (x < 2 || x >= 256) {
 464                         return false;
 465                 }
 466                 return ((SMALL_PRIMES_BF[x >> 5] >> (x & 31)) & (uint)1) != 0;
 467         }
 468
 469         /*
 470          * Test an integer for primality. This function runs up to 50
 471          * Miller-Rabin rounds, which is a lot of overkill but ensures
 472          * that non-primes will be reliably detected (with overwhelming
 473          * probability) even with maliciously crafted inputs. "Normal"
 474          * non-primes will be detected most of the time at the first
 475          * iteration.
 476          *
 477          * This function is not constant-time.
 478          */
 479         public static bool IsPrime(byte[] x)
 480         {
 481                 x = NormalizeBE(x);
 482
 483                 /*
 484                  * Handle easy cases:
 485                  *   0 is not prime
 486                  *   small primes (one byte) are known in a constant bit-field
 487                  *   even numbers (larger than one byte) are non-primes
 488                  */
 489                 if (x.Length == 0) {
 490                         return false;
 491                 }
 492                 if (x.Length == 1) {
 493                         return IsSmallPrime(x[0]);
 494                 }
 495                 if ((x[x.Length - 1] & 0x01) == 0) {
 496                         return false;
 497                 }
 498
 499                 /*
 500                  * Perform some trial divisions by small primes.
 501                  */
 502                 for (int sp = 3; sp < 256; sp += 2) {
 503                         if (!IsSmallPrime(sp)) {
 504                                 continue;
 505                         }
 506                         int z = 0;
 507                         foreach (byte b in x) {
 508                                 z = ((z << 8) + b) % sp;
 509                         }
 510                         if (z == 0) {
 511                                 return false;
 512                         }
 513                 }
 514
 515                 /*
 516                  * Run some Miller-Rabin rounds. We use as basis random
 517                  * integers that are one byte smaller than the modulus.
 518                  */
 519                 ModInt xm1 = new ModInt(x);
 520                 ModInt y = xm1.Dup();
 521                 y.Set(1);
 522                 xm1.Sub(y);
 523                 byte[] e = xm1.Encode();
 524                 ModInt a = new ModInt(x);
 525                 byte[] buf = new byte[x.Length - 1];
 526                 for (int i = 0; i < 50; i ++) {
 527                         RNG.GetBytes(buf);
 528                         a.Decode(buf);
 529                         a.Pow(e);
 530                         if (!a.IsOne) {
 531                                 return false;
 532                         }
 533                 }
 534                 return true;
 535         }
 536
 537         /*
 538          * Right-shift an array of bytes by some bits. The bit count MUST
 539          * be positive or zero. Extra bits are dropped on the right, and
 540          * left positions are filled with zeros.
 541          */
 542         public static void RShift(byte[] buf, int numBits)
 543         {
 544                 RShift(buf, 0, buf.Length, numBits);
 545         }
 546
 547         /*
 548          * Right-shift an array of bytes by some bits. The bit count MUST
 549          * be positive or zero. Extra bits are dropped on the right, and
 550          * left positions are filled with zeros.
 551          */
 552         public static void RShift(byte[] buf, int off, int len, int numBits)
 553         {
 554                 if (numBits >= 8) {
 555                         int zlen = numBits >> 3;
 556                         if (zlen >= len) {
 557                                 for (int i = 0; i < len; i ++) {
 558                                         buf[off + i] = 0;
 559                                 }
 560                                 return;
 561                         }
 562                         Array.Copy(buf, off, buf, off + zlen, len - zlen);
 563                         for (int i = 0; i < zlen; i ++) {
 564                                 buf[off + i] = 0;
 565                         }
 566                         off += zlen;
 567                         len -= zlen;
 568                         numBits &= 7;
 569                 }
 570
 571                 int cc = 0;
 572                 for (int i = 0; i < len; i ++) {
 573                         int x = buf[off + i];
 574                         buf[off + i] = (byte)((x >> numBits) + cc);
 575                         cc = x << (8 - numBits);
 576                 }
 577         }
 578 }
 579
 580 }