http://blogs.perl.org/users/damian_conway/2019/07/vigenere-vs-vigenere.html
第15 届 Perl 每周挑战赛的第二项任务是为 Vigenère Cipher 实现编码器和解码器。但这比看起来要复杂得多,因为以 Blaisede Vigenère 命名的密码实际上并不是由他发明的,而 Vigenère 实际发明的密码并不是以他的名字命名的。
那么我们应该实现 Vigenère Cipher 加密…还是 Vigenère 加密?为什么不两个都要呢!
Vigenère Cipher 是由吉奥万·巴蒂斯塔·贝拉索于 1553 年制定的,然后错误归因到约三百年后的 Vigenère 身上。它使用tabularēcta 把消息文本转换为密文,然后再转回去。
给定用户提供的密钥(例如 “BELLASO”),我们通过匹配密钥和消息的相应字母来加密消息(例如 "VIGENEREDIDNOTINVENTTHIS"
),然后将它们用作两个索引以在 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
换句话说,tabularēcta 的每一列是单独的Caesar Cipher (或ROT-N转录),其中每个连续的密钥字母选择在消息中的相应字母上执行哪个替换。
这种方法在 16 世纪被广泛认为是*“难以理解的”*,尽管查尔斯·巴贝奇在 1854 年“重新发现”的两周内打破了它的一个例子,弗里德里希·卡基斯基在不到十年之后发表了可靠的一般攻击。尽管如此,*Vigenère Cipher* 提供合理的安全性,提供的选择的关键是足够长的时间和不同寻常,足以防止简单的字典攻击。讽刺的是,我们稍后会看到,Vigenère’ 的实际密码优雅解决了这两个问题。
为了实现 VigenèreCipher,我们首先需要构建一个 tabularē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];
如果我们后面切换到包含 '❤️'
的非连续字母表,那么代码会变得更加复杂。
如果 2D 查找表是 2D 字典(在 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};
更好的是,使用这种基于散列的方法来构建2D 解码字典同样简单,只需将嵌套映射从字母字符反转为密码字符即可:
constant %decoder
= @𝑡𝑎𝑏𝑢𝑙𝑎-𝑟𝑒̄𝑐𝑡𝑎.map:
{ @^cipher.head => hash @^cipher Z=> @alphabet }
之后我们可以像这样解码一个加密的字符:
my $plaintext-char = %encoder{$key-char}{$ciphertext-char};
一旦我们有了这两个2D词典,VigenèreCipher就很容易实现:
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的编译器所需要的两个参数。还有一个可选的命名 boolean参数(没有尾随感叹号),指示我们是否要解码。signature ()末尾的长箭头指定子例程返回一个字符串。--> Str
在子例程中,我们首先将文本字符串和键分成单个字符(和)的列表。我们还 需要重复键字符序列,以便键至少 与文本字符串一样长。我们可以准确地计算出 需要多少次重复,但是只需要 经常无限地重复键()就更容易了。 需要在开头的垂直条来展平关键字符列表。否则, 我们最终会得到一个重复的键列表列表,而不是重复的键字符列表 。$text.comb``$key.comb
|$key.comb xx ∞
然后我们根据我们是否正在解码来选择我们需要的两个编码字典中的哪一个。在Raku中,三元选择运算符是*真值*``*假值*
, 而不是*真值*``*假值*
。`test ?? ```` !!
一旦我们完成了所有设置,实际的编码或解码是微不足道的:
(@keychars Z=> @textchars)
.map({ %recoder{.key}{.value} // 0.chr })
.join;
我们首先从下一个文本的每个字符匹配的连续字符从重复键,再次使用的拉链成-A-列表中,对运营商(间) 两个列表:Z=>``(@keychars Z=> @textchars)
然后,我们通过查找查找表中的每个关键字符()和每个 对应的文本字符(),将该对列表映射到加密/解密字符列表。如果 字符组合没有可用的转换,我们只 使用空字符()作为占位符。这可确保 指定字母表外的任何字符都清晰地映射 到加密字符串之外,而不会影响其将来的解密。.key``.value
转换完所有字符后,只需连接列表()即可生成最终字符串。.join
这就是VigenèreCipher。
那么Vigenère的密码呢?
上面讨论的加密技术作为密码具有一些严重的缺点。1863年,Friedrich Kasiski观察到重复密钥字符串以生成足够长的密钥意味着单个加密消息有时可以重复使用表格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
一旦我们知道解密密钥有多长,我们就可以加载一个合适的字典并过滤它以获得合适的候选密钥:
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年,BlaisedeVigenè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
子例程添加另一个互斥行为。我们简单地将现有代码从a sub
更改为multi
:
**multi** ``的V @ genere`` (Str :$text!, Str :$key!, Bool :$decode -->Str)
{
# Body exactly as before
}
然后我们添加第二个multiply dispatched 变体,带有一组不同的参数和一个不同的主体:
multi Vigenère (Str :$text!, Str :$key!, Bool :$decode --> Str)
{
# Body exactly as before
}
此版本需要参数,而不是参数。 然后立即重新分配到原始(Bellaso)变体,将文本 直接传递给未更改的(),但 通过将提供的自动键与文本连接来构造新的(非自动)键::autokey``:key
multi Vigenère (Str :$text!, Str :$autokey! --> Str) {
Vigenère( :$text, :key($autokey ~ $text) );
}
解释器总是知道Vigenère的
哪个变体在任何时候调用,因为它检查传递给每个调用的实际参数,并且不考虑任何其参数列表不接受那些特定参数的变体。这意味着,如果我们传递一个参数,解释器 将始终调用原始(Bellaso)变体,而如果我们传递一个 参数,则解释器将始终调用我们的新(Vigenère)变体。:key``:autokey
需要注意的是,这种新的自动密钥变种的V @ genere
子程序不允许一个说法。这是因为,虽然使用 自动键对文本进行编码只是Bellaso算法的一个小变化, 但再次解码它会稍微复杂一些。:decode
要解码已自动加密的文本,我们显然需要原始加密密钥。但是在自动键系统中,大部分键都是由原始未加密的文本提供的。因此,为了取回未加密的文本,我们必须向解码器提供……未加密的文本。Hmmmmm。
当然,除了自动键的最初几个字符不是原始明文的一部分; 他们是仅有的人物经常键(例如 "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èremultiisub的
第三个变体需要三个必需的参数:文本,原始自动键和标志。所以这个变体 将仅解码自动密钥加密时被调用。:decode
我们首先需要将文本分成两个字符串: 使用原始密钥()加密的初始N个字符,以及 使用未加密的 消息本身()加密的文本的其余部分。为此,我们调用文本字符串的方法,并将其传递给正则表达式。 在正则表达式匹配的地方,文本将被拆分,因此我们在正则表达式中使用断言,强制它仅匹配原始键的长度:
/<?at: $autokey.chars>/
一旦我们有了前N个字符$cipherkey
,我们可以通过调用原始 (Bellaso)解码变体简单地用原始密钥(in $autokey
)解密它们,我们通过将原始密钥作为参数传递而不是作为参数来调用。像这样:
Vigenère( :text($cipherkey), :key($autokey), :decode )
然后我们使用该方法将解密的明文 转换为我们存储的字符列表。.comb``@autokey
现在我们已经解密了明文的前N个字符,我们可以开始遍历剩余加密文本()中的字符列表,使用下一个 已知的自动键字符()来解密下一个 消息字符()。 然后保存新解码的字符以用作后续的 自动键字符()。
当我们解密时,我们还需要捕获每个解码的字符,因此我们最终可以连接并将它们作为解密文本返回。最简单的方法是使用一个gather
块,它可以自动记住我们take
在其中的任何内容。
在这种情况下,我们首先必须收集用原始密钥解密然后存储的所有初始字符@autokey
。所以我们讲的for
环路take
他们,但仅在其第一个迭代:
然后每次我们解密循环中的另一个字符时,我们也必须take
这样做,就在我们将它推入@autokey
数组之前:
@autokey.push:
take %decoder{@autokey.shift}{$^cipherchar} // 0.chr;
一旦解密for
循环终止,gather
它将返回我们传递给的所有内容的列表take
。我们将这些字符()连接成一个字符串……我们就完成了。[~] flat
所以现在,当我们想要VigenèreCipher时,我们写道:
$ciphertext
= Vigenère( :text($plaintext), :key($secret) );
# and later...
$plaintext
= Vigenère( :text($ciphertext), :key($secret), :decode );
And when we want Vigenère’s actual cipher, we write:
$ciphertext
= Vigenère( :text($plaintext), :autokey($secret) );
# and later...
$plaintext
= Vigenère( :text($ciphertext), :autokey($secret), :decode );
当我们想要Vigenère的实际密码时,我们写道:
如果你接受现代语言相对论,那么我们认为的语言可以塑造我们思考的方式。也许甚至限制在我们的方式可以考虑。
编程语言是程序员思考解决方案的工具。所以,你的编程语言的选择,可以塑造你是怎么想的解决方案,甚至可能限制它是如何可能的,你想想他们。
当你在思考世界上的解决方案时,语言模糊,计算复杂,如Vigenère(或我们的!),你需要一种语言足够复杂,计算机表达能力强的语言,使你能够清晰有效地思考。
这就是我在Raku中编程的原因。