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