drivers/usb/host/dwc_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
  41 static void *snmalloc(void *mem_ctx, size_t n, size_t size)
  42 {
  43     void *p;
  44     size *= n;
  45     if (size == 0) 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 //    q = n / w;
  83 //    r = n % w;
  84
  85 #define BIGNUM_INT_BYTES (BIGNUM_INT_BITS / 8)
  86
  87 #define BIGNUM_INTERNAL
  88
  89 static Bignum newbn(void *mem_ctx, int length)
  90 {
  91     Bignum b = snewn(mem_ctx, length + 1, BignumInt);
  92     //if (!b)
  93     //abort();                 /* FIXME */
  94     DWC_MEMSET(b, 0, (length + 1) * sizeof(*b));
  95     b[0] = length;
  96     return b;
  97 }
  98
  99 void freebn(void *mem_ctx, Bignum b)
 100 {
 101     /*
 102      * Burn the evidence, just in case.
 103      */
 104     DWC_MEMSET(b, 0, sizeof(b[0]) * (b[0] + 1));
 105     sfree(mem_ctx, b);
 106 }
 107
 108 /*
 109  * Compute c = a * b.
 110  * Input is in the first len words of a and b.
 111  * Result is returned in the first 2*len words of c.
 112  */
 113 static void internal_mul(BignumInt *a, BignumInt *b,
 114                          BignumInt *c, int len)
 115 {
 116     int i, j;
 117     BignumDblInt t;
 118
 119     for (j = 0; j < 2 * len; j++)
 120         c[j] = 0;
 121
 122     for (i = len - 1; i >= 0; i--) {
 123         t = 0;
 124         for (j = len - 1; j >= 0; j--) {
 125             t += MUL_WORD(a[i], (BignumDblInt) b[j]);
 126             t += (BignumDblInt) c[i + j + 1];
 127             c[i + j + 1] = (BignumInt) t;
 128             t = t >> BIGNUM_INT_BITS;
 129         }
 130         c[i] = (BignumInt) t;
 131     }
 132 }
 133
 134 static void internal_add_shifted(BignumInt *number,
 135                                  unsigned n, int shift)
 136 {
 137     int word = 1 + (shift / BIGNUM_INT_BITS);
 138     int bshift = shift % BIGNUM_INT_BITS;
 139     BignumDblInt addend;
 140
 141     addend = (BignumDblInt)n << bshift;
 142
 143     while (addend) {
 144         addend += number[word];
 145         number[word] = (BignumInt) addend & BIGNUM_INT_MASK;
 146         addend >>= BIGNUM_INT_BITS;
 147         word++;
 148     }
 149 }
 150
 151 /*
 152  * Compute a = a % m.
 153  * Input in first alen words of a and first mlen words of m.
 154  * Output in first alen words of a
 155  * (of which first alen-mlen words will be zero).
 156  * The MSW of m MUST have its high bit set.
 157  * Quotient is accumulated in the `quotient' array, which is a Bignum
 158  * rather than the internal bigendian format. Quotient parts are shifted
 159  * left by `qshift' before adding into quot.
 160  */
 161 static void internal_mod(BignumInt *a, int alen,
 162                          BignumInt *m, int mlen,
 163                          BignumInt *quot, int qshift)
 164 {
 165     BignumInt m0, m1;
 166     unsigned int h;
 167     int i, k;
 168
 169     m0 = m[0];
 170     if (mlen > 1)
 171         m1 = m[1];
 172     else
 173         m1 = 0;
 174
 175     for (i = 0; i <= alen - mlen; i++) {
 176         BignumDblInt t;
 177         unsigned int q, r, c, ai1;
 178
 179         if (i == 0) {
 180             h = 0;
 181         } else {
 182             h = a[i - 1];
 183             a[i - 1] = 0;
 184         }
 185
 186         if (i == alen - 1)
 187             ai1 = 0;
 188         else
 189             ai1 = a[i + 1];
 190
 191         /* Find q = h:a[i] / m0 */
 192         if (h >= m0) {
 193             /*
 194              * Special case.
 195              *
 196              * To illustrate it, suppose a BignumInt is 8 bits, and
 197              * we are dividing (say) A1:23:45:67 by A1:B2:C3. Then
 198              * our initial division will be 0xA123 / 0xA1, which
 199              * will give a quotient of 0x100 and a divide overflow.
 200              * However, the invariants in this division algorithm
 201              * are not violated, since the full number A1:23:... is
 202              * _less_ than the quotient prefix A1:B2:... and so the
 203              * following correction loop would have sorted it out.
 204              *
 205              * In this situation we set q to be the largest
 206              * quotient we _can_ stomach (0xFF, of course).
 207              */
 208             q = BIGNUM_INT_MASK;
 209         } else {
 210             /* Macro doesn't want an array subscript expression passed
 211              * into it (see definition), so use a temporary. */
 212             BignumInt tmplo = a[i];
 213             DIVMOD_WORD(q, r, h, tmplo, m0);
 214
 215             /* Refine our estimate of q by looking at
 216              h:a[i]:a[i+1] / m0:m1 */
 217             t = MUL_WORD(m1, q);
 218             if (t > ((BignumDblInt) r << BIGNUM_INT_BITS) + ai1) {
 219                 q--;
 220                 t -= m1;
 221                 r = (r + m0) & BIGNUM_INT_MASK;     /* overflow? */
 222                 if (r >= (BignumDblInt) m0 &&
 223                     t > ((BignumDblInt) r << BIGNUM_INT_BITS) + ai1) q--;
 224             }
 225         }
 226
 227         /* Subtract q * m from a[i...] */
 228         c = 0;
 229         for (k = mlen - 1; k >= 0; k--) {
 230             t = MUL_WORD(q, m[k]);
 231             t += c;
 232             c = (unsigned)(t >> BIGNUM_INT_BITS);
 233             if ((BignumInt) t > a[i + k])
 234                 c++;
 235             a[i + k] -= (BignumInt) t;
 236         }
 237
 238         /* Add back m in case of borrow */
 239         if (c != h) {
 240             t = 0;
 241             for (k = mlen - 1; k >= 0; k--) {
 242                 t += m[k];
 243                 t += a[i + k];
 244                 a[i + k] = (BignumInt) t;
 245                 t = t >> BIGNUM_INT_BITS;
 246             }
 247             q--;
 248         }
 249         if (quot)
 250             internal_add_shifted(quot, q, qshift + BIGNUM_INT_BITS * (alen - mlen - i));
 251     }
 252 }
 253
 254 /*
 255  * Compute p % mod.
 256  * The most significant word of mod MUST be non-zero.
 257  * We assume that the result array is the same size as the mod array.
 258  * We optionally write out a quotient if `quotient' is non-NULL.
 259  * We can avoid writing out the result if `result' is NULL.
 260  */
 261 void bigdivmod(void *mem_ctx, Bignum p, Bignum mod, Bignum result, 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] = (m[i] << mshift) | (m[i + 1] >> (BIGNUM_INT_BITS - mshift));
 283         m[mlen - 1] = m[mlen - 1] << mshift;
 284     }
 285
 286     plen = p[0];
 287     /* Ensure plen > mlen */
 288     if (plen <= mlen)
 289         plen = mlen + 1;
 290
 291     /* Allocate n of size plen, copy p to n */
 292     n = snewn(mem_ctx, plen, BignumInt);
 293     //if (!n)
 294     //abort();                 /* FIXME */
 295     for (j = 0; j < plen; j++)
 296         n[j] = 0;
 297     for (j = 1; j <= (int)p[0]; j++)
 298         n[plen - j] = p[j];
 299
 300     /* Main computation */
 301     internal_mod(n, plen, m, mlen, quotient, mshift);
 302
 303     /* Fixup result in case the modulus was shifted */
 304     if (mshift) {
 305         for (i = plen - mlen - 1; i < plen - 1; i++)
 306             n[i] = (n[i] << mshift) | (n[i + 1] >> (BIGNUM_INT_BITS - mshift));
 307         n[plen - 1] = n[plen - 1] << mshift;
 308         internal_mod(n, plen, m, mlen, quotient, 0);
 309         for (i = plen - 1; i >= plen - mlen; i--)
 310             n[i] = (n[i] >> mshift) | (n[i - 1] << (BIGNUM_INT_BITS - mshift));
 311     }
 312
 313     /* Copy result to buffer */
 314     if (result) {
 315         for (i = 1; i <= (int)result[0]; i++) {
 316             int j = plen - i;
 317             result[i] = j >= 0 ? n[j] : 0;
 318         }
 319     }
 320
 321     /* Free temporary arrays */
 322     for (i = 0; i < mlen; i++)
 323         m[i] = 0;
 324     sfree(mem_ctx, m);
 325     for (i = 0; i < plen; i++)
 326         n[i] = 0;
 327     sfree(mem_ctx, n);
 328 }
 329
 330 /*
 331  * Simple remainder.
 332  */
 333 Bignum bigmod(void *mem_ctx, Bignum a, Bignum b)
 334 {
 335     Bignum r = newbn(mem_ctx, b[0]);
 336     bigdivmod(mem_ctx, a, b, r, NULL);
 337     return r;
 338 }
 339
 340 /*
 341  * Compute (base ^ exp) % mod.
 342  */
 343 Bignum dwc_modpow(void *mem_ctx, Bignum base_in, Bignum exp, Bignum mod)
 344 {
 345     BignumInt *a, *b, *n, *m;
 346     int mshift;
 347     int mlen, i, j;
 348     Bignum base, result;
 349
 350     /*
 351      * The most significant word of mod needs to be non-zero. It
 352      * should already be, but let's make sure.
 353      */
 354     //assert(mod[mod[0]] != 0);
 355
 356     /*
 357      * Make sure the base is smaller than the modulus, by reducing
 358      * it modulo the modulus if not.
 359      */
 360     base = bigmod(mem_ctx, base_in, mod);
 361
 362     /* Allocate m of size mlen, copy mod to m */
 363     /* We use big endian internally */
 364     mlen = mod[0];
 365     m = snewn(mem_ctx, mlen, BignumInt);
 366     //if (!m)
 367     //abort();                 /* FIXME */
 368     for (j = 0; j < mlen; j++)
 369         m[j] = mod[mod[0] - j];
 370
 371     /* Shift m left to make msb bit set */
 372     for (mshift = 0; mshift < BIGNUM_INT_BITS - 1; mshift++)
 373         if ((m[0] << mshift) & BIGNUM_TOP_BIT)
 374             break;
 375     if (mshift) {
 376         for (i = 0; i < mlen - 1; i++)
 377             m[i] =
 378                 (m[i] << mshift) | (m[i + 1] >>
 379                                     (BIGNUM_INT_BITS - mshift));
 380         m[mlen - 1] = m[mlen - 1] << mshift;
 381     }
 382
 383     /* Allocate n of size mlen, copy base to n */
 384     n = snewn(mem_ctx, mlen, BignumInt);
 385     //if (!n)
 386     //abort();                 /* FIXME */
 387     i = mlen - base[0];
 388     for (j = 0; j < i; j++)
 389         n[j] = 0;
 390     for (j = 0; j < base[0]; j++)
 391         n[i + j] = base[base[0] - j];
 392
 393     /* Allocate a and b of size 2*mlen. Set a = 1 */
 394     a = snewn(mem_ctx, 2 * mlen, BignumInt);
 395     //if (!a)
 396     //abort();                 /* FIXME */
 397     b = snewn(mem_ctx, 2 * mlen, BignumInt);
 398     //if (!b)
 399     //abort();                 /* FIXME */
 400     for (i = 0; i < 2 * mlen; i++)
 401         a[i] = 0;
 402     a[2 * mlen - 1] = 1;
 403
 404     /* Skip leading zero bits of exp. */
 405     i = 0;
 406     j = BIGNUM_INT_BITS - 1;
 407     while (i < exp[0] && (exp[exp[0] - i] & (1 << j)) == 0) {
 408         j--;
 409         if (j < 0) {
 410             i++;
 411             j = BIGNUM_INT_BITS - 1;
 412         }
 413     }
 414
 415     /* Main computation */
 416     while (i < exp[0]) {
 417         while (j >= 0) {
 418             internal_mul(a + mlen, a + mlen, b, mlen);
 419             internal_mod(b, mlen * 2, m, mlen, NULL, 0);
 420             if ((exp[exp[0] - i] & (1 << j)) != 0) {
 421                 internal_mul(b + mlen, n, a, mlen);
 422                 internal_mod(a, mlen * 2, m, mlen, NULL, 0);
 423             } else {
 424                 BignumInt *t;
 425                 t = a;
 426                 a = b;
 427                 b = t;
 428             }
 429             j--;
 430         }
 431         i++;
 432         j = BIGNUM_INT_BITS - 1;
 433     }
 434
 435     /* Fixup result in case the modulus was shifted */
 436     if (mshift) {
 437         for (i = mlen - 1; i < 2 * mlen - 1; i++)
 438             a[i] =
 439                 (a[i] << mshift) | (a[i + 1] >>
 440                                     (BIGNUM_INT_BITS - mshift));
 441         a[2 * mlen - 1] = a[2 * mlen - 1] << mshift;
 442         internal_mod(a, mlen * 2, m, mlen, NULL, 0);
 443         for (i = 2 * mlen - 1; i >= mlen; i--)
 444             a[i] =
 445                 (a[i] >> mshift) | (a[i - 1] <<
 446                                     (BIGNUM_INT_BITS - mshift));
 447     }
 448
 449     /* Copy result to buffer */
 450     result = newbn(mem_ctx, mod[0]);
 451     for (i = 0; i < mlen; i++)
 452         result[result[0] - i] = a[i + mlen];
 453     while (result[0] > 1 && result[result[0]] == 0)
 454         result[0]--;
 455
 456     /* Free temporary arrays */
 457     for (i = 0; i < 2 * mlen; i++)
 458         a[i] = 0;
 459     sfree(mem_ctx, a);
 460     for (i = 0; i < 2 * mlen; i++)
 461         b[i] = 0;
 462     sfree(mem_ctx, b);
 463     for (i = 0; i < mlen; i++)
 464         m[i] = 0;
 465     sfree(mem_ctx, m);
 466     for (i = 0; i < mlen; i++)
 467         n[i] = 0;
 468     sfree(mem_ctx, n);
 469
 470     freebn(mem_ctx, base);
 471
 472     return result;
 473 }
 474
 475
 476 #ifdef UNITTEST
 477
 478 static __u32 dh_p[] = {
 479         96,
 480         0xFFFFFFFF,
 481         0xFFFFFFFF,
 482         0xA93AD2CA,
 483         0x4B82D120,
 484         0xE0FD108E,
 485         0x43DB5BFC,
 486         0x74E5AB31,
 487         0x08E24FA0,
 488         0xBAD946E2,
 489         0x770988C0,
 490         0x7A615D6C,
 491         0xBBE11757,
 492         0x177B200C,
 493         0x521F2B18,
 494         0x3EC86A64,
 495         0xD8760273,
 496         0xD98A0864,
 497         0xF12FFA06,
 498         0x1AD2EE6B,
 499         0xCEE3D226,
 500         0x4A25619D,
 501         0x1E8C94E0,
 502         0xDB0933D7,
 503         0xABF5AE8C,
 504         0xA6E1E4C7,
 505         0xB3970F85,
 506         0x5D060C7D,
 507         0x8AEA7157,
 508         0x58DBEF0A,
 509         0xECFB8504,
 510         0xDF1CBA64,
 511         0xA85521AB,
 512         0x04507A33,
 513         0xAD33170D,
 514         0x8AAAC42D,
 515         0x15728E5A,
 516         0x98FA0510,
 517         0x15D22618,
 518         0xEA956AE5,
 519         0x3995497C,
 520         0x95581718,
 521         0xDE2BCBF6,
 522         0x6F4C52C9,
 523         0xB5C55DF0,
 524         0xEC07A28F,
 525         0x9B2783A2,
 526         0x180E8603,
 527         0xE39E772C,
 528         0x2E36CE3B,
 529         0x32905E46,
 530         0xCA18217C,
 531         0xF1746C08,
 532         0x4ABC9804,
 533         0x670C354E,
 534         0x7096966D,
 535         0x9ED52907,
 536         0x208552BB,
 537         0x1C62F356,
 538         0xDCA3AD96,
 539         0x83655D23,
 540         0xFD24CF5F,
 541         0x69163FA8,
 542         0x1C55D39A,
 543         0x98DA4836,
 544         0xA163BF05,
 545         0xC2007CB8,
 546         0xECE45B3D,
 547         0x49286651,
 548         0x7C4B1FE6,
 549         0xAE9F2411,
 550         0x5A899FA5,
 551         0xEE386BFB,
 552         0xF406B7ED,
 553         0x0BFF5CB6,
 554         0xA637ED6B,
 555         0xF44C42E9,
 556         0x625E7EC6,
 557         0xE485B576,
 558         0x6D51C245,
 559         0x4FE1356D,
 560         0xF25F1437,
 561         0x302B0A6D,
 562         0xCD3A431B,
 563         0xEF9519B3,
 564         0x8E3404DD,
 565         0x514A0879,
 566         0x3B139B22,
 567         0x020BBEA6,
 568         0x8A67CC74,
 569         0x29024E08,
 570         0x80DC1CD1,
 571         0xC4C6628B,
 572         0x2168C234,
 573         0xC90FDAA2,
 574         0xFFFFFFFF,
 575         0xFFFFFFFF,
 576 };
 577
 578 static __u32 dh_a[] = {
 579         8,
 580         0xdf367516,
 581         0x86459caa,
 582         0xe2d459a4,
 583         0xd910dae0,
 584         0x8a8b5e37,
 585         0x67ab31c6,
 586         0xf0b55ea9,
 587         0x440051d6,
 588 };
 589
 590 static __u32 dh_b[] = {
 591         8,
 592         0xded92656,
 593         0xe07a048a,
 594         0x6fa452cd,
 595         0x2df89d30,
 596         0xc75f1b0f,
 597         0x8ce3578f,
 598         0x7980a324,
 599         0x5daec786,
 600 };
 601
 602 static __u32 dh_g[] = {
 603         1,
 604         2,
 605 };
 606
 607 int main(void)
 608 {
 609         int i;
 610         __u32 *k;
 611         k = dwc_modpow(NULL, dh_g, dh_a, dh_p);
 612
 613         printf("\n\n");
 614         for (i=0; i<k[0]; i++) {
 615                 __u32 word32 = k[k[0] - i];
 616                 __u16 l = word32 & 0xffff;
 617                 __u16 m = (word32 & 0xffff0000) >> 16;
 618                 printf("%04x %04x ", m, l);
 619                 if (!((i + 1)%13)) printf("\n");
 620         }
 621         printf("\n\n");
 622
 623         if ((k[0] == 0x60) && (k[1] == 0x28e490e5) && (k[0x60] == 0x5a0d3d4e)) {
 624                 printf("PASS\n\n");
 625         }
 626         else {
 627                 printf("FAIL\n\n");
 628         }
 629
 630 }
 631
 632 #endif /* UNITTEST */
 633
 634 #endif /* CONFIG_MACH_IPMATE */
 635
 636 #endif /*DWC_CRYPTOLIB */