lib/silccrypt/dsa.c

   1 /*
   2
   3   dsa.c
   4
   5   Author: Pekka Riikonen <priikone@silcnet.org>
   6
   7   Copyright (C) 2007 Pekka Riikonen
   8
   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.
  12
  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.
  17
  18 */
  19
  20 #include "silc.h"
  21 #include "dsa.h"
  22
  23 /************************** DSA PKCS Algorithm API **************************/
  24
  25 /* Notes about key formats:
  26
  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
  30    key format:
  31
  32    key ::= SEQUENCE {
  33      ver   INTEGER,
  34      p     INTEGER,
  35      q     INTEGER,
  36      g     INTEGER,
  37      y     INTEGER,
  38      x     INTEGER }
  39
  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):
  45
  46    key ::= SEQUENCE {
  47      p     INTEGER,
  48      q     INTEGER,
  49      g     INTEGER },
  50      y     INTEGER
  51
  52    Notes about signature format:
  53
  54    The encoded signature format is compliant with PKIX (X.509):
  55
  56    sig ::= SEQUENCE {
  57      r     INTEGER,
  58      s     INTEGER }
  59
  60 */
  61
  62 /* Generates DSA key pair.  For now this uses group size of 160 bits. */
  63
  64 SILC_PKCS_ALG_GENERATE_KEY(silc_dsa_generate_key)
  65 {
  66   DsaPublicKey *pubkey;
  67   DsaPrivateKey *privkey;
  68   SilcMPInt tmp, tmp2;
  69   unsigned char rnd[4096];
  70   int i, len = (keylen + 7) / 8, q_len = 160 / 8;
  71
  72   if (keylen < 768 || keylen > 16384)
  73     return FALSE;
  74
  75   pubkey = silc_calloc(1, sizeof(*pubkey));
  76   if (!pubkey)
  77     return FALSE;
  78
  79   privkey = silc_calloc(1, sizeof(*privkey));
  80   if (!privkey) {
  81     silc_free(pubkey);
  82     return FALSE;
  83   }
  84
  85   silc_mp_init(&tmp);
  86   silc_mp_init(&tmp2);
  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);
  96
  97   /* Generate primes q and p.  The p will satisfy (q * rnd) + 1 == p */
  98
  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);
 102
 103   do {
 104     /* Create p.  Take random data, this returns non-zero bytes.  Make the
 105        number even. */
 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);
 111
 112     /* Make p prime.  If it doesn't seem to happen, try again from the
 113        beginning. */
 114     for (i = 0; i < q_len * 2; i++) {
 115       if (silc_math_prime_test(&privkey->p))
 116         break;
 117       silc_mp_add(&privkey->p, &tmp, &privkey->p);
 118       silc_mp_add_ui(&tmp2, &tmp2, 2);
 119     }
 120   } while (i >= q_len * 2);
 121
 122   /* Find generator */
 123   silc_mp_set_ui(&privkey->g, 1);
 124   do {
 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);
 129
 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);
 133
 134   /* Generate public key */
 135   silc_mp_pow_mod(&privkey->y, &privkey->g, &privkey->x, &privkey->p);
 136
 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);
 142
 143   privkey->group_order = q_len;
 144   privkey->bits = keylen;
 145   pubkey->group_order = q_len;
 146   pubkey->bits = keylen;
 147
 148   silc_mp_uninit(&tmp);
 149   silc_mp_uninit(&tmp2);
 150
 151   if (ret_public_key)
 152     *ret_public_key = pubkey;
 153   if (ret_private_key)
 154     *ret_private_key = privkey;
 155
 156   return TRUE;
 157 }
 158
 159 /* Import DSA public key */
 160
 161 SILC_PKCS_ALG_IMPORT_PUBLIC_KEY(silc_dsa_import_public_key)
 162 {
 163   SilcAsn1 asn1;
 164   SilcBufferStruct alg_key;
 165   DsaPublicKey *pubkey;
 166
 167   SILC_LOG_DEBUG(("Import public key"));
 168
 169   if (!ret_public_key)
 170     return 0;
 171
 172   asn1 = silc_asn1_alloc(NULL);
 173   if (!asn1)
 174     return 0;
 175
 176   /* Allocate DSA public key */
 177   *ret_public_key = pubkey = silc_calloc(1, sizeof(*pubkey));
 178   if (!pubkey)
 179     goto err;
 180
 181   /* Parse */
 182   silc_buffer_set(&alg_key, key, key_len);
 183   if (!silc_asn1_decode(asn1, &alg_key,
 184                         SILC_ASN1_OPTS(SILC_ASN1_ALLOC),
 185                         SILC_ASN1_SEQUENCE,
 186                           SILC_ASN1_INT(&pubkey->p),
 187                           SILC_ASN1_INT(&pubkey->q),
 188                           SILC_ASN1_INT(&pubkey->g),
 189                         SILC_ASN1_END,
 190                         SILC_ASN1_INT(&pubkey->y),
 191                         SILC_ASN1_END))
 192     goto err;
 193
 194   /* Set key length */
 195   pubkey->bits = ((silc_mp_sizeinbase(&pubkey->p, 2) + 7) / 8) * 8;
 196
 197   silc_asn1_free(asn1);
 198
 199   return key_len;
 200
 201  err:
 202   silc_free(pubkey);
 203   silc_asn1_free(asn1);
 204   return 0;
 205 }
 206
 207 /* Export DSA public key */
 208
 209 SILC_PKCS_ALG_EXPORT_PUBLIC_KEY(silc_dsa_export_public_key)
 210 {
 211   DsaPublicKey *key = public_key;
 212   SilcAsn1 asn1 = NULL;
 213   SilcBufferStruct alg_key;
 214   unsigned char *ret;
 215
 216   SILC_LOG_DEBUG(("Export public key"));
 217
 218   asn1 = silc_asn1_alloc(stack);
 219   if (!asn1)
 220     goto err;
 221
 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),
 226                         SILC_ASN1_SEQUENCE,
 227                           SILC_ASN1_INT(&key->p),
 228                           SILC_ASN1_INT(&key->q),
 229                           SILC_ASN1_INT(&key->g),
 230                         SILC_ASN1_END,
 231                         SILC_ASN1_INT(&key->y),
 232                         SILC_ASN1_END))
 233     goto err;
 234
 235   ret = silc_buffer_steal(&alg_key, ret_len);
 236   silc_asn1_free(asn1);
 237
 238   return ret;
 239
 240  err:
 241   if (asn1)
 242     silc_asn1_free(asn1);
 243   return NULL;
 244 }
 245
 246 /* Return key length */
 247
 248 SILC_PKCS_ALG_PUBLIC_KEY_BITLEN(silc_dsa_public_key_bitlen)
 249 {
 250   DsaPublicKey *key = public_key;
 251   return key->bits;
 252 }
 253
 254 /* Copy public key */
 255
 256 SILC_PKCS_ALG_PUBLIC_KEY_COPY(silc_dsa_public_key_copy)
 257 {
 258   DsaPublicKey *key = public_key, *new_key;
 259
 260   new_key = silc_calloc(1, sizeof(*new_key));
 261   if (!new_key)
 262     return NULL;
 263
 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;
 270
 271   return new_key;
 272 }
 273
 274 /* Compare public keys */
 275
 276 SILC_PKCS_ALG_PUBLIC_KEY_COMPARE(silc_dsa_public_key_compare)
 277 {
 278   DsaPublicKey *k1 = key1, *k2 = key2;
 279
 280   if (k1->bits != k2->bits)
 281     return FALSE;
 282   if (k1->group_order != k2->group_order)
 283     return FALSE;
 284   if (silc_mp_cmp(&k1->p, &k2->p) != 0)
 285     return FALSE;
 286   if (silc_mp_cmp(&k1->q, &k2->q) != 0)
 287     return FALSE;
 288   if (silc_mp_cmp(&k1->g, &k2->g) != 0)
 289     return FALSE;
 290   if (silc_mp_cmp(&k1->y, &k2->y) != 0)
 291     return FALSE;
 292
 293   return TRUE;
 294 }
 295
 296 /* Free public key */
 297
 298 SILC_PKCS_ALG_PUBLIC_KEY_FREE(silc_dsa_public_key_free)
 299 {
 300   DsaPublicKey *key = public_key;
 301
 302   silc_mp_uninit(&key->p);
 303   silc_mp_uninit(&key->q);
 304   silc_mp_uninit(&key->g);
 305   silc_mp_uninit(&key->y);
 306   silc_free(key);
 307 }
 308
 309 /* Import DSA private key. */
 310
 311 SILC_PKCS_ALG_IMPORT_PRIVATE_KEY(silc_dsa_import_private_key)
 312 {
 313   SilcAsn1 asn1;
 314   SilcBufferStruct alg_key;
 315   DsaPrivateKey *privkey;
 316   SilcUInt32 ver;
 317
 318   SILC_LOG_DEBUG(("Import private key"));
 319
 320   if (!ret_private_key)
 321     return 0;
 322
 323   asn1 = silc_asn1_alloc(NULL);
 324   if (!asn1)
 325     return 0;
 326
 327   /* Allocate DSA private key */
 328   *ret_private_key = privkey = silc_calloc(1, sizeof(*privkey));
 329   if (!privkey)
 330     goto err;
 331
 332   /* Parse */
 333   silc_buffer_set(&alg_key, key, key_len);
 334   if (!silc_asn1_decode(asn1, &alg_key,
 335                         SILC_ASN1_OPTS(SILC_ASN1_ALLOC),
 336                         SILC_ASN1_SEQUENCE,
 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))
 344     goto err;
 345
 346   /* Set key length */
 347   privkey->bits = ((silc_mp_sizeinbase(&privkey->p, 2) + 7) / 8) * 8;
 348
 349   silc_asn1_free(asn1);
 350
 351   return key_len;
 352
 353  err:
 354   silc_free(privkey);
 355   silc_asn1_free(asn1);
 356   return 0;
 357 }
 358
 359 /* Export DSA private key. */
 360
 361 SILC_PKCS_ALG_EXPORT_PRIVATE_KEY(silc_dsa_export_private_key)
 362 {
 363   DsaPrivateKey *key = private_key;
 364   SilcAsn1 asn1;
 365   SilcBufferStruct alg_key;
 366   unsigned char *ret;
 367
 368   SILC_LOG_DEBUG(("Export private key"));
 369
 370   asn1 = silc_asn1_alloc(stack);
 371   if (!asn1)
 372     return FALSE;
 373
 374   /* Encode */
 375   memset(&alg_key, 0, sizeof(alg_key));
 376   if (!silc_asn1_encode(asn1, &alg_key,
 377                         SILC_ASN1_OPTS(SILC_ASN1_ALLOC),
 378                         SILC_ASN1_SEQUENCE,
 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))
 386     goto err;
 387
 388   ret = silc_buffer_steal(&alg_key, ret_len);
 389   silc_asn1_free(asn1);
 390
 391   return ret;
 392
 393  err:
 394   silc_asn1_free(asn1);
 395   return NULL;
 396 }
 397
 398 /* Return key length */
 399
 400 SILC_PKCS_ALG_PRIVATE_KEY_BITLEN(silc_dsa_private_key_bitlen)
 401 {
 402   DsaPrivateKey *key = private_key;
 403   return key->bits;
 404 }
 405
 406 /* Free private key */
 407
 408 SILC_PKCS_ALG_PRIVATE_KEY_FREE(silc_dsa_private_key_free)
 409 {
 410   DsaPrivateKey *key = private_key;
 411
 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);
 417   silc_free(key);
 418 }
 419
 420 /* Encryption.  Not supported */
 421
 422 SILC_PKCS_ALG_ENCRYPT(silc_dsa_encrypt)
 423 {
 424   SILC_LOG_WARNING(("DSA encryption is not supported"));
 425   encrypt_cb(FALSE, NULL, 0, context);
 426   return NULL;
 427 }
 428
 429 /* Decryption.  Not supported */
 430
 431 SILC_PKCS_ALG_DECRYPT(silc_dsa_decrypt)
 432 {
 433   SILC_LOG_WARNING(("DSA decryption is not supported"));
 434   decrypt_cb(FALSE, NULL, 0, context);
 435   return NULL;
 436 }
 437
 438 /* Sign */
 439
 440 SILC_PKCS_ALG_SIGN(silc_dsa_sign)
 441 {
 442   DsaPrivateKey *key = private_key;
 443   unsigned char kbuf[512], hashr[SILC_HASH_MAXLEN];
 444   SilcBufferStruct sig;
 445   SilcMPInt tmp, k, kinv, r, s;
 446   SilcStack stack;
 447   SilcAsn1 asn1;
 448
 449   SILC_LOG_DEBUG(("Sign"));
 450
 451   if (key->group_order > sizeof(kbuf)) {
 452     sign_cb(FALSE, NULL, 0, context);
 453     return NULL;
 454   }
 455
 456   if (!rng) {
 457     SILC_LOG_ERROR(("DSA signing requires random number generator"));
 458     sign_cb(FALSE, NULL, 0, context);
 459     return NULL;
 460   }
 461
 462   /* Compute hash if requested */
 463   if (compute_hash) {
 464     silc_hash_make(hash, src, src_len, hashr);
 465     src = hashr;
 466     src_len = silc_hash_len(hash);
 467   }
 468
 469   stack = silc_stack_alloc(2048, silc_crypto_stack());
 470
 471   asn1 = silc_asn1_alloc(stack);
 472   if (!asn1) {
 473     silc_stack_free(stack);
 474     sign_cb(FALSE, NULL, 0, context);
 475     return NULL;
 476   }
 477
 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);
 483
 484   do {
 485     do {
 486       /* Generate random k */
 487       do {
 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);
 492
 493       /* Compute kinv = k^-1 mod q */
 494       silc_mp_modinv(&kinv, &k, &key->q);
 495
 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);
 500
 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);
 508
 509   /* Encode the signature.  This format is compliant with PKIX. */
 510   memset(&sig, 0, sizeof(sig));
 511   if (!silc_asn1_encode(asn1, &sig,
 512                         SILC_ASN1_SEQUENCE,
 513                           SILC_ASN1_INT(&r),
 514                           SILC_ASN1_INT(&s),
 515                         SILC_ASN1_END, SILC_ASN1_END)) {
 516     sign_cb(FALSE, NULL, 0, context);
 517     goto out;
 518   }
 519
 520   /* Deliver result */
 521   sign_cb(TRUE, silc_buffer_data(&sig), silc_buffer_len(&sig), context);
 522
 523  out:
 524   memset(kbuf, 0, sizeof(kbuf));
 525   if (compute_hash)
 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);
 534
 535   return NULL;
 536 }
 537
 538 /* Verify */
 539
 540 SILC_PKCS_ALG_VERIFY(silc_dsa_verify)
 541 {
 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;
 547   SilcStack stack;
 548   SilcAsn1 asn1;
 549
 550   SILC_LOG_DEBUG(("Verify"));
 551
 552   stack = silc_stack_alloc(2048, silc_crypto_stack());
 553
 554   asn1 = silc_asn1_alloc(stack);
 555   if (!asn1) {
 556     silc_stack_free(stack);
 557     verify_cb(FALSE, context);
 558     return NULL;
 559   }
 560
 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),
 565                         SILC_ASN1_SEQUENCE,
 566                           SILC_ASN1_INT(&r),
 567                           SILC_ASN1_INT(&s),
 568                         SILC_ASN1_END, SILC_ASN1_END)) {
 569     silc_asn1_free(asn1);
 570     silc_stack_free(stack);
 571     verify_cb(FALSE, context);
 572     return NULL;
 573   }
 574
 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);
 582     return NULL;
 583   }
 584
 585   /* Hash data if requested */
 586   if (hash) {
 587     silc_hash_make(hash, data, data_len, hashr);
 588     data = hashr;
 589     data_len = silc_hash_len(hash);
 590   }
 591
 592   silc_mp_sinit(stack, &v);
 593   silc_mp_sinit(stack, &w);
 594   silc_mp_sinit(stack, &u1);
 595   silc_mp_sinit(stack, &u2);
 596
 597   /* Compute w = s^-1 mod q */
 598   silc_mp_modinv(&w, &s, &key->q);
 599
 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);
 604
 605   /* Compute u2 = r * w mod q */
 606   silc_mp_mul(&u2, &r, &w);
 607   silc_mp_mod(&u2, &u2, &key->q);
 608
 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);
 615
 616   /* Compare */
 617   if (silc_mp_cmp(&r, &v) == 0)
 618     ret = TRUE;
 619
 620   /* Deliver result */
 621   verify_cb(ret, context);
 622
 623   if (hash)
 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);
 631
 632   return NULL;
 633 }