l4/pkg/libcrypto/lib/rsaref2/source/nn.c

   1 /* NN.C - natural numbers routines
   2  */
   3
   4 /* Copyright (C) RSA Laboratories, a division of RSA Data Security,
   5      Inc., created 1991. All rights reserved.
   6  */
   7
   8 /* CHANGES MADE TO THIS FILE UNDER RSAREF 2.0 license clause 1(c):
   9
  10    For the MIT PGP 2.5 distribution, this file was modified to permit
  11    replacement of the NN_ModExp routine by an equivalent routine contained
  12    in the PGP 2.5 sources.  To enable this change, an #ifdef was added to this
  13    file (search for #ifndef USEMPILIB below).  RSAREF *must* be compiled with
  14    USEMPILIB defined for this change to occur.
  15
  16    Change made May 8, 1994.  */
  17
  18 #include "global.h"
  19 #include "rsaref.h"
  20 #include "nn.h"
  21 #include "digit.h"
  22
  23 static NN_DIGIT NN_AddDigitMult PROTO_LIST
  24   ((NN_DIGIT *, NN_DIGIT *, NN_DIGIT, NN_DIGIT *, unsigned int));
  25 static NN_DIGIT NN_SubDigitMult PROTO_LIST
  26   ((NN_DIGIT *, NN_DIGIT *, NN_DIGIT, NN_DIGIT *, unsigned int));
  27
  28 static unsigned int NN_DigitBits PROTO_LIST ((NN_DIGIT));
  29
  30 /* Decodes character string b into a, where character string is ordered
  31    from most to least significant.
  32
  33    Lengths: a[digits], b[len].
  34    Assumes b[i] = 0 for i < len - digits * NN_DIGIT_LEN. (Otherwise most
  35    significant bytes are truncated.)
  36  */
  37 void NN_Decode (a, digits, b, len)
  38 NN_DIGIT *a;
  39 unsigned char *b;
  40 unsigned int digits, len;
  41 {
  42   NN_DIGIT t;
  43   int j;
  44   unsigned int i, u;
  45
  46   for (i = 0, j = len - 1; i < digits && j >= 0; i++) {
  47     t = 0;
  48     for (u = 0; j >= 0 && u < NN_DIGIT_BITS; j--, u += 8)
  49       t |= ((NN_DIGIT)b[j]) << u;
  50     a[i] = t;
  51   }
  52
  53   for (; i < digits; i++)
  54     a[i] = 0;
  55 }
  56
  57 /* Encodes b into character string a, where character string is ordered
  58    from most to least significant.
  59
  60    Lengths: a[len], b[digits].
  61    Assumes NN_Bits (b, digits) <= 8 * len. (Otherwise most significant
  62    digits are truncated.)
  63  */
  64 void NN_Encode (a, len, b, digits)
  65 NN_DIGIT *b;
  66 unsigned char *a;
  67 unsigned int digits, len;
  68 {
  69   NN_DIGIT t;
  70   int j;
  71   unsigned int i, u;
  72
  73   for (i = 0, j = len - 1; i < digits && j >= 0; i++) {
  74     t = b[i];
  75     for (u = 0; j >= 0 && u < NN_DIGIT_BITS; j--, u += 8)
  76       a[j] = (unsigned char)(t >> u);
  77   }
  78
  79   for (; j >= 0; j--)
  80     a[j] = 0;
  81 }
  82
  83 /* Assigns a = b.
  84
  85    Lengths: a[digits], b[digits].
  86  */
  87 void NN_Assign (a, b, digits)
  88 NN_DIGIT *a, *b;
  89 unsigned int digits;
  90 {
  91   unsigned int i;
  92
  93   for (i = 0; i < digits; i++)
  94     a[i] = b[i];
  95 }
  96
  97 /* Assigns a = 0.
  98
  99    Lengths: a[digits].
 100  */
 101 void NN_AssignZero (a, digits)
 102 NN_DIGIT *a;
 103 unsigned int digits;
 104 {
 105   unsigned int i;
 106
 107   for (i = 0; i < digits; i++)
 108     a[i] = 0;
 109 }
 110
 111 /* Assigns a = 2^b.
 112
 113    Lengths: a[digits].
 114    Requires b < digits * NN_DIGIT_BITS.
 115  */
 116 void NN_Assign2Exp (a, b, digits)
 117 NN_DIGIT *a;
 118 unsigned int b, digits;
 119 {
 120   NN_AssignZero (a, digits);
 121
 122   if (b >= digits * NN_DIGIT_BITS)
 123     return;
 124
 125   a[b / NN_DIGIT_BITS] = (NN_DIGIT)1 << (b % NN_DIGIT_BITS);
 126 }
 127
 128 /* Computes a = b + c. Returns carry.
 129
 130    Lengths: a[digits], b[digits], c[digits].
 131  */
 132 NN_DIGIT NN_Add (a, b, c, digits)
 133 NN_DIGIT *a, *b, *c;
 134 unsigned int digits;
 135 {
 136   NN_DIGIT ai, carry;
 137   unsigned int i;
 138
 139   carry = 0;
 140
 141   for (i = 0; i < digits; i++) {
 142     if ((ai = b[i] + carry) < carry)
 143       ai = c[i];
 144     else if ((ai += c[i]) < c[i])
 145       carry = 1;
 146     else
 147       carry = 0;
 148     a[i] = ai;
 149   }
 150
 151   return (carry);
 152 }
 153
 154 /* Computes a = b - c. Returns borrow.
 155
 156    Lengths: a[digits], b[digits], c[digits].
 157  */
 158 NN_DIGIT NN_Sub (a, b, c, digits)
 159 NN_DIGIT *a, *b, *c;
 160 unsigned int digits;
 161 {
 162   NN_DIGIT ai, borrow;
 163   unsigned int i;
 164
 165   borrow = 0;
 166
 167   for (i = 0; i < digits; i++) {
 168     if ((ai = b[i] - borrow) > (MAX_NN_DIGIT - borrow))
 169       ai = MAX_NN_DIGIT - c[i];
 170     else if ((ai -= c[i]) > (MAX_NN_DIGIT - c[i]))
 171       borrow = 1;
 172     else
 173       borrow = 0;
 174     a[i] = ai;
 175   }
 176
 177   return (borrow);
 178 }
 179
 180 /* Computes a = b * c.
 181
 182    Lengths: a[2*digits], b[digits], c[digits].
 183    Assumes digits < MAX_NN_DIGITS.
 184  */
 185 void NN_Mult (a, b, c, digits)
 186 NN_DIGIT *a, *b, *c;
 187 unsigned int digits;
 188 {
 189   NN_DIGIT t[2*MAX_NN_DIGITS];
 190   unsigned int bDigits, cDigits, i;
 191
 192   NN_AssignZero (t, 2 * digits);
 193
 194   bDigits = NN_Digits (b, digits);
 195   cDigits = NN_Digits (c, digits);
 196
 197   for (i = 0; i < bDigits; i++)
 198     t[i+cDigits] += NN_AddDigitMult (&t[i], &t[i], b[i], c, cDigits);
 199
 200   NN_Assign (a, t, 2 * digits);
 201
 202   /* Zeroize potentially sensitive information.
 203    */
 204   R_memset ((POINTER)t, 0, sizeof (t));
 205 }
 206
 207 /* Computes a = b * 2^c (i.e., shifts left c bits), returning carry.
 208
 209    Lengths: a[digits], b[digits].
 210    Requires c < NN_DIGIT_BITS.
 211  */
 212 NN_DIGIT NN_LShift (a, b, c, digits)
 213 NN_DIGIT *a, *b;
 214 unsigned int c, digits;
 215 {
 216   NN_DIGIT bi, carry;
 217   unsigned int i, t;
 218
 219   if (c >= NN_DIGIT_BITS)
 220     return (0);
 221
 222   t = NN_DIGIT_BITS - c;
 223
 224   carry = 0;
 225
 226   for (i = 0; i < digits; i++) {
 227     bi = b[i];
 228     a[i] = (bi << c) | carry;
 229     carry = c ? (bi >> t) : 0;
 230   }
 231
 232   return (carry);
 233 }
 234
 235 /* Computes a = c div 2^c (i.e., shifts right c bits), returning carry.
 236
 237    Lengths: a[digits], b[digits].
 238    Requires: c < NN_DIGIT_BITS.
 239  */
 240 NN_DIGIT NN_RShift (a, b, c, digits)
 241 NN_DIGIT *a, *b;
 242 unsigned int c, digits;
 243 {
 244   NN_DIGIT bi, carry;
 245   int i;
 246   unsigned int t;
 247
 248   if (c >= NN_DIGIT_BITS)
 249     return (0);
 250
 251   t = NN_DIGIT_BITS - c;
 252
 253   carry = 0;
 254
 255   for (i = digits - 1; i >= 0; i--) {
 256     bi = b[i];
 257     a[i] = (bi >> c) | carry;
 258     carry = c ? (bi << t) : 0;
 259   }
 260
 261   return (carry);
 262 }
 263
 264 /* Computes a = c div d and b = c mod d.
 265
 266    Lengths: a[cDigits], b[dDigits], c[cDigits], d[dDigits].
 267    Assumes d > 0, cDigits < 2 * MAX_NN_DIGITS,
 268            dDigits < MAX_NN_DIGITS.
 269  */
 270 void NN_Div (a, b, c, cDigits, d, dDigits)
 271 NN_DIGIT *a, *b, *c, *d;
 272 unsigned int cDigits, dDigits;
 273 {
 274   NN_DIGIT ai, cc[2*MAX_NN_DIGITS+1], dd[MAX_NN_DIGITS], t;
 275   int i;
 276   unsigned int ddDigits, shift;
 277
 278   ddDigits = NN_Digits (d, dDigits);
 279   if (ddDigits == 0)
 280     return;
 281
 282   /* Normalize operands.
 283    */
 284   shift = NN_DIGIT_BITS - NN_DigitBits (d[ddDigits-1]);
 285   NN_AssignZero (cc, ddDigits);
 286   cc[cDigits] = NN_LShift (cc, c, shift, cDigits);
 287   NN_LShift (dd, d, shift, ddDigits);
 288   t = dd[ddDigits-1];
 289
 290   NN_AssignZero (a, cDigits);
 291
 292   for (i = cDigits-ddDigits; i >= 0; i--) {
 293     /* Underestimate quotient digit and subtract.
 294      */
 295     if (t == MAX_NN_DIGIT)
 296       ai = cc[i+ddDigits];
 297     else
 298       NN_DigitDiv (&ai, &cc[i+ddDigits-1], t + 1);
 299     cc[i+ddDigits] -= NN_SubDigitMult (&cc[i], &cc[i], ai, dd, ddDigits);
 300
 301     /* Correct estimate.
 302      */
 303     while (cc[i+ddDigits] || (NN_Cmp (&cc[i], dd, ddDigits) >= 0)) {
 304       ai++;
 305       cc[i+ddDigits] -= NN_Sub (&cc[i], &cc[i], dd, ddDigits);
 306     }
 307
 308     a[i] = ai;
 309   }
 310
 311   /* Restore result.
 312    */
 313   NN_AssignZero (b, dDigits);
 314   NN_RShift (b, cc, shift, ddDigits);
 315
 316   /* Zeroize potentially sensitive information.
 317    */
 318   R_memset ((POINTER)cc, 0, sizeof (cc));
 319   R_memset ((POINTER)dd, 0, sizeof (dd));
 320 }
 321
 322 /* Computes a = b mod c.
 323
 324    Lengths: a[cDigits], b[bDigits], c[cDigits].
 325    Assumes c > 0, bDigits < 2 * MAX_NN_DIGITS, cDigits < MAX_NN_DIGITS.
 326  */
 327 void NN_Mod (a, b, bDigits, c, cDigits)
 328 NN_DIGIT *a, *b, *c;
 329 unsigned int bDigits, cDigits;
 330 {
 331   NN_DIGIT t[2 * MAX_NN_DIGITS];
 332
 333   NN_Div (t, a, b, bDigits, c, cDigits);
 334
 335   /* Zeroize potentially sensitive information.
 336    */
 337   R_memset ((POINTER)t, 0, sizeof (t));
 338 }
 339
 340 /* Computes a = b * c mod d.
 341
 342    Lengths: a[digits], b[digits], c[digits], d[digits].
 343    Assumes d > 0, digits < MAX_NN_DIGITS.
 344  */
 345 void NN_ModMult (a, b, c, d, digits)
 346 NN_DIGIT *a, *b, *c, *d;
 347 unsigned int digits;
 348 {
 349   NN_DIGIT t[2*MAX_NN_DIGITS];
 350
 351   NN_Mult (t, b, c, digits);
 352   NN_Mod (a, t, 2 * digits, d, digits);
 353
 354   /* Zeroize potentially sensitive information.
 355    */
 356   R_memset ((POINTER)t, 0, sizeof (t));
 357 }
 358
 359 /* Computes a = b^c mod d.
 360
 361    Lengths: a[dDigits], b[dDigits], c[cDigits], d[dDigits].
 362    Assumes d > 0, cDigits > 0, dDigits < MAX_NN_DIGITS.
 363  */
 364
 365 /* PGP 2.5's mpilib contains a faster modular exponentiation routine, mp_modexp.
 366    If USEMPILIB is defined, NN_ModExp is replaced in the PGP 2.5 sources with a
 367    stub call to mp_modexp.  If USEMPILIB is not defined, we'll get a pure (albeit
 368    slower) RSAREF implementation.
 369
 370    The RSAREF 2.0 license, clause 1(c), permits "...modify[ing] the Program in any
 371    manner for porting or performance improvement purposes..." */
 372
 373 #ifndef USEMPILIB
 374 void NN_ModExp (a, b, c, cDigits, d, dDigits)
 375 NN_DIGIT *a, *b, *c, *d;
 376 unsigned int cDigits, dDigits;
 377 {
 378   NN_DIGIT bPower[3][MAX_NN_DIGITS], ci, t[MAX_NN_DIGITS];
 379   int i;
 380   unsigned int ciBits, j, s;
 381
 382   /* Store b, b^2 mod d, and b^3 mod d.
 383    */
 384   NN_Assign (bPower[0], b, dDigits);
 385   NN_ModMult (bPower[1], bPower[0], b, d, dDigits);
 386   NN_ModMult (bPower[2], bPower[1], b, d, dDigits);
 387
 388   NN_ASSIGN_DIGIT (t, 1, dDigits);
 389
 390   cDigits = NN_Digits (c, cDigits);
 391   for (i = cDigits - 1; i >= 0; i--) {
 392     ci = c[i];
 393     ciBits = NN_DIGIT_BITS;
 394
 395     /* Scan past leading zero bits of most significant digit.
 396      */
 397     if (i == (int)(cDigits - 1)) {
 398       while (! DIGIT_2MSB (ci)) {
 399         ci <<= 2;
 400         ciBits -= 2;
 401       }
 402     }
 403
 404     for (j = 0; j < ciBits; j += 2, ci <<= 2) {
 405       /* Compute t = t^4 * b^s mod d, where s = two MSB's of ci.
 406        */
 407       NN_ModMult (t, t, t, d, dDigits);
 408       NN_ModMult (t, t, t, d, dDigits);
 409       if ((s = DIGIT_2MSB (ci)) != 0)
 410         NN_ModMult (t, t, bPower[s-1], d, dDigits);
 411     }
 412   }
 413
 414   NN_Assign (a, t, dDigits);
 415
 416   /* Zeroize potentially sensitive information.
 417    */
 418   R_memset ((POINTER)bPower, 0, sizeof (bPower));
 419   R_memset ((POINTER)t, 0, sizeof (t));
 420 }
 421 #endif
 422
 423 /* Compute a = 1/b mod c, assuming inverse exists.
 424
 425    Lengths: a[digits], b[digits], c[digits].
 426    Assumes gcd (b, c) = 1, digits < MAX_NN_DIGITS.
 427  */
 428 void NN_ModInv (a, b, c, digits)
 429 NN_DIGIT *a, *b, *c;
 430 unsigned int digits;
 431 {
 432   NN_DIGIT q[MAX_NN_DIGITS], t1[MAX_NN_DIGITS], t3[MAX_NN_DIGITS],
 433     u1[MAX_NN_DIGITS], u3[MAX_NN_DIGITS], v1[MAX_NN_DIGITS],
 434     v3[MAX_NN_DIGITS], w[2*MAX_NN_DIGITS];
 435   int u1Sign;
 436
 437   /* Apply extended Euclidean algorithm, modified to avoid negative
 438      numbers.
 439    */
 440   NN_ASSIGN_DIGIT (u1, 1, digits);
 441   NN_AssignZero (v1, digits);
 442   NN_Assign (u3, b, digits);
 443   NN_Assign (v3, c, digits);
 444   u1Sign = 1;
 445
 446   while (! NN_Zero (v3, digits)) {
 447     NN_Div (q, t3, u3, digits, v3, digits);
 448     NN_Mult (w, q, v1, digits);
 449     NN_Add (t1, u1, w, digits);
 450     NN_Assign (u1, v1, digits);
 451     NN_Assign (v1, t1, digits);
 452     NN_Assign (u3, v3, digits);
 453     NN_Assign (v3, t3, digits);
 454     u1Sign = -u1Sign;
 455   }
 456
 457   /* Negate result if sign is negative.
 458     */
 459   if (u1Sign < 0)
 460     NN_Sub (a, c, u1, digits);
 461   else
 462     NN_Assign (a, u1, digits);
 463
 464   /* Zeroize potentially sensitive information.
 465    */
 466   R_memset ((POINTER)q, 0, sizeof (q));
 467   R_memset ((POINTER)t1, 0, sizeof (t1));
 468   R_memset ((POINTER)t3, 0, sizeof (t3));
 469   R_memset ((POINTER)u1, 0, sizeof (u1));
 470   R_memset ((POINTER)u3, 0, sizeof (u3));
 471   R_memset ((POINTER)v1, 0, sizeof (v1));
 472   R_memset ((POINTER)v3, 0, sizeof (v3));
 473   R_memset ((POINTER)w, 0, sizeof (w));
 474 }
 475
 476 /* Computes a = gcd(b, c).
 477
 478    Lengths: a[digits], b[digits], c[digits].
 479    Assumes b > c, digits < MAX_NN_DIGITS.
 480  */
 481 void NN_Gcd (a, b, c, digits)
 482 NN_DIGIT *a, *b, *c;
 483 unsigned int digits;
 484 {
 485   NN_DIGIT t[MAX_NN_DIGITS], u[MAX_NN_DIGITS], v[MAX_NN_DIGITS];
 486
 487   NN_Assign (u, b, digits);
 488   NN_Assign (v, c, digits);
 489
 490   while (! NN_Zero (v, digits)) {
 491     NN_Mod (t, u, digits, v, digits);
 492     NN_Assign (u, v, digits);
 493     NN_Assign (v, t, digits);
 494   }
 495
 496   NN_Assign (a, u, digits);
 497
 498   /* Zeroize potentially sensitive information.
 499    */
 500   R_memset ((POINTER)t, 0, sizeof (t));
 501   R_memset ((POINTER)u, 0, sizeof (u));
 502   R_memset ((POINTER)v, 0, sizeof (v));
 503 }
 504
 505 /* Returns sign of a - b.
 506
 507    Lengths: a[digits], b[digits].
 508  */
 509 int NN_Cmp (a, b, digits)
 510 NN_DIGIT *a, *b;
 511 unsigned int digits;
 512 {
 513   int i;
 514
 515   for (i = digits - 1; i >= 0; i--) {
 516     if (a[i] > b[i])
 517       return (1);
 518     if (a[i] < b[i])
 519       return (-1);
 520   }
 521
 522   return (0);
 523 }
 524
 525 /* Returns nonzero iff a is zero.
 526
 527    Lengths: a[digits].
 528  */
 529 int NN_Zero (a, digits)
 530 NN_DIGIT *a;
 531 unsigned int digits;
 532 {
 533   unsigned int i;
 534
 535   for (i = 0; i < digits; i++)
 536     if (a[i])
 537       return (0);
 538
 539   return (1);
 540 }
 541
 542 /* Returns the significant length of a in bits.
 543
 544    Lengths: a[digits].
 545  */
 546 unsigned int NN_Bits (a, digits)
 547 NN_DIGIT *a;
 548 unsigned int digits;
 549 {
 550   if ((digits = NN_Digits (a, digits)) == 0)
 551     return (0);
 552
 553   return ((digits - 1) * NN_DIGIT_BITS + NN_DigitBits (a[digits-1]));
 554 }
 555
 556 /* Returns the significant length of a in digits.
 557
 558    Lengths: a[digits].
 559  */
 560 unsigned int NN_Digits (a, digits)
 561 NN_DIGIT *a;
 562 unsigned int digits;
 563 {
 564   int i;
 565
 566   for (i = digits - 1; i >= 0; i--)
 567     if (a[i])
 568       break;
 569
 570   return (i + 1);
 571 }
 572
 573 /* Computes a = b + c*d, where c is a digit. Returns carry.
 574
 575    Lengths: a[digits], b[digits], d[digits].
 576  */
 577 static NN_DIGIT NN_AddDigitMult (a, b, c, d, digits)
 578 NN_DIGIT *a, *b, c, *d;
 579 unsigned int digits;
 580 {
 581   NN_DIGIT carry, t[2];
 582   unsigned int i;
 583
 584   if (c == 0)
 585     return (0);
 586
 587   carry = 0;
 588   for (i = 0; i < digits; i++) {
 589     NN_DigitMult (t, c, d[i]);
 590     if ((a[i] = b[i] + carry) < carry)
 591       carry = 1;
 592     else
 593       carry = 0;
 594     if ((a[i] += t[0]) < t[0])
 595       carry++;
 596     carry += t[1];
 597   }
 598
 599   return (carry);
 600 }
 601
 602 /* Computes a = b - c*d, where c is a digit. Returns borrow.
 603
 604    Lengths: a[digits], b[digits], d[digits].
 605  */
 606 static NN_DIGIT NN_SubDigitMult (a, b, c, d, digits)
 607 NN_DIGIT *a, *b, c, *d;
 608 unsigned int digits;
 609 {
 610   NN_DIGIT borrow, t[2];
 611   unsigned int i;
 612
 613   if (c == 0)
 614     return (0);
 615
 616   borrow = 0;
 617   for (i = 0; i < digits; i++) {
 618     NN_DigitMult (t, c, d[i]);
 619     if ((a[i] = b[i] - borrow) > (MAX_NN_DIGIT - borrow))
 620       borrow = 1;
 621     else
 622       borrow = 0;
 623     if ((a[i] -= t[0]) > (MAX_NN_DIGIT - t[0]))
 624       borrow++;
 625     borrow += t[1];
 626   }
 627
 628   return (borrow);
 629 }
 630
 631 /* Returns the significant length of a in bits, where a is a digit.
 632  */
 633 static unsigned int NN_DigitBits (a)
 634 NN_DIGIT a;
 635 {
 636   unsigned int i;
 637
 638   for (i = 0; i < NN_DIGIT_BITS; i++, a >>= 1)
 639     if (a == 0)
 640       break;
 641
 642   return (i);
 643 }