This is the first post in the "Let's Cipher This!" series and in this post, I'll be talking about the various versions of Monoalphabetic Substitution Ciphers such as:

• Atbash Cipher
• Caesar Cipher
• Affine Cipher

This post will be a bit longer than my previous ones as I had been occupied with a lot of work and other commitments. But I do feel the need to post something atleast once a month with good content, as it keeps me productive (especially during weekends), so hope you'll find this information useful!

What's a Monoalphabetic Substitution Cipher?

It's a type of substitution cipher that is used to replace each letter of a plaintext with another letter using a fixed number or replacement structure, which makes up the ciphertext. There are many variations of these, but today, I have decided to talk about a few that I have mentioned, in the beginning.

Atbash Cipher

Atbash Cipher is a monoalphabetic substitution cipher which is used, originally, to encode Hebrew Alphabets but when modified, it can also be used with any alphabets.

Algorithm

The algorithm is pretty straight-forward, if you have a plaintext of "ABCDEFGHIJKLMNOPQRSTUVWXYZ", then the ciphertext would be the exact reverse of the plaintext: "ZYXWVUTSRQPONMLKJIHGFEDCBA".

original: ABCDEFGHIJKLMNOPQRSTUVWXYZ
reversed: ZYXWVUTSRQPONMLKJIHGFEDCBA

Encryption

Encrypting the message is very simple, you just have to replace every letter of the plaintext with the ciphertext, for example, 'A' would become 'Z' and 'T' would become 'G' and the whole message would be encrypted in this manner.

plaintext:  ATTACKONTITAN
ciphertext: ZGGZXPLMGRGZM

Decryption

Decrypting the Atbash Cipher is the opposite of it's encryption process, for example, 'Z' would become 'A' and 'G' would become 'T' and the whole message would be decrypted in this manner.

ciphertext: ZGGZXPLMGRGZM
plaintext:  ATTACKONTITAN

Cryptanalysis

As you might have understood, this is not a secure cipher and in fact, can be broken very easily, assuming, that the ciphertext has been enciphered using Substitution Cipher or by determining the key by trying out each and every letter i.e. using hill-climbing technique.

However, it can be a bit secure if you add some numbers and punctuation to the plaintext alphabets:

original:  .,?!ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789
reversed: 9876543210ZYXWVUTSRQPONMLKJIHGFEDCBA!?,.

Caesar Cipher

Caesar Cipher is one of the most widely known and simplest substitution ciphers (you probably heard about it or were introduced to it in one of your earlier computer science classes by your ingenious professor!), in which each letter from the plaintext is replaced with another letter that is determined by a fixed number of positions or "shifts". This is named after Julius Caesar, who used it to send private messages that are related to military intelligence with a shift of 3. This is also used in modern ROT-13 system with a shift of 13.

Algorithm

The ciphertext is made by aligning two alphabets, so in this case, I will be using a shift of 15 i.e. letter 'A' would be letter 'P' and letter 'B' would be letter 'Q' and so on.

plaintext:  ABCDEFGHIJKLMNOPQRSTUVWXYZ
ciphertext: PQRSTUVWXYZABCDEFGHIJKLMNO

Encryption

The encryption process is represented using Modular Artihmetic by transforming the letters into it's positions and the mathematical formula is:

E(x) = (x + n) mod 26

By using this formula, we can encrypt our plaintext with a shift of 15:

shifts(n): 15

plaintext:               H  E  L  L  O  W  O  R  L  D
integers(x):             7  4  11 11 14 22 14 17 11 3
E(x) = (x + 15) % 26:    22 19 0  0  3  11 3  6  0  18
ciphertext:              W  T  A  A  D  L  D  G  A  S

Decryption

The decryption, again, is done is reverse with a shift of 15 using Modular Arithmetic i.e. letter 'P' would be letter 'A' and letter 'Q' would be letter 'B' and so on. The mathematical formula for deciphering the text is:

D(x) = (x - n) mod 26

We can use this formula to decrypt the ciphertext:

shifts(n): 15

ciphertext:              W  T  A  A  D  L  D  G  A  S    
integers(x):             22 19 0  0  3  11 3  6  0  18
D(x) = (x - 15) % 26:    7  4  11 11 14 22 14 17 11 3
plaintext:               H  E  L  L  O  W  O  R  L  D

Cryptanalysis

Caesar Cipher is insecure and can be easily broken in two scenarios:

• If the cryptanalyst deduces that it's a Caesar Cipher but doesn't know the shift key.
• If the cryptanalyst figures out that some sort of substitution cipher is used but doesn't know that it's Caesar Cipher.

In the first scenario, it's more straightforward as there are only a limited number of possible shifts (e.g. 26 in English) and can use a Brute Force atack to crack the ciphertext. For the second one, it can be broken using techniques like Frequency analysis or looking for patterns.

Affine Cipher

Affine Cipher is a type of monoalphabetic substitution cipher but it's different compared to Atbash Cipher but similar to Caesar Cipher, where each alphabet is mapped to it's numerical equivalent and then it is encrypted using a simple mathematical function.

Algorithm

The letters are first mapped to the integers in the range of 0, 1, ..., m-1(m = the length of the alphabets used), which then uses a Modular Arithmetic method to convert the integers to it's corresponding letter.

alphabets: A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z
integers:  0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Encryption

The mathematical formula for encrytion is:

E(x) = (ax + b) mod m    

In this formula, a and b are the keys of the cipher and m is the size of the alphabet. The key a must be chosen in such a way that a and m are coprime i.e. "a should not have any common factors with m."

Decryption

Unlike the encryption formula, the decryption process of the ciphertext is performed inversely to retrieve the plaintext:

D(x) = c(y - b) mod m

In this formula, c is the Modular Multiplicative Inverse of a. In order to find the multiplicative inverse of a, you need to find a number x in such a way that it satisfies the following equation:

ax = 1 (mod m)    

Explanation

Let's say you want to encrypt a plaintext that says "HELLOWORLD" with a = 5 and b = 8. The reason I chose "5" for a is because it has to be relatively prime with 26.

plaintext:    H  E  L  L  O  W  O  R  L  D
integers(x):  7  4  11 11 14 22 14 17 11 3

Now, you have to take each value of x and convert it to a different letter using the encryption formula mentioned above:

key a = 5
key b = 8

plaintext:               H  E  L  L  O  W  O  R  L  D
integers(x):             7  4  11 11 14 22 14 17 11 3
E(x) = 5(x) + 8 % 26:    17 2  11 11 0  14 0  15 11 23
ciphertext:              R  C  L  L  A  O  A  P  L  X        

Okay, let's decrypt the ciphertext that says "RCLLAOAPLX" to "HELLOWORLD" using the same keys (a = 5, b = 8):

ciphertext:   R  C  L  L  A  O  A  P  L  X    
integers(y):  17 2  11 11 0  14 0  15 11 23       

Before we proceed, we need to find the modular inverse of a, in this case, it would be 21. You can find the modular inverse using the Extended Euclidean algorithm, which uses Greatest Common Divisor (GCD) of both a and m. If a has a modular inverse modulo m, then the GCD must be 1.

Once you find a, we can start decrypting the ciphertext:

key a = 5
key b = 8

ciphertext:              R  C  L  L  A  O  A  P  L  X    
integers(y):             17 2  11 11 0  14 0  15 11 23
D(y) = a(y - 8) % 26:    7  4  11 11 14 22 14 17 11 3
plaintext:               H  E  L  L  O  W  O  R  L  D

Cryptanalysis

Affine Cipher is known to be a very insecure cipher as it's just another version of Caesar Cipher, which is due to it being a monoalphabetic substitution cipher. If a cryptanalyst is able to discover 2 or more common characters using techniques like Brute Force, Frequency Analysis or maybe even guessing, the key can then be obtained via solving a Simultaneous Equation, since a and m are coprime, it can discard any wrong keys easily in an automated program.

What's next?

So I hope you have understood what's a monoalphabetic substitution cipher and it's applications and variations. You can play around with the encryption tools above or experiment with your own messages to see how it works and prank your friends with it!

References

• Practical Cryptography: Caesar Cipher
• Practical Cryptography: Atbash Cipher
• Practical Cryptography: Affine Cipher

During this week, I was thinking about writing a very long blog post about Cryptography but then it would be too long for the readers that it might get them to feel bored. So, for starters, I thought about making a series of short blog posts called "Let's Cipher This" that would focus on the areas of Cryptography.

What is it about?

Well, the aim of this series is that I want to talk about Codes (I meant secret "codes") and Ciphers, such as:

• How they both work
• How can they both be used to encrypt/decrypt messages
• How to use different methods/strategies to break intercepted code

What's next?

I know that there are a lot of simple and complex ciphers/crypto algorithmic techniques out there and I wanted to make each post as informative and interactive as possible i.e. by giving a detailed description about the cipher/technique, it's history, how it works and it's implementation, which can also be used as a tool for encrypting/decrypting your own messages.

The series is going to be a "Work in Progress", so there won't be an ending to it as the field of the Cryptography is quite vast, deep and complex. I will be updating this series as often as I can, so watch out for new posts that are related to it!

Before you read about this article, try playing the Sudoku Solver above. You can only insert numbers ranging from 1 to 9 in any empty cell. Press Random Level to generate a random sudoku puzzle. Made a mistake? Press Reset to clear the board. To test the algorithm, Press Solve to complete the entire puzzle.

As for the source code, you can view it in my GitHub repository or can be found near the end of this article.

What is Sudoku?

Sudoku stems from the two Japanese words: "Su" and "doku", when translated to English, it means "single numbers only". Although, many people feel that Sudoku was invented by the Japanese, it was actually invented by an American named Howard Garns in 1979 under the name "Number Place" but died in 1989 before a Japanese publisher named Nikoli made it popular, renamed it as "Sudoku" and which of course, became mainstream in 1986.

What is it about?

Sudoku is a logic-based, combinatorial, 9x9 number grid puzzle. The puzzles are usually a partially completed grid, thus allows the puzzle solver to come up with a single solution to the puzzle. The objective of this game is to fill the empty spaces in the partially completed 9x9 grid in such a way that each row, column and 3x3 subgrids (that compose the grid) contains all digits from 1 to 9.

Why did I build it?

Well, one day, I downloaded a Sudoku game on my iPhone and I got hooked to it instantly. I would play the game, usually, during metro rides to my university or any long trips to not make myself feel bored. So one day, I thought "What if I built a sudoku solver and see if it could solve all the puzzles from the game?", which made me even more curious to see how a computer would do it.

Implementation

Okay, I know this is the part that you must be waiting for: "How to implement this?". As I was doing my research on how to implement it, I came across two algorithmic techniques:

• Recursion
• Backtracking

Recursion

Recursion is an algorithmic technique used for breaking down larger problems into smaller instances of the same problem. This is also known as Divide-and-Conquer method. This is usually used in binary search, reversing a file, generating large Fibonacci numbers and the list could go on.

Backtracking

Backtracking is an algorithmic technique used for searching every possible combination in order to solve a problem in an optimized way. You could be familiar with this technique in popular problems like Chess, the 8 Queen Puzzle or Crossword solvers.

Explanation

Imagine, you're playing chess with a friend and you've made a silly move, which prompts you to ask your friend: "Hey, I made a mistake! Can I go back to my old move?", your friend (hopefully, a merciful one) would allow you to return back to your old move. So in this case, you'll return back to your old position and begin to restrategize your plans on how to take down the next pawn or maybe finally hatch your plot to trap your opponent's King (you evil person). If it fails, you can ask again but I don't think your friend would be dumb enough to give you another chance!

Here's a pseudocode on how this strategy would work:

Find [row,col] of an unassigned cell
If there is none, then return true

For digits from 1 to 9
    If there is no conflict for digit at [row,col]
        Assign digit to [row,col] and recursively try to fill in the rest of the grid
        If this recursion is successful, return true
        Otherwise, remove this digit and try another one
    If all digits have been tried for this cell and nothing worked out
        return false, trigger backtracking and try again

Javascript implementation:

//Sudoku solver 
function solveSudoku(grid, row, col) {
    var cell = findUnassignedLocation(grid, row, col);
    row = cell[0];
    col = cell[1];

    // base case: if there's no empty cell  
    if (row == -1) {
        return true;
    }

    for (var num = 1; num <= 9; num++) {

        if (noConflicts(grid, row, col, num)) {   
            grid[row][col] = num;

            if (solveSudoku(grid, row, col)) {                
                return true;
            }

            // mark cell as empty (with 0)    
            grid[row][col] = 0;
        }
    }

    // trigger back tracking
    return false;
}

//Find an empty cell
function findUnassignedLocation(grid, row, col) {
    var done = false;
    var res = [-1, -1];

    while (!done) {
        if (row == 9) {
            done = true;
        }
        else {
            if (grid[row][col] == 0) {
                res[0] = row;
                res[1] = col;
                done = true;
            }
            else {
                if (col < 8) {
                    col++;
                }
                else {
                    row++;
                    col = 0;
                }
            }
        }
    }

    return res;
}

//Check if there are any conflicts in row, column or 3x3 subgrid
function noConflicts(grid, row, col, num) {
    return isRowOk(grid, row, num) && isColOk(grid, col, num) && isBoxOk(grid, row, col, num);
}

//Check if this number is valid in this row
function isRowOk(grid, row, num) {
    for (var col = 0; col < 9; col++)
        if (grid[row][col] == num)
            return false;

    return true;
}

//Check if this number is valid in this column
function isColOk(grid, col, num) {
    for (var row = 0; row < 9; row++)
    if (grid[row][col] == num)
        return false;

    return true;    
}

//check if this number is valid in 3x3 subgrid
function isBoxOk(grid, row, col, num) {
    row = Math.floor(row / 3) * 3;
    col = Math.floor(col / 3) * 3;

    for (var r = 0; r < 3; r++)
        for (var c = 0; c < 3; c++)
            if (grid[row + r][col + c] == num)
                return false;

    return true;
}

What's next?

So now that you have understood the rough concept of how it works, combining and applying these two techniques in a Sudoku puzzle i.e. trying out every possible number to fill an empty square in the 9x9 grid would allow the computer to solve Sudoku puzzles more efficiently and quickly than using a plain Brute Force technique on puzzle that has around 4 x 1038 possibilities (which means, you'll probably require next-gen hardware to compute one puzzle that could take billions of years!)

Oh, you can play around with the Sudoku Solver above by trying out a Sudoku puzzle or generate a random one and solve it. Or best, if you'd like to challenge yourself, you could try to implement this solution on Project Euler's Problem 96 by solving all 50 sudoku puzzles in a row!

References

• Stanford's Exhaustive Recursion and Backtracking
• Solving Every Sudoku Puzzle

Hello World! This is my first blog post.

#include <iostream>
int main()
{
    cout << "Hello World" << endl;
    return 0;
}

I'm not a huge fan of open source CMS projects like Wordpress and Drupal, I decided to build my own custom blog engine for talking and discussing about my favorite topics.

For this blog, I aimed for a minimalistic look, hence I decided not to use any templates or CSS frameworks to make it look bloated or fancy.

On using this blogspace of mine, I intend to talk about technology, math, computer science, design, programming experience and a lot of positive stuff.

Hopefully, I will try my best to update this blog as frequently as possible.

Hope you guys will enjoy reading my future blog posts!