Mercurial > dropbear

comparison dh_sys.c @ 3:7faae8f46238 libtomcrypt-orig

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Branch renaming
author Matt Johnston <matt@ucc.asn.au>
date Mon, 31 May 2004 18:25:41 +0000
parents
children 5d99163f7e32
comparison
equal deleted inserted replaced
-1:000000000000 3:7faae8f46238
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, [email protected], http://libtomcrypt.org
10 */
11 int dh_encrypt_key(const unsigned char *inkey, unsigned long keylen,
12 unsigned char *out, unsigned long *len,
13 prng_state *prng, int wprng, int hash,
14 dh_key *key)
15 {
16 unsigned char pub_expt[768], dh_shared[768], skey[MAXBLOCKSIZE];
17 dh_key pubkey;
18 unsigned long x, y, z, hashsize, pubkeysize;
19 int err;
20
21 _ARGCHK(inkey != NULL);
22 _ARGCHK(out != NULL);
23 _ARGCHK(len != NULL);
24 _ARGCHK(key != NULL);
25
26 /* check that wprng/hash are not invalid */
27 if ((err = prng_is_valid(wprng)) != CRYPT_OK) {
28 return err;
29 }
30
31 if ((err = hash_is_valid(hash)) != CRYPT_OK) {
32 return err;
33 }
34
35 if (keylen > hash_descriptor[hash].hashsize) {
36 return CRYPT_INVALID_HASH;
37 }
38
39 /* make a random key and export the public copy */
40 if ((err = dh_make_key(prng, wprng, dh_get_size(key), &pubkey)) != CRYPT_OK) {
41 return err;
42 }
43
44 pubkeysize = sizeof(pub_expt);
45 if ((err = dh_export(pub_expt, &pubkeysize, PK_PUBLIC, &pubkey)) != CRYPT_OK) {
46 dh_free(&pubkey);
47 return err;
48 }
49
50 /* now check if the out buffer is big enough */
51 if (*len < (1 + 4 + 4 + PACKET_SIZE + pubkeysize + keylen)) {
52 dh_free(&pubkey);
53 return CRYPT_BUFFER_OVERFLOW;
54 }
55
56 /* make random key */
57 hashsize = hash_descriptor[hash].hashsize;
58
59 x = (unsigned long)sizeof(dh_shared);
60 if ((err = dh_shared_secret(&pubkey, key, dh_shared, &x)) != CRYPT_OK) {
61 dh_free(&pubkey);
62 return err;
63 }
64 dh_free(&pubkey);
65
66 z = sizeof(skey);
67 if ((err = hash_memory(hash, dh_shared, x, skey, &z)) != CRYPT_OK) {
68 return err;
69 }
70
71 /* store header */
72 packet_store_header(out, PACKET_SECT_DH, PACKET_SUB_ENC_KEY);
73
74 /* output header */
75 y = PACKET_SIZE;
76
77 /* size of hash name and the name itself */
78 out[y++] = hash_descriptor[hash].ID;
79
80 /* length of DH pubkey and the key itself */
81 STORE32L(pubkeysize, out+y);
82 y += 4;
83 for (x = 0; x < pubkeysize; x++, y++) {
84 out[y] = pub_expt[x];
85 }
86
87 /* Store the encrypted key */
88 STORE32L(keylen, out+y);
89 y += 4;
90
91 for (x = 0; x < keylen; x++, y++) {
92 out[y] = skey[x] ^ inkey[x];
93 }
94 *len = y;
95
96 #ifdef CLEAN_STACK
97 /* clean up */
98 zeromem(pub_expt, sizeof(pub_expt));
99 zeromem(dh_shared, sizeof(dh_shared));
100 zeromem(skey, sizeof(skey));
101 #endif
102
103 return CRYPT_OK;
104 }
105
106 int dh_decrypt_key(const unsigned char *in, unsigned long inlen,
107 unsigned char *outkey, unsigned long *keylen,
108 dh_key *key)
109 {
110 unsigned char shared_secret[768], skey[MAXBLOCKSIZE];
111 unsigned long x, y, z,hashsize, keysize;
112 int hash, err;
113 dh_key pubkey;
114
115 _ARGCHK(in != NULL);
116 _ARGCHK(outkey != NULL);
117 _ARGCHK(keylen != NULL);
118 _ARGCHK(key != NULL);
119
120 /* right key type? */
121 if (key->type != PK_PRIVATE) {
122 return CRYPT_PK_NOT_PRIVATE;
123 }
124
125 /* check if initial header should fit */
126 if (inlen < PACKET_SIZE+1+4+4) {
127 return CRYPT_INVALID_PACKET;
128 } else {
129 inlen -= PACKET_SIZE+1+4+4;
130 }
131
132 /* is header correct? */
133 if ((err = packet_valid_header((unsigned char *)in, PACKET_SECT_DH, PACKET_SUB_ENC_KEY)) != CRYPT_OK) {
134 return err;
135 }
136
137 /* now lets get the hash name */
138 y = PACKET_SIZE;
139 hash = find_hash_id(in[y++]);
140 if (hash == -1) {
141 return CRYPT_INVALID_HASH;
142 }
143
144 /* common values */
145 hashsize = hash_descriptor[hash].hashsize;
146
147 /* get public key */
148 LOAD32L(x, in+y);
149
150 /* now check if the imported key will fit */
151 if (inlen < x) {
152 return CRYPT_INVALID_PACKET;
153 } else {
154 inlen -= x;
155 }
156
157 y += 4;
158 if ((err = dh_import(in+y, x, &pubkey)) != CRYPT_OK) {
159 return err;
160 }
161 y += x;
162
163 /* make shared key */
164 x = (unsigned long)sizeof(shared_secret);
165 if ((err = dh_shared_secret(key, &pubkey, shared_secret, &x)) != CRYPT_OK) {
166 dh_free(&pubkey);
167 return err;
168 }
169 dh_free(&pubkey);
170
171 z = sizeof(skey);
172 if ((err = hash_memory(hash, shared_secret, x, skey, &z)) != CRYPT_OK) {
173 return err;
174 }
175
176 /* load in the encrypted key */
177 LOAD32L(keysize, in+y);
178
179 /* will the outkey fit as part of the input */
180 if (inlen < keysize) {
181 return CRYPT_INVALID_PACKET;
182 } else {
183 inlen -= keysize;
184 }
185
186 if (keysize > *keylen) {
187 err = CRYPT_BUFFER_OVERFLOW;
188 goto done;
189 }
190 y += 4;
191
192 *keylen = keysize;
193
194 for (x = 0; x < keysize; x++, y++) {
195 outkey[x] = skey[x] ^ in[y];
196 }
197
198 err = CRYPT_OK;
199 done:
200 #ifdef CLEAN_STACK
201 zeromem(shared_secret, sizeof(shared_secret));
202 zeromem(skey, sizeof(skey));
203 #endif
204 return err;
205 }
206
207 /* perform an ElGamal Signature of a hash
208 *
209 * The math works as follows. x is the private key, M is the message to sign
210
211 1. pick a random k
212 2. compute a = g^k mod p
213 3. compute b = (M - xa)/k mod p
214 4. Send (a,b)
215
216 Now to verify with y=g^x mod p, a and b
217
218 1. compute y^a * a^b = g^(xa) * g^(k*(M-xa)/k)
219 = g^(xa + (M - xa))
220 = g^M [all mod p]
221
222 2. Compare against g^M mod p [based on input hash].
223 3. If result of #2 == result of #1 then signature valid
224 */
225 int dh_sign_hash(const unsigned char *in, unsigned long inlen,
226 unsigned char *out, unsigned long *outlen,
227 prng_state *prng, int wprng, dh_key *key)
228 {
229 mp_int a, b, k, m, g, p, p1, tmp;
230 unsigned char buf[520];
231 unsigned long x, y;
232 int err;
233
234 _ARGCHK(in != NULL);
235 _ARGCHK(out != NULL);
236 _ARGCHK(outlen != NULL);
237 _ARGCHK(key != NULL);
238
239 /* check parameters */
240 if (key->type != PK_PRIVATE) {
241 return CRYPT_PK_NOT_PRIVATE;
242 }
243
244 if ((err = prng_is_valid(wprng)) != CRYPT_OK) {
245 return err;
246 }
247
248 /* is the IDX valid ? */
249 if (is_valid_idx(key->idx) != 1) {
250 return CRYPT_PK_INVALID_TYPE;
251 }
252
253 /* make up a random value k,
254 * since the order of the group is prime
255 * we need not check if gcd(k, r) is 1
256 */
257 if (prng_descriptor[wprng].read(buf, sets[key->idx].size, prng) !=
258 (unsigned long)(sets[key->idx].size)) {
259 return CRYPT_ERROR_READPRNG;
260 }
261
262 /* init bignums */
263 if ((err = mp_init_multi(&a, &b, &k, &m, &p, &g, &p1, &tmp, NULL)) != MP_OKAY) {
264 return mpi_to_ltc_error(err);
265 }
266
267 /* load k and m */
268 if ((err = mp_read_unsigned_bin(&m, (unsigned char *)in, inlen)) != MP_OKAY) { goto error; }
269 #ifdef FAST_PK
270 if ((err = mp_read_unsigned_bin(&k, buf, MIN(32,sets[key->idx].size))) != MP_OKAY) { goto error; }
271 #else
272 if ((err = mp_read_unsigned_bin(&k, buf, sets[key->idx].size)) != MP_OKAY) { goto error; }
273 #endif
274
275 /* load g, p and p1 */
276 if ((err = mp_read_radix(&g, sets[key->idx].base, 64)) != MP_OKAY) { goto error; }
277 if ((err = mp_read_radix(&p, sets[key->idx].prime, 64)) != MP_OKAY) { goto error; }
278 if ((err = mp_sub_d(&p, 1, &p1)) != MP_OKAY) { goto error; }
279 if ((err = mp_div_2(&p1, &p1)) != MP_OKAY) { goto error; } /* p1 = (p-1)/2 */
280
281 /* now get a = g^k mod p */
282 if ((err = mp_exptmod(&g, &k, &p, &a)) != MP_OKAY) { goto error; }
283
284 /* now find M = xa + kb mod p1 or just b = (M - xa)/k mod p1 */
285 if ((err = mp_invmod(&k, &p1, &k)) != MP_OKAY) { goto error; } /* k = 1/k mod p1 */
286 if ((err = mp_mulmod(&a, &key->x, &p1, &tmp)) != MP_OKAY) { goto error; } /* tmp = xa */
287 if ((err = mp_submod(&m, &tmp, &p1, &tmp)) != MP_OKAY) { goto error; } /* tmp = M - xa */
288 if ((err = mp_mulmod(&k, &tmp, &p1, &b)) != MP_OKAY) { goto error; } /* b = (M - xa)/k */
289
290 /* check for overflow */
291 if ((unsigned long)(PACKET_SIZE + 4 + 4 + mp_unsigned_bin_size(&a) + mp_unsigned_bin_size(&b)) > *outlen) {
292 err = CRYPT_BUFFER_OVERFLOW;
293 goto done;
294 }
295
296 /* store header */
297 y = PACKET_SIZE;
298
299 /* now store them both (a,b) */
300 x = (unsigned long)mp_unsigned_bin_size(&a);
301 STORE32L(x, out+y); y += 4;
302 if ((err = mp_to_unsigned_bin(&a, out+y)) != MP_OKAY) { goto error; }
303 y += x;
304
305 x = (unsigned long)mp_unsigned_bin_size(&b);
306 STORE32L(x, out+y); y += 4;
307 if ((err = mp_to_unsigned_bin(&b, out+y)) != MP_OKAY) { goto error; }
308 y += x;
309
310 /* check if size too big */
311 if (*outlen < y) {
312 err = CRYPT_BUFFER_OVERFLOW;
313 goto done;
314 }
315
316 /* store header */
317 packet_store_header(out, PACKET_SECT_DH, PACKET_SUB_SIGNED);
318 *outlen = y;
319
320 err = CRYPT_OK;
321 goto done;
322 error:
323 err = mpi_to_ltc_error(err);
324 done:
325 mp_clear_multi(&tmp, &p1, &g, &p, &m, &k, &b, &a, NULL);
326 return err;
327 }
328
329
330 /* verify the signature in sig of the given hash */
331 int dh_verify_hash(const unsigned char *sig, unsigned long siglen,
332 const unsigned char *hash, unsigned long hashlen,
333 int *stat, dh_key *key)
334 {
335 mp_int a, b, p, g, m, tmp;
336 unsigned long x, y;
337 int err;
338
339 _ARGCHK(sig != NULL);
340 _ARGCHK(hash != NULL);
341 _ARGCHK(stat != NULL);
342 _ARGCHK(key != NULL);
343
344 /* default to invalid */
345 *stat = 0;
346
347 /* check initial input length */
348 if (siglen < PACKET_SIZE+4+4) {
349 return CRYPT_INVALID_PACKET;
350 }
351
352 /* header ok? */
353 if ((err = packet_valid_header((unsigned char *)sig, PACKET_SECT_DH, PACKET_SUB_SIGNED)) != CRYPT_OK) {
354 return err;
355 }
356
357 /* get hash out of packet */
358 y = PACKET_SIZE;
359
360 /* init all bignums */
361 if ((err = mp_init_multi(&a, &p, &b, &g, &m, &tmp, NULL)) != MP_OKAY) {
362 return mpi_to_ltc_error(err);
363 }
364
365 /* load a and b */
366 INPUT_BIGNUM(&a, sig, x, y, siglen);
367 INPUT_BIGNUM(&b, sig, x, y, siglen);
368
369 /* load p and g */
370 if ((err = mp_read_radix(&p, sets[key->idx].prime, 64)) != MP_OKAY) { goto error1; }
371 if ((err = mp_read_radix(&g, sets[key->idx].base, 64)) != MP_OKAY) { goto error1; }
372
373 /* load m */
374 if ((err = mp_read_unsigned_bin(&m, (unsigned char *)hash, hashlen)) != MP_OKAY) { goto error1; }
375
376 /* find g^m mod p */
377 if ((err = mp_exptmod(&g, &m, &p, &m)) != MP_OKAY) { goto error1; } /* m = g^m mod p */
378
379 /* find y^a * a^b */
380 if ((err = mp_exptmod(&key->y, &a, &p, &tmp)) != MP_OKAY) { goto error1; } /* tmp = y^a mod p */
381 if ((err = mp_exptmod(&a, &b, &p, &a)) != MP_OKAY) { goto error1; } /* a = a^b mod p */
382 if ((err = mp_mulmod(&a, &tmp, &p, &a)) != MP_OKAY) { goto error1; } /* a = y^a * a^b mod p */
383
384 /* y^a * a^b == g^m ??? */
385 if (mp_cmp(&a, &m) == 0) {
386 *stat = 1;
387 }
388
389 /* clean up */
390 err = CRYPT_OK;
391 goto done;
392 error1:
393 err = mpi_to_ltc_error(err);
394 error:
395 done:
396 mp_clear_multi(&tmp, &m, &g, &p, &b, &a, NULL);
397 return err;
398 }
399