PUBLIC KEY ENCRYPTION SYSTEM USING ERROR CORRECTING CODES

• US 20120121084A1
• Filed: 11/15/2011
• Published: 05/17/2012
• Est. Priority Date: 11/16/2010
• Status: Active Grant

• Current Assignee: PQ Solutions Limited
• Original Assignee: Cen Jung Tjhai, Martin Tomlinson
• Inventors: Tomlinson, Martin, Tjhai, Cen Jung
• Granted Patent: US 8,891,763 B2
• Time in Patent Office: Days
• US Class Current: 380/30
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 9/30 Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
• CPC Class Codes: H04L 9/304 based on error correction codes, e.g. McEliece

Abstract

This invention provides improved security and improved throughput of the McEliece public key encryption system and reduces the public key size. Even though the public key is reduced, in some embodiments of the invention the ensemble of cryptograms produced is identical to the ensemble of cryptograms produced by the original system for a given Goppa code, and the same private key. It is possible using this invention that the encrypted message, the cryptogram is a truly random function, not a pseudo random function of the message so that even with the same message and the same public key, a different, unpredictable cryptogram is produced each time. Other embodiments of the invention use a shortened error correcting code allowing the length of the generated cryptogram to match exactly the available transmission or storage media such as is the case of RFID and packet based radio applications.

Claims

1. 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 pre-selected Galois field whose base field is 2, and a Goppa polynomial whose degree is such that the corresponding binary code provides at 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 first permutation matrix,

(c) constructing a reduced echelon k×

n generator matrix by randomly selecting k independent columns of the scrambled k×

n generator matrix according to a second permutation matrix,

(d) 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,

(e) scrambling each binary message vector using a k-bit to k-bit invertible scrambler,

(f) encoding each scrambled binary message vector by adding rows of said reduced echelon generator matrix according to the is in each scrambled message vector to form r codeword vectors of length n bits,

(g) adding to each codeword vector using modulo 2 arithmetic an error vector of length n bits, containing s bit errors where s≦

t, and

(h) forming a cryptogram from the r said corrupted codeword vectors.

2. A method of encrypting data according to claim 1, further comprising using a third permutation matrix to permute the bits of each codeword.

3. A method of encrypting data according to claim 1, further comprising selecting the integer s such that s≦

t for each codeword vector.

4. A method of encrypting data according to claim 1 in which the scrambling function used by the k-bit to k-bit invertible scrambler is derived from the error vector of length n bits.

5. A method of encrypting data according to claim 1 in which the number of errors, the integer s, and the error vector containing s bit errors for each codeword vector is derived from a second stream of scrambled u bit binary message vectors.

6. A method of encrypting data according to claim 1 in which the number of errors, the integer s, and the error vector containing s bit errors for each codeword vector is derived from a combination of a u bit scrambled binary message vector and a v bit random number from a random number generator.

7. A method of encrypting data according to claim 6 in which the k-bit to k-bit invertible scrambler and the u bit to u bit invertible scrambler is derived from the v bit random number.

8. A method of encrypting data according to claim 1 in which a k-bit to k-bit invertible scrambling is carried out by an arrangement producing a k-bit binary output vector which is equivalent to a polynomial multiplication, modulo 1+x^k of a first polynomial of degree k−

1 defined by a k-bit binary input vector and a second fixed polynomial of degree k−

1, where k is a fixed integer.

9. A method of encrypting data according to claim 8 in which a u bit to u bit invertible scrambling is carried out by an arrangement producing a u-bit binary output vector which is equivalent to a polynomial multiplication, modulo 1+x^u of a first polynomial of degree u−

1 defined by a u bit binary input vector and a second fixed polynomial of degree u−

1, where u is a fixed integer.

10. A method of encrypting data according to claim 1 in which each codeword vector of length n bits is from a shortened error correcting code derived by deleting bits in certain fixed positions of each codeword from an error correcting code whose length is greater than n.

11. A method of decrypting data encrypted using the method of claim 1.

12. A method for reconstructing a message from a digital cryptogram constructed according to claim 1 by means of a private key algorithm comprising:

(a) retrieving said cryptogram from a communications channel or storage medium as r retrieved vectors, each of length n symbols,

(b) multiplying each retrieved vector by a first permutation matrix to obtain a codeword of the Goppa code used in creating the public key scrambled generator matrix, corrupted with no more than t bit errors,

(c) applying an error correcting decoding algorithm to each corrupted codeword to form r binary codewords of the Goppa code,

(d) multiplying each binary codeword of the Goppa code by a second permutation matrix,

(e) selecting the scrambled binary message vector of length k bits from each permuted codeword,

(f) descrambling each binary message vector by the inverse of the k-bit to k-bit scrambler used in encryption to form r unscrambled binary message vectors,

(g) reformatting the r unscrambled binary message vectors removing appended dummy bits to form the original digital message.

13. A method for reconstructing a message from a digital cryptogram constructed according to claim 4 by means of a private key algorithm comprising:

(a) retrieving said cryptogram from a communications channel or storage medium as r retrieved vectors, each of length n symbols,

(b) multiplying each retrieved vector by a first permutation matrix to obtain a codeword of the Goppa code used in creating the public key scrambled generator matrix, corrupted with no more than t bit errors,

(c) applying an error correcting decoding algorithm to each corrupted codeword to form r binary codewords of the Goppa code and r error vectors,

(d) multiplying each binary codeword of the Goppa code by a second permutation matrix,

(e) multiplying each error vector by a third permutation matrix,

(f) deriving from each permuted error vector a k to k-bit descrambler,

(g) selecting the scrambled binary message vector of length k bits from each permuted codeword,

(h) descrambling each binary message vector by the k-bit to k-bit descrambler to form r unscrambled binary message vectors,

(i) reformatting the r unscrambled binary message vectors removing appended dummy bits to form the original digital message.

14. A method for reconstructing a message from a digital cryptogram constructed according to claim 5 by means of a private key algorithm comprising:

(a) retrieving said cryptogram from a communications channel or storage medium as r retrieved vectors, each of length n symbols,

(b) multiplying each retrieved vector by a first permutation matrix to obtain a codeword of the Goppa code used in creating the public key scrambled generator matrix, corrupted with no more than t bit errors,

(c) applying an error correcting decoding algorithm to each corrupted codeword to form r binary codewords of the Goppa code and r binary error vectors,

(d) multiplying each binary codeword of the Goppa code by a second permutation matrix,

(e) multiplying each binary error vector by a third permutation matrix,

(f) selecting the scrambled binary message vector of length k bits from each permuted codeword,

(g) descrambling each binary message vector by the inverse of the k-bit to k-bit scrambler used in encryption to form r unscrambled k-bit binary message vectors,

(h) deriving each scrambled binary message vector of length u bits from each permuted binary error vector,

(i) descrambling each scrambled u bit binary message vector by the inverse of the u bit to u bit scrambler used in encryption to form r unscrambled u bit binary message vectors,

(j) reformatting the r unscrambled k-bit and u bit binary message vectors removing appended dummy bits to form the original digital message.

15. A method for reconstructing a message from a digital cryptogram constructed according to claim 6 by means of a private key algorithm comprising:

(a) retrieving said cryptogram from a communications channel or storage medium as r retrieved vectors, each of length n symbols,

(b) multiplying each retrieved vector by a first permutation matrix to obtain a codeword of the Goppa code used in creating the public key scrambled generator matrix, corrupted with no more than t bit errors,

(c) applying an error correcting decoding algorithm to each corrupted codeword to form r binary codewords of the Goppa code and r binary error vectors,

(d) multiplying each binary codeword of the Goppa code by a second permutation matrix,

(e) multiplying each binary error vector by a third permutation matrix,

(f) deriving a vector of length u+v bits from each permuted binary error vector,

(g) selecting each v bit vector,

(h) deriving a k-bit to k-bit descrambler and a u bit to u bit descrambler from each v bit vector,

(i) selecting the scrambled binary message vector of length k bits from each permuted codeword,

(j) descrambling each scrambled k-bit binary message vector by the k-bit to k-bit descrambler to form r unscrambled k-bit binary message vectors,

(k) selecting each u bit vector derived from each permuted binary error vector,

(l) descrambling each u bit vector by the u bit to u bit scrambler to form r unscrambled u bit binary message vectors,

(m) reformatting the r unscrambled k-bit and u bit binary message vectors removing appended dummy bits to form the original digital message.

16. A method according to claim 11 for reconstructing the messages from two or more digital cryptograms in which a message is authenticated by satisfying the conditions that the same message is reconstructed and the error patterns in corresponding corrupted code words have the same bits in error in no more than a specified number of bit positions.

17. A method of decrypting data according to claim 11 in which the descrambling is carried out by an arrangement producing a k-bit binary output vector which is equivalent to a polynomial multiplication, modulo 1+x^k of a first polynomial of degree k−

1 defined by a k-bit binary input vector and a second fixed polynomial of degree k−

1, where k is an integer.

18. A method of decrypting data according to claim 11 in which the u bit descrambling is carried out by an arrangement producing a u bit binary output vector which is equivalent to a polynomial multiplication, modulo 1+x^u of a first polynomial of degree u−

1 defined by a u-bit binary input vector and a second fixed polynomial of degree u−

1, where u is an integer.

21. A method of encrypting data according to claim 1, further comprising a selector operable to select the integer s such that s≦

t for each codeword vector.

24. An apparatus for decrypting data according to claim 12 in which the descrambler is carried out by a shift register arrangement featuring a first shift register with fixed tap positions and a second feedback shift register producing a w bit binary output vector which is equivalent to a polynomial multiplication, modulo 1+x^k of a first polynomial of degree k−

1 defined by the w bit binary input vector and a second polynomial of degree k−

1 defined by the fixed tap positions of the first shift register, where k is an integer.

25. An apparatus for decrypting data according to claim 12 in which the u bit descrambler is carried out by a shift register arrangement featuring a first shift register with fixed tap positions and a second feedback shift register producing a u bit binary output vector which is equivalent to a polynomial multiplication, modulo 1+x^u of a first polynomial of degree u−

1 defined by the u bit binary input vector and a second polynomial of degree u−

1 defined by the fixed tap positions of the first shift register, where u is an integer.

19. Apparatus for encrypting data by constructing a digital cryptogram by means of a public key algorithm, comprising:

(a) a first constructor operable to construct a first generator matrix of a binary code with dimension k with a pre-selected Galois field whose base field is 2, and a Goppa polynomial whose degree is such that the corresponding binary code provides at error correcting capability by utilising n−

k parity bits,

(b) a second constructor operable to construct 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 first permutation matrix,

(c) a third constructor operable to construct a reduced echelon k×

n generator matrix by randomly selecting k independent columns of the scrambled k×

n generator matrix according to a second permutation matrix,

(d) a convertor operable to convert 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,

(e) a scrambler operable to scramble each binary message vector using a k-bit to k-bit invertible scrambler,

(f) an encoder operable to encode each scrambled binary message vector by adding rows of said reduced echelon generator matrix according to the is in each scrambled message vector to form r codeword vectors of length n bits,

(g) an adder operable to add to each codeword vector using modulo 2 arithmetic an error vector of length n bits, containing s bit errors where s≦

t, and

(h) a former operable to form a cryptogram from the r said corrupted codeword vectors.

20. An apparatus for encrypting data according to claim 19, further comprising a permuter operable to use a third permutation matrix to permute the bits of each codeword.

22. An apparatus for encrypting data according to claim 19 in which the k-bit invertible scrambler is carried out by a shift register arrangement featuring a first shift register with fixed tap positions and a second feedback shift register producing a w bit binary output vector which is equivalent to a polynomial multiplication, modulo 1+x^k of a first polynomial of degree k−

1 defined by the w bit binary input vector and a second polynomial of degree k−

1 defined by the fixed tap positions of the first shift register, where k is an integer.

23. An apparatus for encrypting data according to claim 19 in which the u bit invertible scrambler is carried out by a shift register arrangement featuring a first shift register with fixed tap positions and a second feedback shift register producing a u bit binary output vector which is equivalent to a polynomial multiplication, modulo 1+x^u of a first polynomial of degree u−

1 defined by the u bit binary input vector and a second polynomial of degree u−

1 defined by the fixed tap positions of the first shift register, where u is an integer.

26. An apparatus according to claim 19 in which a passive RFID or barcode system encrypts information securely such that the information can only be retrieved using the private key.

27. An apparatus according to claim 19 using a mobile phone to encrypt information securely onto a 2D barcode such that the information can only be retrieved by a mobile phone using the private key.

28. An apparatus according to claim 19 in which an active RFID system encrypts information and transmits the cryptogram using wireless such that the information cannot be retrieved using a wireless receiver without the knowledge of the private key.

29. An apparatus according to claim 19 in which an RFID system encrypts information and transmits cryptograms using wireless such that authentication is provided using a wireless receiver with the knowledge of the private key.

30. An apparatus according to claim 19 in which a packet radio system encrypts information and transmits cryptograms using wireless such that authentication is provided using a radio receiver with the knowledge of the private key.

31. An apparatus according to claim 19 in which an e-mail or text messaging service encrypts information using a public key and transmits the cryptogram such that the information cannot be retrieved by interception of the transmission without the knowledge of the private key.

32. A non-transitory computer-readable storage medium storing computer-executable instructions that when executed perform the 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 pre-selected Galois field whose base field is 2, and a Goppa polynomial whose degree is such that the corresponding binary code provides at 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 first permutation matrix,

(c) constructing a reduced echelon k×

n generator matrix by randomly selecting k independent columns of the scrambled k×

n generator matrix according to a second permutation matrix,

(d) 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,

(e) scrambling each binary message vector using a k-bit to k-bit invertible scrambler,

(f) encoding each scrambled binary message vector by adding rows of said reduced echelon generator matrix according to the is in each scrambled message vector to form r codeword vectors of length n bits,

(g) adding to each codeword vector using modulo 2 arithmetic an error vector of length n bits, containing s bit errors where s≦

t, and

(h) forming a cryptogram from the r said corrupted codeword vectors.