Rail fence cipher
The rail fence cipher (also called a zigzag cipher) is a classical type of transposition cipher. It derives its name from the manner in which encryption is performed. Encryption. In the rail fence cipher, the plaintext is written downwards diagonally on successive "rails" of an imaginary fence, then moving up when the bottom rail is reached, down again when the top rail is reached, and so on until the whole plaintext is written out. The ciphertext is then read off in rows. For example, to encrypt the message 'WE ARE DISCOVERED. RUN AT ONCE.' with 3 "rails , write the text as: (Note that spaces and punctuation are omitted.) Then read off the text horizontally to get the ciphertext: Decryption. Let formula_1 be the number of rails used during encryption. Observe that as the plaintext is written, the sequence of each letter's vertical position on the rails varies up and down in a repeating cycle. In the above example (where formula_2) the vertical position repeats with a period of 4. In general the sequence repeats with a period of formula_3. Let formula_4 be the length of the string to be decrypted. Suppose for a moment that formula_4 	Rail fence cipher
27081739	is a multiple of formula_3 and let formula_7. One begins by splitting the ciphertext into strings such that the length of the first and last string is formula_8 and the length of each intermediate string is formula_9. For the above example with formula_10, we have formula_11, so we split the ciphertext as follows: Write each string on a separate line with spaces after each letter in the first and last line: Then one can read off the plaintext down the first column, diagonally up, down the next column, and so on. If formula_4 is not a multiple of formula_3, the 	Rail fence cipher
27081740	determination of how to split up the ciphertext is slightly more complicated than as described above, but the basic approach is the same. Alternatively, for simplicity in decrypting, one can pad the plaintext with extra letters to make its length a multiple of formula_3. If the ciphertext has not been padded, but you either know or are willing to brute-force the number of rails used, you can decrypt it using the following steps. As above, let formula_4 be the length of the string to be decrypted and let formula_1 be the number of rails used during encryption. We will 	Rail fence cipher
27081741	add two variables, formula_17 and formula_18, where formula_19 = the number of diagonals in the decrypted Rail Fence, and formula_18 = the number of empty spaces in the last diagonal. formula_21 Next solve for formula_17 and formula_18 algebraically, where both values are the smallest number possible. This is easily done by incrementing formula_17 by 1 until the denominator is larger than formula_4, and then simply solving for formula_18. Consider the example cipher, modified to use 6 rails instead of 3. The resulting cipher text is: We know that formula_10, and if we use formula_28 we can solve the equation above	Rail fence cipher
27081742	. formula_29 formula_30 Simplify the fraction. formula_31 Solve for formula_17 formula_33 Solve for formula_18 We now have formula_28, formula_36, and formula_37. Or, 6 rails, 5 diagonals (4+1), and 2 empty spaces at the end. By blocking out the empty spaces at the end of the last diagonal, we can simply fill in the Rail Fence line by line using the ciphertext. Cryptanalysis. The cipher's key is formula_1, the number of rails. If formula_1 is known, the ciphertext can be decrypted by using the above algorithm. Values of formula_1 equal to or greater than formula_4, the length of the 	Rail fence cipher
27081743	ciphertext, are not usable, since then the ciphertext is the same as the plaintext. Therefore the number of usable keys is low, allowing the brute-force attack of trying all possible keys. As a result, the rail-fence cipher is considered weak. Zigzag cipher. The term zigzag cipher may refer to the rail fence cipher as described above. However, it may also refer to a different type of cipher described by Fletcher Pratt in Secret and Urgent". It is "written by ruling a sheet of paper in vertical columns, with a letter at the head of each column. A dot  is made for each letter of the message in the proper column, reading from top to bottom of the sheet. The letters at the head of the columns are then cut off, the ruling erased and the message of dots sent along to the recipient, who, knowing the width of the columns and the arrangement of the letters at the top, reconstitutes the diagram and reads what it has to say."