5 Author: Pekka Riikonen <priikone@silcnet.org>
7 Copyright (C) 2007 Pekka Riikonen
9 This program is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; version 2 of the License.
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
23 /************************** DSA PKCS Algorithm API **************************/
25 /* Notes about key formats:
27 For DSA private key format the PKCS#8 (defined in PKCS#11) can be used but
28 would be an overkill for this low level API. Thus, we use our own DSA
29 private key format that is equivalent to GnuTLS and OpenSSL DSA private
40 For DSA public keys we also use our own format since the standard formats
41 require the public key ASN.1 data to be in two parts (algorithm params and
42 the key itself). We don't require such format for this low level API and
43 expect that if that format is used it is trivial to convert it to this
44 internal format (which is just concatenation of the params and the key):
52 Notes about signature format:
54 The encoded signature format is compliant with PKIX (X.509):
62 /* Generates DSA key pair. For now this uses group size of 160 bits. */
64 SILC_PKCS_ALG_GENERATE_KEY(silc_dsa_generate_key)
67 DsaPrivateKey *privkey;
69 unsigned char rnd[4096];
70 int i, len = (keylen + 7) / 8, q_len = 160 / 8;
72 if (keylen < 768 || keylen > 16384)
75 pubkey = silc_calloc(1, sizeof(*pubkey));
79 privkey = silc_calloc(1, sizeof(*privkey));
87 silc_mp_init(&privkey->p);
88 silc_mp_init(&privkey->q);
89 silc_mp_init(&privkey->g);
90 silc_mp_init(&privkey->y);
91 silc_mp_init(&privkey->x);
92 silc_mp_init(&pubkey->p);
93 silc_mp_init(&pubkey->q);
94 silc_mp_init(&pubkey->g);
95 silc_mp_init(&pubkey->y);
97 /* Generate primes q and p. The p will satisfy (q * rnd) + 1 == p */
99 /* Generate prime q */
100 silc_math_gen_prime(&privkey->q, q_len * 8, FALSE, rng);
101 silc_mp_add(&tmp, &privkey->q, &privkey->q);
104 /* Create p. Take random data, this returns non-zero bytes. Make the
106 silc_rng_get_rn_data(rng, len - q_len, rnd, sizeof(rnd));
107 rnd[(len - q_len) - 1] &= ~1;
108 silc_mp_bin2mp(rnd, len - q_len, &tmp2);
109 silc_mp_mul(&privkey->p, &privkey->q, &tmp2);
110 silc_mp_add_ui(&privkey->p, &privkey->p, 1);
112 /* Make p prime. If it doesn't seem to happen, try again from the
114 for (i = 0; i < q_len * 2; i++) {
115 if (silc_math_prime_test(&privkey->p))
117 silc_mp_add(&privkey->p, &tmp, &privkey->p);
118 silc_mp_add_ui(&tmp2, &tmp2, 2);
120 } while (i >= q_len * 2);
123 silc_mp_set_ui(&privkey->g, 1);
125 silc_mp_add_ui(&privkey->g, &privkey->g, 1);
126 silc_mp_pow_mod(&tmp, &privkey->g, &tmp2, &privkey->p);
127 } while (silc_mp_cmp_ui(&tmp, 1) == 0);
128 silc_mp_set(&privkey->g, &tmp);
130 /* Generate private key */
131 silc_rng_get_rn_data(rng, q_len, rnd, sizeof(rnd));
132 silc_mp_bin2mp(rnd, q_len, &privkey->x);
134 /* Generate public key */
135 silc_mp_pow_mod(&privkey->y, &privkey->g, &privkey->x, &privkey->p);
137 /* Now set the integers to public key too */
138 silc_mp_set(&pubkey->p, &privkey->p);
139 silc_mp_set(&pubkey->q, &privkey->q);
140 silc_mp_set(&pubkey->g, &privkey->g);
141 silc_mp_set(&pubkey->y, &privkey->y);
143 privkey->group_order = q_len;
144 privkey->bits = keylen;
145 pubkey->group_order = q_len;
146 pubkey->bits = keylen;
148 silc_mp_uninit(&tmp);
149 silc_mp_uninit(&tmp2);
152 *ret_public_key = pubkey;
154 *ret_private_key = privkey;
159 /* Import DSA public key */
161 SILC_PKCS_ALG_IMPORT_PUBLIC_KEY(silc_dsa_import_public_key)
164 SilcBufferStruct alg_key;
165 DsaPublicKey *pubkey;
167 SILC_LOG_DEBUG(("Import public key"));
172 asn1 = silc_asn1_alloc(NULL);
176 /* Allocate DSA public key */
177 *ret_public_key = pubkey = silc_calloc(1, sizeof(*pubkey));
182 silc_buffer_set(&alg_key, key, key_len);
183 if (!silc_asn1_decode(asn1, &alg_key,
184 SILC_ASN1_OPTS(SILC_ASN1_ALLOC),
186 SILC_ASN1_INT(&pubkey->p),
187 SILC_ASN1_INT(&pubkey->q),
188 SILC_ASN1_INT(&pubkey->g),
190 SILC_ASN1_INT(&pubkey->y),
195 pubkey->bits = ((silc_mp_sizeinbase(&pubkey->p, 2) + 7) / 8) * 8;
197 silc_asn1_free(asn1);
203 silc_asn1_free(asn1);
207 /* Export DSA public key */
209 SILC_PKCS_ALG_EXPORT_PUBLIC_KEY(silc_dsa_export_public_key)
211 DsaPublicKey *key = public_key;
212 SilcAsn1 asn1 = NULL;
213 SilcBufferStruct alg_key;
216 SILC_LOG_DEBUG(("Export public key"));
218 asn1 = silc_asn1_alloc(stack);
222 /* Encode public key */
223 memset(&alg_key, 0, sizeof(alg_key));
224 if (!silc_asn1_encode(asn1, &alg_key,
225 SILC_ASN1_OPTS(SILC_ASN1_ALLOC),
227 SILC_ASN1_INT(&key->p),
228 SILC_ASN1_INT(&key->q),
229 SILC_ASN1_INT(&key->g),
231 SILC_ASN1_INT(&key->y),
235 ret = silc_buffer_steal(&alg_key, ret_len);
236 silc_asn1_free(asn1);
242 silc_asn1_free(asn1);
246 /* Return key length */
248 SILC_PKCS_ALG_PUBLIC_KEY_BITLEN(silc_dsa_public_key_bitlen)
250 DsaPublicKey *key = public_key;
254 /* Copy public key */
256 SILC_PKCS_ALG_PUBLIC_KEY_COPY(silc_dsa_public_key_copy)
258 DsaPublicKey *key = public_key, *new_key;
260 new_key = silc_calloc(1, sizeof(*new_key));
264 silc_mp_init(&new_key->p);
265 silc_mp_init(&new_key->q);
266 silc_mp_init(&new_key->g);
267 silc_mp_init(&new_key->y);
268 new_key->bits = key->bits;
269 new_key->group_order = key->group_order;
274 /* Compare public keys */
276 SILC_PKCS_ALG_PUBLIC_KEY_COMPARE(silc_dsa_public_key_compare)
278 DsaPublicKey *k1 = key1, *k2 = key2;
280 if (k1->bits != k2->bits)
282 if (k1->group_order != k2->group_order)
284 if (silc_mp_cmp(&k1->p, &k2->p) != 0)
286 if (silc_mp_cmp(&k1->q, &k2->q) != 0)
288 if (silc_mp_cmp(&k1->g, &k2->g) != 0)
290 if (silc_mp_cmp(&k1->y, &k2->y) != 0)
296 /* Free public key */
298 SILC_PKCS_ALG_PUBLIC_KEY_FREE(silc_dsa_public_key_free)
300 DsaPublicKey *key = public_key;
302 silc_mp_uninit(&key->p);
303 silc_mp_uninit(&key->q);
304 silc_mp_uninit(&key->g);
305 silc_mp_uninit(&key->y);
309 /* Import DSA private key. */
311 SILC_PKCS_ALG_IMPORT_PRIVATE_KEY(silc_dsa_import_private_key)
314 SilcBufferStruct alg_key;
315 DsaPrivateKey *privkey;
318 SILC_LOG_DEBUG(("Import private key"));
320 if (!ret_private_key)
323 asn1 = silc_asn1_alloc(NULL);
327 /* Allocate DSA private key */
328 *ret_private_key = privkey = silc_calloc(1, sizeof(*privkey));
333 silc_buffer_set(&alg_key, key, key_len);
334 if (!silc_asn1_decode(asn1, &alg_key,
335 SILC_ASN1_OPTS(SILC_ASN1_ALLOC),
337 SILC_ASN1_SHORT_INT(&ver),
338 SILC_ASN1_INT(&privkey->p),
339 SILC_ASN1_INT(&privkey->q),
340 SILC_ASN1_INT(&privkey->g),
341 SILC_ASN1_INT(&privkey->y),
342 SILC_ASN1_INT(&privkey->x),
343 SILC_ASN1_END, SILC_ASN1_END))
347 privkey->bits = ((silc_mp_sizeinbase(&privkey->p, 2) + 7) / 8) * 8;
349 silc_asn1_free(asn1);
355 silc_asn1_free(asn1);
359 /* Export DSA private key. */
361 SILC_PKCS_ALG_EXPORT_PRIVATE_KEY(silc_dsa_export_private_key)
363 DsaPrivateKey *key = private_key;
365 SilcBufferStruct alg_key;
368 SILC_LOG_DEBUG(("Export private key"));
370 asn1 = silc_asn1_alloc(stack);
375 memset(&alg_key, 0, sizeof(alg_key));
376 if (!silc_asn1_encode(asn1, &alg_key,
377 SILC_ASN1_OPTS(SILC_ASN1_ALLOC),
379 SILC_ASN1_SHORT_INT(0),
380 SILC_ASN1_INT(&key->p),
381 SILC_ASN1_INT(&key->q),
382 SILC_ASN1_INT(&key->g),
383 SILC_ASN1_INT(&key->y),
384 SILC_ASN1_INT(&key->x),
385 SILC_ASN1_END, SILC_ASN1_END))
388 ret = silc_buffer_steal(&alg_key, ret_len);
389 silc_asn1_free(asn1);
394 silc_asn1_free(asn1);
398 /* Return key length */
400 SILC_PKCS_ALG_PRIVATE_KEY_BITLEN(silc_dsa_private_key_bitlen)
402 DsaPrivateKey *key = private_key;
406 /* Free private key */
408 SILC_PKCS_ALG_PRIVATE_KEY_FREE(silc_dsa_private_key_free)
410 DsaPrivateKey *key = private_key;
412 silc_mp_uninit(&key->p);
413 silc_mp_uninit(&key->q);
414 silc_mp_uninit(&key->g);
415 silc_mp_uninit(&key->y);
416 silc_mp_uninit(&key->x);
420 /* Encryption. Not supported */
422 SILC_PKCS_ALG_ENCRYPT(silc_dsa_encrypt)
424 SILC_LOG_WARNING(("DSA encryption is not supported"));
425 encrypt_cb(FALSE, NULL, 0, context);
429 /* Decryption. Not supported */
431 SILC_PKCS_ALG_DECRYPT(silc_dsa_decrypt)
433 SILC_LOG_WARNING(("DSA decryption is not supported"));
434 decrypt_cb(FALSE, NULL, 0, context);
440 SILC_PKCS_ALG_SIGN(silc_dsa_sign)
442 DsaPrivateKey *key = private_key;
443 unsigned char kbuf[512], hashr[SILC_HASH_MAXLEN];
444 SilcBufferStruct sig;
445 SilcMPInt tmp, k, kinv, r, s;
449 SILC_LOG_DEBUG(("Sign"));
451 if (key->group_order > sizeof(kbuf)) {
452 sign_cb(FALSE, NULL, 0, context);
457 SILC_LOG_ERROR(("DSA signing requires random number generator"));
458 sign_cb(FALSE, NULL, 0, context);
462 /* Compute hash if requested */
464 silc_hash_make(hash, src, src_len, hashr);
466 src_len = silc_hash_len(hash);
469 stack = silc_stack_alloc(2048, silc_crypto_stack());
471 asn1 = silc_asn1_alloc(stack);
473 silc_stack_free(stack);
474 sign_cb(FALSE, NULL, 0, context);
478 silc_mp_sinit(stack, &k);
479 silc_mp_sinit(stack, &kinv);
480 silc_mp_sinit(stack, &r);
481 silc_mp_sinit(stack, &s);
482 silc_mp_sinit(stack, &tmp);
486 /* Generate random k */
488 silc_rng_get_rn_data(rng, key->group_order, kbuf, sizeof(kbuf));
489 silc_mp_bin2mp(kbuf, key->group_order, &k);
490 silc_mp_gcd(&tmp, &k, &key->q);
491 } while (silc_mp_cmp_ui(&tmp, 1) != 0);
493 /* Compute kinv = k^-1 mod q */
494 silc_mp_modinv(&kinv, &k, &key->q);
496 /* Compute signature part r = g^k mod p mod q */
497 silc_mp_pow_mod(&r, &key->g, &k, &key->p);
498 silc_mp_mod(&r, &r, &key->q);
499 } while (silc_mp_cmp_ui(&r, 0) == 0);
501 /* Compute signature part s = (src + x * r) / k mod q */
502 silc_mp_bin2mp(src, src_len, &tmp);
503 silc_mp_mul(&s, &key->x, &r);
504 silc_mp_add(&s, &s, &tmp);
505 silc_mp_mul(&s, &s, &kinv);
506 silc_mp_mod(&s, &s, &key->q);
507 } while (silc_mp_cmp_ui(&s, 0) == 0);
509 /* Encode the signature. This format is compliant with PKIX. */
510 memset(&sig, 0, sizeof(sig));
511 if (!silc_asn1_encode(asn1, &sig,
515 SILC_ASN1_END, SILC_ASN1_END)) {
516 sign_cb(FALSE, NULL, 0, context);
521 sign_cb(TRUE, silc_buffer_data(&sig), silc_buffer_len(&sig), context);
524 memset(kbuf, 0, sizeof(kbuf));
526 memset(hashr, 0, sizeof(hashr));
527 silc_mp_suninit(stack, &k);
528 silc_mp_suninit(stack, &kinv);
529 silc_mp_suninit(stack, &r);
530 silc_mp_suninit(stack, &s);
531 silc_mp_suninit(stack, &tmp);
532 silc_asn1_free(asn1);
533 silc_stack_free(stack);
540 SILC_PKCS_ALG_VERIFY(silc_dsa_verify)
542 DsaPublicKey *key = public_key;
543 unsigned char hashr[SILC_HASH_MAXLEN];
544 SilcBool ret = FALSE;
545 SilcBufferStruct sig;
546 SilcMPInt r, s, v, w, u1, u2;
550 SILC_LOG_DEBUG(("Verify"));
552 stack = silc_stack_alloc(2048, silc_crypto_stack());
554 asn1 = silc_asn1_alloc(stack);
556 silc_stack_free(stack);
557 verify_cb(FALSE, context);
561 /* Decode the signature */
562 silc_buffer_set(&sig, signature, signature_len);
563 if (!silc_asn1_decode(asn1, &sig,
564 SILC_ASN1_OPTS(SILC_ASN1_ALLOC),
568 SILC_ASN1_END, SILC_ASN1_END)) {
569 silc_asn1_free(asn1);
570 silc_stack_free(stack);
571 verify_cb(FALSE, context);
575 if (silc_mp_cmp_ui(&r, 0) == 0 ||
576 silc_mp_cmp_ui(&s, 0) == 0 ||
577 silc_mp_cmp(&r, &key->q) >= 0 ||
578 silc_mp_cmp(&s, &key->q) >= 0) {
579 silc_asn1_free(asn1);
580 silc_stack_free(stack);
581 verify_cb(FALSE, context);
585 /* Hash data if requested */
587 silc_hash_make(hash, data, data_len, hashr);
589 data_len = silc_hash_len(hash);
592 silc_mp_sinit(stack, &v);
593 silc_mp_sinit(stack, &w);
594 silc_mp_sinit(stack, &u1);
595 silc_mp_sinit(stack, &u2);
597 /* Compute w = s^-1 mod q */
598 silc_mp_modinv(&w, &s, &key->q);
600 /* Compute u1 = data * w mod q */
601 silc_mp_bin2mp(data, data_len, &u1);
602 silc_mp_mul(&u1, &u1, &w);
603 silc_mp_mod(&u1, &u1, &key->q);
605 /* Compute u2 = r * w mod q */
606 silc_mp_mul(&u2, &r, &w);
607 silc_mp_mod(&u2, &u2, &key->q);
609 /* Compute v = g ^ u1 * y ^ u2 mod p mod q */
610 silc_mp_pow_mod(&u1, &key->g, &u1, &key->p);
611 silc_mp_pow_mod(&u2, &key->y, &u2, &key->p);
612 silc_mp_mul(&v, &u1, &u2);
613 silc_mp_mod(&v, &v, &key->p);
614 silc_mp_mod(&v, &v, &key->q);
617 if (silc_mp_cmp(&r, &v) == 0)
621 verify_cb(ret, context);
624 memset(hashr, 0, sizeof(hashr));
625 silc_mp_suninit(stack, &v);
626 silc_mp_suninit(stack, &w);
627 silc_mp_suninit(stack, &u1);
628 silc_mp_suninit(stack, &u2);
629 silc_asn1_free(asn1);
630 silc_stack_free(stack);