ヒルの暗号。 詳細分析

この出版物では、ヒルアルゴリズムを使用した暗号化と復号化を可能な限り詳細に説明しようとします。 だから、これ以上苦労することなく、まさにその通りです。

暗号化

Hillアルゴリズムを使用してテキストを暗号化するには、次の手順を実行する必要があります。

1. コード化されたアルファベットを作成します。 ロシア語のテキストを暗号化するとします。 アルファベットの長さは33文字になります。 アルファベットにさらに4文字を追加して選択することをお勧めします。「？」、「。」、「、」、「」を追加します。 これは、アルファベットの長さが素数になるように行われます。 それだけで完全に1で割られる数 1以外の一般的な除数はありませんでした。アルファベットの長さが素数の場合、この条件が満たされるキーがはるかに多くあります。 アルファベットの各文字には整数コードが割り当てられています。 文字番号を使用するのが最も便利です。 したがって、エンコードされたアルファベットを取得します。
   
   
   
   
2. 次に、暗号化するテキストを取得し、アルファベットを使用してエンコードします。 「Cipher」という単語を例にとると、そのコードは25 9 21 17のようになります。
   
   
3. ここで、キーとして使用するキーワードまたは文字セットのみを選択します。 このキーワードの長さは整数の2乗に等しいことが重要です。 4、9、16、25など そうしてはじめて、暗号化に必要な正方行列にすることができます。 「アルピニス」という言葉を選びました。 アルファベットを使用してエンコードします。 0 12 29 16 9 14 9 8 13を取得します。 キーを3x3マトリックスの形式で記述します。
   
   
   
   より便利な場合は、キーをマトリックスですぐに設定できます。 キーワードを使用しました。
   
   
4. ここで、テキストをそれぞれn文字のブロックに分割する必要があります。この場合、マトリックスのn次元は3です。分割を始めましょう。
   
   最初のブロック： （25 9 21）
   
   2番目のブロックには、残りの番号は1つしかありません-17。この場合の最も簡単な解決策：できるだけ多くの文字を追加して、ブロック全体を形成します。 スペースを追加することにしました。
   
   次に、2番目のブロック： （17 35 35）
   
   
5. 次に、テキストを暗号化します。 テキスト暗号化の場合、各ブロックとキーのマトリックスのマトリックス乗算を実行する必要があります。 ここでは、行ではなく列にブロックを書き込むことができることに注意してください。 次に、キーに列を掛けますが、これは大きな違いではありません。
   
   この暗号のもう1つの重要な要素は、キーマトリックスの決定要因です。ゼロ以外である必要があります。そうでない場合、暗号化されたテキストを解読することはできません。
   
   したがって、最初のブロックにキーを乗算します。
   
   
   
   2番目のブロックにキーを乗算します。
   
   
   
   行列の乗算は複雑な演算ではないため、詳しく説明しませんでした。
   ここで、結果の行列を法37で除算する必要があります。 37による除算の残りを取ります。
   
   最初の行列を分割します。
   
   
   
   2番目の行列を分割します。
   
   
   
   なぜ37で割るのですか？ これはアルファベットの長さであるため、異なる長さのアルファベットがある場合は、異なる数で割ります。 たとえば、英語のアルファベットの場合、26で除算するか、文字を追加した場合は29で除算します。
   
   
6. 次に、アルファベットを使用して結果のマトリックスをデコードします。
   
   最初のマトリックス：AYUN
   2番目のマトリックス：CHYA
   
   2つの行列を接着し、暗号文を取得します：AYUNCHHYA
   

解読

次に、復号化に進みます。 復号化は、次のアルゴリズムに従って実行されます。

1. 暗号文を数字に逆コーディングし、ブロックに分割します。
   
   
2. キー行列の行列式を見つけます。
   
   
   
   行列式の検索も非常に簡単な操作なので、ペイントしませんでした。
   
   
3. ここで、拡張ユークリッドアルゴリズムを使用して、 d 、 x 、 yを見つけます。
   
   説明とアルゴリズム自体については説明しません。 このアルゴリズムに関する情報は、インターネットで簡単に見つけることができます。 アルゴリズムの入力で、 det Kとアルファベットの長さを指定します。 出力では、 d = 1 、 x = -4 、 y = 41を取得します。 興味があるのはxだけです。
   
   
4. 複雑で重要なことです。 37を法とするリングの要素の逆行列式を見つける必要があります。 これを行うには、次を実行します。
   
   •行列式が負でxが正の場合、行列式の逆はxになります。
   •行列式が正でxが負の場合、行列式の逆数は37 + xになります。
   •行列式が正でxが正の場合、行列式の逆はxになります。
   •行列式とxが負の場合、逆は-xになります。
   
   実験的に逆要素を検索するためにこのアルゴリズムを選択しました。 このトピックに役立つものは見つかりませんでした。 いずれにせよ、このアルゴリズムが原始的であっても機能します。
   
   したがって、行列式は379であり 、正であり、 xは-4-負です。 次に、式37 + x = 37 +（-4）= 37-4 = 33によって、行列式に逆の要素を見つけます。
   
   
5. インターネットで有用な情報を見つけることができなかったため、私は長い間苦しんでいた別の瞬間があります。 37を法とするキー行列の逆行列を見つける必要があります。 このマトリックスを見つけるために、キーの代数的補数のマトリックスとキーマトリックスの逆行列式を見つける必要があります（前の段落で既に見つかりました）。 代数的加算の行列も見つけるのが非常に簡単で、ペイントしません。 この場合、次のようになります。
   
   
   
   ここで、この行列を法で37で除算します。これはすでに暗号化で描いています。 このような行列を取得します。ここでは、要素の符号を失わないことが重要です（マイナスの損失でモジュロ除算を行うものもあります。これはこのアルゴリズムでは受け入れられません）。
   
   
   
   代数補数の行列に要素の逆行列式を掛けます。 次のマトリックスを取得します。
   
   
   
   この行列を法で37で除算します。
   
   
   
   それを転置します（場所の行と列を入れ替えます）：
   
   
   
   マトリックス要素が負の場合、式37+ <element>で計算された別の要素に変更します 。
   
   
   
   最後に取得される行列は、キー行列の逆モジュロです。 キーのマトリックスとこのマトリックスを乗算し、結果をモジュロ37で除算すると、恒等マトリックス、つまり 次の形式の行列：
   
   
   
   
6. 暗号文を解読するには、暗号文の行にキーの逆行列を掛けます。
   最初の行を乗算します：
   
   
   
   2行目を乗算します。
   
   
   
   結果の行を37モジュロで除算します。
   
   
   
   マトリックス（25 9 21 13 35 35）を接着し、アルファベット：暗号を使用してデコードします。
   
   結果として、最後に余分なスペースが2つあるソーステキストが得られましたが、これは何の役割も果たしていません。
   

ご清聴ありがとうございました！