commit 847230c311c8d9e0101a1de98f69a7f800c966fe
Author: olikru <olikru@tkruger.se>
Date: Thu, 11 Jan 2024 10:50:32 +0100
initial
Diffstat:
10 files changed, 334 insertions(+), 0 deletions(-)
diff --git a/Makefile b/Makefile
@@ -0,0 +1,58 @@
+.SUFFIXES: .c .o .so
+CC=clang
+CFLAGS+=-std=c99 -pedantic -Wall -Werror -Wstrict-prototypes
+CFLAGS+=-Wmissing-prototypes -Wmissing-declarations -Wshadow
+CFLAGS+=-Wpointer-arith -Wcast-qual -Wsign-compare
+CFLAGS+=-O2 -g
+CFLAGS+=-fstack-protector-all -Wtype-limits -fno-common
+CFLAGS+=-fno-builtin
+CFLAGS+=-I/usr/local/include
+
+CFLAGS+=-I/usr/local/include/flint
+LDFLAGS+=-L/usr/local/lib -lflint -lgmp
+
+INSTALL_PATH=$(HOME)/.local
+BUILD=build
+
+TEST_SOURCE=test_angrepp.c
+HEADERS=smallfactor.h
+OBJS=\
+smallfactor.o\
+hnp.o
+TOOLS=\
+hnpsolve
+SHARED=angrepp.so
+LIBSHARED=libangrepp.so
+
+BUILD_OBJS=$(OBJS:S/^/$(BUILD)\//g)
+TOOLS_DIR=tools
+
+all: build $(OBJS) $(SHARED) $(TOOLS) test
+
+build:
+ mkdir -p $(BUILD)
+ mkdir -p $(BUILD)/tools
+
+.c.o:
+ $(CC) $(CFLAGS) -c $< -o $(BUILD)/$@
+
+$(SHARED):
+ $(CC) -shared -fPIC $(BUILD_OBJS) -o $(BUILD)/$(SHARED) $(LDFLAGS)
+
+test: $(TEST_SOURCE)
+ $(CC) $(CFLAGS) -o $(BUILD)/test $(TEST_SOURCE) $(BUILD_OBJS) $(LDFLAGS)
+
+# -- tools
+
+hnpsolve: build $(OBJS)
+ $(CC) -I. $(CFLAGS) -o $(BUILD)/tools/hnpsolve $(TOOLS_DIR)/hnpsolve.c $(BUILD_OBJS) $(LDFLAGS)
+
+install:
+ mkdir -p $(INSTALL_PATH)/lib/angrepp
+ cp $(BUILD)/$(SHARED) $(INSTALL_PATH)/lib/angrepp/$(LIBSHARED)
+ chmod 644 $(INSTALL_PATH)/lib/angrepp/$(LIBSHARED)
+ mkdir -p $(INSTALL_PATH)/include/angrepp
+ cp $(HEADERS) $(INSTALL_PATH)/include/angrepp/
+
+clean:
+ rm -rf $(BUILD)
diff --git a/README b/README
@@ -0,0 +1,20 @@
+
+ ________ _ __________ _______ ___
+ / ___/ _ | / |/ / ___/ _ \/ __/ _ \/ _ \
+ / /__/ __ |/ / (_ / , _/ _// ___/ ___/
+ \___/_/ |_/_/|_/\___/_/|_/___/_/ /_/
+
+
+Collection of functions related to cryptographic attacks of various
+kinds. This is an attempt to build a decent library which heavily
+depends on FLINT (see https://flintlib.org/).
+
+== 0 - Table of contents
+
+0 - Table of contents
+1 - Hidden number problem (hnp.c)
+
+== 1 - Hidden number problem
+
+The hidden number problem shows up in various contexts of cryptographic
+attacks. TODO TODO , api TODO
diff --git a/TODO b/TODO
@@ -0,0 +1,3 @@
+* Unit tests
+* Documentation, spec. README
+* Implement fun stuff
diff --git a/examples/hnp_instance.txt b/examples/hnp_instance.txt
@@ -0,0 +1,4 @@
+3 11 131101
+46396 65911
+3185 5049
+30618 56983
diff --git a/hnp.c b/hnp.c
@@ -0,0 +1,96 @@
+#include "hnp.h"
+
+int hidden_number_problem(fmpz *res, const slong nres, const fmpz *t,
+ const fmpz *a, const slong m, const fmpz_t n,
+ const fmpz_t B) {
+ if (nres < m + 1)
+ return (-1);
+
+ // initialise a zero matrix
+ fmpz_mat_t A;
+ fmpz_mat_init(A, m + 2, m + 2);
+ fmpz_mat_zero(A);
+
+ // set up n^2's on the diagonal
+ slong i;
+ fmpz_t n_squared;
+ fmpz_init_set(n_squared, n);
+ fmpz_pow_ui(n_squared, n_squared, 2);
+ for (i = 0; i < m; i++) {
+ fmpz *m_i_i = fmpz_mat_entry(A, i, i);
+ fmpz_set(m_i_i, n_squared);
+ }
+ fmpz_clear(n_squared);
+
+ // setting up last two diagonal entries
+ fmpz *m_i_i = fmpz_mat_entry(A, m, m);
+ fmpz_set(m_i_i, B);
+ m_i_i = fmpz_mat_entry(A, m + 1, m + 1);
+ fmpz_mul(m_i_i, B, n);
+
+ // columnwise setup
+ for (i = 0; i < m; i++) {
+ // t[i]*n
+ fmpz *tmp = fmpz_mat_entry(A, m, i);
+ fmpz_mul(tmp, &t[i], n);
+
+ // a[i]*n
+ tmp = fmpz_mat_entry(A, m + 1, i);
+ fmpz_mul(tmp, &a[i], n);
+ }
+
+ // use LLL for lattice reduction (delta = 0.99, eta = 0.501)
+ fmpq_t delta, eta;
+ fmpq_init(delta);
+ fmpq_init(eta);
+ fmpq_set_ui(delta, 99, 100);
+ fmpq_set_ui(eta, 501, 1000);
+
+ fmpz_mat_lll_original(A, delta, eta);
+
+ fmpq_clear(delta);
+ fmpq_clear(eta);
+
+ // extract the potential solution
+ fmpz_t Bn;
+ fmpz_init(Bn);
+ fmpz_mul(Bn, B, n);
+ for (i = 0; i < m + 2; i++) {
+ if (fmpz_cmpabs(fmpz_mat_entry(A, i, m + 1), Bn) == 0)
+ break;
+ }
+ if (i >= m + 2)
+ return 1;
+ fmpz_clear(Bn);
+
+ slong r = i;
+
+ for (i = 0; i < m; i++) {
+ fmpz *tmp = fmpz_mat_entry(A, r, i);
+ fmpz_tdiv_q(&res[i], tmp, n);
+ }
+ fmpz_tdiv_q(&res[m], fmpz_mat_entry(A, r, m), B);
+
+ fmpz_mat_clear(A);
+
+ // test that the solution is a solution to original HNP
+ fmpz_t tmp;
+ fmpz_init(tmp);
+
+ for (i = 0; i < m; i++) {
+ // tmp <- t[i]*alpha - a[i] mod n
+ fmpz_mul(tmp, &t[i], &res[m]);
+ fmpz_add(tmp, tmp, &a[i]);
+ fmpz_sub(tmp, tmp, &res[i]);
+ fmpz_mod(tmp, tmp, n);
+
+ if (fmpz_cmp_ui(tmp, 0) != 0) {
+ fmpz_clear(tmp);
+ return 1;
+ }
+ }
+
+ fmpz_clear(tmp);
+
+ return 0;
+}
diff --git a/hnp.h b/hnp.h
@@ -0,0 +1,30 @@
+#ifndef HNP_H
+#define HNP_H
+
+#include <flint.h>
+#include <fmpq.h>
+#include <fmpz.h>
+#include <fmpz_mat.h>
+#include <gmp.h>
+
+/**
+ * Solve the hidden number problem
+ * t[i]*alpha - a[i] == b[i] (mod n), i = 0,1,...,m-1
+ * for
+ * b[i], i = 0,1,...,m-1, and
+ * alpha
+ * where |b[i]| < B.
+ *
+ * @param res
+ * an already initialised vector that has size nres, this vector
+ * may be overwritten even if the result is not verified
+ * @return
+ * -1 if failure (ex. res too small to fit m+1 values)
+ * 1 if reduction okay, but solution fails to verify
+ * 0 if solution found
+ */
+int hidden_number_problem(fmpz *res, const slong nres, const fmpz *t,
+ const fmpz *a, const slong m, const fmpz_t n,
+ const fmpz_t B);
+
+#endif
diff --git a/smallfactor.c b/smallfactor.c
@@ -0,0 +1,5 @@
+#include "smallfactor.h"
+
+int smallfactor(int x, int y) {
+ return x * y;
+}
diff --git a/smallfactor.h b/smallfactor.h
@@ -0,0 +1,8 @@
+#ifndef SMALLFACTOR_H
+#define SMALLFACTOR_H
+
+#include <stdlib.h>
+
+int smallfactor(int x, int y);
+
+#endif
diff --git a/test_angrepp.c b/test_angrepp.c
@@ -0,0 +1,7 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <assert.h>
+
+int main() {
+ printf("test unimplemented\n");
+}
diff --git a/tools/hnpsolve.c b/tools/hnpsolve.c
@@ -0,0 +1,103 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <flint.h>
+#include <fmpz_vec.h>
+#include <hnp.h>
+
+#define LINE_SIZE_MAX 4096
+
+static int read_next_fmpz(fmpz_t res)
+{
+ char buffer[LINE_SIZE_MAX];
+ size_t i;
+
+ int next_char = getchar();
+ while(next_char == '\n' || next_char == ' ')
+ next_char = getchar();
+
+ if(next_char == EOF)
+ return -1;
+
+ buffer[0] = next_char;
+ i = 1;
+ while(i < LINE_SIZE_MAX-1) {
+ next_char = getchar();
+ if(next_char == EOF || next_char == '\n' || next_char == ' ')
+ break;
+
+ buffer[i] = (char) next_char;
+
+ i++;
+ }
+ buffer[i] = '\0';
+
+ return fmpz_set_str(res, buffer, 10);
+}
+
+static int read_stdin_instance(fmpz** a, fmpz** t, slong* m, fmpz_t* B, fmpz_t* n)
+{
+ flint_scanf("%wd", m);
+
+ if(read_next_fmpz(*B))
+ return -1;
+
+ if(read_next_fmpz(*n))
+ return -1;
+
+ *a = _fmpz_vec_init(*m);
+ *t = _fmpz_vec_init(*m);
+
+
+ slong i;
+ int fail = 0;
+ for(i = 0; i < *m; i++) {
+ if(read_next_fmpz(&(*t)[i])) {
+ fail = 1;
+ break;
+ }
+
+ if(read_next_fmpz(&(*a)[i])) {
+ fail = 1;
+ break;
+ }
+ }
+
+ if(fail) {
+ _fmpz_vec_clear(*a, *m);
+ _fmpz_vec_clear(*t, *m);
+ return -1;
+ }
+
+ return 0;
+}
+
+int main(int argc, char* argv[])
+{
+ slong m;
+ fmpz* a;
+ fmpz* t;
+ fmpz_t B, n;
+ fmpz_init(B);
+ fmpz_init(n);
+
+ if(read_stdin_instance(&a, &t, &m, &B, &n) != 0) {
+ fprintf(stderr, "ERROR! Bad input format?\n");
+ exit(1);
+ }
+
+ fmpz res[m+1];
+ slong i;
+ for(i = 0; i < m+1; i++) fmpz_init(&res[i]);
+
+ int ret = hidden_number_problem(res, m+1, t, a, m, n, B);
+ if(ret == 0) {
+ for(i = 0; i < m; i++) {
+ fmpz_print(&res[i]);
+ printf(" ");
+ }
+ fmpz_print(&res[m]);
+ printf("\n");
+ }
+
+ return 0;
+}
