An Oversimplified Introduction to Cryptology
Before embarking on this fascinating but somewhat strenuous journey of understanding the rudiments of CRYPTOLOGY (boo 👻), I’m going to explain why anyone would (and ought to) embark on it. Cryptology as everyone knows (or should know) has infiltrated almost every sphere of our lives. Obvious things like computers and phones are prime examples. However, other modern applications such as e Passports, banking cards, and VPNs (Virtual Private Networks) are all too familiar in our daily life. So it shouldn’t surprise you when I say:
“Modern society and its welfare wholly depends on the validity and cunning of algorithms that a few brilliant researchers thought up in a decrepit classroom.”
-Owen Agnel 2019 (This quoting feature makes you feel so powerful.)
Wow that’s kinda deep. But even more surprising, is that these very algorithms are completely public and as a matter a fact, not even that complicated to understand with a little nasty math. So after this monologue describing to you the importance of cryptology in our lives, I have an itty-bitty question for you: “Aren’t you interested in understanding how and why these little algorithms that we depend on so dearly function?”. Well if you aren’t go watch Stranger Things or something, I did my best to convince you. But if you are, stick along on this little series and you might have Fun? Yeah you will outright love it by the end.
Quick disclaimer:
I have not studied this stuff under any professor (except the fantastic lectures by Prof. Christof Paar on youtube) or in any university and I’m by no means an expert. This is just a fun project of mine that I hope will introduce someone to the field of cryptology.
Index
Here’s just an overview of this article for those of you who are picky :
- A short history of cryptology
- Notation
- Kerckhoff’s principle
- Example of a historical cipher and showing how terrible it is
A short history of cryptology
We obviously can’t dive straight into the inner workings of AES without first doing a bit of history (aww…) I know, I hate history too. Surprisingly (or at least you’re supposed to be surprised, you might not be — I wasn’t) cryptology has been in use since at least 1900 BC. It was used in an inscription on the tomb of some noble Egyptian dude. Later, the greeks used it, then Caesar used it blablabla — what I’m trying to say is that cryptology is pretty old. GOOD cryptology on the other hand is very very young (less than a century). It feels a bit mean to say that. Substitution ciphers were quite ingenious for the time and, to be fair, did work well against the cryptanalysts of the past. Nowadays we can make a distinction between two types of ciphers: historical ciphers which are complete trash and modern ciphers which are a LOT better (yay progress!). Note that cryptology encompasses a lot more more than just ciphers or “secret messages”. Message integrity checking, network protocols etc… are also included. I’m getting ahead of myself. The question we should be asking ourselves is why were ciphers invented in the first place. Well say two people want to communicate, let’s call them Alice and Bob (creative, I know). Regrettably, between them there is an insecure channel with an imbecile, “Oscar”, who wants to spy on them. Insecure channel sounds all technical and everything, but it can be something as simple as an overrun dusty road between two military camps, brimming with enemy spies; or insecure http (the one without the ‘s’ at the end).
Well, to communicate securely Alice and Bob have to find a way of making their message readable to only themselves. TA-DAH cryptography was invented. Wait, what? Did I just say cryptography? What’s the difference between cryptology and cryptography (and cryptanalysis). Well I won’t bore you with a crash course on etymology, but cryptography is basically the art of creating and writing encryption algorithms, where cryptanalysis is the art of finding a vulnerability in the algorithm (i.e. Oscar’s job, cracking the cipher) and cryptology is union of the two.
Notation
History is over kids (Hurray!) now let’s look at some notation (aww…). This is really quick but super important because we will be using the same symbols during the whole series:
- x = plaintext “hello you..” (thing you want to encrypt)
- y = ciphertext “kzjjgfpg’99” (thing Oscar can’t read)
- e(x) = encryption function “pick one yourself, could be caesar cipher for ex.”
- d(y) = decryption function “c.f. above”
- k = key “game_of_thrones”
- |k|= key space (number of possible keys) “a lot (or not)”
Kerckhoff’s principle
See that wasn’t too bad! To make up for this big boring part of the article where about half of you probably left (that must leave me with approximately one person), let’s learn something cool. This single quote pretty much revolutionised cryptology and propelled the whole shebang into the modern age (about a hundred years after the guy said it). It is Kerckhoff’s principle 1883 (come on that sounds cool! no? ok fine.) :
“A cryptosystem should be secure even if the attacker knows all the details about the system with the exception of the secret key” -Kerckhoff 1883
Which translates to “Tell everyone about your algorithm and see if they can break it, if they can’t it’s probably secure!”. When you think about it, this principle is seems kinda counterintuitive. Why would you tell everyone how your cipher works? But it’s nonetheless true.
Example of a historical cipher and showing how terrible it is
To end this article let’s have a bit of fun roasting a bad cipher (that was still cool for the time). The famous, the incredible, the one we used for 3000 years (and when we were 7), the substitution cipher! So the idea is, you replace every letter of the alphabet by a different letter (or symbol). N.B. you may recall a more specific version of the cipher is the Caesar Cipher, where instead of replacing each letter by a random letter, we simply shift the alphabet a certain number of times (ex: if k = 2 then A→c, B→d, … Z→b).
Here’s an example (not caesar cipher) :
- A→h
- B→k
- C→p
…
So imagine we were to encrypt ABBA which is our… yes plaintext! Also written “x”!
Well, e(ABBA)=hkkh (remember e(x) is the encryption function); that wasn’t too hard! Now let’s break the cipher. So let me ask you two questions, try to answer:
- Is this secure?
- If not, how can we attack it?
Done?
So if you answered NOO! to the first question then good job, it really isn’t secure but WHY? That’s a little trickier. So let’s look at all the attacks we have available. The first one sounds cool and is really kinda intuitive, “brute-force”, which means try all the combinations you can until it works (and break the cipher). This method is very efficient if the key space is small (like in caesar cipher where |k|= 25), especially for a computer. However, if the key space is large then it’s practically useless. So what is the key space of this particular cipher (substitution cipher)? It turns out that the key space is:
|k|= 26! = 2 ^88 (Awww…)
Why? Well because for the first letter transcription (i.e. A → any letter) we have 26 letters to chose from to create our secret alphabet. For the second (B→any letter) we have 26 –1 (the one we already used)… and so we have 26! = 26x25x24x…x2x1. Needless to say this number is huge and it would take even a good computer a litteral eternity to try all possibilities. So that’s the end of brute-force.
What other attacks can we use? I’m just gonna tell you : “letter frequency analysis”. The attack uses the fact that in the english language we use certain letters (like “e”) way more often than others (“x”) — points in scrabble use this principle.
Since each letter in our plaintext is always transcribed as the same cipher one, all we have to do is figure out the frequency at which a letter appears in the ciphertext and deduce the plaintext letter using the table above. Example : 1. Figure out frequency of any given letter (suppose in the ciphertext “h” appears 9% of the time), 2. Look that frequency up in the table (“a” appears 8% of the time in the English language) and 3. Deduce the correct letter (h must be a!). This method works best when the cipher text is longer, since the frequencies of cipher letters will approach the values in the table. Okay, so we just showed that substitution ciphers are worthless, Yay! Never use them to speak in private…
Sources :
- Paar, Christof, and Jan Pelzl. Understanding Cryptography : A Textbook for Students and Practitioners. Heidelberg, 2010. Print.
- “BASIC CRYPTANALYSIS” Field manual No 34–40–2, HEADQUARTERS DEPARTMENT OF THE ARMY, Washington DC, September 1990
- Silvio Micali. 6.875 Cryptography and Cryptanalysis. Spring 2005. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.
