實現 Mceliece 加密 - 製作生成器矩陣
我正在研究Mceliece 加密系統 (MCE)和 Niederreiter 加密系統的實現。我已經通過有限域、多項式算術和一些編碼理論的基礎知識來理解它。
簡要給出 MCE 參數 $ n, k, t $ , 這樣就結束了 $ GF(2^m) $ , $ n = 2^m $ , $ k = n - mt $ 是線性碼的維數和 $ t $ 是沒有。程式碼將糾正的錯誤，公鑰是 $ X = S.G.P $ ， 在哪裡 $ S $ 是一個 $ k $ X $ k $ 非奇異矩陣， $ G $ 是個 $ k $ X $ n $ 線性碼的生成矩陣和 $ P $ 是一個 $ n $ X $ n $ 置換矩陣。
弄清楚如何獲得 $ G $ 是問題的原因。我想更好地理解生成矩陣是如何建構的，它的元素只是 $ 0 $ 或者 $ 1 $ , 一旦我們有了不可約的次數多項式 $ t $ ， 支持 $ L $ 和奇偶校驗矩陣 $ H $ . $ L $ & $ H $ 由以下元素組成 $ GF(2^m) $ 以二進制形式表示為多項式，例如 $ x^4 + x^2 + 1 $ 表示為 $ 10101 $ .
我知道有很多方法可以獲取生成器矩陣，但在網上找到的資訊有限。我歡迎對數學/算法的簡化解釋或任何指向站點/書籍的指針，這將有助於解決這個問題。
我將假設您使用的是二進制 Goppa 程式碼。這意味著，你得到支持 $ \mathbf{L} \in \mathbb{F}{2^m} $ , 一個 Goppa 多項式 $ \Gamma $ 度數為 t，係數為 $ \mathbb{F}{2^m} $ 並建構 GRS 程式碼的所有程式碼字，然後將它們與 $ \mathbb{F}_2^n $ ，導致程式碼實際上是 $ \mathbb{F}2^n $ （而不是 $ \mathbb{F}{2^m}^n $ ）。這是 McEliece 在其原始命題中使用的經典定義。
正如您可能已經閱讀的那樣，二進制 Goppa 程式碼有一個校驗矩陣（維基百科文章中有一個錯誤，這個是正確的）：
$$ H_{grs} = \begin{pmatrix} 1 & \dots & 1 \ L_0 & \dots & L_{n-1}\ L_0^2 & \dots & L_{n-1}^2\ \vdots & & \vdots\ L_0^{t-1} & \dots & L_{n-1}^{t-1}\end{pmatrix} \begin{pmatrix} \frac{1}{\Gamma(L_0)} & & \ & \ddots & \ & & \frac{1}{\Gamma(L_{n-1})} \end{pmatrix} $$ 現在，你是否清楚，這是一個 $ t \times n $ 矩陣 $ \mathbb{F}{2^m} $ 因此會給你程式碼字 $ \mathbb{F}{2^m}^n $ . 但我們只對暗語感興趣 $ \mathbb{F}_{2}^n $ . 可以得到一個校驗矩陣，它只給出程式碼字 $ \mathbb{F}2 $ 通過擴展矩陣中的每個條目 $ \mathbb{F}{2^m} $ .
這意味著，如果您輸入的矩陣表示為向量 $ 0101 $ 在 $ \mathbb{F}_2^4 $ （為了 $ m=4 $ )，您可以將此條目擴展為四個條目並將它們寫成四行：0、1、0、1。
範例：讓您的檢查矩陣中的一行 $ H_{grs} $ 是
$$ \begin{pmatrix}0101& 1010 &0001& 1000\end{pmatrix} $$ 那麼你可以這樣寫 $$ \begin{pmatrix} 0 & 1 & 0 & 1\ 1 & 0 & 0 & 0\ 0 & 1 & 0 & 0\ 1 & 0 & 1 & 0\end{pmatrix} $$ 您對所有行都執行此操作，最終會得到一個校驗矩陣 $ H $ 大小的 $ mt \times n $ ，因為您將每一行擴展為 $ m $ 行。從現在開始，你只需要加班 $ \mathbb{F}_2 $ ; 使用這個檢查矩陣，你會得到程式碼字 $ \mathbb{F}_2^n $ . 注意：此時您必須進行高斯消除以消除給出相同方程的行。這將減少您的行數並為您提供減小的校驗矩陣 $ (n-k) \times n $ ，其中 k 是二進制程式碼的維數。 現在，得到一個生成矩陣 $ G $ 對於該程式碼，您需要查找一個滿秩矩陣 $ H^\top G=0 $ . 有很多方法可以實現這一點，你應該找到足夠的材料。例如：http ://en.wikipedia.org/wiki/Parity-check_matrix 。請記住，如果 $ H $ 是一個校驗矩陣 $ G $ ， 然後 $ G $ 是一個校驗矩陣 $ H $ . 所以你建立 $ G $ 通過假裝 $ H $ 是一個生成器，您想為該程式碼找到一個校驗矩陣。
我希望這是你所要求的。