开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > Windows编程 > 钩子与API截获 > 查看源码
big_num.cpp
资源名称：HookAPI　[点击查看]
上传用户：nbcables
上传日期：2007-01-11
资源大小：1243k
文件大小：13k
源码类别：

钩子与API截获

开发平台：

Visual C++

big_num.cpp：源码内容
  1. /*
  2.  * NN.C - natural numbers routines
  3.  */
  5. #include "stdafx.h"
  6. #include "rsaref.h"
  7. #include "big_num.h"
  9. static NN_DIGIT NN_AddDigitMult PROTO_LIST 
  10.   ((NN_DIGIT *, NN_DIGIT *, NN_DIGIT, NN_DIGIT *, unsigned int));
  11. static NN_DIGIT NN_SubDigitMult PROTO_LIST 
  12.   ((NN_DIGIT *, NN_DIGIT *, NN_DIGIT, NN_DIGIT *, unsigned int));
  14. static unsigned int NN_DigitBits PROTO_LIST ((NN_DIGIT));
  16. /* Decodes character string b into a, where character string is ordered
  17.    from most to least significant.
  19.    Lengths: a[digits], b[len].
  20.    Assumes b[i] = 0 for i < len - digits * NN_DIGIT_LEN. (Otherwise most
  21.    significant bytes are truncated.)
  22.  */
  23. void NN_Decode (NN_DIGIT *a, unsigned int digits, unsigned char *b, unsigned int len)
  24. {
  25.   NN_DIGIT t;
  26.   int j;
  27.   unsigned int i, u;
  28.   
  29.   for (i = 0, j = len - 1; i < digits && j >= 0; i++) {
  30.     t = 0;
  31.     for (u = 0; j >= 0 && u < NN_DIGIT_BITS; j--, u += 8)
  32.       t |= ((NN_DIGIT)b[j]) << u;
  33.     a[i] = t;
  34.   }
  35.   
  36.   for (; i < digits; i++)
  37.     a[i] = 0;
  38. }
  40. /* Encodes b into character string a, where character string is ordered
  41.    from most to least significant.
  43.    Lengths: a[len], b[digits].
  44.    Assumes NN_Bits (b, digits) <= 8 * len. (Otherwise most significant
  45.    digits are truncated.)
  46.  */
  47. void NN_Encode (unsigned char *a, unsigned int len, NN_DIGIT *b, unsigned int digits)
  48. {
  49.   NN_DIGIT t;
  50.   int j;
  51.   unsigned int i, u;
  53.   for (i = 0, j = len - 1; i < digits && j >= 0; i++) {
  54.     t = b[i];
  55.     for (u = 0; j >= 0 && u < NN_DIGIT_BITS; j--, u += 8)
  56.       a[j] = (unsigned char)(t >> u);
  57.   }
  59.   for (; j >= 0; j--)
  60.     a[j] = 0;
  61. }
  63. /* Assigns a = b.
  65.    Lengths: a[digits], b[digits].
  66.  */
  67. void NN_Assign (NN_DIGIT *a, NN_DIGIT *b, unsigned int digits)
  68. {
  69.   unsigned int i;
  71.   for (i = 0; i < digits; i++)
  72.     a[i] = b[i];
  73. }
  75. /* Assigns a = 0.
  77.    Lengths: a[digits].
  78.  */
  79. void NN_AssignZero (NN_DIGIT *a, unsigned int digits)
  80. {
  81.   unsigned int i;
  83.   for (i = 0; i < digits; i++)
  84.     a[i] = 0;
  85. }
  87. /* Assigns a = 2^b.
  89.    Lengths: a[digits].
  90.    Requires b < digits * NN_DIGIT_BITS.
  91.  */
  92. void NN_Assign2Exp (NN_DIGIT *a, unsigned int b, unsigned int digits)
  93. {
  94.   NN_AssignZero (a, digits);
  96.   if (b >= digits * NN_DIGIT_BITS)
  97.     return;
  99.   a[b / NN_DIGIT_BITS] = (NN_DIGIT)1 << (b % NN_DIGIT_BITS);
  100. }
  102. /* Computes a = b + c. Returns carry.
  104.    Lengths: a[digits], b[digits], c[digits].
  105.  */
  106. NN_DIGIT NN_Add (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, unsigned int digits)
  107. {
  108.   NN_DIGIT ai, carry;
  109.   unsigned int i;
  111.   carry = 0;
  113.   for (i = 0; i < digits; i++) {
  114.     if ((ai = b[i] + carry) < carry)
  115.       ai = c[i];
  116.     else if ((ai += c[i]) < c[i])
  117.       carry = 1;
  118.     else
  119.       carry = 0;
  120.     a[i] = ai;
  121.   }
  123.   return (carry);
  124. }
  126. /* Computes a = b - c. Returns borrow.
  128.    Lengths: a[digits], b[digits], c[digits].
  129.  */
  130. NN_DIGIT NN_Sub (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, unsigned int digits)
  131. {
  132.   NN_DIGIT ai, borrow;
  133.   unsigned int i;
  135.   borrow = 0;
  137.   for (i = 0; i < digits; i++) {
  138.     if ((ai = b[i] - borrow) > (MAX_NN_DIGIT - borrow))
  139.       ai = MAX_NN_DIGIT - c[i];
  140.     else if ((ai -= c[i]) > (MAX_NN_DIGIT - c[i]))
  141.       borrow = 1;
  142.     else
  143.       borrow = 0;
  144.     a[i] = ai;
  145.   }
  147.   return (borrow);
  148. }
  150. /* Computes a = b * c.
  152.    Lengths: a[2*digits], b[digits], c[digits].
  153.    Assumes digits < MAX_NN_DIGITS.
  154.  */
  155. void NN_Mult (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, unsigned int digits)
  156. {
  157.   NN_DIGIT t[2*MAX_NN_DIGITS];
  158.   unsigned int bDigits, cDigits, i;
  160.   NN_AssignZero (t, 2 * digits);
  161.   
  162.   bDigits = NN_Digits (b, digits);
  163.   cDigits = NN_Digits (c, digits);
  165.   for (i = 0; i < bDigits; i++)
  166.     t[i+cDigits] += NN_AddDigitMult (&t[i], &t[i], b[i], c, cDigits);
  167.   
  168.   NN_Assign (a, t, 2 * digits);
  169.   
  170.   /* Zeroize potentially sensitive information.
  171.    */
  172.   R_memset ((POINTER)t, 0, sizeof (t));
  173. }
  175. /* Computes a = b * 2^c (i.e., shifts left c bits), returning carry.
  177.    Lengths: a[digits], b[digits].
  178.    Requires c < NN_DIGIT_BITS.
  179.  */
  180. NN_DIGIT NN_LShift (NN_DIGIT *a, NN_DIGIT *b, unsigned int c, unsigned int digits)
  181. {
  182.   NN_DIGIT bi, carry;
  183.   unsigned int i, t;
  184.   
  185.   if (c >= NN_DIGIT_BITS)
  186.     return (0);
  187.   
  188.   t = NN_DIGIT_BITS - c;
  190.   carry = 0;
  192.   for (i = 0; i < digits; i++) {
  193.     bi = b[i];
  194.     a[i] = (bi << c) | carry;
  195.     carry = c ? (bi >> t) : 0;
  196.   }
  197.   
  198.   return (carry);
  199. }
  201. /* Computes a = c div 2^c (i.e., shifts right c bits), returning carry.
  203.    Lengths: a[digits], b[digits].
  204.    Requires: c < NN_DIGIT_BITS.
  205.  */
  206. NN_DIGIT NN_RShift (NN_DIGIT *a, NN_DIGIT *b, unsigned int c, unsigned int digits)
  207. {
  208.   NN_DIGIT bi, carry;
  209.   int i;
  210.   unsigned int t;
  211.   
  212.   if (c >= NN_DIGIT_BITS)
  213.     return (0);
  214.   
  215.   t = NN_DIGIT_BITS - c;
  217.   carry = 0;
  219.   for (i = digits - 1; i >= 0; i--) {
  220.     bi = b[i];
  221.     a[i] = (bi >> c) | carry;
  222.     carry = c ? (bi << t) : 0;
  223.   }
  224.   
  225.   return (carry);
  226. }
  228. /* Computes a = c div d and b = c mod d.
  230.    Lengths: a[cDigits], b[dDigits], c[cDigits], d[dDigits].
  231.    Assumes d > 0, cDigits < 2 * MAX_NN_DIGITS,
  232.            dDigits < MAX_NN_DIGITS.
  233.  */
  234. void NN_Div (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, unsigned int cDigits, NN_DIGIT *d, unsigned int dDigits)
  235. {
  236.   NN_DIGIT ai, cc[2*MAX_NN_DIGITS+1], dd[MAX_NN_DIGITS], t;
  237.   int i;
  238.   unsigned int ddDigits, shift;
  239.   
  240.   ddDigits = NN_Digits (d, dDigits);
  241.   if (ddDigits == 0)
  242.     return;
  243.   
  244.   /* Normalize operands.
  245.    */
  246.   shift = NN_DIGIT_BITS - NN_DigitBits (d[ddDigits-1]);
  247.   NN_AssignZero (cc, ddDigits);
  248.   cc[cDigits] = NN_LShift (cc, c, shift, cDigits);
  249.   NN_LShift (dd, d, shift, ddDigits);
  250.   t = dd[ddDigits-1];
  251.   
  252.   NN_AssignZero (a, cDigits);
  254.   for (i = cDigits-ddDigits; i >= 0; i--) {
  255.     /* Underestimate quotient digit and subtract.
  256.      */
  257.     if (t == MAX_NN_DIGIT)
  258.       ai = cc[i+ddDigits];
  259.     else
  260.       NN_DigitDiv (&ai, &cc[i+ddDigits-1], t + 1);
  261.     cc[i+ddDigits] -= NN_SubDigitMult (&cc[i], &cc[i], ai, dd, ddDigits);
  263.     /* Correct estimate.
  264.      */
  265.     while (cc[i+ddDigits] || (NN_Cmp (&cc[i], dd, ddDigits) >= 0)) {
  266.       ai++;
  267.       cc[i+ddDigits] -= NN_Sub (&cc[i], &cc[i], dd, ddDigits);
  268.     }
  269.     
  270.     a[i] = ai;
  271.   }
  272.   
  273.   /* Restore result.
  274.    */
  275.   NN_AssignZero (b, dDigits);
  276.   NN_RShift (b, cc, shift, ddDigits);
  278.   /* Zeroize potentially sensitive information.
  279.    */
  280.   R_memset ((POINTER)cc, 0, sizeof (cc));
  281.   R_memset ((POINTER)dd, 0, sizeof (dd));
  282. }
  284. /* Computes a = b mod c.
  286.    Lengths: a[cDigits], b[bDigits], c[cDigits].
  287.    Assumes c > 0, bDigits < 2 * MAX_NN_DIGITS, cDigits < MAX_NN_DIGITS.
  288.  */
  289. void NN_Mod (NN_DIGIT *a, NN_DIGIT *b, unsigned int bDigits, NN_DIGIT *c, unsigned int cDigits)
  290. {
  291.   NN_DIGIT t[2 * MAX_NN_DIGITS];
  292.   
  293.   NN_Div (t, a, b, bDigits, c, cDigits);
  294.   
  295.   /* Zeroize potentially sensitive information.
  296.    */
  297.   R_memset ((POINTER)t, 0, sizeof (t));
  298. }
  300. /* Computes a = b * c mod d.
  302.    Lengths: a[digits], b[digits], c[digits], d[digits].
  303.    Assumes d > 0, digits < MAX_NN_DIGITS.
  304.  */
  305. void NN_ModMult (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, NN_DIGIT *d, unsigned int digits)
  306. {
  307.   NN_DIGIT t[2*MAX_NN_DIGITS];
  309.   NN_Mult (t, b, c, digits);
  310.   NN_Mod (a, t, 2 * digits, d, digits);
  311.   
  312.   /* Zeroize potentially sensitive information.
  313.    */
  314.   R_memset ((POINTER)t, 0, sizeof (t));
  315. }
  317. /* Computes a = b^c mod d.
  319.    Lengths: a[dDigits], b[dDigits], c[cDigits], d[dDigits].
  320.    Assumes d > 0, cDigits > 0, dDigits < MAX_NN_DIGITS.
  321.  */
  323. /* PGP 2.5's mpilib contains a faster modular exponentiation routine, mp_modexp.
  324.    If USEMPILIB is defined, NN_ModExp is replaced in the PGP 2.5 sources with a 
  325.    stub call to mp_modexp.  If USEMPILIB is not defined, we'll get a pure (albeit
  326.    slower) RSAREF implementation.
  328.    The RSAREF 2.0 license, clause 1(c), permits "...modify[ing] the Program in any
  329.    manner for porting or performance improvement purposes..." */
  331. #ifndef USEMPILIB
  332. void NN_ModExp (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, unsigned int cDigits, NN_DIGIT *d, unsigned int dDigits)
  333. {
  334.   NN_DIGIT bPower[3][MAX_NN_DIGITS], ci, t[MAX_NN_DIGITS];
  335.   int i;
  336.   unsigned int ciBits, j, s;
  338.   /* Store b, b^2 mod d, and b^3 mod d.
  339.    */
  340.   NN_Assign (bPower[0], b, dDigits);
  341.   NN_ModMult (bPower[1], bPower[0], b, d, dDigits);
  342.   NN_ModMult (bPower[2], bPower[1], b, d, dDigits);
  343.   
  344.   NN_ASSIGN_DIGIT (t, 1, dDigits);
  346.   cDigits = NN_Digits (c, cDigits);
  347.   for (i = cDigits - 1; i >= 0; i--) {
  348.     ci = c[i];
  349.     ciBits = NN_DIGIT_BITS;
  350.     
  351.     /* Scan past leading zero bits of most significant digit.
  352.      */
  353.     if (i == (int)(cDigits - 1)) {
  354.       while (! DIGIT_2MSB (ci)) {
  355.         ci <<= 2;
  356.         ciBits -= 2;
  357.       }
  358.     }
  360.     for (j = 0; j < ciBits; j += 2, ci <<= 2) {
  361.       /* Compute t = t^4 * b^s mod d, where s = two MSB's of ci.
  362.        */
  363.       NN_ModMult (t, t, t, d, dDigits);
  364.       NN_ModMult (t, t, t, d, dDigits);
  365.       if ((s = DIGIT_2MSB (ci)) != 0)
  366.         NN_ModMult (t, t, bPower[s-1], d, dDigits);
  367.     }
  368.   }
  369.   
  370.   NN_Assign (a, t, dDigits);
  371.   
  372.   /* Zeroize potentially sensitive information.
  373.    */
  374.   R_memset ((POINTER)bPower, 0, sizeof (bPower));
  375.   R_memset ((POINTER)t, 0, sizeof (t));
  376. }
  377. #endif
  379. /* Compute a = 1/b mod c, assuming inverse exists.
  380.    
  381.    Lengths: a[digits], b[digits], c[digits].
  382.    Assumes gcd (b, c) = 1, digits < MAX_NN_DIGITS.
  383.  */
  384. void NN_ModInv (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, unsigned int digits)
  385. {
  386.   NN_DIGIT q[MAX_NN_DIGITS], t1[MAX_NN_DIGITS], t3[MAX_NN_DIGITS],
  387.     u1[MAX_NN_DIGITS], u3[MAX_NN_DIGITS], v1[MAX_NN_DIGITS],
  388.     v3[MAX_NN_DIGITS], w[2*MAX_NN_DIGITS];
  389.   int u1Sign;
  391.   /* Apply extended Euclidean algorithm, modified to avoid negative
  392.      numbers.
  393.    */
  394.   NN_ASSIGN_DIGIT (u1, 1, digits);
  395.   NN_AssignZero (v1, digits);
  396.   NN_Assign (u3, b, digits);
  397.   NN_Assign (v3, c, digits);
  398.   u1Sign = 1;
  400.   while (! NN_Zero (v3, digits)) {
  401.     NN_Div (q, t3, u3, digits, v3, digits);
  402.     NN_Mult (w, q, v1, digits);
  403.     NN_Add (t1, u1, w, digits);
  404.     NN_Assign (u1, v1, digits);
  405.     NN_Assign (v1, t1, digits);
  406.     NN_Assign (u3, v3, digits);
  407.     NN_Assign (v3, t3, digits);
  408.     u1Sign = -u1Sign;
  409.   }
  410.   
  411.   /* Negate result if sign is negative.
  412.     */
  413.   if (u1Sign < 0)
  414.     NN_Sub (a, c, u1, digits);
  415.   else
  416.     NN_Assign (a, u1, digits);
  418.   /* Zeroize potentially sensitive information.
  419.    */
  420.   R_memset ((POINTER)q, 0, sizeof (q));
  421.   R_memset ((POINTER)t1, 0, sizeof (t1));
  422.   R_memset ((POINTER)t3, 0, sizeof (t3));
  423.   R_memset ((POINTER)u1, 0, sizeof (u1));
  424.   R_memset ((POINTER)u3, 0, sizeof (u3));
  425.   R_memset ((POINTER)v1, 0, sizeof (v1));
  426.   R_memset ((POINTER)v3, 0, sizeof (v3));
  427.   R_memset ((POINTER)w, 0, sizeof (w));
  428. }
  430. /* Computes a = gcd(b, c).
  432.    Lengths: a[digits], b[digits], c[digits].
  433.    Assumes b > c, digits < MAX_NN_DIGITS.
  434.  */
  435. void NN_Gcd (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, unsigned int digits)
  436. {
  437.   NN_DIGIT t[MAX_NN_DIGITS], u[MAX_NN_DIGITS], v[MAX_NN_DIGITS];
  439.   NN_Assign (u, b, digits);
  440.   NN_Assign (v, c, digits);
  442.   while (! NN_Zero (v, digits)) {
  443.     NN_Mod (t, u, digits, v, digits);
  444.     NN_Assign (u, v, digits);
  445.     NN_Assign (v, t, digits);
  446.   }
  448.   NN_Assign (a, u, digits);
  450.   /* Zeroize potentially sensitive information.
  451.    */
  452.   R_memset ((POINTER)t, 0, sizeof (t));
  453.   R_memset ((POINTER)u, 0, sizeof (u));
  454.   R_memset ((POINTER)v, 0, sizeof (v));
  455. }
  457. /* Returns sign of a - b.
  459.    Lengths: a[digits], b[digits].
  460.  */
  461. int NN_Cmp (NN_DIGIT *a, NN_DIGIT *b, unsigned int digits)
  462. {
  463.   int i;
  464.   
  465.   for (i = digits - 1; i >= 0; i--) {
  466.     if (a[i] > b[i])
  467.       return (1);
  468.     if (a[i] < b[i])
  469.       return (-1);
  470.   }
  472.   return (0);
  473. }
  475. /* Returns nonzero iff a is zero.
  477.    Lengths: a[digits].
  478.  */
  479. int NN_Zero (NN_DIGIT *a, unsigned int digits)
  480. {
  481.   unsigned int i;
  482.   
  483.   for (i = 0; i < digits; i++)
  484.     if (a[i])
  485.       return (0);
  486.     
  487.   return (1);
  488. }
  490. /* Returns the significant length of a in bits.
  492.    Lengths: a[digits].
  493.  */
  494. unsigned int NN_Bits (NN_DIGIT *a, unsigned int digits)
  495. {
  496.   if ((digits = NN_Digits (a, digits)) == 0)
  497.     return (0);
  499.   return ((digits - 1) * NN_DIGIT_BITS + NN_DigitBits (a[digits-1]));
  500. }
  502. /* Returns the significant length of a in digits.
  504.    Lengths: a[digits].
  505.  */
  506. unsigned int NN_Digits (NN_DIGIT *a, unsigned int digits)
  507. {
  508.   int i;
  509.   
  510.   for (i = digits - 1; i >= 0; i--)
  511.     if (a[i])
  512.       break;
  514.   return (i + 1);
  515. }
  517. /* Computes a = b + c*d, where c is a digit. Returns carry.
  519.    Lengths: a[digits], b[digits], d[digits].
  520.  */
  521. static NN_DIGIT NN_AddDigitMult (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT c, NN_DIGIT *d, unsigned int digits)
  522. {
  523.   NN_DIGIT carry, t[2];
  524.   unsigned int i;
  526.   if (c == 0)
  527.     return (0);
  529.   carry = 0;
  530.   for (i = 0; i < digits; i++) {
  531.     NN_DigitMult (t, c, d[i]);
  532.     if ((a[i] = b[i] + carry) < carry)
  533.       carry = 1;
  534.     else
  535.       carry = 0;
  536.     if ((a[i] += t[0]) < t[0])
  537.       carry++;
  538.     carry += t[1];
  539.   }
  540.   
  541.   return (carry);
  542. }
  544. /* Computes a = b - c*d, where c is a digit. Returns borrow.
  546.    Lengths: a[digits], b[digits], d[digits].
  547.  */
  548. static NN_DIGIT NN_SubDigitMult (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT c, NN_DIGIT *d, unsigned int digits)
  549. {
  550.   NN_DIGIT borrow, t[2];
  551.   unsigned int i;
  553.   if (c == 0)
  554.     return (0);
  556.   borrow = 0;
  557.   for (i = 0; i < digits; i++) {
  558.     NN_DigitMult (t, c, d[i]);
  559.     if ((a[i] = b[i] - borrow) > (MAX_NN_DIGIT - borrow))
  560.       borrow = 1;
  561.     else
  562.       borrow = 0;
  563.     if ((a[i] -= t[0]) > (MAX_NN_DIGIT - t[0]))
  564.       borrow++;
  565.     borrow += t[1];
  566.   }
  567.   
  568.   return (borrow);
  569. }
  571. /* Returns the significant length of a in bits, where a is a digit.
  572.  */
  573. static unsigned int NN_DigitBits (NN_DIGIT a)
  574. {
  575.   unsigned int i;
  576.   
  577.   for (i = 0; i < NN_DIGIT_BITS; i++, a >>= 1)
  578.     if (a == 0)
  579.       break;
  580.     
  581.   return (i);
  582. }