1/* LibTomCrypt, modular cryptographic library -- Tom St Denis
2 *
3 * LibTomCrypt is a library that provides various cryptographic
4 * algorithms in a highly modular and flexible manner.
5 *
6 * The library is free for all purposes without any express
7 * guarantee it works.
8 *
9 * Tom St Denis, tomstdenis@gmail.com, http://libtomcrypt.com
10 */
11
12/* Implements ECC over Z/pZ for curve y^2 = x^3 - 3x + b
13 *
14 * All curves taken from NIST recommendation paper of July 1999
15 * Available at http://csrc.nist.gov/cryptval/dss.htm
16 */
17#include "tomcrypt.h"
18
19/**
20  @file ecc_import.c
21  ECC Crypto, Tom St Denis
22*/
23
24#ifdef MECC
25
26static int is_point(ecc_key *key)
27{
28   void *prime, *b, *t1, *t2;
29   int err;
30
31   if ((err = mp_init_multi(&prime, &b, &t1, &t2, NULL)) != CRYPT_OK) {
32      return err;
33   }
34
35   /* load prime and b */
36   if ((err = mp_read_radix(prime, key->dp->prime, 16)) != CRYPT_OK)                          { goto error; }
37   if ((err = mp_read_radix(b, key->dp->B, 16)) != CRYPT_OK)                                  { goto error; }
38
39   /* compute y^2 */
40   if ((err = mp_sqr(key->pubkey.y, t1)) != CRYPT_OK)                                         { goto error; }
41
42   /* compute x^3 */
43   if ((err = mp_sqr(key->pubkey.x, t2)) != CRYPT_OK)                                         { goto error; }
44   if ((err = mp_mod(t2, prime, t2)) != CRYPT_OK)                                             { goto error; }
45   if ((err = mp_mul(key->pubkey.x, t2, t2)) != CRYPT_OK)                                     { goto error; }
46
47   /* compute y^2 - x^3 */
48   if ((err = mp_sub(t1, t2, t1)) != CRYPT_OK)                                                { goto error; }
49
50   /* compute y^2 - x^3 + 3x */
51   if ((err = mp_add(t1, key->pubkey.x, t1)) != CRYPT_OK)                                     { goto error; }
52   if ((err = mp_add(t1, key->pubkey.x, t1)) != CRYPT_OK)                                     { goto error; }
53   if ((err = mp_add(t1, key->pubkey.x, t1)) != CRYPT_OK)                                     { goto error; }
54   if ((err = mp_mod(t1, prime, t1)) != CRYPT_OK)                                             { goto error; }
55   while (mp_cmp_d(t1, 0) == LTC_MP_LT) {
56      if ((err = mp_add(t1, prime, t1)) != CRYPT_OK)                                          { goto error; }
57   }
58   while (mp_cmp(t1, prime) != LTC_MP_LT) {
59      if ((err = mp_sub(t1, prime, t1)) != CRYPT_OK)                                          { goto error; }
60   }
61
62   /* compare to b */
63   if (mp_cmp(t1, b) != LTC_MP_EQ) {
64      err = CRYPT_INVALID_PACKET;
65   } else {
66      err = CRYPT_OK;
67   }
68
69error:
70   mp_clear_multi(prime, b, t1, t2, NULL);
71   return err;
72}
73
74/**
75  Import an ECC key from a binary packet
76  @param in      The packet to import
77  @param inlen   The length of the packet
78  @param key     [out] The destination of the import
79  @return CRYPT_OK if successful, upon error all allocated memory will be freed
80*/
81int ecc_import(const unsigned char *in, unsigned long inlen, ecc_key *key)
82{
83   return ecc_import_ex(in, inlen, key, NULL);
84}
85
86/**
87  Import an ECC key from a binary packet, using user supplied domain params rather than one of the NIST ones
88  @param in      The packet to import
89  @param inlen   The length of the packet
90  @param key     [out] The destination of the import
91  @param dp      pointer to user supplied params; must be the same as the params used when exporting
92  @return CRYPT_OK if successful, upon error all allocated memory will be freed
93*/
94int ecc_import_ex(const unsigned char *in, unsigned long inlen, ecc_key *key, const ltc_ecc_set_type *dp)
95{
96   unsigned long key_size;
97   unsigned char flags[1];
98   int           err;
99
100   LTC_ARGCHK(in  != NULL);
101   LTC_ARGCHK(key != NULL);
102   LTC_ARGCHK(ltc_mp.name != NULL);
103
104   /* init key */
105   if (mp_init_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z, &key->k, NULL) != CRYPT_OK) {
106      return CRYPT_MEM;
107   }
108
109   /* find out what type of key it is */
110   if ((err = der_decode_sequence_multi(in, inlen,
111                                  LTC_ASN1_BIT_STRING, 1UL, &flags,
112                                  LTC_ASN1_EOL,        0UL, NULL)) != CRYPT_OK) {
113      goto done;
114   }
115
116
117   if (flags[0] == 1) {
118      /* private key */
119      key->type = PK_PRIVATE;
120      if ((err = der_decode_sequence_multi(in, inlen,
121                                     LTC_ASN1_BIT_STRING,      1UL, flags,
122                                     LTC_ASN1_SHORT_INTEGER,   1UL, &key_size,
123                                     LTC_ASN1_INTEGER,         1UL, key->pubkey.x,
124                                     LTC_ASN1_INTEGER,         1UL, key->pubkey.y,
125                                     LTC_ASN1_INTEGER,         1UL, key->k,
126                                     LTC_ASN1_EOL,             0UL, NULL)) != CRYPT_OK) {
127         goto done;
128      }
129   } else {
130      /* public key */
131      key->type = PK_PUBLIC;
132      if ((err = der_decode_sequence_multi(in, inlen,
133                                     LTC_ASN1_BIT_STRING,      1UL, flags,
134                                     LTC_ASN1_SHORT_INTEGER,   1UL, &key_size,
135                                     LTC_ASN1_INTEGER,         1UL, key->pubkey.x,
136                                     LTC_ASN1_INTEGER,         1UL, key->pubkey.y,
137                                     LTC_ASN1_EOL,             0UL, NULL)) != CRYPT_OK) {
138         goto done;
139      }
140   }
141
142   if (dp == NULL) {
143     /* find the idx */
144     for (key->idx = 0; ltc_ecc_sets[key->idx].size && (unsigned long)ltc_ecc_sets[key->idx].size != key_size; ++key->idx);
145     if (ltc_ecc_sets[key->idx].size == 0) {
146       err = CRYPT_INVALID_PACKET;
147       goto done;
148     }
149     key->dp = &ltc_ecc_sets[key->idx];
150   } else {
151     key->idx = -1;
152     key->dp = dp;
153   }
154   /* set z */
155   if ((err = mp_set(key->pubkey.z, 1)) != CRYPT_OK) { goto done; }
156
157   /* is it a point on the curve?  */
158   if ((err = is_point(key)) != CRYPT_OK) {
159      goto done;
160   }
161
162   /* we're good */
163   return CRYPT_OK;
164done:
165   mp_clear_multi(key->pubkey.x, key->pubkey.y, key->pubkey.z, key->k, NULL);
166   return err;
167}
168#endif
169/* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ecc_import.c,v $ */
170/* $Revision: 1.11 $ */
171/* $Date: 2006/12/04 02:19:48 $ */
172
173