lib/silccrypt/dsa.c

   1 /*
   2
   3   dsa.c
   4
   5   Author: Pekka Riikonen <priikone@silcnet.org>
   6
   7   Copyright (C) 2007 - 2008 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 "silccrypto.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.  The q length and hash comes as argument. */
  63
  64 static SilcBool
  65 silc_dsa_generate_key_int(const struct SilcPKCSAlgorithmStruct *pkcs,
  66                           SilcUInt32 q_len, const char *hash,
  67                           SilcUInt32 keylen, SilcRng rng,
  68                           void **ret_public_key, void **ret_private_key)
  69 {
  70   DsaPublicKey *pubkey;
  71   DsaPrivateKey *privkey;
  72   SilcMPInt tmp, tmp2;
  73   unsigned char rnd[4096];
  74   int i, len = (keylen + 7) / 8;
  75
  76   q_len /= 8;
  77
  78   if (keylen < 768 || keylen > 16384)
  79     return FALSE;
  80
  81   if (!silc_hash_is_supported(hash))
  82     return FALSE;
  83
  84   pubkey = silc_calloc(1, sizeof(*pubkey));
  85   if (!pubkey)
  86     return FALSE;
  87
  88   privkey = silc_calloc(1, sizeof(*privkey));
  89   if (!privkey) {
  90     silc_free(pubkey);
  91     return FALSE;
  92   }
  93
  94   silc_hash_alloc(hash, &pubkey->hash);
  95   silc_hash_alloc(hash, &privkey->hash);
  96
  97   silc_mp_init(&tmp);
  98   silc_mp_init(&tmp2);
  99   silc_mp_init(&privkey->p);
 100   silc_mp_init(&privkey->q);
 101   silc_mp_init(&privkey->g);
 102   silc_mp_init(&privkey->y);
 103   silc_mp_init(&privkey->x);
 104   silc_mp_init(&pubkey->p);
 105   silc_mp_init(&pubkey->q);
 106   silc_mp_init(&pubkey->g);
 107   silc_mp_init(&pubkey->y);
 108
 109   /* Generate primes q and p.  The p will satisfy (q * rnd) + 1 == p */
 110
 111   /* Generate prime q */
 112   silc_math_gen_prime(&privkey->q, q_len * 8, FALSE, rng);
 113   silc_mp_add(&tmp, &privkey->q, &privkey->q);
 114
 115   do {
 116     /* Create p.  Take random data, this returns non-zero bytes. */
 117     silc_rng_get_rn_data(rng, len - q_len, rnd, sizeof(rnd));
 118     rnd[(len - q_len) - 1] &= ~1;
 119     silc_mp_bin2mp(rnd, len - q_len, &tmp2);
 120     silc_mp_mul(&privkey->p, &privkey->q, &tmp2);
 121     silc_mp_add_ui(&privkey->p, &privkey->p, 1);
 122
 123     /* Make p prime.  If it doesn't seem to happen, try again from the
 124        beginning. */
 125     for (i = 0; i < q_len * 2; i++) {
 126       if (silc_math_prime_test(&privkey->p))
 127         break;
 128       silc_mp_add(&privkey->p, &tmp, &privkey->p);
 129       silc_mp_add_ui(&tmp2, &tmp2, 2);
 130     }
 131   } while (i >= q_len * 2);
 132
 133   /* Find generator */
 134   silc_mp_set_ui(&privkey->g, 1);
 135   do {
 136     silc_mp_add_ui(&privkey->g, &privkey->g, 1);
 137     silc_mp_pow_mod(&tmp, &privkey->g, &tmp2, &privkey->p);
 138   } while (silc_mp_cmp_ui(&tmp, 1) == 0);
 139   silc_mp_set(&privkey->g, &tmp);
 140
 141   /* Generate private key */
 142   silc_rng_get_rn_data(rng, q_len, rnd, sizeof(rnd));
 143   silc_mp_bin2mp(rnd, q_len, &privkey->x);
 144
 145   /* Generate public key */
 146   silc_mp_pow_mod(&privkey->y, &privkey->g, &privkey->x, &privkey->p);
 147
 148   /* Now set the integers to public key too */
 149   silc_mp_set(&pubkey->p, &privkey->p);
 150   silc_mp_set(&pubkey->q, &privkey->q);
 151   silc_mp_set(&pubkey->g, &privkey->g);
 152   silc_mp_set(&pubkey->y, &privkey->y);
 153
 154   privkey->group_order = q_len;
 155   privkey->bits = keylen;
 156   pubkey->group_order = q_len;
 157   pubkey->bits = keylen;
 158
 159   silc_mp_uninit(&tmp);
 160   silc_mp_uninit(&tmp2);
 161
 162   if (ret_public_key)
 163     *ret_public_key = pubkey;
 164   if (ret_private_key)
 165     *ret_private_key = privkey;
 166
 167   return TRUE;
 168 }
 169
 170 /* Generates DSA key pair.  Complies with FIPS186-2.  Uses 160 bit q. */
 171
 172 SILC_PKCS_ALG_GENERATE_KEY(silc_dsa_fips186_2_generate_key)
 173 {
 174   return silc_dsa_generate_key_int(pkcs, 160, "sha1", keylen, rng,
 175                                    ret_public_key, ret_private_key);
 176 }
 177
 178 /* Generates DSA key pair.  Complies with FIPS186-3.  Same as the FIPS186-2
 179    but determines the length of q automatically. */
 180
 181 SILC_PKCS_ALG_GENERATE_KEY(silc_dsa_generate_key)
 182 {
 183   SilcUInt32 q_len;
 184   const char *hash;
 185
 186   if (keylen <= 1024) {
 187     q_len = 160;
 188     hash = "sha1";
 189   } else if (keylen <= 2048) {
 190     q_len = 224;
 191     hash = "sha224";
 192   } else {
 193     q_len = 256;
 194     hash = "sha256";
 195   }
 196
 197   return silc_dsa_generate_key_int(pkcs, q_len, hash, keylen, rng,
 198                                    ret_public_key, ret_private_key);
 199 }
 200
 201 /* Import DSA public key */
 202
 203 SILC_PKCS_ALG_IMPORT_PUBLIC_KEY(silc_dsa_import_public_key)
 204 {
 205   SilcAsn1 asn1;
 206   SilcBufferStruct alg_key;
 207   DsaPublicKey *pubkey;
 208
 209   SILC_LOG_DEBUG(("Import public key"));
 210
 211   if (!ret_public_key)
 212     return 0;
 213
 214   asn1 = silc_asn1_alloc(NULL);
 215   if (!asn1)
 216     return 0;
 217
 218   /* Allocate DSA public key */
 219   *ret_public_key = pubkey = silc_calloc(1, sizeof(*pubkey));
 220   if (!pubkey)
 221     goto err;
 222
 223   /* Parse */
 224   silc_buffer_set(&alg_key, key, key_len);
 225   if (!silc_asn1_decode(asn1, &alg_key,
 226                         SILC_ASN1_OPTS(SILC_ASN1_ALLOC),
 227                         SILC_ASN1_SEQUENCE,
 228                           SILC_ASN1_INT(&pubkey->p),
 229                           SILC_ASN1_INT(&pubkey->q),
 230                           SILC_ASN1_INT(&pubkey->g),
 231                         SILC_ASN1_END,
 232                         SILC_ASN1_INT(&pubkey->y),
 233                         SILC_ASN1_END))
 234     goto err;
 235
 236   /* Set key length */
 237   pubkey->bits = ((silc_mp_sizeinbase(&pubkey->p, 2) + 7) / 8) * 8;
 238
 239   silc_asn1_free(asn1);
 240
 241   return key_len;
 242
 243  err:
 244   silc_free(pubkey);
 245   silc_asn1_free(asn1);
 246   return 0;
 247 }
 248
 249 /* Export DSA public key */
 250
 251 SILC_PKCS_ALG_EXPORT_PUBLIC_KEY(silc_dsa_export_public_key)
 252 {
 253   DsaPublicKey *key = public_key;
 254   SilcAsn1 asn1 = NULL;
 255   SilcBufferStruct alg_key;
 256   unsigned char *ret;
 257
 258   SILC_LOG_DEBUG(("Export public key"));
 259
 260   asn1 = silc_asn1_alloc(stack);
 261   if (!asn1)
 262     goto err;
 263
 264   /* Encode public key */
 265   memset(&alg_key, 0, sizeof(alg_key));
 266   if (!silc_asn1_encode(asn1, &alg_key,
 267                         SILC_ASN1_OPTS(SILC_ASN1_ALLOC),
 268                         SILC_ASN1_SEQUENCE,
 269                           SILC_ASN1_INT(&key->p),
 270                           SILC_ASN1_INT(&key->q),
 271                           SILC_ASN1_INT(&key->g),
 272                         SILC_ASN1_END,
 273                         SILC_ASN1_INT(&key->y),
 274                         SILC_ASN1_END))
 275     goto err;
 276
 277   ret = silc_buffer_steal(&alg_key, ret_len);
 278   silc_asn1_free(asn1);
 279
 280   return ret;
 281
 282  err:
 283   if (asn1)
 284     silc_asn1_free(asn1);
 285   return NULL;
 286 }
 287
 288 /* Return key length */
 289
 290 SILC_PKCS_ALG_PUBLIC_KEY_BITLEN(silc_dsa_public_key_bitlen)
 291 {
 292   DsaPublicKey *key = public_key;
 293   return key->bits;
 294 }
 295
 296 /* Copy public key */
 297
 298 SILC_PKCS_ALG_PUBLIC_KEY_COPY(silc_dsa_public_key_copy)
 299 {
 300   DsaPublicKey *key = public_key, *new_key;
 301
 302   new_key = silc_calloc(1, sizeof(*new_key));
 303   if (!new_key)
 304     return NULL;
 305
 306   silc_mp_init(&new_key->p);
 307   silc_mp_init(&new_key->q);
 308   silc_mp_init(&new_key->g);
 309   silc_mp_init(&new_key->y);
 310   new_key->bits = key->bits;
 311   new_key->group_order = key->group_order;
 312
 313   return new_key;
 314 }
 315
 316 /* Compare public keys */
 317
 318 SILC_PKCS_ALG_PUBLIC_KEY_COMPARE(silc_dsa_public_key_compare)
 319 {
 320   DsaPublicKey *k1 = key1, *k2 = key2;
 321
 322   if (k1->bits != k2->bits)
 323     return FALSE;
 324   if (k1->group_order != k2->group_order)
 325     return FALSE;
 326   if (silc_mp_cmp(&k1->p, &k2->p) != 0)
 327     return FALSE;
 328   if (silc_mp_cmp(&k1->q, &k2->q) != 0)
 329     return FALSE;
 330   if (silc_mp_cmp(&k1->g, &k2->g) != 0)
 331     return FALSE;
 332   if (silc_mp_cmp(&k1->y, &k2->y) != 0)
 333     return FALSE;
 334
 335   return TRUE;
 336 }
 337
 338 /* Free public key */
 339
 340 SILC_PKCS_ALG_PUBLIC_KEY_FREE(silc_dsa_public_key_free)
 341 {
 342   DsaPublicKey *key = public_key;
 343
 344   silc_mp_uninit(&key->p);
 345   silc_mp_uninit(&key->q);
 346   silc_mp_uninit(&key->g);
 347   silc_mp_uninit(&key->y);
 348   silc_hash_free(key->hash);
 349   silc_free(key);
 350 }
 351
 352 /* Import DSA private key. */
 353
 354 SILC_PKCS_ALG_IMPORT_PRIVATE_KEY(silc_dsa_import_private_key)
 355 {
 356   SilcAsn1 asn1;
 357   SilcBufferStruct alg_key;
 358   DsaPrivateKey *privkey;
 359   SilcUInt32 ver;
 360
 361   SILC_LOG_DEBUG(("Import private key"));
 362
 363   if (!ret_private_key)
 364     return 0;
 365
 366   asn1 = silc_asn1_alloc(NULL);
 367   if (!asn1)
 368     return 0;
 369
 370   /* Allocate DSA private key */
 371   *ret_private_key = privkey = silc_calloc(1, sizeof(*privkey));
 372   if (!privkey)
 373     goto err;
 374
 375   /* Parse */
 376   silc_buffer_set(&alg_key, key, key_len);
 377   if (!silc_asn1_decode(asn1, &alg_key,
 378                         SILC_ASN1_OPTS(SILC_ASN1_ALLOC),
 379                         SILC_ASN1_SEQUENCE,
 380                           SILC_ASN1_SHORT_INT(&ver),
 381                           SILC_ASN1_INT(&privkey->p),
 382                           SILC_ASN1_INT(&privkey->q),
 383                           SILC_ASN1_INT(&privkey->g),
 384                           SILC_ASN1_INT(&privkey->y),
 385                           SILC_ASN1_INT(&privkey->x),
 386                         SILC_ASN1_END, SILC_ASN1_END))
 387     goto err;
 388
 389   /* Set key length */
 390   privkey->bits = ((silc_mp_sizeinbase(&privkey->p, 2) + 7) / 8) * 8;
 391
 392   silc_asn1_free(asn1);
 393
 394   return key_len;
 395
 396  err:
 397   silc_free(privkey);
 398   silc_asn1_free(asn1);
 399   return 0;
 400 }
 401
 402 /* Export DSA private key. */
 403
 404 SILC_PKCS_ALG_EXPORT_PRIVATE_KEY(silc_dsa_export_private_key)
 405 {
 406   DsaPrivateKey *key = private_key;
 407   SilcAsn1 asn1;
 408   SilcBufferStruct alg_key;
 409   unsigned char *ret;
 410
 411   SILC_LOG_DEBUG(("Export private key"));
 412
 413   asn1 = silc_asn1_alloc(stack);
 414   if (!asn1)
 415     return FALSE;
 416
 417   /* Encode */
 418   memset(&alg_key, 0, sizeof(alg_key));
 419   if (!silc_asn1_encode(asn1, &alg_key,
 420                         SILC_ASN1_OPTS(SILC_ASN1_ALLOC),
 421                         SILC_ASN1_SEQUENCE,
 422                           SILC_ASN1_SHORT_INT(0),
 423                           SILC_ASN1_INT(&key->p),
 424                           SILC_ASN1_INT(&key->q),
 425                           SILC_ASN1_INT(&key->g),
 426                           SILC_ASN1_INT(&key->y),
 427                           SILC_ASN1_INT(&key->x),
 428                         SILC_ASN1_END, SILC_ASN1_END))
 429     goto err;
 430
 431   ret = silc_buffer_steal(&alg_key, ret_len);
 432   silc_asn1_free(asn1);
 433
 434   return ret;
 435
 436  err:
 437   silc_asn1_free(asn1);
 438   return NULL;
 439 }
 440
 441 /* Return key length */
 442
 443 SILC_PKCS_ALG_PRIVATE_KEY_BITLEN(silc_dsa_private_key_bitlen)
 444 {
 445   DsaPrivateKey *key = private_key;
 446   return key->bits;
 447 }
 448
 449 /* Free private key */
 450
 451 SILC_PKCS_ALG_PRIVATE_KEY_FREE(silc_dsa_private_key_free)
 452 {
 453   DsaPrivateKey *key = private_key;
 454
 455   silc_mp_uninit(&key->p);
 456   silc_mp_uninit(&key->q);
 457   silc_mp_uninit(&key->g);
 458   silc_mp_uninit(&key->y);
 459   silc_mp_uninit(&key->x);
 460   silc_hash_free(key->hash);
 461   silc_free(key);
 462 }
 463
 464 /* Encryption.  Not supported */
 465
 466 SILC_PKCS_ALG_ENCRYPT(silc_dsa_encrypt)
 467 {
 468   SILC_LOG_WARNING(("DSA encryption is not supported"));
 469   encrypt_cb(FALSE, NULL, 0, context);
 470   return NULL;
 471 }
 472
 473 /* Decryption.  Not supported */
 474
 475 SILC_PKCS_ALG_DECRYPT(silc_dsa_decrypt)
 476 {
 477   SILC_LOG_WARNING(("DSA decryption is not supported"));
 478   decrypt_cb(FALSE, NULL, 0, context);
 479   return NULL;
 480 }
 481
 482 /* Sign */
 483
 484 SILC_PKCS_ALG_SIGN(silc_dsa_sign)
 485 {
 486   DsaPrivateKey *key = private_key;
 487   unsigned char kbuf[512], hashr[SILC_HASH_MAXLEN];
 488   SilcBufferStruct sig;
 489   SilcMPInt tmp, k, kinv, r, s;
 490   SilcStack stack;
 491   SilcAsn1 asn1;
 492
 493   SILC_LOG_DEBUG(("Sign"));
 494
 495   if (key->group_order > sizeof(kbuf)) {
 496     sign_cb(FALSE, NULL, 0, context);
 497     return NULL;
 498   }
 499
 500   if (!rng) {
 501     SILC_LOG_ERROR(("DSA signing requires random number generator"));
 502     sign_cb(FALSE, NULL, 0, context);
 503     return NULL;
 504   }
 505
 506   /* Compute hash if requested */
 507   if (compute_hash) {
 508     if (!hash)
 509       hash = key->hash;
 510     silc_hash_make(hash, src, src_len, hashr);
 511     src = hashr;
 512     src_len = silc_hash_len(hash);
 513     if (src_len > key->group_order)
 514       src_len = key->group_order;
 515   }
 516
 517   stack = silc_stack_alloc(2048, silc_crypto_stack());
 518
 519   asn1 = silc_asn1_alloc(stack);
 520   if (!asn1) {
 521     silc_stack_free(stack);
 522     sign_cb(FALSE, NULL, 0, context);
 523     return NULL;
 524   }
 525
 526   silc_mp_sinit(stack, &k);
 527   silc_mp_sinit(stack, &kinv);
 528   silc_mp_sinit(stack, &r);
 529   silc_mp_sinit(stack, &s);
 530   silc_mp_sinit(stack, &tmp);
 531
 532   do {
 533     do {
 534       /* Generate random k */
 535       do {
 536         silc_rng_get_rn_data(rng, key->group_order, kbuf, sizeof(kbuf));
 537         silc_mp_bin2mp(kbuf, key->group_order, &k);
 538         silc_mp_gcd(&tmp, &k, &key->q);
 539       } while (silc_mp_cmp_ui(&tmp, 1) != 0);
 540
 541       /* Compute kinv = k^-1 mod q */
 542       silc_mp_modinv(&kinv, &k, &key->q);
 543
 544       /* Compute signature part r = g^k mod p mod q */
 545       silc_mp_pow_mod(&r, &key->g, &k, &key->p);
 546       silc_mp_mod(&r, &r, &key->q);
 547     } while (silc_mp_cmp_ui(&r, 0) == 0);
 548
 549     /* Compute signature part s = (src + x * r) / k mod q */
 550     silc_mp_bin2mp(src, src_len, &tmp);
 551     silc_mp_mul(&s, &key->x, &r);
 552     silc_mp_add(&s, &s, &tmp);
 553     silc_mp_mul(&s, &s, &kinv);
 554     silc_mp_mod(&s, &s, &key->q);
 555   } while (silc_mp_cmp_ui(&s, 0) == 0);
 556
 557   /* Encode the signature.  This format is compliant with PKIX. */
 558   memset(&sig, 0, sizeof(sig));
 559   if (!silc_asn1_encode(asn1, &sig,
 560                         SILC_ASN1_SEQUENCE,
 561                           SILC_ASN1_INT(&r),
 562                           SILC_ASN1_INT(&s),
 563                         SILC_ASN1_END, SILC_ASN1_END)) {
 564     sign_cb(FALSE, NULL, 0, context);
 565     goto out;
 566   }
 567
 568   /* Deliver result */
 569   sign_cb(TRUE, silc_buffer_data(&sig), silc_buffer_len(&sig), context);
 570
 571  out:
 572   memset(kbuf, 0, sizeof(kbuf));
 573   if (compute_hash)
 574     memset(hashr, 0, sizeof(hashr));
 575   silc_mp_uninit(&k);
 576   silc_mp_uninit(&kinv);
 577   silc_mp_uninit(&r);
 578   silc_mp_uninit(&s);
 579   silc_mp_uninit(&tmp);
 580   silc_asn1_free(asn1);
 581   silc_stack_free(stack);
 582
 583   return NULL;
 584 }
 585
 586 /* Verify */
 587
 588 SILC_PKCS_ALG_VERIFY(silc_dsa_verify)
 589 {
 590   DsaPublicKey *key = public_key;
 591   unsigned char hashr[SILC_HASH_MAXLEN];
 592   SilcBool ret = FALSE;
 593   SilcBufferStruct sig;
 594   SilcMPInt r, s, v, w, u1, u2;
 595   SilcStack stack;
 596   SilcAsn1 asn1;
 597
 598   SILC_LOG_DEBUG(("Verify"));
 599
 600   stack = silc_stack_alloc(2048, silc_crypto_stack());
 601
 602   asn1 = silc_asn1_alloc(stack);
 603   if (!asn1) {
 604     silc_stack_free(stack);
 605     verify_cb(FALSE, context);
 606     return NULL;
 607   }
 608
 609   /* Decode the signature */
 610   silc_buffer_set(&sig, signature, signature_len);
 611   if (!silc_asn1_decode(asn1, &sig,
 612                         SILC_ASN1_OPTS(SILC_ASN1_ALLOC),
 613                         SILC_ASN1_SEQUENCE,
 614                           SILC_ASN1_INT(&r),
 615                           SILC_ASN1_INT(&s),
 616                         SILC_ASN1_END, SILC_ASN1_END)) {
 617     silc_asn1_free(asn1);
 618     silc_stack_free(stack);
 619     verify_cb(FALSE, context);
 620     return NULL;
 621   }
 622
 623   if (silc_mp_cmp_ui(&r, 0) == 0 ||
 624       silc_mp_cmp_ui(&s, 0) == 0 ||
 625       silc_mp_cmp(&r, &key->q) >= 0 ||
 626       silc_mp_cmp(&s, &key->q) >= 0) {
 627     silc_asn1_free(asn1);
 628     silc_stack_free(stack);
 629     verify_cb(FALSE, context);
 630     return NULL;
 631   }
 632
 633   /* Hash data if requested */
 634   if (compute_hash) {
 635     if (!hash)
 636       hash = key->hash;
 637     silc_hash_make(hash, data, data_len, hashr);
 638     data = hashr;
 639     data_len = silc_hash_len(hash);
 640     if (data_len > key->group_order)
 641       data_len = key->group_order;
 642   }
 643
 644   silc_mp_sinit(stack, &v);
 645   silc_mp_sinit(stack, &w);
 646   silc_mp_sinit(stack, &u1);
 647   silc_mp_sinit(stack, &u2);
 648
 649   /* Compute w = s^-1 mod q */
 650   silc_mp_modinv(&w, &s, &key->q);
 651
 652   /* Compute u1 = data * w mod q */
 653   silc_mp_bin2mp(data, data_len, &u1);
 654   silc_mp_mul(&u1, &u1, &w);
 655   silc_mp_mod(&u1, &u1, &key->q);
 656
 657   /* Compute u2 = r * w mod q */
 658   silc_mp_mul(&u2, &r, &w);
 659   silc_mp_mod(&u2, &u2, &key->q);
 660
 661   /* Compute v = g ^ u1 * y ^ u2 mod p mod q */
 662   silc_mp_pow_mod(&u1, &key->g, &u1, &key->p);
 663   silc_mp_pow_mod(&u2, &key->y, &u2, &key->p);
 664   silc_mp_mul(&v, &u1, &u2);
 665   silc_mp_mod(&v, &v, &key->p);
 666   silc_mp_mod(&v, &v, &key->q);
 667
 668   /* Compare */
 669   if (silc_mp_cmp(&r, &v) == 0)
 670     ret = TRUE;
 671
 672   /* Deliver result */
 673   verify_cb(ret, context);
 674
 675   if (compute_hash)
 676     memset(hashr, 0, sizeof(hashr));
 677   silc_mp_uninit(&v);
 678   silc_mp_uninit(&w);
 679   silc_mp_uninit(&u1);
 680   silc_mp_uninit(&u2);
 681   silc_asn1_free(asn1);
 682   silc_stack_free(stack);
 683
 684   return NULL;
 685 }