动机
每次只改变一个字母的代换,很容易用代数来描述。用矩阵混合若干个字母似乎能隐藏更多结构,而让位移量随位置变化似乎能击败单一的代换表。这些都是值得研究的有用的数学改进,但单靠任何一种运算都不能确立保密性。解释解密的同一套代数,也揭示了观察者能够学到什么。
我们把矩阵密码和周期位移密码当作有限的代数系统来考察。我们的问题是精确的:解密何时是唯一确定的?需要多少已知明文才能确定一个矩阵?即使密钥未知,加密之后仍保留哪些关系?回答这些问题不需要对典型英文文本作任何假设,也不依赖统计攻击的效果。
字母用剩余类表示,A 为零,B 为一,依此类推。例子使用模二十六,但证明对一般的剩余类环都成立。这些是经典的教学构造,并不是对当代消息的保护方案。它们在这里的价值,在于把可逆性、密钥重用与可区分的消息分布联系起来。
定义
定义 5.2.1
(Hill 密码)
设 ,。长度为 的块上的 Hill 密码使用矩阵 和列明文块 ,密文为 。一个合法的解密密钥必须使该映射在所有块上都是双射。所有例子均使用列向量约定;采用行向量约定会改变矩阵作用在哪一侧。
定义 5.2.2
(周期加法密码)
周期为 的周期加法密码使用密钥 。对长度为 的明文,其输出为
当字母表大小为二十六时,这就是 Vigenère 密码通常的代数模型。在作相应的恢复论断时,我们假定块边界与密钥对齐方式是已知的。若消息不能填满一个块,则必须另行约定填充规则;块映射的可逆性并没有规定填充。
概念视角结构
周期密码是交错排列的几个移位密码
按相位划分位置:对 ,第 组包含 。在第 组上,密码只加上同一个常数 ,所以每组都是带自身密钥的单表移位。因此,周期为 的密钥恰好是作用于交错子序列上的 个独立移位密码。固定替换的每个不变量,例如等号模式和重新标记后的符号计数,都在每组内保留;同相位差恒等式正是移位情形下的这一事实。
定义 5.2.3
(完美保密性)
作为比较,完美保密性是指:对于任意与密钥独立的明文分布,观察到密文后明文的分布保持不变。等价地,所有允许的明文诱导出相同的密文分布。这个强的有限概念不同于计算上无法区分消息,并且允许用特别选取的明文给出精确的反例。
定理/命题
定理 5.2.4
(剩余类环上正确的可逆性检验)
Hill 映射对每个块都能唯一解密,当且仅当 是 中的单位,等价地 。对于 ,可逆矩阵密钥的个数为
在合数模下,非零的行列式不一定是单位。
定理 5.2.5
(已知块与周期差分会揭示结构)
若 个已知明文块构成行列式为单位的矩阵 ,则它们的密文矩阵 唯一确定 Hill 密钥为 。在周期加法密码中,模周期同余的位置 满足 。特别地,对长度超过周期的所有消息,重复使用的周期密钥不能给出完美保密性。
定理 5.2.6
(完美保密性的有限密钥空间障碍)
对有限的消息集与密钥集,若加密是确定性的、解密是正确且确定性的,并且具有完美保密性,则当所有消息都允许时,要求具有正概率的密钥至少与消息一样多。因此,当 时,仅有 种可能取值的周期为 的密钥,无论其密钥分布如何,都不能完美地隐藏 中每一条长度为 的消息。
证明思路或证明
行列式必须是单位,而不仅仅是非零
证明
(单位、伴随矩阵与中国剩余定理计数)
若 有矩阵逆 ,则在交换环中 ,所以 是单位。反之,伴随矩阵恒等式 在乘以行列式的逆之后给出逆矩阵。由 Bézout 恒等式, 中的单位恰是与 互素的剩余类。
为了把矩阵可逆性与所述的可解密性质联系起来:双射 对每个标准基列向量都有原像。把这些原像放入矩阵 中,得到 。由行列式可知 是单位,再由伴随矩阵得到双侧逆。这样就避免了事先假设任意逆函数都可由矩阵表示。反之,矩阵逆显然给出唯一解密。
中国剩余定理把模二十六的每个元素对应到它模二与模十三的一对剩余类。这是环同构,所以它把矩阵乘积与逆矩阵变为逐分量的乘积与逆。矩阵可逆当且仅当两个域上的矩阵都可逆。在有 个元素的域上,可逆二阶矩阵的第一列可以是任一非零向量,共 种选择。它的张成空间有 个元素;第二列在其外选取,有 种选择。由此得到乘积公式,代入二与十三即得所示的计数。若数遍全部 个矩阵,则会包含许多不能解密的密钥。
只有当数据构成一组基时,才能由已知明文求解
证明
(右乘数据矩阵的逆)
把已知块写成列。加密给出 ,所以若 可逆,右乘 得 。这同时证明了恢复性与唯一性。仅有观察到的块的个数是不够的;它们必须在实际的剩余类环中满足可逆条件。
反例模式
数据的行列式非零并不足够
例如,在 上 不可逆。两个可逆密钥 与 在这些观察上给出相同的密文矩阵 。因此,即使行列式非零(此处为四),两个观察到的块也不足以确定一个二阶密钥。在这个环上,普通的域上线性无关性并不是正确的检验。修正正是定理的假设:数据矩阵 的行列式必须是单位,在这里即与 互素。
即使没有任何已知明文,也存在泄露。可逆线性映射只把零映到零。因此无论在可逆密钥上使用什么分布,零块与任何非零块的密文分布的支撑都不相交。纯粹的 Hill 密码无法完美地隐藏这一对。更一般地,设 为 中由一个块的各坐标生成的理想。由于 的每个坐标都是 各坐标的线性组合,所以 。再应用逆映射即得相等。因此,所生成的坐标理想是与密钥无关的不变量,所揭示的不仅是该块是否为零。
重复使周期密钥相互抵消
证明
(相同相位消去密钥)
在密钥相位相同的位置,把两个密文等式相减会消去密钥符号,给出差分恒等式。为看出精确的保密性失败,设 ,并比较两个明文:全零字与仅在位置 处为一的字。对前者, 必然成立;对后者,该差必然为一。无论周期密钥取何种分布,观察者都能完美地区分它们。不需要任何语言频率的估计。
当两条消息用相同对齐的加法密钥加密时,同样的重用现象也会发生:把密文相减就揭示了明文之间的差。此时已知的某条消息会暴露它所用到的每个对应密钥符号。然而,如果密钥对每个消息位置有一个独立均匀的符号且只使用一次,则每个明文都诱导出所有密文字上的均匀分布。对任何给定的明文和密文,恰好存在一个把它们联系起来的加法密钥。因此在此模型中,一次一密具有完美保密性;重复一个较短的密钥会使这一性质消失。
两种攻击遵循同一模式:观察者都不需要先恢复整个密钥。只要两条允许的消息迫使某个可观察不变量取不同的值,保密性断言就失败了,即使穷举密钥搜索并不方便。
为什么密钥空间的下界不可避免
证明
(从消息到密钥支撑集的单射)
选取一个给每条允许的消息赋予正概率的明文分布。某个密文 以正概率出现。完美保密性要求在观察到它之后每条消息仍然是可能的。因此,对每条消息 ,必须存在一个具有正概率、把 加密为 的密钥。不同的消息需要不同的密钥:由于正确性,一个固定的密钥和密文只能解密为一条消息。为每条消息指定一个这样的密钥,就得到从消息集到密钥支撑集的单射。因此密钥支撑集不能更小。
证明透视
每个假设在计数论证中的位置
全支撑的先验分布是关键一步。它由证明者选取,这是允许的,因为完美保密性必须对每个明文分布成立;有了它,完美保密性就表示:观察到任何正概率的密文后,没有消息会变得不可能。固定一个这样的密文 ,安全性定义便变成存在性陈述:每条消息 都有正概率的密钥使 。
正确的确定性解密只用来使选取 成为单射,因为固定密钥只把 解密为一条消息。证明以比较基数收尾。“所有消息都允许”这个假设是必要的:若只允许 与 两条消息,则只在第一个位置加上一个均匀符号,就能用 个密钥完美隐藏它们,不论长度为何。
这个计数条件是必要的,而不是充分的。一大族线性密钥仍然保持零不变,如前所示。反之,较短密钥的方案可以以计算安全性而非完美保密性为目标;这个计数定理并不反驳一个精确陈述的计算性假设。明确保持安全性概念,能防止把密钥数量的观察误当作关于所有加密的普遍论断。
例题详解
例题 5.2.7
(加密并求逆一个双字母块)
取模二十六下的 。它的行列式是九,九的逆元是三。因此
字母 HI 构成列向量 。相乘得 ,即字母 TC。再应用逆矩阵得 ,恢复出 HI。如果取转置而不改变列向量约定,就会得到一个不同的密码,所以编码与解密的计算都必须使用所声明的方向。
例题 5.2.8
(由一对合适的块恢复密钥)
设已知明文矩阵为 。对前面的密钥,密文矩阵为 。由于模二十六下 ,计算 即恢复出 。该攻击使用两个完整对齐的块,不需要猜测字母频率。对于前面所述行列式非单位的观察,其证明就会失效。
例题 5.2.9
(一个三符号的周期位移)
使用密钥剩余类 与明文 HELLOW,它表示为 。重复密钥后得到密文 ,即 KFPOPA。位置零与位置三相位相同,它们的密文之差为 ,恰等于明文之差 。其余相位相同的差模二十六分别为十与十一。若前三个明文符号已知,把它们从前三个密文符号中减去即恢复整个周期,并能以相同的对齐方式解密所有后续位置。
常见错误
常见错误
(可逆的密码不一定能隐藏消息)
可逆性是正确性性质。单位矩阵是可逆的,却暴露其全部明文。即使在所有可逆 Hill 密钥中均匀选取,零和坐标理想仍被保持。可逆性、大的密钥空间与完美保密性是三个独立的断言,需要分别论证。
例如,坐标生成偶数剩余类理想的块,在可逆矩阵作用下不可能加密为生成整个环的块。量 与代表元的选取无关地描述了这个理想。选择另一个可逆矩阵无法消除这种泄露。
常见错误
(重复使用平移块会重新引入关系)
加上一个独立均匀的平移块 以得到 ,会使一个块在任意固定的 条件下是均匀的,因为平移是双射。这一观察针对的是新采样的全长度掩码。在多个块上重复使用同一个 ,会使它们的密文差等于 乘以明文差,重新引入关系。仅仅把该密码称为仿射并没有规定安全的密钥使用实验。
总结
矩阵解密要求在剩余类环中行列式为单位。合适的已知明文会暴露矩阵,而坐标理想即使没有恢复密钥也已经揭示了结构。重复使用的加法密钥会暴露相位相同位置之间的差。精确的计数解释了为什么较短的有限密钥不能完美地隐藏每条更长的消息,而一次一密则展示了完整的独立掩码如何满足这一强要求。
练习
快速检查
(为什么 在模二十六下不能唯一解密?给出两个发生冲突的明文块。)
在核中找一个非零块。
解答
它的行列式二不是单位。不同的块 与 都加密为零,因为模二十六下 。在有零因子的环中,非零的行列式并不能阻止出现非平凡的核。
快速检查
(计算 上可逆二阶矩阵的个数。)
先数第一列,再数不在其张成空间中的第二列。
解答 · 答案
非零的第一列有八种选法。它的张成空间有三个向量,所以第二列有六种选择。个数为 。
快速检查
(周期为二的密钥加密四符号消息 与 。在不知道密钥的情况下,给出一个能区分这两个密文分布的观察量。)
用两个密钥相位相同的位置。
解答 · 答案
观察 。这两个位置的密钥相位相同。对第一条消息该差总为零,对第二条消息总为一,所以在任何密钥分布下它们的密文支撑都不相交。
快速检查
(为什么有限密钥空间的下界并不能证明一个碰巧密钥多于消息的密码具有完美保密性?)
问一个基数条件能否说明密文分布。
解答
该定理只给出一个必要的基数条件,对于不同消息是否诱导出相同的密文分布则只字未提。Hill 族给出了充分性的反例:无论它有多少个密钥,每个线性密钥都把零送到零,并把每条非零消息送到非零密文。