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

源码开发语言/平台
当前位置：首页 > 源码/资料 > 加密解密 > CA认证 > 查看源码
mpmontg.c
资源名称：nss-3.1.1.tar.gz　[点击查看]
上传用户：lyxiangda
上传日期：2007-01-12
资源大小：3042k
文件大小：11k
源码类别：

CA认证

开发平台：

WINDOWS

mpmontg.c：源码内容
  1. /*
  2.  * The contents of this file are subject to the Mozilla Public
  3.  * License Version 1.1 (the "License"); you may not use this file
  4.  * except in compliance with the License. You may obtain a copy of
  5.  * the License at http://www.mozilla.org/MPL/
  6.  * 
  7.  * Software distributed under the License is distributed on an "AS
  8.  * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
  9.  * implied. See the License for the specific language governing
  10.  * rights and limitations under the License.
  11.  * 
  12.  * The Original Code is the Netscape security libraries.
  13.  * 
  14.  * The Initial Developer of the Original Code is Netscape
  15.  * Communications Corporation. Portions created by Netscape are 
  16.  * Copyright (C) 2000 Netscape Communications Corporation.  All
  17.  * Rights Reserved.
  18.  * 
  19.  * Contributor(s):
  20.  * 
  21.  * Alternatively, the contents of this file may be used under the
  22.  * terms of the GNU General Public License Version 2 or later (the
  23.  * "GPL"), in which case the provisions of the GPL are applicable 
  24.  * instead of those above. If you wish to allow use of your 
  25.  * version of this file only under the terms of the GPL and not to
  26.  * allow others to use your version of this file under the MPL,
  27.  * indicate your decision by deleting the provisions above and
  28.  * replace them with the notice and other provisions required by
  29.  * the GPL.  If you do not delete the provisions above, a recipient
  30.  * may use your version of this file under either the MPL or the
  31.  * GPL.
  32.  *  $Id: mpmontg.c,v 1.8 2000/09/14 00:30:51 nelsonb%netscape.com Exp $
  33.  */
  35. /* This file implements moduluar exponentiation using Montgomery's
  36.  * method for modular reduction.  This file implements the method
  37.  * described as "Improvement 1" in the paper "A Cryptogrpahic Library for
  38.  * the Motorola DSP56000" by Stephen R. Dusse' and Burton S. Kaliski Jr.
  39.  * published in "Advances in Cryptology: Proceedings of EUROCRYPT '90"
  40.  * "Lecture Notes in Computer Science" volume 473, 1991, pg 230-244,
  41.  * published by Springer Verlag.
  42.  */
  44. #include <string.h>
  45. #include "mpi-priv.h"
  46. #include "mplogic.h"
  47. #include "mpprime.h"
  49. #define STATIC
  50. /* #define DEBUG 1  */
  52. #define MAX_WINDOW_BITS 6
  53. #define MAX_ODD_INTS    32   /* 2 ** (WINDOW_BITS - 1) */
  55. typedef struct {
  56.   mp_int       N; /* modulus N */
  57.   mp_digit     n0prime; /* n0' = - (n0 ** -1) mod MP_RADIX */
  58.   mp_size      b; /* R == 2 ** b,  also b = # significant bits in N */
  59. } mp_mont_modulus;
  61. mp_err   s_mp_mul_mont(const mp_int *a, const mp_int *b, mp_int *c, 
  62.                mp_mont_modulus *mmm);
  64. /* computes T = REDC(T), 2^b == R */
  65. STATIC
  66. mp_err s_mp_redc(mp_int *T, mp_mont_modulus *mmm)
  67. {
  68.   mp_err res;
  69.   mp_size i;
  70. #ifdef DEBUG
  71.   mp_int m;
  72.   MP_DIGITS(&m) = 0;
  73. #endif
  75.   i = MP_USED(T) + MP_USED(&mmm->N) + 2;
  76.   MP_CHECKOK( s_mp_pad(T, i) );
  77.   for (i = 0; i < MP_USED(&mmm->N); ++i ) {
  78.     mp_digit m_i = MP_DIGIT(T, i) * mmm->n0prime;
  79.     /* T += N * m_i * (MP_RADIX ** i); */
  80.     MP_CHECKOK( s_mp_mul_d_add_offset(&mmm->N, m_i, T, i) );
  81.   }
  82.   s_mp_clamp(T);
  84.   /* T /= R */
  85. #ifdef DEBUG
  86.   MP_CHECKOK( mp_init(&m) );
  87.   MP_CHECKOK( mp_div_2d(T, mmm->b, T, &m));
  88.   /* here, remainder m should be equal to zero */
  89.   if (mp_cmp_z(&m) != 0) {
  90.     res = MP_UNDEF;
  91.     goto CLEANUP;
  92.   }
  93. #else
  94.   s_mp_div_2d(T, mmm->b); 
  95. #endif
  97.   if ((res = s_mp_cmp(T, &mmm->N)) >= 0) {
  98.     /* T = T - N */
  99.     MP_CHECKOK( s_mp_sub(T, &mmm->N) );
  100. #ifdef DEBUG
  101.     if ((res = mp_cmp(T, &mmm->N)) >= 0) {
  102.       res = MP_UNDEF;
  103.       goto CLEANUP;
  104.     }
  105. #endif
  106.   }
  107.   res = MP_OKAY;
  108. CLEANUP:
  109. #ifdef DEBUG
  110.   mp_clear(&m);
  111. #endif
  112.   return res;
  113. }
  115. #if !defined(MP_ASSEMBLY_MUL_MONT) && !defined(MP_MONT_USE_MP_MUL)
  116. mp_err s_mp_mul_mont(const mp_int *a, const mp_int *b, mp_int *c, 
  117.            mp_mont_modulus *mmm)
  118. {
  119.   mp_digit *pb;
  120.   mp_digit m_i;
  121.   mp_err   res;
  122.   mp_size  ib;
  123.   mp_size  useda, usedb;
  125.   ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
  127.   if (MP_USED(a) < MP_USED(b)) {
  128.     const mp_int *xch = b; /* switch a and b, to do fewer outer loops */
  129.     b = a;
  130.     a = xch;
  131.   }
  133.   MP_USED(c) = 1; MP_DIGIT(c, 0) = 0;
  134.   ib = MP_USED(a) + MP_MAX(MP_USED(b), MP_USED(&mmm->N)) + 2;
  135.   if((res = s_mp_pad(c, ib)) != MP_OKAY)
  136.     goto CLEANUP;
  138.   useda = MP_USED(a);
  139.   pb = MP_DIGITS(b);
  140.   s_mpv_mul_d(MP_DIGITS(a), useda, *pb++, MP_DIGITS(c));
  141.   s_mp_setz(MP_DIGITS(c) + useda + 1, ib - (useda + 1));
  142.   m_i = MP_DIGIT(c, 0) * mmm->n0prime;
  143.   s_mp_mul_d_add_offset(&mmm->N, m_i, c, 0);
  145.   /* Outer loop:  Digits of b */
  146.   usedb = MP_USED(b);
  147.   for (ib = 1; ib < usedb; ib++) {
  148.     mp_digit b_i    = *pb++;
  150.     /* Inner product:  Digits of a */
  151.     if (b_i)
  152.       s_mpv_mul_d_add_prop(MP_DIGITS(a), useda, b_i, MP_DIGITS(c) + ib);
  153.     m_i = MP_DIGIT(c, ib) * mmm->n0prime;
  154.     s_mp_mul_d_add_offset(&mmm->N, m_i, c, ib);
  155.   }
  156.   if (usedb < MP_USED(&mmm->N)) {
  157.     for (usedb = MP_USED(&mmm->N); ib < usedb; ++ib ) {
  158.       m_i = MP_DIGIT(c, ib) * mmm->n0prime;
  159.       s_mp_mul_d_add_offset(&mmm->N, m_i, c, ib);
  160.     }
  161.   }
  162.   s_mp_clamp(c);
  163.   s_mp_div_2d(c, mmm->b); 
  164.   if (s_mp_cmp(c, &mmm->N) >= 0) {
  165.     MP_CHECKOK( s_mp_sub(c, &mmm->N) );
  166.   }
  167.   res = MP_OKAY;
  169. CLEANUP:
  170.   return res;
  171. }
  172. #endif
  174. STATIC
  175. mp_err s_mp_to_mont(const mp_int *x, mp_mont_modulus *mmm, mp_int *xMont)
  176. {
  177.   mp_err res;
  179.   /* xMont = x * R mod N   where  N is modulus */
  180.   MP_CHECKOK( mpl_lsh(x, xMont, mmm->b) );   /* xMont = x << b */
  181.   MP_CHECKOK( mp_div(xMont, &mmm->N, 0, xMont) ); /*         mod N */
  182. CLEANUP:
  183.   return res;
  184. }
  187. mp_err mp_exptmod(const mp_int *inBase, const mp_int *exponent, 
  188.   const mp_int *modulus, mp_int *result)
  189. {
  190.   const mp_int *base;
  191.   mp_int *pa1, *pa2, *ptmp;
  192.   mp_size bits_in_exponent;
  193.   mp_size i;
  194.   mp_size window_bits, odd_ints;
  195.   mp_err res;
  196.   mp_int square, accum1, accum2, goodBase;
  197.   mp_mont_modulus mmm;
  199.   /* function for computing n0prime only works if n0 is odd */
  200.   if (!mp_isodd(modulus))
  201.     return s_mp_exptmod(inBase, exponent, modulus, result);
  203.   MP_DIGITS(&square) = 0;
  204.   MP_DIGITS(&accum1) = 0;
  205.   MP_DIGITS(&accum2) = 0;
  206.   MP_DIGITS(&goodBase) = 0;
  208.   if (mp_cmp(inBase, modulus) < 0) {
  209.     base = inBase;
  210.   } else {
  211.     MP_CHECKOK( mp_init(&goodBase) );
  212.     base = &goodBase;
  213.     MP_CHECKOK( mp_mod(inBase, modulus, &goodBase) );
  214.   }
  216.   MP_CHECKOK( mp_init_size(&square, 2 * MP_USED(modulus) + 2) );
  217.   MP_CHECKOK( mp_init_size(&accum1, 3 * MP_USED(modulus) + 2) );
  218.   MP_CHECKOK( mp_init_size(&accum2, 3 * MP_USED(modulus) + 2) );
  220.   mmm.N = *modulus; /* a copy of the mp_int struct */
  221.   i = mpl_significant_bits(modulus);
  222.   i += MP_DIGIT_BIT - 1;
  223.   mmm.b = i - i % MP_DIGIT_BIT;
  225.   /* compute n0', given n0, n0' = -(n0 ** -1) mod MP_RADIX
  226.   ** where n0 = least significant mp_digit of N, the modulus.
  227.   */
  228.   mmm.n0prime = 0 - s_mp_invmod_radix( MP_DIGIT(modulus, 0) );
  230.   MP_CHECKOK( s_mp_to_mont(base, &mmm, &square) );
  232.   bits_in_exponent = mpl_significant_bits(exponent);
  233.   if (bits_in_exponent > 480)
  234.     window_bits = 6;
  235.   else if (bits_in_exponent > 160)
  236.     window_bits = 5;
  237.   else
  238.     window_bits = 4;
  239.   odd_ints = 1 << (window_bits - 1);
  240.   i = bits_in_exponent % window_bits;
  241.   if (i != 0) {
  242.     bits_in_exponent += window_bits - i;
  243.   } 
  244.   {
  245.     /* oddPowers[i] = base ** (2*i + 1); */
  246.     int expOff;
  247.     /* power2 = base ** 2; oddPowers[i] = base ** (2*i + 1); */
  248.     mp_int power2, oddPowers[MAX_ODD_INTS];
  250.     MP_CHECKOK( mp_init_copy(oddPowers, &square) );
  252.     mp_init_size(&power2, MP_USED(modulus) + 2 * MP_USED(&square) + 2);
  253.     MP_CHECKOK( mp_sqr(&square, &power2) ); /* square = square ** 2 */
  254.     MP_CHECKOK( s_mp_redc(&power2, &mmm) );
  256.     for (i = 1; i < odd_ints; ++i) {
  257.       mp_init_size(oddPowers + i, MP_USED(modulus) + 2 * MP_USED(&power2) + 2);
  258.       MP_CHECKOK( mp_mul(oddPowers + (i - 1), &power2, oddPowers + i) );
  259.       MP_CHECKOK( s_mp_redc(oddPowers + i, &mmm) );
  260.     }
  261.     mp_set(&accum1, 1);
  262.     MP_CHECKOK( s_mp_to_mont(&accum1, &mmm, &accum1) );
  263.     pa1 = &accum1;
  264.     pa2 = &accum2;
  266. #define SQR(a,b) 
  267.     MP_CHECKOK( mp_sqr(a, b) );
  268.     MP_CHECKOK( s_mp_redc(b, &mmm) )
  270. #if defined(MP_MONT_USE_MP_MUL)
  271. #define MUL(x,a,b) 
  272.     MP_CHECKOK( mp_mul(a, oddPowers + (x), b) ); 
  273.     MP_CHECKOK( s_mp_redc(b, &mmm) ) 
  274. #else
  275. #define MUL(x,a,b) 
  276.     MP_CHECKOK( s_mp_mul_mont(a, oddPowers + (x), b, &mmm) )
  277. #endif
  279. #define SWAPPA ptmp = pa1; pa1 = pa2; pa2 = ptmp
  281.     for (expOff = bits_in_exponent - window_bits; expOff >= 0; expOff -= window_bits) {
  282.       mp_size smallExp;
  283.       MP_CHECKOK( mpl_get_bits(exponent, expOff, window_bits) );
  284.       smallExp = (mp_size)res;
  286.       if (window_bits == 4) {
  287. if (!smallExp) {
  288.   SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
  289. } else if (smallExp & 1) {
  290.   SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
  291.   MUL(smallExp/2, pa1,pa2); SWAPPA;
  292. } else if (smallExp & 2) {
  293.   SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); 
  294.   MUL(smallExp/4,pa2,pa1); SQR(pa1,pa2); SWAPPA;
  295. } else if (smallExp & 4) {
  296.   SQR(pa1,pa2); SQR(pa2,pa1); MUL(smallExp/8,pa1,pa2); 
  297.   SQR(pa2,pa1); SQR(pa1,pa2); SWAPPA;
  298. } else if (smallExp & 8) {
  299.   SQR(pa1,pa2); MUL(smallExp/16,pa2,pa1); SQR(pa1,pa2); 
  300.   SQR(pa2,pa1); SQR(pa1,pa2); SWAPPA;
  301. } else {
  302.   abort();
  303. }
  304.       } else if (window_bits == 5) {
  305. if (!smallExp) {
  306.   SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
  307.   SQR(pa1,pa2); SWAPPA;
  308. } else if (smallExp & 1) {
  309.   SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
  310.   SQR(pa1,pa2); MUL(smallExp/2,pa2,pa1);
  311. } else if (smallExp & 2) {
  312.   SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
  313.   MUL(smallExp/4,pa1,pa2); SQR(pa2,pa1);
  314. } else if (smallExp & 4) {
  315.   SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); 
  316.   MUL(smallExp/8,pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
  317. } else if (smallExp & 8) {
  318.   SQR(pa1,pa2); SQR(pa2,pa1); MUL(smallExp/16,pa1,pa2); 
  319.   SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
  320. } else if (smallExp & 0x10) {
  321.   SQR(pa1,pa2); MUL(smallExp/32,pa2,pa1); SQR(pa1,pa2); 
  322.   SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
  323. } else {
  324.     abort();
  325. }
  326.       } else if (window_bits == 6) {
  327. if (!smallExp) {
  328.   SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
  329.   SQR(pa1,pa2); SQR(pa2,pa1);
  330. } else if (smallExp & 1) {
  331.   SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
  332.   SQR(pa1,pa2); SQR(pa2,pa1); MUL(smallExp/2,pa1,pa2); SWAPPA;
  333. } else if (smallExp & 2) {
  334.   SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
  335.   SQR(pa1,pa2); MUL(smallExp/4,pa2,pa1); SQR(pa1,pa2); SWAPPA;
  336. } else if (smallExp & 4) {
  337.   SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
  338.   MUL(smallExp/8,pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SWAPPA;
  339. } else if (smallExp & 8) {
  340.   SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); 
  341.   MUL(smallExp/16,pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
  342.   SQR(pa1,pa2); SWAPPA;
  343. } else if (smallExp & 0x10) {
  344.   SQR(pa1,pa2); SQR(pa2,pa1); MUL(smallExp/32,pa1,pa2); 
  345.   SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SWAPPA;
  346. } else if (smallExp & 0x20) {
  347.   SQR(pa1,pa2); MUL(smallExp/64,pa2,pa1); SQR(pa1,pa2); 
  348.   SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SWAPPA;
  349. } else {
  350.   abort();
  351. }
  352.       } else {
  353. abort();
  354.       }
  355.     }
  357.     mp_clear(&power2);
  358.     for (i = 0; i < odd_ints; ++i) {
  359.       mp_clear(oddPowers + i);
  360.     }
  361.   }
  362.   res = s_mp_redc(pa1, &mmm);
  363.   mp_exch(pa1, result);
  364. CLEANUP:
  365.   mp_clear(&square);
  366.   mp_clear(&accum1);
  367.   mp_clear(&accum2);
  368.   mp_clear(&goodBase);
  369.   /* Don't mp_clear mmm.N because it is merely a copy of modulus.
  370.   ** Just zap it.
  371.   */
  372.   memset(&mmm, 0, sizeof mmm);
  373.   return res;
  374. }