你如何计算原始位置没有字母的英文单字母密码的密钥 space？

Question

我刚刚开始学习密码学，了解到单字母密码的密钥空间是 26x25x24...x3x2x1 排列的结果。但这考虑了密码字母可以与原始明文字母匹配的密钥。如果我不想让任何字母代表原始字母，我该如何计算新的键空间？也许我很天真，但它是从 25 而不是 26 开始排列那么简单，还是需要其他一些方法来计算可能的键总数？我试图在 Google 和 Whosebug 上找到答案，但找不到。如果这是一个愚蠢的问题，我深表歉意。

Answer 1

这叫做 derangement:

In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position. In other words, a derangement is a permutation that has no fixed points.

操作写成 !n 并由等式 !n=(n-1)(!(n-1)+!(n-2)) 给出，其中 !0 是 1，!1 是 0。例如，您可以写按照 Ruby 代码进行操作：

#!/usr/bin/env ruby

def derangements(n)
  case n
  when 0
    1
  when 1
    0
  else
    (n - 1) * (derangements(n - 1) + derangements(n - 2))
  end
end

puts derangements(ARGV[0].to_i)

运行这个带有 26 的代码给我们 148 362 637 348 470 135 821 287 825。这样的密码有略多于 86 位的熵，但很快就会落入字母频率密码分析。

你如何计算原始位置没有字母的英文单字母密码的密钥 space？

How do you calculate the key space of an English monoalphabetic cipher where no letters are in the original position?

cryptography