algorithm - 如果要加密的字母数发生变化，Hill Cipher key 是否会有所不同？

Question

如果我想加密一个由 26 个符号组成的字母组，山密码中使用的 key 与加密一个 35 个字母组的 key 是否不同？

Answer 1

想法没有改变，只是计算略有不同。我记得你上一个关于 Hill Cipher 的问题，你实际上想为它实现 CBC 模式。我建议您选择计算 mod 256 而不是计算 mod 26 - 这样您就可以轻松地来回映射到 key 的字节表示、IV 和生成的密文。此外，它还允许您使用空格和其他标点符号，您甚至可以为您的消息使用 UTF-8 或类似编码。

key 的想法不会改变 mod 256，但计算方式会有所不同。您不必选择在 Z^n/26 中可逆的 n x n 矩阵，而必须选择在 Z^n/256 中可逆的矩阵。假设您选择了一个 3 x 3 矩阵，它仍然很容易可逆，那么您可以通过检查非零行列式模 256 来检查您选择的 key (矩阵)是否可逆，如 Wikipedia article 中所述。 .然后，您的 key 的字节数组表示形式将只是一个长度为 9 的数组，从矩阵到数组的直接映射:元素 (1,2)(假定从零开始的索引)将是数组的第五个元素( 1*3 + 2) 等

然后，您可以将消息拆分为 3 字节 block (如果最后一个 block 未与三个字节对齐，则使用某种形式的填充)，表示要与 key 矩阵相乘的向量，再次产生 3 字节输出 block 。

如您所见，使用 mod 256 表示非常简洁，因为这种方式的加密/解密可以与相同的接口(interface)一起使用，该接口(interface)也可以用于 AES 等最先进的 block 密码，即您通过将基于字节数组 key 的加密/解密函数应用于分成适当大小的 block / block 的消息来加密消息。

在 Z^n/256 中生成 3x3 加密和解密矩阵

生成加密矩阵只需要用 Z256 中的元素创建一个随机 3x3 矩阵，直到找到一个具有非零行列式 (mod 256) 和模逆元素 mod 256(我们将使用扩展欧几里德算法计算) ).然后，计算逆矩阵遵循与计算常规 3x3 矩阵逆矩阵相同的规则，除了所有计算都需要在 Z256 中进行。有一个用于计算 3x3 矩阵逆的封闭公式，如发现的那样 here .我们可以使用 Z256 中的模运算来计算完全相同的东西，以获得 Z^n/256 中的逆。

下面是一些生成 key 矩阵及其逆矩阵的 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]]