Modular Arithmetic

Modular arithmetic is the central mathematical concept and fundamental in cryptography. Almost any cipher from the Caesar Cipher (Julius Caesar) to the RSA Cipher use modular arithmetic. Initially, starting with Caesar cipher (also known as a shift cipher) is one of the simplest forms of encryption. Caesar cipher is a substitution cipher that replaces each plaintext letter by another one.

Note: The replacement rule is very simple, where it takes each letter that follows the key (k) positions in the alphabet. The table below shows the mapping letters with numbers.

screen-shot-2017-02-16-at-9-42-48-am

The table above represents the letters in plaintext. In order to send a message using these letters in a ciphertext form, the sender and receiver should generate a secret key (k). For example, if k = 8, the table would be updated to the following:

screen-shot-2017-02-16-at-9-42-59-am

Plaintext ATTACK 0, 19, 19, 0, 2, 10.
Ciphertext IBBIKS 8, 1, 1, 8, 10, 18.

 

So, the table below is a comparison between the plaintext table and the cipher text table:

screen-shot-2017-02-16-at-9-41-30-am

 

Another simple way to look at the Caesar cipher (shift cipher) would be:

screen-shot-2017-02-16-at-9-41-08-am

 

Caesar cipher is an elegant mathematical description of the cipher, since k, x, y ε {0, 1, 2, 3, …, 23, 24, 25}.

  • Encryption: y = ek(x) ≡ x + k mod 26.
  • Decryption: x = dk(x) ≡ y – k mod 26.

 

The question we keep asking is – – “Is the shift cipher secure?”; The answer is No, because there are several attacks occurred on this cipher, including:

  1. The limitation of the key (Exhaustive key search) – key space is only 26.
  2. The letter frequency analysis is similar to attack against substitution cipher.

 

Eventually, Caesar’s cipher is not that nowadays, but asymmetric cryptography (RSA and elliptic curve crypto) uses modular arithmetic extensively.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s