McEliece encryption/decryption algorithm

Question

I'm trying to program the McEliece cryptosystem, but I'm having trouble combining the binary vectors and linsolve section in the decryption step of the algorithm.

I'm expecting the array m to be equal to the message array x after decryption, but I'm getting the wrong result:

x =
     1     1     1     1

ciphertext =
     1     1     1     1     0     1     1

m =
    1.2500    0.5000    0.5000    0.7500

Why does my decrypted result differ from my plain-text message?

Here is what I have so far:

clc;clear all;
n = 7;
k = 4; %Let C be an (n,k)-linear code
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]; %Let G be a generator matrix for C.
s = [ 1 1 0 1
      1 0 0 1
      0 1 1 1
      1 1 0 0]; %Alice selects a random (k x k) binary non-singular matrix S
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]; %Alice selects a random (n x n) permutation matrix P.

    % s , g and p is private key ( alice has a private key )
    % g'=s*g*p is public key (alice compute the public key and send to Bob )

gg = s*g*p; %Alice computes the (n x k)matrix g'=s*g*p .
key = mod(gg,2); % public key
x = [ 1 1 1 1 ] %message
t = 1;
e = [ 0 0 0 0 1 0 0 ]; % the erorr

%%the Encryption (( Bob Encrypt the message x by using the public key) )
y = x*key;
y1=mod(y,2);
ciphertext=mod((y+e),2) % ciphertext is Encrypt the message x ( send the ciphertext to Alice)

%%the Decryption ((alice decrypt the ciphertext , the result must equal to the orginal message x  ( by using the private key) ))
yy = ciphertext*inv(p);
ee = e*inv(p);
xsg = mod((yy-ee),2);
xs = linsolve(g',xsg');
m = mod((xs' * inv(s)),2) % m must equal to x .

More details on the McEliece cryptosystem can be found here:

http://www-math.ucdenver.edu/~wcherowi/courses/m5410/ctcmcel.html

I tried to implement this example given in the above link:

For an example we shall use the (7,4) Hamming code which corrects all single errors. A generator matrix for this code is given by (note the clever choice):

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

and Bob chooses the scrambler matrix

S = [1  1  0  1
     1  0  0  1
     0  1  1  1
     1  1  0  0];

and the permutation matrix

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

Bob makes public the generator matrix

G' = SGP = [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];

If Alice wishes to send the message x = (1 1 0 1) to Bob, she first constructs a weight 1 error vector, say e = (0 0 0 0 1 0 0) and computes

y = xG' + e 
  = (0 1 1 0 0 1 0) + (0 0 0 0 1 0 0)
  = (0 1 1 0 1 1 0)

which she then sends to Bob.

Upon receiving y, Bob first computes y' = yP^-1, where

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

obtaining y' = (1 0 0 0 1 1 1). Now Bob decodes y' by the fast decoding algorithm (Hamming decoding in this example). The syndrome of y' is (1 1 1 0)T, so the error occurs in position 7 (details omitted). Bob now has the code word y'' = (1 0 0 0 1 1 0). Because of the clever choice for G, Bob knows that xS = (1 0 0 0), and he can now obtain x by multiplying by the matrix

 S-1 = [1  1  0  1
        1  1  0  0
        0  1  1  1
        1  0  0  1];

obtaining

x = (1 0 0 0)S^-1 = (1 1 0 1).

Answer 1

Nice example. Added error removal. Tested in Octave

% Further references
%   https://www.avoggu.com/posts/an-efficient-algorithm-for-hamming-(74)-decoding-matlab-implementation/
%   https://www.tutorialspoint.com/hamming-code-for-single-error-correction-double-error-detection
%   https://en.wikipedia.org/wiki/Hamming(7,4)
%   http://michael.dipperstein.com/hamming/index.html


n=7;
%% Individual message size
k=4;
%% Generator Matrix
    %d1 d2 d3 d4 p1 p2 p3 
G = [ 1, 0, 0, 0, 1, 1, 0;... %d1
      0, 1, 0, 0, 1, 0, 1;... %d2
      0, 0, 1, 0, 0, 1, 1;... %d3
      0, 0, 0, 1, 1, 1, 1;];  %d4
%% Parity check
    %d1 d2 d3 d4 p1 p2 p3
H = [ 1, 1, 0, 1, 1, 0, 0;  %p1
      1, 0, 1, 1, 0, 1, 0;  %p2
      0, 1, 1, 1, 0, 0, 1;];%p3 
%% A random invertible scrambler binary random matrix 
S=zeros(k);
while ( abs(cond(S)) > 10 )  
  S = rand(k) > 0.5;
endwhile
%% A random permutation matrix
P = eye(n) (:,randperm(n));

%% Public key
Gprime = mod(S*G*P,2);

%% message
message = [1,1,0,1]
%% error vector
error = [1,0,0,0,0,0,0]  (1,randperm(n));

%% encrypted message 
encrypted_message = mod(message*Gprime + error,2)

% Decryption
% Undo permutation
encrypted_message = mod(encrypted_message/P,2);
% Remove error
find_error = mod(H*encrypted_message',2);
%% Use a lookup table bit to flip
error_position_table=[5,6,1,7,2,3,4];
error_indicator = (find_error(1))*1 + ...
                  (find_error(2))*2 + ...
                  (find_error(3))*4;
if error_indicator > 0                  
  encrypted_message(error_position_table(error_indicator)) +=1;
endif
xSG = mod(encrypted_message,2);
% Due to ordering of columns in G message is in first k columns
xS = xSG(1:k);
decrypted_message = mod(round(xS/S),2)

Answer 2

Really I just followed your tutorial link, it seems like you struggled at the end and stopped doing what was in the tutorial? The algorithm is detailed well enough to follow, as below.

The main issue you were having is that you didn't need linsolve at all. The key changes I've made come in the last block of the code - the decryption. Two main things:

1. Using the forward slash operator is better than using inv(). From the documentation for the back slash operator (equivalent for pre-multiplication):

   x = A\b is computed differently than x = inv(A)*b and is recommended for solving systems of linear equations

2. Using information about how the generator matrix was formed, the algorithm becomes much easier, as noted in your linked tutorial.

   [By writing] G in standard form [Ik A], xS would just be the first k positions of xSG

Corrected code with comments:

clc; clear all;
% McEliece Encryption / Decryption, source material for example:
% http://www-math.ucdenver.edu/~wcherowi/courses/m5410/ctcmcel.html

n = 7;

%Let C be an (n,k)-linear code
k = 4; 

%Let G be a generator matrix for C.
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];
%Alice selects a random (k x k) binary non-singular matrix S     
S = [1 1 0 1
     1 0 0 1
     0 1 1 1
     1 1 0 0]; 
%Alice selects a random (n x n) permutation matrix P.
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];

% S, G and P are the private key (Alice has a private key)
% GG = S*G*P is public key (Alice computes the public key and sends it to Bob)
GG = S*G*P; 

publickey = mod(GG,2);  % public key

% --- public key sent from Alice to Bob --- %

% Bob wants to send a message, msg, so encrypts it using Alice's public key
msg = [1 1 0 1]       % message
e = [0 0 0 0 1 0 0];  % the weight vector - treated as an error by Alice

% Encryption 
y = msg*publickey;
% ciphertext is the encrypted message (send the ciphertext to Alice)
ciphertext = mod((y+e),2) 

% --- message sent from Bob to Alice --- %

% Decryption (Alice decrypts the ciphertext by using the private key, 
% the result must be equal to the orginal message

% Using a forward slash can be quicker and more accurate than inv() 
YY = ciphertext/P;

ee = e/P;

xSG = mod((YY-ee),2);

% Because G was of the form [I_k, A], xS is just the first k positions of
% xSG, and no multiplication is needed. This can be found in source material.

xS = xSG(1:k);

decoded = mod(xS/S,2)

Output:

msg =

    1     1     0     1


ciphertext =

     0     1     1     0     1     1     0


decoded =

     1     1     0     1