动机
替换密码把每个字母换成另一个字母。表面上,原来的单词已经消失,但替换过程可能保留足够多的结构,使观察者能够重建原文。研究时应依次提出几个不同的问题:加密规则是否存在逆映射?不知道逆映射的人能推断什么?哪些观察足以确定密钥?这些问题不能混为一谈。证明接收者可以正确解密,并不等于证明旁观者无法了解明文。
本节用模运算描述有限字母表。这个模型既能精确推导仿射替换的解密规则,也能严格证明某些信息必然泄漏。26 个字母与全部数值密钥仅用于说明计算。
定义
固定整数 ,用剩余类集合 表示字母表。对于英文大写字母,取 ,并约定 。长度为 的消息是剩余类组成的向量 。大小写、空格与标点都需要明确的编码规则。本节例子去掉空格并使用大写字母;这个约定只是简化计算。如果通信的其他部分暴露了单词边界,去掉空格并不自动隐藏那些边界。
定义 5.1.1
(单表替换密码与仿射密码)
单表替换密码在整条消息中使用同一个字母表置换 ,把各个 变为 。仿射密码进一步限制替换形式为
其中 是模 的剩余类,而且 必须可逆。有序对 是密钥。若存在整数 使 ,就称 是单位。记号 表示这个乘法逆元,而不是实数意义的倒数 。解密必须能恢复字母表中的每一个符号,不能只对某一条恰好选中的消息有效。
定理/命题
定理 5.1.2
(仿射解密的判别条件)
设 。映射 是 上的置换,当且仅当 。满足这个条件时,其逆映射是模 意义下的 。
证明
(以贝祖(Bézout)等式得逆映射,以碰撞证逆命题)
若 ,由贝祖(Bézout)等式可取整数 使 。取模后得到 ,于是
反过来,把 代入加密公式也会得到 ,所以这确实是双边逆映射。现在设 。剩余类 与 不同,但
因此这两个输入都加密为 。存在这种碰撞的函数不是单射,不可能在整个字母表上具有解密逆函数。两个方向均已证明。
加法参数 没有限制,因为加上 总可以通过加上 撤销;真正需要检查的是乘法。当 时,允许的乘数为
所以 有 12 种选择, 有 26 种选择,共有 312 个仿射密钥。不同的有序对确实给出不同的函数:函数在 处的值确定 ,在 处与在 处的函数值之差确定 。一般单表替换可以使用 个置换,但较大的密钥空间并不会消除所有结构性泄漏。
例题
例题 5.1.3
(加密并解密 MATH)
取 。欧几里得(Euclid)算法给出 ,故 ,从而 。明文对应的剩余类 加密为
密文是 QIZR。解密 Q 时,计算 ,还原为 M。其余三个符号分别给出 、、。逆映射直接恢复整条消息,不需要猜测其含义。
例题 5.1.4
(乘数非零仍然可能失败)
规则 不能在全部 26 个字母上唯一解密。A 对应 ,N 对应 ,两者都会加密为对应 的 D。若把 两边除以 2,却仍保留模数 26,就会错误地消除这种歧义。正确的约化结果是 ,它在模 26 下有两个可能值。
例题 5.1.5
(由两个已知字母恢复密钥)
观察者知道同一个仿射密钥把 E 变成 C,把 T 变成 Z。用剩余类表示,就是 与 。相减得 。由于 ,两边乘以 7 得 ,再得 。把结果代回两条原始同余式可以核对全部数据;只找到一个看起来合理的 ,还不算完成检查。
已知明文与一次同余方程
上例的关键不只是“有两个观察”,而是两个已知明文剩余类之差可逆。一般地,若已知 与 ,则
若 是单位,第一式给出唯一的候选 ;随后仍要检查 是否为单位,以及它是否满足所有观察。若这个差不是单位,就不能随意除以它。此时应使用一般的一次同余方程定理。
定理 5.1.6
(一次同余方程的解数)
设 为整数,,且 。同余方程 有解,当且仅当 。有解时,它在模 下恰有 个不同解。只有同时满足 的解,才能作为仿射密码的乘数。
证明
(系数与模数一起约简)
若 被 整除,则 与 的每个公因子也整除 ,这证明了必要性。反过来,设 ,写成 、、。原方程等价于 。因为 ,它确定模 的唯一一个类 。如果 ,所有整数都属于唯一的剩余类,无需进行逆元计算。该类在模 下的代表可以写成
这些值模 两两不同,而且穷尽所有解。仿射密码要求乘数为单位,是另外的筛选条件,不能与同余方程本身的解数混淆。
证明透视
如何安全地约简同余式
必要性只用到整除: 与 的公因子整除 及 ,从而整除 。充分性靠一个步骤:把 、 与模数 同时除以 。若只除 与 而保留模数 ,就会犯乘数 例子中的错误: 会变成错误的 。
约简后, 使 模 可逆,所以模 恰有一个类 。个数 来自提升:模 的一个类分裂成模 的 个类。整个证明没有用到仿射乘数的可逆性,所以它必须事后作为另一个筛选条件加上。
定理数的是同余方程的解,而不是密钥;下面的情形显示两个数目可以相差多远。
反例模式
两个已知字母未必确定密钥
例如,若 A 加密为 D,N 加密为 Q,则 ,并且 。这条方程只说明 是奇数。在它的 13 个解中, 不是单位,其余 12 个都是合法乘数。因此,这两个观察仍留下 12 个仿射密钥。“任意两个已知字母一定确定仿射密钥”是错误命题。另一方面,不可逆的差也未必留下多个合法密钥:方程 有解 ,其中只有 1 是单位。修正正是定理的假设:两个观察唯一确定乘数,当且仅当 模 是单位;否则必须用 筛选 个解,并逐一核对每个观察。
精确信息泄漏与频率分析
用固定单表替换得到的密文保留完全相同的重复位置模式:
正向成立是因为函数对相同输入给出相同输出;反向成立来自置换的单射性。两个位置的明文字母相同,当且仅当对应的密文字母相同。因此,每个字母出现的次数也只是被重新标记。若明文符号 出现 次,则密文符号 也出现 次。
这些结论是确定性的。频率分析则加入了统计假设:用某种语言或文体写成的较长消息,往往具有不均匀的符号频率。分析者可以把密文的实际计数与某个语言模型比较,并尝试可能的替换。高频密文符号可能对应高频明文符号,但这只是候选推断,不是严格证明。短样本、特殊词汇、不同语言、刻意限制用字的文章,以及是否保留标点,都可能改变证据的意义。猜测得到的替换关系,应当用整条消息及其他已知信息继续检验。
例题 5.1.7
(BANANA 的计数只是换了标签)
在 时,B N、A I、N V,所以 BANANA 变成 NIVIVI。明文 A、N、B 的次数分别为 ,密文 I、V、N 的次数也是 。位置模式仍然是一个符号、第二个符号、第三个符号、第二个、第三个、第二个。长样本中猜测最高频符号可能有帮助,但这个六字母例子本身并不能确立某种语言频率模型。
一个计数统计量可以进一步区分这两类论证。对于长度 的字符串,定义重合指数
分子计算字符相同的有序不同位置对;分母计算全部有序不同位置对。因此,从字符串中均匀抽取两个不同位置时, 就是所见字符相同的概率。单表替换只改变计数的标签,所以严格保持 。BANANA 的重合指数为 。如果字符独立地按概率 抽取,则期望的匹配概率是 。这里的独立抽样模型是额外假设,不能当作任意文章都满足的定理。
对于模 26 的仿射密码,也可以枚举全部 312 个密钥,查看各自给出的候选明文。枚举是有限搜索;根据语言是否自然对候选排序,则属于另一个推断步骤。如果观察者能够请求同一密钥下选定符号的密文,只需请求 与 ,就能直接得到 与 ,从而恢复整个仿射密钥。因此,声称密码能够抵御观察者之前,必须先说明观察者被允许获得哪些信息。
一个可严格证明的安全边界
定理 5.1.8
(固定替换必然泄漏一种两字母区别)
设字母表包含不同符号 。无论如何随机选择置换密钥,只要两个位置使用相同置换,观察者就能以确定方式区分消息 与 :前者的两个密文符号相同,后者的两个密文符号不同。
证明
(每个置换都保持相等关系)
每个置换同时保持符号的相等与不等,所以两种消息可能产生的密文集合互不相交。观察者只要检查两个密文符号是否相等,就能判断是哪一种消息,完全不依赖密钥的抽样分布。即使每条完整消息都重新抽取一个置换,论证仍然成立;若在不同位置使用不同变换,就已经换成另一种系统。
概念视角结构
均匀随机替换泄漏的恰好是模式
若长度为 的消息 对所有位置 都满足 ,称它们模式等价。此时规则 在用到的符号上良定义且为单射,因此可延拓为一个置换 ,使逐坐标有 。若 在全部 个置换上均匀分布,则 也是如此;所以 与 同分布。上面的定理又以确定性区分不同的模式,两者合起来说明:这种系统泄漏的恰好是等号模式。
这证明固定替换无法隐藏一个明确指定的消息区别,既不依赖英文频率,也不依赖密钥空间小。它并没有断言每一种确定公式在任何密钥实验中都会失败。密钥如何抽样是关键。考虑 上的一次一密:选择与消息独立的均匀密钥向量 ,并令 。对于任意固定的输入向量 和密文向量 ,恰好一个密钥向量产生 ,所以按 的随机选择计算,概率为
只要密钥向量独立于消息,同样长度的每条消息都会得到相同的密文分布。这就是该有限模型中的完全保密性。它要求密钥与明文等长、均匀随机、独立生成、保持秘密,而且只使用一次;这些都是实质性假设。
若消息 重用同一个密钥向量,则逐坐标有 。即使观察者最初不知道任何一条明文,也会得到两条明文之间的关系。一条明文后来一旦已知,另一条即可由减法恢复。此外,给密文加上选定向量 ,会使解密明文也增加 。所以保密本身不意味着消息真实且未被篡改。这些代数事实说明,正确性、机密性、密钥管理和消息完整性必须分别讨论。本节的仿射例子与抽象一次一密模型,都没有规定一个可直接部署的通信协议。
常见错误
常见错误
(乘数非零不等于可逆)
在域中,例如素数模数的剩余类中,“乘数非零”确实足以保证可逆;模 26 时却不成立:乘数 2 把 A 和 N 送到同一个字母。正确的判据是 。
常见错误
(模逆元不是倒数)
5 模 26 的逆元是剩余类 21,因为 。它不是有理数 ;后者根本不是剩余类。
常见错误
(频率保持不会说出明文字母)
频率保持并不表示明文最高频符号一定是 E。它表示实际计数无论是什么,替换都会保留这些计数,只改变标签。一条全由 A 构成的消息,加密后只显示一个不断重复的符号;仅凭这个数学不变量,不能判定该符号原来就是 A。最后,可能密钥的数量只是搜索空间的大小,并不概括观察者能够利用的全部信息。结构不变量可能在完全没有识别密钥的情况下,就已经回答观察者关心的问题。
练习
快速检查
(在模 26 下,求 的解密规则,并加密 CODE。)
解答
因为 ,解密规则是 。CODE 的剩余类为 ,分别加密为 ,所以密文是 RXYF。将这四个密文值代入解密式,会恢复原来的四个剩余类。
快速检查
(字母表大小为 12 时,判断 与 能否唯一解密。能够解密时给出逆映射;不能时给出具体碰撞。)
解答
第一式的乘数在模 12 下的逆元是 5,故逆映射为 。第二式的乘数与 12 的最大公因子为 4;因为 ,输入 和 都加密为 1。因此第二式不能在整个字母表上可逆。
快速检查
(同一个模 26 仿射密钥把 A 加密为 F,把 B 加密为 M。求密钥,并解密 M。)
解答 · 答案
方程为 与 ,故 。由于 ,M 对应的 12 解密为 ,即 B。这与已知观察吻合。
快速检查
(解 ,再筛选出能够用于模 15 仿射密码的乘数。)
解答
此时 整除 9。把系数、右边与模数同时除以 3,得到 ,即 。模 15 的解为 。合法乘数是与 15 互素的 4 与 14;9 不满足要求。
快速检查
(某段长度为 8 的密文,各符号的非零计数为 。求重合指数。仅凭这个数能否识别原来的明文字母?)
解答 · 答案
重合指数是 。任意重新标记字母都不改变这个数,因此它不能确定具体字母。在明确的统计模型中,它仍可能提供部分证据。
快速检查
(一个模 26 密钥垫被重复使用。同一位置的两条密文剩余类分别为 8 与 15。若第一条明文在该位置为 2,求第二条明文和密钥垫在该位置的剩余类。)
解答 · 答案
密钥垫剩余类是 ,第二条明文是 ,对应 J。也可以直接算 。所有等式均在模 26 下解释。
快速检查
(证明两个合法模 仿射密码的复合仍是合法仿射密码。进行两次仿射加密是否扩大了可能的加密函数族?)
解答
先应用 ,再应用 ,结果为 。由于 都是单位, 的逆元为 ,所以复合仍为仿射密码。任何仿射密码也都可以与恒等密钥 复合得到,所以重复仿射加密并不扩大函数族。这个结论讨论的是最终的加密函数,而不是能描述同一个函数的不同密钥对组合的数量。