[openssh.git] / schnorr.c

/* $OpenBSD: schnorr.c,v 1.3 2009/03/05 07:18:19 djm Exp $ */
/*
 * Copyright (c) 2008 Damien Miller.  All rights reserved.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

/*
 * Implementation of Schnorr signatures / zero-knowledge proofs, based on
 * description in:
 * 	
 * F. Hao, P. Ryan, "Password Authenticated Key Exchange by Juggling",
 * 16th Workshop on Security Protocols, Cambridge, April 2008
 *
 * http://grouper.ieee.org/groups/1363/Research/contributions/hao-ryan-2008.pdf
 */

#include "includes.h"

#include <sys/types.h>

#include <string.h>
#include <stdarg.h>
#include <stdio.h>

#include <openssl/evp.h>
#include <openssl/bn.h>

#include "xmalloc.h"
#include "buffer.h"
#include "log.h"

#include "schnorr.h"

#include "openbsd-compat/openssl-compat.h"

/* #define SCHNORR_DEBUG */		/* Privacy-violating debugging */
/* #define SCHNORR_MAIN */		/* Include main() selftest */

#ifndef SCHNORR_DEBUG
# define SCHNORR_DEBUG_BN(a)
# define SCHNORR_DEBUG_BUF(a)
#else
# define SCHNORR_DEBUG_BN(a)	debug3_bn a
# define SCHNORR_DEBUG_BUF(a)	debug3_buf a
#endif /* SCHNORR_DEBUG */

/*
 * Calculate hash component of Schnorr signature H(g || g^v || g^x || id)
 * using the hash function defined by "evp_md". Returns signature as
 * bignum or NULL on error.
 */
static BIGNUM *
schnorr_hash(const BIGNUM *p, const BIGNUM *q, const BIGNUM *g,
    const EVP_MD *evp_md, const BIGNUM *g_v, const BIGNUM *g_x,
    const u_char *id, u_int idlen)
{
	u_char *digest;
	u_int digest_len;
	BIGNUM *h;
	Buffer b;
	int success = -1;

	if ((h = BN_new()) == NULL) {
		error("%s: BN_new", __func__);
		return NULL;
	}

	buffer_init(&b);

	/* h = H(g || p || q || g^v || g^x || id) */
	buffer_put_bignum2(&b, g);
	buffer_put_bignum2(&b, p);
	buffer_put_bignum2(&b, q);
	buffer_put_bignum2(&b, g_v);
	buffer_put_bignum2(&b, g_x);
	buffer_put_string(&b, id, idlen);

	SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b),
	    "%s: hashblob", __func__));
	if (hash_buffer(buffer_ptr(&b), buffer_len(&b), evp_md,
	    &digest, &digest_len) != 0) {
		error("%s: hash_buffer", __func__);
		goto out;
	}
	if (BN_bin2bn(digest, (int)digest_len, h) == NULL) {
		error("%s: BN_bin2bn", __func__);
		goto out;
	}
	success = 0;
	SCHNORR_DEBUG_BN((h, "%s: h = ", __func__));
 out:
	buffer_free(&b);
	bzero(digest, digest_len);
	xfree(digest);
	digest_len = 0;
	if (success == 0)
		return h;
	BN_clear_free(h);
	return NULL;
}

/*
 * Generate Schnorr signature to prove knowledge of private value 'x' used
 * in public exponent g^x, under group defined by 'grp_p', 'grp_q' and 'grp_g'
 * using the hash function "evp_md".
 * 'idlen' bytes from 'id' will be included in the signature hash as an anti-
 * replay salt.
 * 
 * On success, 0 is returned. The signature values are returned as *e_p
 * (g^v mod p) and *r_p (v - xh mod q). The caller must free these values.
 * On failure, -1 is returned.
 */
int
schnorr_sign(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g,
    const EVP_MD *evp_md, const BIGNUM *x, const BIGNUM *g_x,
    const u_char *id, u_int idlen, BIGNUM **r_p, BIGNUM **e_p)
{
	int success = -1;
	BIGNUM *h, *tmp, *v, *g_v, *r;
	BN_CTX *bn_ctx;

	SCHNORR_DEBUG_BN((x, "%s: x = ", __func__));
	SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__));

	/* Avoid degenerate cases: g^0 yields a spoofable signature */
	if (BN_cmp(g_x, BN_value_one()) <= 0) {
		error("%s: g_x < 1", __func__);
		return -1;
	}

	h = g_v = r = tmp = v = NULL;
	if ((bn_ctx = BN_CTX_new()) == NULL) {
		error("%s: BN_CTX_new", __func__);
		goto out;
	}
	if ((g_v = BN_new()) == NULL ||
	    (r = BN_new()) == NULL ||
	    (tmp = BN_new()) == NULL) {
		error("%s: BN_new", __func__);
		goto out;
	}

	/*
	 * v must be a random element of Zq, so 1 <= v < q
	 * we also exclude v = 1, since g^1 looks dangerous
	 */
	if ((v = bn_rand_range_gt_one(grp_p)) == NULL) {
		error("%s: bn_rand_range2", __func__);
		goto out;
	}
	SCHNORR_DEBUG_BN((v, "%s: v = ", __func__));

	/* g_v = g^v mod p */
	if (BN_mod_exp(g_v, grp_g, v, grp_p, bn_ctx) == -1) {
		error("%s: BN_mod_exp (g^v mod p)", __func__);
		goto out;
	}
	SCHNORR_DEBUG_BN((g_v, "%s: g_v = ", __func__));

	/* h = H(g || g^v || g^x || id) */
	if ((h = schnorr_hash(grp_p, grp_q, grp_g, evp_md, g_v, g_x,
	    id, idlen)) == NULL) {
		error("%s: schnorr_hash failed", __func__);
		goto out;
	}

	/* r = v - xh mod q */
	if (BN_mod_mul(tmp, x, h, grp_q, bn_ctx) == -1) {
		error("%s: BN_mod_mul (tmp = xv mod q)", __func__);
		goto out;
	}
	if (BN_mod_sub(r, v, tmp, grp_q, bn_ctx) == -1) {
		error("%s: BN_mod_mul (r = v - tmp)", __func__);
		goto out;
	}
	SCHNORR_DEBUG_BN((g_v, "%s: e = ", __func__));
	SCHNORR_DEBUG_BN((r, "%s: r = ", __func__));

	*e_p = g_v;
	*r_p = r;

	success = 0;
 out:
	BN_CTX_free(bn_ctx);
	if (h != NULL)
		BN_clear_free(h);
	if (v != NULL)
		BN_clear_free(v);
	BN_clear_free(tmp);

	return success;
}

/*
 * Generate Schnorr signature to prove knowledge of private value 'x' used
 * in public exponent g^x, under group defined by 'grp_p', 'grp_q' and 'grp_g'
 * using a SHA256 hash.
 * 'idlen' bytes from 'id' will be included in the signature hash as an anti-
 * replay salt.
 * On success, 0 is returned and *siglen bytes of signature are returned in
 * *sig (caller to free). Returns -1 on failure.
 */
int
schnorr_sign_buf(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g,
    const BIGNUM *x, const BIGNUM *g_x, const u_char *id, u_int idlen,
    u_char **sig, u_int *siglen)
{
	Buffer b;
	BIGNUM *r, *e;

	if (schnorr_sign(grp_p, grp_q, grp_g, EVP_sha256(),
	    x, g_x, id, idlen, &r, &e) != 0)
		return -1;

	/* Signature is (e, r) */
	buffer_init(&b);
	/* XXX sigtype-hash as string? */
	buffer_put_bignum2(&b, e);
	buffer_put_bignum2(&b, r);
	*siglen = buffer_len(&b);
	*sig = xmalloc(*siglen);
	memcpy(*sig, buffer_ptr(&b), *siglen);
	SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b),
	    "%s: sigblob", __func__));
	buffer_free(&b);

	BN_clear_free(r);
	BN_clear_free(e);

	return 0;
}

/*
 * Verify Schnorr signature { r (v - xh mod q), e (g^v mod p) } against
 * public exponent g_x (g^x) under group defined by 'grp_p', 'grp_q' and
 * 'grp_g' using hash "evp_md".
 * Signature hash will be salted with 'idlen' bytes from 'id'.
 * Returns -1 on failure, 0 on incorrect signature or 1 on matching signature.
 */
int
schnorr_verify(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g,
    const EVP_MD *evp_md, const BIGNUM *g_x, const u_char *id, u_int idlen,
    const BIGNUM *r, const BIGNUM *e)
{
	int success = -1;
	BIGNUM *h, *g_xh, *g_r, *expected;
	BN_CTX *bn_ctx;

	SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__));

	/* Avoid degenerate cases: g^0 yields a spoofable signature */
	if (BN_cmp(g_x, BN_value_one()) <= 0) {
		error("%s: g_x < 1", __func__);
		return -1;
	}

	h = g_xh = g_r = expected = NULL;
	if ((bn_ctx = BN_CTX_new()) == NULL) {
		error("%s: BN_CTX_new", __func__);
		goto out;
	}
	if ((g_xh = BN_new()) == NULL ||
	    (g_r = BN_new()) == NULL ||
	    (expected = BN_new()) == NULL) {
		error("%s: BN_new", __func__);
		goto out;
	}

	SCHNORR_DEBUG_BN((e, "%s: e = ", __func__));
	SCHNORR_DEBUG_BN((r, "%s: r = ", __func__));

	/* h = H(g || g^v || g^x || id) */
	if ((h = schnorr_hash(grp_p, grp_q, grp_g, evp_md, e, g_x,
	    id, idlen)) == NULL) {
		error("%s: schnorr_hash failed", __func__);
		goto out;
	}

	/* g_xh = (g^x)^h */
	if (BN_mod_exp(g_xh, g_x, h, grp_p, bn_ctx) == -1) {
		error("%s: BN_mod_exp (g_x^h mod p)", __func__);
		goto out;
	}
	SCHNORR_DEBUG_BN((g_xh, "%s: g_xh = ", __func__));

	/* g_r = g^r */
	if (BN_mod_exp(g_r, grp_g, r, grp_p, bn_ctx) == -1) {
		error("%s: BN_mod_exp (g_x^h mod p)", __func__);
		goto out;
	}
	SCHNORR_DEBUG_BN((g_r, "%s: g_r = ", __func__));

	/* expected = g^r * g_xh */
	if (BN_mod_mul(expected, g_r, g_xh, grp_p, bn_ctx) == -1) {
		error("%s: BN_mod_mul (expected = g_r mod p)", __func__);
		goto out;
	}
	SCHNORR_DEBUG_BN((expected, "%s: expected = ", __func__));

	/* Check e == expected */
	success = BN_cmp(expected, e) == 0;
 out:
	BN_CTX_free(bn_ctx);
	if (h != NULL)
		BN_clear_free(h);
	BN_clear_free(g_xh);
	BN_clear_free(g_r);
	BN_clear_free(expected);
	return success;
}

/*
 * Verify Schnorr signature 'sig' of length 'siglen' against public exponent
 * g_x (g^x) under group defined by 'grp_p', 'grp_q' and 'grp_g' using a
 * SHA256 hash.
 * Signature hash will be salted with 'idlen' bytes from 'id'.
 * Returns -1 on failure, 0 on incorrect signature or 1 on matching signature.
 */
int
schnorr_verify_buf(const BIGNUM *grp_p, const BIGNUM *grp_q,
    const BIGNUM *grp_g,
    const BIGNUM *g_x, const u_char *id, u_int idlen,
    const u_char *sig, u_int siglen)
{
	Buffer b;
	int ret = -1;
	u_int rlen;
	BIGNUM *r, *e;

	e = r = NULL;
	if ((e = BN_new()) == NULL ||
	    (r = BN_new()) == NULL) {
		error("%s: BN_new", __func__);
		goto out;
	}

	/* Extract g^v and r from signature blob */
	buffer_init(&b);
	buffer_append(&b, sig, siglen);
	SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b),
	    "%s: sigblob", __func__));
	buffer_get_bignum2(&b, e);
	buffer_get_bignum2(&b, r);
	rlen = buffer_len(&b);
	buffer_free(&b);
	if (rlen != 0) {
		error("%s: remaining bytes in signature %d", __func__, rlen);
		goto out;
	}

	ret = schnorr_verify(grp_p, grp_q, grp_g, EVP_sha256(),
	    g_x, id, idlen, r, e);
 out:
	BN_clear_free(e);
	BN_clear_free(r);

	return ret;
}

/* Helper functions */

/*
 * Generate uniformly distributed random number in range (1, high).
 * Return number on success, NULL on failure.
 */
BIGNUM *
bn_rand_range_gt_one(const BIGNUM *high)
{
	BIGNUM *r, *tmp;
	int success = -1;

	if ((tmp = BN_new()) == NULL) {
		error("%s: BN_new", __func__);
		return NULL;
	}
	if ((r = BN_new()) == NULL) {
		error("%s: BN_new failed", __func__);
		goto out;
	}
	if (BN_set_word(tmp, 2) != 1) {
		error("%s: BN_set_word(tmp, 2)", __func__);
		goto out;
	}
	if (BN_sub(tmp, high, tmp) == -1) {
		error("%s: BN_sub failed (tmp = high - 2)", __func__);
		goto out;
	}
	if (BN_rand_range(r, tmp) == -1) {
		error("%s: BN_rand_range failed", __func__);
		goto out;
	}
	if (BN_set_word(tmp, 2) != 1) {
		error("%s: BN_set_word(tmp, 2)", __func__);
		goto out;
	}
	if (BN_add(r, r, tmp) == -1) {
		error("%s: BN_add failed (r = r + 2)", __func__);
		goto out;
	}
	success = 0;
 out:
	BN_clear_free(tmp);
	if (success == 0)
		return r;
	BN_clear_free(r);
	return NULL;
}

/*
 * Hash contents of buffer 'b' with hash 'md'. Returns 0 on success,
 * with digest via 'digestp' (caller to free) and length via 'lenp'.
 * Returns -1 on failure.
 */
int
hash_buffer(const u_char *buf, u_int len, const EVP_MD *md,
    u_char **digestp, u_int *lenp)
{
	u_char digest[EVP_MAX_MD_SIZE];
	u_int digest_len;
	EVP_MD_CTX evp_md_ctx;
	int success = -1;

	EVP_MD_CTX_init(&evp_md_ctx);

	if (EVP_DigestInit_ex(&evp_md_ctx, md, NULL) != 1) {
		error("%s: EVP_DigestInit_ex", __func__);
		goto out;
	}
	if (EVP_DigestUpdate(&evp_md_ctx, buf, len) != 1) {
		error("%s: EVP_DigestUpdate", __func__);
		goto out;
	}
	if (EVP_DigestFinal_ex(&evp_md_ctx, digest, &digest_len) != 1) {
		error("%s: EVP_DigestFinal_ex", __func__);
		goto out;
	}
	*digestp = xmalloc(digest_len);
	*lenp = digest_len;
	memcpy(*digestp, digest, *lenp);
	success = 0;
 out:
	EVP_MD_CTX_cleanup(&evp_md_ctx);
	bzero(digest, sizeof(digest));
	digest_len = 0;
	return success;
}

/* print formatted string followed by bignum */
void
debug3_bn(const BIGNUM *n, const char *fmt, ...)
{
	char *out, *h;
	va_list args;

	out = NULL;
	va_start(args, fmt);
	vasprintf(&out, fmt, args);
	va_end(args);
	if (out == NULL)
		fatal("%s: vasprintf failed", __func__);

	if (n == NULL)
		debug3("%s(null)", out);
	else {
		h = BN_bn2hex(n);
		debug3("%s0x%s", out, h);
		free(h);
	}
	free(out);
}

/* print formatted string followed by buffer contents in hex */
void
debug3_buf(const u_char *buf, u_int len, const char *fmt, ...)
{
	char *out, h[65];
	u_int i, j;
	va_list args;

	out = NULL;
	va_start(args, fmt);
	vasprintf(&out, fmt, args);
	va_end(args);
	if (out == NULL)
		fatal("%s: vasprintf failed", __func__);

	debug3("%s length %u%s", out, len, buf == NULL ? " (null)" : "");
	free(out);
	if (buf == NULL)
		return;

	*h = '\0';
	for (i = j = 0; i < len; i++) {
		snprintf(h + j, sizeof(h) - j, "%02x", buf[i]);
		j += 2;
		if (j >= sizeof(h) - 1 || i == len - 1) {
			debug3("    %s", h);
			*h = '\0';
			j = 0;
		}
	}
}

/*
 * Construct a MODP group from hex strings p (which must be a safe
 * prime) and g, automatically calculating subgroup q as (p / 2)
 */
struct modp_group *
modp_group_from_g_and_safe_p(const char *grp_g, const char *grp_p)
{
	struct modp_group *ret;

	ret = xmalloc(sizeof(*ret));
	ret->p = ret->q = ret->g = NULL;
	if (BN_hex2bn(&ret->p, grp_p) == 0 ||
	    BN_hex2bn(&ret->g, grp_g) == 0)
		fatal("%s: BN_hex2bn", __func__);
	/* Subgroup order is p/2 (p is a safe prime) */
	if ((ret->q = BN_new()) == NULL)
		fatal("%s: BN_new", __func__);
	if (BN_rshift1(ret->q, ret->p) != 1)
		fatal("%s: BN_rshift1", __func__);

	return ret;
}

void
modp_group_free(struct modp_group *grp)
{
	if (grp->g != NULL)
		BN_clear_free(grp->g);
	if (grp->p != NULL)
		BN_clear_free(grp->p);
	if (grp->q != NULL)
		BN_clear_free(grp->q);
	bzero(grp, sizeof(*grp));
	xfree(grp);
}

/* main() function for self-test */

#ifdef SCHNORR_MAIN
static void
schnorr_selftest_one(const BIGNUM *grp_p, const BIGNUM *grp_q,
    const BIGNUM *grp_g, const BIGNUM *x)
{
	BIGNUM *g_x;
	u_char *sig;
	u_int siglen;
	BN_CTX *bn_ctx;

	if ((bn_ctx = BN_CTX_new()) == NULL)
		fatal("%s: BN_CTX_new", __func__);
	if ((g_x = BN_new()) == NULL)
		fatal("%s: BN_new", __func__);

	if (BN_mod_exp(g_x, grp_g, x, grp_p, bn_ctx) == -1)
		fatal("%s: g_x", __func__);
	if (schnorr_sign_buf(grp_p, grp_q, grp_g, x, g_x, "junk", 4,
	    &sig, &siglen))
		fatal("%s: schnorr_sign", __func__);
	if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "junk", 4,
	    sig, siglen) != 1)
		fatal("%s: verify fail", __func__);
	if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "JUNK", 4,
	    sig, siglen) != 0)
		fatal("%s: verify should have failed (bad ID)", __func__);
	sig[4] ^= 1;
	if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "junk", 4,
	    sig, siglen) != 0)
		fatal("%s: verify should have failed (bit error)", __func__);
	xfree(sig);
	BN_free(g_x);
	BN_CTX_free(bn_ctx);
}

static void
schnorr_selftest(void)
{
	BIGNUM *x;
	struct modp_group *grp;
	u_int i;
	char *hh;

	grp = jpake_default_group();
	if ((x = BN_new()) == NULL)
		fatal("%s: BN_new", __func__);
	SCHNORR_DEBUG_BN((grp->p, "%s: grp->p = ", __func__));
	SCHNORR_DEBUG_BN((grp->q, "%s: grp->q = ", __func__));
	SCHNORR_DEBUG_BN((grp->g, "%s: grp->g = ", __func__));

	/* [1, 20) */
	for (i = 1; i < 20; i++) {
		printf("x = %u\n", i);
		fflush(stdout);
		if (BN_set_word(x, i) != 1)
			fatal("%s: set x word", __func__);
		schnorr_selftest_one(grp->p, grp->q, grp->g, x);
	}

	/* 100 x random [0, p) */
	for (i = 0; i < 100; i++) {
		if (BN_rand_range(x, grp->p) != 1)
			fatal("%s: BN_rand_range", __func__);
		hh = BN_bn2hex(x);
		printf("x = (random) 0x%s\n", hh);
		free(hh);
		fflush(stdout);
		schnorr_selftest_one(grp->p, grp->q, grp->g, x);
	}

	/* [q-20, q) */
	if (BN_set_word(x, 20) != 1)
		fatal("%s: BN_set_word (x = 20)", __func__);
	if (BN_sub(x, grp->q, x) != 1)
		fatal("%s: BN_sub (q - x)", __func__);
	for (i = 0; i < 19; i++) {
		hh = BN_bn2hex(x);
		printf("x = (q - %d) 0x%s\n", 20 - i, hh);
		free(hh);
		fflush(stdout);
		schnorr_selftest_one(grp->p, grp->q, grp->g, x);
		if (BN_add(x, x, BN_value_one()) != 1)
			fatal("%s: BN_add (x + 1)", __func__);
	}
	BN_free(x);
}

int
main(int argc, char **argv)
{
	log_init(argv[0], SYSLOG_LEVEL_DEBUG3, SYSLOG_FACILITY_USER, 1);

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