Some notes and explanations for crypto. Title is a joke reference to crypto guide titles often containing the word “made Simple”, or “Gentle introduction”.
prereqs:
modulo function (remainder in division)
XOR function (2 bits are the same: 0, 2 bits are different: 1)
Terminology
Ciphertext: Encrypted text, should not give any information about the plaintext.
Plaintext: The original (secret) message. We want to share this without anyone else being able to eavesdrop.
Key: Secret “password”. This is used to encrypt and/or decrypt messages.
Bruteforce: Dumbly trying all possible combinations/keys.
Initialization vector: Initial starting value when doing chained block encryption.
Secret-key/Symetric crypto
Secret-key crypto is the simplest form of encryption. You can use the same key for encryption and decryption. A very simple usable function is the XOR function. This is also called the One time pad or Vernam cipher.
In case of the one-time-pad/xor, One must be very sure to not encrypt two messages with the same key k as that would make an attacker able to derive the original messages by XOR’ing the two ciphertexts
Secret key crypto is hard to use because the key has to be shared between the two parties, without anyone else being having access to it. This is even more cumbersome if the key has to be different for every message sent. You also have to have a secret key shared with every person that you want to communicate with which will mean 0.5 * N * (N-1) keys for N people, which will very, very, very quickly add up.
Public key/Asymetric crypto
Public key cryptography solves this problem by having two types of keys. A public and a private key. The public key can be safely published for anyone to see and the private key is kept only by you. Anyone can encrypt a message with your public key but only you can decrypt it with your private key.
A good way of explaining this to a non-cryptographer is the example where the public key is a lock that you can send to anyone, but only you have the key to. Anyone that wants to send you a message can request a lock (public key) from you, lock it. And then send the locked crate with a secret message knowing that only you can unlock it. An attacker getting their hands on a lock is not a big deal, but getting the key to all the locks is.
Cipher functions (caesar,substitution)
A small step back to the olden days. You might have heard of the caesar cipher where any character is replaced by another character N places further. This N is the key and posession of this N allows for decrypting the message. This decryption was hard when it had to be done by hand but now with computers it is trivial to bruteforce. The class of cipher functions that the the above c’s cipher belongs to is called substitution ciphers. (Simply replacing a character by another according to simple rules)
Stream cipher
A stream cipher is a more generic name for encryption that happens bit-by-bit, take for example XOR’ing with a key that is just repeated over and over. This can end up being relatively slow for larger data sizes.
Block Cipher
Generally an improvement to stream ciphers is to instead use fixed-size blocks. This often means that we have to add some padding to the content to fit the total block size.
The plaintext is split up into parts of block-size b, where if needed this is extended to not have any half-full blocks. (generally with 1000… or 0000..)
Feistel cipher structure
The Feistel cipher is a structure used in for example the old (and unsafe) encryption standard DES. Many modern ciphers are based on the Feistel structure.
The feistel cipher works by having multiple rounds, where for each round a different (sub)key is used (K0 – Kn). The input is split into two equal parts (Left and Right). Then the encryption function is ran over R0 with Key k0, the result of which is XOR’d with the left plaintext. Then left and right are switched around for the next round. Given enough (even 3-4) rounds the cipher is already a pseudorandom permutation
More info on the wikipedia page, But this is not very important for the basics of cryptography.
Feistel ciphers have a very cool property: If you swap the ciphertext and throw it in the place where the plaintext is normaly put in, it will output the plaintext. Even if F is a hashing function, then it will still be able to decrypt it. This works because the XOR operation is always reversible.
Modes of operation
There are multiple ways to structure the encryption steps of multiple blocks. Here are a couple of the simplest ones, but they might not all be secure. All the methods talked about here are about Symetric-key encryption. (same key for encrypt and decrypt)
ECB
Ecb is perhaps the simplest mode of operation, every block is encrypted on its own without any input from other blocks. While this is simple and is good if you don’t want single-bit errors in encrypted blocks to propagate, it is possible to view the old data.
CFB
CFB chains the encryption togeter, using the output of the last block’s ciphertext as part of the encryption for the next block. The first encryption step instead uses a randomly generated initialization vector which is just a fancy word for starting value. This should be shared together with the secret key to allow for decryption later on.
This is a lot more secure because patterns in the input will not be discernible from the output anymore. The downside is that errors in one of the encryption steps will propagate throughout the other blocks.
OFB
OFB is very similar to CFB in the way the chaining works, but the output of the encryption step is directly used in the next step without the XOR. This still requires has the advantage of being able to precompute the outputs of the encryption functions when you have the IV and key, and later run the XOR operations when you have the ciphertext which can be done in parallel (fast 🙂 )
The structure is also very resembling of a stream cipher.
RSA
RSA is one of the older and most common examples of asymetric cryptography. You can (should) read more about it here: https://en.wikipedia.org/wiki/RSA_(cryptosystem) Until i get the will to write down more about the math involved… (too many p’s and q’s floating around in my head)
Elliptic curve
This is a more modern approach to cryptography, but sadly also a lot harder to implement. Elliptic curve cryptography is used for example in ed25519 SSH keys.
This post is often seen as a good introduction if you like math (or are just interested and have had enough coffee).