{"id":676,"date":"2008-08-24T19:10:11","date_gmt":"2008-08-24T19:10:11","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2008\/08\/24\/transposition-ciphers\/"},"modified":"2008-08-24T19:10:11","modified_gmt":"2008-08-24T19:10:11","slug":"transposition-ciphers","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2008\/08\/24\/transposition-ciphers\/","title":{"rendered":"Transposition Ciphers"},"content":{"rendered":"

The second major family of encryption techniques is called transposition ciphers<\/em>. I find transposition ciphers to be
\nrather dull; in their pure form, they’re very simple, and not very difficult
\nto crack, even without computers. But some of the most sophisticated
\nmodern ciphers can be looked at as a sort of strange combination of
\nsubstitution and transposition, so it’s worth looking at.<\/p>\n

A transposition cipher doesn’t change the characters in the plain-text when it generates the cipher-text – it just re-arranges them. It applies some kind of permutation function to the text to produce a re-arrangement, which can be reversed if you know the secret to the the permutation.<\/p>\n

<\/p>\n

For example, the most classic version is called the rail fence cipher. In a rail fence cipher, you pick a number of rows, and then write your text as a zig-zag across those rows. For example, here’s the words “FOR EXAMPLE”
\narranged in the rail-fence pattern with three rows:<\/p>\n

\nF   X   L\nO E A P E\nR   M\n<\/pre>\n
 Now, the ciphertext is what you get by reading the rows straight across, left to right: “FXLOEAPEPM”.<\/p>\n
 Much the same flavor, but a bit more complicated is the column
\ntransposition cipher: arrange the letters into a rectangular grid,
\nand re-arrange the columns according to some secret key. Then read
\nthe characters off the resulting rows right to left.<\/p>\n
 For an example, we’ll take the sentence “FOR EXAMPLE THE MOST CLASSIC VERSION IS CALLED THE RAIL FENCE CIPHER”. We’ll run it through four
\nrows. For simplicity, we generally pad out the end to fill in the rectangle. The padding should attempt to follow the frequency distribution of letters
\nin the plaintext. Here it is, with the end padded using the characters “CRA”.<\/p>\n
\nFXLETSVISLHINIR\nOAEMCSEOCEELCPC\nRMTOLIRNADRFEHR\nEPHSACSILTAECEA\n<\/pre>\n
 Now, you take the columns, and re-arrange them, according to some pattern. For example, there are fifteen columns here, and we can use
\na five-column permutation, repeated on three groups of five. For example,
\n(2,1,4,5,3):<\/p>\n
\nXFETL VSSLI IHIRN\nAOMCE ESCEO LEPCC\nMROLT RIADN FRHRE\nPESAH SCLTI EAEAC\n<\/pre>\n
 Now, we read across, and get the following, with spaces separating groups of four characters for ease of reading (the convenience spacing is deliberately different than the cipher size): “XFET LVSS LIIH IRNA OMCE ESCE OLEP CCMR OLTR IADN FRHR EPES AHSC LTIE AEAC”.<\/p>\n
 This kind of column transposition cipher can easily be based on
\na password. The idea is that you use the password both the
\ndecide the size of the grid to be used for the transposition, and
\nthe order of column transposition. For example, if we used the password
\n“chowder”, we’d use a grid with width 7; and we’d define the transposition
\nby the alphabetic order of the characters in the password: 1457236.<\/p>\n
 So let’s do that to our example. It’s got 58 characters,
\nand we want 7 columns, so we’ll use 9 rows, and pad the end. Here’s
\nthe initial grid, before the transposition.<\/p>\n
\n1 2 3 4 5 6 7\nF E L S L L H\nO T A I E F E\nR H S O D E R\nE E S N T N C\nX M I I H C C\nA O C S E E Q\nM S V C R C U\nP T E A A I P\nL C R L I P E\n<\/pre>\n
Now, we transpose the grid, putting in the order (1, 4, 5, 7, 2, 3, 6):<\/p>\n
\n1 4 5 7 2 3 6\nF S L H E L L\nO I E E T A F\nR O D R H S E\nE N T C E S N\nX I H C M I C\nA S E Q O C E\nM C R U S V C\nP A A P T E I\nL L I E C R P\n<\/pre>\n
 Reading that off, we get “FSLH ELLO IEET AFRO DRHS EENT CESN XIHC MICA SEQO CEMC RUSV CPAA PCEI LLIE CRP”.<\/p>\n
 Decoding is almost the same. We’ll take our ciphertext, and write it out
\nin rows the width of the password:<\/p>\n
\n1 2 3 4 5 6 7\nF S L H E L L\nO I E E T A F\nR O D R H S E\nE N T C E S N\nX I H C M I C\nA S E Q O C E\nM C R U S V C\nP A A P T E I\nL L I E C R P\n<\/pre>\n
 Now, we take our password, and create the reverse permutation. Before,
\nwe mapped column 1 clear to column 1 cipher, column 4 clear to column 2 cipher, 5 to 3, 7 to 4, 2 to 5, 3 to 6, and 6 to 7.  So
\nthe reverse is (1:1, 2:4, 3:5, 4:7, 5:2, 6:3, 7:6); or, in
\nthe same form as the encryption mapping, (1, 5, 6, 2, 3, 7, 6).<\/p>\n
 You can get even more clever, and use a route cipher: in a route cipher, instead of uniformly re-arranging the rows, you follow a particular fixed path through the text. If you make a sufficiently complex path, it can
\nproduce a decent result.<\/p>\n
 The problem with all of the transposition ciphers is that they’re
\neasy to crack without knowing the secret. Just start permuting letters, looking for words – starting with the simplest words. For example,
\nyou expect most sentences to have “the” in them; so you look for “t”, “h”, and “e” – and try removing that as a word. Keep doing that, and you can get some simple words from the text. You can also look for relatively
\nunusual characters in the text, and see what words you can form using characters from the text. For example, the “X” in the our sample text is
\nvery unusual; there aren’t that many common words that include “X”. You can search to see if you can form one of them using the ciphertext characters. And once you’ve found a few words, you can start finding the pattern that
\nwill allow you to decode the entire text.<\/p>\n
 If it’s a column transposition cipher, you just need to start experimenting with different numbers of columns – eventually, you’ll start
\nseeing columns containing words!<\/p>\n
 Some of this can be worked around: for example, perform a column transposition, then do a row-transposition on the result. That breaks
\nfree of the “try different widths” problem. But still, for a typical short encrypted message, the permutation technique will get you the message in a reasonable amount of time.<\/p>\n
 What makes transposition ciphers interesting is that they work well in combination with other things. Take a rotating substitution cipher, and
\ndo transpositions both before and after the substitution. You’ve just made frequency analysis of anything larger than letters a lot<\/em> harder.<\/p>\n","protected":false},"excerpt":{"rendered":"
The second major family of encryption techniques is called transposition ciphers. I find transposition ciphers to be rather dull; in their pure form, they’re very simple, and not very difficult to crack, even without computers. But some of the most sophisticated modern ciphers can be looked at as a sort of strange combination of substitution […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[84],"tags":[],"class_list":["post-676","post","type-post","status-publish","format-standard","hentry","category-encryption"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-aU","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/676","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=676"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/676\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=676"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=676"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=676"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}