ヒル暗号

古典暗号において、ヒル暗号は線形代数に基づくポリグラフ置換暗号である。 1929年にレスター・S・ヒルによって発明されたこの暗号は、一度に3つ以上の記号を操作することが（かろうじて）可能であった最初のポリグラフ暗号であった。

以下の説明では、行列に関する基本的な知識を前提としています。

各文字は 26 を法とする数字で表されます。これは暗号の本質的な特徴ではありませんが、この単純な方式はよく使用されます。

メッセージを暗号化するには、n文字の各ブロック ( n成分のベクトルとして考えられます) に、法26 に対して可逆な n × n 行列を掛けます。メッセージを復号化するには、各ブロックに、暗号化に使用された行列の逆を掛けます。

暗号化に使用される行列は暗号鍵であり、可逆なn × n行列のセット ( 26を法として) からランダムに選択する必要があります。もちろん、暗号は任意の文字数のアルファベットに適応できます。すべての演算は、 26 を法としてではなく、文字数を法として実行する必要があります。

メッセージ「ACT」と以下のキー（または文字では GYB / NQK / URP）について考えてみましょう。

${\displaystyle {\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}}$

「A」は 0、「C」は 2、「T」は 19 なので、メッセージはベクトルになります。

${\displaystyle {\begin{pmatrix}0\\2\\19\end{pmatrix}}}$

したがって、暗号化されたベクトルは次のように表されます。

${\displaystyle {\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}{\begin{pmatrix}0\\2\\19\end{pmatrix}}={\begin{pmatrix}67\\222\\319\end{pmatrix}}\equiv {\begin{pmatrix}15\\14\\7\end{pmatrix}}{\pmod {26}}}$

これは「POH」という暗号文に相当します。ここで、メッセージが「CAT」、つまり次のようになると仮定します。

${\displaystyle {\begin{pmatrix}2\\0\\19\end{pmatrix}}}$

今回、暗号化されたベクトルは次のように与えられます。

${\displaystyle {\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}{\begin{pmatrix}2\\0\\19\end{pmatrix}}={\begin{pmatrix}31\\216\\325\end{pmatrix}}\equiv {\begin{pmatrix}5\\8\\13\end{pmatrix}}{\pmod {26}}}$

これは「FIN」という暗号文に相当します。すべての文字が変更されています。ヒル暗号はシャノンの拡散を実現しており、n次元のヒル暗号は一度にn個のシンボルに完全に拡散することができます。

復号化するには、暗号文をベクトルに戻し、キー行列の逆行列(文字では IFK / VIV / VMI) を掛けるだけです。26を法として、前の例で使用した行列の逆行列は次のようになります。

${\displaystyle {\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}^{-1}{\pmod {26}}\equiv {\begin{pmatrix}8&5&10\\21&8&21\\21&12&8\end{pmatrix}}}$

前述の「POH」の暗号文の例を取ると、次のようになります。

${\displaystyle {\begin{pmatrix}8&5&10\\21&8&21\\21&12&8\end{pmatrix}}{\begin{pmatrix}15\\14\\7\end{pmatrix}}={\begin{pmatrix}260\\574\\539\end{pmatrix}}\equiv {\begin{pmatrix}0\\2\\19\end{pmatrix}}{\pmod {26}}}$

予想通り、「ACT」に戻ります。

暗号化マトリックスの選択には 1 つの複雑な点があります。

1. すべての行列に逆行列があるわけではありません。行列の行列式が n を法として可逆な場合のみ、その行列には逆行列があります。ここで、n はモジュラー基数です。

したがって、上記のように 26 を法として計算する場合、行列式は 0 以外でなければならず、2 または 13 で割り切れない必要があります。行列式が 0 の場合、またはモジュラー ベースと共通の因数がある場合、その行列は Hill 暗号では使用できず、別の行列を選択する必要があります (そうしないと、復号化できなくなります)。幸い、Hill 暗号で使用される条件を満たす行列はかなり一般的です。

キーマトリックスの例:

${\displaystyle {\begin{vmatrix}6&24&1\\13&16&10\\20&17&15\end{vmatrix}}=6(16\cdot 15-10\cdot 17)-24(13\cdot 15-10\cdot 20)+1(13\cdot 17-16\cdot 20)=441\equiv 25{\pmod {26}}}$

したがって、26 を法として、行列式は 25 です。および であるため、25 には 26 との共通因数が存在せず、この行列は Hill 暗号に使用できます。 ${\displaystyle 25=5^{2}}$${\displaystyle 26=2\times 13}$

行列式が係数と共通因数を持つリスクは、係数を素数にすることで排除できます。その結果、ヒル暗号の有用な変種では、3 つの追加記号 (スペース、ピリオド、疑問符など) を追加して係数を 29 に増やします。

させて

${\displaystyle K={\begin{pmatrix}3&3\\2&5\end{pmatrix}}}$

をキーとし、平文メッセージが「HELP」であると仮定します。この平文は2つのペアで表されます

${\displaystyle HELP\to {\begin{pmatrix}H\\E\end{pmatrix}},{\begin{pmatrix}L\\P\end{pmatrix}}\to {\begin{pmatrix}7\\4\end{pmatrix}},{\begin{pmatrix}11\\15\end{pmatrix}}}$

次に計算する

${\displaystyle {\begin{pmatrix}3&3\\2&5\end{pmatrix}}{\begin{pmatrix}7\\4\end{pmatrix}}\equiv {\begin{pmatrix}7\\8\end{pmatrix}}{\pmod {26}},}$そして

${\displaystyle {\begin{pmatrix}3&3\\2&5\end{pmatrix}}{\begin{pmatrix}11\\15\end{pmatrix}}\equiv {\begin{pmatrix}0\\19\end{pmatrix}}{\pmod {26}}}$

次のように暗号化を続行します。

${\displaystyle {\begin{pmatrix}7\\8\end{pmatrix}},{\begin{pmatrix}0\\19\end{pmatrix}}\to {\begin{pmatrix}H\\I\end{pmatrix}},{\begin{pmatrix}A\\T\end{pmatrix}}}$

行列Kは逆行列であるため、となる。Kの逆行列は、次の式で計算できる。${\displaystyle K^{-1}}$${\displaystyle KK^{-1}=K^{-1}K=I_{2}}$ ${\displaystyle {\begin{pmatrix}a&b\\c&d\end{pmatrix}}^{-1}=(ad-bc)^{-1}{\begin{pmatrix}d&-b\\-c&a\end{pmatrix}}}$

この式は、モジュラー逆数を使用して計算する場合、モジュラー還元後も成立します。したがって、この場合は、次のように計算します。 ${\displaystyle (ad-bc)^{-1}}$

${\displaystyle K^{-1}\equiv 9^{-1}{\begin{pmatrix}5&23\\24&3\end{pmatrix}}\equiv 3{\begin{pmatrix}5&23\\24&3\end{pmatrix}}\equiv {\begin{pmatrix}15&17\\20&9\end{pmatrix}}{\pmod {26}}}$

${\displaystyle HIAT\to {\begin{pmatrix}H\\I\end{pmatrix}},{\begin{pmatrix}A\\T\end{pmatrix}}\to {\begin{pmatrix}7\\8\end{pmatrix}},{\begin{pmatrix}0\\19\end{pmatrix}}}$

次に計算する

${\displaystyle {\begin{pmatrix}15&17\\20&9\end{pmatrix}}{\begin{pmatrix}7\\8\end{pmatrix}}={\begin{pmatrix}241\\212\end{pmatrix}}\equiv {\begin{pmatrix}7\\4\end{pmatrix}}{\pmod {26}},}$そして

${\displaystyle {\begin{pmatrix}15&17\\20&9\end{pmatrix}}{\begin{pmatrix}0\\19\end{pmatrix}}={\begin{pmatrix}323\\171\end{pmatrix}}\equiv {\begin{pmatrix}11\\15\end{pmatrix}}{\pmod {26}}}$

したがって、

${\displaystyle {\begin{pmatrix}7\\4\end{pmatrix}},{\begin{pmatrix}11\\15\end{pmatrix}}\to {\begin{pmatrix}H\\E\end{pmatrix}},{\begin{pmatrix}L\\P\end{pmatrix}}\to HELP}$。

基本的なヒル暗号は完全に線形であるため、既知平文​​攻撃に対して脆弱です。平文/暗号文の文字ペアを傍受した敵は、（通常は）簡単に解読できる線形システムを構築できます。このシステムが不確定な場合は、平文/暗号文のペアをさらにいくつか追加するだけで済みます。標準的な線形代数アルゴリズムでこの解を計算するのに、ほとんど時間がかかりません。 ${\displaystyle n^{2}}$

行列乗算だけでは安全な暗号にはなりませんが、他の非線形演算と組み合わせると、行列乗算によって拡散が可能になるため、依然として有用なステップとなります。たとえば、適切に選択された行列により、行列乗算前の小さな差が行列乗算後に大きな差になることが保証されます。実際、一部の最新の暗号では、拡散を提供するために行列乗算ステップが使用されています。たとえば、AESの MixColumns ステップは行列乗算です。Twofishの関数gは、非線形 S ボックスと慎重に選択された行列乗算 (MDS) の組み合わせです。

キー空間は、すべての可能なキーの集合です。キー空間のサイズは、可能なキーの数です。有効なキー サイズ(ビット数) は、キー空間のサイズの 2 進対数です。

n × n次元の行列が存在する。したがって、またはおよそ は、n × n行列を使用するヒル暗号の鍵サイズの上限である。これは上限にすぎない。すべての行列が逆行列で鍵として使用できるわけではないからである。逆行列の数は、中国剰余定理によって計算できる。すなわち、行列が 26 を法として逆行列である場合、かつその行列が 2 を法として逆行列である場合、および 13 を法として逆行列である場合に限る。2 を法として逆行列のn × n行列の数は、一般線型群GL(n, Z ₂ )の位数に等しい。 ${\displaystyle 26^{n^{2}}}$${\displaystyle \log _{2}(26^{n^{2}})}$${\displaystyle 4.7n^{2}}$

${\displaystyle 2^{n^{2}}(1-1/2)(1-1/2^{2})\cdots (1-1/2^{n}).}$

同様に、13を法とする逆行列の数（つまりGL(n, Z ₁₃ )の次数）は

${\displaystyle 13^{n^{2}}(1-1/13)(1-1/13^{2})\cdots (1-1/13^{n}).}$

26を法とする可逆行列の数は、これら2つの数の積である。したがって、

${\displaystyle 26^{n^{2}}(1-1/2)(1-1/2^{2})\cdots (1-1/2^{n})(1-1/13)(1-1/13^{2})\cdots (1-1/13^{n}).}$

さらに、鍵行列にゼロが多すぎると拡散が減少するため、避けた方が賢明と思われます。最終的な効果は、基本的なヒル暗号の有効な鍵空間が約 になることです。5 × 5 ヒル暗号の場合、これは約 114 ビットです。もちろん、鍵検索は最も効率的な既知の攻撃ではありません。 ${\displaystyle 4.64n^{2}-1.7}$

2 つの記号を同時に処理する場合、ヒル暗号はプレイフェア暗号や二分暗号に比べて特に優れているわけではなく、実際はどちらよりも弱く、紙と鉛筆で処理するには少し手間がかかります。次元が大きくなるにつれて、暗号は人間が手作業で処理することが急速に不可能になります。

6次元のヒル暗号が機械的に実装されました。ヒルとパートナーは、ギアとチェーンのシステムを使用して6×6行列乗算をモジュロ26で実行するこの装置の特許（米国特許1,845,947）を取得しました。

残念ながら、ギアリングの配置 (およびキー) はどのマシンでも固定されていたため、セキュリティのために 3 重の暗号化が推奨されました。つまり、秘密の非線形ステップ、マシンからの広い拡散ステップ、そして 3 つ目の秘密の非線形ステップです (ずっと後のEven-Mansour 暗号でも、キーなしの拡散中間ステップが使用されています)。このような組み合わせは 1929 年当時としては非常に強力であり、ヒルが中間者攻撃の概念だけでなく、混乱と拡散の概念も理解していたことを示しています。残念ながら、彼のマシンは売れませんでした。^[要出典]

その他の実用的な「鉛筆と紙」によるポリグラフ暗号には次のものがあります。

• プレイフェア暗号
• 二分暗号
• 三分割暗号

• レスター・S・ヒル、「代数アルファベットの暗号化」、アメリカ数学月刊誌第36巻、1929年6月～7月、306～312ページ。(PDF)
• レスター・S・ヒル、「暗号化の特定の線形変換装置について」、アメリカ数学月刊誌第38巻、1931年、135～154頁。
• Jeffrey Overbey、William Traves、Jerzy Wojdylo、「Hill Cipher のキー空間について」、Cryptologia、Vol.29、No.1、2005 年 1 月、pp59–72。(CiteSeerX) (PDF)

• 「ヒル暗号ウェブアプリ」はヒル暗号を実装し、関連する行列を表示します。
• 「ヒル暗号の説明」はヒル暗号の背後にある線形代数を説明する。
• 「ヒルの暗号計算機」はウェブページでヒル暗号の概要を説明します。