![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to nn.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [rsaref] / rsaref / source|
Return to nn.c CVS log | Up to [rsaref] / rsaref / source |
1.1 root 1: /* NN.C - natural numbers routines
2: */
3:
1.1.1.2 ! root 4: /* Copyright (C) RSA Laboratories, a division of RSA Data Security,
! 5: Inc., created 1991. All rights reserved.
1.1 root 6: */
7:
1.1.1.2 ! root 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:
1.1 root 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:
1.1.1.2 ! root 33: Lengths: a[digits], b[len].
1.1 root 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:
1.1.1.2 ! root 46: for (i = 0, j = len - 1; i < digits && j >= 0; i++) {
1.1 root 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:
1.1.1.2 ! root 73: for (i = 0, j = len - 1; i < digits && j >= 0; i++) {
1.1 root 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:
1.1.1.2 ! root 83: /* Assigns a = b.
1.1 root 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:
1.1.1.2 ! root 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:
1.1 root 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].
1.1.1.2 ! root 362: Assumes d > 0, cDigits > 0, dDigits < MAX_NN_DIGITS.
1.1 root 363: */
1.1.1.2 ! root 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
1.1 root 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) {
1.1.1.2 ! root 405: /* Compute t = t^4 * b^s mod d, where s = two MSB's of ci.
1.1 root 406: */
407: NN_ModMult (t, t, t, d, dDigits);
408: NN_ModMult (t, t, t, d, dDigits);
1.1.1.2 ! root 409: if ((s = DIGIT_2MSB (ci)) != 0)
1.1 root 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: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.