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