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.
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
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 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
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
To encrypt an Affine Cipher, follow these steps:
- Find the alphanumeric code for the first letter in the plaintext
a*x + b mod 26
- Find the letter from the result of step 2 and place in ciphertext
- Repeat with the next letter.
Decrypting, however, is a little tricky...
- Find the alphanumeric code for the first letter in the ciphertext.
x + 26*n - b mod a = 0, given that
xis the result of step 1.
(x + 26*n - b)/a mod 26
- Find the letter given the result from step 3 and add to the plaintext.
- Repeat with the next letter.
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.
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_2 are given in the plaintext 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 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).
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.
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, ...
Cryptanalysis of Substitution Ciphers
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.
Pollux and Morbit Ciphers
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:
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.
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
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.
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_2 are the greatest factors of
n. Then, you can calculate
d using the extended Euclidean algorithm. Starting with
r_0 = φ,
t_1=1, you begin your extended Euclidean algorithm iterating while
r_(i+1) is not equal to 1 with
t_(i+1) mod φ. Then, using the public key and private key, you can encrypt and decrypt values using the expressions mentioned earlier.
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
@LizFoster No, i as in the iteration count in a series. For example, when i=1,
r_i=r_1. I used i since it is normally used as a counter in summations and n was already taken as part of the public key. However, it can be somewhat confusing with how i also represents the Greek letter iota (ι) which is the square root of -1 and the basis of the complex number system.
@LizFoster However, if you are interested in quantum mechanics as well, there is a more recent quantum cryptography method involving quantum entanglement that I think uses complex numbers. However, quantum is practically every physicist's nightmare with how weird it is, so I haven't gone very far into quantum cryptography.
@LizFoster Yeah... When it comes to physics, it is just easier to think big than small (small as in quantum). However, of course astrophysics is a little difficult as well (it is also my preferred area of physics), especially when you start getting into Relativity. By the way, if you know General Relativity or at least how the tensors work, PLEASE create a learn post on it! I mean, the basis of GR is simple, but when you get to the EFEs, everything just gets confusing, especially if you only really know Euclidean geometry, although I REALLY want to learn non-Euclidean as well.
@LizFoster Same here. I had to teach myself calculus and trig (well, actually this year, in my math class, we learned trig, but I already knew it) and even had to derive formulas in order to work with complex exponentiation and logarithms and stuff like that (honestly, I derived those formulas when I was bored in my math class because I already knew what the teacher was teaching). However, I did get extra credit in my math class for creating proofs for everything... However, what I don't really understand is why schools teach the mathematical concepts and not as much actual math. At least in my math classes, we never had assignments to create proofs or derive formulas (I did those anyways on assignments though (once I even derived the volume of a sphere using Riemann Sums and integral calculus, although I could have just looked it up)), and only were told to apply basic mathematical concepts.
@AmazingMech2418 Well, think of it like it as a 3D heat map, in the shape of a dome. You would have rectangular prisms (instead of rectangles) nested inside the dome (probably centered). You would find the volumes of those rectangular prisms, and approximate the volume of the dome that way. As you make the length and width of those rectangular prisms smaller and smaller, it will approach the real volume of the dome.
For those of you who still don't understand how RSA works, here's an example:
Let's say p, q, and e are all prime numbers. The formula for encrypting is:
(decimal of a letter)^e % (p x q)
For decryption, you can use Euclid's algorithm to find d.
e x d = 1(mod (p-1) x (q - 1))
To decrypt, you use the equation:
(decimal of letter) = (ciphertext decimal) ^ d % e.
I used x's instead of * so that repl doesn't think that I'm trying to style my post
@AmazingMech2418 awesome! Also looking at what the kappa test is, to improve that thing your were telling me about earlier you could maybe use a stream cipher type thing to determine the keys for the individual letters in the vignere cipher. Of course the correlation will be heavy if you don’t choose carefully so there is that, but still... might.... might help.
I use user's password + 200 character key + user's password as an AES-128 encryption key on my repl with a signup feature, is that secure?
i include the users password in it so you need the password to decrypt it and cant just decrypt it if you have the 200 character key