問題タブ [galois-field]

AES暗号化を実装しています。混合列/逆混合列の手順では、ガロア体の乗算を行う必要があります。次のドキュメントのルックアップ テーブルを使用しています (セクション 5.4.2) https://www.ime.usp.br/~rt/cranalysis/AESSimplified.pdf

上記のセクションに移動すると、L テーブルの (0,0) 列は空です。では、L(0,0) を検索する必要がある場合、何を返せばよいでしょうか。0 を返そうとしましたが、暗号化が間違っています。

消去とエラーの両方のデコードをサポートする Python で Reed-Solomon エンコーダー/デコーダーを実装しようとしていますが、それが私を夢中にさせています。

実装は現在、エラーのみまたは消去のみのデコードをサポートしていますが、同時に両方をサポートすることはありません (たとえ 2*errors+erasures <= (nk) の理論的境界を下回っていたとしても)。

Blahut の論文 ( hereおよびhere ) から、Berlekamp-Massey 内のエラーロケータ多項式を暗黙的に計算するには、エラー ロケータ多項式を消去ロケータ多項式で初期化するだけでよいようです。

このアプローチは私にとって部分的に機能します: 2*errors+erasures < (nk)/2 の場合は機能しますが、実際にはデバッグ後にのみ機能します。これは、BM が消去ロケーター多項式とまったく同じ値を取得するエラー ロケーター多項式を計算するためです。 (エラーのみの修正の制限を下回っているため)、ガロア フィールドを介して切り捨てられ、消去ロケータ多項式の正しい値になります (少なくともそれが私が理解している方法であり、間違っている可能性があります)。

ただし、(nk)/2 を超えると、たとえば n = 20 で k = 11 の場合、(nk)=9 個の消去されたシンボルがあり、修正できます。5 個の消去をフィードすると、BM はうまくいきません。4 個の消去 + 1 個のエラー (2*エラー + 消去 = 2+4 = 6 < 9 であるため、まだ境界をはるかに下回っています) をフィードした場合でも、BM は正しく動作しません。

私が実装した Berlekamp-Massey の正確なアルゴリズムは、このプレゼンテーション(15 ～ 17 ページ) にありますが、非常によく似た説明がこことここにあります。ここに、数学的な説明のコピーを添付します。

これで、この数学的アルゴリズムを Python コードにほぼ正確に再現できました。私が望むのは、消去ロケーターでエラーロケーターシグマを初期化することによって試みた消去をサポートするように拡張することです:

Polynomial と GF256int は、それぞれ 2^8 上の多項式とガロア体の一般的な実装です。これらのクラスは単体テスト済みで、通常はバグが証明されています。Forney や Chien 検索など、Reed-Solomon の残りのエンコード/デコード方法についても同様です。ここで話している問題の簡単なテスト ケースを含む完全なコードは、http: //codepad.org/l2Qi0y8oにあります。

出力例を次に示します。

ここでは、イレージャー ロケーターの計算に BM をまったく使用しないため、イレージャー デコードは常に正しく行われます。通常、他の 2 つのテスト ケースは同じシグマを出力するはずですが、そうではありません。

問題が BM に起因するという事実は、最初の 2 つのテスト ケースを比較すると明らかです。シンドロームと消去ロケータは同じですが、結果のシグマはまったく異なります (2 番目のテストでは BM が使用され、消去のみの最初のテスト ケース BM は呼び出されません)。

これをデバッグする方法についての助けやアイデアをありがとう。あなたの答えは数学でもコードでもかまいませんが、私のアプローチで何がうまくいかなかったのか説明してください.

/編集:エラータ BM デコーダーを正しく実装する方法がまだ見つかりませんでした (以下の私の回答を参照してください)。この報奨金は、問題を解決できる (または少なくとも私を解決策に導いてくれる) 人に提供されます。

/EDIT2:愚かな私、申し訳ありませんが、スキーマを読み直したところ、割り当ての変更を見逃していることがわかりましたL = r - L - erasures_count...コードを更新して修正し、回答を再承認しました。

バイナリ行列 A( と のみ)1と、ガロア体 (256)0のベクトルがあります。DベクトルCは次のように計算されます。

ここで、A^^-1は の行列の逆行列を表しA、GF(2)は*乗算演算です。結果ベクトルCは にある必要がありますGF(256)。Matlabでやってみました。

ただし、上記のコードでは、期待した結果を達成できません

次のようなエラーが発生します

期待した結果を達成するのを手伝ってもらえますか?

ガロア体での 2 の乗算から Matlab の C コードを転写しています。問題は、私の matlab コードが C コードと同じ値を表示していないことです。どうやらすべて問題ありません。コードの下にある C コードの適応を識別するために、matlab のコードにコメントを付けました。

子：

出力：

マットラボ:

出力：

C コードは正しく動作%dします。コードの冒頭でキャストされているため、変数の整数値を表示するために C コードを出力しています。

誰かが何が起こっているのか知っています