AmazingMech2418

# Cryptography 101

Note: Many ciphers are labeled "Coming soon..." since the explanations will be long and would preferably be added in edits to this post.

Cryptography is a great field which combines mathematics, linguistics, and computer science with real-world applications. For example, cryptography is allowing you to see this right now! Repl.it uses HTTPS (HyperText Transfer Protocol Secure) which encrypts web traffic. What happens is that the Repl.it server encrypts the content of the website and sends it to the Internet where browsers like the one you are using right now decrypt the web traffic to provide you with this wonderful coding website and this post which is on that very website.

In order to understand what is going on with web traffic encryption, you need to know cryptography.

## Basic Terms

Cryptography - The study of encryption and decryption
Cryptanalysis - The process of decrypting codes with limited information
Cipher - An algorithm used to encrypt and decrypt information
Key - Information required to decrypt an encrypted message
Symmetric Encryption - An algorithm which uses the same key to encrypt and decrypt
Asymmetric Encryption - An algorithm which uses different keys to encrypt and decrypt
Public Key - A key in an asymmetric encryption algorithm that is available to everyone
Private Key - A key in an asymmetric encryption algorithm that is available only to one person
Alphanumeric - Relating to letters and numbers; in cryptography, alphanumeric codes are numbers that correspond to letters
Plaintext - Original text in encryption, or decrypted text in decryption
Ciphertext - Encrypted version of the plaintext

Other terms will be explained throughout the post

## Alphanumeric Codes

One of the most well-known ciphers is the A1Z26 cipher where A=1, B=2, C=3, ...

However, this is not what is used normally in alphanumeric codes in other ciphers. Other ciphers normally use A0Z25 where A=0, B=1, C=2, ...

Alphanumeric codes can be free-standing ciphers like A1Z26 or can be incorporated into other ciphers like what is commonly done with A0Z25.

## Affine Ciphers

Affine Ciphers are a class of ciphers which follow the expression `a*x + b mod 26`. In this case, `x` is the alphanumeric code for a given letter in the plaintext and `a` and `b` are the keys. `mod` refers to the modulus function which returns the remainder from dividing the number before it by the number after it and is normally referred to in programming as the `%` operator which is used in many languages, including Python and JavaScript. This expression will return the alphanumeric code for the letter in the ciphertext.

To encrypt an Affine Cipher, follow these steps:

1. Find the alphanumeric code for the first letter in the plaintext
2. Evaluate `a*x + b mod 26`
3. Find the letter from the result of step 2 and place in ciphertext
4. Repeat with the next letter.

Decrypting, however, is a little tricky...

1. Find the alphanumeric code for the first letter in the ciphertext.
2. Define `n` where `x + 26*n - b mod a = 0`, given that `x` is the result of step 1.
3. Evaluate `(x + 26*n - b)/a mod 26`
4. Find the letter given the result from step 3 and add to the plaintext.
5. Repeat with the next letter.

### Caesar Cipher

The Caesar Cipher is actually an Affine Cipher, just with `a = 1`. However, encrypting and decrypting the Caesar Cipher is much easier. To encrypt, just use `x + b mod 26` where `x` is the alphanumeric code for a given letter and `b` is the Caesar shift, the key for the Caesar Cipher. To decrypt, given that `x` is the alphanumeric code of a given letter in the ciphertext, just use `x - b mod 26`.

#### ROT-13

The ROT-13 Cipher is a Caesar Cipher with `b = 13`. The interesting thing, however, is that encryption and decryption result in the same values since the range of alphanumeric codes is from 0 to 25 and 13 is right in the middle of that.

### Cryptanalysis of the Affine Cipher

To decrypt the Affine Cipher without the key, you just need two different letters to be known. Either, these could be intercepted somehow from the encryption source, guessed based on the context of the encrypted message, or figured out by using simple methods such as the one-letter word method where you just know that one-letter words are either "a" or "i" and use these to decrypt the cipher.

Using two given letters where `x_1` and `x_2` are given in the plaintext and `c_1` and `c_2` in the ciphertext, you can just use a system of equations between `x_1*a + b mod 26 = c_1` and `x_2*a + b mod 26 = c_2`. To solve this, subtract the two equations, remove the modulus, and add 26 to the right side until an integer value of `a` would satisfy the equation. Then, solve for `a` and substitute `a` into one of the original equations. Then, solve for `b` to finish getting your key. Then, just decrypt the rest of your Affine Cipher using the key and your cryptanalysis is complete!

## Monoalphabetic Substitution

Monoalphabetic substitution ciphers are ciphers where one letter stands for another letter and no letters are repeated in the new "alphabet" generated. Monoalphabetic substitution ciphers may be based on a specific rule like Atbash, one of the special cases of monoalphabetic substitution ciphers, may have a specific, well-known alphabet like Pigpen, another special case, or may have a randomized alphabet or even an alphabet with a key (K1, K2, or K3; I will not go into these in this post, but essentially, the key is just hidden within the alphabet).

### Pigpen

The Pigpen Cipher is a special-case monoalphabetic substitution cipher that can be decoded using a tic-tac-toe board and an "x". Yes, you read that right! It is decoded with a tic-tac-toe board and an "x" as shown in this picture: (image from Wikipedia)

All you need to do for the Pigpen cipher is look at the tic-tac-toe board and the x and draw the borders around the letter you are looking for and add a dot if on the second tic-tac-toe board or the second x. For example, A would have a line at the bottom and right with no dot while Y would have a diagonal line going towards the top right and another going towards the bottom right with a dot.

### Atbash

The Atbash Cipher is another special-case monoalphabetic substitution cipher where the alphabet is simply reversed. In this case, A=Z, B=Y, C=X, ...

Coming soon...

## Vigenere

The Vigenere Cipher is similar to a Caesar Cipher, but with multiple shifts. In a Vigenere Cipher, you take the alphanumeric codes in a letter in the plaintext and the corresponding letter in the key and add them, apply modulus 26, and use that number to get the letter in the ciphertext. When decrypting it, you just subtract the alphanumeric code from the key from the alphanumeric code from the ciphertext. So, now you may be wondering how the key works. The key repeats with one letter on top of each letter of the plaintext or ciphertext. The letter on top of any letter in the plaintext/ciphertext is the corresponding letter from the key. Using these letters in the key, you can then encrypt/decrypt your Vigenere Cipher.

### Cryptanalysis of the Vigenere Cipher

#### Plaintext Attack ("Crib")

One way to cryptanalyze (decrypt) a Vigenere Cipher is to use a plaintext attack known as a "crib". This means that you have some letters known in the plaintext. Using these letters, you can subtract the ciphertext letter's alphanumeric code from the alphanumeric code of the plaintext letter and apply modulus 26 to get a number to gain the alphanumeric code of that key letter. In a Vigenere Cipher, the key is also normally a word, so, given certain letters of a key, but not the entire key, it is still possible to gain the entire key by just guessing and checking to make sure that the completed key would create an understandable phrase.

#### Kappa Test (aka Friedman Test) (Information from https://www.nku.edu/~christensen/1402%20Friedman%20test%202.pdf )

The Kappa Test, created by William Friedman, is a test to determine the length of the key in a Vigenere Cipher to then be able to test letters in the key to cryptanalyze the cipher. It is based on the index of coincidence, the probability of two randomly selected letters to be the same, approximated at 0.0656010. By determining the probability of selecting two random numbers and them matching (determined by frequencies of letters), you can estimate the length of the key of the Vigenere Cipher. The PDF I used to get the information on the Kappa Test also includes the formula and a table of key lengths that you can use if you would like to use the Kappa Test, but the Kappa Test is an extremely advanced method of cryptanalyzing the Vigenere Cipher, which was for a long time considered unbreakable.

Coming soon...

## Baconian Cipher

The Baconian Cipher, named after its inventor, Francis Bacon, is a cipher that is actually based on the binary number system! Binary numbers from 0 to 23 go as follows:
00000, 00001, 00010, 00011, 00100, 00101, 00110, 00111, 01000, 01001, 01010, 01011, 01100, 01101, 01110, 01111, 10000, 10001, 10010, 10011, 10100, 10101, 10110, 10111. In the Baconian Cipher, it goes similarly, just with 0s replaced with "A" and 1s replaced with "B". To get the letters from these binary-based values, you sort the values in ascending order and write out the alphabet, just with I and J together and U and V together.
This is the key for the Baconian Cipher: (from https://www.dcode.fr/bacon-cipher)

The Baconian Cipher, however, normally has one or more A values and one or more B values that you must figure out. However, most groups of letters start with A, so starting with the first letter as A is a great place to start. Also, weird headlines with five-letter words and/or two-letter and three-letter words side-by-side and no words with more than five letters are normally just masked Baconian Ciphers where every letter used in the headlines corresponds with either A or B, normally in a pattern.

Coming soon...

## Diffie-Hellman Key Exchange

The Diffie-Hellman Key Exchange is a way of generating a shared secret key from public and private keys. Given a private key, `x`, you can find the public key to be `b^x mod n` where `b` and `n` are the public base and modulus. Then, given a public key, `p`, and a private key, `x`, from different people within the key exchange, you can find a shared secret with `p^x mod n`. This shared secret can then be used with symmetric encryption to allow the members of the Diffie-Hellman Key Exchange to transmit messages without ever giving anyone their private keys or allowing their shared secret to be easily intercepted.

## RSA

The RSA Cipher is the most well-known asymmetric encryption method and is commonly used in web traffic encryption. It utilizes modular exponentiation, extended Euclidean algorithms, and factoring. It uses the public key `(n, e)` and private key `(n, d)` to encrypt and decrypt a value, `v`. To encrypt, you use `v^e mod n` and to decrypt you use `v^d mod n`. However, given a public key, you can get a private key by using an extended Euclidean algorithm. However, first you need to find φ (phi). `φ = (f_1-1)(f_2-2)` where `f_1` and `f_2` are the greatest factors of `n`. Then, you can calculate `d` using the extended Euclidean algorithm. Starting with `r_0 = φ`, `r_1=e`, `s_0=1`, `s_1=0`, `t_0=0`, and `t_1=1`, you begin your extended Euclidean algorithm iterating while `r_(i+1)` is not equal to 1 with `q_i=floor(r_(i-1)/r_i)`, `r_(i+1)=r_(i-1)-q_i*r_i`, `s_(i+1)=s_(i-1)-q_i*s_i`, and `t_(i+1)=t_(i-1)-q_i*t_i` with `d` equaling `t_(i+1) mod φ`. Then, using the public key and private key, you can encrypt and decrypt values using the expressions mentioned earlier.

## Credits

This post is based on a conversation on cryptography with @LizFoster and @Highwayman in the learn post https://repl.it/talk/learn/Lets-talk-about-p/31380 (feel free to learn about π in that post once the 404 and 500 errors get fixed!) and the content of this post is based on information gathered over the past few years during my journey into cryptography. Information on the Kappa Test is from https://www.nku.edu/~christensen/1402%20Friedman%20test%202.pdf

You are viewing a single comment. View All
AmazingMech2418