Created
May 8, 2023 16:14
-
-
Save Twilight-Dream-Of-Magic/e4ad92a79a920c360f2544c5627ada6c to your computer and use it in GitHub Desktop.
One way function (version 2) with cryptography
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <NTL/ZZ_pX.h> | |
#include <NTL/mat_ZZ_p.h> | |
#include <random> | |
std::random_device rd; | |
std::default_random_engine generator(rd()); | |
// Set the PRNG seed | |
void set_seed(unsigned int seed) { | |
generator.seed(seed); | |
} | |
// Generate a pseudorandom number within the range [min, max] | |
std::uint64_t generate_pseudorandom_number(std::uint64_t min, std::uint64_t max) { | |
std::uniform_int_distribution<std::uint64_t> distribution(min, max); | |
return distribution(generator); | |
} | |
NTL::mat_ZZ_p generate_random_ZZ_p_matrix(int rows, int cols) { | |
NTL::mat_ZZ_p matrix; | |
matrix.SetDims(rows, cols); | |
for (int i = 0; i < rows; i++) { | |
for (int j = 0; j < cols; j++) { | |
std::uint64_t big_number = generate_pseudorandom_number(0, std::numeric_limits<uint64_t>::max()); | |
std::string big_number_string = std::to_string(big_number); | |
NTL::conv(matrix[i][j], big_number_string.data()); | |
} | |
} | |
return matrix; | |
} | |
NTL::ZZ_pX convert_matrix_to_poly(const NTL::mat_ZZ_p& matrix) { | |
NTL::ZZ_pX poly; | |
int rows = matrix.NumRows(); | |
int cols = matrix.NumCols(); | |
int idx = 0; | |
for (int i = 0; i < rows; i++) { | |
for (int j = 0; j < cols; j++) { | |
NTL::SetCoeff(poly, idx++, matrix[i][j]); | |
} | |
} | |
return poly; | |
} | |
int main() { | |
NTL::ZZ big_modulo = NTL::conv<NTL::ZZ>("680564733841876926926749214863536422887"); | |
NTL::ZZ_p::init(big_modulo); | |
int matrix_size = 64; | |
unsigned int seed = 42; | |
set_seed(seed); | |
// Generate the key matrix (KM) and random distribution matrix (RM) | |
NTL::mat_ZZ_p KM = generate_random_ZZ_p_matrix(matrix_size, matrix_size); | |
NTL::mat_ZZ_p RM = generate_random_ZZ_p_matrix(matrix_size, matrix_size); | |
std::cout << "Key Matrix (KM):" << std::endl; | |
std::cout << KM << '\n'; | |
std::cout << "Random Distribution Matrix (RM):" << std::endl; | |
std::cout << RM << '\n'; | |
// Convert the matrices to polynomials | |
NTL::ZZ_pX KM_poly = convert_matrix_to_poly(KM); | |
NTL::ZZ_pX RM_poly = convert_matrix_to_poly(RM); | |
std::cout << "KM Polynomial: " << KM_poly << std::endl; | |
std::cout << '\n'; | |
std::cout << "RM Polynomial: " << RM_poly << std::endl; | |
std::cout << '\n'; | |
// Multiply the polynomials and perform modulo with the large ZZ number | |
NTL::ZZ_pX result_poly = (KM_poly * RM_poly); | |
std::cout << "Big Polynomial: " << result_poly << std::endl; | |
std::cout << '\n'; | |
NTL::ZZ small_modulo = NTL::conv<NTL::ZZ>("18446744073709551616"); | |
std::uint32_t poly_degree = NTL::deg(result_poly); | |
for (size_t i = 0; i <= poly_degree; i++) | |
{ | |
NTL::ZZ_p& coeff = result_poly[i]; | |
coeff._ZZ_p__rep %= small_modulo; | |
} | |
std::cout << "Result Small Polynomial: " << result_poly << std::endl; | |
std::cout << '\n'; | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package main | |
import ( | |
"crypto/rand" | |
"fmt" | |
"math/big" | |
"math/rand" | |
) | |
const ( | |
bigModulo = "680564733841876926926749214863536422887" | |
smallModulo = "18446744073709551616" | |
matrixSize = 64 | |
seed = 42 | |
) | |
func setSeed(seed int64) { | |
rand.Seed(seed) | |
} | |
func generatePseudorandomNumber(minVal, maxVal int64) int64 { | |
return rand.Int63n(maxVal-minVal) + minVal | |
} | |
func generateRandomZZPMatrix(rows, cols int, modulus *big.Int) [][]*big.Int { | |
matrix := make([][]*big.Int, rows) | |
for i := range matrix { | |
matrix[i] = make([]*big.Int, cols) | |
} | |
maxUint64 := big.NewInt(1<<64 - 1) | |
for i := 0; i < rows; i++ { | |
for j := 0; j < cols; j++ { | |
bigNumber := new(big.Int).Rand(rand.Reader, maxUint64) | |
matrix[i][j] = new(big.Int).Mod(bigNumber, modulus) | |
} | |
} | |
return matrix | |
} | |
func convertMatrixToPoly(matrix [][]*big.Int) []*big.Int { | |
coeffs := make([]*big.Int, 0) | |
for _, row := range matrix { | |
for _, col := range row { | |
coeffs = append(coeffs, col) | |
} | |
} | |
return coeffs | |
} | |
func main() { | |
bigModulus, _ := new(big.Int).SetString(bigModulo, 10) | |
smallModulus, _ := new(big.Int).SetString(smallModulo, 10) | |
setSeed(seed) | |
KM := generateRandomZZPMatrix(matrixSize, matrixSize, bigModulus) | |
RM := generateRandomZZPMatrix(matrixSize, matrixSize, bigModulus) | |
fmt.Println("Key Matrix (KM):") | |
for _, row := range KM { | |
fmt.Println(row) | |
} | |
fmt.Println("\nRandom Distribution Matrix (RM):") | |
for _, row := range RM { | |
fmt.Println(row) | |
} | |
KMPoly := convertMatrixToPoly(KM) | |
RMPoly := convertMatrixToPoly(RM) | |
fmt.Println("\nKM Polynomial:", KMPoly) | |
fmt.Println("\nRM Polynomial:", RMPoly) | |
bigPoly := make([]*big.Int, len(KMPoly)) | |
for i := range KMPoly { | |
bigPoly[i] = new(big.Int).Mul(KMPoly[i], RMPoly[i]) | |
bigPoly[i].Mod(bigPoly[i], bigModulus) | |
} | |
fmt.Println("\nBig Polynomial:", bigPoly) | |
resultPoly := make([]*big.Int, len(bigPoly)) | |
for i, coeff := range bigPoly { | |
resultPoly[i] = new(big.Int).Mod(coeff, smallModulus) | |
} | |
fmt.Println("\nResult Small Polynomial:", resultPoly) | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.math.BigInteger; | |
import java.util.ArrayList; | |
import java.util.List; | |
import java.util.Random; | |
public class Main { | |
private static final BigInteger BIG_MODULO = new BigInteger("680564733841876926926749214863536422887"); | |
private static final BigInteger SMALL_MODULO = new BigInteger("18446744073709551616"); | |
private static final int MATRIX_SIZE = 64; | |
public static void main(String[] args) { | |
int seed = 42; | |
Random random = new Random(seed); | |
BigInteger[][] KM = generateRandomMatrix(MATRIX_SIZE, MATRIX_SIZE, BIG_MODULO, random); | |
BigInteger[][] RM = generateRandomMatrix(MATRIX_SIZE, MATRIX_SIZE, BIG_MODULO, random); | |
System.out.println("Key Matrix (KM):"); | |
printMatrix(KM); | |
System.out.println("\nRandom Distribution Matrix (RM):"); | |
printMatrix(RM); | |
List<BigInteger> KM_poly = convertMatrixToPoly(KM); | |
List<BigInteger> RM_poly = convertMatrixToPoly(RM); | |
System.out.println("\nKM Polynomial: " + KM_poly); | |
System.out.println("\nRM Polynomial: " + RM_poly); | |
List<BigInteger> bigPoly = new ArrayList<>(); | |
for (int i = 0; i < KM_poly.size(); i++) { | |
bigPoly.add(KM_poly.get(i).multiply(RM_poly.get(i)).mod(BIG_MODULO)); | |
} | |
System.out.println("\nBig Polynomial: " + bigPoly); | |
List<BigInteger> resultPoly = new ArrayList<>(); | |
for (BigInteger coeff : bigPoly) { | |
resultPoly.add(coeff.mod(SMALL_MODULO)); | |
} | |
System.out.println("\nResult Small Polynomial: " + resultPoly); | |
} | |
private static BigInteger[][] generateRandomMatrix(int rows, int cols, BigInteger modulus, Random random) { | |
BigInteger[][] matrix = new BigInteger[rows][cols]; | |
for (int i = 0; i < rows; i++) { | |
for (int j = 0; j < cols; j++) { | |
matrix[i][j] = new BigInteger(64, random).mod(modulus); | |
} | |
} | |
return matrix; | |
} | |
private static List<BigInteger> convertMatrixToPoly(BigInteger[][] matrix) { | |
List<BigInteger> coeffs = new ArrayList<>(); | |
for (int i = 0; i < matrix.length; i++) { | |
for (int j = 0; j < matrix[0].length; j++) { | |
coeffs.add(matrix[i][j]); | |
} | |
} | |
return coeffs; | |
} | |
private static void printMatrix(BigInteger[][] matrix) { | |
for (int i = 0; i < matrix.length; i++) { | |
for (int j = 0; j < matrix[0].length; j++) { | |
System.out.print(matrix[i][j] + " "); | |
} | |
System.out.println(); | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Follow the installation instructions at: https://www.sagemath.org/download.html | |
from sage.all import * | |
import random | |
def set_seed(seed): | |
random.seed(seed) | |
def generate_pseudorandom_number(min_val, max_val): | |
return random.randint(min_val, max_val) | |
def generate_random_ZZ_p_matrix(rows, cols, modulus): | |
matrix = Matrix(Zmod(modulus), rows, cols) | |
max_uint64 = 2**64 - 1 | |
for i in range(rows): | |
for j in range(cols): | |
big_number = generate_pseudorandom_number(0, max_uint64) | |
matrix[i, j] = big_number | |
return matrix | |
def convert_matrix_to_poly(matrix): | |
coeffs = [] | |
rows, cols = matrix.dimensions() | |
for i in range(rows): | |
for j in range(cols): | |
coeffs.append(matrix[i, j]) | |
return coeffs | |
def main(): | |
big_modulo = 680564733841876926926749214863536422887 | |
small_modulo = 18446744073709551616 | |
matrix_size = 64 | |
seed = 42 | |
set_seed(seed) | |
# Generate the key matrix (KM) and random distribution matrix (RM) | |
KM = generate_random_ZZ_p_matrix(matrix_size, matrix_size, big_modulo) | |
RM = generate_random_ZZ_p_matrix(matrix_size, matrix_size, big_modulo) | |
print("Key Matrix (KM):") | |
print(KM) | |
print("\nRandom Distribution Matrix (RM):") | |
print(RM) | |
# Convert the matrices to polynomials(coefficient vector) | |
KM_poly = convert_matrix_to_poly(KM) | |
RM_poly = convert_matrix_to_poly(RM) | |
print("\nKM Polynomial:", KM_poly) | |
print("\nRM Polynomial:", RM_poly) | |
# Multiply the polynomials and perform modulo with the large ZZ number | |
big_poly = [] | |
for k, r in zip(KM_poly, RM_poly): | |
big_poly.append(k * r % big_modulo) | |
print("\nBig Polynomial:", big_poly) | |
# The polynomials and perform modulo with the small ZZ number | |
result_poly = [] | |
for coeff in big_poly: | |
result_poly.append(ZZ(coeff) % small_modulo) | |
print("\nResult Small Polynomial:", result_poly) | |
if __name__ == "__main__": | |
main() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
\begin{aligned} | |
& \textbf{Step 1: Seed the Pseudorandom Number Generator} \\ | |
& \mathbf{PRNG.set\_seed}(seed) \\ | |
& \\ | |
& \textbf{Step 2: Generate Key Matrix (KM) and Random Distribution Matrix (RM)} \\ | |
& KM_{i,j} = \text{generate\_pseudorandom\_number}(PRNG, 0, 2^{64}-1) \pmod{M_{big}} \quad \forall i,j \in \{0, \dots, m-1\} \times \{0, \dots, n-1\} \\ | |
& RM_{i,j} = \text{generate\_pseudorandom\_number}(PRNG, 0, 2^{64}-1) \pmod{M_{big}} \quad \forall i,j \in \{0, \dots, m-1\} \times \{0, \dots, n-1\} \\ | |
& \\ | |
& \textbf{Step 3: Convert Matrices to Polynomials (Coefficient Vectors)} \\ | |
& KM_{\text{poly}} = \begin{bmatrix} KM_{0,0} & KM_{0,1} & \cdots & KM_{m-1,n-1} \end{bmatrix} \\ | |
& RM_{\text{poly}} = \begin{bmatrix} RM_{0,0} & RM_{0,1} & \cdots & RM_{m-1,n-1} \end{bmatrix} \\ | |
& \\ | |
& \textbf{Step 4: Multiply the Polynomials and Perform Modulo with the Large ZZ Number} \\ | |
& \text{Big\_poly} = \begin{bmatrix} KM_{\text{poly}}[0] \times RM_{\text{poly}}[0] \pmod{M_{big}} & \cdots & KM_{\text{poly}}[mn-1] \times RM_{\text{poly}}[mn-1] \pmod{M_{big}} \end{bmatrix} \\ | |
& \\ | |
& \textbf{Step 5: Perform Modulo with the Small ZZ Number} \\ | |
& \text{Result\_Small\_poly} = \begin{bmatrix} \text{Big\_poly}[0] \pmod{M_{small}} & \cdots & \text{Big\_poly}[mn-1] \pmod{M_{small}} \end{bmatrix} | |
\end{aligned} | |
\newline | |
\begin{aligned} | |
x = & 2 \\ | |
p(x) = & x^{128} + x^{127} + x^{126} + x^{125} + x^{124} + x^{123} + x^{122} + x^{121} + x^{120} + x^{119} + x^{118} + x^{117} + x^{116} + x^{115} + x^{114} + x^{113} + x^{112} + x^{111} + x^{110} + x^{109} + x^{108} + x^{107} + x^{106} + x^{105} + x^{104} + x^{103} + x^{102} + x^{101} + x^{100} + \\ | |
& x^{99} + x^{98} + x^{97} + x^{96} + x^{95} + x^{94} + x^{93} + x^{92} + x^{91} + x^{90} + x^{89} + x^{88} + x^{87} + x^{86} + x^{85} + x^{84} + x^{83} + x^{82} + x^{81} + x^{80} + \\ | |
& x^{79} + x^{78} + x^{77} + x^{76} + x^{75} + x^{74} + x^{73} + x^{72} + x^{71} + x^{70} + x^{69} + x^{68} + x^{67} + x^{66} + x^{65} + x^{64} + x^{63} + x^{62} + x^{61} + x^{60} + \\ | |
& x^{59} + x^{58} + x^{57} + x^{56} + x^{55} + x^{54} + x^{53} + x^{52} + x^{51} + x^{50} + x^{49} + x^{48} + x^{47} + x^{46} + x^{45} + x^{44} + x^{43} + x^{42} + x^{41} + x^{40} + \\ | |
& x^{39} + x^{38} + x^{37} + x^{36} + x^{35} + x^{34} + x^{33} + x^{32} + x^{31} + x^{30} + x^{29} + x^{28} + x^{27} + x^{26} + x^{25} + x^{24} + x^{23} + x^{22} + x^{21} + x^{20} + \\ | |
& x^{19} + x^{18} + x^{17} + x^{16} + x^{15} + x^{14} + x^{13} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + x^6 + x^5 + x^3 + 1 | |
\end{aligned} | |
\newline | |
\begin{aligned} | |
& x = 2 \\ | |
& p2(x) = x^{64} | |
\end{aligned} | |
\newline | |
\text{Here, $M_{big} = 680564733841876926926749214863536422887$ = $\mathbf{p}(x)$ and $M_{small} = 18446744073709551616$ = $\mathbf{p2}(x)$ are the large and small modulo, respectively.} | |
\newline | |
\text{The dimensions of the matrices, $m$ and $n$, are set by the user and must satisfy the following conditions:} | |
\begin{aligned} | |
& m = n \mathbf{ and } \equiv 0 \pmod{32}\\ | |
& m, n \geq 4 \\ | |
\end{aligned} | |
\newline | |
\text{These conditions ensure the post-quantum standard data security.} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment