以维吉尼亚密码为代表的多表置换密码存在一个极端严重的问题:保留了明文中的统计规律信息。
就以维吉尼亚密码为例,由于其使用的密钥长度 通常较短(否则不利于密钥的保密交换,尤其是为了防止已知明文攻击,每次都必须新交换一个密钥,或需要提前约定好大量密钥供备用),导致每个下标关于 同余的明文字符总被偏移相同的长度,或者说被进行同样的替换,比如明文为 ddd,密钥为 cb,就会发现结果是 fef,第一位和第三位的偏移量相同。
在唯密文攻击的前提下,如果攻击者知道了明文的统计规律,如每个字符的出现概率分布,那么就可以枚举密钥的长度 ,将按照下标关于 的余数对字符分组,由于每组的字符的替换相同,组内密文字符出现的概率分布就和明文相当相似(在维吉尼亚密码的情形下,是明文分布的一个偏移)。
我们定义这样一个多表替换密码体制,令 ,明文 ,密钥 ,,且是一个双射,则密文 。
为了便于频率分析,明文和密钥还满足如下条件:
- 。
- 明文字符按照下标关于 的余数分组后,各组相同字符出现的频率都相等,且能表示为 为分母的分数。
- 在任何一组中,每种字符出现的频率如果非零则唯一。
容易发现,每种(出现过的)字符出现的频率是唯一的,可以利用这个性质来分析按下标关于 分组后,每组密文字符中每种密文字符对应的明文字符。
现在,我们将给出符合如上密码体制约束的一个密文(以 Base64 编码,RFC 4648 标准,+/),请你用频率分析法来分析出其明文(仅由 ASCII 可显示字符构成)。如果有多解,输出使得 最小的明文。