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 

爲什麼我的解密結果從我的純文本消息不同？

這是我到目前爲止有：對McEliece公鑰體制密碼

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 . 

更多細節可以在這裏找到：

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

我試圖實現這個例子在上面的鏈接給出：

例如，我們將使用（7,4）漢明碼corr影響所有 單個錯誤。對於這個碼的生成矩陣由下式給出（注意 聰明的選擇）：

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

和Bob選擇的擾頻器矩陣

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

鮑勃使得公開發電機矩陣

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

如果Alice希望將消息發送x = (1 1 0 1)給Bob，她第一 構造一個權重1的誤差矢量，說e = (0 0 0 0 1 0 0)和 計算

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

她然後發送給Bob。

在接收y，鮑勃首先計算y' = yP^-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]; 

獲得y' = (1 0 0 0 1 1 1)。現在Bob用快速的 解碼算法解碼y'（在這個例子中是Hamming解碼）。 y'的徵狀是(1 1 1 0)T，所以錯誤發生在位置7（細節 省略）。鮑勃現在擁有代碼字y'' = (1 0 0 0 1 1 0)。因爲聰明的選擇 爲G，Bob知道xS = (1 0 0 0)，他 現在可以通過矩陣

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

獲得

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

Answer 1

真的，我只是跟着你tutorial link相乘獲得x，看起來你最終在掙扎，並停止了教程中的內容？該算法詳細描述如下，如下所示。

您遇到的主要問題是您根本不需要linsolve。我所做的關鍵改變來自代碼的最後一塊 - 解密。兩兩件事：

1. 使用正斜槓操作is better比使用inv()。從用於反斜槓操作者（相當於預乘法）的文檔：

   X = A \ B被計算不同於X = INV（A）* B，推薦用於求解線性方程組

   的系統

2. 使用關於生成矩陣如何形成的信息，該算法變得更加容易，如鏈接教程中所述。

   [通過寫入]標準形式[Ik A]G，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