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