1

26記号の文字セットを暗号化する場合、ヒル暗号で使用されるキーは35文字セットの暗号化とは異なりますか？

4

1 に答える 1

2

考え方は変わりませんが、計算方法が若干異なります。Hill Cipher に関する前回の質問で、実際に CBC モードを実装したいとおっしゃっていたのを覚えています。mod 26 を計算する代わりに、代わりに mod 256 を計算することを選択することをお勧めします。この方法では、キーのバイト表現、IV、および結果の暗号文への簡単なマッピングを行うことができます。さらに、スペースやその他の句読点を使用できるようになり、メッセージに UTF-8 などのエンコーディングを使用することもできます。

キーの考え方は mod 256 と変わりませんが、計算方法が少し異なります。Z^n/26 で可逆な anxn 行列を選択する代わりに、Z^n/256 で可逆な行列を選択する必要があります。ウィキペディアの記事で概説されているように、3 x 3 行列を選択するとします。これはまだ十分に簡単に可逆であり、選択したキー (行列) が 256 を法とするゼロ以外の行列式をチェックすることによって可逆であるかどうかを確認できます。キーのバイト配列表現は、単純に長さ 9 の配列になり、行列から配列への単純なマッピングが行われます: 要素 (1,2) (ゼロベースのインデックスを想定) は、配列の 5 番目の要素 ( 1*3 + 2) など

次に、メッセージを 3 バイトのブロックに分割し (最後のブロックが 3 バイトに整列されていない場合は、何らかの形式のパディングを使用します)、キー マトリックスで乗算されるベクトルを表すと、再び 3 バイトの出力ブロックになります。

ご覧のとおり、mod 256 表現を使用するのは非常に巧妙です。この方法では、AES などの最先端のブロック暗号にも使用される同一のインターフェイスで暗号化/復号化を使用できるためです。つまり、メッセージを暗号化します。適切なサイズのチャンク/ブロックに分割されたメッセージに、バイト配列キーに基づく暗号化/復号化関数を適用することによって。

Z^n/256 での 3x3 暗号化と復号化行列の生成

暗号化行列を生成するには、ゼロ以外の行列式 (mod 256) と剰余逆要素 mod 256 (拡張ユークリッド アルゴリズムを使用して計算します) を持つ行列が見つかるまで、Z256 からの要素を持つランダムな 3x3 行列を作成する必要があります。次に、逆行列の計算は、すべての計算を Z256 で行う必要があるという事実を除いて、通常の 3x3 行列の逆行列を計算するのと同じ規則に従います。hereにあるように、3x3 逆行列を計算するための閉じた式があります。Z^n/256 の逆数を得るために、Z256 の剰余演算を使用してまったく同じことを計算できます。

キー マトリックスとその逆を生成する Ruby コードを次に示します。

require 'matrix'

class Integer
  def modinv(modulus)
    a, b = modulus, self
    q, r = a / b, a % b
    t0, t1 = 0, 1

    while r > 0
      t0, t1 = t1, (t0 - q * t1) % modulus
      a, b = b, r
      q, r = a / b, a % b
    end

    raise RuntimeError.new("#{self} has no inverse modulo #{modulus}") unless b == 1
    t1
  end
end

while true
  m = Matrix.build(3) { rand(0..256) }
  mod_det = m.determinant % 256
  next if mod_det == 0
  begin
    det_inv = mod_det.modinv(256)
    break
  rescue RuntimeError => e
    next
  end
end

inv = Matrix[
  [ (m[2,2]*m[1,1] - m[2,1]*m[1,2]), -(m[2,2]*m[0,1] - m[2,1]*m[0,2]),  (m[1,2]*m[0,1] - m[1,1]*m[0,2])],
  [-(m[2,2]*m[1,0] - m[2,0]*m[1,2]),  (m[2,2]*m[0,0] - m[2,0]*m[0,2]), -(m[1,2]*m[0,0] - m[1,0]*m[0,2])],
  [ (m[2,1]*m[1,0] - m[2,0]*m[1,1]), -(m[2,1]*m[0,0] - m[2,0]*m[0,1]),  (m[1,1]*m[0,0] - m[1,0]*m[0,1])]
].map { |e| e * det_inv % 256 }

p m #=> encryption matrix
p inv #=> decryption matrix
identity = (inv * m).map { |e| e % 256 }
p identity #=> living proof that m * inv is the identity matrix

出力例:

m   = Matrix[[167, 8, 48], [54, 107, 25], [170, 184, 107]]
inv = Matrix[[119, 152, 136], [184, 235, 231], [174, 120, 59]]
于 2012-05-22T21:42:04.403 に答える