The four-square cipher is an encryption technique that was invented by the famous French cryptographer Félix Marie Delastelle¹ (1840–1902). The technique uses four $$5 \times 5$$ grids arranged in a square. Each of these grids contains all letters of the alphabet just once, except for the fact that the letters I and J are both put in the same location to reduce the alphabet to fit. While encoding and decoding messages, the letter J is considered to be equal to the letter I. The upper-left and lower-right grids are the plaintext squares and each contain the standard alphabet when read from left to right, and from top to bottom. The upper-right and lower-left squares are the ciphertext squares and contain a permutation of the standard alphabet when read from left to right, and from top to bottom.

The ciphertext squares are generated by first filling in the spaces in the grid from left to right, and from top to bottom with the letters of a keyword. Duplicate letters are dropped in the process, so that each letter is used only once. The remaining spaces are then filled with the rest of the letters of the alphabet in order (the letters that weren't used yet while filling the grid). Both during filling in the grid with letters of the keyword and the remaining letters of the alphabet, the letter J is considered to be equal to the letter I. The four-square algorithm allows for two separate keys, that are used respectively to fill in the upper-right and lower-left squares.

As an example, here are the four-square matrices for the keywords EXAMPLE and KEYWORD. The plaintext squares are in lowercase and the ciphertext squares are in uppercase to make this example visually more clear.

a b c d e     E X A M P
f g h i k     L B C D F
l m n o p     G H I K N
q r s t u     O Q R S T
v w x y z     U V W Y Z

K E Y W O     a b c d e
R D A B C     f g h i k
F G H I L     l m n o p
M N P Q S     q r s t u
T U V X Z     v w x y z

To encrypt a given message, one would follow these steps:

1. Split the message into digraphs (pairs of successive letters). In doing so, ignore characters in the message that are no letters (punctuation, whitespace, …). If the message contains an odd number of letters, append an extra letter Q at the end of the message.are ignored. This way, the message HELLO WORLD! is split into digraphs in the following way:

   HE LL OW OR LD

2. Find the first letter in the original digraph in the upper-left plaintext grid.

   a b c d e     E X A M P
   f g h i k     L B C D F
   l m n o p     G H I K N
   q r s t u     O Q R S T
   v w x y z     U V W Y Z
   
   K E Y W O     a b c d e
   R D A B C     f g h i k
   F G H I L     l m n o p
   M N P Q S     q r s t u
   T U V X Z     v w x y z

3. Find the second letter in the original digraph in the lower-right plaintext grid.

   a b c d e     E X A M P
   f g h i k     L B C D F
   l m n o p     G H I K N
   q r s t u     O Q R S T
   v w x y z     U V W Y Z
   
   K E Y W O     a b c d e
   R D A B C     f g h i k
   F G H I L     l m n o p
   M N P Q S     q r s t u
   T U V X Z     v w x y z

4. The first letter of the encrypted digraph is in the same row as the first plaintext letter and the same column as the second plaintext letter. It is therefore in the upper-right ciphertext square.

   a b c d e     E X A M P
   f g h i k     L B C D F
   l m n o p     G H I K N
   q r s t u     O Q R S T
   v w x y z     U V W Y Z
   
   K E Y W O     a b c d e
   R D A B C     f g h i k
   F G H I L     l m n o p
   M N P Q S     q r s t u
   T U V X Z     v w x y z

5. The second letter of the encrypted digraph is in the same row as the second plaintext letter and the same column as the first plaintext letter. It is therefore in the lower-left ciphertext square.

   a b c d e     E X A M P
   f g h i k     L B C D F
   l m n o p     G H I K N
   q r s t u     O Q R S T
   v w x y z     U V W Y Z
   
   K E Y W O     a b c d e
   R D A B C     f g h i k
   F G H I L     l m n o p
   M N P Q S     q r s t u
   T U V X Z     v w x y z

Using the four-square example given above, we can encrypt the plaintext message "Help me Obi-Wan Kenobi" as:

he lp me ob iw an ke no bi
FE MB ML HU DY RB FT KF BO

Here is the four-square written out again but blanking all of the values that aren't used for encrypting the first digraph he into FY.

- - - - -     - - - - -
- - h - -     - - - - F
- - - - -     - - - - -
- - - - -     - - - - -
- - - - -     - - - - -

- - Y - -     - - - - e
- - - - -     - - - - -
- - - - -     - - - - -
- - - - -     - - - - -
- - - - -     - - - - -

As can be seen clearly, the method of encryption simply involves finding the other two corners of a rectangle defined by the two letters in the plaintext digraph. The encrypted digraph is simply the letters at the other two corners, with the upper-right letter coming first.

Decryption works the same way, but in reverse. The ciphertext digraph is split with the first character going into the upper-right grid and the second character going into the lower-left grid. The other corners of the rectangle are then located. These represent the plaintext digraph with the upper-left grid component coming first.

Assignment

Define a class Square that can be used to represent the $$5 \times 5$$ grids used in the four-square cipher. The rows of the grid are index top to bottom starting from zero, and the columns are index left to right starting from zero. The class Square must at least support the following methods:

• An initialization method to which a keyword can be passed. The spaces in the grid must be filled from left to right, and from top to bottom, first with the letters of the given keyword (without duplicates), then with the remaining letters of the alphabet. In case no keyword is passed to the initialization method, the grid only needs to be filled in with the letters of the alphabet.

• A method __str__ that returns a string representation of the grid. In this string representation, all letters on a row of the grid must be separated using a single space. All letters should be displayed in uppercase.

• A method letter that takes the row and column index of a position in the grid. The method must return the uppercase letter the is found at that position in the grid. In case the given row and column index does not indicate a position inside the grid, the method must raise an AssertionError with the message invalid position.

• A method position that takes a letter. The method must return a tuple containing the row and column index of the position where the given letter is found in the grid. No distinction should be made between uppercase and lowercase letters. In case no letter was passed, the method must raise an AssertionError with the message invalid letter.

Use the class Square to define a class FourSquare that can be used to encode and decode messages according to the four-square cipher defined by two given keywords. While encoding or decoding messages, no distinction should be made between uppercase and lowercase letters, and the letter J should always be treated equal to the letter I. All letters in encoded or decoded message should be represented as uppercase, and the letter I/J is represented by the letter I. The class FourSquare must support at least the following methods:

• An initialization method that takes two keywords. These are the keywords that are used to respectively fill in the upper-right and lower-left ciphertext squares that are used to encode and decode digraphs.

• A method encode that takes a string argument. The method must return the string that results from encrypting the given string according to the four-square cipher with the two given keywords.

• A method decode that takes a string argument. The method must return the string that results from decrypting the given string according to the four-square cipher with the two given keywords. In case an extra letter Q was appended to the original message during encryption, the method should not remove this letter from the decrypted message.

Example

>>> square = Square()
>>> print(square)
A B C D E
F G H I K
L M N O P
Q R S T U
V W X Y Z
>>> square.letter(3, 2)
'S'
>>> square.letter(7, 1)
Traceback (most recent call last):
AssertionError: invalid position
>>> square.position('A')
(0, 0)
>>> square.position('?')
Traceback (most recent call last):
AssertionError: invalid letter

>>> square = Square('EXAMPLE')
>>> print(square)
E X A M P
L B C D F
G H I K N
O Q R S T
U V W Y Z
>>> square.letter(3, 2)
'R'
>>> square.position('A')
(0, 2)

>>> square = Square('keyword')
>>> print(square)
K E Y W O
R D A B C
F G H I L
M N P Q S
T U V X Z
>>> square.letter(3, 2)
'P'
>>> square.position('a')
(1, 2)

>>> cipher = FourSquare('EXAMPLE', 'keyword')
>>> cipher.encode('Help me Obi-Wan Kenobi!')
'FYNFNEHWBXAFFOKHMD'
>>> cipher.decode('FYNFNEHWBXAFFOKHMD')
'HELPMEOBIWANKENOBI'