crypto/openssh/schnorr.c

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