ヒル暗号は選択平文攻撃に対してなぜ脆弱？仕組みと解読方法を徹底解説

ヒル暗号とは

ヒル暗号（Hill Cipher）は、レスター・S・ヒル（Lester S. Hill）によって考案された、複数文字を単位とする多表式暗号です。平文を暗号文へ変換する暗号化、そして暗号文を平文へ戻す復号の段階において、行列の概念と線形合同法の考え方を組み合わせた符号化システムとして知られています。

ヒル暗号では、暗号化・復号に行列の掛け算を利用するため、平文中の同一の文字が必ずしも同一の暗号文字に置き換えられません。また、多表式暗号であるヒル暗号は、対象テキストが一定サイズのブロックに分割されて処理されるという点で、ブロック暗号にも分類されます。

一つのブロック内の各文字は、暗号化・復号の手順の中で互いに影響を与え合うため、同じ文字が同じ文字へ対応付けられることはありません。

既知平文攻撃への弱点

ヒル暗号は古典暗号アルゴリズムの一つであり、暗号文ファイルだけを頼りに解読する場合、暗号解読者にとっては非常に困難な対象です。しかし、暗号文ファイルに加えて平文ファイルの一部でも入手できれば、驚くほど簡単に解読できてしまいます。この暗号解読手法は「既知平文攻撃（known-plaintext attack）」と呼ばれています。

ヒル暗号の基礎：行列演算

ヒル暗号の基盤となるのは、行列の乗算と逆行列の計算です。その核心は n×n の行列にあり、n はブロックサイズを表します。

鍵となる行列 K は可逆行列、すなわち逆行列 K^-1 を持つ行列でなければなりません。復号に使用される鍵が K^-1 行列であるため、鍵には必ず逆行列が存在する必要があります。

ヒル暗号の処理ステップ

• 平文を同じサイズのブロックに分割します。
• ブロックを1つずつ暗号化します。このとき、ブロック内の各文字が他の文字の暗号化に寄与します。
• 鍵は m×m の正方行列で、m はブロックサイズを定義します。これを鍵行列 K と呼びます。

平文ブロックに m 個の文字 P₁, P₂, …, P_m があるとき、対応する暗号文ブロックの文字 C₁, C₂, …, C_m は次の式で表されます。

C₁ = P₁K₁₁ + P₂K₁₂ + P₃K₁₃ (mod 26)
C₂ = P₁K₂₁ + P₂K₂₂ + P₃K₂₃ (mod 26)
C₃ = P₁K₃₁ + P₂K₃₂ + P₃K₃₃ (mod 26)

これらの式は、列ベクトルの形で次のようにまとめられます。

(C₁, C₂, C₃)^T = K × (P₁, P₂, P₃)^T (mod 26)

一般化すると、ヒル暗号の暗号化・復号は以下の式で定義できます。

C = KP (mod 26)
P = K^-1C (mod 26)

既知平文攻撃・選択平文攻撃による解読

ヒル暗号は既知平文攻撃によって容易に破られてしまいます。長さ m の平文・暗号文ペアを m 組入手できると仮定します。

C_i = KP_i （1 ≤ i ≤ m）

未知の鍵行列 K は、次のように計算できます。

K = C_i P_i^-1

鍵が一度求まってしまえば、暗号全体は簡単に解読されてしまいます。さらに「選択平文攻撃」では、攻撃者が任意の平文を選んでその暗号化結果を取得できるため、必要な平文・暗号文ペアを意図的に収集することが可能です。その結果、鍵行列 K の特定はいっそう容易になり、ヒル暗号は実用性の高い現代暗号としては不十分であることが分かります。