drivers/usb/dwc_otg_310/common_port/dwc_modpow.c

   1 /* Bignum routines adapted from PUTTY sources.  PuTTY copyright notice follows.
   2  *
   3  * PuTTY is copyright 1997-2007 Simon Tatham.
   4  *
   5  * Portions copyright Robert de Bath, Joris van Rantwijk, Delian
   6  * Delchev, Andreas Schultz, Jeroen Massar, Wez Furlong, Nicolas Barry,
   7  * Justin Bradford, Ben Harris, Malcolm Smith, Ahmad Khalifa, Markus
   8  * Kuhn, and CORE SDI S.A.
   9  *
  10  * Permission is hereby granted, free of charge, to any person
  11  * obtaining a copy of this software and associated documentation files
  12  * (the "Software"), to deal in the Software without restriction,
  13  * including without limitation the rights to use, copy, modify, merge,
  14  * publish, distribute, sublicense, and/or sell copies of the Software,
  15  * and to permit persons to whom the Software is furnished to do so,
  16  * subject to the following conditions:
  17  *
  18  * The above copyright notice and this permission notice shall be
  19  * included in all copies or substantial portions of the Software.
  20
  21  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  22  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  23  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  24  * NONINFRINGEMENT.  IN NO EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE
  25  * FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
  26  * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  27  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  28  *
  29  */
  30 #ifdef DWC_CRYPTOLIB
  31
  32 #ifndef CONFIG_MACH_IPMATE
  33
  34 #include "dwc_modpow.h"
  35
  36 #define BIGNUM_INT_MASK  0xFFFFFFFFUL
  37 #define BIGNUM_TOP_BIT   0x80000000UL
  38 #define BIGNUM_INT_BITS  32
  39
  40 static void *snmalloc(void *mem_ctx, size_t n, size_t size)
  41 {
  42         void *p;
  43         size *= n;
  44         if (size == 0)
  45                 size = 1;
  46         p = dwc_alloc(mem_ctx, size);
  47         return p;
  48 }
  49
  50 #define snewn(ctx, n, type) ((type *)snmalloc((ctx), (n), sizeof(type)))
  51 #define sfree dwc_free
  52
  53 /*
  54  * Usage notes:
  55  *  * Do not call the DIVMOD_WORD macro with expressions such as array
  56  *    subscripts, as some implementations object to this (see below).
  57  *  * Note that none of the division methods below will cope if the
  58  *    quotient won't fit into BIGNUM_INT_BITS. Callers should be careful
  59  *    to avoid this case.
  60  *    If this condition occurs, in the case of the x86 DIV instruction,
  61  *    an overflow exception will occur, which (according to a correspondent)
  62  *    will manifest on Windows as something like
  63  *      0xC0000095: Integer overflow
  64  *    The C variant won't give the right answer, either.
  65  */
  66
  67 #define MUL_WORD(w1, w2) ((BignumDblInt)w1 * w2)
  68
  69 #if defined __GNUC__ && defined __i386__
  70 #define DIVMOD_WORD(q, r, hi, lo, w) \
  71     __asm__("div %2" : \
  72             "=d" (r), "=a" (q) : \
  73             "r" (w), "d" (hi), "a" (lo))
  74 #else
  75 #define DIVMOD_WORD(q, r, hi, lo, w) do { \
  76     BignumDblInt n = (((BignumDblInt)hi) << BIGNUM_INT_BITS) | lo; \
  77     q = n / w; \
  78     r = n % w; \
  79 } while (0)
  80 #endif
  81
  82 #define BIGNUM_INT_BYTES (BIGNUM_INT_BITS / 8)
  83
  84 #define BIGNUM_INTERNAL
  85
  86 static Bignum newbn(void *mem_ctx, int length)
  87 {
  88         Bignum b = snewn(mem_ctx, length + 1, BignumInt);
  89         /* if (!b) */
  90         /* abort(); */                 /* FIXME */
  91         DWC_MEMSET(b, 0, (length + 1) * sizeof(*b));
  92         b[0] = length;
  93         return b;
  94 }
  95
  96 void freebn(void *mem_ctx, Bignum b)
  97 {
  98         /*
  99          * Burn the evidence, just in case.
 100          */
 101         DWC_MEMSET(b, 0, sizeof(b[0]) * (b[0] + 1));
 102         sfree(mem_ctx, b);
 103 }
 104
 105 /*
 106  * Compute c = a * b.
 107  * Input is in the first len words of a and b.
 108  * Result is returned in the first 2*len words of c.
 109  */
 110 static void internal_mul(BignumInt *a, BignumInt *b, BignumInt *c, int len)
 111 {
 112         int i, j;
 113         BignumDblInt t;
 114
 115         for (j = 0; j < 2 * len; j++)
 116                 c[j] = 0;
 117
 118         for (i = len - 1; i >= 0; i--) {
 119                 t = 0;
 120                 for (j = len - 1; j >= 0; j--) {
 121                         t += MUL_WORD(a[i], (BignumDblInt) b[j]);
 122                         t += (BignumDblInt) c[i + j + 1];
 123                         c[i + j + 1] = (BignumInt) t;
 124                         t = t >> BIGNUM_INT_BITS;
 125                 }
 126                 c[i] = (BignumInt) t;
 127         }
 128 }
 129
 130 static void internal_add_shifted(BignumInt *number, unsigned n, int shift)
 131 {
 132         int word = 1 + (shift / BIGNUM_INT_BITS);
 133         int bshift = shift % BIGNUM_INT_BITS;
 134         BignumDblInt addend;
 135
 136         addend = (BignumDblInt) n << bshift;
 137
 138         while (addend) {
 139                 addend += number[word];
 140                 number[word] = (BignumInt) addend & BIGNUM_INT_MASK;
 141                 addend >>= BIGNUM_INT_BITS;
 142                 word++;
 143         }
 144 }
 145
 146 /*
 147  * Compute a = a % m.
 148  * Input in first alen words of a and first mlen words of m.
 149  * Output in first alen words of a
 150  * (of which first alen-mlen words will be zero).
 151  * The MSW of m MUST have its high bit set.
 152  * Quotient is accumulated in the `quotient' array, which is a Bignum
 153  * rather than the internal bigendian format. Quotient parts are shifted
 154  * left by `qshift' before adding into quot.
 155  */
 156 static void internal_mod(BignumInt *a, int alen,
 157                          BignumInt *m, int mlen, BignumInt *quot, int qshift)
 158 {
 159         BignumInt m0, m1;
 160         unsigned int h;
 161         int i, k;
 162
 163         m0 = m[0];
 164         if (mlen > 1)
 165                 m1 = m[1];
 166         else
 167                 m1 = 0;
 168
 169         for (i = 0; i <= alen - mlen; i++) {
 170                 BignumDblInt t;
 171                 unsigned int q, r, c, ai1;
 172
 173                 if (i == 0) {
 174                         h = 0;
 175                 } else {
 176                         h = a[i - 1];
 177                         a[i - 1] = 0;
 178                 }
 179
 180                 if (i == alen - 1)
 181                         ai1 = 0;
 182                 else
 183                         ai1 = a[i + 1];
 184
 185                 /* Find q = h:a[i] / m0 */
 186                 if (h >= m0) {
 187                         /*
 188                          * Special case.
 189                          *
 190                          * To illustrate it, suppose a BignumInt is 8 bits, and
 191                          * we are dividing (say) A1:23:45:67 by A1:B2:C3. Then
 192                          * our initial division will be 0xA123 / 0xA1, which
 193                          * will give a quotient of 0x100 and a divide overflow.
 194                          * However, the invariants in this division algorithm
 195                          * are not violated, since the full number A1:23:... is
 196                          * _less_ than the quotient prefix A1:B2:... and so the
 197                          * following correction loop would have sorted it out.
 198                          *
 199                          * In this situation we set q to be the largest
 200                          * quotient we _can_ stomach (0xFF, of course).
 201                          */
 202                         q = BIGNUM_INT_MASK;
 203                 } else {
 204                         /* Macro doesn't want an array subscript expression passed
 205                          * into it (see definition), so use a temporary. */
 206                         BignumInt tmplo = a[i];
 207                         DIVMOD_WORD(q, r, h, tmplo, m0);
 208
 209                         /* Refine our estimate of q by looking at
 210                            h:a[i]:a[i+1] / m0:m1 */
 211                         t = MUL_WORD(m1, q);
 212                         if (t > ((BignumDblInt) r << BIGNUM_INT_BITS) + ai1) {
 213                                 q--;
 214                                 t -= m1;
 215                                 r = (r + m0) & BIGNUM_INT_MASK; /* overflow? */
 216                                 if (r >= (BignumDblInt) m0 &&
 217                                     t >
 218                                     ((BignumDblInt) r << BIGNUM_INT_BITS) + ai1)
 219                                         q--;
 220                         }
 221                 }
 222
 223                 /* Subtract q * m from a[i...] */
 224                 c = 0;
 225                 for (k = mlen - 1; k >= 0; k--) {
 226                         t = MUL_WORD(q, m[k]);
 227                         t += c;
 228                         c = (unsigned)(t >> BIGNUM_INT_BITS);
 229                         if ((BignumInt) t > a[i + k])
 230                                 c++;
 231                         a[i + k] -= (BignumInt) t;
 232                 }
 233
 234                 /* Add back m in case of borrow */
 235                 if (c != h) {
 236                         t = 0;
 237                         for (k = mlen - 1; k >= 0; k--) {
 238                                 t += m[k];
 239                                 t += a[i + k];
 240                                 a[i + k] = (BignumInt) t;
 241                                 t = t >> BIGNUM_INT_BITS;
 242                         }
 243                         q--;
 244                 }
 245                 if (quot)
 246                         internal_add_shifted(quot, q,
 247                                              qshift + BIGNUM_INT_BITS * (alen -
 248                                                                          mlen -
 249                                                                          i));
 250         }
 251 }
 252
 253 /*
 254  * Compute p % mod.
 255  * The most significant word of mod MUST be non-zero.
 256  * We assume that the result array is the same size as the mod array.
 257  * We optionally write out a quotient if `quotient' is non-NULL.
 258  * We can avoid writing out the result if `result' is NULL.
 259  */
 260 void bigdivmod(void *mem_ctx, Bignum p, Bignum mod, Bignum result,
 261                Bignum quotient)
 262 {
 263         BignumInt *n, *m;
 264         int mshift;
 265         int plen, mlen, i, j;
 266
 267         /* Allocate m of size mlen, copy mod to m */
 268         /* We use big endian internally */
 269         mlen = mod[0];
 270         m = snewn(mem_ctx, mlen, BignumInt);
 271         /* if (!m) */
 272         /* abort(); */                /* FIXME */
 273         for (j = 0; j < mlen; j++)
 274                 m[j] = mod[mod[0] - j];
 275
 276         /* Shift m left to make msb bit set */
 277         for (mshift = 0; mshift < BIGNUM_INT_BITS - 1; mshift++)
 278                 if ((m[0] << mshift) & BIGNUM_TOP_BIT)
 279                         break;
 280         if (mshift) {
 281                 for (i = 0; i < mlen - 1; i++)
 282                         m[i] =
 283                             (m[i] << mshift) | (m[i + 1] >>
 284                                                 (BIGNUM_INT_BITS - mshift));
 285                 m[mlen - 1] = m[mlen - 1] << mshift;
 286         }
 287
 288         plen = p[0];
 289         /* Ensure plen > mlen */
 290         if (plen <= mlen)
 291                 plen = mlen + 1;
 292
 293         /* Allocate n of size plen, copy p to n */
 294         n = snewn(mem_ctx, plen, BignumInt);
 295         /* if (!n) */
 296         /* abort(); */                /* FIXME */
 297         for (j = 0; j < plen; j++)
 298                 n[j] = 0;
 299         for (j = 1; j <= (int)p[0]; j++)
 300                 n[plen - j] = p[j];
 301
 302         /* Main computation */
 303         internal_mod(n, plen, m, mlen, quotient, mshift);
 304
 305         /* Fixup result in case the modulus was shifted */
 306         if (mshift) {
 307                 for (i = plen - mlen - 1; i < plen - 1; i++)
 308                         n[i] =
 309                             (n[i] << mshift) | (n[i + 1] >>
 310                                                 (BIGNUM_INT_BITS - mshift));
 311                 n[plen - 1] = n[plen - 1] << mshift;
 312                 internal_mod(n, plen, m, mlen, quotient, 0);
 313                 for (i = plen - 1; i >= plen - mlen; i--)
 314                         n[i] =
 315                             (n[i] >> mshift) | (n[i - 1] <<
 316                                                 (BIGNUM_INT_BITS - mshift));
 317         }
 318
 319         /* Copy result to buffer */
 320         if (result) {
 321                 for (i = 1; i <= (int)result[0]; i++) {
 322                         int j = plen - i;
 323                         result[i] = j >= 0 ? n[j] : 0;
 324                 }
 325         }
 326
 327         /* Free temporary arrays */
 328         for (i = 0; i < mlen; i++)
 329                 m[i] = 0;
 330         sfree(mem_ctx, m);
 331         for (i = 0; i < plen; i++)
 332                 n[i] = 0;
 333         sfree(mem_ctx, n);
 334 }
 335
 336 /*
 337  * Simple remainder.
 338  */
 339 Bignum bigmod(void *mem_ctx, Bignum a, Bignum b)
 340 {
 341         Bignum r = newbn(mem_ctx, b[0]);
 342         bigdivmod(mem_ctx, a, b, r, NULL);
 343         return r;
 344 }
 345
 346 /*
 347  * Compute (base ^ exp) % mod.
 348  */
 349 Bignum dwc_modpow(void *mem_ctx, Bignum base_in, Bignum exp, Bignum mod)
 350 {
 351         BignumInt *a, *b, *n, *m;
 352         int mshift;
 353         int mlen, i, j;
 354         Bignum base, result;
 355
 356         /*
 357          * The most significant word of mod needs to be non-zero. It
 358          * should already be, but let's make sure.
 359          */
 360         /* assert(mod[mod[0]] != 0); */
 361
 362         /*
 363          * Make sure the base is smaller than the modulus, by reducing
 364          * it modulo the modulus if not.
 365          */
 366         base = bigmod(mem_ctx, base_in, mod);
 367
 368         /* Allocate m of size mlen, copy mod to m */
 369         /* We use big endian internally */
 370         mlen = mod[0];
 371         m = snewn(mem_ctx, mlen, BignumInt);
 372         /* if (!m) */
 373         /* abort(); */                /* FIXME */
 374         for (j = 0; j < mlen; j++)
 375                 m[j] = mod[mod[0] - j];
 376
 377         /* Shift m left to make msb bit set */
 378         for (mshift = 0; mshift < BIGNUM_INT_BITS - 1; mshift++)
 379                 if ((m[0] << mshift) & BIGNUM_TOP_BIT)
 380                         break;
 381         if (mshift) {
 382                 for (i = 0; i < mlen - 1; i++)
 383                         m[i] =
 384                             (m[i] << mshift) | (m[i + 1] >>
 385                                                 (BIGNUM_INT_BITS - mshift));
 386                 m[mlen - 1] = m[mlen - 1] << mshift;
 387         }
 388
 389         /* Allocate n of size mlen, copy base to n */
 390         n = snewn(mem_ctx, mlen, BignumInt);
 391         /* if (!n) */
 392         /* abort(); */                /* FIXME */
 393         i = mlen - base[0];
 394         for (j = 0; j < i; j++)
 395                 n[j] = 0;
 396         for (j = 0; j < base[0]; j++)
 397                 n[i + j] = base[base[0] - j];
 398
 399         /* Allocate a and b of size 2*mlen. Set a = 1 */
 400         a = snewn(mem_ctx, 2 * mlen, BignumInt);
 401         /* if (!a) */
 402         /* abort(); */                /* FIXME */
 403         b = snewn(mem_ctx, 2 * mlen, BignumInt);
 404         /* if (!b) */
 405         /* abort(); */                /* FIXME */
 406         for (i = 0; i < 2 * mlen; i++)
 407                 a[i] = 0;
 408         a[2 * mlen - 1] = 1;
 409
 410         /* Skip leading zero bits of exp. */
 411         i = 0;
 412         j = BIGNUM_INT_BITS - 1;
 413         while (i < exp[0] && (exp[exp[0] - i] & (1 << j)) == 0) {
 414                 j--;
 415                 if (j < 0) {
 416                         i++;
 417                         j = BIGNUM_INT_BITS - 1;
 418                 }
 419         }
 420
 421         /* Main computation */
 422         while (i < exp[0]) {
 423                 while (j >= 0) {
 424                         internal_mul(a + mlen, a + mlen, b, mlen);
 425                         internal_mod(b, mlen * 2, m, mlen, NULL, 0);
 426                         if ((exp[exp[0] - i] & (1 << j)) != 0) {
 427                                 internal_mul(b + mlen, n, a, mlen);
 428                                 internal_mod(a, mlen * 2, m, mlen, NULL, 0);
 429                         } else {
 430                                 BignumInt *t;
 431                                 t = a;
 432                                 a = b;
 433                                 b = t;
 434                         }
 435                         j--;
 436                 }
 437                 i++;
 438                 j = BIGNUM_INT_BITS - 1;
 439         }
 440
 441         /* Fixup result in case the modulus was shifted */
 442         if (mshift) {
 443                 for (i = mlen - 1; i < 2 * mlen - 1; i++)
 444                         a[i] =
 445                             (a[i] << mshift) | (a[i + 1] >>
 446                                                 (BIGNUM_INT_BITS - mshift));
 447                 a[2 * mlen - 1] = a[2 * mlen - 1] << mshift;
 448                 internal_mod(a, mlen * 2, m, mlen, NULL, 0);
 449                 for (i = 2 * mlen - 1; i >= mlen; i--)
 450                         a[i] =
 451                             (a[i] >> mshift) | (a[i - 1] <<
 452                                                 (BIGNUM_INT_BITS - mshift));
 453         }
 454
 455         /* Copy result to buffer */
 456         result = newbn(mem_ctx, mod[0]);
 457         for (i = 0; i < mlen; i++)
 458                 result[result[0] - i] = a[i + mlen];
 459         while (result[0] > 1 && result[result[0]] == 0)
 460                 result[0]--;
 461
 462         /* Free temporary arrays */
 463         for (i = 0; i < 2 * mlen; i++)
 464                 a[i] = 0;
 465         sfree(mem_ctx, a);
 466         for (i = 0; i < 2 * mlen; i++)
 467                 b[i] = 0;
 468         sfree(mem_ctx, b);
 469         for (i = 0; i < mlen; i++)
 470                 m[i] = 0;
 471         sfree(mem_ctx, m);
 472         for (i = 0; i < mlen; i++)
 473                 n[i] = 0;
 474         sfree(mem_ctx, n);
 475
 476         freebn(mem_ctx, base);
 477
 478         return result;
 479 }
 480
 481 #ifdef UNITTEST
 482
 483 static __u32 dh_p[] = {
 484         96,
 485         0xFFFFFFFF,
 486         0xFFFFFFFF,
 487         0xA93AD2CA,
 488         0x4B82D120,
 489         0xE0FD108E,
 490         0x43DB5BFC,
 491         0x74E5AB31,
 492         0x08E24FA0,
 493         0xBAD946E2,
 494         0x770988C0,
 495         0x7A615D6C,
 496         0xBBE11757,
 497         0x177B200C,
 498         0x521F2B18,
 499         0x3EC86A64,
 500         0xD8760273,
 501         0xD98A0864,
 502         0xF12FFA06,
 503         0x1AD2EE6B,
 504         0xCEE3D226,
 505         0x4A25619D,
 506         0x1E8C94E0,
 507         0xDB0933D7,
 508         0xABF5AE8C,
 509         0xA6E1E4C7,
 510         0xB3970F85,
 511         0x5D060C7D,
 512         0x8AEA7157,
 513         0x58DBEF0A,
 514         0xECFB8504,
 515         0xDF1CBA64,
 516         0xA85521AB,
 517         0x04507A33,
 518         0xAD33170D,
 519         0x8AAAC42D,
 520         0x15728E5A,
 521         0x98FA0510,
 522         0x15D22618,
 523         0xEA956AE5,
 524         0x3995497C,
 525         0x95581718,
 526         0xDE2BCBF6,
 527         0x6F4C52C9,
 528         0xB5C55DF0,
 529         0xEC07A28F,
 530         0x9B2783A2,
 531         0x180E8603,
 532         0xE39E772C,
 533         0x2E36CE3B,
 534         0x32905E46,
 535         0xCA18217C,
 536         0xF1746C08,
 537         0x4ABC9804,
 538         0x670C354E,
 539         0x7096966D,
 540         0x9ED52907,
 541         0x208552BB,
 542         0x1C62F356,
 543         0xDCA3AD96,
 544         0x83655D23,
 545         0xFD24CF5F,
 546         0x69163FA8,
 547         0x1C55D39A,
 548         0x98DA4836,
 549         0xA163BF05,
 550         0xC2007CB8,
 551         0xECE45B3D,
 552         0x49286651,
 553         0x7C4B1FE6,
 554         0xAE9F2411,
 555         0x5A899FA5,
 556         0xEE386BFB,
 557         0xF406B7ED,
 558         0x0BFF5CB6,
 559         0xA637ED6B,
 560         0xF44C42E9,
 561         0x625E7EC6,
 562         0xE485B576,
 563         0x6D51C245,
 564         0x4FE1356D,
 565         0xF25F1437,
 566         0x302B0A6D,
 567         0xCD3A431B,
 568         0xEF9519B3,
 569         0x8E3404DD,
 570         0x514A0879,
 571         0x3B139B22,
 572         0x020BBEA6,
 573         0x8A67CC74,
 574         0x29024E08,
 575         0x80DC1CD1,
 576         0xC4C6628B,
 577         0x2168C234,
 578         0xC90FDAA2,
 579         0xFFFFFFFF,
 580         0xFFFFFFFF,
 581 };
 582
 583 static __u32 dh_a[] = {
 584         8,
 585         0xdf367516,
 586         0x86459caa,
 587         0xe2d459a4,
 588         0xd910dae0,
 589         0x8a8b5e37,
 590         0x67ab31c6,
 591         0xf0b55ea9,
 592         0x440051d6,
 593 };
 594
 595 static __u32 dh_b[] = {
 596         8,
 597         0xded92656,
 598         0xe07a048a,
 599         0x6fa452cd,
 600         0x2df89d30,
 601         0xc75f1b0f,
 602         0x8ce3578f,
 603         0x7980a324,
 604         0x5daec786,
 605 };
 606
 607 static __u32 dh_g[] = {
 608         1,
 609         2,
 610 };
 611
 612 int main(void)
 613 {
 614         int i;
 615         __u32 *k;
 616         k = dwc_modpow(NULL, dh_g, dh_a, dh_p);
 617
 618         printf("\n\n");
 619         for (i = 0; i < k[0]; i++) {
 620                 __u32 word32 = k[k[0] - i];
 621                 __u16 l = word32 & 0xffff;
 622                 __u16 m = (word32 & 0xffff0000) >> 16;
 623                 printf("%04x %04x ", m, l);
 624                 if (!((i + 1) % 13))
 625                         printf("\n");
 626         }
 627         printf("\n\n");
 628
 629         if ((k[0] == 0x60) && (k[1] == 0x28e490e5) && (k[0x60] == 0x5a0d3d4e)) {
 630                 printf("PASS\n\n");
 631         } else {
 632                 printf("FAIL\n\n");
 633         }
 634
 635 }
 636
 637 #endif /* UNITTEST */
 638
 639 #endif /* CONFIG_MACH_IPMATE */
 640
 641 #endif /*DWC_CRYPTOLIB */