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