crypto/openssh/schnorr.c

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