← Back to branch summary

~ubuntu-branches/debian/lenny/dropbear/lenny

« back to all changes in this revision

Viewing changes to libtomcrypt/dh_sys.c

  • Committer: Bazaar Package Importer
  • Author(s): Matt Johnston
  • Date: 2004-06-16 12:44:54 UTC
  • Revision ID: james.westby@ubuntu.com-20040616124454-1udcijfiroqczfpe
Tags: upstream-0.42
Import upstream version 0.42

Show diffs side-by-side

added added

removed removed

Lines of Context:
libtomcrypt/dh_sys.c
 
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@iahu.ca, 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