schnorr.c

   1 /* $OpenBSD: schnorr.c,v 1.5 2010/12/03 23:49:26 djm Exp $ */
   2 /*
   3  * Copyright (c) 2008 Damien Miller.  All rights reserved.
   4  *
   5  * Permission to use, copy, modify, and distribute this software for any
   6  * purpose with or without fee is hereby granted, provided that the above
   7  * copyright notice and this permission notice appear in all copies.
   8  *
   9  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  10  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  11  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  12  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  13  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  14  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  15  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  16  */
  17
  18 /*
  19  * Implementation of Schnorr signatures / zero-knowledge proofs, based on
  20  * description in:
  21  *
  22  * F. Hao, P. Ryan, "Password Authenticated Key Exchange by Juggling",
  23  * 16th Workshop on Security Protocols, Cambridge, April 2008
  24  *
  25  * http://grouper.ieee.org/groups/1363/Research/contributions/hao-ryan-2008.pdf
  26  */
  27
  28 #include "includes.h"
  29
  30 #include <sys/types.h>
  31
  32 #include <string.h>
  33 #include <stdarg.h>
  34 #include <stdio.h>
  35
  36 #include <openssl/evp.h>
  37 #include <openssl/bn.h>
  38
  39 #include "xmalloc.h"
  40 #include "buffer.h"
  41 #include "log.h"
  42
  43 #include "schnorr.h"
  44
  45 #include "openbsd-compat/openssl-compat.h"
  46
  47 /* #define SCHNORR_DEBUG */             /* Privacy-violating debugging */
  48 /* #define SCHNORR_MAIN */              /* Include main() selftest */
  49
  50 #ifndef SCHNORR_DEBUG
  51 # define SCHNORR_DEBUG_BN(a)
  52 # define SCHNORR_DEBUG_BUF(a)
  53 #else
  54 # define SCHNORR_DEBUG_BN(a)    debug3_bn a
  55 # define SCHNORR_DEBUG_BUF(a)   debug3_buf a
  56 #endif /* SCHNORR_DEBUG */
  57
  58 /*
  59  * Calculate hash component of Schnorr signature H(g || g^v || g^x || id)
  60  * using the hash function defined by "evp_md". Returns signature as
  61  * bignum or NULL on error.
  62  */
  63 static BIGNUM *
  64 schnorr_hash(const BIGNUM *p, const BIGNUM *q, const BIGNUM *g,
  65     const EVP_MD *evp_md, const BIGNUM *g_v, const BIGNUM *g_x,
  66     const u_char *id, u_int idlen)
  67 {
  68         u_char *digest;
  69         u_int digest_len;
  70         BIGNUM *h;
  71         Buffer b;
  72         int success = -1;
  73
  74         if ((h = BN_new()) == NULL) {
  75                 error("%s: BN_new", __func__);
  76                 return NULL;
  77         }
  78
  79         buffer_init(&b);
  80
  81         /* h = H(g || p || q || g^v || g^x || id) */
  82         buffer_put_bignum2(&b, g);
  83         buffer_put_bignum2(&b, p);
  84         buffer_put_bignum2(&b, q);
  85         buffer_put_bignum2(&b, g_v);
  86         buffer_put_bignum2(&b, g_x);
  87         buffer_put_string(&b, id, idlen);
  88
  89         SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b),
  90             "%s: hashblob", __func__));
  91         if (hash_buffer(buffer_ptr(&b), buffer_len(&b), evp_md,
  92             &digest, &digest_len) != 0) {
  93                 error("%s: hash_buffer", __func__);
  94                 goto out;
  95         }
  96         if (BN_bin2bn(digest, (int)digest_len, h) == NULL) {
  97                 error("%s: BN_bin2bn", __func__);
  98                 goto out;
  99         }
 100         success = 0;
 101         SCHNORR_DEBUG_BN((h, "%s: h = ", __func__));
 102  out:
 103         buffer_free(&b);
 104         bzero(digest, digest_len);
 105         xfree(digest);
 106         digest_len = 0;
 107         if (success == 0)
 108                 return h;
 109         BN_clear_free(h);
 110         return NULL;
 111 }
 112
 113 /*
 114  * Generate Schnorr signature to prove knowledge of private value 'x' used
 115  * in public exponent g^x, under group defined by 'grp_p', 'grp_q' and 'grp_g'
 116  * using the hash function "evp_md".
 117  * 'idlen' bytes from 'id' will be included in the signature hash as an anti-
 118  * replay salt.
 119  *
 120  * On success, 0 is returned. The signature values are returned as *e_p
 121  * (g^v mod p) and *r_p (v - xh mod q). The caller must free these values.
 122  * On failure, -1 is returned.
 123  */
 124 int
 125 schnorr_sign(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g,
 126     const EVP_MD *evp_md, const BIGNUM *x, const BIGNUM *g_x,
 127     const u_char *id, u_int idlen, BIGNUM **r_p, BIGNUM **e_p)
 128 {
 129         int success = -1;
 130         BIGNUM *h, *tmp, *v, *g_v, *r;
 131         BN_CTX *bn_ctx;
 132
 133         SCHNORR_DEBUG_BN((x, "%s: x = ", __func__));
 134         SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__));
 135
 136         /* Avoid degenerate cases: g^0 yields a spoofable signature */
 137         if (BN_cmp(g_x, BN_value_one()) <= 0) {
 138                 error("%s: g_x < 1", __func__);
 139                 return -1;
 140         }
 141         if (BN_cmp(g_x, grp_p) >= 0) {
 142                 error("%s: g_x > g", __func__);
 143                 return -1;
 144         }
 145
 146         h = g_v = r = tmp = v = NULL;
 147         if ((bn_ctx = BN_CTX_new()) == NULL) {
 148                 error("%s: BN_CTX_new", __func__);
 149                 goto out;
 150         }
 151         if ((g_v = BN_new()) == NULL ||
 152             (r = BN_new()) == NULL ||
 153             (tmp = BN_new()) == NULL) {
 154                 error("%s: BN_new", __func__);
 155                 goto out;
 156         }
 157
 158         /*
 159          * v must be a random element of Zq, so 1 <= v < q
 160          * we also exclude v = 1, since g^1 looks dangerous
 161          */
 162         if ((v = bn_rand_range_gt_one(grp_p)) == NULL) {
 163                 error("%s: bn_rand_range2", __func__);
 164                 goto out;
 165         }
 166         SCHNORR_DEBUG_BN((v, "%s: v = ", __func__));
 167
 168         /* g_v = g^v mod p */
 169         if (BN_mod_exp(g_v, grp_g, v, grp_p, bn_ctx) == -1) {
 170                 error("%s: BN_mod_exp (g^v mod p)", __func__);
 171                 goto out;
 172         }
 173         SCHNORR_DEBUG_BN((g_v, "%s: g_v = ", __func__));
 174
 175         /* h = H(g || g^v || g^x || id) */
 176         if ((h = schnorr_hash(grp_p, grp_q, grp_g, evp_md, g_v, g_x,
 177             id, idlen)) == NULL) {
 178                 error("%s: schnorr_hash failed", __func__);
 179                 goto out;
 180         }
 181
 182         /* r = v - xh mod q */
 183         if (BN_mod_mul(tmp, x, h, grp_q, bn_ctx) == -1) {
 184                 error("%s: BN_mod_mul (tmp = xv mod q)", __func__);
 185                 goto out;
 186         }
 187         if (BN_mod_sub(r, v, tmp, grp_q, bn_ctx) == -1) {
 188                 error("%s: BN_mod_mul (r = v - tmp)", __func__);
 189                 goto out;
 190         }
 191         SCHNORR_DEBUG_BN((g_v, "%s: e = ", __func__));
 192         SCHNORR_DEBUG_BN((r, "%s: r = ", __func__));
 193
 194         *e_p = g_v;
 195         *r_p = r;
 196
 197         success = 0;
 198  out:
 199         BN_CTX_free(bn_ctx);
 200         if (h != NULL)
 201                 BN_clear_free(h);
 202         if (v != NULL)
 203                 BN_clear_free(v);
 204         BN_clear_free(tmp);
 205
 206         return success;
 207 }
 208
 209 /*
 210  * Generate Schnorr signature to prove knowledge of private value 'x' used
 211  * in public exponent g^x, under group defined by 'grp_p', 'grp_q' and 'grp_g'
 212  * using a SHA256 hash.
 213  * 'idlen' bytes from 'id' will be included in the signature hash as an anti-
 214  * replay salt.
 215  * On success, 0 is returned and *siglen bytes of signature are returned in
 216  * *sig (caller to free). Returns -1 on failure.
 217  */
 218 int
 219 schnorr_sign_buf(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g,
 220     const BIGNUM *x, const BIGNUM *g_x, const u_char *id, u_int idlen,
 221     u_char **sig, u_int *siglen)
 222 {
 223         Buffer b;
 224         BIGNUM *r, *e;
 225
 226         if (schnorr_sign(grp_p, grp_q, grp_g, EVP_sha256(),
 227             x, g_x, id, idlen, &r, &e) != 0)
 228                 return -1;
 229
 230         /* Signature is (e, r) */
 231         buffer_init(&b);
 232         /* XXX sigtype-hash as string? */
 233         buffer_put_bignum2(&b, e);
 234         buffer_put_bignum2(&b, r);
 235         *siglen = buffer_len(&b);
 236         *sig = xmalloc(*siglen);
 237         memcpy(*sig, buffer_ptr(&b), *siglen);
 238         SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b),
 239             "%s: sigblob", __func__));
 240         buffer_free(&b);
 241
 242         BN_clear_free(r);
 243         BN_clear_free(e);
 244
 245         return 0;
 246 }
 247
 248 /*
 249  * Verify Schnorr signature { r (v - xh mod q), e (g^v mod p) } against
 250  * public exponent g_x (g^x) under group defined by 'grp_p', 'grp_q' and
 251  * 'grp_g' using hash "evp_md".
 252  * Signature hash will be salted with 'idlen' bytes from 'id'.
 253  * Returns -1 on failure, 0 on incorrect signature or 1 on matching signature.
 254  */
 255 int
 256 schnorr_verify(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g,
 257     const EVP_MD *evp_md, const BIGNUM *g_x, const u_char *id, u_int idlen,
 258     const BIGNUM *r, const BIGNUM *e)
 259 {
 260         int success = -1;
 261         BIGNUM *h = NULL, *g_xh = NULL, *g_r = NULL, *gx_q = NULL;
 262         BIGNUM *expected = NULL;
 263         BN_CTX *bn_ctx;
 264
 265         SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__));
 266
 267         /* Avoid degenerate cases: g^0 yields a spoofable signature */
 268         if (BN_cmp(g_x, BN_value_one()) <= 0) {
 269                 error("%s: g_x <= 1", __func__);
 270                 return -1;
 271         }
 272         if (BN_cmp(g_x, grp_p) >= 0) {
 273                 error("%s: g_x >= p", __func__);
 274                 return -1;
 275         }
 276
 277         h = g_xh = g_r = expected = NULL;
 278         if ((bn_ctx = BN_CTX_new()) == NULL) {
 279                 error("%s: BN_CTX_new", __func__);
 280                 goto out;
 281         }
 282         if ((g_xh = BN_new()) == NULL ||
 283             (g_r = BN_new()) == NULL ||
 284             (gx_q = BN_new()) == NULL ||
 285             (expected = BN_new()) == NULL) {
 286                 error("%s: BN_new", __func__);
 287                 goto out;
 288         }
 289
 290         SCHNORR_DEBUG_BN((e, "%s: e = ", __func__));
 291         SCHNORR_DEBUG_BN((r, "%s: r = ", __func__));
 292
 293         /* gx_q = (g^x)^q must === 1 mod p */
 294         if (BN_mod_exp(gx_q, g_x, grp_q, grp_p, bn_ctx) == -1) {
 295                 error("%s: BN_mod_exp (g_x^q mod p)", __func__);
 296                 goto out;
 297         }
 298         if (BN_cmp(gx_q, BN_value_one()) != 0) {
 299                 error("%s: Invalid signature (g^x)^q != 1 mod p", __func__);
 300                 goto out;
 301         }
 302
 303         SCHNORR_DEBUG_BN((g_xh, "%s: g_xh = ", __func__));
 304         /* h = H(g || g^v || g^x || id) */
 305         if ((h = schnorr_hash(grp_p, grp_q, grp_g, evp_md, e, g_x,
 306             id, idlen)) == NULL) {
 307                 error("%s: schnorr_hash failed", __func__);
 308                 goto out;
 309         }
 310
 311         /* g_xh = (g^x)^h */
 312         if (BN_mod_exp(g_xh, g_x, h, grp_p, bn_ctx) == -1) {
 313                 error("%s: BN_mod_exp (g_x^h mod p)", __func__);
 314                 goto out;
 315         }
 316         SCHNORR_DEBUG_BN((g_xh, "%s: g_xh = ", __func__));
 317
 318         /* g_r = g^r */
 319         if (BN_mod_exp(g_r, grp_g, r, grp_p, bn_ctx) == -1) {
 320                 error("%s: BN_mod_exp (g_x^h mod p)", __func__);
 321                 goto out;
 322         }
 323         SCHNORR_DEBUG_BN((g_r, "%s: g_r = ", __func__));
 324
 325         /* expected = g^r * g_xh */
 326         if (BN_mod_mul(expected, g_r, g_xh, grp_p, bn_ctx) == -1) {
 327                 error("%s: BN_mod_mul (expected = g_r mod p)", __func__);
 328                 goto out;
 329         }
 330         SCHNORR_DEBUG_BN((expected, "%s: expected = ", __func__));
 331
 332         /* Check e == expected */
 333         success = BN_cmp(expected, e) == 0;
 334  out:
 335         BN_CTX_free(bn_ctx);
 336         if (h != NULL)
 337                 BN_clear_free(h);
 338         if (gx_q != NULL)
 339                 BN_clear_free(gx_q);
 340         if (g_xh != NULL)
 341                 BN_clear_free(g_xh);
 342         if (g_r != NULL)
 343                 BN_clear_free(g_r);
 344         if (expected != NULL)
 345                 BN_clear_free(expected);
 346         return success;
 347 }
 348
 349 /*
 350  * Verify Schnorr signature 'sig' of length 'siglen' against public exponent
 351  * g_x (g^x) under group defined by 'grp_p', 'grp_q' and 'grp_g' using a
 352  * SHA256 hash.
 353  * Signature hash will be salted with 'idlen' bytes from 'id'.
 354  * Returns -1 on failure, 0 on incorrect signature or 1 on matching signature.
 355  */
 356 int
 357 schnorr_verify_buf(const BIGNUM *grp_p, const BIGNUM *grp_q,
 358     const BIGNUM *grp_g,
 359     const BIGNUM *g_x, const u_char *id, u_int idlen,
 360     const u_char *sig, u_int siglen)
 361 {
 362         Buffer b;
 363         int ret = -1;
 364         u_int rlen;
 365         BIGNUM *r, *e;
 366
 367         e = r = NULL;
 368         if ((e = BN_new()) == NULL ||
 369             (r = BN_new()) == NULL) {
 370                 error("%s: BN_new", __func__);
 371                 goto out;
 372         }
 373
 374         /* Extract g^v and r from signature blob */
 375         buffer_init(&b);
 376         buffer_append(&b, sig, siglen);
 377         SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b),
 378             "%s: sigblob", __func__));
 379         buffer_get_bignum2(&b, e);
 380         buffer_get_bignum2(&b, r);
 381         rlen = buffer_len(&b);
 382         buffer_free(&b);
 383         if (rlen != 0) {
 384                 error("%s: remaining bytes in signature %d", __func__, rlen);
 385                 goto out;
 386         }
 387
 388         ret = schnorr_verify(grp_p, grp_q, grp_g, EVP_sha256(),
 389             g_x, id, idlen, r, e);
 390  out:
 391         BN_clear_free(e);
 392         BN_clear_free(r);
 393
 394         return ret;
 395 }
 396
 397 /* Helper functions */
 398
 399 /*
 400  * Generate uniformly distributed random number in range (1, high).
 401  * Return number on success, NULL on failure.
 402  */
 403 BIGNUM *
 404 bn_rand_range_gt_one(const BIGNUM *high)
 405 {
 406         BIGNUM *r, *tmp;
 407         int success = -1;
 408
 409         if ((tmp = BN_new()) == NULL) {
 410                 error("%s: BN_new", __func__);
 411                 return NULL;
 412         }
 413         if ((r = BN_new()) == NULL) {
 414                 error("%s: BN_new failed", __func__);
 415                 goto out;
 416         }
 417         if (BN_set_word(tmp, 2) != 1) {
 418                 error("%s: BN_set_word(tmp, 2)", __func__);
 419                 goto out;
 420         }
 421         if (BN_sub(tmp, high, tmp) == -1) {
 422                 error("%s: BN_sub failed (tmp = high - 2)", __func__);
 423                 goto out;
 424         }
 425         if (BN_rand_range(r, tmp) == -1) {
 426                 error("%s: BN_rand_range failed", __func__);
 427                 goto out;
 428         }
 429         if (BN_set_word(tmp, 2) != 1) {
 430                 error("%s: BN_set_word(tmp, 2)", __func__);
 431                 goto out;
 432         }
 433         if (BN_add(r, r, tmp) == -1) {
 434                 error("%s: BN_add failed (r = r + 2)", __func__);
 435                 goto out;
 436         }
 437         success = 0;
 438  out:
 439         BN_clear_free(tmp);
 440         if (success == 0)
 441                 return r;
 442         BN_clear_free(r);
 443         return NULL;
 444 }
 445
 446 /*
 447  * Hash contents of buffer 'b' with hash 'md'. Returns 0 on success,
 448  * with digest via 'digestp' (caller to free) and length via 'lenp'.
 449  * Returns -1 on failure.
 450  */
 451 int
 452 hash_buffer(const u_char *buf, u_int len, const EVP_MD *md,
 453     u_char **digestp, u_int *lenp)
 454 {
 455         u_char digest[EVP_MAX_MD_SIZE];
 456         u_int digest_len;
 457         EVP_MD_CTX evp_md_ctx;
 458         int success = -1;
 459
 460         EVP_MD_CTX_init(&evp_md_ctx);
 461
 462         if (EVP_DigestInit_ex(&evp_md_ctx, md, NULL) != 1) {
 463                 error("%s: EVP_DigestInit_ex", __func__);
 464                 goto out;
 465         }
 466         if (EVP_DigestUpdate(&evp_md_ctx, buf, len) != 1) {
 467                 error("%s: EVP_DigestUpdate", __func__);
 468                 goto out;
 469         }
 470         if (EVP_DigestFinal_ex(&evp_md_ctx, digest, &digest_len) != 1) {
 471                 error("%s: EVP_DigestFinal_ex", __func__);
 472                 goto out;
 473         }
 474         *digestp = xmalloc(digest_len);
 475         *lenp = digest_len;
 476         memcpy(*digestp, digest, *lenp);
 477         success = 0;
 478  out:
 479         EVP_MD_CTX_cleanup(&evp_md_ctx);
 480         bzero(digest, sizeof(digest));
 481         digest_len = 0;
 482         return success;
 483 }
 484
 485 /* print formatted string followed by bignum */
 486 void
 487 debug3_bn(const BIGNUM *n, const char *fmt, ...)
 488 {
 489         char *out, *h;
 490         va_list args;
 491
 492         out = NULL;
 493         va_start(args, fmt);
 494         vasprintf(&out, fmt, args);
 495         va_end(args);
 496         if (out == NULL)
 497                 fatal("%s: vasprintf failed", __func__);
 498
 499         if (n == NULL)
 500                 debug3("%s(null)", out);
 501         else {
 502                 h = BN_bn2hex(n);
 503                 debug3("%s0x%s", out, h);
 504                 free(h);
 505         }
 506         free(out);
 507 }
 508
 509 /* print formatted string followed by buffer contents in hex */
 510 void
 511 debug3_buf(const u_char *buf, u_int len, const char *fmt, ...)
 512 {
 513         char *out, h[65];
 514         u_int i, j;
 515         va_list args;
 516
 517         out = NULL;
 518         va_start(args, fmt);
 519         vasprintf(&out, fmt, args);
 520         va_end(args);
 521         if (out == NULL)
 522                 fatal("%s: vasprintf failed", __func__);
 523
 524         debug3("%s length %u%s", out, len, buf == NULL ? " (null)" : "");
 525         free(out);
 526         if (buf == NULL)
 527                 return;
 528
 529         *h = '\0';
 530         for (i = j = 0; i < len; i++) {
 531                 snprintf(h + j, sizeof(h) - j, "%02x", buf[i]);
 532                 j += 2;
 533                 if (j >= sizeof(h) - 1 || i == len - 1) {
 534                         debug3("    %s", h);
 535                         *h = '\0';
 536                         j = 0;
 537                 }
 538         }
 539 }
 540
 541 /*
 542  * Construct a MODP group from hex strings p (which must be a safe
 543  * prime) and g, automatically calculating subgroup q as (p / 2)
 544  */
 545 struct modp_group *
 546 modp_group_from_g_and_safe_p(const char *grp_g, const char *grp_p)
 547 {
 548         struct modp_group *ret;
 549
 550         ret = xmalloc(sizeof(*ret));
 551         ret->p = ret->q = ret->g = NULL;
 552         if (BN_hex2bn(&ret->p, grp_p) == 0 ||
 553             BN_hex2bn(&ret->g, grp_g) == 0)
 554                 fatal("%s: BN_hex2bn", __func__);
 555         /* Subgroup order is p/2 (p is a safe prime) */
 556         if ((ret->q = BN_new()) == NULL)
 557                 fatal("%s: BN_new", __func__);
 558         if (BN_rshift1(ret->q, ret->p) != 1)
 559                 fatal("%s: BN_rshift1", __func__);
 560
 561         return ret;
 562 }
 563
 564 void
 565 modp_group_free(struct modp_group *grp)
 566 {
 567         if (grp->g != NULL)
 568                 BN_clear_free(grp->g);
 569         if (grp->p != NULL)
 570                 BN_clear_free(grp->p);
 571         if (grp->q != NULL)
 572                 BN_clear_free(grp->q);
 573         bzero(grp, sizeof(*grp));
 574         xfree(grp);
 575 }
 576
 577 /* main() function for self-test */
 578
 579 #ifdef SCHNORR_MAIN
 580 static void
 581 schnorr_selftest_one(const BIGNUM *grp_p, const BIGNUM *grp_q,
 582     const BIGNUM *grp_g, const BIGNUM *x)
 583 {
 584         BIGNUM *g_x;
 585         u_char *sig;
 586         u_int siglen;
 587         BN_CTX *bn_ctx;
 588
 589         if ((bn_ctx = BN_CTX_new()) == NULL)
 590                 fatal("%s: BN_CTX_new", __func__);
 591         if ((g_x = BN_new()) == NULL)
 592                 fatal("%s: BN_new", __func__);
 593
 594         if (BN_mod_exp(g_x, grp_g, x, grp_p, bn_ctx) == -1)
 595                 fatal("%s: g_x", __func__);
 596         if (schnorr_sign_buf(grp_p, grp_q, grp_g, x, g_x, "junk", 4,
 597             &sig, &siglen))
 598                 fatal("%s: schnorr_sign", __func__);
 599         if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "junk", 4,
 600             sig, siglen) != 1)
 601                 fatal("%s: verify fail", __func__);
 602         if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "JUNK", 4,
 603             sig, siglen) != 0)
 604                 fatal("%s: verify should have failed (bad ID)", __func__);
 605         sig[4] ^= 1;
 606         if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "junk", 4,
 607             sig, siglen) != 0)
 608                 fatal("%s: verify should have failed (bit error)", __func__);
 609         xfree(sig);
 610         BN_free(g_x);
 611         BN_CTX_free(bn_ctx);
 612 }
 613
 614 static void
 615 schnorr_selftest(void)
 616 {
 617         BIGNUM *x;
 618         struct modp_group *grp;
 619         u_int i;
 620         char *hh;
 621
 622         grp = jpake_default_group();
 623         if ((x = BN_new()) == NULL)
 624                 fatal("%s: BN_new", __func__);
 625         SCHNORR_DEBUG_BN((grp->p, "%s: grp->p = ", __func__));
 626         SCHNORR_DEBUG_BN((grp->q, "%s: grp->q = ", __func__));
 627         SCHNORR_DEBUG_BN((grp->g, "%s: grp->g = ", __func__));
 628
 629         /* [1, 20) */
 630         for (i = 1; i < 20; i++) {
 631                 printf("x = %u\n", i);
 632                 fflush(stdout);
 633                 if (BN_set_word(x, i) != 1)
 634                         fatal("%s: set x word", __func__);
 635                 schnorr_selftest_one(grp->p, grp->q, grp->g, x);
 636         }
 637
 638         /* 100 x random [0, p) */
 639         for (i = 0; i < 100; i++) {
 640                 if (BN_rand_range(x, grp->p) != 1)
 641                         fatal("%s: BN_rand_range", __func__);
 642                 hh = BN_bn2hex(x);
 643                 printf("x = (random) 0x%s\n", hh);
 644                 free(hh);
 645                 fflush(stdout);
 646                 schnorr_selftest_one(grp->p, grp->q, grp->g, x);
 647         }
 648
 649         /* [q-20, q) */
 650         if (BN_set_word(x, 20) != 1)
 651                 fatal("%s: BN_set_word (x = 20)", __func__);
 652         if (BN_sub(x, grp->q, x) != 1)
 653                 fatal("%s: BN_sub (q - x)", __func__);
 654         for (i = 0; i < 19; i++) {
 655                 hh = BN_bn2hex(x);
 656                 printf("x = (q - %d) 0x%s\n", 20 - i, hh);
 657                 free(hh);
 658                 fflush(stdout);
 659                 schnorr_selftest_one(grp->p, grp->q, grp->g, x);
 660                 if (BN_add(x, x, BN_value_one()) != 1)
 661                         fatal("%s: BN_add (x + 1)", __func__);
 662         }
 663         BN_free(x);
 664 }
 665
 666 int
 667 main(int argc, char **argv)
 668 {
 669         log_init(argv[0], SYSLOG_LEVEL_DEBUG3, SYSLOG_FACILITY_USER, 1);
 670
 671         schnorr_selftest();
 672         return 0;
 673 }
 674 #endif
 675