schnorr.c

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