Bifid cipher
The Bifid cipher is a fractionating transposition cipher invented by the French cryptographer Félix Delastelle in 1895, which combines elements of substitution and transposition to enhance security beyond simple monoalphabetic ciphers. It operates using a 5×5 Polybius square that maps the 25 letters of the alphabet (typically omitting 'J' or merging it with 'I') to row and column coordinates from 1 to 5; each plaintext letter is converted to its pair of coordinates, which are written out in a sequence, transposed by reading them in a different order (often by grouping into a grid and reading column by column), and then recombined back into letters via the same square to produce the ciphertext. This fractionation process breaks letters into components, diffusing them across multiple positions for greater resistance to frequency analysis.[1] Delastelle first described the cipher in the French journal Revue du Génie civil under the title "cryptographie nouvelle," and it was later detailed in his 1902 book Traité élémentaire de cryptographie. As one of several manual ciphers developed by Delastelle—including the related Trifid and Four-square variants—the Bifid cipher gained popularity among amateur cryptographers in the early 20th century but was never adopted for official military or governmental use due to its vulnerability to systematic cryptanalysis. Its strength lies in the period length (typically 5 or 10) that determines grouping, allowing for variable complexity, though modern computational methods like simulated annealing can break it efficiently.[1] The cipher's design exemplifies early polygraphic techniques, where multiple letters influence each ciphertext symbol, making it a notable precursor to more advanced systems like the ADFGVX cipher used in World War I. Despite its historical limitations, the Bifid remains a pedagogical tool for understanding transposition and fractionation principles in cryptography education.[1]History
Invention and Inventor
The Bifid cipher was invented by Félix Delastelle, a French cryptographer active in the late 19th and early 20th centuries.[2] Delastelle first described the cipher in 1895 under the title "Cryptographie nouvelle" in the journal Revue du Génie civil, where he introduced it as a method combining substitution and transposition techniques based on the classical Polybius square.[1] This innovation marked an early application of fractionation in cryptography, splitting letters into components to obscure their individual identities.[3] Born on January 2, 1840, in Saint-Malo, France, and passing away on April 2, 1902, Delastelle pursued cryptography as an intellectual pursuit alongside his professional career in public administration, including roles in the French tobacco monopoly.[2] As an amateur in the field during an era dominated by military and diplomatic experts, he contributed significantly through self-study and experimentation, publishing his ideas in periodicals and later compiling them in works such as Traité élémentaire de cryptographie (1902).[1] Delastelle's primary motivation for developing the Bifid cipher was to create a system resistant to simple frequency analysis, a common cryptanalytic technique of the time that exploited letter occurrence patterns in monoalphabetic ciphers.[1] By fractionating the plaintext into rows and columns via the Polybius square and then rearranging them through transposition, the cipher diffused letter statistics across multiple positions, making it more secure for manual encryption.[3] This approach reflected his broader interest in polygraphic ciphers; he also invented the related Trifid and Four-square ciphers, which similarly employed multiple substitution tables and fractionation for enhanced security.[2]Historical Context and Usage
The Bifid cipher emerged in the late 19th and early 20th centuries, during the final era of manual cryptographic systems that relied on pen-and-paper methods, preceding the advent of mechanical encryption devices such as the Enigma machine patented in 1918.[4] Invented by French cryptographer Félix Delastelle and detailed in his 1902 book Traité Élémentaire de Cryptographie, it represented an advancement in polygraphic ciphers through its use of fractionation to achieve greater diffusion of plaintext letters compared to simpler digraphic substitutions like the Playfair cipher, which was employed by British forces during World War I.[4][5] While primarily adopted by amateur cryptographers for recreational and educational purposes, the Bifid cipher saw limited practical application in military and espionage contexts. During World War II, it was used in the Dutch resistance's Operation North Pole alongside ciphers such as double transposition and Playfair for secure tactical communications.[4] The cipher's popularity waned in the 1920s with the proliferation of rotor-based machines, which offered higher security and efficiency for large-scale communications, rendering manual polygraphics like the Bifid obsolete for professional use but retaining niche appeal among enthusiasts.[4]Description
Polybius Square Setup
The Bifid cipher relies on a Polybius square, a 5×5 grid that accommodates the 25 letters of the English alphabet by omitting the letter J or combining it with I. This grid structure, numbering rows and columns from 1 to 5, serves as the foundational mapping mechanism for converting plaintext letters into numerical coordinates during encryption.[1] Letters are placed in the grid in row-major order, starting from the top-left cell and proceeding left to right, top to bottom. To enhance security, a keyword is often used to rearrange the alphabet: duplicates are removed from the keyword, and the remaining letters of the alphabet (excluding J) are appended in standard order. For example, with the keyword "KEYWORD", the unique letters K, E, Y, W, O, R, D are placed first, followed by A, B, C, F, G, H, I, L, M, N, P, Q, S, T, U, V, X, Z. This results in the following grid:| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | K | E | Y | W | O |
| 2 | R | D | A | B | C |
| 3 | F | G | H | I | L |
| 4 | M | N | P | Q | S |
| 5 | T | U | V | X | Z |
Message Fractionation
In the Bifid cipher, the message fractionation step begins with preparing the plaintext by removing all spaces, punctuation, and converting it to uppercase letters, while typically combining I and J into a single position in the 5x5 grid to accommodate the 25-letter alphabet. This preparation ensures a clean sequence of letters for processing.[1] Each letter in the prepared plaintext is then converted to a pair of numerical coordinates—row and column numbers—based on its position in the Polybius square, a 5x5 grid filled with letters in a keyed order. The row numbers for all letters form a single horizontal layer (sequence), and the column numbers form a parallel layer directly alongside it, creating two numerical strings of equal length to the plaintext. This digraphic fractionation splits the identity of each letter across the layers, enhancing diffusion before further processing. The message is often processed according to a period length (commonly 5) in the subsequent transposition step.[1] To illustrate, consider the short plaintext "DEFEND" using the keyed Polybius square from the previous subsection:- Prepared message: DEFEND
- Coordinates: D(2,2), E(1,2), F(3,1), E(1,2), N(4,2), D(2,2)
- Row layer: 2 1 3 1 4 2
- Column layer: 2 2 1 2 2 2
Encryption Process
Coordinate Extraction and Layering
In the encryption process of the Bifid cipher, the first phase following message fractionation involves extracting the numerical coordinates from the Polybius square and organizing them into two distinct layers. Each plaintext letter, after being mapped to its row and column position in the 5x5 Polybius square (where I and J are typically merged), yields a pair of digits representing the row and column indices (numbered 1 through 5). These coordinates are then separated: all row numbers form the first (upper) layer as a sequence, and all column numbers form the second (lower) layer as a parallel sequence, each of equal length to the original message length n. This layering preserves the total count of digits (2n) while preparing them for subsequent transposition without altering their individual values.[6] The Polybius square used is a key-dependent 5x5 grid filled with a mixed alphabet derived from a keyword followed by the remaining letters (e.g., a standard square without keyword places A at row 1 column 1, B at 1-2, up to Z at 5-5). For fractionation, the plaintext is converted letter-by-letter into these coordinates; for instance, in a standard square, H corresponds to row 2 column 3, E to 1-5, L to 3-1, and so on. The row layer is written sequentially above the column layer, creating a two-row block of digits where the position aligns with the original message order. This structure facilitates the cipher's fractionation by treating each letter as two independent components, enhancing diffusion before recombination.[7] To illustrate, consider the plaintext "HELLO" using the standard Polybius square: \begin{array}{c|ccccc} & 1 & 2 & 3 & 4 & 5 \\ \hline 1 & \text{A} & \text{B} & \text{C} & \text{D} & \text{E} \\ 2 & \text{F} & \text{G} & \text{H} & \text{I/J} & \text{K} \\ 3 & \text{L} & \text{M} & \text{N} & \text{O} & \text{P} \\ 4 & \text{Q} & \text{R} & \text{S} & \text{T} & \text{U} \\ 5 & \text{V} & \text{W} & \text{X} & \text{Y} & \text{Z} \\ \end{array} The coordinates are: H (2,3), E (1,5), L (3,1), L (3,1), O (3,4). The row layer is thus 2 1 3 3 3, and the column layer is 3 5 1 1 4, both sequences of length 5 matching the message. No padding is added for this step, as the layers directly reflect the message length, ensuring balanced transposition in the next phase. This example demonstrates how the layering isolates positional data for mixing while maintaining traceability to the original fractionation.[8][7]Rearrangement and Recombination
After the coordinates have been extracted from the Polybius square and separated into distinct row and column layers, the encryption process advances to the rearrangement phase, where these layers are transposed to diffuse the information. The transposition involves concatenating the sequence of row numbers followed by the sequence of column numbers, forming a single mixed string of digits for the block (determined by the period length, often equal to the message length for short examples). This step disrupts the original pairing by blending digits from multiple letters, achieving the cipher's fractionation effect.[9] To recombine, the mixed digit string is divided into consecutive pairs, where the first digit of each pair represents the row and the second the column in the Polybius square. Each pair is then mapped back to the corresponding letter, producing the ciphertext block. This pairing ensures that the row coordinate for a ciphertext letter may come from one plaintext letter, while its column coordinate derives from another, further obscuring the original message. The process is typically applied block by block if a period is specified, with blocks concatenated to form the final ciphertext.[1] Consider a simple example using the standard 5x5 Polybius square (I/J combined) with no keyword, and plaintext "HELLO" (period 5):| Row/Col | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | A | B | C | D | E |
| 2 | F | G | H | I | K |
| 3 | L | M | N | O | P |
| 4 | Q | R | S | T | U |
| 5 | V | W | X | Y | Z |
Decryption Process
Layer Separation and Coordinate Recovery
To decrypt, first convert each ciphertext letter to its row and column coordinates using the Polybius square, then concatenate these coordinates in order: for each ciphertext letter, append its row number followed by its column number. This produces a sequence of 2m digits, where m is the message length (or block length if using a period). The first m digits of this sequence are the original row coordinates, and the last m digits are the original column coordinates.[1][10] Equivalently, this can be visualized by writing the 2m-digit sequence into a 2×m grid filled row by row—the top row will contain the original row coordinates, and the bottom row the original column coordinates—effectively isolating the fractionated components. This step reverses the diffusion from the encryption process.[1][10] For messages longer than the period length (typically 5 or 10), apply this process separately to each block of the ciphertext corresponding to the period. Proper execution requires knowing the period and the Polybius square used in encryption.[1] For example, consider the ciphertext corresponding to the plaintext "HELLO" (detailed in the next subsection), which yields the coordinate sequences 2,1,3,3,3 for rows and 3,5,1,1,4 for columns after separation.[1][10] These recovered coordinate sequences are then paired position by position and mapped back using the Polybius square to reconstruct the plaintext.[1][10]Message Reconstruction
After recovering the separated row and column coordinate sequences through the layer separation process, message reconstruction in the Bifid cipher involves pairing these sequences positionally to restore the original digrams and mapping them back to plaintext letters using the Polybius square.[10][1] The row sequence, consisting of the row indices (typically numbered 1 to 5) for each original plaintext letter, is aligned directly with the corresponding column sequence of column indices. For a message of length m, this produces m pairs (r_i, c_i), where r_i is the i-th element of the row sequence and c_i is the i-th element of the column sequence. Each pair (r_i, c_i) is then located in the Polybius square to identify the corresponding letter, effectively reversing the initial fractionation step.[10][1] The Polybius square is a 5×5 grid (25 positions for the 26-letter alphabet, excluding one letter or combining two), ensuring a unique mapping from each pair to a single letter. For instance, in a standard square without a keyword: \begin{array}{c|ccccc} & 1 & 2 & 3 & 4 & 5 \\ \hline 1 & \text{A} & \text{B} & \text{C} & \text{D} & \text{E} \\ 2 & \text{F} & \text{G} & \text{H} & \text{I/J} & \text{K} \\ 3 & \text{L} & \text{M} & \text{N} & \text{O} & \text{P} \\ 4 & \text{Q} & \text{R} & \text{S} & \text{T} & \text{U} \\ 5 & \text{V} & \text{W} & \text{X} & \text{Y} & \text{Z} \\ \end{array} I and J ambiguities are handled by merging them into a single position (typically row 2, column 4), with the encryption convention dictating the output: both input I and J map to this position, and during reconstruction, the position is conventionally rendered as I unless context requires J.[10][1] To verify, consider reconstructing "HELLO" from its separated coordinates using the above square (row sequence 2,1,3,3,3 and column sequence 3,5,1,1,4). Pairing positionally gives: (2,3) → H, (1,5) → E, (3,1) → L, (3,1) → L, (3,4) → O, yielding the original plaintext "HELLO". This process ensures the message is fully restored without loss, provided the square and period match those used in encryption. For the full example, the ciphertext for "HELLO" using this square and period 5 is "FNNVD"; applying the separation recovers the coordinates as shown.[10]Examples
Simple Encryption Example
To illustrate the encryption process of the Bifid cipher, consider the plaintext message "BIFID" using the standard 5×5 Polybius square, where the letters I and J share the same position (row 2, column 4), and the alphabet is arranged sequentially without a keyword. This example uses a period of 5 (equal to message length) for simplicity. The Polybius square is set up as follows:| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | A | B | C | D | E |
| 2 | F | G | H | I/J | K |
| 3 | L | M | N | O | P |
| 4 | Q | R | S | T | U |
| 5 | V | W | X | Y | Z |
- B: row 1, column 2
- I: row 2, column 4
- F: row 2, column 1
- I: row 2, column 4
- D: row 1, column 4
and the column sequence: 2 4 1 4 4 Next, layer the sequences by concatenating the row numbers followed by the column numbers to form a single string of digits: 1222124144 Then, rearrange by dividing this string into consecutive pairs, treating the first digit of each pair as the new row and the second as the new column: 12, 22, 12, 41, 44 Finally, recombine by converting each pair back to a letter using the Polybius square:
- 12: row 1, column 2 = B
- 22: row 2, column 2 = G
- 12: row 1, column 2 = B
- 41: row 4, column 1 = Q
- 44: row 4, column 4 = T
Decryption Verification
To verify the decryption process and confirm its bidirectionality with the encryption steps, consider the ciphertext "BGBQT" generated in the simple encryption example using the standard Polybius square. The decryption reverses the process: first convert each ciphertext letter to its row and column coordinates, yielding the layered sequence 1222124144 (rows of ciphertext letters: 1 2 1 4 4; columns: 2 2 2 1 4; concatenated). For this 5-letter ciphertext, this yields 10 numbers. The inverse operation separates the first 5 numbers as the original row coordinates (1 2 2 2 1) and the last 5 as the original column coordinates (2 4 1 4 4), reversing the layering applied during encryption. Pairing them positionally—(1,2), (2,4), (2,1), (2,4), (1,4)—and mapping each pair back to the corresponding letters in the Polybius square yields the original plaintext "BIFID."| Position | Row Coordinate | Column Coordinate | Mapped Letter |
|---|---|---|---|
| 1 | 1 | 2 | B |
| 2 | 2 | 4 | I |
| 3 | 2 | 1 | F |
| 4 | 2 | 4 | I |
| 5 | 1 | 4 | D |