Learn to Code via Tutorials on Repl.it!

← Back to all posts
Cryptography 101
h
AmazingMech2418 (891)

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, ...

Cryptanalysis of Substitution Ciphers

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.

Pollux and Morbit Ciphers

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.

Transposition Ciphers

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

Commentshotnewtop
LizFoster (606)

Wow... This is cool! T~T

AmazingMech2418 (891)

@LizFoster Does this make it easier to understand the concepts in cryptography? By the way, it is now updated to include everything but RSA, Pollux and Morbit, transposition ciphers, and the cryptanalysis of substitution ciphers.

LizFoster (606)

@AmazingMech2418 It does, I suppose. It's still confusing, but I guess it does make it a bit easier to visualize.

AmazingMech2418 (891)

@LizFoster Great! So, I didn't use too many technical terms that I didn't explain? I kind of have a reputation of always overusing the technical terms when trying to explain something.

LizFoster (606)

@AmazingMech2418 Honestly, I do the same.. (Lol)

No, it was clear enough!

AmazingMech2418 (891)

@LizFoster Great! I honestly think nearly all of us math people tend to overuse technical terms though. Of course, there are some who do very well at explaining things in simpler terms, but sometimes, it is just easier to use the technical terms.

AmazingMech2418 (891)

@LizFoster I just added RSA. Although the most difficult, I think it will be your favorite since it is the most math-based with extended Euclidean algorithms and modular exponentiation.

AmazingMech2418 (891)

@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.

AmazingMech2418 (891)

@LizFoster Also, underscores are used to represent subscripts in LaTeX, so that's what the underscores mean.

LizFoster (606)

@AmazingMech2418 Yes, I got a bit excited there T~T

AmazingMech2418 (891)

@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 (606)

@AmazingMech2418 Yeah, I've considered dabbling in Quantum Mechanics, but it really is a nightmare to deal with..

AmazingMech2418 (891)

@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 (606)

@AmazingMech2418 non-Euclidean, as in complex/higher dimensional geometry?

AmazingMech2418 (891)

@LizFoster Basically (I think...). I'm specifically referring to Gaussian coordinates and Riemannian tensors and stuff like that as used in GR.

LizFoster (606)

@AmazingMech2418 Ooh boy, I am actually starting to learn about those right now! It'll be a journey for the both of us.. (Lol)

AmazingMech2418 (891)

@LizFoster Wow! How are you learning it? Are you looking it up or are you taking a class that teaches it or what?

LizFoster (606)

@AmazingMech2418 Looking it up. No way would my school teach us something at this level!

LizFoster (606)

@AmazingMech2418 Yeah. I had to learn almost everything I know about math today by myself, since they only teach us the bare minimum; nothing cool, like sigma, e, phi, tau, PI (uppercase obviously), or fractal geometry..

AmazingMech2418 (891)

@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.

LizFoster (606)

@AmazingMech2418 Wow, that sounds really fun! So, what would the equation be for a 3 Dimensional Riemann Sum?

AmazingMech2418 (891)

@LizFoster I didn't actually use a 3D Riemann Sum. I just created a summation of the area of a layer of a hemisphere and then converted to an integral, integrated it, and multiplied by two to get the volume of the sphere.

AmazingMech2418 (891)

@LizFoster I honestly don't even know if there is such a thing as a 3D Riemann Sum.

LizFoster (606)

@AmazingMech2418 Lol

I was joking, I meant that I was going to make that a reality! (Lol)

AmazingMech2418 (891)

@LizFoster Okay. I was just a little confused... So, now are you creating a 3D Riemann Sum? I think it would really be just two nested summations.

LizFoster (606)

@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.

AmazingMech2418 (891)

@LizFoster Yes, but the issue would be trying to notate that. I think it would be something like \sum_{n=1}^{n_{x}}Δx\sum_{i=1}^{n_{y}}Δy\cdot f\left(x_{n},y_{i}\right) (copy into Desmos) which would be based on the right Riemann Sum. It is really just a nested Riemann Sum.

LizFoster (606)

@AmazingMech2418 Whew, that is interesting. Yeah, I suppose it really is just that!

AmazingMech2418 (891)

@LizFoster Now, the question is what 3D integrals would be like...

LizFoster (606)

@AmazingMech2418 That sounds amusing, but I'll see what I can do...

AmazingMech2418 (891)

@LizFoster Actually, wouldn't that be something like \int_{0}^{n_{x}}\left(\int_{0}^{n_{y}}f\left(x,y\right)dy\right)dx? I'm not sure, but I think that's what it would be.

LizFoster (606)

@AmazingMech2418 and what would f(x, y) be exactly?

AmazingMech2418 (891)

@LizFoster The function that you are finding the 3D integral of.

LizFoster (606)

@AmazingMech2418 Ah, of course. Sorry, I'm a bit sluggish right now -_-

AmazingMech2418 (891)

@LizFoster So, do you think that would work for 3D integrals?

LizFoster (606)

@AmazingMech2418 Possibly, but how would it find the z (depth) of each rectangular prism?

AmazingMech2418 (891)

@LizFoster That would be the result of f(x,y). Kind of like how you use f(x) to get y in a 2D integral...

LizFoster (606)

@AmazingMech2418 I'm not sure, I can't seem to get it to work properly..

AmazingMech2418 (891)

@LizFoster Well, I don't think Desmos can handle 3D if you are using that.

LizFoster (606)

@AmazingMech2418 No, I attempted using GeoGebra. That is incredibly slow, though, and I don't know what the syntax for integrals is there..

AmazingMech2418 (891)

@LizFoster You could probably use LaTeX and copy it in there. I know Desmos at leasts uses LaTeX, so you could probably just copy from Desmos.

LizFoster (606)

@AmazingMech2418 Hold up, how do I access LaTeX? Is that like some special website I need to go to?

AmazingMech2418 (891)

@LizFoster It's just an equation format. You can just type something in Desmos and copy and paste it and it will automatically format into LaTeX.

AmazingMech2418 (891)

@LizFoster By the way, what is Repl.it's issue with your post "Let's talk about π"? It's down again... I just replied to the person who is in charge of the bug reports, so hopefully it gets fixed (again) soon.

LizFoster (606)

@AmazingMech2418 Yeah.

No, I can't seem to get it to work properly..

AmazingMech2418 (891)

@LizFoster Integral(f(x),x) is how you notate integrals it seems. It does not seem to use LaTeX though, so you just have to do it all on GeoGebra.

AmazingMech2418 (891)

@LizFoster Yeah... However, it shouldn't take TOO long to just type it in there, but of course it is more inconvenient.

LizFoster (606)

@AmazingMech2418 Jeez, this is exhausting to the mind.. I'll take a break for tonight....

AmazingMech2418 (891)

@LizFoster Well, just imagine if you were doing something with quantum instead! (Actually, don't. That would be more exhausting)

AmazingMech2418 (891)

@LizFoster LOL! Though, I agree. It would probably be good for you to take a break for the day. (It would also probably be good for you to get more than four hours of sleep each night, but that's your choice...)

LizFoster (606)

@AmazingMech2418 I should, but.. I work best at night!

AmazingMech2418 (891)

@LizFoster Same here, but I know that if I get too little sleep, I will be grumpy the next morning. Probably the only times I get less sleep and am fine are when I have a competition or a rocket launch to watch (I really like space exploration).

proficypython (1)

WOW an amazing tut bro. Ive read encryption books but this is just great thanks.

SixBeeps (2988)

Wow, that's a lot of algorithms to cover. Can't wait to see them all :)

AmazingMech2418 (891)

@SixBeeps It is now updated to include everything but RSA, Pollux and Morbit, transposition ciphers, and the cryptanalysis of substitution ciphers.

Codemonkey51 (850)

@AmazingMech2418 oh, one sec, there you go take my updoot

AmazingMech2418 (891)

@Codemonkey51 It is now updated to include everything but RSA, Pollux and Morbit, transposition ciphers, and the cryptanalysis of substitution ciphers.

Codemonkey51 (850)

@AmazingMech2418 lol, 3 Thank you!'s in one thread

AmazingMech2418 (891)

@Highwayman It's still a work-in-progress... The project, however, has information on most of the other ciphers labeled "Coming soon...".

AmazingMech2418 (891)

@Highwayman It is now updated to include everything but RSA, Pollux and Morbit, transposition ciphers, and the cryptanalysis of substitution ciphers.

Highwayman (1357)

@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.

AmazingMech2418 (891)

@Highwayman What exactly do you mean by a stream cipher? I've actually never heard of that one.

Highwayman (1357)

@AmazingMech2418 basically you take a given key and use it to seed a RNG which create a stream of keys that you then use instead of the original key.

Highwayman (1357)

@AmazingMech2418 I took a second to look it up. Maybe you know it by the name of state cipher?

AmazingMech2418 (891)

@Highwayman So, really just a pseudorandom key generator?

Highwayman (1357)

@AmazingMech2418 basically. Kinda. It’s generating several keys determined by the first key is the point. Yes.

ironblockhd (369)

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

AmazingMech2418 (891)

@ironblockhd It would still be possible to decrypt it with the 200 character key. I'd recommend hashing instead of encryption/decryption.

ironblockhd (369)

@AmazingMech2418 what do you think about my new repls password security?

AmazingMech2418 (891)

@ironblockhd Nice! The AES encryption with a 300-character key and the hashing would make it very difficult to crack the hash. Though, SHA256 or SHA512 would be better than SHA224 due to less overlap.