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
is_point(ecc_key * key)26 static 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
69 error:
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 */
ecc_import(const unsigned char * in,unsigned long inlen,ecc_key * key)81 int 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 */
ecc_import_ex(const unsigned char * in,unsigned long inlen,ecc_key * key,const ltc_ecc_set_type * dp)94 int 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 = <c_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;
164 done:
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