util/rsaref/nn.h

   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))