加密

第15周挑战赛的第二个任务是实现 Vigenère 密码的编码器和解码器。但这比看起来要复杂一些，因为以 Blaise de Vigenère 命名的密码其实并不是他发明的，而 Vigenère 真正发明的密码也不是以他的名字命名的。

所以我们应该实现维根埃密码…还是维根埃的密码？为什么不两者兼而有之呢!

Vigenère 密码是由 Giovan Battista Bellaso 在1553年设计的，然后在大约三百年后被误认为是 Vigenère 发明的。它使用了一个 tabula rēcta 来将信息文本翻译成密码文本，然后再翻译回来。

给定一个用户提供的密钥（如 “BELLASO”），我们通过匹配密钥和信息中各自的字母来加密信息（如 “VIGENEREDIDNOTINVENTTHIS”），然后用它们作为两个索引，在 tabula rēcta 的相应列和行中查找相应的密文字符。而如果密钥比信息短，我们只需回收密钥，次数不限。

比如说:

   Key:  B E L L A S O B E L L A S O B E L L A S O B E L L A...
  Text:  V I G E N E R E D I D N O T I N V E N T T H I S
 Table:  ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
Cipher:  W M R P N W F F H T O N G H J R G P N L H I M D

换句话说，tabula rēcta 的每一列都是一个独立的凯撒密码（或 ROT-N 转录），钥匙的每一个连续字母都会选择对信息中的相应字母进行哪种替换。

这种方法早在15世纪就被广泛地认为是"不可能的"，尽管查尔斯-巴贝奇在1854年"重新发现 “后的两周内就打破了这种方法的范例，而弗里德里希-卡西斯基则在不到十年后发表了对这种方法的可靠的总攻击。尽管如此，Vigenère 密码还是提供了合理的安全性，只要所选的密钥足够长，足够不寻常，就可以防止简单的字典攻击。具有讽刺意味的是，正如我们在后面看到的，Vigenère 的实际密码优雅地解决了 Vigenère 密码的这两个问题。

为了实现 Vigenère 密码，我们首先需要建立一个 tabula rēcta。在 Raku 中，这只是:

constant @alphabet = ['A'...'Z'];

constant @𝑡𝑎𝑏𝑢𝑙𝑎-𝑟𝑒̄𝑐𝑡𝑎
    = @alphabet, *.rotate ... *.head eq @alphabet.tail;

该表只是一个数组序列，其中第一个数组是原始字母，其余数组的构造是将前一个数组循环旋转一个字符（*.rotate）。所以 ['A'...'Z'] 后面是 ['B'...'Z', 'A']，后面依次是 ['C'...'Z', 'A'...'B']。循环往复，直到我们最终生成一个旋转，其中第一个字母(*.head)是原始字母表(@alphabet.tail)的最后一个字母。换句话说，我们生成每一次旋转，直到达到 ['Z', 'A'...'Y']。

请注意，我们可以简单地通过替换 @alphabet 的内容来改变我们正在使用的字母表。例如，如果我们希望能够用 “I❤️Bellaso” 这样的键来编码 “Vigenère did NOT invent this!” 这样的信息，那么我们就会像这样重新配置我们的字母表:

# Valid message characters are all printable Latin-1 + lurve...
constant @alphabet = [' '...'ÿ', '❤️'];

Raku 是一种现代语言，在数据和源代码中都内置了对完整 Unicode 字符集的支持，所以完全可以使用带有表情符号的字符串，比如 “I❤️Bellaso”，或者声明一个变量，比如 @𝑡𝑎𝑏𝑢𝑙𝑎-𝑟𝑒̄𝑐𝑡𝑎，它的名字中包含了那些奇怪的 Unicode 数学斜体字符和 ēvēn ā cōmbīnīng mārk.

使用斜体的 Unicode 变量名似乎是一件疯狂的事情，但这也意味着我们不再受制于英语帝国主义。而不是被迫命名一个关键变量 $cipher-text，我们可以用我们通常使用的语言自然地命名它：$texte-chiffré 或 $النص-المشفر 或 $加密文字 或 $Κρυπτογραφημένο-κείμενο 甚至 $ĉifrita-teksto。 Raku 的目标是为世界上100%的程序员赋能。

我们可以直接使用我们的 @𝑡𝑎𝑏𝑢𝑙𝑎-𝑟𝑒̄𝑐𝑡𝑎 数组来查找给定文本/密钥字符对的密文字符，但这样做有点不方便。我们需要将每个字符转换回它的整数 ASCII 码(通过内置的 .ord 方法)，然后将其归一化为 0..25 范围的表索引，就像这样:

my $key-index   = $key-char.ord  - 'A'.ord;
my $text-index  = $text-char.ord - 'A'.ord;

my $cipher-char = @𝑡𝑎𝑏𝑢𝑙𝑎-𝑟𝑒̄𝑐𝑡𝑎[$key-index][$text-index];

而如果我们以后改用非连续的字母表，比如包括 ‘❤️’ 在内的字母表，那么这个代码就会变得非常复杂。

如果二维查询表是一个二维字典（Raku 术语：哈希），并且可以直接以我们字母表中的实际字符为索引，而不是以零开始的整数为索引，那就简单多了。

而这很容易安排：

constant %encoder
    = @𝑡𝑎𝑏𝑢𝑙𝑎-𝑟𝑒̄𝑐𝑡𝑎.map:
        { @^cipher.head => hash @alphabet Z=> @^cipher }

在这里，对于 tabula rēcta 的每一个密文行（@^cipher），我们建立一个哈希条目，其键是旋转字母表的第一个字母（@^cipher.head），其值是一个嵌套的哈希，将字母表的每个字母映射到密文行中的相应字母（@alphabet Z=> @^cipher）。

Z=> 运算符将其两个列表参数中的对应元素压缩在一起，将每两个参数传递给 => 对构造函数，因此映射操作产生的哈希条目如下：

# Key     Text->Cipher, etc.

'M' => %('A'=>'M', 'B'=>'N', 'C'=>'O' ... 'Y'=>'K', 'Z'=>'L')

所以现在当我们要查询相应的密文字符时，顶层哈希索引选择关键列，二级哈希索引选择明文字符的行。就像这样：

my $ciphertext-char = %encoder{$key-char}{$plaintext-char};

更好的是，使用这种基于哈希的方法来构建二维解码字典也同样简单，只需将字母字符到密码字符的嵌套映射反转即可。

constant %decoder
    = @𝑡𝑎𝑏𝑢𝑙𝑎-𝑟𝑒̄𝑐𝑡𝑎.map: 
        { @^cipher.head => hash @^cipher Z=> @alphabet }

之后，我们可以像这样解码一个加密字符：

my $plaintext-char = %encoder{$key-char}{$ciphertext-char};

一旦我们有了这两个二维字典，Vigenère 密码就很容易实现了：

sub Vigenère (Str :$text!, Str :$key!, Bool :$decode --> Str) {

    # Extract lists of table indices from the two strings...
    my @textchars =  $text.comb;
    my @keychars  = |$key.comb xx ∞;

    # Chose our trancoder...
    my %recoder = $decode ?? %decoder !! %encoder;

    # Pair up indices, transcode, and concatenate the results...
    (@keychars Z=> @textchars)
        .map({ %recoder{.key}{.value} // 0.chr })
        .join;
}

该子程序需要两个命名的字符串参数：一个文本（明文或加密）和加密/解密密钥。两个参数名称后面的感叹号告诉 Raku 编译器这两个参数是必需的。还有一个可选的命名为布尔参数（后面没有感叹号），表示我们是否要解码。签名末尾的长箭头(--> Str)指定子程序返回一个字符串。

在子程序中，我们首先将文本字符串和密钥拆分为单个字符的列表（$text.comb 和 $key.comb）。我们还需要重复键字符序列，使键至少与文本字符串一样长。我们可以精确地计算出需要重复多少次，但只需让键无限次地重复(|$key.comb xx ∞)就容易多了。开头的竖条是用来压平键字符列表的。否则，我们最终得到的将不是一个重复的键字符列表，而是一个重复的键字符列表。

然后，我们根据是否要解码，选择我们需要的两个编码字典中的哪一个。在 Raku 中，三元选择操作符是 ?? true-value !! false-value, 而不是 test ? true-value : false-value。

一旦我们把一切都设置好了，实际的编码或解码就很琐碎了:

(@keychars Z=> @textchars)
    .map({ %recoder{.key}{.value} // 0.chr })
    .join;

我们首先将文本中的每个字符与重复键中的下一个连续字符进行匹配，再次在两个列表之间使用 zip-into-a-list-of-pairs 操作符(Z=>)。(@keychars Z=> @textchars)。

然后，我们将该对列表映射到加密/解密字符列表，通过在查找表中查找每个密钥字符（.key）和每个对应的文本字符（.value）。如果对字符组合没有可用的转换，我们只用一个空字符（0.chr）作为占位符。这确保了指定字母表之外的任何字符都能干净利落地从加密字符串中映射出来，而不会影响其未来的解密。

一旦所有的字符都被转换，列表就会被简单地连接起来（.join）以产生最终的字符串。

这就是 Vigenère 密码。

那么，Vigenère 的加密技术又是怎样的呢？

上面讨论的加密技术作为密码有一些严重的弱点。1863年，Friedrich Kasiski 观察到，为了生成一个足够长的密钥而重复使用密钥串，这意味着一个单一的加密信息有时可能会重复使用 tabula rēcta 的相同列来编码后来在原始信息中重新出现的相同明文字符序列。

因此，如果我们截取一个加密字符串，如。

LLGMMZWRGIIVATJVVBKRVMMZWRGIILLEDCIVATJVV

…那么就比较容易发现，明文电文中重复的两个地方，显然是用两个相同的关键字符的独立副本进行加密的。

LLGMMZWRGIIVATJVVBKRVMMZWRGIILLEDCIVATJVV

LLGMMZWRGIIVATJVVBKRVMMZWRGIILLEDCIVATJVV

第一个明显的单词重复发生在18个字符之间，所以如果两个单词使用相同的密钥字符进行编码，密钥必须在18个字符之后重复。这意味着密钥长度必须是18或18的某个整数因子（即9、6、3、2或1）。第二个重复发生在24个字符之间，所以键长必须同时是24的某个系数（即12、8、6、4、3、2或1）。由于两种情况下都是同一个键，因此键长必须是18和24的共同因子：6、3、2或1。

考虑到这些可能性，密钥很可能是6个字符长，因为从心理学上讲，其他长度都太短了。在这种情况下，我们也许可以简单地通过使用所有17706个英语六字母单词尝试字典攻击来解码信息。

要做到这一点，我们首先要知道最有可能的密钥长度是多少。

sub large-factors ($n) { set (4..$n).grep($n %% *) }

my $gap
    = any keys [∩] map {large-factors(.<gap>.chars)},
      $encoded ~~ m:ex/$<gap>=[ $<seq>=[. ** 3..*] .+] $<seq>/;

在这里，我们详尽地将(m:ex)编码文本与定位任何三个或更多连续字符序列的 regex 进行匹配($<seq>=[. ** 3..* ])，然后是一个空隙(.+)，然后再是之前的字符序列($<seq>)。然后我们确定每个间隙的长度(.<gap>.chars)，建立一个每个长度的显著因子集(map {large-factors(...)})，并取这些集合的交集([∩])来寻找共同因子。最后，我们将得到的公因子集用任意结转换为一个值。随后，我们就可以将字长与该结点进行匹配，选择适当长度的潜在关键词。

一旦我们知道了解密密钥的长度，我们就可以加载一个合适的字典，并筛选出合适的候选密钥。

my @candidate-keys
    = '/usr/share/dict/words'.IO.lines.grep(*.chars==$gap)».uc;

my @common-words
    = '/usr/share/dict/common'.IO.lines.grep(*.chars > 2)».uc;

我们只保留那些长度合适的词：.grep(*.chars==$gap)。我们还加载了第二个较小的常用词库，我们将用它来检测可信的解密。

然后，我们用每一个可能的长度合适的密钥对密文进行解密，并打印出任何看起来包含合理数量的英文单词的解密。

    # Request text to be deciphered...
    my $encoded = prompt "Ciphertext: ";

    # Try each potential key...
    for @candidate-keys -> $key {

        # Decrypt with that key...
        my $candidate = Vigenère( :text($encoded), :$key, :decode);

        # Count any real words found in the decryption...
        my $found = 0;
        for @common-words -> $word {

            # Report any plausible decryptions found...
            if $candidate.contains($word) && ++$found > 3 {
                say "$key --> $candidate";
                last;
            }
        }
    }

在短短不到20秒的时间里，产生了:

Ciphertext: LLGMMZWRGIIVATJVVBKRVMMZWRGIILLEDCIVATJVV

HYDROA --> ENDVYZPTDRUVTVGEHBDTSVYZPTDRULEGALUVTVGEH
HYDROA --> ENDVYZPTDRUVTVGEHBDTSVYZPTDRULEGALUVTVGEH
HOGGIE --> EXAGEVPDACARTFDPNXDDPGEVPDACAHEQXWARTFDPN
SECRET --> THEVIGENERECIPHERISNTVIGENERESTABLECIPHER
STRICH --> TSPEKSEYPAGOIASNTUSYEEKSEYPAGETLMUGOIASNT
WAGGIE --> PLAGEVARACARETDPNXORPGEVARACAHPEXWARETDPN
WEDGIE --> PHDGEVANDCAREPGPNXONSGEVANDCAHPAAWAREPGPN

这里的根本问题（和许多密码技术一样）是密钥太短。我们可以坚持要求用户提供一个至少和实际信息一样长的密钥：

sub Vigenère (
    Str  :$text!,
    Str  :$key! where { $key.chars >= $text.chars },
    Bool :$decode
    --> Str)
    {...}

然而，在1586年，Blaise de Vigenère 找到了一个简单得多的解决方案：无论他们提供什么密钥，与其用额外的副本来扩展它本身，不如用信息的"随机"字符来扩展密钥。

也就是说，与其:

   Key: SECRETSECRETSECRETSECRETSECRETSECRETSECRET...
  Text: THEVIGENERECIPHERISNTVIGENERESTABLECIPHER
 Table: ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
Cipher: LLGMMZWRGIIVATJVVBKRVMMZWRGIILLEDCIVATJVV

…我们不如使用:

   Key: SECRETTHEVIGENERECIPHERISNTVIGENERESTABLECIPHER
  Text: THEVIGENERECIPHERISNTVIGENERESTABLECIPHER
 Table: ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
Cipher: LLGMMZXUIMMIMCLVVKACAZZOWAXMMYXNFCIUBPIPV

这样就不会在密文中产生明显的重复，因为明文中的重复词不再是用一个短密钥的重复来加密。这种方法被称为自动密钥密码，因为完整的密钥是由消息本身为我们自动生成的。

假设我们想扩展我们之前的 Vigenère 子程序，让它也提供自动密钥加密。我们可能只是在签名中添加另一个参数，然后根据实际提供的参数选择合适的行为。

sub Vigenère (
    Str :$text!,
    Str :$key,
    Str :$autokey,
    Bool :$decode
    --> Str
) {
    if    $autokey {...}
    elsif $key     {...}
    else           { fail 'Must specify :key or :autokey' }
}

但是 Raku 支持多重分派，所以有一个更干净的方法可以给 Vigenère 子程序增加另一个互斥行为。我们简单的将现有的代码从 sub 改为 multi:

multi Vigenère (Str :$text!, Str :$key!, Bool :$decode --> Str)
{
    # Body exactly as before
}

然后，我们再添加第二个乘法派发的变体，有不同的参数集和不同的主体:

multi Vigenère (Str :$text!, Str :$autokey! --> Str) {
    Vigenère( :$text, :key($autokey ~ $text) );
}

这个版本需要一个 :autokey 参数，而不是 :key 参数。然后，它立即重新分配到原来的(Bellaso)变体，直接通过文本不变(:$text)，但通过将所提供的自动键与文本连接起来，构建一个新的(非自动)键： :key($autokey ~ $text)。

解释器总是知道在任何时候都要调用 Vigenère 的哪个变体，因为它检查每次调用中传递的实际参数，并从考虑中排除任何参数列表不接受这些特定参数的变体。这意味着，如果我们传递一个 :key 参数，解释器将总是调用原来的 (Bellaso) 变体，而如果我们传递一个 :autokey 参数，解释器将总是调用我们新的 (Vigenère) 变体。

请注意，Vigenère 子程序的这个新的 autokey 变体不允许使用 :decode 参数。这是因为，使用 autokey 对文本进行编码只是 Bellaso 算法的一个小变化，而再次解码则要复杂一些。

要对经过自动密钥加密的文本进行解码，我们显然需要原始加密密钥。但在自动密钥系统中，大部分密钥都是由未加密的原始文本提供的。所以为了取回未加密的文本，我们必须向解码器提供…未加密的文本。嗯，嗯。

当然，除了自动密钥的最初几个字符并不是原始明文的一部分，它们只是指定的常规密钥（如 “BELLASO”、“SECRET” 等）的字符。

给定这个部分密钥，我们至少可以破译出加密文本的那么几个初始字符。这就给了我们原始信息的前几个字符，所以我们可以立即使用这些字符作为下一部分密钥，使我们能够解密更多的加密文本，从而给我们提供更多的几个信息字符，这就给了我们一些额外的密钥字符，有了这些字符，我们可以再提取几个明文字符，这…等等，等等，直到整个文本被解码。

在 Raku 中，这看起来像这样：

multi Vigenère (Str :$text!, Str :$autokey!, :$decode! --> Str)
{
    # Break out text that was enciphered by the original key...
    my ($cipherkey, $ciphertext)
        = $text.split: /<?at: $autokey.chars>/;

    # Decipher that key-enciphered initial text...
    my @autokey
        = Vigenère( :text($cipherkey), :key($autokey), :decode )
             .comb;

    # Progressively decipher the rest...
    [~] flat gather for $ciphertext.comb {
        FIRST take @autokey;
        @autokey.push:
           take %decoder{@autokey.shift}{$^cipherchar} // 0.chr;
    }
}

Vigenère multisub 的第三个变体需要三个必要的参数：文本、原始自动密钥和 :decode 标志。所以这个变体只有在解码一个自动密钥加密时才会被调用。

我们首先需要将文本分解成两个字符串：使用原始密钥加密的初始N个字符($cipherkey)，以及使用未加密消息本身加密的文本的剩余部分($ciphertext)。要做到这一点，我们调用文本字符串的 .split 方法，并传递给它一个 regex。只要 regex 匹配，文本就会被分割，所以我们在 regex 中使用 <?at: position> 断言，强制它只匹配原始密钥的长度：/<?at: $autokey.chars>/。

一旦我们在 $cipherkey 中得到了前N个字符，我们就可以通过调用原始的（Bellaso）解码变体来简单地用原始密钥（在 $autokey 中）对它们进行解密，我们通过将原始密钥作为一个 :key 参数，而不是作为 :autokey 来调用。像这样：

Vigenère( :text($cipherkey), :key($autokey), :decode )

然后我们使用 .comb 方法将解密后的明文转换成一个字符列表，并将其存储在 @autokey 中。

现在我们已经解密了前 N 个明文字符，我们可以开始从剩余的加密文本中迭代字符列表 (对于 $ciphertext.com {...})，使用下一个已知的自动密钥字符 (@autokey.shift) 来解密下一个消息字符 (%decoder{@autokey.shift}{$^cipherchar})。新解密的字符会被保存下来，作为后续的自动密钥字符使用（@autokey.push:）。

当我们在解密时，我们还需要捕获每一个被解密的字符，这样我们就可以最终将它们连接起来并作为解密后的文本返回.最简单的方法是使用一个 gather 块，它可以自动记住我们在它里面获取(take)的任何东西。

在本例中，我们首先要收集所有用原始密钥解密后存储在 @autokey 中的初始字符。因此，我们告诉 for 循环去获取(take)它们，但只在它的第一次迭代中:

FIRST take @autokey;

然后每次我们在循环中解密另一个字符时，我们也要把它取走，就在我们把它推到 @autokey 数组之前。

@autokey.push:
    take %decoder{@autokey.shift}{$^cipherchar} // 0.chr;

一旦解密 for 循环终止，gather 将返回一个我们传递给 take 的所有内容的列表。我们将这些字符（[~] flat）连成一个单一的字符串…就完成了。

所以现在，当我们想要 Vigenère 密码的时候，我们这样写：

$ciphertext
  = Vigenère( :text($plaintext), :key($secret) );

# and later...

$plaintext
  = Vigenère( :text($ciphertext), :key($secret), :decode );

而当我们想要 Vigenère 的实际密码时，我们这样写：

$ciphertext
  = Vigenère( :text($plaintext), :autokey($secret) );

# and later...

$plaintext
  = Vigenère( :text($ciphertext), :autokey($secret), :decode );

如果你接受现代语言学相对论，那么我们思考的语言可以塑造我们思考的方式，甚至可能限制我们思考的方式。

编程语言是程序员思考解决方案的工具。所以，你对编程语言的选择可能会塑造你思考解决方案的方式，甚至可能制约你思考解决方案的可能。

当你在一个像 Vigenère 世界（或者我们的世界！）这样一个语言模糊、计算复杂的世界里思考解决方案的时候，你需要一种语言足够复杂、计算能力足够强的语言，让你能够清晰有效地思考。

这也是我用 Raku 编程的原因。

by Damian