McEliece加密/解密算法

Question

我试图对McEliece密码系统进行编程，但是在算法的解密步骤中，我很难将二进制向量和linsolve部分组合起来。

我期望数组m在解密后与消息数组x相等，但是我得到了错误的结果：

x =
     1     1     1     1

ciphertext =
     1     1     1     1     0     1     1

m =
    1.2500    0.5000    0.5000    0.7500

为什么我的解密结果与我的纯文本信息不同？

以下是我到目前为止所拥有的：

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 .

有关McEliece密码系统的更多细节可以在这里找到：

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

我尝试实现上述链接中给出的示例：

例如，我们将使用(7,4) Hamming码来纠正所有单个错误。此代码的生成器矩阵由(注意聪明的选择)提供： G=1 0 0 0 1 1 1 0 0 1 0 1 0 1 0 0 1 1 0 0 1 0 0 1 1 0 0 0 1 1 1； 而Bob选择了扰码矩阵 S=1 1 0 1 1 0 0 1 1 1 0 0； 和置换矩阵 P=0 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 0 0 0 Bob公开了生成器矩阵。 G‘= SGP =1 1 1 0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 如果Alice希望将消息x = (1 1 0 1)发送给Bob，她首先构造一个权重1错误向量，比如e = (0 0 0 0 1 0 0)并计算。 Y= xG‘+e= (0 1 1 0 0 0 1 0) + (0 0 0 1 0 0) = (0 1 1 0 1 1 0) 然后她寄给鲍勃。 在接收到y后，Bob首先计算y' = yP^-1，其中 P^-1 =0 0 0 1 0 0 1 0 0 0 获得y' = (1 0 0 0 1 1 1)。现在，Bob用快速解码算法(在本例中为Hamming解码)对y'进行解码。y'的症候群是(1 1 1 0)T，因此错误发生在位置7(细节省略)。现在，Bob的代码是y'' = (1 0 0 0 1 1 0)。由于对G的明智选择，鲍伯知道xS = (1 0 0 0)，现在他可以通过乘以矩阵获得x。 S-1 =1 1 0 1 1 1 0 0 1 1 1 0 0 1； 获取 X= (1 0 0 0)S^-1 = (1 1 0 1)

Answer 1

真的，我只是跟着你的教程链接，似乎你在最后挣扎，停止做教程中的内容？算法非常详细，如下所示。

您所遇到的主要问题是您根本不需要linsolve。我所做的关键改变出现在代码的最后一块--解密。主要有两件事：

1. 使用正斜杠运算符是更好的比使用inv()。来自反斜杠运算符的文档(等效于预乘法)： X= A\b的计算方法不同于x= inv(A)*b，建议用于求解线性方程组。
2. 使用有关生成器矩阵如何形成的信息，该算法将变得更容易，正如您在链接教程中所指出的那样。 通过以标准表格G [Ik A]编写xS，xS将成为xSG的第一个k职位。

更正后的代码及注释：

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)

输出：

msg =

    1     1     0     1


ciphertext =

     0     1     1     0     1     1     0


decoded =

     1     1     0     1

Answer 2

很好的例子。添加错误删除。在八度中测试

% 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)