Understand Caesar Cipher by Implementing it in Python

What will we cover?

  • Understand what Caesar Cipher is
  • Implement Caesar Cipher in Python
  • Understand the weakness of Caesar Cipher

What is Caesar Cipher

Caesar Cipher is a simple substitution cipher, which is limited to only shift the characters by fix number.

Imagine you got the message: BRX DUH DZHVRPH. What to make out of it. Makes no sense. Just ignore it, right?

Well, for the untrained eye, yes, ignore it. But why would anyone bother sending you that message? Aren’t you curious?

I would be. Let’s say your friend told you it was a Caesar Cipher with a 3-key shift. What does that mean?

In the picture below, you can see how the letters are shifted from the green letters (plain text), to the encrypted red letters (cipher text). As an example, A is encrypted to D, and B is encrypted to E, and so forth.

By using that strategy, you can also figure out that a cipher B (red letters) maps to the plain Y (green letters). A cipher R maps to the plain O. And so forth. That results in that your secret message decrypts to YOU ARE AWESOME.

What a nice message to get.

Implementation of Caesar Cipher in Python

Below is an example of how you could implement the Caesar Cipher in Python.

def generate_key(n):
    chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    key = {}
    cnt = 0
    for c in chars:
        key[c] = chars[(cnt + n) % len(chars)]
        cnt += 1
    return key

def encrypt(key, message):
    cipher = ""
    for c in message:
        if c in key:
            cipher += key[c]
        else:
            cipher += c
    return cipher

def get_decrypt_key(key):
    dkey = {}
    for k in key:
        dkey[key[k]] = k
    return dkey

key = generate_key(3)
dkey = generate_key(23)
cipher = encrypt(key, "YOU ARE AWESOME")
print(cipher)
message = encrypt(dkey, cipher)
print(message)
dkey = get_decrypt_key(key)
print(encrypt(dkey, cipher))

There are some things to notice. First of all, the generate_key function comes in handy, when we extend our cipher function to the more general substitution cipher.

Also, notice, that encryption and decryption are done with the same function, just different keys. The decryption key of key-3 is key-23.

See that you can actually calculate the decryption key quite nice, as done in the get_decrypt_key function, which can be used if this is extended to a general substitution cipher.

How to de-cipher a Caesar Cipher message

Image you had received the message BRX DUH DZHVRPH, but didn’t know the key. What to do?

No worries, there is a way to solve that problem efficiently.

The scenario is that Alice wants to send Bob a secret message, but someone (you) get’s a copy of the message (and you are called Eve).

The secrecy of the message was intended to be, that you (Eve) does not know the Algorithm (how the encryption is done). That might seems naive today, but back in the time of Caesar, this was the state of the art, and people were not that knowledgable about the art of cryptography.

But you are in luck. Yes, I am talking to you Eve.

You know the Algorithm and you are soon to figure out, that the key space is quite small. Actually it only contains 26 possible keys.

That is in the reach of you manually trying out all possible keys.

But you are in more luck, because you realised that you also have Python. So let’s try to fix it in Python.

def generate_key(n):
    chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    key = {}
    cnt = 0
    for c in chars:
        key[c] = chars[(cnt + n) % len(chars)]
        cnt += 1
    return key

def encrypt(key, message):
    cipher = ""
    for c in message:
        if c in key:
            cipher += key[c]
        else:
            cipher += c
    return cipher

cipher = "BRX DUH DZHVRPH"
for i in range(26):
    key = generate_key(i)
    message = encrypt(key, cipher)
    print(message)

That will generate the following output.

CSY EVI EAIWSQI
DTZ FWJ FBJXTRJ
EUA GXK GCKYUSK
FVB HYL HDLZVTL
GWC IZM IEMAWUM
HXD JAN JFNBXVN
IYE KBO KGOCYWO
JZF LCP LHPDZXP
KAG MDQ MIQEAYQ
LBH NER NJRFBZR
MCI OFS OKSGCAS
NDJ PGT PLTHDBT
OEK QHU QMUIECU
PFL RIV RNVJFDV
QGM SJW SOWKGEW
RHN TKX TPXLHFX
SIO ULY UQYMIGY
TJP VMZ VRZNJHZ
UKQ WNA WSAOKIA
VLR XOB XTBPLJB
WMS YPC YUCQMKC
XNT ZQD ZVDRNLD
YOU ARE AWESOME
ZPV BSF BXFTPNF
AQW CTG CYGUQOG

That was awesome right.

Conclusion

The security of Caesar Cipher was by keeping the Algorithm secret. That approach to security is not used anymore. Kerckhoffs’ Principle states that the adversary (Eve) should not be able to break the cipher even when she knows the Algorithm.

Bubble Sort Explained, Implemented in Python and Time Complexity Analysis

What will we cover?

  • What is Bubble sort and how does it work?
  • How to implement it in Python
  • How to evaluate the time complexity of the Bubble sort algorithm

What is Bubble sort and how does it work?

In this video the Bubble sort algorithm is explained. On a high level, it takes an unsorted list and returns it sorted.

How to implement Bubble sort in Python

Well, notice the above description. It is straight forward and simple to implement. That is one of the beauties of the algorithm. Simple to understand. Simple to implement.

def bubble_sort(my_list):
    for i in range(len(my_list), 1, -1):
        for j in range(1, i):
            if my_list[j-1] > my_list[j]:
                my_list[j-1], my_list[j] = my_list[j], my_list[j-1]

An simple illustration of how you can use it.

import random

def generate_random_list(n):
    my_list = []
    for i in range(n):
        my_list.append(random.randint(0, n))
    return my_list

def bubble_sort(my_list):
    for i in range(len(my_list), 1, -1):
        for j in range(1, i):
            if my_list[j-1] > my_list[j]:
                my_list[j-1], my_list[j] = my_list[j], my_list[j-1]

my_list = generate_random_list(20)
print(my_list)
bubble_sort(my_list)
print(my_list)

Evaluating the performance of Bubble sort

First of the algorithm has two for-loops. An outer and an inner for-loop. With an input of a list of length N, the loops will be iterated the following number of times.

  • Outer for-loop: N times
  • Inner for-loop: N-1 + N-2 + N-3 + … + 1 + 0 times

Knowing the formula

  • N-1 + N-2 + … + 1 + 0 = (N-1)*N/2

We can add that the time complexity of Bubble sort is O(n^2).

But let’s try to experiment with real running data, to see if we can confirm that complexity.

To get run-times from the algorithm the cProfile library comes in handy. It is easy to use and gives good insights. A simple way to get run-times is to set it like this.

import random
import cProfile

def generate_random_list(n):
    return [random.randint(0, 4*n) for i in range(n)]

def bubble_sort(my_list):
    for i in range(len(my_list), 1, -1):
        for j in range(1, i):
            if my_list[j-1] > my_list[j]:
                my_list[j-1], my_list[j] = my_list[j], my_list[j-1]

def profile_bubble_sort(n):
    my_list = generate_random_list(n)
    bubble_sort(my_list)

cProfile.run("profile_bubble_sort(10000)")

It will result in an output in the following manner.

         56372 function calls in 11.056 seconds
   Ordered by: standard name
   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000   11.056   11.056 <string>:1(<module>)
        1    0.000    0.000   11.055   11.055 BubbleSortProfiling.py:16(profile_bubble_sort)
        1    0.000    0.000    0.034    0.034 BubbleSortProfiling.py:5(generate_random_list)
        1    0.008    0.008    0.034    0.034 BubbleSortProfiling.py:6(<listcomp>)
        1   11.021   11.021   11.021   11.021 BubbleSortProfiling.py:9(bubble_sort)
    10000    0.010    0.000    0.022    0.000 random.py:200(randrange)
    10000    0.005    0.000    0.027    0.000 random.py:244(randint)
    10000    0.007    0.000    0.012    0.000 random.py:250(_randbelow_with_getrandbits)
        1    0.000    0.000   11.056   11.056 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.len}
    10000    0.001    0.000    0.001    0.000 {method 'bit_length' of 'int' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
    16364    0.003    0.000    0.003    0.000 {method 'getrandbits' of '_random.Random' objects}

You get the time spend in Bubble sort by looking the highlighted line. In the column cumtime you get the time spend in total in the function.

By collecting the run-time for various sizes of lists, we get the following graph.

The graph has a O(n^2) growth as expected.

How to Implement a Stack in Python and Check the Run-time Performance

We will cover the following in this article

  • What is a Stack – a short introduction
  • How to implement a Stack in Python
  • Investigate the run-time performance

What is a Stack

A Stack is a useful concept that is used in daily life, and hence, a concept that is important to understand and master as a programmer.

To understand Stacks just think of a stack of plates. There are two main operations you can do. First, you can add a plate on top of the stack. That operation is called push adds the element on top of the stack. Second, you can remove the top plate of the stack. That operation is called pop, and returns the top element of the stack.

In the diagram below a Stack is pictured. It contains of a Stack of element on the left side. The operation push of the element 03 is executed and results is pictured on the right side. Notice, that the push operation puts the element on top of the stack.

Below the operation pop is executed. Notice, that the pop operation takes from the top of the stack.

Implementation of a Stack in Python

It is a good idea to have a helper class Node that represents the elements on the stack.

class Node:
    def __init__(self, element=None, next_node=None):
        self.element = element
        self.next_node = next_node

The actual functionality of the Stack is kept in a Stack class.

class Stack:
    def __init__(self):
        self.stack = None
    def push(self, element):
        self.stack = Node(element, self.stack)
    def pop(self):
        element = self.stack.element
        self.stack = self.stack.next_node
        return element
    def is_empty(self):
        return self.stack is None

Now you can use your stack. Like the example below.

s = Stack()
for i in range(5):
    s.push(i)
while not s.is_empty():
    print(s.pop())

Will give the following output.

4
3
2
1
0

Notice the order of the element being removed from the stack by pop.

Run-time Performance

If we look at how the stack perform in order of the data size. To investigate the run-time performance the cProfile library is a good choice and simple to use. The following piece of code will help you investigate the performance.

import cProfile
def profile_stack(n):
    s = Stack()
    for i in range(n):
        s.push(i)
    while not s.is_empty():
        s.pop()

cProfile.run("profile_stack(100000)")

See the following graph.

As you see, the push and pop operations are constant, O(1), resulting in a linear performance of n push and pop operations as in the above experiment.