Cryptanalyzing Columnar Transposition by Cribbing ================================================= Solution by Michael Lee First searched for Cryptography_, August, _CRYPTO_, etc. Find that the width is most likely 7 Hints for chosing cribs: put spaces before and after, use more than one word, etc. If you think lengths of columns are equal: Print out the 7 columns (out of order) to see what might be a good crib. Here's an excerpt: ======= anta,_S rbar_Ba ENERa_G INFOAL_ TIONRMA EET__SH r_WoDea hop_rks ======= I chose _INFORMATION_ to analyze further because CAPS appear infrequently, but _Santa_Barbara_ would have worked too. The order in which subcribs appear is: ================================= 16 203 388 575 760 943 1132 FO R_ IT M NI _A ON ================================= The problem is that each column is the same length since 7 divides 1302. We can't use the technique in example 3, shown on p5 to eliminate possibilities. There are two techniques to try now: 1) The technique of eliminating possibilities in example 3 does not always eliminate everything. For example, if N=6, 4 possibilities might be eliminated. At that point, we would have to try two permutations. In this case, none are eliminated so we try all 7 by brute force. I just tried all 7 possible appearances of the crib by brute force. After trying several, it turns out that the way the crib appears in the plaintext is: ============= 0 1 2 3 4 5 6 _ I N F O R M A T I O N _ ============= Subcrib FO appears first in the ciphertext, so we know column 5 is the first value in tau (the transposition). Similarly, column 0 is the second value. Continue in this way to find the permutation: ============= 5 0 3 1 4 2 6 ============= 2) Second way: since the columns are of the same length, is to write out the columns side by side (even though you don't know the right order yet) and reverse the anagram (or permutation) to form English words at the top of the table. This descrambling will reveal the permutation. Feed the width and permutation into a program to print out the plaintext (this code can be reused in the next assignment). Plaintext follows: ================================================================================ Workshop_on_the_Theory_and_Application_of_Cryptographic_Techniques_University_of _California,_Santa_Barbara_GENERAL_INFORMATION_SHEET_Dear_Workshop_Participant:_ Welcome_to_the_University_of_California_at_Santa_Barbara!_We_are_happy_to_have_y ou_here_and_hope_that_you_will_find_this_workshop_both_fruitful_and_enjoyable._T he_following_information_may_prove_useful_during_your_stay:_GETTING_ABOUT:_If_yo u_don't_have_a_car,_but_would_like_to_see_something_of_Santa_Barbara,_you_can_ta ke_bus_ten_or_twenty four_from_the_East_Gate_of_the_campus_(close_to_the_Enginee ring_Building)_to_the_downtown_area._Timetables_are_available_at_the_Information _Desk._Alternately,_you_may_wish_to_wander_westward_on_foot,_to_the_student_resi dential_township_of_Isla_Vista,_which_adjoins_the_campus._Here_you_may_discover_ a_few_offbeat_shops_as_well_as_some_unusual_places_to_eat._You_can_also_rent_bic ycles_in_downtown_Santa_Barbara_(Open_Air_Bicycles_and_elsewhere),_and_use_the_n etwork_of_bikepaths_extending_all_the_way_from_Santa_Barbara_to_the_campus._Inci dentally,_please_remember_that_cyclists_have_priority_on_the_blue_painted_bikepa ths_on_campus,_and_have_been_known_to_take_full_advantage_of_this_fact._To_go_to _a_beach,_walk_out_to_the_East_Gate_and_turn_right._Goleta_Beach_is_just_a_moder ate_walk_down_the_bike ================================================================================ Formatting: 12345678901234567890123456789012345678901234567890123456789012345678901234567890