U. 频率分析法

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

以维吉尼亚密码为代表的多表置换密码存在一个极端严重的问题:保留了明文中的统计规律信息。

就以维吉尼亚密码为例,由于其使用的密钥长度 通常较短(否则不利于密钥的保密交换,尤其是为了防止已知明文攻击,每次都必须新交换一个密钥,或需要提前约定好大量密钥供备用),导致每个下标关于 同余的明文字符总被偏移相同的长度,或者说被进行同样的替换,比如明文为 ddd,密钥为 cb,就会发现结果是 fef,第一位和第三位的偏移量相同。

在唯密文攻击的前提下,如果攻击者知道了明文的统计规律,如每个字符的出现概率分布,那么就可以枚举密钥的长度 ,将按照下标关于 的余数对字符分组,由于每组的字符的替换相同,组内密文字符出现的概率分布就和明文相当相似(在维吉尼亚密码的情形下,是明文分布的一个偏移)。

我们定义这样一个多表替换密码体制,令 ,明文 ,密钥 ,,且是一个双射,则密文 。

为了便于频率分析,明文和密钥还满足如下条件:

  • 。
  • 明文字符按照下标关于 的余数分组后,各组相同字符出现的频率都相等,且能表示为 为分母的分数。
  • 在任何一组中,每种字符出现的频率如果非零则唯一。

容易发现,每种(出现过的)字符出现的频率是唯一的,可以利用这个性质来分析按下标关于 分组后,每组密文字符中每种密文字符对应的明文字符。

现在,我们将给出符合如上密码体制约束的一个密文(以 Base64 编码,RFC 4648 标准,+/),请你用频率分析法来分析出其明文(仅由 ASCII 可显示字符构成)。如果有多解,输出使得 最小的明文。

输入格式

第一行一个字符串 ,表示 Base64 编码后的密文。

第二行 个整数,第 个数(从 开始数)表示 ASCII 码为 的字符出现的概率 的值。

输出格式

一行一个字符串,表示明文。

样例

样例输入 1

1AJbTbqlW52/oreO1E3UQNQsIABbosZAgJEgQFuO1I4YornLucu0AiBNugDUz4BNIJHGLNSOW885jtRAOQLLTb9Ayyy0TSBAW52/ndRNv023/bnLOcuATVvP1EA5ndSiNEAgncYjxqU0TYCd1I45TYAjOU25TRidv5HLkdSlICzUz8Y6v8u/jlui1E3Gz7ojOY6Az7pNgE23kcYsxiw5z4A6Oc8gQNSd1CzULL8j1M/UQFsCxsvLz8vPy6XLpYClt023pTTLv6XGnVs6xo63onrP1CyATVtNIEC3LLdN1JEYTSAsuU3UQL/LgJ3Gz4AjW50gyxjLgJ25kYBNGEBbzw==
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 0 0 14 0 7 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 2 0 13 0 0 0 6 0 4 0 0 0 0 0 23 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 10 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 11 12 0 0 0 0 0 0 0 3 0 

样例输出 1

OICOI_CveG_*OOOCOuuACGvC-/uCC*O*lGGeGeAIuOIAO--Ou/vuO*C-**OC*I/OeC/uAOuCCvevOOeO_6Ge*e-OC-OC*vOG~Cuvvlv_~O-vO**O-l*OGOlve///O_uuO-v~eee*CGOOv-Il**--IO-O_/vuvu*--~*-uCOvOuOuelO-OCCIve/-/-/_/_-__O__~ee_vvC~v*_G6-Ou-OCOuC_u_OO/lOuuGOOCee-vv--lCvuele-vG/-OlCC-

数据范围与提示

对于前 的数据,密文与明文相等。(提示:只需解码 base64 字符串)

对于所有数据,。

友情提示:

  • char 类型是有符号的,当你需要将大于 127 的编码作为数组下标时,请使用 unsigned char。
  • 为了满足约束,密钥长度只有 种,可从小到大逐一验证。
  • 这题比较难写,下题比较难想。如果觉得写不出来可以转战下一题的部分分。