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