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

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

CA认证

开发平台：

WINDOWS

rsa.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) 1994-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.  *
  33.  */
  35. /*
  36.  * RSA key generation, public key op, private key op.
  37.  *
  38.  * $Id: rsa.c,v 1.17 2000/10/02 17:39:37 mcgreer%netscape.com Exp $
  39.  */
  41. #include "secerr.h"
  43. #include "blapi.h"
  44. #include "mpi.h"
  45. #include "mpprime.h"
  46. #include "secmpi.h"
  47. #include "secitem.h"
  49. /*
  50. ** RSA encryption/decryption. When encrypting/decrypting the output
  51. ** buffer must be at least the size of the public key modulus.
  52. */
  54. static SECStatus
  55. rsa_keygen_from_primes(mp_int *p, mp_int *q, mp_int *e, RSAPrivateKey *key)
  56. {
  57.     mp_int n, d, phi;
  58.     mp_int psub1, qsub1, tmp;
  59.     mp_err   err = MP_OKAY;
  60.     SECStatus rv = SECSuccess;
  61.     MP_DIGITS(&n)     = 0;
  62.     MP_DIGITS(&d)     = 0;
  63.     MP_DIGITS(&phi)   = 0;
  64.     MP_DIGITS(&psub1) = 0;
  65.     MP_DIGITS(&qsub1) = 0;
  66.     MP_DIGITS(&tmp)   = 0;
  67.     CHECK_MPI_OK( mp_init(&n)     );
  68.     CHECK_MPI_OK( mp_init(&d)     );
  69.     CHECK_MPI_OK( mp_init(&phi)   );
  70.     CHECK_MPI_OK( mp_init(&psub1) );
  71.     CHECK_MPI_OK( mp_init(&qsub1) );
  72.     CHECK_MPI_OK( mp_init(&tmp)   );
  73.     /* 1.  Compute n = p*q */
  74.     CHECK_MPI_OK( mp_mul(p, q, &n) );
  75.     /* 2.  Compute phi = (p-1)*(q-1) */
  76.     CHECK_MPI_OK( mp_sub_d(p, 1, &psub1) );
  77.     CHECK_MPI_OK( mp_sub_d(q, 1, &qsub1) );
  78.     CHECK_MPI_OK( mp_mul(&psub1, &qsub1, &phi) );
  79.     /* 3.  Compute d = e**-1 mod(phi) using extended Euclidean algorithm */
  80.     CHECK_MPI_OK( mp_xgcd(e, &phi, &tmp, &d, NULL) );
  81.     CHECK_MPI_OK( mp_mod(&d, &phi, &d) );
  82.     /*     Verify that phi(n) and e have no common divisors */
  83.     if (mp_cmp_d(&tmp, 1) != 0) { 
  84. PORT_SetError(SEC_ERROR_NEED_RANDOM);
  85. rv = SECFailure;
  86. goto cleanup;
  87.     }
  88.     MPINT_TO_SECITEM(&n, &key->modulus, key->arena);
  89.     MPINT_TO_SECITEM(&d, &key->privateExponent, key->arena);
  90.     /* 4.  Compute exponent1 = d mod (p-1) */
  91.     CHECK_MPI_OK( mp_mod(&d, &psub1, &tmp) );
  92.     MPINT_TO_SECITEM(&tmp, &key->exponent1, key->arena);
  93.     /* 5.  Compute exponent2 = d mod (q-1) */
  94.     CHECK_MPI_OK( mp_mod(&d, &qsub1, &tmp) );
  95.     MPINT_TO_SECITEM(&tmp, &key->exponent2, key->arena);
  96.     /* 6.  Compute coefficient = q**-1 mod p */
  97.     CHECK_MPI_OK( mp_invmod(q, p, &tmp) );
  98.     MPINT_TO_SECITEM(&tmp, &key->coefficient, key->arena);
  99. cleanup:
  100.     mp_clear(&n);
  101.     mp_clear(&d);
  102.     mp_clear(&phi);
  103.     mp_clear(&psub1);
  104.     mp_clear(&qsub1);
  105.     mp_clear(&tmp);
  106.     if (err) {
  107. MP_TO_SEC_ERROR(err);
  108. rv = SECFailure;
  109.     }
  110.     return rv;
  111. }
  113. /*
  114. ** Generate and return a new RSA public and private key.
  115. ** Both keys are encoded in a single RSAPrivateKey structure.
  116. ** "cx" is the random number generator context
  117. ** "keySizeInBits" is the size of the key to be generated, in bits.
  118. **    512, 1024, etc.
  119. ** "publicExponent" when not NULL is a pointer to some data that
  120. **    represents the public exponent to use. The data is a byte
  121. **    encoded integer, in "big endian" order.
  122. */
  123. RSAPrivateKey *
  124. RSA_NewKey(int keySizeInBits, SECItem *publicExponent)
  125. {
  126.     unsigned char *pb = NULL, *qb = NULL;
  127.     unsigned int primeLen;
  128.     unsigned long counter;
  129.     mp_int p, q, e;
  130.     mp_err   err = MP_OKAY;
  131.     SECStatus rv = SECSuccess;
  132.     int prerr = 0;
  133.     RSAPrivateKey *key = NULL;
  134.     PRArenaPool *arena = NULL;
  135.     /* Require key size to be a multiple of 16 bits. */
  136.     if (!publicExponent || keySizeInBits % 16 != 0) {
  137. PORT_SetError(SEC_ERROR_INVALID_ARGS);
  138. return NULL;
  139.     }
  140.     /* length of primes p and q (in bytes) */
  141.     primeLen = keySizeInBits / (2 * BITS_PER_BYTE);
  142.     MP_DIGITS(&p) = 0;
  143.     MP_DIGITS(&q) = 0;
  144.     MP_DIGITS(&e) = 0;
  145.     CHECK_MPI_OK( mp_init(&p) );
  146.     CHECK_MPI_OK( mp_init(&q) );
  147.     CHECK_MPI_OK( mp_init(&e) );
  148.     /* 1. Allocate arena & key */
  149.     arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
  150.     if (!arena) {
  151. PORT_SetError(SEC_ERROR_NO_MEMORY);
  152. return NULL;
  153.     }
  154.     key = (RSAPrivateKey *)PORT_ArenaZAlloc(arena, sizeof(RSAPrivateKey));
  155.     if (!key) {
  156. PORT_SetError(SEC_ERROR_NO_MEMORY);
  157. PORT_FreeArena(arena, PR_TRUE);
  158. return NULL;
  159.     }
  160.     key->arena = arena;
  161.     /* 2.  Set the version number (PKCS1 v1.5 says it should be zero) */
  162.     SECITEM_AllocItem(arena, &key->version, 1);
  163.     key->version.data[0] = 0;
  164.     /* 3.  Set the public exponent */
  165.     SECITEM_CopyItem(arena, &key->publicExponent, publicExponent);
  166.     SECITEM_TO_MPINT(*publicExponent, &e);
  167.     /* 4.  Generate primes p and q */
  168.     pb = PORT_Alloc(primeLen);
  169.     qb = PORT_Alloc(primeLen);
  170.     do {
  171. CHECK_SEC_OK( RNG_GenerateGlobalRandomBytes(pb, primeLen) );
  172. CHECK_SEC_OK( RNG_GenerateGlobalRandomBytes(qb, primeLen) );
  173. pb[0]          |= 0x80; /* set high-order bit */
  174. pb[primeLen-1] |= 0x01; /* set low-order bit  */
  175. qb[0]          |= 0x80; /* set high-order bit */
  176. qb[primeLen-1] |= 0x01; /* set low-order bit  */
  177. CHECK_MPI_OK( mp_read_unsigned_octets(&p, pb, primeLen) );
  178. CHECK_MPI_OK( mp_read_unsigned_octets(&q, qb, primeLen) );
  179. CHECK_MPI_OK( mpp_make_prime(&p, primeLen * 8, PR_FALSE, &counter) );
  180. CHECK_MPI_OK( mpp_make_prime(&q, primeLen * 8, PR_FALSE, &counter) );
  181. rv = rsa_keygen_from_primes(&p, &q, &e, key);
  182. if (rv == SECSuccess)
  183.     break; /* generated two good primes */
  184. prerr = PORT_GetError();
  185.     } while (prerr == SEC_ERROR_NEED_RANDOM); /* loop until have primes */
  186.     MPINT_TO_SECITEM(&p, &key->prime1, arena);
  187.     MPINT_TO_SECITEM(&q, &key->prime2, arena);
  188. cleanup:
  189.     mp_clear(&p);
  190.     mp_clear(&q);
  191.     mp_clear(&e);
  192.     if (pb)
  193. PORT_ZFree(pb, primeLen);
  194.     if (qb)
  195. PORT_ZFree(qb, primeLen);
  196.     if (err) {
  197. MP_TO_SEC_ERROR(err);
  198. rv = SECFailure;
  199.     }
  200.     if (rv && arena) {
  201. PORT_FreeArena(arena, PR_TRUE);
  202.     }
  203.     return key;
  204. }
  206. static unsigned int
  207. rsa_modulusLen(SECItem *modulus)
  208. {
  209.     unsigned char byteZero = modulus->data[0];
  210.     unsigned int modLen = modulus->len - !byteZero;
  211.     return modLen;
  212. }
  214. /*
  215. ** Perform a raw public-key operation 
  216. ** Length of input and output buffers are equal to key's modulus len.
  217. */
  218. SECStatus 
  219. RSA_PublicKeyOp(RSAPublicKey  *key, 
  220.                 unsigned char *output, 
  221.                 unsigned char *input)
  222. {
  223.     unsigned int modLen;
  224.     mp_int n, e, m, c;
  225.     mp_err err   = MP_OKAY;
  226.     SECStatus rv = SECSuccess;
  227.     if (!key || !output || !input) {
  228. PORT_SetError(SEC_ERROR_INVALID_ARGS);
  229. return SECFailure;
  230.     }
  231.     MP_DIGITS(&n) = 0;
  232.     MP_DIGITS(&e) = 0;
  233.     MP_DIGITS(&m) = 0;
  234.     MP_DIGITS(&c) = 0;
  235.     CHECK_MPI_OK( mp_init(&n) );
  236.     CHECK_MPI_OK( mp_init(&e) );
  237.     CHECK_MPI_OK( mp_init(&m) );
  238.     CHECK_MPI_OK( mp_init(&c) );
  239.     modLen = rsa_modulusLen(&key->modulus);
  240.     /* 1.  Obtain public key (n, e) */
  241.     SECITEM_TO_MPINT(key->modulus, &n);
  242.     SECITEM_TO_MPINT(key->publicExponent, &e);
  243.     /* 2.  Represent message as integer in range [0..n-1] */
  244.     CHECK_MPI_OK( mp_read_unsigned_octets(&m, input, modLen) );
  245.     /* 3.  Compute c = m**e mod n */
  246. #ifdef USE_MPI_EXPT_D
  247.     /* XXX see which is faster */
  248.     if (MP_USED(&e) == 1) {
  249. CHECK_MPI_OK( mp_exptmod_d(&m, MP_DIGIT(&e, 0), &n, &c) );
  250.     } else
  251. #endif
  252.     CHECK_MPI_OK( mp_exptmod(&m, &e, &n, &c) );
  253.     /* 4.  result c is ciphertext */
  254.     err = mp_to_fixlen_octets(&c, output, modLen);
  255.     if (err >= 0) err = MP_OKAY;
  256. cleanup:
  257.     mp_clear(&n);
  258.     mp_clear(&e);
  259.     mp_clear(&m);
  260.     mp_clear(&c);
  261.     if (err) {
  262. MP_TO_SEC_ERROR(err);
  263. rv = SECFailure;
  264.     }
  265.     return rv;
  266. }
  268. /*
  269. **  RSA Private key operation (no CRT).
  270. */
  271. static SECStatus 
  272. rsa_PrivateKeyOp(RSAPrivateKey *key, 
  273.                  unsigned char *output, 
  274.                  unsigned char *input)
  275. {
  276.     mp_int n, d, m, c;
  277.     mp_err   err = MP_OKAY;
  278.     SECStatus rv = SECSuccess;
  279.     unsigned int modLen;
  280.     modLen = rsa_modulusLen(&key->modulus);
  281.     MP_DIGITS(&n) = 0;
  282.     MP_DIGITS(&d) = 0;
  283.     MP_DIGITS(&m) = 0;
  284.     MP_DIGITS(&c) = 0;
  285.     CHECK_MPI_OK( mp_init(&n) );
  286.     CHECK_MPI_OK( mp_init(&d) );
  287.     CHECK_MPI_OK( mp_init(&m) );
  288.     CHECK_MPI_OK( mp_init(&c) );
  289.     /* copy private key parameters into mp integers */
  290.     SECITEM_TO_MPINT(key->modulus,         &n); /* n */
  291.     SECITEM_TO_MPINT(key->privateExponent, &d); /* d */
  292.     /* copy input into mp integer c */
  293.     OCTETS_TO_MPINT(input, &c, modLen);
  294.     /* 1. m = c**d mod n */
  295.     CHECK_MPI_OK( mp_exptmod(&c, &d, &n, &m) );
  296.     /* m is the output */
  297.     err = mp_to_fixlen_octets(&m, output, modLen);
  298.     if (err >= 0) err = MP_OKAY;
  299. cleanup:
  300.     mp_clear(&n);
  301.     mp_clear(&d);
  302.     mp_clear(&m);
  303.     mp_clear(&c);
  304.     if (err) {
  305. MP_TO_SEC_ERROR(err);
  306. rv = SECFailure;
  307.     }
  308.     return rv;
  309. }
  311. /*
  312. **  RSA Private key operation using CRT.
  313. */
  314. static SECStatus 
  315. rsa_PrivateKeyOpCRT(RSAPrivateKey *key, 
  316.                     unsigned char *output, 
  317.                     unsigned char *input)
  318. {
  319.     mp_int p, q, d_p, d_q, qInv;
  320.     mp_int m, m1, m2, b2, h, c, ctmp;
  321.     mp_err   err = MP_OKAY;
  322.     SECStatus rv = SECSuccess;
  323.     unsigned int modLen;
  324.     modLen = rsa_modulusLen(&key->modulus);
  325.     MP_DIGITS(&p)    = 0;
  326.     MP_DIGITS(&q)    = 0;
  327.     MP_DIGITS(&d_p)  = 0;
  328.     MP_DIGITS(&d_q)  = 0;
  329.     MP_DIGITS(&qInv) = 0;
  330.     MP_DIGITS(&m)    = 0;
  331.     MP_DIGITS(&m1)   = 0;
  332.     MP_DIGITS(&m2)   = 0;
  333.     MP_DIGITS(&b2)   = 0;
  334.     MP_DIGITS(&h)    = 0;
  335.     MP_DIGITS(&c)    = 0;
  336.     MP_DIGITS(&ctmp) = 0;
  337.     CHECK_MPI_OK( mp_init(&p)    );
  338.     CHECK_MPI_OK( mp_init(&q)    );
  339.     CHECK_MPI_OK( mp_init(&d_p)  );
  340.     CHECK_MPI_OK( mp_init(&d_q)  );
  341.     CHECK_MPI_OK( mp_init(&qInv) );
  342.     CHECK_MPI_OK( mp_init(&m)    );
  343.     CHECK_MPI_OK( mp_init(&m1)   );
  344.     CHECK_MPI_OK( mp_init(&m2)   );
  345.     CHECK_MPI_OK( mp_init(&b2)   );
  346.     CHECK_MPI_OK( mp_init(&h)    );
  347.     CHECK_MPI_OK( mp_init(&c)    );
  348.     CHECK_MPI_OK( mp_init(&ctmp) );
  349.     /* copy private key parameters into mp integers */
  350.     SECITEM_TO_MPINT(key->prime1,      &p);    /* p */
  351.     SECITEM_TO_MPINT(key->prime2,      &q);    /* q */
  352.     SECITEM_TO_MPINT(key->exponent1,   &d_p);  /* d_p  = d mod (p-1) */
  353.     SECITEM_TO_MPINT(key->exponent2,   &d_q);  /* d_p  = d mod (q-1) */
  354.     SECITEM_TO_MPINT(key->coefficient, &qInv); /* qInv = q**-1 mod p */
  355.     /* copy input into mp integer c */
  356.     OCTETS_TO_MPINT(input, &c, modLen);
  357.     /* 1. m1 = c**d_p mod p */
  358.     CHECK_MPI_OK( mp_mod(&c, &p, &ctmp) );
  359.     CHECK_MPI_OK( mp_exptmod(&ctmp, &d_p, &p, &m1) );
  360.     /* 2. m2 = c**d_q mod q */
  361.     CHECK_MPI_OK( mp_mod(&c, &q, &ctmp) );
  362.     CHECK_MPI_OK( mp_exptmod(&ctmp, &d_q, &q, &m2) );
  363.     /* 3.  h = (m1 - m2) * qInv mod p */
  364.     CHECK_MPI_OK( mp_submod(&m1, &m2, &p, &h) );
  365.     CHECK_MPI_OK( mp_mulmod(&h, &qInv, &p, &h)  );
  366.     /* 4.  m = m2 + h * q */
  367.     CHECK_MPI_OK( mp_mul(&h, &q, &m) );
  368.     CHECK_MPI_OK( mp_add(&m, &m2, &m) );
  369.     /* m is the output */
  370.     err = mp_to_fixlen_octets(&m, output, modLen);
  371.     if (err >= 0) err = MP_OKAY;
  372. cleanup:
  373.     mp_clear(&p);
  374.     mp_clear(&q);
  375.     mp_clear(&d_p);
  376.     mp_clear(&d_q);
  377.     mp_clear(&qInv);
  378.     mp_clear(&m);
  379.     mp_clear(&m1);
  380.     mp_clear(&m2);
  381.     mp_clear(&b2);
  382.     mp_clear(&h);
  383.     mp_clear(&c);
  384.     if (err) {
  385. MP_TO_SEC_ERROR(err);
  386. rv = SECFailure;
  387.     }
  388.     return rv;
  389. }
  391. /*
  392. ** Perform a raw private-key operation 
  393. ** Length of input and output buffers are equal to key's modulus len.
  394. */
  395. SECStatus 
  396. RSA_PrivateKeyOp(RSAPrivateKey *key, 
  397.                  unsigned char *output, 
  398.                  unsigned char *input)
  399. {
  400.     unsigned int modLen;
  401.     unsigned int offset;
  402.     if (!key || !output || !input) {
  403. PORT_SetError(SEC_ERROR_INVALID_ARGS);
  404. return SECFailure;
  405.     }
  406.     /* check input out of range (needs to be in range [0..n-1]) */
  407.     modLen = rsa_modulusLen(&key->modulus);
  408.     offset = (key->modulus.data[0] == 0) ? 1 : 0; /* may be leading 0 */
  409.     if (memcmp(input, key->modulus.data + offset, modLen) >= 0) {
  410. PORT_SetError(SEC_ERROR_INVALID_ARGS);
  411. return SECFailure;
  412.     }
  413.     if ( key->prime1.len      == 0 ||
  414.          key->prime2.len      == 0 ||
  415.          key->exponent1.len   == 0 ||
  416.          key->exponent2.len   == 0 ||
  417.          key->coefficient.len == 0) {
  418. return rsa_PrivateKeyOp(key, output, input);
  419.     } else {
  420. return rsa_PrivateKeyOpCRT(key, output, input);
  421.     }
  422. }