Cryptanalyzing Columnar Transposition with Language Modeling
============================================================
Solution by Michael Lee
Note: Use the print program in this directory cause the one in hwk1 is foomt.
Use the log-odds scoring program on the ciphertext for widths from 4 to 8.
The table for the most likely width appears below:
================================================================================================
Table for N=6
0 1 2 3 4 5
------------------------------------------------------------------------------------------------
0 0.790263(0) -0.939454(3) -0.85621(5) -0.50539(3) -0.733563(4)
1 -0.594954(3) -0.865472(6) 0.729744(0) -0.921598(5) -0.763808(7)
2 -0.828555(2) -0.935992(5) -1.0269(4) 0.970614(0) -0.588115(4)
3 -0.801126(5) -0.500111(4) -0.852619(2) -0.472969(3) 0.833118(0)
4 0.673511(0) -0.653523(3) -0.406319(1) -0.712047(2) -0.868593(4)
5 -0.797026(6) -0.735042(3) 0.765673(0) -0.425304(3) -0.628438(3)
================================================================================================
For each row from 0 to 5, we look across for the best score (hopefully with no
impossible pairs). That column is the one that goes to the right of the column
under consideration.
For example, what should go to the right of column 0? There is a positive value
in column 1, and no impossible pairs there. Every other column has a negative
value, so it is likely that column 1 goes to the right of column 0.
===================
1 to the right of 0
3 to the right of 1
4 to the right of 2
5 to the right of 3
0 to the right of 4
2 to the right of 5
===================
From this we know tau inverse, down to a cyclic shift. If one of the lines in
the table above were missing, there would be a column that has no neighbot to
the right, and we would know the exact permutation. As it is, we have narrowed
it down to N=6 possibilities.
====================
tau^-1=(0,1,3,5,2,4)
====================
Now there are six possibilities which must be tried: one for each of the cyclic
shifts.
To find tau from tau inverse, we take each n=[0..5] and find the column in tau
inverse where that n appears.
So 0 appears in tau^-1 in position 0 and 5 appears in tau^-1 in position 3, etc.
===========================
tau^-1 tau
----------- -----------
0,1,3,5,2,4 0,1,4,2,5,3
1,3,5,2,4,0 5,0,3,1,4,2
3,5,2,4,0,1 4,5,2,0,3,1
5,2,4,0,1,3 3,4,1,5,2,0
2,4,0,1,3,5 2,3,0,4,1,5
4,0,1,3,5,2 1,2,5,3,0,4
===========================
We have our program try all N possibilities. Only one of the 6 produces English
text, so we know the permutation:
===========
5 0 3 1 4 2
===========
Plaintext follows:
================================================================================
Computer_science_has_undergone_a_dramatic_period_of_growth_in_the_last_decade._T
oday,_computer_technology_touches_our_lives_in_many_ways,_from_24-hour_banktelle
rs_to_satellite_communications_systems._The_computer_science_program_at_UCSB_cov
ers_this_exciting_multi-faceted_discipline._Completion_of_this_program_results_i
n_a_broad_body_of_skills_and_knowledge_which_can_be_used_in_a_wide_range_of_area
s_of_scientific_study,_business,_and_industry._This_brochure_will_explain_some_o
f_the_more_important_features_of_the_computer_science_program._Of_course,_some_q
uestions_may_not_be_answered_here._For_additional_information_or_counseling,_ple
ase_drop_by_the_Department_of_Computer_Science_in_2111_Engineering_(961-4321)_or
_the_student_advising_office_in_2163_Engineering_(961-3508)._Most_questions_can_
be_answered_by_the_staff_on_a_drop-in_basis,_although_some_will_be_referred_to_t
he_faculty_member_best_qualified_to_answer_them.
================================================================================
Formatting:
12345678901234567890123456789012345678901234567890123456789012345678901234567890