![[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 [PGP] / pgp / rsaref / source|
Return to nn.c CVS log | Up to [PGP] / pgp / rsaref / source |
1.1 root 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: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.