This page provides a simple explanation of how the key is created for McEliece crypto. It uses a (7,4) Hamming code with one bit error correction [Hamming code][McEliece crypto]
McEliece with Hamming Codes |
Hamming codes
With (7,4) Hamming code we take 4 bits of data and add 3 Hamming bits to give 7 bits for each 4-bit value. We create a code generator matrix G and the parity-check matrix H. The input data is multiplied by G, and then to check the result is multiplied by H:
\(H=\begin{bmatrix} 1 0 0 0 1 1 1 \\ 0 1 0 0 0 1 1 \\ 0 0 1 0 1 0 1 \\ 0 0 0 1 1 1 0 \end{bmatrix}\)
\(G=\begin{bmatrix} 1 0 0 0 1 1 1 \\ 0 1 0 1 0 1 1 \\ 0 0 1 1 1 0 1 \end{bmatrix}\)
If we have a data input of [1 0 1 0] then to create the message to send we get:
\( Output= \begin{bmatrix}1 0 1 0\end{bmatrix} \times \begin{bmatrix} 1 0 0 0 1 1 1 \\ 0 1 0 0 0 1 1 \\ 0 0 1 0 1 0 1 \\ 0 0 0 1 1 1 0 \end{bmatrix} = \begin{bmatrix}1 0 1 1 0 1 0\end{bmatrix} \)
The bits transmitted will thus be “1 0 1 1 0 1 0”.
\( Received= \begin{bmatrix} 1 0 1 1 1 0 0 \\ 1 1 0 1 0 1 0 \\ 1 1 1 0 0 0 1 \end{bmatrix} \times \begin{bmatrix}1 \\ 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} \)
which identifies there are no errors. For a data input of “1010”, we get the following:
Input Coded (1 error) Error Position [1 0 1 0] [1 0 1 1 0 1 0] [0 0 0] ---------------------- Single Errors: Input Coded (1 error) Error Position [1 0 1 0] [0 0 1 1 0 1 0] [1 0 0] [1 0 1 0] [1 1 1 1 0 1 0] [0 1 0] [1 0 1 0] [1 0 0 1 0 1 0] [0 0 1] [1 0 1 0] [1 0 1 0 0 1 0] [0 1 1] [1 0 1 0] [1 0 1 1 1 1 0] [1 0 1] [1 0 1 0] [1 0 1 1 0 0 0] [1 1 0] [1 0 1 0] [1 0 1 1 0 1 1] [1 1 1]
It can be seen that the data is “1010” and after the Hamming bits are added the result is “1011010”. If there are no errors the result is “000”, which means there are no errors.
If we add an error of the first coded bit we get a received value of “0 0 1 1 0 1 0”. The result is then “100” which identifies that Bit 0 is in error. If we look at an error in the next bit, we get a value of “010” which identifies that position is in error, and so each result correctly identifies the error, and we can thus correct it (for single-bit errors). And now we will use this method to perform our encryption.
McEliece with Hamming codes
We illustrate the process with a (7,4) Hamming code which corrects one error. The generator matrix is then:
1 0 0 0 1 1 1 G = 0 1 0 0 0 1 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0
Bob then selected a scrambler matrix (S):
1 1 0 1 S = 1 0 0 1 0 1 1 1 1 1 0 0
And also a permutation matrix
0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 P = 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0
Bob public key then becomes the dot product of these matrices
1 1 0 1 0 1 0 G' = SGP = 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 1 1 1 0 0 0
Bob will use \(G'\) as a public key, but \(S\), \(G\) and \(P\) are secret. Next, for Alice to send a ciphered message to Bob, she converts the message into binary vectors of length \(k\).
For a message of m Alice will create randomly a binary \(n\)-vector of weight \(t\), and randomly places \(t\) ones in a zero vector of length n).
This is then sent to Bob:
\(y = mG' + e\)
Bob then decrypts with:
\(yP^{-1} = (mG' + e)P^{-1} = mSG + eP^{-1} = mSG + e'\)
At this stage, we will use our H matrix to determine the syndrome, and identify where the error is. As the position of the error would have changed because of the permutation matrix, we need to remap the position of the error.
Sample run
A sample run is:
Message: [1. 0. 1. 1.] G: [[1 0 0 0 1 1 1] [0 1 0 0 0 1 1] [0 0 1 0 1 0 1] [0 0 0 1 1 1 0]] S: [[1 1 0 1] [1 0 0 1] [0 1 1 1] [1 1 0 0]] P: [[0 1 0 0 0 0 0] [0 0 0 1 0 0 0] [0 0 0 0 0 0 1] [1 0 0 0 0 0 0] [0 0 1 0 0 0 0] [0 0 0 0 0 1 0] [0 0 0 0 1 0 0]] Result (GSP): [[1 1 0 1 0 1 0] [1 1 0 0 1 0 0] [1 0 0 1 0 0 1] [0 1 1 1 0 0 0]] Cipher: [0. 0. 1. 1. 1. 1. 1.] P^{-1}: [[0. 0. 0. 1. 0. 0. 0.] [1. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 1. 0. 0.] [0. 1. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 1.] [0. 0. 0. 0. 0. 1. 0.] [0. 0. 1. 0. 0. 0. 0.]] syndrome': [1. 1. 0.] 3.0 Error position: 5 y': [0. 1. 1. 0. 1. 1. 1.] y' (corrected): [0. 1. 1. 0. 0. 1. 1.] S^{-1}: [[1. 1. 0. 1.] [1. 1. 0. 0.] [0. 1. 1. 1.] [1. 0. 0. 1.]] Decipher: [1. 0. 1. 1.]
Coding
The following is an outline:
import numpy import sys import io g =numpy.array([[1,0,0,0,1,1,1],[0,1,0,0,0,1,1],[0,0,1,0,1,0,1],[0,0,0,1,1,1,0]]) h=numpy.array([[1,0,0,0,1,1,1],[0,1,0,1,0,1,1],[0,0,1,1,1,0,1]]) s =numpy.array([[1,1,0,1],[1,0,0,1],[0,1,1,1],[1,1,0,0]]) p=numpy.array([[0,1,0,0,0,0,0],[0,0,0,1,0,0,0],[0,0,0,0,0,0,1],[1,0,0,0,0,0,0],[0,0,1,0,0,0,0],[0,0,0,0,0,1,0],[0,0,0,0,1,0,0]]) mapping=([4,1,5,2,7,6,3]) matrix = numpy.dot(s,g)%2 G_1 = numpy.dot(matrix,p)%2 message = ([1,1,0,0]) e = ([0,0,0,0,1,0,0]) if (len(sys.argv)>1): message=numpy.genfromtxt(io.StringIO(sys.argv[1]),delimiter=',') print('Message:\n',message) print('G:\n',g) print('S:\n',s) print('P:\n',p) print('Result (GSP):\n',G_1) res=numpy.dot(message,G_1)%2 cipher = numpy.add(res,e)%2 print('\nCipher:',cipher) p_1=numpy.linalg.inv(p)%2 print('\nP^{-1}:\n',p_1) y_1 = numpy.dot(cipher,p_1)%2 syndrome = numpy.dot(h,numpy.transpose(cipher))%2 error = syndrome[0]+2*syndrome[1]+4*syndrome[2] print("\nsyndrome\':",syndrome,error) error=mapping[int(error-1)] print ("Error position: ",error) print ("y': ",y_1) y_1[error-1]=(y_1[error-1]+1)%2 print ("y' (corrected): ",y_1) s_1=numpy.linalg.inv(s)%2 print ('\nS^{-1}:\n',s_1) # syn = ([1,0,0,0]) decipher = numpy.dot(y_1[0:4],s_1)%2 print ('\nDecipher:',decipher)