loading...

re: Daily Challenge #42 - Caesar Cipher VIEW POST

FULL DISCUSSION
 

I’m learning Erlang and I love it.

My solution for cracking the message tries all keys, performs frequency analysis on each result, and sorts the candidates by closeness to the frequencies of letters in the English language.

-module( caesar ).
-compile( export_all ).
-export( [ caesar/2 ] ).

-include_lib("eunit/include/eunit.hrl").

shift_char( Char, Key ) when Char >= $a, Char =< $z ->
    $a + ( Char - $a + Key ) rem 26;
shift_char( Char, Key ) when Char >= $A, Char =< $Z ->
    $A + ( Char - $A + Key ) rem 26;
shift_char( Char, _ ) ->
    Char.

caesar( Message, Key ) when is_integer( Key ), Key > 0, Key < 26 ->
    lists:map( fun( C ) -> shift_char( C, Key ) end, Message ).

shift_char_test_() -> [
    ?_assertEqual( $b, shift_char( $a, 1 ) ),
    ?_assertEqual( $f, shift_char( $a, 5 ) ),
    ?_assertEqual( $a, shift_char( $z, 1 ) ),
    ?_assertEqual( $z, shift_char( $r, 8 ) ),
    ?_assertEqual( $b, shift_char( $r, 10 ) ),
    ?_assertEqual( $M, shift_char( $K, 2 ) ),
    ?_assertEqual( $D, shift_char( $W, 7 ) )
].

casear_test_() -> [
    ?_assertEqual( "b", caesar( "a", 1 ) ),
    ?_assertEqual( "e", caesar( "a", 4 ) ),
    ?_assertEqual( "a", caesar( "z", 1 ) ),
    ?_assertEqual( "efgfoe uif fbtu xbmm pg uif dbtumf", caesar( "defend the east wall of the castle", 1 ) ),
    ?_assertEqual( "dwwdfn iurp wkh zrrgv dw gdzq", caesar( "attack from the woods at dawn", 3 ) ),
    ?_assertEqual( "Dro aesmu, lbygx pyh TEWZON yfob dro vkji nyq!", caesar( "The quick, brown fox JUMPED over the lazy dog!", 10 ) )
].

% calculate the frequencies of the letters in the message
freqs( Message ) ->
    freqs( string:lowercase( Message ), #{}, 0 ).
freqs( [ C | Rest ], Freqs, Count ) when C >= $a, C =< $z ->
    NewFreqs = maps:put( C, maps:get( C, Freqs, 0 ) + 1, Freqs ),
    freqs( Rest, NewFreqs, Count + 1 );
freqs( [ _ | Rest ], Freqs, Count ) ->
    freqs( Rest, Freqs, Count );
freqs( [], Freqs, Count ) ->
    maps:map( fun( _C, Freq ) -> 100 * Freq / Count end, Freqs ).

% calculate the distance between the frequency of a letter in the message
% and the frequency of the same letter in the English language
freq_distance( C, Freq ) ->
    EnglishFreq = maps:get( C, english_frequencies() ),
    math:pow( EnglishFreq - Freq, 2 ).

% calculate the distance between frequencies in the message and frequencies in the English language
distance( Freqs ) ->
    lists:foldr(
        fun( { _, Dist }, Acc ) -> Acc + Dist end,
        0,
        maps:to_list(
            maps:map( fun freq_distance/2, Freqs )
        )
    ).

% try all keys and sort them starting with the decrypted message that has the least distance
% with the frequencies of the English language
crack( Message ) ->
    Keys = lists:seq( 1, 25 ),
    Candidates = lists:map( fun( Key ) -> { 26 - Key, caesar( Message, Key ) } end, Keys ),
    Freqs = lists:map( fun( { Key, Msg } ) -> { Key, Msg, freqs( Msg ) } end, Candidates ),
    Distances = lists:map( fun( { Key, Msg, Frq } ) -> { Key, Msg, distance( Frq ) } end, Freqs ),
    _BestKeys = lists:sort( fun( { _, _, Dist1 }, { _, _, Dist2 } ) -> ( Dist1 - Dist2 ) =< 0 end, Distances ).

% frequencies of the letters in the English language, from
% http://pi.math.cornell.edu/~mec/2003-2004/cryptography/subs/frequencies.html
english_frequencies() ->
    _Frequencies = #{
        $e => 12.02, $t => 9.10, $a => 8.12, $o => 7.68, $i => 7.31, $n => 6.95, $s => 6.28,
        $r => 6.02, $h => 5.92, $d => 4.32, $l => 3.98, $u => 2.88, $c => 2.71, $m => 2.61,
        $f => 2.30, $y => 2.11, $w => 2.09, $g => 2.03, $p => 1.82, $b => 1.49, $v => 1.11,
        $k => 0.69, $x => 0.17, $q => 0.11, $j => 0.10, $z => 0.07
    }.

To try:

% erl
1> c(caesar).
{ok,caesar}

2> caesar:test().
  All 13 tests passed.
ok

3> caesar:caesar( "attack from the woods at dawn", 3 ).
"dwwdfn iurp wkh zrrgv dw gdzq"

4> caesar:crack("efgfoe uif fbtu xbmm pg uif dbtumf" ).
[{1,"defend the east wall of the castle",232.3872551020408},
 {12,"stutcs iwt tphi lpaa du iwt rphiat",339.90096938775514},
 {13,"rstsbr hvs sogh kozz ct hvs qoghzs",514.9585122448979},
 ...

5> caesar:crack("dwwdfn iurp wkh zrrgv dw gdzq").
[{3,"attack from the woods at dawn",309.13214444444446},
 {18,"leelnv qczx esp hzzod le olhy",409.1672777777778},
 {25,"exxego jvsq xli asshw ex hear",415.19877777777776},

6> caesar:crack("Dro aesmu, lbygx pyh TEWZON yfob dro vkji nyq!").
[{10,"The quick, brown fox JUMPED over the lazy dog!",
  142.00382345679012},
 {20,"Jxu gkysa, rhemd ven ZKCFUT eluh jxu bqpo tew!",
  281.83945679012345},
 {21,"Iwt fjxrz, qgdlc udm YJBETS dktg iwt apon sdv!",
  307.0069345679012},
 

Of course, instead of decrypting the message 25 times, I should perform frequency analysis, shift the keys of the map 25 times, take the three shortest distances and then decrypt the message with the corresponding keys. I’ll update my solution later.

code of conduct - report abuse