ecc.c

这是由Rinick编写的加解密函数库。最近找了不少关于加解密的C源码

/* LibTomCrypt, modular cryptographic library -- Tom St Denis
 *
 * LibTomCrypt is a library that provides various cryptographic
 * algorithms in a highly modular and flexible manner.
 *
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, [e-mail], http://libtomcrypt.org
 */

/* Implements ECC over Z/pZ for curve y^2 = x^3 - 3x + b
 *
 * All curves taken from NIST recommendation paper of July 1999
 * Available at http://csrc.nist.gov/cryptval/dss.htm
 */
#include "tomcrypt.h"

/**
  @file ecc.c
  ECC Crypto, Tom St Denis
*/  

#ifdef MECC

/* size of our temp buffers for exported keys */
#define ECC_BUF_SIZE 256

/* max private key size */
#define ECC_MAXSIZE  66

/* This holds the key settings.  ***MUST*** be organized by size from smallest to largest. */
const ltc_ecc_set_type ecc_sets[]  = {
#ifdef ECC192
{
    24,
   "ECC-192",
   /* prime */
   "/////////////////////l//////////",

   /* B */
   "P2456UMSWESFf+chSYGmIVwutkp1Hhcn",

   /* order */
   "////////////////cTxuDXHhoR6qqYWn",

   /* Gx */
   "68se3h0maFPylo3hGw680FJ/2ls2/n0I",

   /* Gy */
   "1nahbV/8sdXZ417jQoJDrNFvTw4UUKWH"
},
#endif
#ifdef ECC224
{
   28,
   "ECC-224",

   /* prime */
   "3/////////////////////0000000000000001",

   /* B */
   "2q1Gg530Ipg/L1CbPGHB2trx/OkYSBEKCZLV+q",

   /* order */
   "3//////////////////nQYuBZmFXFTAKLSN2ez",

   /* Gx */
   "2t3WozQxI/Vp8JaBbA0y7JLi8H8ZGoWDOHN1qX",


   /* Gy */
   "2zDsE8jVSZ+qmYt+RDGtMWMWT7P4JLWPc507uq",
},
#endif
#ifdef ECC256
{
   32,
   "ECC-256",
   /* Prime */
   "F////y000010000000000000000////////////////",

   /* B */
   "5h6DTYgEfFdi+kzLNQOXhnb7GQmp5EmzZlEF3udqc1B",

   /* Order */
   "F////y00000//////////+yvlgjfnUUXFEvoiByOoLH",

   /* Gx */
   "6iNqVBXB497+BpcvMEaGF9t0ts1BUipeFIXEKNOcCAM",

   /* Gy */
   "4/ZGkB+6d+RZkVhIdmFdXOhpZDNQp5UpiksG6Wtlr7r"
},
#endif
#ifdef ECC384
{
   48,
   "ECC-384",
   /* prime */
   "//////////////////////////////////////////x/////00000000003/"
   "////",

   /* B */
   "ip4lf+8+v+IOZWLhu/Wj6HWTd6x+WK4I0nG8Zr0JXrh6LZcDYYxHdIg5oEtJ"
   "x2hl",

   /* Order */
   "////////////////////////////////nsDDWVGtBTzO6WsoIB2dUkpi6MhC"
   "nIbp",

   /* Gx and Gy */
   "geVA8hwB1JUEiSSUyo2jT6uTEsABfvkOMVT1u89KAZXL0l9TlrKfR3fKNZXo"
   "TWgt",

   "DXVUIfOcB6zTdfY/afBSAVZq7RqecXHywTen4xNmkC0AOB7E7Nw1dNf37NoG"
   "wWvV"
},
#endif
#ifdef ECC521
{
   65,
   "ECC-521",
   /* prime */
   "V///////////////////////////////////////////////////////////"
   "///////////////////////////",

   /* B */
   "56LFhbXZXoQ7vAQ8Q2sXK3kejfoMvcp5VEuj8cHZl49uLOPEL7iVfDx5bB0l"
   "JknlmSrSz+8FImqyUz57zHhK3y0",

   /* Order */
   "V//////////////////////////////////////////+b66XuE/BvPhVym1I"
   "FS9fT0xjScuYPn7hhjljnwHE6G9",

   /* Gx and Gy */
   "CQ5ZWQt10JfpPu+osOZbRH2d6I1EGK/jI7uAAzWQqqzkg5BNdVlvrae/Xt19"
   "wB/gDupIBF1XMf2c/b+VZ72vRrc",

   "HWvAMfucZl015oANxGiVHlPcFL4ILURH6WNhxqN9pvcB9VkSfbUz2P0nL2v0"
   "J+j1s4rF726edB2G8Y+b7QVqMPG",
},
#endif
{
   0,
   NULL, NULL, NULL, NULL, NULL, NULL
}
};

int is_valid_idx(int n)
{
   int x;

   for (x = 0; ecc_sets[x].size != 0; x++);
   if ((n < 0) || (n >= x)) {
      return 0;
   }
   return 1;
}

ecc_point *ecc_new_point(void)
{
   ecc_point *p;
   p = XMALLOC(sizeof(ecc_point));
   if (p == NULL) {
      return NULL;
   }
   if (mp_init_multi(&p->x, &p->y, &p->z, NULL) != MP_OKAY) {
      XFREE(p);
      return NULL;
   }
   return p;
}

void ecc_del(ecc_point *p)
{
   /* prevents free'ing null arguments */
   if (p != NULL) {
      mp_clear_multi(&p->x, &p->y, &p->z, NULL);
      XFREE(p);
   }
}

int ecc_map(ecc_point *P, mp_int *modulus, mp_digit mp)
{
   mp_int t1, t2;
   int err;

   if ((err = mp_init_multi(&t1, &t2, NULL)) != CRYPT_OK) {
      return CRYPT_MEM;
   }

   /* first map z back to normal */
   if ((err = mp_montgomery_reduce(&P->z, modulus, mp)) != MP_OKAY)           { goto error; }

   /* get 1/z */
   if ((err = mp_invmod(&P->z, modulus, &t1)) != MP_OKAY)                     { goto error; }
 
   /* get 1/z^2 and 1/z^3 */
   if ((err = mp_sqr(&t1, &t2)) != MP_OKAY)                                   { goto error; }
   if ((err = mp_mod(&t2, modulus, &t2)) != MP_OKAY)                          { goto error; }
   if ((err = mp_mul(&t1, &t2, &t1)) != MP_OKAY)                              { goto error; }
   if ((err = mp_mod(&t1, modulus, &t1)) != MP_OKAY)                          { goto error; }

   /* multiply against x/y */
   if ((err = mp_mul(&P->x, &t2, &P->x)) != MP_OKAY)                          { goto error; }
   if ((err = mp_montgomery_reduce(&P->x, modulus, mp)) != MP_OKAY)           { goto error; }
   if ((err = mp_mul(&P->y, &t1, &P->y)) != MP_OKAY)                          { goto error; }
   if ((err = mp_montgomery_reduce(&P->y, modulus, mp)) != MP_OKAY)           { goto error; }
   mp_set(&P->z, 1);

   err = CRYPT_OK;
   goto done;
error:
   err = mpi_to_ltc_error(err);
done:
   mp_clear_multi(&t1, &t2, NULL);
   return err;

}

/* double a point R = 2P, R can be P*/
int ecc_dbl(ecc_point *P, ecc_point *R, mp_int *modulus, mp_digit mp)
{
   mp_int t1, t2;
   int err;

   if ((err = mp_init_multi(&t1, &t2, NULL)) != MP_OKAY) {
      return mpi_to_ltc_error(err);
   }

   if ((err = mp_copy(&P->x, &R->x)) != MP_OKAY)                                   { goto error; }
   if ((err = mp_copy(&P->y, &R->y)) != MP_OKAY)                                   { goto error; }
   if ((err = mp_copy(&P->z, &R->z)) != MP_OKAY)                                   { goto error; }

   /* t1 = Z * Z */
   if ((err = mp_sqr(&R->z, &t1)) != MP_OKAY)                                      { goto error; }
   if ((err = mp_montgomery_reduce(&t1, modulus, mp)) != MP_OKAY)                  { goto error; }
   /* Z = Y * Z */
   if ((err = mp_mul(&R->z, &R->y, &R->z)) != MP_OKAY)                             { goto error; }
   if ((err = mp_montgomery_reduce(&R->z, modulus, mp)) != MP_OKAY)                { goto error; }
   /* Z = 2Z */
   if ((err = mp_mul_2(&R->z, &R->z)) != MP_OKAY)                                  { goto error; }
   if (mp_cmp(&R->z, modulus) != MP_LT) {
      if ((err = mp_sub(&R->z, modulus, &R->z)) != MP_OKAY)                        { goto error; }
   }

   /* T2 = X - T1 */
   if ((err = mp_sub(&R->x, &t1, &t2)) != MP_OKAY)                                 { goto error; }
   if (mp_cmp_d(&t2, 0) == MP_LT) {
      if ((err = mp_add(&t2, modulus, &t2)) != MP_OKAY)                            { goto error; }
   }
   /* T1 = X + T1 */
   if ((err = mp_add(&t1, &R->x, &t1)) != MP_OKAY)                                 { goto error; }
   if (mp_cmp(&t1, modulus) != MP_LT) {
      if ((err = mp_sub(&t1, modulus, &t1)) != MP_OKAY)                            { goto error; }
   }
   /* T2 = T1 * T2 */
   if ((err = mp_mul(&t1, &t2, &t2)) != MP_OKAY)                                   { goto error; }
   if ((err = mp_montgomery_reduce(&t2, modulus, mp)) != MP_OKAY)                  { goto error; }
   /* T1 = 2T2 */
   if ((err = mp_mul_2(&t2, &t1)) != MP_OKAY)                                      { goto error; }
   if (mp_cmp(&t1, modulus) != MP_LT) {
      if ((err = mp_sub(&t1, modulus, &t1)) != MP_OKAY)                            { goto error; }
   }
   /* T1 = T1 + T2 */
   if ((err = mp_add(&t1, &t2, &t1)) != MP_OKAY)                                   { goto error; }
   if (mp_cmp(&t1, modulus) != MP_LT) {
      if ((err = mp_sub(&t1, modulus, &t1)) != MP_OKAY)                            { goto error; }
   }

   /* Y = 2Y */
   if ((err = mp_mul_2(&R->y, &R->y)) != MP_OKAY)                                  { goto error; }
   if (mp_cmp(&R->y, modulus) != MP_LT) {
      if ((err = mp_sub(&R->y, modulus, &R->y)) != MP_OKAY)                        { goto error; }
   }
   /* Y = Y * Y */
   if ((err = mp_sqr(&R->y, &R->y)) != MP_OKAY)                                    { goto error; }
   if ((err = mp_montgomery_reduce(&R->y, modulus, mp)) != MP_OKAY)                { goto error; }
   /* T2 = Y * Y */
   if ((err = mp_sqr(&R->y, &t2)) != MP_OKAY)                                      { goto error; }
   if ((err = mp_montgomery_reduce(&t2, modulus, mp)) != MP_OKAY)                  { goto error; }
   /* T2 = T2/2 */
   if (mp_isodd(&t2)) {
      if ((err = mp_add(&t2, modulus, &t2)) != MP_OKAY)                            { goto error; }
   }
   if ((err = mp_div_2(&t2, &t2)) != MP_OKAY)                                      { goto error; }
   /* Y = Y * X */
   if ((err = mp_mul(&R->y, &R->x, &R->y)) != MP_OKAY)                             { goto error; }
   if ((err = mp_montgomery_reduce(&R->y, modulus, mp)) != MP_OKAY)                { goto error; }

   /* X  = T1 * T1 */
   if ((err = mp_sqr(&t1, &R->x)) != MP_OKAY)                                      { goto error; }
   if ((err = mp_montgomery_reduce(&R->x, modulus, mp)) != MP_OKAY)                { goto error; }
   /* X = X - Y */
   if ((err = mp_sub(&R->x, &R->y, &R->x)) != MP_OKAY)                             { goto error; }
   if (mp_cmp_d(&R->x, 0) == MP_LT) {
      if ((err = mp_add(&R->x, modulus, &R->x)) != MP_OKAY)                        { goto error; }
   }
   /* X = X - Y */
   if ((err = mp_sub(&R->x, &R->y, &R->x)) != MP_OKAY)                             { goto error; }
   if (mp_cmp_d(&R->x, 0) == MP_LT) {
      if ((err = mp_add(&R->x, modulus, &R->x)) != MP_OKAY)                        { goto error; }
   }

   /* Y = Y - X */     
   if ((err = mp_sub(&R->y, &R->x, &R->y)) != MP_OKAY)                             { goto error; }
   if (mp_cmp_d(&R->y, 0) == MP_LT) {
      if ((err = mp_add(&R->y, modulus, &R->y)) != MP_OKAY)                        { goto error; }
   }
   /* Y = Y * T1 */
   if ((err = mp_mul(&R->y, &t1, &R->y)) != MP_OKAY)                               { goto error; }
   if ((err = mp_montgomery_reduce(&R->y, modulus, mp)) != MP_OKAY)                { goto error; }
   /* Y = Y - T2 */
   if ((err = mp_sub(&R->y, &t2, &R->y)) != MP_OKAY)                               { goto error; }
   if (mp_cmp_d(&R->y, 0) == MP_LT) {
      if ((err = mp_add(&R->y, modulus, &R->y)) != MP_OKAY)                        { goto error; }
   }
 
   err = CRYPT_OK;
   goto done;
error:
   err = mpi_to_ltc_error(err);
done:
   mp_clear_multi(&t1, &t2, NULL);
   return err;
}

/* add two different points over Z/pZ, R = P + Q, note R can equal either P or Q */
int ecc_add(ecc_point *P, ecc_point *Q, ecc_point *R, mp_int *modulus, mp_digit mp)
{
   mp_int t1, t2, x, y, z;
   int err;

   if ((err = mp_init_multi(&t1, &t2, &x, &y, &z, NULL)) != MP_OKAY) {
      return mpi_to_ltc_error(err);
   }

   if ((err = mp_copy(&P->x, &x)) != MP_OKAY)                                   { goto error; }
   if ((err = mp_copy(&P->y, &y)) != MP_OKAY)                                   { goto error; }
   if ((err = mp_copy(&P->z, &z)) != MP_OKAY)                                   { goto error; }

      /* T1 = Z' * Z' */
      if ((err = mp_sqr(&Q->z, &t1)) != MP_OKAY)                                { goto error; }
      if ((err = mp_montgomery_reduce(&t1, modulus, mp)) != MP_OKAY)            { goto error; }
      /* X = X * T1 */
      if ((err = mp_mul(&t1, &x, &x)) != MP_OKAY)                               { goto error; }
      if ((err = mp_montgomery_reduce(&x, modulus, mp)) != MP_OKAY)             { goto error; }
      /* T1 = Z' * T1 */
      if ((err = mp_mul(&Q->z, &t1, &t1)) != MP_OKAY)                           { goto error; }
      if ((err = mp_montgomery_reduce(&t1, modulus, mp)) != MP_OKAY)            { goto error; }
      /* Y = Y * T1 */
      if ((err = mp_mul(&t1, &y, &y)) != MP_OKAY)                               { goto error; }
      if ((err = mp_montgomery_reduce(&y, modulus, mp)) != MP_OKAY)             { goto error; }

   /* T1 = Z*Z */
   if ((err = mp_sqr(&z, &t1)) != MP_OKAY)                                      { goto error; }
   if ((err = mp_montgomery_reduce(&t1, modulus, mp)) != MP_OKAY)               { goto error; }
   /* T2 = X' * T1 */
   if ((err = mp_mul(&Q->x, &t1, &t2)) != MP_OKAY)                              { goto error; }
   if ((err = mp_montgomery_reduce(&t2, modulus, mp)) != MP_OKAY)               { goto error; }
   /* T1 = Z * T1 */
   if ((err = mp_mul(&z, &t1, &t1)) != MP_OKAY)                                 { goto error; }
   if ((err = mp_montgomery_reduce(&t1, modulus, mp)) != MP_OKAY)               { goto error; }
   /* T1 = Y' * T1 */
   if ((err = mp_mul(&Q->y, &t1, &t1)) != MP_OKAY)                              { goto error; }
   if ((err = mp_montgomery_reduce(&t1, modulus, mp)) != MP_OKAY)               { goto error; }