2603. Cipher

单点时限: 3.0 sec

内存限制: 256 MB

The Playfair cipher or Playfair square is a manual symmetric encryption technique and was the first literal digraph

substitution cipher. The technique encrypts pairs of letters (digraphs), instead of single letters as in the simple

substitution cipher and rather more complex Vigenère cipher systems then in use. The Playfair is thus significantly harder

to break since the frequency analysis used for simple substitution ciphers does not work with it. Frequency analysis can still

be undertaken, but on the 600 possible digraphs rather than the 26 possible monographs. The frequency analysis of digraphs

is possible, but considerably more difficult and it generally requires a much larger ciphertext in order to be useful.

Despite its invention by Wheatstone, it became known as the Playfair cipher after Lord Playfair, who heavily promoted its

use. The first recorded description of the Playfair cipher was in a document signed by Wheatstone on 26 March 1854.It was

used for tactical purposes by British forces in the Second Boer War and in World War I and for the same purpose by the

Australians and Germans during World War II. This was because Playfair is reasonably fast to use and requires no special

equipment. A typical scenario for Playfair use would be to protect important but non-critical secrets during actual combat.

By the time the enemy cryptanalysts could break the message, the information was useless to them.

However Playfair is no longer used by military forces because of the advent of digital encryption devices. Playfair is now

regarded as insecure for any purpose because modern hand-held computers could easily break the cipher within seconds.

The Playfair cipher uses a 5 by 5 table containing a keyword or phrase. Memorization of the keyword and some simple

rules was all that was required to create the 5 by 5 table and use the cipher.

To generate the key table, one would first

fill in the spaces in the table with the letters of the keyword (dropping any duplicate letters), then fill the remaining

spaces with the rest of the letters of the alphabet in order (combine ‘I’ and ‘J’ to reduce the alphabet to fit).

To encrypt a message, one would change the lowercase to uppercase, break the message into digraphs (groups of 2 letters

and throw away spaces) such that, for example, “Hello World” becomes “HE LL OW OR LD”, and map them out on the key table.

The two letters of the digraph look like the corners of a rectangle in the key

table. Note the relative position of the corners of this rectangle. Then apply the following rules, in order, to each pair

of letters in the plaintext:

If both letters are the same (or only one letter is left), add an ‘X’ after the first letter. Encrypt the new pair and continue.

If the letters appear on the same row of your table, replace them with the letters to their immediate right respectively

(wrapping around to the left side of the row if a letter in the original pair was on the right side of the row).

If the letters appear on the same column of your table, replace them with the letters immediately below respectively

(wrapping around to the top side of the column if a letter in the original pair was on the bottom side of the column).

If the letters are not on the same row or column, replace them with the letters on the same row respectively but at the

other pair of corners of the rectangle defined by the original pair.

The order is important-the first encrypted letter of the pair is the one that lies on the same row as the first plaintext letter.

输入格式

The input consists of multiple test cases. The first line of input contains an integer T, which is the number of test cases.

Each test case containing two lines: the key and the message.

The length of the key and the message will

not exceed 500.

You may assume that the message does not contain substring such as “XX”, “IJ” , “JI”, and does not end with “X”.

输出格式

For each test case, print one line containing the encrypted message.

样例

Input
3
Charles
Meet me at the Hammersmith Bridge tonight
Death
Laboulaye Lady
to go to jail together
to stand up for freedom together
Output
GDVBYTBCQYPRSCRKYKDCDIMPASHMEMDOUGKIRP
MEIKQOTXCQTEZY
OGNITUMPQDIEKHHWDPADOGOHGLHB
Hint1.
Using "Death" as the key, the table becomes:
D E A T H
B C F G I / J
K L M N O
P Q R S U
V W X Y Z
NOTE that 'J' is in same place with 'I'!
Encrypting the message "Laboulaye Lady":
LA BO UL AY EL AD YX
The pair LA forms a rectangle, replace it with ME.
The pair BO forms a rectangle, replace it with IK.
The pair UL forms a rectangle, replace it with QO.
The pair AY forms a rectangle, replace it with TX.
The pair EL in a column, replace it with CQ.
The pair AD in a row, replace it with TE.
The pair YX in a row, replace it with ZY.
ME IK QO TX CQ TE ZY
Thus the message becomes "MEIKQOTXCQTEZY".
2.
Assume one wants to encrypt the digraph OR. There are three general cases:
1)
* * * * *
* O Y R Z
* * * * *
* * * * *
* * * * *
Hence, OR -> YZ
2)
* * O * *
* * B * *
* * * * *
* * R * *
* * Y * *
Hence, OR -> BY
3)
Z * * O *
* * * * *
* * * * *
R * * X *
* * * * *
Hence, OR -> ZX

0 人解决,1 人已尝试。

0 份提交通过,共有 1 份提交。

9.9 EMB 奖励。

创建: 11 年,8 月前.

修改: 3 年,3 月前.

最后提交: 11 年,7 月前.

来源: The 4th Baidu Cup Central China Invitational Programming Contest

题目标签