| [23095] | 1 | /* NN.H - header file for NN.C |
|---|
| 2 | */ |
|---|
| 3 | |
|---|
| 4 | /* Copyright (C) RSA Laboratories, a division of RSA Data Security, |
|---|
| 5 | Inc., created 1991. All rights reserved. |
|---|
| 6 | */ |
|---|
| 7 | |
|---|
| 8 | /* Type definitions. |
|---|
| 9 | */ |
|---|
| 10 | typedef UINT4 NN_DIGIT; |
|---|
| 11 | typedef UINT2 NN_HALF_DIGIT; |
|---|
| 12 | |
|---|
| 13 | /* Constants. |
|---|
| 14 | |
|---|
| 15 | Note: MAX_NN_DIGITS is long enough to hold any RSA modulus, plus |
|---|
| 16 | one more digit as required by R_GeneratePEMKeys (for n and phiN, |
|---|
| 17 | whose lengths must be even). All natural numbers have at most |
|---|
| 18 | MAX_NN_DIGITS digits, except for double-length intermediate values |
|---|
| 19 | in NN_Mult (t), NN_ModMult (t), NN_ModInv (w), and NN_Div (c). |
|---|
| 20 | */ |
|---|
| 21 | /* Length of digit in bits */ |
|---|
| 22 | #define NN_DIGIT_BITS 32 |
|---|
| 23 | #define NN_HALF_DIGIT_BITS 16 |
|---|
| 24 | /* Length of digit in bytes */ |
|---|
| 25 | #define NN_DIGIT_LEN (NN_DIGIT_BITS / 8) |
|---|
| 26 | /* Maximum length in digits */ |
|---|
| 27 | #define MAX_NN_DIGITS \ |
|---|
| 28 | ((MAX_RSA_MODULUS_LEN + NN_DIGIT_LEN - 1) / NN_DIGIT_LEN + 1) |
|---|
| 29 | /* Maximum digits */ |
|---|
| 30 | #define MAX_NN_DIGIT 0xffffffff |
|---|
| 31 | #define MAX_NN_HALF_DIGIT 0xffff |
|---|
| 32 | |
|---|
| 33 | /* Macros. |
|---|
| 34 | */ |
|---|
| 35 | #define LOW_HALF(x) ((x) & MAX_NN_HALF_DIGIT) |
|---|
| 36 | #define HIGH_HALF(x) (((x) >> NN_HALF_DIGIT_BITS) & MAX_NN_HALF_DIGIT) |
|---|
| 37 | #define TO_HIGH_HALF(x) (((NN_DIGIT)(x)) << NN_HALF_DIGIT_BITS) |
|---|
| 38 | #define DIGIT_MSB(x) (unsigned int)(((x) >> (NN_DIGIT_BITS - 1)) & 1) |
|---|
| 39 | #define DIGIT_2MSB(x) (unsigned int)(((x) >> (NN_DIGIT_BITS - 2)) & 3) |
|---|
| 40 | |
|---|
| 41 | /* CONVERSIONS |
|---|
| 42 | NN_Decode (a, digits, b, len) Decodes character string b into a. |
|---|
| 43 | NN_Encode (a, len, b, digits) Encodes a into character string b. |
|---|
| 44 | |
|---|
| 45 | ASSIGNMENTS |
|---|
| 46 | NN_Assign (a, b, digits) Assigns a = b. |
|---|
| 47 | NN_ASSIGN_DIGIT (a, b, digits) Assigns a = b, where b is a digit. |
|---|
| 48 | NN_AssignZero (a, b, digits) Assigns a = 0. |
|---|
| 49 | NN_Assign2Exp (a, b, digits) Assigns a = 2^b. |
|---|
| 50 | |
|---|
| 51 | ARITHMETIC OPERATIONS |
|---|
| 52 | NN_Add (a, b, c, digits) Computes a = b + c. |
|---|
| 53 | NN_Sub (a, b, c, digits) Computes a = b - c. |
|---|
| 54 | NN_Mult (a, b, c, digits) Computes a = b * c. |
|---|
| 55 | NN_LShift (a, b, c, digits) Computes a = b * 2^c. |
|---|
| 56 | NN_RShift (a, b, c, digits) Computes a = b / 2^c. |
|---|
| 57 | NN_Div (a, b, c, cDigits, d, dDigits) Computes a = c div d and b = c mod d. |
|---|
| 58 | |
|---|
| 59 | NUMBER THEORY |
|---|
| 60 | NN_Mod (a, b, bDigits, c, cDigits) Computes a = b mod c. |
|---|
| 61 | NN_ModMult (a, b, c, d, digits) Computes a = b * c mod d. |
|---|
| 62 | NN_ModExp (a, b, c, cDigits, d, dDigits) Computes a = b^c mod d. |
|---|
| 63 | NN_ModInv (a, b, c, digits) Computes a = 1/b mod c. |
|---|
| 64 | NN_Gcd (a, b, c, digits) Computes a = gcd (b, c). |
|---|
| 65 | |
|---|
| 66 | OTHER OPERATIONS |
|---|
| 67 | NN_EVEN (a, digits) Returns 1 iff a is even. |
|---|
| 68 | NN_Cmp (a, b, digits) Returns sign of a - b. |
|---|
| 69 | NN_EQUAL (a, digits) Returns 1 iff a = b. |
|---|
| 70 | NN_Zero (a, digits) Returns 1 iff a = 0. |
|---|
| 71 | NN_Digits (a, digits) Returns significant length of a in digits. |
|---|
| 72 | NN_Bits (a, digits) Returns significant length of a in bits. |
|---|
| 73 | */ |
|---|
| 74 | void NN_Decode PROTO_LIST |
|---|
| 75 | ((NN_DIGIT *, unsigned int, unsigned char *, unsigned int)); |
|---|
| 76 | void NN_Encode PROTO_LIST |
|---|
| 77 | ((unsigned char *, unsigned int, NN_DIGIT *, unsigned int)); |
|---|
| 78 | |
|---|
| 79 | void NN_Assign PROTO_LIST ((NN_DIGIT *, NN_DIGIT *, unsigned int)); |
|---|
| 80 | void NN_AssignZero PROTO_LIST ((NN_DIGIT *, unsigned int)); |
|---|
| 81 | void NN_Assign2Exp PROTO_LIST ((NN_DIGIT *, unsigned int, unsigned int)); |
|---|
| 82 | |
|---|
| 83 | NN_DIGIT NN_Add PROTO_LIST |
|---|
| 84 | ((NN_DIGIT *, NN_DIGIT *, NN_DIGIT *, unsigned int)); |
|---|
| 85 | NN_DIGIT NN_Sub PROTO_LIST |
|---|
| 86 | ((NN_DIGIT *, NN_DIGIT *, NN_DIGIT *, unsigned int)); |
|---|
| 87 | void NN_Mult PROTO_LIST ((NN_DIGIT *, NN_DIGIT *, NN_DIGIT *, unsigned int)); |
|---|
| 88 | void NN_Div PROTO_LIST |
|---|
| 89 | ((NN_DIGIT *, NN_DIGIT *, NN_DIGIT *, unsigned int, NN_DIGIT *, |
|---|
| 90 | unsigned int)); |
|---|
| 91 | NN_DIGIT NN_LShift PROTO_LIST |
|---|
| 92 | ((NN_DIGIT *, NN_DIGIT *, unsigned int, unsigned int)); |
|---|
| 93 | NN_DIGIT NN_RShift PROTO_LIST |
|---|
| 94 | ((NN_DIGIT *, NN_DIGIT *, unsigned int, unsigned int)); |
|---|
| 95 | |
|---|
| 96 | void NN_Mod PROTO_LIST |
|---|
| 97 | ((NN_DIGIT *, NN_DIGIT *, unsigned int, NN_DIGIT *, unsigned int)); |
|---|
| 98 | void NN_ModMult PROTO_LIST |
|---|
| 99 | ((NN_DIGIT *, NN_DIGIT *, NN_DIGIT *, NN_DIGIT *, unsigned int)); |
|---|
| 100 | void NN_ModExp PROTO_LIST |
|---|
| 101 | ((NN_DIGIT *, NN_DIGIT *, NN_DIGIT *, unsigned int, NN_DIGIT *, |
|---|
| 102 | unsigned int)); |
|---|
| 103 | void NN_ModInv PROTO_LIST |
|---|
| 104 | ((NN_DIGIT *, NN_DIGIT *, NN_DIGIT *, unsigned int)); |
|---|
| 105 | void NN_Gcd PROTO_LIST ((NN_DIGIT *, NN_DIGIT *, NN_DIGIT *, unsigned int)); |
|---|
| 106 | |
|---|
| 107 | int NN_Cmp PROTO_LIST ((NN_DIGIT *, NN_DIGIT *, unsigned int)); |
|---|
| 108 | int NN_Zero PROTO_LIST ((NN_DIGIT *, unsigned int)); |
|---|
| 109 | unsigned int NN_Bits PROTO_LIST ((NN_DIGIT *, unsigned int)); |
|---|
| 110 | unsigned int NN_Digits PROTO_LIST ((NN_DIGIT *, unsigned int)); |
|---|
| 111 | |
|---|
| 112 | #define NN_ASSIGN_DIGIT(a, b, digits) {NN_AssignZero (a, digits); a[0] = b;} |
|---|
| 113 | #define NN_EQUAL(a, b, digits) (! NN_Cmp (a, b, digits)) |
|---|
| 114 | #define NN_EVEN(a, digits) (((digits) == 0) || ! (a[0] & 1)) |
|---|
