A Practical Example for McEliece Cryptography

A Practical Example for McEliece Cryptography

Using the (7,4) Hamming code with one bit error correction

Robert McEliece, in 1978, outlined the McEliece cryptosystem [here]:

Overall it is asymmetric encryption method (with a public key and a private key), and, at the time, looked to be a serious contender. Unfortunately for the method, RSA became the King of the Hill, and the McEliece method was pushed to the end of the queue for designers. It has basically drifted in the 38 years since. But, as an era of quantum computers is dawning, it is now being reconsidered, as it is seen to be immune to attacks using Shor’s algorithm.

This is based on the example [here]. 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  0
G = 0  1  0  0  1  0  1
    0  0  1  0  0  1  1
    0  0  0  1  1  1  1

Bob then selectes 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 (P):

     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’s public key (G′) then becomes the dot product of these matrices (S.G.P):

             1  1  1  1  0  0  0
G' = SGP   = 1  1  0  0  1  0  0
             1  0  0  1  1  0  1
             0  1  0  1  1  1  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 randomly create 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:

Sample run

A sample run is [here]:

Message: [ 1.  1.  0.  1.]
G:
[[1 0 0 0 1 1 0]
 [0 1 0 0 1 0 1]
 [0 0 1 0 0 1 1]
 [0 0 0 1 1 1 1]]
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:
[[1 1 1 1 0 0 0]
 [1 1 0 0 1 0 0]
 [1 0 0 1 1 0 1]
 [0 1 0 1 1 1 0]]

Cipher: [ 0.  1.  1.  0.  1.  1.  0.]

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.]]

y': [ 1.  0.  0.  0.  1.  1.  1.]

S^{-1}:
[[ 1.  1.  0.  1.]
 [ 1.  1.  0.  0.]
 [-0.  1.  1.  1.]
 [ 1.  0.  0.  1.]]

Decipher: [ 1.  1.  0.  1.]

Coding

The following is an outline:

import numpy
import sys

g =numpy.array([[1,0,0,0,1,1,0],[0,1,0,0,1,0,1],[0,0,1,0,0,1,1 ],[0,0,0,1,1,1,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]])	

print('G:\n',g)
print('S:\n',s)
print('P:\n',p)

matrix = numpy.dot(s,g)%2
G_1 = numpy.dot(matrix,p)%2

print('Result:\n',G_1)

message = ([1,1,0,1])
e = ([0,0,0,0,1,0,0])

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

print("\ny\':",y_1)

And you can run yourself:

Conclusions

While our existing public key methods are at risk from quantum computers, the McEliece public key method has stood the test of time, and it will still be a hard problem.