diff options
| -rw-r--r-- | .gitignore | 6 | ||||
| -rw-r--r-- | .reuse/dep5 | 10 | ||||
| -rw-r--r-- | LICENSES/CC0-1.0.txt | 121 | ||||
| -rw-r--r-- | Makefile | 15 | ||||
| -rw-r--r-- | README.md | 23 | ||||
| -rw-r--r-- | README.md.license | 3 | ||||
| -rwxr-xr-x | dev-shell | 10 | ||||
| -rw-r--r-- | poly_mul.c | 278 |
8 files changed, 466 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..3fdc49e --- /dev/null +++ b/.gitignore @@ -0,0 +1,6 @@ +# SPDX-License-Identifier: CC0-1.0 +# +# Copyright (C) 2024 W. Kosior <koszko@koszko.org> + +poly_mul +*.o diff --git a/.reuse/dep5 b/.reuse/dep5 new file mode 100644 index 0000000..b8585cb --- /dev/null +++ b/.reuse/dep5 @@ -0,0 +1,10 @@ +Format: https://www.debian.org/doc/packaging-manuals/copyright-format/1.0/ +Upstream-Name: Post-quantum blind signatures implementation +Upstream-Contact: W. Kosior <koszko@koszko.org> +Source: https://git.koszko.org/pq-blind-sigs-impl + +# Sample paragraph, commented out: +# +# Files: src/* +# Copyright: $YEAR $NAME <$CONTACT> +# License: ... diff --git a/LICENSES/CC0-1.0.txt b/LICENSES/CC0-1.0.txt new file mode 100644 index 0000000..0e259d4 --- /dev/null +++ b/LICENSES/CC0-1.0.txt @@ -0,0 +1,121 @@ +Creative Commons Legal Code + +CC0 1.0 Universal + + CREATIVE COMMONS CORPORATION IS NOT A LAW FIRM AND DOES NOT PROVIDE + LEGAL SERVICES. DISTRIBUTION OF THIS DOCUMENT DOES NOT CREATE AN + ATTORNEY-CLIENT RELATIONSHIP. CREATIVE COMMONS PROVIDES THIS + INFORMATION ON AN "AS-IS" BASIS. CREATIVE COMMONS MAKES NO WARRANTIES + REGARDING THE USE OF THIS DOCUMENT OR THE INFORMATION OR WORKS + PROVIDED HEREUNDER, AND DISCLAIMS LIABILITY FOR DAMAGES RESULTING FROM + THE USE OF THIS DOCUMENT OR THE INFORMATION OR WORKS PROVIDED + HEREUNDER. + +Statement of Purpose + +The laws of most jurisdictions throughout the world automatically confer +exclusive Copyright and Related Rights (defined below) upon the creator +and subsequent owner(s) (each and all, an "owner") of an original work of +authorship and/or a database (each, a "Work"). + +Certain owners wish to permanently relinquish those rights to a Work for +the purpose of contributing to a commons of creative, cultural and +scientific works ("Commons") that the public can reliably and without fear +of later claims of infringement build upon, modify, incorporate in other +works, reuse and redistribute as freely as possible in any form whatsoever +and for any purposes, including without limitation commercial purposes. +These owners may contribute to the Commons to promote the ideal of a free +culture and the further production of creative, cultural and scientific +works, or to gain reputation or greater distribution for their Work in +part through the use and efforts of others. + +For these and/or other purposes and motivations, and without any +expectation of additional consideration or compensation, the person +associating CC0 with a Work (the "Affirmer"), to the extent that he or she +is an owner of Copyright and Related Rights in the Work, voluntarily +elects to apply CC0 to the Work and publicly distribute the Work under its +terms, with knowledge of his or her Copyright and Related Rights in the +Work and the meaning and intended legal effect of CC0 on those rights. + +1. Copyright and Related Rights. A Work made available under CC0 may be +protected by copyright and related or neighboring rights ("Copyright and +Related Rights"). Copyright and Related Rights include, but are not +limited to, the following: + + i. the right to reproduce, adapt, distribute, perform, display, + communicate, and translate a Work; + ii. moral rights retained by the original author(s) and/or performer(s); +iii. publicity and privacy rights pertaining to a person's image or + likeness depicted in a Work; + iv. rights protecting against unfair competition in regards to a Work, + subject to the limitations in paragraph 4(a), below; + v. rights protecting the extraction, dissemination, use and reuse of data + in a Work; + vi. database rights (such as those arising under Directive 96/9/EC of the + European Parliament and of the Council of 11 March 1996 on the legal + protection of databases, and under any national implementation + thereof, including any amended or successor version of such + directive); and +vii. other similar, equivalent or corresponding rights throughout the + world based on applicable law or treaty, and any national + implementations thereof. + +2. Waiver. To the greatest extent permitted by, but not in contravention +of, applicable law, Affirmer hereby overtly, fully, permanently, +irrevocably and unconditionally waives, abandons, and surrenders all of +Affirmer's Copyright and Related Rights and associated claims and causes +of action, whether now known or unknown (including existing as well as +future claims and causes of action), in the Work (i) in all territories +worldwide, (ii) for the maximum duration provided by applicable law or +treaty (including future time extensions), (iii) in any current or future +medium and for any number of copies, and (iv) for any purpose whatsoever, +including without limitation commercial, advertising or promotional +purposes (the "Waiver"). Affirmer makes the Waiver for the benefit of each +member of the public at large and to the detriment of Affirmer's heirs and +successors, fully intending that such Waiver shall not be subject to +revocation, rescission, cancellation, termination, or any other legal or +equitable action to disrupt the quiet enjoyment of the Work by the public +as contemplated by Affirmer's express Statement of Purpose. + +3. Public License Fallback. Should any part of the Waiver for any reason +be judged legally invalid or ineffective under applicable law, then the +Waiver shall be preserved to the maximum extent permitted taking into +account Affirmer's express Statement of Purpose. In addition, to the +extent the Waiver is so judged Affirmer hereby grants to each affected +person a royalty-free, non transferable, non sublicensable, non exclusive, +irrevocable and unconditional license to exercise Affirmer's Copyright and +Related Rights in the Work (i) in all territories worldwide, (ii) for the +maximum duration provided by applicable law or treaty (including future +time extensions), (iii) in any current or future medium and for any number +of copies, and (iv) for any purpose whatsoever, including without +limitation commercial, advertising or promotional purposes (the +"License"). The License shall be deemed effective as of the date CC0 was +applied by Affirmer to the Work. Should any part of the License for any +reason be judged legally invalid or ineffective under applicable law, such +partial invalidity or ineffectiveness shall not invalidate the remainder +of the License, and in such case Affirmer hereby affirms that he or she +will not (i) exercise any of his or her remaining Copyright and Related +Rights in the Work or (ii) assert any associated claims and causes of +action with respect to the Work, in either case contrary to Affirmer's +express Statement of Purpose. + +4. Limitations and Disclaimers. + + a. No trademark or patent rights held by Affirmer are waived, abandoned, + surrendered, licensed or otherwise affected by this document. + b. Affirmer offers the Work as-is and makes no representations or + warranties of any kind concerning the Work, express, implied, + statutory or otherwise, including without limitation warranties of + title, merchantability, fitness for a particular purpose, non + infringement, or the absence of latent or other defects, accuracy, or + the present or absence of errors, whether or not discoverable, all to + the greatest extent permissible under applicable law. + c. Affirmer disclaims responsibility for clearing rights of other persons + that may apply to the Work or any use thereof, including without + limitation any person's Copyright and Related Rights in the Work. + Further, Affirmer disclaims responsibility for obtaining any necessary + consents, permissions or other rights required for any use of the + Work. + d. Affirmer understands and acknowledges that Creative Commons is not a + party to this document and has no duty or obligation with respect to + this CC0 or use of the Work. diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..b78f6c0 --- /dev/null +++ b/Makefile @@ -0,0 +1,15 @@ +# SPDX-License-Identifier: CC0-1.0 +# +# Copyright (C) 2024 W. Kosior <koszko@koszko.org> + +CC = gcc +CFLAGS = -std=c11 -Wall -Wextra -Werror + +poly_mul: poly_mul.o + $(CC) -lflint -lgmp -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 + guix shell qemu -- qemu-x86_64 -cpu max $< diff --git a/README.md b/README.md new file mode 100644 index 0000000..c89656e --- /dev/null +++ b/README.md @@ -0,0 +1,23 @@ +# Post-quantum blind signatures implementation (in progress) + +This is a small university project with the goal of implementing Markus +Rückert's lattice-based blind signature scheme from 2008[1]. + +Please consider it a toy program — it's being developed with shortcuts +(e.g. using a big scientific library (FLINT[2]) for efficient polynomial +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 +non-canonical range — [-(n-1)/2, (n-1)/2] rather than [0, n-1]. Interestingly, +only modulo operations in the latter range seem to be directly supported in +FLINT as of today. + +## Building + +Please consult the included Makefile :) + +- [1] https://eprint.iacr.org/2008/322 +- [2] https://flintlib.org/ diff --git a/README.md.license b/README.md.license new file mode 100644 index 0000000..5c9c439 --- /dev/null +++ b/README.md.license @@ -0,0 +1,3 @@ +SPDX-License-Identifier: CC0-1.0 + +Copyright (C) 2024 W. Kosior <koszko@koszko.org> diff --git a/dev-shell b/dev-shell new file mode 100755 index 0000000..615fa53 --- /dev/null +++ b/dev-shell @@ -0,0 +1,10 @@ +#!/bin/sh +# SPDX-License-Identifier: CC0-1.0 +# +# Copyright (C) 2024 W. Kosior <koszko@koszko.org> + +# It is so annoying to have some shell read garbage from script while you edit +# 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 diff --git a/poly_mul.c b/poly_mul.c new file mode 100644 index 0000000..db45bfd --- /dev/null +++ b/poly_mul.c @@ -0,0 +1,278 @@ +/* + * 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); +} + +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_prod; + slong divisor_degree; + poly_ring_ctx_t poly_ring_ctx; + + printf("Give first polynomial to multiply:\n"); + init_read_poly(poly1, stdin); + + printf("Read polynomial: "); + fmpz_poly_print_pretty(poly1, "x"); + putchar('\n'); + + printf("Give second polynomial to multiply:\n"); + init_read_poly(poly2, stdin); + + printf("Read polynomial: "); + fmpz_poly_print_pretty(poly2, "x"); + putchar('\n'); + + printf("Normal product of polynomials:\n"); + fmpz_poly_init(poly_prod); + fmpz_poly_mul(poly_prod, poly1, poly2); + fmpz_poly_print_pretty(poly_prod, "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_prod, poly1, poly2, poly_ring_ctx); + fmpz_poly_print_pretty(poly_prod, "x"); + putchar('\n'); + + fmpz_poly_clear(poly1); + fmpz_poly_clear(poly2); + fmpz_poly_clear(poly_prod); + + poly_ring_ctx_clear(poly_ring_ctx); + } /* End of experiment 2 */ + + mod_c0_ctx_clear(mod_ctx); + fmpz_clear(prime); + + return EXIT_SUCCESS; +} |