diff options
author | W. Kosior <koszko@koszko.org> | 2025-01-24 13:11:01 +0100 |
---|---|---|
committer | W. Kosior <koszko@koszko.org> | 2025-01-25 19:13:14 +0100 |
commit | b17ec0d059d0b27858d0a68dcea62a313417ca1e (patch) | |
tree | 7273fda4ff2dbcd6097ca50111eeb1b9410de50f | |
parent | b6411343c8d53e2bbbece10067f02f0e3e3bc8f1 (diff) | |
download | pq-blind-sigs-impl-b17ec0d059d0b27858d0a68dcea62a313417ca1e.tar.gz pq-blind-sigs-impl-b17ec0d059d0b27858d0a68dcea62a313417ca1e.zip |
Implement the signing protocol.
-rw-r--r-- | Makefile | 31 | ||||
-rw-r--r-- | README.md | 56 | ||||
-rwxr-xr-x | dev-shell | 2 | ||||
-rw-r--r-- | poly_mul.c | 301 | ||||
-rw-r--r-- | pqcrypto_bitcnt_bytes.h | 14 | ||||
-rw-r--r-- | pqcrypto_blind_sig.c | 1123 | ||||
-rw-r--r-- | pqcrypto_blind_sig.h | 253 | ||||
-rw-r--r-- | pqcrypto_blind_sig_example.c | 144 | ||||
-rw-r--r-- | pqcrypto_blind_sig_serializable.c | 57 | ||||
-rw-r--r-- | pqcrypto_commitment_shake256.c | 30 | ||||
-rw-r--r-- | pqcrypto_commitment_shake256.h | 10 | ||||
-rw-r--r-- | pqcrypto_hash.h | 21 | ||||
-rw-r--r-- | pqcrypto_hash_shake256.c | 72 | ||||
-rw-r--r-- | pqcrypto_hash_shake256.h | 16 | ||||
-rw-r--r-- | pqcrypto_poly.c | 236 | ||||
-rw-r--r-- | pqcrypto_poly.h | 110 | ||||
-rw-r--r-- | pqcrypto_poly_example.c | 167 | ||||
-rw-r--r-- | pqcrypto_prng.h | 14 | ||||
-rw-r--r-- | pqcrypto_prng_getrandom.c | 19 | ||||
-rw-r--r-- | pqcrypto_prng_getrandom.h | 14 | ||||
-rw-r--r-- | pqcrypto_prng_seeded.c | 41 | ||||
-rw-r--r-- | pqcrypto_prng_seeded.h | 27 |
22 files changed, 2448 insertions, 310 deletions
@@ -1,16 +1,35 @@ # SPDX-License-Identifier: CC0-1.0 # -# Copyright (C) 2024 W. Kosior <koszko@koszko.org> +# Copyright (C) 2024, 2025 W. Kosior <koszko@koszko.org> CC = gcc -CFLAGS = -std=c11 -Wall -Wextra -Werror +CFLAGS = -std=c11 -Wall -Wextra -Werror -O2 $(CFLAGS_EXTRA) +LDLIBS = -lflint -lgcrypt -lgmp -poly_mul: poly_mul.o - $(CC) -lflint -lgmp -o $@ $^ +PROGRAMS = poly_example blind_sig_example + +all: $(PROGRAMS) + +poly_example: pqcrypto_poly.o pqcrypto_poly_example.o pqcrypto_prng_getrandom.o + $(CC) $(LDLIBS) -o $@ $^ + +blind_sig_example: pqcrypto_blind_sig.o pqcrypto_blind_sig_example.o \ + pqcrypto_commitment_shake256.o pqcrypto_hash_shake256.o \ + pqcrypto_poly.o pqcrypto_prng_getrandom.o \ + pqcrypto_prng_seeded.o + $(CC) $(LDLIBS) -o $@ $^ # For fans of old librebooted ThinkPads — the FLINT build in some distros (at # least Guix) uses processor instructions not available in old Core 2 Duo # processors… For mere testing it is enough tu run with QEMU emulation, tho. -run_poly_mul: poly_mul + +run_poly_example: poly_example guix shell qemu -- qemu-x86_64 -cpu max $< -.PHONY: run_poly_mul +.PHONY: run_poly_example + +run_blind_sig_example: blind_sig_example + guix shell qemu -- qemu-x86_64 -cpu max $< +.PHONY: run_blind_sig_example + +clean: + rm -rf *.o $(PROGRAMS) @@ -9,8 +9,60 @@ multiplication). Also, there are possibly better BS algorithms by now. ## How it works -Well, the actual program is not there yet. There's just some code to facilitate -polynomial multiplication in a ring modulo X^m+1 over a modulo field with +A simple program that signs something in memory (while printing some diagnostic +messages) and discards the result can be invoke like this. + +``` +$ make run_blind_sig_example +guix shell qemu -- qemu-x86_64 -cpu max blind_sig_example +Preparing blind signature context ("Current III" set from Rückert's paper). +n = 1024 +d_s = 283 +m = 9 +phi = 4 +psi = 1 +d_alpha = 1024 +d_epsilon_star = 1023 +d_y = 10928598810624 +d_g_star = 10928302353408 +d_beta = 402860937956032512 +d_g = 402850009653679104 +q = 1208925819614629174706189 +Making a test signature for ASCII buffer: "This is a message to blind-sign.". +User retries with new alpha. +User retries with new alpha. +User retries with new alpha. +User successfully obtained signature. +Signer acknowledged success in signing. +Done, cleaning up. +$ make run_blind_sig_example +guix shell qemu -- qemu-x86_64 -cpu max blind_sig_example +Preparing blind signature context ("Current III" set from Rückert's paper). +n = 1024 +d_s = 283 +m = 9 +phi = 4 +psi = 1 +d_alpha = 1024 +d_epsilon_star = 1023 +d_y = 10928598810624 +d_g_star = 10928302353408 +d_beta = 402860937956032512 +d_g = 402850009653679104 +q = 1208925819614629174706189 +Making a test signature for ASCII buffer: "This is a message to blind-sign.". +User could not obtain signature, restart is being requested from signer. +Restart triggered by signer from step 5. +User retries with new alpha. +Restart triggered by signer from step 3. +Restart triggered by signer from step 3. +User successfully obtained signature. +Signer acknowledged success in signing. +Done, cleaning up. +``` + +There is also a program (remnant of initial development) that serves as an +example of polynomial operations in a ring modulo X^m+1 over a modulo field with non-canonical range — [-(n-1)/2, (n-1)/2] rather than [0, n-1]. ``` @@ -7,4 +7,4 @@ # it… Why not load all of it to memory first? exec sh -c "$(awk '{if (after) print} /#{3}/{after=1}' "$0")" "$0" "$@" ### -guix shell gcc-toolchain flint make +guix shell gcc-toolchain flint libgcrypt make diff --git a/poly_mul.c b/poly_mul.c deleted file mode 100644 index dd86596..0000000 --- a/poly_mul.c +++ /dev/null @@ -1,301 +0,0 @@ -/* - * SPDX-License-Identifier: CC0-1.0 - * - * Copyright (C) 2024 W. Kosior <koszko@koszko.org> - */ - -#include <stdbool.h> -#include <stdio.h> -#include <stdlib.h> -#include <unistd.h> - -#include <flint/flint.h> -#include <flint/fmpz.h> -#include <flint/fmpz_mod.h> -#include <flint/fmpz_poly.h> - -/* Exponent for Mersenne prime, for testing. */ -#define TEST_MERSENNE_EXPONENT 7 /* 89 */ - -void marsenne_prime_init(fmpz_t prime, const ulong exponent) { - fmpz_init(prime); - - fmpz_ui_pow_ui(prime, 2, exponent); - fmpz_sub_ui(prime, prime, 1); -} - -void init_read_poly(fmpz_poly_t poly, FILE * file) { - bool first = true; - fmpz_t coef; - - fmpz_poly_init(poly); - fmpz_init(coef); - - for (ulong exponent = 0;; exponent++) { - int separator_char; - - if (first) { - first = false; - } else { - separator_char = getc(file); - - if (separator_char == '\n') - break; - - if (separator_char != ' ') - goto error; - } - - if (fmpz_fread(file, coef) < 0) - goto error; - - fmpz_poly_set_coeff_fmpz(poly, exponent, coef); - } - - fmpz_clear(coef); - return; - -error: - fprintf(stderr, "Error reading polynomial.\n"); - abort(); -} - -/* - * FLINT seems to assume all modulo operations are performed on integers in - * range [0, n-1]. Here we provide a facility for performing modulo operations - * on big integers in range [-(n-1)/2, (n-1)/2]. - */ - -struct mod_centered_0_ctx { - fmpz_t mod; - fmpz_t range_max; -}; - -typedef struct mod_centered_0_ctx mod_centered_0_ctx_t[1]; - -void mod_c0_ctx_init(mod_centered_0_ctx_t ctx, fmpz_t mod) { - struct mod_centered_0_ctx *ctxp = ctx; - - fmpz_init_set(ctxp->mod, mod); - - fmpz_init(ctxp->range_max); - fmpz_sub_ui(ctxp->range_max, ctxp->mod, 1); - /* Bit-shifting is faster but FLINT lacks convenient API for it. */ - fmpz_divexact_ui(ctxp->range_max, ctxp->range_max, 2); -} - -void mod_c0_ctx_clear(mod_centered_0_ctx_t ctx) { - fmpz_clear(ctx[0].mod); - fmpz_clear(ctx[0].range_max); -} - -void mod_c0(fmpz_t value, mod_centered_0_ctx_t ctx) { - fmpz_add(value, value, ctx[0].range_max); - fmpz_fdiv_r(value, value, ctx[0].mod); - fmpz_sub(value, value, ctx[0].range_max); -} - -void mod_c0_ctx_init_set(mod_centered_0_ctx_t dst_ctx, - mod_centered_0_ctx_t src_ctx) { - fmpz_init_set(dst_ctx[0].mod, src_ctx[0].mod); - fmpz_init_set(dst_ctx[0].range_max, src_ctx[0].range_max); -} - -/* - * Here we provide a facility for performing operations in polynomial rings - * modulo X^m+1 over fields of integers modulo n shifted to range [-(n-1)/2, - * (n-1)/2]. - */ - -struct poly_ring_ctx { - mod_centered_0_ctx_t mod_ctx; - slong divisor_degree; -}; - -typedef struct poly_ring_ctx poly_ring_ctx_t[1]; - -void poly_ring_ctx_init(poly_ring_ctx_t ctx, mod_centered_0_ctx_t mod_ctx, - slong divisor_degree) { - if (divisor_degree < 0) - abort(); - - mod_c0_ctx_init_set(ctx[0].mod_ctx, mod_ctx); - ctx[0].divisor_degree = divisor_degree; -} - -void poly_ring_ctx_clear(poly_ring_ctx_t ctx) { - mod_c0_ctx_clear(ctx[0].mod_ctx); -} - -/* - * Apply modulo operations to make poly a member of the ring designated by ctx. - */ -void poly_to_ring(fmpz_poly_t poly, poly_ring_ctx_t ctx) { - slong degree = fmpz_poly_degree(poly); - fmpz_t new_coef_value; - - fmpz_init(new_coef_value); - - for (slong coef_idx = 0; - coef_idx < ctx[0].divisor_degree; - coef_idx++) { - int sign = 1; - slong higher_coef_idx = coef_idx; - - fmpz_poly_get_coeff_fmpz(new_coef_value, poly, coef_idx); - - /* - * Polynomial division by X^m+1 can be achieved by substituting - * -1 for X^m. - */ - do { - fmpz const * higher_coef; - - sign *= -1; - higher_coef_idx += ctx[0].divisor_degree; - - if (higher_coef_idx > degree) - break; - - higher_coef = - fmpz_poly_get_coeff_ptr(poly, higher_coef_idx); - - (sign == 1 ? &fmpz_add : &fmpz_sub) - (new_coef_value, new_coef_value, higher_coef); - } while (true); - - mod_c0(new_coef_value, ctx[0].mod_ctx); - fmpz_poly_set_coeff_fmpz(poly, coef_idx, new_coef_value); - } - - if (degree >= ctx[0].divisor_degree) - fmpz_poly_realloc(poly, ctx[0].divisor_degree); - - fmpz_clear(new_coef_value); -} - -void poly_mul_in_ring(fmpz_poly_t res, fmpz_poly_t poly1, fmpz_poly_t poly2, - poly_ring_ctx_t ctx) { - fmpz_poly_mul(res, poly1, poly2); - poly_to_ring(res, ctx); -} - -void poly_add_in_ring(fmpz_poly_t res, fmpz_poly_t poly1, fmpz_poly_t poly2, - poly_ring_ctx_t ctx) { - fmpz_poly_add(res, poly1, poly2); - poly_to_ring(res, ctx); -} - -void poly_sub_in_ring(fmpz_poly_t res, fmpz_poly_t poly1, fmpz_poly_t poly2, - poly_ring_ctx_t ctx) { - fmpz_poly_sub(res, poly1, poly2); - poly_to_ring(res, ctx); -} - -int main(const int argc, const char* const* const argv) { - fmpz_t prime; /* integer for modulo operations */ - mod_centered_0_ctx_t mod_ctx; - - (void) argc; - (void) argv; - - /* - * Marsenne primes are used just for testing. Cryptographic algorithm - * will use different ones. - */ - marsenne_prime_init(prime, TEST_MERSENNE_EXPONENT); - - printf("Prime used for modulo operations: "); - fmpz_fprint(stdout, prime); - putchar('\n'); - - mod_c0_ctx_init(mod_ctx, prime); - - { /* Experiment 1 — modulo addition */ - fmpz_t num1, num2, num_sum; - - fmpz_init_set_ui(num1, 55); - fmpz_init_set_ui(num2, 31); - fmpz_init(num_sum); - - fmpz_fprint(stdout, num1); - printf(" + "); - fmpz_fprint(stdout, num2); - printf(" mod [-"); - fmpz_fprint(stdout, mod_ctx[0].range_max); - putchar(','); - fmpz_fprint(stdout, mod_ctx[0].range_max); - printf("] = "); - - fmpz_add(num_sum, num1, num2); - mod_c0(num_sum, mod_ctx); - fmpz_fprint(stdout, num_sum); - putchar('\n'); - - fmpz_clear(num1); - fmpz_clear(num2); - fmpz_clear(num_sum); - } /* End of experiment 1 */ - - { /* Experiment 2 */ - fmpz_poly_t poly1, poly2, poly_computed; - slong divisor_degree; - poly_ring_ctx_t poly_ring_ctx; - - printf("Give first polynomial for the experiment:\n"); - init_read_poly(poly1, stdin); - - printf("Read polynomial: "); - fmpz_poly_print_pretty(poly1, "x"); - putchar('\n'); - - printf("Give second polynomial for the experiment:\n"); - init_read_poly(poly2, stdin); - - printf("Read polynomial: "); - fmpz_poly_print_pretty(poly2, "x"); - putchar('\n'); - - fmpz_poly_init(poly_computed); - - printf("Normal product of polynomials:\n"); - fmpz_poly_mul(poly_computed, poly1, poly2); - fmpz_poly_print_pretty(poly_computed, "x"); - putchar('\n'); - - printf("Normal sum of polynomials:\n"); - fmpz_poly_add(poly_computed, poly1, poly2); - fmpz_poly_print_pretty(poly_computed, "x"); - putchar('\n'); - - printf("Give the degree m of X^m+1 polynomial to be used as "); - printf("divisor in the ring:\n"); - if (flint_scanf("%wd", &divisor_degree) < 1 || - divisor_degree < 1) { - fprintf(stderr, "Bad divisor.\n"); - abort(); - } - poly_ring_ctx_init(poly_ring_ctx, mod_ctx, divisor_degree); - - printf("Product of polynomials in the ring:\n"); - poly_mul_in_ring(poly_computed, poly1, poly2, poly_ring_ctx); - fmpz_poly_print_pretty(poly_computed, "x"); - putchar('\n'); - - printf("Sum of polynomials in the ring:\n"); - poly_add_in_ring(poly_computed, poly1, poly2, poly_ring_ctx); - fmpz_poly_print_pretty(poly_computed, "x"); - putchar('\n'); - - fmpz_poly_clear(poly1); - fmpz_poly_clear(poly2); - fmpz_poly_clear(poly_computed); - - poly_ring_ctx_clear(poly_ring_ctx); - } /* End of experiment 2 */ - - mod_c0_ctx_clear(mod_ctx); - fmpz_clear(prime); - - return EXIT_SUCCESS; -} diff --git a/pqcrypto_bitcnt_bytes.h b/pqcrypto_bitcnt_bytes.h new file mode 100644 index 0000000..ff3c4e7 --- /dev/null +++ b/pqcrypto_bitcnt_bytes.h @@ -0,0 +1,14 @@ +/* + * SPDX-License-Identifier: CC0-1.0 + * + * Copyright (C) 2025 W. Kosior <koszko@koszko.org> + */ + +#ifndef PQCRYPTO_BITCNT_BYTES_H +#define PQCRYPTO_BITCNT_BYTES_H + +#include <stdint.h> + +#define BITCNT_BYTES(n) ((n - 1) / 8 + 1) + +#endif /* PQCRYPTO_BITCNT_BYTES_H */ diff --git a/pqcrypto_blind_sig.c b/pqcrypto_blind_sig.c new file mode 100644 index 0000000..ababed2 --- /dev/null +++ b/pqcrypto_blind_sig.c @@ -0,0 +1,1123 @@ +/* + * SPDX-License-Identifier: CC0-1.0 + * + * Copyright (C) 2025 W. Kosior <koszko@koszko.org> + */ + +#define _POSIX_C_SOURCE 200809L /* for fmemopen() */ + +#include <arpa/inet.h> +#include <stdint.h> +#include <stdlib.h> +#include <string.h> + +#include "pqcrypto_bitcnt_bytes.h" +#define PQCRYPTO_BLIND_SIG_C +#include "pqcrypto_blind_sig.h" +#include "pqcrypto_commitment_shake256.h" +#include "pqcrypto_hash_shake256.h" +#include "pqcrypto_prng_getrandom.h" +#include "pqcrypto_prng_seeded.h" + + + +/*** + *** Serialization, deserialization and deinitialization of structures. + ***/ + +/* + * bool (de)serialization. + * + * Note: these 2 function rely on additionam macro wrappers for them (defined + * later on) and they don't accept the context argument. + */ + +static size_t bool_serialize(FILE * stream, bool flag) { + if (putc(flag, stream) == EOF) + abort(); + + return 1; +} + +/* + * Note: this deserialization function accepts destination pointer not concealed + * as an array type. + */ + +static size_t bool_deserialize(FILE * stream, bool * flag) { + int result = getc(stream); + + if (result == EOF) + abort(); + + *flag = result; + + return 1; +} + +/* + * Reasonably big number (de)serialization. + * + * Note: these 2 functions are only called "manually" (not from + * SERIALIZABLE_STRUCT() macros) and they don't accept the context argument. + */ + +static size_t uint_least64_serialize(FILE * stream, uint_least64_t number) { + uint32_t halfs[2]; + + halfs[0] = htonl(number >> 32); + halfs[1] = htonl(number & UINT32_MAX); + + if (fwrite(halfs, sizeof(halfs), 1, stream) != 1) + abort(); + + return sizeof(halfs); +} + +/* + * Note: this deserialization function accepts destination pointer not concealed + * as an array type. + */ + +static size_t uint_least64_deserialize(FILE * stream, uint_least64_t * number) { + uint32_t halfs[2]; + + if (fread(halfs, sizeof(halfs), 1, stream) != 1) + abort(); + + *number = ((uint_least64_t) ntohl(halfs[0])) << 32; + *number |= ntohl(halfs[1]); + + return sizeof(halfs); +} + +/* fmpz_t (de)serialization and deinitialization. */ + +static size_t fmpz_t_serialize(FILE * stream, fmpz_t const number, + blind_sig_ctx_t const ctx) { + size_t written = fmpz_out_raw(stream, number); + + (void) ctx; + + if (!written) + abort(); + + return written; +} + +static size_t fmpz_t_deserialize(FILE * stream, fmpz_t number, + blind_sig_ctx_t const ctx) { + size_t read; + + (void) ctx; + + fmpz_init(number); + + read = fmpz_inp_raw(number, stream); + if (!read) + abort(); + + return read; +} + +inline static void fmpz_t_clear(fmpz_t fmpz, blind_sig_ctx_t const ctx) { + (void) ctx; + + fmpz_clear(fmpz); +} + +/* Message (de)serialization and deinitialization. */ + +static size_t blind_sig_message_t_serialize(FILE * stream, + blind_sig_message_t const message, + blind_sig_ctx_t const ctx) { + size_t written; + + (void) ctx; + + written = uint_least64_serialize(stream, message->bytes); + + if (fwrite(message->buf, message->bytes, 1, stream) != 1) + abort(); + + written += message->bytes; + + return written; +} + +static size_t blind_sig_message_t_deserialize(FILE * stream, + blind_sig_message_t message, + blind_sig_ctx_t const ctx) { + uint_least64_t size; + size_t read; + + (void) ctx; + + read = uint_least64_deserialize(stream, &size); + if (size > SIZE_MAX) + abort(); + + message->bytes = size; + + message->buf = malloc(size); + if (!message->buf) + abort(); + + if (fread(message->buf, size, 1, stream) != 1) + abort(); + + read += size; + + return read; +} + +inline static void blind_sig_message_t_clear(blind_sig_message_t message, + blind_sig_ctx_t const ctx) { + (void) ctx; + + free(message->buf); +} + +/* fmpz_poly_t (de)serialization. */ + +static size_t fmpz_poly_t_serialize(FILE * stream, fmpz_poly_t const poly, + blind_sig_ctx_t const ctx) { + slong length = fmpz_poly_length(poly); + fmpz_t coef; + size_t written; + + written = uint_least64_serialize(stream, length); + + fmpz_init(coef); + + while (length--) { + fmpz_poly_get_coeff_fmpz(coef, poly, length); + written += fmpz_t_serialize(stream, coef, ctx); + } + + fmpz_clear(coef); + + return written; +} + +static size_t fmpz_poly_t_deserialize(FILE * stream, fmpz_poly_t poly, + blind_sig_ctx_t const ctx) { + uint_least64_t length; + fmpz_t coef; + size_t read; + + read = uint_least64_deserialize(stream, &length); + if (length > WORD_MAX) + abort(); + + fmpz_poly_init(poly); + + while (length && length--) { + read += fmpz_t_deserialize(stream, coef, ctx); + fmpz_poly_set_coeff_fmpz(poly, length, coef); + fmpz_clear(coef); + } + + return read; +} + +inline static void fmpz_poly_t_clear(fmpz_poly_t poly, + blind_sig_ctx_t const ctx) { + (void) ctx; + + fmpz_poly_clear(poly); +} + +/* Polynomials vector (de)serialization. */ + +static size_t blind_sig_poly_vector_t_serialize(FILE * stream, + blind_sig_poly_vector_t const + polys, + blind_sig_ctx_t const ctx) { + size_t written = 0; + + for (ulong i = 0; i < ctx->m; i++) + written += fmpz_poly_t_serialize(stream, *polys + i, ctx); + + return written; +} + +static size_t blind_sig_poly_vector_t_deserialize(FILE * stream, + blind_sig_poly_vector_t + polys, + blind_sig_ctx_t const ctx) { + size_t read = 0; + + *polys = malloc(ctx->m * sizeof(fmpz_poly_struct)); + if (!*polys) + abort(); + + for (ulong i = 0; i < ctx->m; i++) + read += fmpz_poly_t_deserialize(stream, *polys + i, ctx); + + return read; +} + +static void blind_sig_poly_vector_t_clear(blind_sig_poly_vector_t polys, + blind_sig_ctx_t const ctx) { + for (ulong i = 0; i < ctx->m; i++) + fmpz_poly_clear(*polys + i); + + free(*polys); +} + +/* Randomness or commitment buffer (de)serialization. */ + +static size_t blind_sig_n_bit_buf_t_serialize(FILE * stream, + blind_sig_n_bit_buf_t const + buffer, + blind_sig_ctx_t const ctx) { + size_t bytes = BITCNT_BYTES(ctx->n); + + if (fwrite(*buffer, bytes, 1, stream) != 1) + abort(); + + return bytes; +} + +static size_t blind_sig_n_bit_buf_t_deserialize(FILE * stream, + blind_sig_n_bit_buf_t buffer, + blind_sig_ctx_t const ctx) { + size_t bytes = BITCNT_BYTES(ctx->n); + + *buffer = malloc(bytes); + if (!*buffer) + abort(); + + if (fread(*buffer, bytes, 1, stream) != 1) + abort(); + + return bytes; +} + +inline static void blind_sig_n_bit_buf_t_clear(blind_sig_n_bit_buf_t buffer, + blind_sig_ctx_t const ctx) { + (void) ctx; + + free(*buffer); +} + +/* + * bool (de)serializer macro wrappers that returns early if bool field's value + * is false. + * + * Here we assume the bool is always an ok-type flag and later struct members + * are only valid/initialized/meaningful when it is true. + */ + +#define _Bool_serialize(stream, bool_expr, ctx) \ + /* count += */ bool_serialize(stream, bool_expr); \ + \ + if (!bool_expr) \ + return count + +#define _Bool_deserialize(stream, bool_expr, ctx) \ + /* count += */ bool_deserialize(stream, &bool_expr); \ + \ + if (!bool_expr) \ + return count + +/* (De)serialization of structures from the separate file. */ + +#define FIELD(type, name) \ + count += MAKE_NAME(type)(stream, obj->name, ctx); + +#define SERIALIZABLE_STRUCT(name, fields) \ + size_t MAKE_NAME(name)(FILE * stream, name##_t MAYBE_CONST obj, \ + blind_sig_ctx_t const ctx) { \ + size_t count = 0; \ + \ + fields; \ + \ + return count; \ + } \ + \ + void MAKE_NAME(name##_file)(const char * filename, \ + name##_t MAYBE_CONST obj, \ + blind_sig_ctx_t const ctx) { \ + FILE * stream = fopen(filename, MAKE_NAME(FOPEN_MODE)); \ + \ + if (!stream) \ + abort(); \ + \ + MAKE_NAME(name)(stream, obj, ctx); \ + \ + if (fclose(stream) == EOF) \ + abort(); \ + } + +#define FOPEN_MODE_serialize "w" +#define FOPEN_MODE_deserialize "r" + +#define MAKE_NAME(prefix) prefix##_serialize +#define MAYBE_CONST const + +#include "pqcrypto_blind_sig_serializable.c" + +#undef MAKE_NAME +#undef MAYBE_CONST + +#define MAKE_NAME(prefix) prefix##_deserialize +#define MAYBE_CONST + +#include "pqcrypto_blind_sig_serializable.c" + +#undef MAKE_NAME +#undef MAYBE_CONST + +#undef FOPEN_MODE_serialize +#undef FOPEN_MODE_deserialize + +#undef FIELD +#undef SERIALIZABLE_STRUCT + +#undef bool_serialize +#undef bool_deserialize + +/* bool deinitializer macro (similar logic as before). */ + +#define bool_clear(bool_expr, ctx) \ + if (!bool_expr) \ + return; + +/* Deinitialization of structures from the separate file. */ + +#define FIELD(type, name) \ + type##_clear(obj->name, ctx); + +#define SERIALIZABLE_STRUCT(name, fields) \ + void name##_clear(name##_t obj, blind_sig_ctx_t const ctx) { \ + fields; \ + } + +#include "pqcrypto_blind_sig_serializable.c" + +#undef FIELD +#undef SERIALIZABLE_STRUCT + +#undef bool_clear + + + +/*** + *** Initialization and operations on blind_sig_message_t, + *** blind_sig_poly_vector_t and blind_sig_n_bit_buf_t. + ***/ + +/* Initialization of blind_sig_message_t. */ + +static void blind_sig_message_init_set_buf(blind_sig_message_t message, + void const * buf, size_t bytes) { + message->buf = malloc(bytes); + if (!message->buf) + abort(); + + memcpy(message->buf, buf, bytes); + message->bytes = bytes; +} + +/* Initialization of blind_sig_poly_vector_t. */ + +static void blind_sig_poly_vector_init(blind_sig_poly_vector_t polys, + blind_sig_ctx_t const ctx) { + *polys = malloc(ctx->m * sizeof(fmpz_poly_struct)); + if (!*polys) + abort(); + + for (ulong i = 0; i < ctx->m; i++) + fmpz_poly_init(*polys + i); +} + +static void blind_sig_poly_vector_init_set(blind_sig_poly_vector_t dst_polys, + blind_sig_poly_vector_t const + src_polys, + blind_sig_ctx_t const ctx) { + blind_sig_poly_vector_init(dst_polys, ctx); + + for (ulong i = 0; i < ctx->m; i++) + fmpz_poly_set(*dst_polys + i, *src_polys + i); +} + +/* Initialization of blind_sig_n_bit_buf_t. */ + +static void blind_sig_n_bit_buf_init(blind_sig_n_bit_buf_t n_bit_buf, + blind_sig_ctx_t const ctx) { + *n_bit_buf = malloc(BITCNT_BYTES(ctx->n)); + if (!*n_bit_buf) + abort(); +} + +static void blind_sig_n_bit_buf_init_set(blind_sig_n_bit_buf_t dst_n_bit_buf, + blind_sig_n_bit_buf_t const + src_n_bit_buf, + blind_sig_ctx_t const ctx) { + blind_sig_n_bit_buf_init(dst_n_bit_buf, ctx); + + memcpy(*dst_n_bit_buf, *src_n_bit_buf, BITCNT_BYTES(ctx->n)); +} + +/*** + *** Context handling. + ***/ + +blind_sig_params_t const blind_sig_params_current_III = { + { + .n = 1024, + .q_bits = 81, + .phi = 4, + .psi = 1, + .d_s = 283, + .m = 9, + .log_level = BLIND_SIG_LOG_INFO_2_PARAMETERS, + } +}; + +blind_sig_params_t const blind_sig_params_toy = { + { + .n = 4, + .q_bits = 17, + .phi = 2, + .psi = 1, + .d_s = 3, + .m = 6, + .log_level = BLIND_SIG_LOG_DEBUG_2_VALUES, + } +}; + +static char const public_initialization_seed[] = "Ruckert 2008 lattices"; + +void blind_sig_ctx_init(blind_sig_ctx_t ctx, blind_sig_params_t const params) { + prng_seeded_state_t prng_state; + fmpz_t q, d_s_check, mod_divisor_tmp; + mod_centered_0_ctx_t mod_ctx; + + /* Make some sanity checks. */ + + if (params->q_bits < 3 || + params->q_bits > UWORD_MAX || + params->n < 2 || + params->n > WORD_MAX || + BITCNT_BYTES(params->n) > SIZE_MAX || + params->d_s < 1 || + params->d_s > WORD_MAX || + SIZE_MAX / sizeof(fmpz_poly_struct) < params->m) + abort(); + + /* Set the simple params. */ + + ctx->n = params->n; + ctx->d_s = params->d_s; + ctx->m = params->m; + ctx->phi = params->phi; + ctx->psi = params->psi; + ctx->public_commitment_function = commitment_shake256; + *ctx->public_hash_function = *hash_function_shake256; + ctx->log_level = params->log_level; + + /* Prepare this fmpz for use throughout this function. */ + + fmpz_init(mod_divisor_tmp); + + /* Derive the prime for modulo operations. */ + + fmpz_init(q); + fmpz_ui_pow_ui(q, 2, params->q_bits - 1); + fmpz_nextprime(q, q, 0); + + /* Make sure d_s is not too big. */ + + fmpz_init_set_ui(d_s_check, params->d_s); + fmpz_mul2_uiui(d_s_check, d_s_check, params->n, 4); + + if (fmpz_cmp(d_s_check, q) >= 0) + abort(); + + fmpz_clear(d_s_check); + + /* Prepare the context for key generation. */ + + if (params->d_s > (UWORD_MAX - 1) / 2) + abort(); + + fmpz_set_ui(mod_divisor_tmp, params->d_s * 2 + 1); + + mod_c0_ctx_init(ctx->key_gen_ctx, mod_divisor_tmp); + + /* Prepare d_alpha and the context for generating the alpha value. */ + + if (UWORD_MAX / params->psi < params->n) + abort(); + + ctx->d_alpha = params->psi * params->n; + + fmpz_set_ui(mod_divisor_tmp, ctx->d_alpha); + fmpz_mul_2exp(mod_divisor_tmp, mod_divisor_tmp, 1); + fmpz_add_ui(mod_divisor_tmp, mod_divisor_tmp, 1); + + mod_c0_ctx_init(ctx->alpha_gen_ctx, mod_divisor_tmp); + + /* + * Prepare d_epsilon_star and d_y, as well as the context for generating + * the Y commitment. + */ + + ctx->d_epsilon_star = ctx->d_alpha - 1; + + fmpz_init(ctx->d_y); + fmpz_ui_pow_ui(ctx->d_y, params->n, 2); + fmpz_mul_ui(ctx->d_y, ctx->d_y, params->phi); + fmpz_mul_ui(ctx->d_y, ctx->d_y, params->m); + fmpz_mul_ui(ctx->d_y, ctx->d_y, params->d_s); + fmpz_mul_ui(ctx->d_y, ctx->d_y, ctx->d_epsilon_star); + + fmpz_mul_2exp(mod_divisor_tmp, ctx->d_y, 1); + fmpz_add_ui(mod_divisor_tmp, mod_divisor_tmp, 1); + + mod_c0_ctx_init(ctx->y_commitment_gen_ctx, mod_divisor_tmp); + + /* + * Prepare d_g_star, d_beta and d_g, as well as the context for + * generating the Beta. + */ + + fmpz_init_set_ui(ctx->d_g_star, params->n); + fmpz_mul_ui(ctx->d_g_star, ctx->d_g_star, params->d_s); + fmpz_mul_ui(ctx->d_g_star, ctx->d_g_star, ctx->d_epsilon_star); + fmpz_sub(ctx->d_g_star, ctx->d_y, ctx->d_g_star); + + fmpz_init_set_ui(ctx->d_beta, params->phi); + fmpz_mul_ui(ctx->d_beta, ctx->d_beta, params->m); + fmpz_mul_ui(ctx->d_beta, ctx->d_beta, params->n); + fmpz_mul(ctx->d_beta, ctx->d_beta, ctx->d_g_star); + + fmpz_init(ctx->d_g); + fmpz_sub(ctx->d_g, ctx->d_beta, ctx->d_g_star); + + fmpz_mul_2exp(mod_divisor_tmp, ctx->d_beta, 1); + fmpz_add_ui(mod_divisor_tmp, mod_divisor_tmp, 1); + + mod_c0_ctx_init(ctx->beta_gen_ctx, mod_divisor_tmp); + + /* Prepare contexts for modulo field and polynomial operations. */ + + mod_c0_ctx_init(mod_ctx, q); + + poly_ring_ctx_init(ctx->poly_ring_ctx, mod_ctx, params->n); + + mod_c0_ctx_clear(mod_ctx); + + /* Derive the vector of polynomials to serve as public homomorphism. */ + + blind_sig_poly_vector_init(ctx->public_homomorphism, ctx); + + prng_seeded_state_init(prng_state, public_initialization_seed, + sizeof(public_initialization_seed)); + + for (ulong i = 0; i < params->m; i++) { + poly_prng_in_ring(*ctx->public_homomorphism + i, + prng_seeded, prng_state, ctx->poly_ring_ctx); + } + + prng_seeded_state_clear(prng_state); + + /* Print parameters. */ + +#define X(fmt, arg) blind_sig_log_INFO_2_PARAMETERS(ctx, fmt, arg) + + X("n = %{ulong}\n", ctx->n); + X("d_s = %{ulong}\n", ctx->d_s); + X("m = %{ulong}\n", ctx->m); + X("phi = %{ulong}\n", ctx->phi); + X("psi = %{ulong}\n", ctx->psi); + X("d_alpha = %{ulong}\n", ctx->d_alpha); + X("d_epsilon_star = %{ulong}\n", ctx->d_epsilon_star); + X("d_y = %{fmpz}\n", ctx->d_y); + X("d_g_star = %{fmpz}\n", ctx->d_g_star); + X("d_beta = %{fmpz}\n", ctx->d_beta); + X("d_g = %{fmpz}\n", ctx->d_g); + X("q = %{fmpz}\n", q); + +#undef X + + /* Free the memory associated temprarily. */ + + fmpz_clear(mod_divisor_tmp); + fmpz_clear(q); +} + +void blind_sig_ctx_clear(blind_sig_ctx_t ctx) { + mod_c0_ctx_clear(ctx->key_gen_ctx); + + mod_c0_ctx_clear(ctx->alpha_gen_ctx); + + fmpz_clear(ctx->d_y); + + mod_c0_ctx_clear(ctx->y_commitment_gen_ctx); + + fmpz_clear(ctx->d_g_star); + + fmpz_clear(ctx->d_beta); + + mod_c0_ctx_clear(ctx->beta_gen_ctx); + + fmpz_clear(ctx->d_g); + + poly_ring_ctx_clear(ctx->poly_ring_ctx); + + blind_sig_poly_vector_t_clear(ctx->public_homomorphism, ctx); +} + + + +/*** + *** Helper functions used from a few places. + ***/ + +int blind_sig_vlog(blind_sig_ctx_t const ctx, + enum blind_sig_log_level message_level, + char const * fmt, va_list ap) { + if (message_level <= ctx->log_level) + return flint_vfprintf(stderr, fmt, ap); + + return 0; +} + +static void apply_homomorphism(fmpz_poly_t res, + blind_sig_poly_vector_t const polys, + blind_sig_ctx_t const ctx) { + fmpz_poly_t tmp; + + fmpz_poly_init(tmp); + + for (ulong i = 0; i < ctx->m; i++) { + poly_mul_in_ring(i ? tmp : res, + *polys + i, *ctx->public_homomorphism + i, + ctx->poly_ring_ctx); + + if (i) + poly_add_in_ring(res, res, tmp, ctx->poly_ring_ctx); + } + + fmpz_poly_clear(tmp); +} + +static void apply_hash(fmpz_poly_t res, fmpz_poly_t const input, + blind_sig_n_bit_buf_t const commitment, + blind_sig_ctx_t const ctx) { + int extracted; + void * hash_state = ctx->public_hash_function->make(); + void * fmpz_buf; + FILE * fmpz_memfile; + size_t fmpz_bytes, fmpz_written; + fmpz_t coef; + + fmpz_bytes = fmpz_size(ctx->poly_ring_ctx->mod_ctx->divisor); + /* Give space for 1 more limb just in case. */ + fmpz_bytes++; + fmpz_bytes *= sizeof(ulong); + /* Fit serialized length, which is 4 bytes according to Flint doc. */ + fmpz_bytes += 4; + + fmpz_buf = malloc(fmpz_bytes); + if (!fmpz_buf) + abort(); + + fmpz_memfile = fmemopen(fmpz_buf, fmpz_bytes, "w"); + setbuf(fmpz_memfile, NULL); + + fmpz_init(coef); + + for (ulong i = 0; i < ctx->n; i++) { + fmpz_poly_get_coeff_fmpz(coef, input, i); + fmpz_written = fmpz_out_raw(fmpz_memfile, coef); + if (!fmpz_written) + abort(); + + ctx->public_hash_function->feed(hash_state, fmpz_buf, + fmpz_written); + + fseek(fmpz_memfile, 0, SEEK_SET); + } + + ctx->public_hash_function->feed(hash_state, *commitment, + BITCNT_BYTES(ctx->n)); + + fmpz_poly_zero(res); + fmpz_poly_realloc(res, ctx->n); + + for (ulong i = 0; i < ctx->n; i++) { + do { + extracted = ctx->public_hash_function->getc(hash_state); + + fmpz_poly_set_coeff_si(res, i, extracted % 3 - 1); + } while (extracted >= 255); + } + + ctx->public_hash_function->free(hash_state); + + fclose(fmpz_memfile); + free(fmpz_buf); + + fmpz_clear(coef); +} + + + +/*** + *** Key handling. + ***/ + +void blind_sig_key_init_gen(blind_sig_priv_key_t priv_key, + blind_sig_pub_key_t pub_key, + blind_sig_ctx_t const ctx) { + blind_sig_poly_vector_init(priv_key->key_polys, ctx); + + for (ulong i = 0; i < ctx->m; i++) { + poly_rand_mod_c0(*priv_key->key_polys + i, ctx->n, + ctx->key_gen_ctx); + } + + fmpz_poly_init(pub_key->key_poly); + + apply_homomorphism(pub_key->key_poly, priv_key->key_polys, ctx); +} + + + +/*** + *** Signature protocol. + ***/ + +void blind_sig_signer_state_init(blind_sig_signer_state_t state, + blind_sig_ctx_t const ctx) { + blind_sig_poly_vector_init(state->y_commitment_random, ctx); + fmpz_poly_init(state->y_commitment); + blind_sig_poly_vector_init(state->z_star, ctx); + fmpz_poly_init(state->epsilon_star); +} + +void blind_sig_user_state_init(blind_sig_user_state_t state, + blind_sig_ctx_t const ctx) { + blind_sig_n_bit_buf_init(state->randomness, ctx); + blind_sig_n_bit_buf_init(state->commitment, ctx); + fmpz_poly_init(state->alpha); + blind_sig_poly_vector_init(state->beta, ctx); + fmpz_poly_init(state->epsilon); + fmpz_poly_init(state->epsilon_star); +} + +void blind_sig_proto_p1_init_do(blind_sig_proto_p1_t result, + blind_sig_signer_state_t state, + blind_sig_ctx_t const ctx) { + blind_sig_log_DEBUG_1_PHASES(ctx, "Protocol phase 1 started.\n"); + + for (ulong i = 0; i < ctx->m; i++) { + poly_rand_mod_c0(*state->y_commitment_random + i, + ctx->n, ctx->y_commitment_gen_ctx); + } + + apply_homomorphism(state->y_commitment, state->y_commitment_random, + ctx); + + fmpz_poly_init(result->y_commitment); + fmpz_poly_set(result->y_commitment, state->y_commitment); + + blind_sig_log_DEBUG_2_VALUES( + ctx, "Y commitment computed as %{fmpz_poly}.\n", + result->y_commitment); +} + +void blind_sig_proto_p2_init_do(blind_sig_proto_p2_t result, + blind_sig_user_state_t state, + blind_sig_pub_key_t const pub_key, + void const * message_buf, + size_t message_bytes, + blind_sig_proto_p1_t const p1_result, + unsigned long * retries_left, + blind_sig_ctx_t const ctx) { + fmpz_poly_t transformed_beta; + + blind_sig_message_init_set_buf(state->message, message_buf, + message_bytes); + + blind_sig_log_DEBUG_1_PHASES(ctx, "Protocol phase 2 started.\n"); + + prng_getrandom(*state->randomness, BITCNT_BYTES(ctx->n), NULL); + + ctx->public_commitment_function( + *state->commitment, message_buf, message_bytes, + *state->randomness, ctx->n); + + for (ulong i = 0; i < ctx->m; i++) + poly_rand_mod_c0(*state->beta + i, ctx->n, ctx->beta_gen_ctx); + + fmpz_poly_init(transformed_beta); + + apply_homomorphism(transformed_beta, state->beta, ctx); + + while (true) { + poly_rand_mod_c0(state->alpha, ctx->n, ctx->alpha_gen_ctx); + + blind_sig_log_DEBUG_2_VALUES( + ctx, "alpha chosen as %{fmpz_poly}.\n", state->alpha); + + poly_mul_in_ring(state->epsilon, pub_key->key_poly, + state->alpha, ctx->poly_ring_ctx); + fmpz_poly_neg(state->epsilon, state->epsilon); + + poly_add_in_ring(state->epsilon, state->epsilon, + p1_result->y_commitment, ctx->poly_ring_ctx); + + poly_sub_in_ring(state->epsilon, state->epsilon, + transformed_beta, ctx->poly_ring_ctx); + + apply_hash(state->epsilon, state->epsilon, state->commitment, + ctx); + + blind_sig_log_DEBUG_2_VALUES( + ctx, "epsilon computed as %{fmpz_poly}.\n", + state->epsilon); + + poly_sub_in_ring(state->epsilon_star, state->epsilon, + state->alpha, ctx->poly_ring_ctx); + + blind_sig_log_DEBUG_2_VALUES( + ctx, "epsilon_star computed as %{fmpz_poly}.\n", + state->epsilon_star); + + if (poly_all_abs_leq_ui(state->epsilon_star, + ctx->d_epsilon_star)) { + fmpz_poly_init(result->epsilon_star); + fmpz_poly_set(result->epsilon_star, + state->epsilon_star); + result->ok = true; + + break; + } + + if (!(*retries_left && (*retries_left)--)) { + result->ok = false; + + blind_sig_log_ERROR( + ctx, "User failed to choose a proper alpha.\n"); + + break; + } + + blind_sig_log_INFO_1_CONTROL( + ctx, "User retries with new alpha.\n"); + } + + fmpz_poly_clear(transformed_beta); +} + +void blind_sig_proto_p3_init_do(blind_sig_proto_p3_t result, + blind_sig_signer_state_t state, + blind_sig_priv_key_t const priv_key, + blind_sig_proto_p2_t const p2_result, + blind_sig_ctx_t const ctx) { + blind_sig_log_DEBUG_1_PHASES(ctx, "Protocol phase 3 started.\n"); + + fmpz_poly_set(state->epsilon_star, p2_result->epsilon_star); + + for (ulong i = 0; i < ctx->m; i++) { + poly_mul_in_ring(*state->z_star + i, *priv_key->key_polys + i, + state->epsilon_star, ctx->poly_ring_ctx); + poly_add_in_ring(*state->z_star + i, *state->z_star + i, + *state->y_commitment_random + i, + ctx->poly_ring_ctx); + + if (!poly_all_abs_leq(*state->z_star + i, ctx->d_g_star)) { + result->ok = false; + + blind_sig_log_INFO_1_CONTROL( + ctx, "Restart triggered by signer from step" + " 3.\n"); + + return; + } + } + + blind_sig_poly_vector_init_set(result->z_star, state->z_star, ctx); + + result->ok = true; +} + +void blind_sig_proto_p4_init_do(blind_sig_proto_p4_t result, + blind_sig_t sig, + blind_sig_user_state_t const state, + blind_sig_proto_p3_t const p3_result, + blind_sig_ctx_t const ctx) { + blind_sig_poly_vector_t z; + + blind_sig_log_DEBUG_1_PHASES(ctx, "Protocol phase 4 started.\n"); + + /* Rater that clearing z later, we shall use it in the result. */ + + blind_sig_poly_vector_init(z, ctx); + + for (ulong i = 0; i < ctx->m; i++) { + poly_sub_in_ring(*z + i, + *p3_result->z_star + i, *state->beta + i, + ctx->poly_ring_ctx); + + if (!poly_all_abs_leq(*z + i, ctx->d_g)) + goto fail; + } + + blind_sig_message_init_set_buf(sig->message, state->message->buf, + state->message->bytes); + + blind_sig_n_bit_buf_init_set(sig->randomness, state->randomness, ctx); + + *sig->z = *z; + + fmpz_poly_init(sig->epsilon); + fmpz_poly_set(sig->epsilon, state->epsilon); + + result->needs_restart = false; + + blind_sig_log_INFO_1_CONTROL( + ctx, "User successfully obtained signature.\n"); + + return; + +fail: + blind_sig_n_bit_buf_init_set(result->commitment, state->commitment, + ctx); + + fmpz_poly_init(result->alpha); + fmpz_poly_set(result->alpha, state->alpha); + + /* Reuse z to store beta. */ + *result->beta = *z; + + for (ulong i = 0; i < ctx->m; i++) + fmpz_poly_set(*result->beta + i, *state->beta + i); + + fmpz_poly_init(result->epsilon); + fmpz_poly_set(result->epsilon, state->epsilon); + + result->needs_restart = true; + + blind_sig_log_INFO_1_CONTROL( + ctx, "User could not obtain signature, restart is being" + " requested from signer.\n"); +} + +void blind_sig_proto_p5_init_do(blind_sig_proto_p5_t result, + blind_sig_signer_state_t state, + blind_sig_pub_key_t pub_key, + blind_sig_proto_p4_t const p4_result, + blind_sig_ctx_t const ctx) { + fmpz_poly_t epsilon, tmp; + blind_sig_poly_vector_t z = {NULL}; + + blind_sig_log_DEBUG_1_PHASES(ctx, "Protocol phase 5 started.\n"); + + fmpz_poly_init(epsilon); + fmpz_poly_init(tmp); + + if (!p4_result->needs_restart) { + blind_sig_log_INFO_1_CONTROL( + ctx, "Signer acknowledged success in signing.\n"); + + goto success; + } + + /* Compute epsilon from alpha and epsilon_star, verify. */ + poly_add_in_ring(epsilon, state->epsilon_star, p4_result->alpha, + ctx->poly_ring_ctx); + if (!fmpz_poly_equal(epsilon, p4_result->epsilon)) + goto failed_proving; + + /* Compute epsilon from alpha and beta, verify. */ + apply_homomorphism(tmp, p4_result->beta, ctx); + + poly_mul_in_ring(epsilon, pub_key->key_poly, p4_result->alpha, + ctx->poly_ring_ctx); + fmpz_poly_neg(epsilon, epsilon); + + poly_add_in_ring(epsilon, epsilon, state->y_commitment, + ctx->poly_ring_ctx); + + poly_sub_in_ring(epsilon, epsilon, tmp, ctx->poly_ring_ctx); + + apply_hash(epsilon, epsilon, p4_result->commitment, ctx); + + if (!fmpz_poly_equal(epsilon, p4_result->epsilon)) + goto failed_proving; + + /* Compute epsilon from beta and z_star, verify. */ + blind_sig_poly_vector_init(z, ctx); + + for (ulong i = 0; i < ctx->m; i++) { + poly_sub_in_ring(*z + i, + *state->z_star + i, *p4_result->beta + i, + ctx->poly_ring_ctx); + } + + apply_homomorphism(tmp, z, ctx); + + poly_mul_in_ring(epsilon, epsilon, pub_key->key_poly, + ctx->poly_ring_ctx); + fmpz_poly_neg(epsilon, epsilon); + + poly_add_in_ring(epsilon, epsilon, tmp, ctx->poly_ring_ctx); + + apply_hash(epsilon, epsilon, p4_result->commitment, ctx); + + if (!fmpz_poly_equal(epsilon, p4_result->epsilon)) + goto failed_proving; + + /* Verify that z really doesn't belong to its target domain. */ + for (ulong i = 0; i < ctx->m; i++) { + if (!poly_all_abs_leq(*z + i, ctx->d_g)) { + result->ok = false; + + blind_sig_log_INFO_1_CONTROL( + ctx, "Restart triggered by signer from step" + " 5.\n"); + + goto out; + } + } + +failed_proving: + blind_sig_log_ERROR( + ctx, "User failed to prove to the signer that obtaining" + " signature failed :(\n"); + +success: + blind_sig_poly_vector_init_set(result->y_commitment_random, + state->y_commitment_random, ctx); + blind_sig_poly_vector_init_set(result->z_star, state->z_star, ctx); + + fmpz_poly_init(result->y_commitment); + fmpz_poly_init(result->epsilon_star); + + fmpz_poly_set(result->y_commitment, state->y_commitment); + fmpz_poly_set(result->epsilon_star, state->epsilon_star); + + result->ok = true; + +out: + fmpz_poly_clear(epsilon); + fmpz_poly_clear(tmp); + + if (*z) + blind_sig_poly_vector_t_clear(z, ctx); +} + + + +/*** + *** Signature verification. + ***/ + +/* TODO! */ diff --git a/pqcrypto_blind_sig.h b/pqcrypto_blind_sig.h new file mode 100644 index 0000000..2193bf2 --- /dev/null +++ b/pqcrypto_blind_sig.h @@ -0,0 +1,253 @@ +/* + * SPDX-License-Identifier: CC0-1.0 + * + * Copyright (C) 2025 W. Kosior <koszko@koszko.org> + */ + +#ifndef PQCRYPTO_BLIND_SIG_H +#define PQCRYPTO_BLIND_SIG_H + +#include <stdarg.h> +#include <stdbool.h> +#include <stdio.h> +#include <stdlib.h> + +#include "pqcrypto_poly.h" +#include "pqcrypto_hash.h" + + + +/*** + *** Definitions of types serializable as parts of other structers (but without + *** exposed API functions for this). + ***/ + +struct blind_sig_message { + void * buf; + size_t bytes; +}; + +typedef struct blind_sig_message blind_sig_message_t[1]; + +typedef fmpz_poly_struct * blind_sig_poly_vector_t[1]; + +typedef void * blind_sig_n_bit_buf_t[1]; + + + +/*** + *** Definitions of non-serializable types. + ***/ + +enum blind_sig_log_level { + BLIND_SIG_LOG_QUIET = 0, + BLIND_SIG_LOG_ERROR = 1, + BLIND_SIG_LOG_INFO_1_CONTROL = 2, + BLIND_SIG_LOG_INFO_2_PARAMETERS = 3, + BLIND_SIG_LOG_DEBUG_1_PHASES = 4, + BLIND_SIG_LOG_DEBUG_2_VALUES = 5, +}; + +struct blind_sig_params { + /* + * n — number of polynomial coefficients to work on, the computations + * will be performed in a ring modulo X^n + 1 + */ + ulong n; + /* + * q_bits — number of bits of a prime quotient for a modulo field to + * which polynomial coefficients will belong + */ + flint_bitcnt_t q_bits; + /* + * phi — a constant, affects completeness + */ + ulong phi; + /* + * psi — a constant, affects speed + */ + ulong psi; + /* + * d_s — maximum coefficient value for a polynomial in the private key + */ + ulong d_s; + /* + * m — number of polynomials in a private key, equal to the number of + * polynomials in the + */ + ulong m; + /* + * whether to print information about performed operations to stderr + */ + enum blind_sig_log_level log_level; +}; + +typedef struct blind_sig_params blind_sig_params_t[1]; + +typedef void (* commitment_function_t) (void * res, void const * data, + size_t data_len, + void const * randomness, ulong n); + +struct blind_sig_ctx { + ulong n; + ulong d_s; + mod_centered_0_ctx_t key_gen_ctx; + ulong m; + ulong phi; + ulong psi; + ulong d_alpha; + mod_centered_0_ctx_t alpha_gen_ctx; + ulong d_epsilon_star; + fmpz_t d_y; + mod_centered_0_ctx_t y_commitment_gen_ctx; + fmpz_t d_g_star; + fmpz_t d_beta; + mod_centered_0_ctx_t beta_gen_ctx; + fmpz_t d_g; + poly_ring_ctx_t poly_ring_ctx; + blind_sig_poly_vector_t public_homomorphism; + commitment_function_t public_commitment_function; + hash_function_t public_hash_function; + enum blind_sig_log_level log_level; +}; + +typedef struct blind_sig_ctx blind_sig_ctx_t[1]; + + + +/*** + *** Serializable structure definitions and their (de)serialization and + *** deinitialization function stubs. + ***/ + +#define FIELD(type, name) type name; + +#define SERIALIZABLE_STRUCT(name, fields) \ + struct name { fields }; \ + \ + typedef struct name name##_t[1]; \ + \ + size_t name##_serialize(FILE * stream, name##_t const obj, \ + blind_sig_ctx_t const ctx); \ + \ + void name##_file_serialize(const char * filename, name##_t const obj, \ + blind_sig_ctx_t const ctx); \ + \ + size_t name##_deserialize(FILE * stream, name##_t obj, \ + blind_sig_ctx_t const ctx); \ + \ + void name##_file_deserialize(const char * filename, name##_t obj, \ + blind_sig_ctx_t const ctx); \ + \ + void name##_clear(name##_t obj, blind_sig_ctx_t const ctx); + +#include "pqcrypto_blind_sig_serializable.c" + +#undef FIELD +#undef SERIALIZABLE_STRUCT + + + +/*** + *** Declarations related to context handling. + ***/ + +void blind_sig_ctx_init(blind_sig_ctx_t ctx, blind_sig_params_t const params); + +void blind_sig_ctx_clear(blind_sig_ctx_t ctx); + +#ifndef PQCRYPTO_BLIND_SIG_C +extern blind_sig_params_t blind_sig_params_current_III, blind_sig_params_toy; +#endif + + + +/*** + *** Logging facility. + ***/ + +int blind_sig_vlog(blind_sig_ctx_t const ctx, + enum blind_sig_log_level message_level, + char const * fmt, va_list ap); + +#define X(level) \ + inline static int blind_sig_log_##level(blind_sig_ctx_t const ctx, \ + char const * fmt, ...) { \ + va_list ap; \ + int result = 0; \ + \ + va_start(ap, fmt); \ + \ + result = blind_sig_vlog(ctx, BLIND_SIG_LOG_##level, fmt, ap); \ + \ + va_end(ap); \ + \ + return result; \ + } + +X(ERROR) +X(INFO_1_CONTROL) +X(INFO_2_PARAMETERS) +X(DEBUG_1_PHASES) +X(DEBUG_2_VALUES) + +#undef X + + + +/*** + *** Key handling function stubs. + ***/ + +void blind_sig_key_init_gen(blind_sig_priv_key_t priv_key, + blind_sig_pub_key_t pub_key, + blind_sig_ctx_t const ctx); + + + +/*** + *** Signature protocol-related function stubs. + ***/ + +void blind_sig_signer_state_init(blind_sig_signer_state_t state, + blind_sig_ctx_t const ctx); + +void blind_sig_user_state_init(blind_sig_user_state_t state, + blind_sig_ctx_t const ctx); + +void blind_sig_proto_p1_init_do(blind_sig_proto_p1_t result, + blind_sig_signer_state_t state, + blind_sig_ctx_t const ctx); + +void blind_sig_proto_p2_init_do(blind_sig_proto_p2_t result, + blind_sig_user_state_t state, + blind_sig_pub_key_t const pub_key, + void const * message_buf, size_t message_bytes, + blind_sig_proto_p1_t const p1_result, + unsigned long * retries_left, + blind_sig_ctx_t const ctx); + +void blind_sig_proto_p3_init_do(blind_sig_proto_p3_t result, + blind_sig_signer_state_t state, + blind_sig_priv_key_t const priv_key, + blind_sig_proto_p2_t const p2_result, + blind_sig_ctx_t const ctx); + +/* + * Also initializes and populates sig, but only of the signature could be + * successfully obtained (result->needs_restart == false). + */ + +void blind_sig_proto_p4_init_do(blind_sig_proto_p4_t result, + blind_sig_t sig, + blind_sig_user_state_t const state, + blind_sig_proto_p3_t const p3_result, + blind_sig_ctx_t const ctx); + +void blind_sig_proto_p5_init_do(blind_sig_proto_p5_t result, + blind_sig_signer_state_t state, + blind_sig_pub_key_t pub_key, + blind_sig_proto_p4_t const p4_result, + blind_sig_ctx_t const ctx); + +#endif /* PQCRYPTO_BLIND_SIG_H */ diff --git a/pqcrypto_blind_sig_example.c b/pqcrypto_blind_sig_example.c new file mode 100644 index 0000000..666dc95 --- /dev/null +++ b/pqcrypto_blind_sig_example.c @@ -0,0 +1,144 @@ +/* + * SPDX-License-Identifier: CC0-1.0 + * + * Copyright (C) 2025 W. Kosior <koszko@koszko.org> + */ + +#include <stdio.h> +#include <stdlib.h> + +#include "pqcrypto_blind_sig.h" + +static const char test_message[] = "This is a message to blind-sign."; + +#define RETRIES_MAX 1000U + +static void perform_signing(struct blind_sig_ctx * const ctx) { + unsigned long retries_left = RETRIES_MAX; + + blind_sig_priv_key_t priv_key; + blind_sig_pub_key_t pub_key; + blind_sig_signer_state_t signer_state; + blind_sig_user_state_t user_state; + + blind_sig_proto_p1_t p1_result; + blind_sig_proto_p2_t p2_result; + blind_sig_proto_p3_t p3_result; + blind_sig_proto_p4_t p4_result; + blind_sig_proto_p5_t p5_result; + + blind_sig_t sig; + + blind_sig_key_init_gen(priv_key, pub_key, ctx); + + blind_sig_signer_state_init(signer_state, ctx); + + blind_sig_user_state_init(user_state, ctx); + +p1: + blind_sig_proto_p1_init_do(p1_result, signer_state, ctx); + +/* p2: */ + blind_sig_proto_p2_init_do(p2_result, user_state, pub_key, test_message, + sizeof(test_message), p1_result, + &retries_left, ctx); + + if (!p2_result->ok) { + blind_sig_proto_p1_clear(p1_result, ctx); + blind_sig_proto_p2_clear(p2_result, ctx); + + goto too_many_retries; + } + +/* p3: */ + blind_sig_proto_p3_init_do(p3_result, signer_state, priv_key, + p2_result, ctx); + + if (!p3_result->ok) { + blind_sig_proto_p1_clear(p1_result, ctx); + blind_sig_proto_p2_clear(p2_result, ctx); + blind_sig_proto_p3_clear(p3_result, ctx); + + if (!(retries_left && retries_left--)) + goto too_many_retries; + + goto p1; + } + +/* p4: */ + blind_sig_proto_p4_init_do(p4_result, sig, user_state, test_message, + sizeof(test_message), p3_result, ctx); + +/* p5: */ + blind_sig_proto_p5_init_do(p5_result, signer_state, pub_key, p4_result, + ctx); + + if (!p5_result->ok) { + blind_sig_proto_p1_clear(p1_result, ctx); + blind_sig_proto_p2_clear(p2_result, ctx); + blind_sig_proto_p3_clear(p3_result, ctx); + blind_sig_proto_p4_clear(p4_result, ctx); + blind_sig_proto_p5_clear(p5_result, ctx); + + if (!(retries_left && retries_left--)) + goto too_many_retries; + + goto p1; + } + +/* out: */ + if (!p4_result->needs_restart) + blind_sig_clear(sig, ctx); + + blind_sig_priv_key_clear(priv_key, ctx); + + blind_sig_pub_key_clear(pub_key, ctx); + + blind_sig_signer_state_clear(signer_state, ctx); + + blind_sig_user_state_clear(user_state, ctx); + + blind_sig_proto_p1_clear(p1_result, ctx); + blind_sig_proto_p2_clear(p2_result, ctx); + blind_sig_proto_p3_clear(p3_result, ctx); + blind_sig_proto_p4_clear(p4_result, ctx); + blind_sig_proto_p5_clear(p5_result, ctx); + + return; + +too_many_retries: + fprintf(stderr, "Too many retries.\n"); +}; + +int main(const int argc, const char* const* const argv) { + blind_sig_params_t params; + blind_sig_ctx_t ctx; + + (void) argc; + (void) argv; + + fprintf(stderr, "Preparing blind signature context (\"Current III\" set" + " from Rückert's paper).\n"); + + *params = *blind_sig_params_current_III; + + /* fprintf(stderr, "Preparing blind signature context (toy set of" */ + /* " parameters).\n"); */ + + /* *params = *blind_sig_params_toy; */ + + blind_sig_ctx_init(ctx, params); + + fprintf(stderr, "Making a test signature for ASCII buffer: \"%s\".\n", + test_message); + + perform_signing(ctx); + + fprintf(stderr, "Done, cleaning up.\n"); + + blind_sig_ctx_clear(ctx); + + flint_cleanup(); + + return EXIT_SUCCESS; +} diff --git a/pqcrypto_blind_sig_serializable.c b/pqcrypto_blind_sig_serializable.c new file mode 100644 index 0000000..38fd887 --- /dev/null +++ b/pqcrypto_blind_sig_serializable.c @@ -0,0 +1,57 @@ +/* + * SPDX-License-Identifier: CC0-1.0 + * + * Copyright (C) 2025 W. Kosior <koszko@koszko.org> + */ + +SERIALIZABLE_STRUCT(blind_sig, + FIELD(blind_sig_message_t, message) + FIELD(blind_sig_n_bit_buf_t, randomness) + FIELD(blind_sig_poly_vector_t, z) + FIELD(fmpz_poly_t, epsilon)) + +SERIALIZABLE_STRUCT(blind_sig_priv_key, + FIELD(blind_sig_poly_vector_t, key_polys)) + +SERIALIZABLE_STRUCT(blind_sig_pub_key, + FIELD(fmpz_poly_t, key_poly)) + +SERIALIZABLE_STRUCT(blind_sig_signer_state, + FIELD(blind_sig_poly_vector_t, y_commitment_random) + FIELD(fmpz_poly_t, y_commitment) + FIELD(blind_sig_poly_vector_t, z_star) + FIELD(fmpz_poly_t, epsilon_star)) + +SERIALIZABLE_STRUCT(blind_sig_user_state, + FIELD(blind_sig_message_t, message) + FIELD(blind_sig_n_bit_buf_t, randomness) + FIELD(blind_sig_n_bit_buf_t, commitment) + FIELD(fmpz_poly_t, alpha) + FIELD(blind_sig_poly_vector_t, beta) + FIELD(fmpz_poly_t, epsilon) + FIELD(fmpz_poly_t, epsilon_star)) + +SERIALIZABLE_STRUCT(blind_sig_proto_p1, + FIELD(fmpz_poly_t, y_commitment)) + +SERIALIZABLE_STRUCT(blind_sig_proto_p2, + FIELD(bool, ok) + FIELD(fmpz_poly_t, epsilon_star)) + +SERIALIZABLE_STRUCT(blind_sig_proto_p3, + FIELD(bool, ok) + FIELD(blind_sig_poly_vector_t, z_star)) + +SERIALIZABLE_STRUCT(blind_sig_proto_p4, + FIELD(bool, needs_restart) + FIELD(blind_sig_n_bit_buf_t, commitment) + FIELD(fmpz_poly_t, alpha) + FIELD(blind_sig_poly_vector_t, beta) + FIELD(fmpz_poly_t, epsilon)) + +SERIALIZABLE_STRUCT(blind_sig_proto_p5, + FIELD(bool, ok) + FIELD(blind_sig_poly_vector_t, y_commitment_random) + FIELD(fmpz_poly_t, y_commitment) + FIELD(fmpz_poly_t, epsilon_star) + FIELD(blind_sig_poly_vector_t, z_star)) diff --git a/pqcrypto_commitment_shake256.c b/pqcrypto_commitment_shake256.c new file mode 100644 index 0000000..f843205 --- /dev/null +++ b/pqcrypto_commitment_shake256.c @@ -0,0 +1,30 @@ +#include "pqcrypto_bitcnt_bytes.h" +#include "pqcrypto_commitment_shake256.h" + +#include <gcrypt.h> + +void commitment_shake256(void * res, void const * data, size_t data_bytes, + void const * randomness, ulong n) { + ulong randomness_bytes = BITCNT_BYTES(n); + ulong commitment_bytes = randomness_bytes; + gcry_md_hd_t hd; + + if (!n) + abort(); + + if (gcry_md_open(&hd, GCRY_MD_SHAKE256, GCRY_MD_FLAG_SECURE) != + GPG_ERR_NO_ERROR) + abort(); + + gcry_md_write(hd, data, data_bytes); + gcry_md_write(hd, randomness, randomness_bytes); + + gcry_md_extract(hd, 0, res, commitment_bytes); + + gcry_md_close(hd); + + if (n % 8) { + ((unsigned char *) res)[commitment_bytes - 1] &= + (1 << (n % 8)) - 1; + } +} diff --git a/pqcrypto_commitment_shake256.h b/pqcrypto_commitment_shake256.h new file mode 100644 index 0000000..ae47d26 --- /dev/null +++ b/pqcrypto_commitment_shake256.h @@ -0,0 +1,10 @@ +#ifndef PQCRYPTO_COMMITMENT_SHAKE256_H +#define PQCRYPTO_COMMITMENT_SHAKE256_H + +#include <stdlib.h> +#include <flint/fmpz.h> + +void commitment_shake256(void * res, void const * data, size_t data_bytes, + void const * randomness, ulong n); + +#endif /* PQCRYPTO_COMMITMENT_SHAKE256_H */ diff --git a/pqcrypto_hash.h b/pqcrypto_hash.h new file mode 100644 index 0000000..504a7e6 --- /dev/null +++ b/pqcrypto_hash.h @@ -0,0 +1,21 @@ +/* + * SPDX-License-Identifier: CC0-1.0 + * + * Copyright (C) 2025 W. Kosior <koszko@koszko.org> + */ + +#ifndef PQCRYPTO_HASH_H +#define PQCRYPTO_HASH_H + +#include <stdlib.h> + +struct hash_function { + void * (* make)(void); + void (* free)(void * state); + void (* feed)(void * state, void const * data, size_t data_bytes); + int (* getc)(void * state); +}; + +typedef struct hash_function hash_function_t[1]; + +#endif /* PQCRYPTO_HASH_H */ diff --git a/pqcrypto_hash_shake256.c b/pqcrypto_hash_shake256.c new file mode 100644 index 0000000..6be917f --- /dev/null +++ b/pqcrypto_hash_shake256.c @@ -0,0 +1,72 @@ +/* + * SPDX-License-Identifier: CC0-1.0 + * + * Copyright (C) 2025 W. Kosior <koszko@koszko.org> + */ + +#include <stdbool.h> + +#include <flint/fmpz.h> +#include <gcrypt.h> + +#define PQCRYPTO_HASH_SHAKE256_C +#include "pqcrypto_hash_shake256.h" + +struct hash_shake256_state { + bool finished; + gcry_md_hd_t hd; +}; + +static void * hash_shake256_make(void) { + struct hash_shake256_state * state = + malloc(sizeof(struct hash_shake256_state)); + + if (!state) + abort(); + + if (gcry_md_open(&state->hd, GCRY_MD_SHAKE256, GCRY_MD_FLAG_SECURE) != + GPG_ERR_NO_ERROR) + abort(); + + state->finished = false; + + return state; +} + +static void hash_shake256_free(void * state) { + struct hash_shake256_state * state_ = state; + + gcry_md_close(state_->hd); + + free(state_); +} + +static void hash_shake256_feed(void * state, void const * data, + size_t data_bytes) { + struct hash_shake256_state * state_ = state; + + if (state_->finished) + abort(); + + gcry_md_write(state_->hd, data, data_bytes); +} + +static int hash_shake256_getc(void * state) { + struct hash_shake256_state * state_ = state; + unsigned char extracted; + + state_->finished = true; + + gcry_md_extract(state_->hd, 0, &extracted, 1); + + return extracted; +} + +hash_function_t hash_function_shake256 = { + { + .make = hash_shake256_make, + .free = hash_shake256_free, + .feed = hash_shake256_feed, + .getc = hash_shake256_getc, + } +}; diff --git a/pqcrypto_hash_shake256.h b/pqcrypto_hash_shake256.h new file mode 100644 index 0000000..2f570a0 --- /dev/null +++ b/pqcrypto_hash_shake256.h @@ -0,0 +1,16 @@ +/* + * SPDX-License-Identifier: CC0-1.0 + * + * Copyright (C) 2025 W. Kosior <koszko@koszko.org> + */ + +#ifndef PQCRYPTO_HASH_SHAKE256_H +#define PQCRYPTO_HASH_SHAKE256_H + +#include "pqcrypto_hash.h" + +#ifndef PQCRYPTO_HASH_SHAKE256_C +extern hash_function_t hash_function_shake256; +#endif + +#endif /* PQCRYPTO_HASH_SHAKE256_H */ diff --git a/pqcrypto_poly.c b/pqcrypto_poly.c new file mode 100644 index 0000000..fcb619b --- /dev/null +++ b/pqcrypto_poly.c @@ -0,0 +1,236 @@ +/* + * SPDX-License-Identifier: CC0-1.0 + * + * Copyright (C) 2024, 2025 W. Kosior <koszko@koszko.org> + */ + +#include <stdbool.h> +#include <stdlib.h> +#include <sys/types.h> + +#include <flint/flint.h> +#include <flint/fmpz_mod.h> + +#include "pqcrypto_poly.h" +#include "pqcrypto_prng_getrandom.h" + + + +/*** + *** Modulo operations. + ***/ + +void mod_c0_ctx_init(mod_centered_0_ctx_t ctx, fmpz_t divisor) { + fmpz_init_set(ctx[0].divisor, divisor); + + fmpz_init(ctx[0].range_max); + fmpz_sub_ui(ctx[0].range_max, ctx[0].divisor, 1); + + fmpz_tdiv_q_2exp(ctx[0].range_max, ctx[0].range_max, 1); +} + +void mod_c0_ctx_clear(mod_centered_0_ctx_t ctx) { + fmpz_clear(ctx[0].divisor); + fmpz_clear(ctx[0].range_max); +} + +void mod_c0(fmpz_t value, mod_centered_0_ctx_t const ctx) { + fmpz_add(value, value, ctx[0].range_max); + fmpz_fdiv_r(value, value, ctx[0].divisor); + fmpz_sub(value, value, ctx[0].range_max); +} + +void mod_c0_ctx_init_set(mod_centered_0_ctx_t dst_ctx, + mod_centered_0_ctx_t const src_ctx) { + fmpz_init_set(dst_ctx[0].divisor, src_ctx[0].divisor); + fmpz_init_set(dst_ctx[0].range_max, src_ctx[0].range_max); +} + +void mod_c0_prng(fmpz_t value, mod_centered_0_ctx_t const ctx, + prng_t prng, void * prng_state) { + flint_bitcnt_t mod_bits_count = fmpz_bits(ctx[0].divisor); + flint_bitcnt_t high_limb_bits_count = mod_bits_count % FLINT_BITS; + ulong mod_limbs_count = + mod_bits_count / FLINT_BITS + !!high_limb_bits_count; + ulong high_limb_bit_mask = + (((unsigned long long) 1) << high_limb_bits_count) - 1; + size_t rand_bytes_count = mod_limbs_count * sizeof(ulong); + ulong * rand_limbs = malloc(rand_bytes_count); + + if (!rand_limbs) + abort(); + + do { + prng(rand_limbs, rand_bytes_count, prng_state); + + if (high_limb_bits_count) + rand_limbs[mod_limbs_count - 1] &= high_limb_bit_mask; + + fmpz_set_ui_array(value, rand_limbs, mod_limbs_count); + } while (fmpz_cmp(value, ctx[0].divisor) >= 0); + + fmpz_sub(value, value, ctx[0].range_max); + + free(rand_limbs); +} + +void mod_c0_rand(fmpz_t value, mod_centered_0_ctx_t const ctx) { + mod_c0_prng(value, ctx, prng_getrandom, NULL); +} + + + +/*** + *** Simple operations on polynomials. + ***/ + +void poly_prng_mod_c0(fmpz_poly_t res, prng_t prng, void * prng_state, + ulong coef_count, mod_centered_0_ctx_t const ctx) { + fmpz_t new_coef_value; + + if (coef_count > (ulong) WORD_MAX) + abort(); + + fmpz_init(new_coef_value); + + fmpz_poly_realloc(res, coef_count); + + for (ulong coef_idx = 0; coef_idx < coef_count; coef_idx++) { + mod_c0_prng(new_coef_value, ctx, prng, prng_state); + fmpz_poly_set_coeff_fmpz(res, coef_idx, new_coef_value); + } + + fmpz_clear(new_coef_value); +} + +void poly_rand_mod_c0(fmpz_poly_t res, ulong coef_count, + mod_centered_0_ctx_t const ctx) { + poly_prng_mod_c0(res, prng_getrandom, NULL, coef_count, ctx); +} + +bool poly_all_abs_leq(fmpz_poly_struct const * poly, fmpz const * max_coef) { + ulong length = fmpz_poly_length(poly); + fmpz_t coef; + bool result = true; + + fmpz_init(coef); + + for (ulong i = 0; i < length; i++) { + fmpz_poly_get_coeff_fmpz(coef, poly, i); + fmpz_abs(coef, coef); + if (fmpz_cmp(coef, max_coef) > 0) { + result = false; + break; + } + } + + fmpz_clear(coef); + + return result; +} + +bool poly_all_abs_leq_ui(fmpz_poly_struct const * poly, ulong max_coef) { + fmpz_t max_coef_fmpz; + bool result; + + fmpz_init_set_ui(max_coef_fmpz, max_coef); + + result = poly_all_abs_leq(poly, max_coef_fmpz); + + fmpz_clear(max_coef_fmpz); + + return result; +} + + + +/*** + *** Operations in polynomial rings. + ***/ + +void poly_ring_ctx_init(poly_ring_ctx_t ctx, mod_centered_0_ctx_t mod_ctx, + ulong divisor_degree) { + if (divisor_degree > (ulong) WORD_MAX) + abort(); + + mod_c0_ctx_init_set(ctx[0].mod_ctx, mod_ctx); + ctx[0].divisor_degree = divisor_degree; +} + +void poly_ring_ctx_clear(poly_ring_ctx_t ctx) { + mod_c0_ctx_clear(ctx[0].mod_ctx); +} + +void poly_to_ring(fmpz_poly_t poly, poly_ring_ctx_t const ctx) { + ulong degree = fmpz_poly_degree(poly); + fmpz_t new_coef_value; + + fmpz_init(new_coef_value); + + for (ulong coef_idx = 0; coef_idx < ctx[0].divisor_degree; coef_idx++) { + int sign = 1; + ulong higher_coef_idx = coef_idx; + + fmpz_poly_get_coeff_fmpz(new_coef_value, poly, coef_idx); + + /* + * Polynomial division by X^m+1 can be achieved by substituting + * -1 for X^m. + */ + do { + fmpz const * higher_coef; + + sign *= -1; + + if (UWORD_MAX - ctx[0].divisor_degree < higher_coef_idx) + break; + + higher_coef_idx += ctx[0].divisor_degree; + + if (higher_coef_idx > degree) + break; + + higher_coef = + fmpz_poly_get_coeff_ptr(poly, higher_coef_idx); + + (sign == 1 ? &fmpz_add : &fmpz_sub) + (new_coef_value, new_coef_value, higher_coef); + } while (true); + + mod_c0(new_coef_value, ctx[0].mod_ctx); + fmpz_poly_set_coeff_fmpz(poly, coef_idx, new_coef_value); + } + + if (degree >= ctx[0].divisor_degree) + fmpz_poly_realloc(poly, ctx[0].divisor_degree); + + fmpz_clear(new_coef_value); +} + +void poly_mul_in_ring(fmpz_poly_t res, fmpz_poly_t const poly1, + fmpz_poly_t const poly2, poly_ring_ctx_t const ctx) { + fmpz_poly_mul(res, poly1, poly2); + poly_to_ring(res, ctx); +} + +void poly_add_in_ring(fmpz_poly_t res, fmpz_poly_t const poly1, + fmpz_poly_t const poly2, poly_ring_ctx_t const ctx) { + fmpz_poly_add(res, poly1, poly2); + poly_to_ring(res, ctx); +} + +void poly_sub_in_ring(fmpz_poly_t res, fmpz_poly_t const poly1, + fmpz_poly_t const poly2, poly_ring_ctx_t const ctx) { + fmpz_poly_sub(res, poly1, poly2); + poly_to_ring(res, ctx); +} + +void poly_prng_in_ring(fmpz_poly_t res, prng_t prng, void * prng_state, + poly_ring_ctx_t const ctx) { + poly_prng_mod_c0(res, prng, prng_state, ctx[0].divisor_degree, + ctx[0].mod_ctx); +} + +void poly_rand_in_ring(fmpz_poly_t res, poly_ring_ctx_t const ctx) { + poly_prng_in_ring(res, prng_getrandom, NULL, ctx); +} diff --git a/pqcrypto_poly.h b/pqcrypto_poly.h new file mode 100644 index 0000000..f828c24 --- /dev/null +++ b/pqcrypto_poly.h @@ -0,0 +1,110 @@ +/* + * SPDX-License-Identifier: CC0-1.0 + * + * Copyright (C) 2024, 2025 W. Kosior <koszko@koszko.org> + */ + +#ifndef PQCRYPTO_POLY_H +#define PQCRYPTO_POLY_H + +#include <stdbool.h> + +#include <flint/fmpz.h> +#include <flint/fmpz_poly.h> + +#include "pqcrypto_prng.h" + + + +/*** + *** Modulo operations. + ***/ + +/* + * FLINT seems to assume all modulo operations are performed on integers in + * range [0, n-1]. Here we provide a facility for performing modulo operations + * on big integers in range [-(n-1)/2, (n-1)/2]. + */ + +struct mod_centered_0_ctx { + fmpz_t divisor; + fmpz_t range_max; +}; + +typedef struct mod_centered_0_ctx mod_centered_0_ctx_t[1]; + +void mod_c0_ctx_init(mod_centered_0_ctx_t ctx, fmpz_t divisor); + +void mod_c0_ctx_clear(mod_centered_0_ctx_t ctx); + +void mod_c0(fmpz_t value, mod_centered_0_ctx_t const ctx); + +void mod_c0_ctx_init_set(mod_centered_0_ctx_t dst_ctx, + mod_centered_0_ctx_t const src_ctx); + +void mod_c0_prng(fmpz_t value, mod_centered_0_ctx_t const ctx, + prng_t prng, void * state); + +void mod_c0_rand(fmpz_t value, mod_centered_0_ctx_t const ctx); + + + +/*** + *** Simple operations on polynomials. + ***/ + +void poly_prng_mod_c0(fmpz_poly_t res, prng_t prng, void * prng_state, + ulong coef_count, mod_centered_0_ctx_t const ctx); + +void poly_rand_mod_c0(fmpz_poly_t res, ulong coef_count, + mod_centered_0_ctx_t const ctx); + +bool poly_all_abs_leq(fmpz_poly_struct const * poly, fmpz const * max_coef); + +bool poly_all_abs_leq_ui(fmpz_poly_struct const * poly, ulong max_coef); + + + +/*** + *** Operations in polynomial rings. + ***/ + +/* + * Here we provide a facility for performing operations in polynomial rings + * modulo X^m+1 over fields of integers modulo n shifted to range [-(n-1)/2, + * (n-1)/2]. + */ + +struct poly_ring_ctx { + mod_centered_0_ctx_t mod_ctx; + ulong divisor_degree; +}; + +typedef struct poly_ring_ctx poly_ring_ctx_t[1]; + +void poly_ring_ctx_init(poly_ring_ctx_t ctx, mod_centered_0_ctx_t mod_ctx, + ulong divisor_degree); + +void poly_ring_ctx_clear(poly_ring_ctx_t ctx); + +/* + * Applies modulo operations to make poly a member of the ring designated by + * ctx. + */ +void poly_to_ring(fmpz_poly_t poly, poly_ring_ctx_t const ctx); + +void poly_mul_in_ring(fmpz_poly_t res, fmpz_poly_t const poly1, + fmpz_poly_t const poly2, poly_ring_ctx_t const ctx); + +void poly_add_in_ring(fmpz_poly_t res, fmpz_poly_t const poly1, + fmpz_poly_t const poly2, poly_ring_ctx_t const ctx); + +void poly_sub_in_ring(fmpz_poly_t res, fmpz_poly_t const poly1, + fmpz_poly_t const poly2, poly_ring_ctx_t const ctx); + +void poly_prng_in_ring(fmpz_poly_t res, prng_t prng, void * prng_state, + poly_ring_ctx_t const ctx); + +void poly_rand_in_ring(fmpz_poly_t res, poly_ring_ctx_t const ctx); + +#endif /* PQCRYPTO_POLY_H */ diff --git a/pqcrypto_poly_example.c b/pqcrypto_poly_example.c new file mode 100644 index 0000000..74d82d2 --- /dev/null +++ b/pqcrypto_poly_example.c @@ -0,0 +1,167 @@ +/* + * SPDX-License-Identifier: CC0-1.0 + * + * Copyright (C) 2024 W. Kosior <koszko@koszko.org> + */ + +#include <stdbool.h> +#include <stdio.h> +#include <stdlib.h> + +#include "pqcrypto_poly.h" + +/* Exponent for Mersenne prime, for testing. */ +#define TEST_MERSENNE_EXPONENT 7 /* 89 */ + +static void marsenne_prime_init(fmpz_t prime, const ulong exponent) { + fmpz_init(prime); + + fmpz_ui_pow_ui(prime, 2, exponent); + fmpz_sub_ui(prime, prime, 1); +} + +static void init_read_poly(fmpz_poly_t poly, FILE * file) { + bool first = true; + fmpz_t coef; + + fmpz_poly_init(poly); + fmpz_init(coef); + + for (ulong exponent = 0;; exponent++) { + int separator_char; + + if (first) { + first = false; + } else { + separator_char = getc(file); + + if (separator_char == '\n') + break; + + if (separator_char != ' ') + goto error; + } + + if (fmpz_fread(file, coef) < 0) + goto error; + + fmpz_poly_set_coeff_fmpz(poly, exponent, coef); + } + + fmpz_clear(coef); + return; + +error: + fprintf(stderr, "Error reading polynomial.\n"); + abort(); +} + +int main(const int argc, const char* const* const argv) { + fmpz_t prime; /* integer for modulo operations */ + mod_centered_0_ctx_t mod_ctx; + + (void) argc; + (void) argv; + + /* + * Marsenne primes are used just for testing. Cryptographic algorithm + * will use different ones. + */ + marsenne_prime_init(prime, TEST_MERSENNE_EXPONENT); + + printf("Prime used for modulo operations: "); + fmpz_fprint(stdout, prime); + putchar('\n'); + + mod_c0_ctx_init(mod_ctx, prime); + + { /* Experiment 1 — modulo addition */ + fmpz_t num1, num2, num_sum; + + fmpz_init_set_ui(num1, 55); + fmpz_init_set_ui(num2, 31); + fmpz_init(num_sum); + + fmpz_fprint(stdout, num1); + printf(" + "); + fmpz_fprint(stdout, num2); + printf(" mod [-"); + fmpz_fprint(stdout, mod_ctx[0].range_max); + putchar(','); + fmpz_fprint(stdout, mod_ctx[0].range_max); + printf("] = "); + + fmpz_add(num_sum, num1, num2); + mod_c0(num_sum, mod_ctx); + fmpz_fprint(stdout, num_sum); + putchar('\n'); + + fmpz_clear(num1); + fmpz_clear(num2); + fmpz_clear(num_sum); + } /* End of experiment 1 */ + + { /* Experiment 2 */ + fmpz_poly_t poly1, poly2, poly_computed; + slong divisor_degree; + poly_ring_ctx_t poly_ring_ctx; + + printf("Give first polynomial for the experiment:\n"); + init_read_poly(poly1, stdin); + + printf("Read polynomial: "); + fmpz_poly_print_pretty(poly1, "x"); + putchar('\n'); + + printf("Give second polynomial for the experiment:\n"); + init_read_poly(poly2, stdin); + + printf("Read polynomial: "); + fmpz_poly_print_pretty(poly2, "x"); + putchar('\n'); + + fmpz_poly_init(poly_computed); + + printf("Normal product of polynomials:\n"); + fmpz_poly_mul(poly_computed, poly1, poly2); + fmpz_poly_print_pretty(poly_computed, "x"); + putchar('\n'); + + printf("Normal sum of polynomials:\n"); + fmpz_poly_add(poly_computed, poly1, poly2); + fmpz_poly_print_pretty(poly_computed, "x"); + putchar('\n'); + + printf("Give the degree m of X^m+1 polynomial to be used as "); + printf("divisor in the ring:\n"); + if (flint_scanf("%wd", &divisor_degree) < 1 || + divisor_degree < 1) { + fprintf(stderr, "Bad divisor.\n"); + abort(); + } + poly_ring_ctx_init(poly_ring_ctx, mod_ctx, divisor_degree); + + printf("Product of polynomials in the ring:\n"); + poly_mul_in_ring(poly_computed, poly1, poly2, poly_ring_ctx); + fmpz_poly_print_pretty(poly_computed, "x"); + putchar('\n'); + + printf("Sum of polynomials in the ring:\n"); + poly_add_in_ring(poly_computed, poly1, poly2, poly_ring_ctx); + fmpz_poly_print_pretty(poly_computed, "x"); + putchar('\n'); + + fmpz_poly_clear(poly1); + fmpz_poly_clear(poly2); + fmpz_poly_clear(poly_computed); + + poly_ring_ctx_clear(poly_ring_ctx); + } /* End of experiment 2 */ + + mod_c0_ctx_clear(mod_ctx); + fmpz_clear(prime); + + flint_cleanup(); + + return EXIT_SUCCESS; +} diff --git a/pqcrypto_prng.h b/pqcrypto_prng.h new file mode 100644 index 0000000..16159a8 --- /dev/null +++ b/pqcrypto_prng.h @@ -0,0 +1,14 @@ +/* + * SPDX-License-Identifier: CC0-1.0 + * + * Copyright (C) 2025 W. Kosior <koszko@koszko.org> + */ + +#ifndef PQCRYPTO_PRNG_H +#define PQCRYPTO_PRNG_H + +#include <stdlib.h> + +typedef void (*prng_t) (void * buf, size_t buflen, void * state); + +#endif /* PQCRYPTO_PRNG_H */ diff --git a/pqcrypto_prng_getrandom.c b/pqcrypto_prng_getrandom.c new file mode 100644 index 0000000..da3ce1a --- /dev/null +++ b/pqcrypto_prng_getrandom.c @@ -0,0 +1,19 @@ +/* + * SPDX-License-Identifier: CC0-1.0 + * + * Copyright (C) 2025 W. Kosior <koszko@koszko.org> + */ + +#include <stdio.h> +#include <sys/random.h> + +#include "pqcrypto_prng_getrandom.h" + +void prng_getrandom(void * buf, size_t buf_len, void * state) { + (void) state; + + if (getrandom(buf, buf_len, 0) != (ssize_t) buf_len) { + fprintf(stderr, "Failed to get %zu random bytes.\n", buf_len); + abort(); + } +} diff --git a/pqcrypto_prng_getrandom.h b/pqcrypto_prng_getrandom.h new file mode 100644 index 0000000..fd51c4e --- /dev/null +++ b/pqcrypto_prng_getrandom.h @@ -0,0 +1,14 @@ +/* + * SPDX-License-Identifier: CC0-1.0 + * + * Copyright (C) 2025 W. Kosior <koszko@koszko.org> + */ + +#ifndef PQCRYPTO_PRNG_GETRANDOM_H +#define PQCRYPTO_PRNG_GETRANDOM_H + +#include <stdlib.h> + +void prng_getrandom(void * buf, size_t buf_len, void * state); + +#endif /* PQCRYPTO_PRNG_GETRANDOM_H */ diff --git a/pqcrypto_prng_seeded.c b/pqcrypto_prng_seeded.c new file mode 100644 index 0000000..c4d43fe --- /dev/null +++ b/pqcrypto_prng_seeded.c @@ -0,0 +1,41 @@ +/* + * SPDX-License-Identifier: CC0-1.0 + * + * Copyright (C) 2025 W. Kosior <koszko@koszko.org> + */ + +#include <stdio.h> + +#include <gcrypt.h> + +#include "pqcrypto_prng_seeded.h" + +void prng_seeded_state_init(prng_seeded_state_t state, + void const * seed, size_t seed_len) { + state[0].seed = seed; + state[0].seed_len = seed_len; + state[0].iterator = 0; +} + +void prng_seeded_state_clear(prng_seeded_state_t state) { + (void) state; +} + +void prng_seeded(void * buf, size_t buf_len, void * state) { + struct prng_seeded_state * state_ = state; + char pseudo_salt[9]; + + if (state_->iterator > 99999999UL) + abort(); + + sprintf(pseudo_salt, "%08lu", state_->iterator++); + + if (gcry_kdf_derive(state_->seed, state_->seed_len, + GCRY_KDF_SALTED_S2K, GCRY_MD_SHA256, + pseudo_salt, 8, 1, + buf_len, buf)) { + fprintf(stderr, "Failed to derive %zu pseudorandom bytes.\n", + buf_len); + abort(); + } +} diff --git a/pqcrypto_prng_seeded.h b/pqcrypto_prng_seeded.h new file mode 100644 index 0000000..1ca559f --- /dev/null +++ b/pqcrypto_prng_seeded.h @@ -0,0 +1,27 @@ +/* + * SPDX-License-Identifier: CC0-1.0 + * + * Copyright (C) 2025 W. Kosior <koszko@koszko.org> + */ + +#ifndef PQCRYPTO_PRNG_SEEDED_H +#define PQCRYPTO_PRNG_SEEDED_H + +#include <stdlib.h> + +struct prng_seeded_state { + void const * seed; + size_t seed_len; + unsigned long iterator; +}; + +typedef struct prng_seeded_state prng_seeded_state_t[1]; + +void prng_seeded_state_init(prng_seeded_state_t state, + void const * material, size_t material_len); + +void prng_seeded(void * buf, size_t buflen, void * state); + +void prng_seeded_state_clear(prng_seeded_state_t state); + +#endif /* PQCRYPTO_PRNG_SEEDED_H */ |