dev.to staff

Posted on Aug 16, 2019

Daily Challenge #42 - Caesar Cipher

#challenge

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 yo+challenge@dev.to with your suggestions!

Top comments (14)

La blatte • Aug 16 '19

Here we go:

f=(s)=>[...Array(26)].map((_,i)=>26-i).map(n=>`key: ${26-n}\ncipher: ${s}\nplain: ${[...s].map(l=>(a=l.charCodeAt(0),String.fromCharCode(a<123&&a>96?97+((a-97+n)%26):a))).join('')}`).join`\n---\n`

Without any proper dictionary, I guess I'll stick to the "bruteforce" method! Here's how it works:

First, build an Array containing numbers from 26 to 1 ([...Array(26)].map((_,i)=>26-i))
Print the current index (26-n) and the cipher (s)
Build the associated original text: For each character, if its charCode is between 97 and 122 (hence, if it is a valid lowercase character), add the current index to it, else just return it.
Finally, print the complete result

f('dwwdfn iurp wkh zrrgv dw gdzq');

"key: 0
cipher: dwwdfn iurp wkh zrrgv dw gdzq
plain: dwwdfn iurp wkh zrrgv dw gdzq
---
key: 1
cipher: dwwdfn iurp wkh zrrgv dw gdzq
plain: cvvcem htqo vjg yqqfu cv fcyp
---
key: 2
cipher: dwwdfn iurp wkh zrrgv dw gdzq
plain: buubdl gspn uif xppet bu ebxo
---
key: 3
cipher: dwwdfn iurp wkh zrrgv dw gdzq
plain: attack from the woods at dawn
---
key: 4
cipher: dwwdfn iurp wkh zrrgv dw gdzq
plain: zsszbj eqnl sgd vnncr zs czvm
---
key: 5
cipher: dwwdfn iurp wkh zrrgv dw gdzq
plain: yrryai dpmk rfc ummbq yr byul
---
key: 6
cipher: dwwdfn iurp wkh zrrgv dw gdzq
plain: xqqxzh colj qeb tllap xq axtk
---
key: 7
cipher: dwwdfn iurp wkh zrrgv dw gdzq
plain: wppwyg bnki pda skkzo wp zwsj
---
key: 8
cipher: dwwdfn iurp wkh zrrgv dw gdzq
plain: voovxf amjh ocz rjjyn vo yvri
---
key: 9
cipher: dwwdfn iurp wkh zrrgv dw gdzq
plain: unnuwe zlig nby qiixm un xuqh
---
key: 10
cipher: dwwdfn iurp wkh zrrgv dw gdzq
plain: tmmtvd ykhf max phhwl tm wtpg
---
key: 11
cipher: dwwdfn iurp wkh zrrgv dw gdzq
plain: sllsuc xjge lzw oggvk sl vsof
---
key: 12
cipher: dwwdfn iurp wkh zrrgv dw gdzq
plain: rkkrtb wifd kyv nffuj rk urne
---
key: 13
cipher: dwwdfn iurp wkh zrrgv dw gdzq
plain: qjjqsa vhec jxu meeti qj tqmd
---
key: 14
cipher: dwwdfn iurp wkh zrrgv dw gdzq
plain: piiprz ugdb iwt lddsh pi splc
---
key: 15
cipher: dwwdfn iurp wkh zrrgv dw gdzq
plain: ohhoqy tfca hvs kccrg oh rokb
---
key: 16
cipher: dwwdfn iurp wkh zrrgv dw gdzq
plain: nggnpx sebz gur jbbqf ng qnja
---
key: 17
cipher: dwwdfn iurp wkh zrrgv dw gdzq
plain: mffmow rday ftq iaape mf pmiz
---
key: 18
cipher: dwwdfn iurp wkh zrrgv dw gdzq
plain: leelnv qczx esp hzzod le olhy
---
key: 19
cipher: dwwdfn iurp wkh zrrgv dw gdzq
plain: kddkmu pbyw dro gyync kd nkgx
---
key: 20
cipher: dwwdfn iurp wkh zrrgv dw gdzq
plain: jccjlt oaxv cqn fxxmb jc mjfw
---
key: 21
cipher: dwwdfn iurp wkh zrrgv dw gdzq
plain: ibbiks nzwu bpm ewwla ib liev
---
key: 22
cipher: dwwdfn iurp wkh zrrgv dw gdzq
plain: haahjr myvt aol dvvkz ha khdu
---
key: 23
cipher: dwwdfn iurp wkh zrrgv dw gdzq
plain: gzzgiq lxus znk cuujy gz jgct
---
key: 24
cipher: dwwdfn iurp wkh zrrgv dw gdzq
plain: fyyfhp kwtr ymj bttix fy ifbs
---
key: 25
cipher: dwwdfn iurp wkh zrrgv dw gdzq
plain: exxego jvsq xli asshw ex hear"

Olivier “Ölbaum” Scherler • Aug 16 '19 • Edited

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},

Olivier “Ölbaum” Scherler • Aug 16 '19

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.

Alvaro Montoro • Aug 16 '19

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.

Jackson DaSilva • Aug 16 '19

C#

Rept.it

using System;

class MainClass {
  public static void Main (string[] args) {
    var caesarCipher = new CaesarCipher();

    caesarCipher.Encrypt(3, "attack from the woods at dawn");
  }
}

public class CaesarCipher {
  public void Encrypt(int key, string text){

    if(key < 1 || key > 26){
      throw new Exception("Key must be between 1 and 26 inclusive.");
    }

    Console.WriteLine("Plain:");
    Console.WriteLine(text);

    var decText = new char[text.Length];

    for(int i = 0; i < text.Length; i++){
      int dec = (int)text[i];

      if(dec >= 65 && dec <= 90 || dec >= 97 && dec <= 122){
        decText[i] = (char)(dec + key);
      } else {
        decText[i] = (char)dec;
      }
    }

    Console.WriteLine("Encrypted:");
    Console.WriteLine(decText);
  }
}

LordApple • Aug 17 '19 • Edited

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;
}

K.V.Harish • Oct 7 '19 • Edited

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(' ');

Gael Roussel • Aug 17 '19 • Edited

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)

Vincent Thibault • Aug 17 '19 • Edited

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)

Faye • Aug 17 '19 • Edited

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));

Seiei Miyagi • Aug 17 '19

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')

View full discussion (14 comments)

DEV Community

Daily Challenge #42 - Caesar Cipher

Top comments (14)

C#

Read next

Inferência de Tipos com o Operador Losango

Getting Started with Playwright: A Step-by-Step Guide

A Introduction to Understanding Cloud Technology

Exploring AWS EKS Auto Mode: A Simplified Kubernetes Experience