密码破解者
题目背景
1941 年 12 月 7 日凌晨,珍珠港驻守美军通信员截获了一份日军电报。早上 8 时日军的正式进攻就会展开,为了减少太平洋战场伤亡,你被指派去协助破解密文。情报部门已得知了密文加密的层数和每层加密的方法。由于时间紧急,你只剩 1 秒的时间来破解日军的密文。
题目描述
据情报得知日军共有 $3$ 种加密方式:
一、栅栏密码:
所谓栅栏密码,就是把要加密的明文分成 $L$ 个一组,然后把每组的第 $1$ 个字连起来,形成一段无规律的话。一般比较常见的是 $2$ 栏的棚栏密码。
比如明文:`THERE IS A CIPHER`
去掉空格后变为:`THEREISACIPHER`
两个一组,得到:`TH ER EI SA CI PH ER`
先取出第一个字母:`TEESCPE`
再取出第二个字母:`HRIAIHR`
连在一起就是:`TEESCPEHRIAIHR`
这样就得到我们需要的密码了。
但也可能有更多的栏数。
注:若明文长度不能整除栏数,则分组后剩下的单独为一组,如:
`THERE IS A CIPHER`,$3$ 栏加密分组为:`THE REI SAC IPH ER`
先后取出第一二三个字母(最后一组只能取前两个),加密后为: `TRSIE HEAPR EICH`(去掉空格)。
二、维吉尼亚(Vigenère)密码:
维吉尼亚密码首先应用了“密钥”的思想,其在密码届具有十分重要的意义。
在密码学中,我们称需要加密的信息为明文,用 $M$ 表示;称加密后的信息为密文,用 $C$ 表示;而密钥是一种参数,是将明文转换为密文或将密文转换为明文的算法中输入的数据,记为 $k$。在 Vigenère 密码中,密钥 $k$ 是一个字母串,$k=k_1k_2\cdots k_n$。当明文 $M=m_1m_2\cdots m_n$ 时,得到的密文 $C=c_1c_2\cdots c_n$,其中 $c_i=m_i\oplus k_i$,运算 $\oplus$ 的规则如下表所示:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
A -A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
B -B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
C -C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
D -D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
E -E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
F -F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
G -G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
H -H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
I -I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
J -J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
K -K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
L -L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
M -M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
N -N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
O -O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
P -P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
Q -Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
R -R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
S -S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
T -T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
U -U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
V -V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
W -W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
X -X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
Y -Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
Z -Z A B C D E F G H I J K L M N O P Q R S T U V W X Y
Vigenère 加密在操作时需要注意:
当明文 M 的长度大于密钥 k 的长度时,将密钥 k 重复使用。
例如,明文 M=Helloworld,密钥 k=abc 时,密文 C=Hfnlpyosnd。
三、QWE键盘码:
随着键盘普及,也出现了相应的键盘码。
这是一个常见的键盘,在左边字母区有三行字母分别为:
QWERTYUIOP
ASDFGHJKL
ZXCVBNM
从第一排第一列开始分别用Q替代A,W替代B……M替代Z以此类推。
如 CODING 加密后即为 EGROFU.
这对于现在来说算是简单的加密方法,但对于键盘不普及的二战时期却是一大难题。
输入输出格式
输入格式
输入第一行为一个正整数N 表示截获的密文共用了N重密码加密。
第二行为一个字符串S表示加密后的密文。
以下3-N+2行共N行每行开头一个正整数K(1<=K<=3)表示对应的加密方式。
给出的加密方式按顺序给出,即给出的第I重加密为实际加密过程的第I重(1<=I<=N)。
若K=1则表示用栅栏密码加密,之后一个正整数L表示加密所用栏数。
若K=2则表示用维吉尼亚码加密,之后一个字符串T表示密钥。
若K=3则表示用QWE键盘码加密。
输出格式
共一行。一个字符串,表示破解N重加密后的明文。
输入输出样例
输入样例 #1
2
YSLTRIQXSHTQTR
1 2
3
输出样例 #1
FULLSPEEDAHEAD
说明
n<=1000