Public key cryptosystem based on goppa codes and puf based random generation

A method of encrypting data by constructing a digital cryptogram by means of a public key algorithm comprising:

• (a) constructing a first generator matrix of a binary code with dimension k with a preselected Galois field whose base field is 2, and a Goppa polynomial whose degree is such that the corresponding binary code provides a t error correcting capability by utilising n−k parity bits,
• (b) constructing a scrambled k×n generator matrix by matrix multiplication, said scrambled generator matrix being the product of a non-singular matrix, said first generator matrix and a permutation matrix,
• (c) converting a message to be sent into binary form and formatting it by appending dummy bits as necessary into ah integral number r of binary message vectors of length k bits each,
• (d) encoding each message vector by adding rows of said scrambled generator matrix according to the 1's in each message vector to form r codeword vectors of length n bits,
• (e) for each codeword vector, using a random number generator to generate independently an integer s such that s<t
• (f) for each codeword vector, using a random number generator to generate independently an integer u such that u<n−2(t−s),
• (g) adding to each codeword vector using modulo 2 arithmetic an error vector of length n bits, containing s bit errors in randomly generated bit positions plus u bit errors in predefined positions according to a position vector and deleting 2(t−s) bits from the codeword vector in pre-defined positions according to the aforesaid position vector,
• (h) forming a cryptogram from the r said corrupted codeword vectors.

A method of encrypting data by constructing a digital cryptogram by means of a public key algorithm comprising:

• (a) constructing a first generator matrix of a binary code with dimension k with a preselected Galois field whose base field is 2, and a Goppa polynomial whose degree is such that the corresponding binary code provides a t error correcting capability by utilising n−k parity bits,
• (b) constructing a scrambled k×n generator matrix by matrix multiplication, said scrambled generator matrix being the product of a non-singular matrix, said first generator matrix and a permutation matrix,
• (c) converting a message to be sent into binary form and formatting it by appending dummy bits as necessary into an integral number r of binary message vectors of length k bits each,
• (d) for each message vector, using a random number generator to generate independently an integer s such that s<t,
• (e) for each message vector, generate independently a random error vector of length n bits, containing s bit errors,
• (f) for each message vector and associated error vector of length n bits, containing s bit errors, deriving a scrambler whose key is derived from the error vector and scrambling the k bit message vector into a k bit scrambled message vector,
• (g) encoding each scrambled message vector by adding rows of said scrambled generator matrix according to the 1's in each scrambled message vector to form r codeword vectors of length n bits,
• (h) adding to each codeword vector using modulo 2 arithmetic the said associated error vector of length n bits, containing s bit errors and deleting 2(t−s) bits from the codeword vector according to a pre-defined position vector,
• (i) forming a cryptogram from the r said corrupted codeword vectors.