// polynomial.h #pragma once #include #include #include #include #include #include #include #include "hash.h" namespace pol { typedef unsigned long long u64_t; typedef unsigned u32_t; typedef unsigned char u8_t; /** * @brief Máxima longitud en bit de un polinomio */ const u32_t POL1V_MAXLENGTH = 4096; /** * @brief */ const u32_t M32 = 0xffffffff; /** * @brief Máxima grado del polinomio de la clave privada */ const u32_t KEY_DEG = 3; /** * @brief Característica del campo finito */ const u32_t MODSIZE = 61; /** * @brief */ const u32_t BUFSIZE = 8; /** * @brief Tamaño del campo finito */ const u64_t MOD = 2305843009213693951; // 2147483647; // // 2^61 - 1 /** * @brief Operaciones sobre el campo finito */ class u61_t { private: u64_t data; public: u61_t(u64_t x = 0); operator u64_t() const; u61_t operator+(const u61_t &) const; u61_t operator-(const u61_t &) const; u61_t operator*(const u61_t &) const; u61_t operator/(const u61_t &) const; u61_t& operator+=(const u61_t &); u61_t& operator-=(const u61_t &); u61_t& operator*=(const u61_t &); u61_t& operator/=(const u61_t &); u61_t inverse() const; u61_t pow(u32_t) const; inline u64_t* get_addr(); inline const u64_t* get_addr() const; inline u64_t& get_buf(); inline const u64_t& get_buf() const; void print(FILE *, u32_t) const; }; /** * @brief El tipo de representación de coeficientes de un polinomio */ enum pol_format_t { BINPR, // representación polinómica de un número en binario TEXTPR, // representación polinómica de un número en texto HTMLPR // representación polinómica ... }; /** * @brief Clase que representa un polinomio de un variable sobre el campo finito */ class pol_t { private: std::vector data; u32_t degree; public: typedef std::vector vector_t; pol_t(); pol_t& operator=(const pol_t&); void change_degree(u32_t); pol_t& operator+=(const pol_t&); pol_t& operator-=(const pol_t&); pol_t& operator*=(const pol_t&); pol_t& operator%=(const pol_t&); pol_t& operator/=(const pol_t&); pol_t operator+(const pol_t&) const; pol_t operator-(const pol_t&) const; pol_t operator*(const pol_t&) const; pol_t operator%(const pol_t&) const; pol_t operator/(const pol_t&) const; operator bool() const; bool operator==(const pol_t &) const; pol_t pow(u32_t) const; pol_t mpow(u64_t, const pol_t &) const; pol_t mpow(u64_t, u64_t, const pol_t &) const; /** * @brief Normaliza el polinomio. * * El coeficiente lider (de máximo grado) sea 1. * * @return polinonio normalizado */ pol_t normalize() const; /** * @brief Deriva el polinomio * * @return polinomio derivado */ pol_t deriv() const; /** * @brief Leer un polinomio desde un archivo * @param fin * @param format */ void read(FILE * fin, pol_format_t format = TEXTPR); /** * @brief Escribir un polinomio hacia un archivo * @param fout * @param format * @param endofline */ void write(FILE * fout, pol_format_t format = HTMLPR, bool endofline = true) const; u61_t& operator[](u32_t); const u61_t& operator[](u32_t) const; u64_t& operator()(u32_t); const u64_t& operator()(u32_t) const; /** * @brief Retorna el grado del polinomio * @return grado del polinomio */ u32_t get_deg() const; /** * @brief Factoriza el poloniomio */ void fact(u32_t, vector_t &) const; void ddf(u32_t, vector_t &) const; /** * @brief Separa el polinomio en sus factores * */ void split(u32_t, vector_t &) const; }; /** * @brief Estructura para mantener el grado de un polinomio de varias variables */ union deg_t { u64_t key; struct { u32_t x, y; }; deg_t(); deg_t(u32_t, u32_t); bool operator<(const deg_t &) const; bool operator==(const deg_t &) const; deg_t operator+(const deg_t&) const; }; typedef std::pair pol3v1_t; typedef std::list list_t; typedef std::map polmap_t; typedef pol_t::vector_t vector_t; /** * @brief Clase que representa un polinomio de tres variables */ class pol3v_t { private: public: list_t data; u32_t dx; u32_t dy; u32_t dt; pol3v_t(); pol3v_t(const polmap_t &); pol3v_t& operator=(const pol3v_t &); pol3v_t operator+(const pol3v_t&) const; pol3v_t operator-(const pol3v_t&) const; pol3v_t operator*(const pol3v_t&) const; pol3v_t& operator+=(const pol3v_t &); pol3v_t& operator-=(const pol3v_t &); pol3v_t& operator*=(const pol3v_t &); pol_t subst(const pol_t &, const pol_t &) const; /** * @brief Retorna un polinomio con la misma característica (forma) * @return */ pol3v_t get_same_rand_pol() const; /** * @brief Leer un polinomio desde un archivo * @param fin * @param format */ void read(FILE *, pol_format_t); /** * @brief Escribir un polinomio hacia un archivo * @param fout * @param format * @param endofline */ void write(FILE * fout, pol_format_t format = HTMLPR, bool endofline = 1) const; }; enum file_mode_t { READ, WRITE }; /** * @brief Clase para gestionar un archivo en el sistema de archivos */ class File { private: FILE *file; bool opened; file_mode_t mode; u64_t buf; size_t pos, count, read_size; public: File(); File(FILE *, file_mode_t); File(const char *, file_mode_t); ~File(); bool open(const char *, file_mode_t); void close(); void flush(); size_t read(u61_t &); size_t write(const u61_t &, size_t = MODSIZE - 1); }; /** * @brief Clase para generar números pseudo-aleatorios */ class random_t { private: std::mt19937_64 generator; public: random_t(); u61_t operator()(); }; /** * @brief Retorna el máximo común dividor * @return máximo común dividor */ pol_t gcd(const pol_t &, const pol_t &); pol_t get_x(); /** * @brief Retorna un polinomio aleatorio de una variable * @param deg * @param f * @return polinomio aleatorio de una variable */ pol_t get_rand_pol(u32_t deg, bool f = true); /** * Genera la clave pública a partir de dos polinomios que corresponden a la clave privada */ template pol3v_t get_open_key(const pol_t &, const pol_t &); /** * Cifra un archivo dado la clave pública (polinomio de tres variables) */ template void encrypt(File &, FILE *, const pol3v_t &); /** * Descifra un archivo dada la clave privada en dos polinomios de una variable */ template void decrypt(FILE *, File &, const pol_t &, const pol_t &); /** * @brief Retorna el polinomio divisor f utilizado para el proceso de cifrado * @param max_deg * @param Key_Deg * @return polinomio divisor f utilizado para el proceso de cifrado */ pol3v_t XXX_get_f(const u64_t max_deg, const u32_t Key_Deg); /** * @brief Retorna el mensaje convertido en polinomio * @param max_deg * @param Key_Deg * @return mensaje convertido en polinomio */ pol3v_t XXX_get_mes(const u64_t max_deg, const u32_t Key_Deg, const u64_t size, const std::vector &); /** * @brief * @param fact * @param deg * @param res */ void XXX_get_fact(const vector_t &fact, u64_t deg, vector_t &res); #include "polinomial.hpp" };