Daily Challenge #42 - Caesar Cipher

A Caesar cipher, or a shift cipher, is one of the most well known encryption techniques. It works by substituting the letters in the message with letters some fixed number of positions down the alphabet.

Your challenge is to write a function that will accept a string and a shift key. It will return the encrypted text. If something in the string is not in the alphabet (e.g. punctuation, spaces) leave it as is.

key: 1
plain: defend the east wall of the castle
cipher: efgfoe uif fbtu xbmm pg uif dbtumf

Bonus
Write a function that will crack the cipher without knowing the shift. The shift key can only be in range of [1, 26].

key: 3
cipher: dwwdfn iurp wkh zrrgv dw gdzq
plain: attack from the woods at dawn

I've used the brute-force method before (printing every possible key and manually searching for the right one). I can't wait to see other solutions to cracking this easy cipher.

Good luck!

---

Want to propose a challenge for a future post? Email [e-mail] with your suggestions!

Comments

[Adrian]

This is an interesting one. It can be easily solved if you implement first the modulo function in JavaScript.

I have an article about this:
dev.to/codeguppy/javascript-modulo...

[K.V.Harish]

My solution in js

const encode = (sentence, key) => sentence.split(' ')
                                          .map((word) => word.split('')
                                          .map((char) => (/[a-z]/i.test(char)) ? String.fromCharCode(char.charCodeAt(0) + key) : char)
                                          .join(''))
                                          .join(' ');

[Olivier “Ölbaum” Scherler]

My updated Erlang solution.

I now perform frequency analysis on the encrypted message, calculate the correlation with the frequencies of letters in the English language, and use the best N correlation values to decrypt the message.

-module( caesar ).
-export( [ caesar/2, crack/1, crack/2 ] ).

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

wrap( Char, Length ) when is_integer( Length ), Length > 0 ->
    ( Char rem Length + Length ) rem Length.

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

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

% 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 ).

freq_array( FreqMap ) ->
    lists:map(
        fun( X ) -> maps:get( $a + X - 1, FreqMap, 0 ) end,
        lists:seq( 1, 26 )
    ).

shift_fun( F, Tau, Period ) ->
    { F1, F2 } = lists:split( wrap( Tau, Period ), F ),
    F2 ++ F1.

correlation( F, G ) when length( F ) == length ( G ) ->
    Period = length( F ),
    lists:map(
        fun( Tau ) ->
            Z = lists:zip( F, shift_fun( G, Tau, Period ) ),
            lists:foldl( fun( { X, Y }, Acc ) -> X * Y / Period + Acc end, 0, Z )
        end,
        lists:seq( 0, Period - 1 )
    ).

% determine the most likely keys by correlation with the frequencies in the English language
crack( Message ) ->
    crack( Message, 1 ).

crack( Message, Attempts ) ->
    Freqs = freqs( Message ),
    Correlation = correlation( freq_array( english_frequencies() ), freq_array( Freqs ) ),
    Points = lists:zip( lists:seq( 0, 25 ), Correlation ),
    BestKeys = lists:reverse( lists:ukeysort( 2, Points ) ),
    lists:sublist(
        lists:map( fun( { Key, C } ) -> { Key, C, caesar( Message, - Key ) } end, BestKeys ), Attempts
    ).

% 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
    }.

wrap_test_() -> [
        ?_assertEqual(  0, wrap( 0, 26 ) ),
        ?_assertEqual(  3, wrap( 3, 26 ) ),
        ?_assertEqual(  0, wrap( 26, 26 ) ),
        ?_assertEqual( 25, wrap( -1, 26 ) ),
        ?_assertEqual( 10, wrap( -42, 26 ) ),
        ?_assertEqual( 25, wrap( 77, 26 ) ),
        ?_assertEqual( 5, wrap( 15, 10 ) ),
        ?_assertEqual( 0, wrap( 7, 1 ) )
    ].

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 ) ),
    ?_assertEqual( $a, shift_char( $a, 0 ) ),
    ?_assertEqual( $a, shift_char( $b, -1 ) ),
    ?_assertEqual( $c, shift_char( $a, 28 ) ),
    ?_assertEqual( $r, shift_char( $c, -11 ) )
].

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 ) ),
    ?_assertEqual( caesar( "defend the east wall of the castle", 15 ), caesar( "defend the east wall of the castle", -11 ) )
].

freqs_test_() -> [
    ?_assertEqual( #{ $a => 100.0 }, freqs( "a" ) ),
    ?_assertEqual( #{ $b => 50.0, $f => 50.0 }, freqs( "bf fb" ) ),
    ?_assertEqual( #{ $a => 50.0, $b => 30.0, $c => 20.0 }, freqs( "baac baba bacca cabba aa" ) )
].

freq_array_test_() -> [
    ?_assertEqual( 100.0, lists:nth( 1, freq_array( #{ $a => 100.0 } ) ) ),
    ?_assertEqual(  50.0, lists:nth( 2, freq_array( #{ $b => 50.0, $f => 50.0 } ) ) ),
    ?_assertEqual(  50.0, lists:nth( 6, freq_array( #{ $b => 50.0, $f => 50.0 } ) ) ),
    ?_assertEqual(  50.0, lists:nth( 1, freq_array( #{ $a => 50.0, $b => 30.0, $c => 20.0 } ) ) ),
    ?_assertEqual(  30.0, lists:nth( 2, freq_array( #{ $a => 50.0, $b => 30.0, $c => 20.0 } ) ) ),
    ?_assertEqual(  20.0, lists:nth( 3, freq_array( #{ $a => 50.0, $b => 30.0, $c => 20.0 } ) ) )
].

correlation_test_() ->
    F = [ 0, 0, 2, 0, 0 ],
    G = [ 0, 1, 2, 3, 0 ],
    H = [ 1, 2, 1, 4, 6 ],
    Appr = fun( L ) -> lists:map( fun( X ) -> round( X * 100 ) end, L ) end,
    [
        ?_assertEqual( Appr( [ 4/5, 0.0, 0.0, 0.0, 0.0 ] ), Appr( correlation( F, F ) ) ),
        ?_assertEqual( Appr( [ 4/5, 6/5, 0.0, 0.0, 2/5 ] ), Appr( correlation( F, G ) ) ),
        ?_assertEqual( Appr( [ 2/5, 8/5, 12/5, 2/5, 4/5 ] ), Appr( correlation( F, H ) ) ),
        ?_assertEqual( Appr( [ 4/5, 2/5, 0.0, 0.0, 6/5 ] ), Appr( correlation( G, F ) ) ),
        ?_assertEqual( Appr( [ 14/5, 8/5, 3/5, 3/5, 8/5 ] ), Appr( correlation( G, G ) ) ),
        ?_assertEqual( Appr( [ 16/5, 27/5, 19/5, 14/5, 8/5 ] ), Appr( correlation( G, H ) ) ),
        ?_assertEqual( Appr( [ 2/5, 4/5, 2/5, 12/5, 8/5 ] ), Appr( correlation( H, F ) ) ),
        ?_assertEqual( Appr( [ 16/5, 8/5, 14/5, 19/5, 27/5 ] ), Appr( correlation( H, G ) ) ),
        ?_assertEqual( Appr( [ 58/5, 38/5, 31/5, 31/5, 38/5 ] ), Appr( correlation( H, H ) ) )
    ].

To try:

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

2> caesar:crack("efgfoe uif fbtu xbmm pg uif dbtumf").                                                               [{1,27.732142857142858, "defend the east wall of the castle"}]

3> caesar:crack("dwwdfn iurp wkh zrrgv dw gdzq").
[{3,24.07692307692308,"attack from the woods at dawn"}]

4> caesar:crack("Dro aesmu, lbygx pyh TEWZON yfob dro vkji nyq!", 3).
[{10,19.342948717948715, "The quick, brown fox JUMPED over the lazy dog!"},
 {0,16.821581196581192, "Dro aesmu, lbygx pyh TEWZON yfob dro vkji nyq!"},
 {20,16.384615384615383, "Jxu gkysa, rhemd ven ZKCFUT eluh jxu bqpo tew!"}]

[Héctor Pascual]

Python :

def cypher(m, key):
    m_cypher = ''
    for i in m:
        if i != ' ' and i != '.':
            m_cypher += chr(ord(i) + key)
        else:
            m_cypher += i
    return m_cypher

One line :

cypher = lambda m, key : ''.join(chr(ord(i) + key) if i != ' ' and i != '.' else i for i in m)

[Seiei Miyagi]

ruby <3

def decrypt_caesar_cipher(s, shift)
  decrypter = (?a..?z).cycle.lazy.then { @1.zip(@1.drop(26 - shift)).take(26).to_h }
  decrypter.default_proc = -> { @1.fetch(@2.downcase, nil)&.upcase || @2 }
  s.each_char.inject('') { @1 + decrypter[@2] }
end

def brute_force_caesar_cipher(s)
  0...26 |> to_h { [@1, decrypt_caesar_cipher(s, @1)] }
end

p decrypt_caesar_cipher('dwwdfn iurp wkh zrrgv dw gdzq', 3)
pp brute_force_caesar_cipher('dwwdfn iurp wkh zrrgv dw gdzq')

[LordApple]

C++

#include <iostream>

int main(){
    unsigned key = 1;
    std::string toEncrypt = "defend the east wall of the castle";

    if(key < 1 || key > 26){
        std::cout << "Key must be in range of 1-26" << std::endl;
        return 0;
    }

    for(char& c : toEncrypt){
        if(c < 'A' || c > 'z'){
            continue;
        }else if(c + key > 'z'){
            c = 'a' + (c + key) % 122 - 1;
            continue;
        }else if(c + key > 'Z' && c < 'a'){
            c = 'A' + (c + key) % 90 - 1;
            continue;
        }

        c += key;
    }
    std::cout << toEncrypt;
    return 0;
}

[Faye]

JavaScript

//-----------------------------------------------------------------------
//-----------------------------Caesar Cipher-----------------------------
//-----------------------------------------------------------------------
//a == 97 z == 122
//A == 65 Z == 90

const cypher = function(msg,key)
{
    let inRange = (number, x, y) =>
    {
        if(number >= x && number <= y)
        {
            return true;
        }
        return false;
    }
    let newMsg = "";
    for(let i = 0; i < msg.length; i++)
    {
        let charUnicode = msg.codePointAt(i);
        if(inRange(charUnicode, 97, 122) || inRange(charUnicode, 65, 90))
        {
            newMsg += String.fromCodePoint(charUnicode + key);
        }else
        {
            newMsg += msg[i];
        }
    }
    return newMsg;
}

let message = "This took hella lotta time !";
console.log(cypher(message, 4));

[Vincent Thibault]

Using English frequency analysis (but you actually need to know the language source), here is a javascript version:

// English letter frequency a-z
// source: https://en.wikipedia.org/wiki/Letter_frequency
const ENGLISH_FREQUENCIES = new Float32Array([
  0.0816, 0.0149, 0.0278, 0.0425, 0.1270, 0.0222, 0.0201, 0.0609, 0.0696, 0.0015, 0.0077, 0.0402, 0.0240,
  0.0674, 0.0750, 0.0192, 0.0009, 0.0598, 0.0632, 0.0905, 0.0275, 0.0097, 0.0236, 0.0015, 0.0197, 0.0007,
].map(v => Math.log(v) / Math.LN2));

// Here we are !
const decipher = str =>
  Array.from({ length: 26 }, (_, key) => {
    // Rotate text
    const text = str
      .toLowerCase()
      .replace(/[a-z]/g, $0 =>
        String.fromCharCode(97 + (($0.charCodeAt(0) - 97 + key) % 26))
      );

    // Get entropy information based on Shannon
    // https://en.wikipedia.org/wiki/Entropy_(information_theory)
    const entropy = text
      .match(/[a-z]/g)
      .map(c => ENGLISH_FREQUENCIES[c.charCodeAt(0) - 97])
      .reduce((sum, frequency, _, arr) => sum - frequency / arr.length, 0);

    return { key, text, entropy };
  }).sort((a, b) => a.entropy - b.entropy); // Sort results

You'll get results sort by entropy score:

console.log(
  decipher("dwwdfn iurp wkh zrrgv dw gdzq")
    .map(({ key, text, entropy }) => `${entropy.toFixed(3)} - ${text} (${key})`)
    .join("\n")
);

// 4.227 - attack from the woods at dawn (23)
// 4.936 - piiprz ugdb iwt lddsh pi splc (12)
// 4.974 - ohhoqy tfca hvs kccrg oh rokb (11)
// 5.098 - tmmtvd ykhf max phhwl tm wtpg (16)

[Gael Roussel]

Ruby

class String
  def cesar_encrypt(key)
    raise ArgumentError, 'Key must be between 1 and 26 inclusive.' if key < 1 || key > 26

    letters_min = ('a'..'z').to_a
    letters_maj = ('A'..'Z').to_a

    result = tr!(letters_min.join, letters_min.rotate(key).join)
    result.tr(letters_maj.join, letters_maj.rotate(key).join)
  end

  def cesar_decrypt(key)
    raise ArgumentError, 'Key must be between 1 and 26 inclusive.' if key < 1 || key > 26

    letters_min = ('a'..'z').to_a
    letters_maj = ('A'..'Z').to_a

    result = tr!(letters_min.join, letters_min.rotate(-key).join)
    result.tr(letters_maj.join, letters_maj.rotate(-key).join)
  end
end

pp 'efgfoe uif fbtu xbmm pg uif dbtumfabAB'.cesar_decrypt(1)
pp 'defend the east wall of the castlezaZA'.cesar_encrypt(1)

[Alvaro Montoro]

JavaScript

const cipher = (s, k) => s.toLowerCase()
                          .split('')
                          .map(c => c.charCodeAt(0) < 'a'.charCodeAt(0) || c.charCodeAt(0) > 'z'.charCodeAt(0) 
                                    ? c
                                    : c.charCodeAt(0) > 122 - k
                                      ? String.fromCharCode(97 + (c.charCodeAt(0) + k - 1) % 122)
                                      : String.fromCharCode(c.charCodeAt(0) + k))
                          .join('');

I imagine that for now, the only way to decypher a phrase would be to check each word to verify that it is valid using either a dictionary or an API. Which may be a pain.

A thing that is not going to work now, but maybe it could work in the future (big "maybe" here, but bear with me for a second):

• Browsers contain their own dictionary for spell checking.
• CSS has pseudo-elements for grammar and spelling errors that allows to target content within an element that the browser has identified as having grammar mistakes (::grammar-error) or being misspelled (::spelling-error).
• We could create a hidden input, add the content of the decyphered text and check if there is a pseudo-element that fulfills one of the error pseudo-elements.

It would be super hacky, but it would allow us to use the browser dictionary (if it's not open already, in which case, we should use it) instead of having our own dictionary or having to call an API.

Unfortunately, ::grammar-error and ::spelling-error are not currently supported by any browser, so I cannot test this crazy idea at the moment.