Solving cryptic puzzles can be a lot of fun, provided you know the basics of Cryptography. So here is a quick overview of basics of Cryptography – All in one.
The infamous Caesar Cipher (shift, ROT)
Ok, for all you cryptographers-in-the-making (and everyone else, for that matter), I have decided to give simple, yet educational explanations of the basics of cryptography.
One of the very first methods of cryptography was the Caesar Cipher, also known as “shift” or “ROT” (rotate).
The Caesar cipher is quite simple: you shift all of the letters of the alphabet down a certain number of spaces. So, if you want a rotation of 1, here’s what you’d use (the upper letters are the normal alphabet, and the lower letters are what you replace them with):
So the message:
The quick brown fox jumped over the lazy dogs
Uif rvjdl cspxo gpy kvnqfe pwfs uif mbaz epht
But, just to make this harder, many people took out the spaces, and made it all caps. So that it would become:
This is the Caesar Shift 1, or ROT1. You can rotate by more than 1 letter if you wish. The original Caesar Shift was 3 letters, but has grown beyond it’s originalities to encompass all rotations.
The monoalphabetic cipher
The term comes from latin – mono, meaning 1, alphabet meaning, well, alphabet, so it’s a cipher that uses 1 alphabet. We use an alphabt every day, don’t we? Yes we do. But, the monoalphabetic cipher uses a different alphabet, one where each letter is replaced by another letter.
So, you could have the plain alphabet (above) and a cipher alphabet (below)
Now, if we were to encrypt the same string as before, using the same format as shown the second time around:
The quick brown fox jumped over the lazy dogs
As you can see, the 2 strings seem so different from each other that it seems impossible that there’s a relationship between them. If you truly believe that there isn’t, and that it’s too hard to figure out, then you’re sadly mistaken, and you might not have what it takes to become a cryptographer.
Just reverse what you did, switching the 2 alphabets around, then replacing each letter, and you have the original text.
The first monoalphabetic ciphers actually had extra characters, null chars, to throw people off. They would be inserted in random locations throught the text to try to deteriorate the accuracy of the decryptor.
The polyalphabetic cipher
For those of you who don’t know latin, the terms comes from poly, meaning many, and alphabet, meaning alphabet.
An example would be like this:
Now, because This would take way too long anyways, I’ll just translate the alphabet, ABCDEFGHIJKLMNOPQRSTUVWXYZ
With the spaces ever 5 letters, the alphabet would become:
Now, we can immediately see that there are 2 G’s. Why? Because the first G occurs because a letter is being translated by the first alphabet, and the second is being translated by the second alphabet, so there will be a tendency of producing conflictions, making the cipher harder than the ordinary monoalphabetic cipher.
Now, for the Vigenere Cipher, the best example of this type of encryption.
In fact, it uses a chart:
And there’s your Vigenere Square. It’s more square when written, but you get the idea. Or, if you don’t, then keep reading.
The very first line (the one with the 2 =’s (sorry about that, but I had to keep consitency)) is the KEY line. The first column (the one with the |’s next to it) is the plaintext alphabet.
Choose a word to act as your key. preferably, it shouldn’t have too many letters. I’ll use JOE. next, choose some text. I’ll use ENCRYPT…lame, but effective.
Now, when I encrypt, I look at the chart, and look for the plaintext letter E. Then I look up the key letter J. They cross at an O. So, my plainxt so far says O.
Then, I look up N with O, and get C, so I have OC. Then, I look up C with E, and find H, for OCH. Now, since there are no remaining letters in the key, I start at the beginning of the key, with the J. R–>J=B. Y–>O=N. P–>E=U. T–>J=D.
So, ENCRYPT=OCHBNUD, and I’ve had 2 loops of the pass.
Public-Key Cryptography is different from the other 3 types discussed earlier, in the type of key used. Public-Key means, literally, that the key is given to the public.
Now you’re thinking “Well, that’s really stupid, isn’t it? They can just undo what was done to encrypt it, and it’s a really bad thing”. You’re wrong, because it uses an ASYMETRIC KEY. that means that in order to decrypt it, different steps must be taken than those to encrypt it.
The most famous type of this cryptography is called “RSA”, the first initials of the 3 people who invented it. RSA, when put to the test, is the only unbreakable pure cipher out there. I say “pure cipher”, because there’s something going around called “PGP”, or “Pretty Good Privacy”, which involves RSA, but uses another encryption, making it a cross-breed.
Now, for how to use RSA. I will give you an example, but you can use different numbers for each variable.
First, pick 2 ODD prime numbers (2 is an even prime number), that multiplied together, totals a number greater than 127. These numbers are going to be p and q.
I’ll use p = 11 and q = 17. When you multiply them together, you get 187, or our value of N. We also need another odd number, e. in this case, I’ll use 7.
We now have:
p = 11
q = 17
N = 187
e = 7
Then, we publish our values of N and e into a directory listing of everyone’s values of N and e. Let’s say someone wants to send you the message ‘p’ (just something short). Well, they’d first need to know ASCII. you can get an ascii chart here. first, they would have to look up the numerical value of p, which s 112. They now get into exponents. Exponents are simply how many times you multiply a number by itself. 2^4 is 2 to the fourth power. The exponent is 4, and the number is 2. We multiply 2 by itself 4 times, or 2*2*2*2, and we get 16.
What the person does is they take the value of p (112) and put it in M.
C, the ciphertext of M, equates to M^e (mod N). That means that we take M, multiply it by itself e times, and “mod” that by N.
The term mod is short for (no, not moderator. that’s for the forums) modulus arithmetic. Take a clock. it’s 7:00. what time will it be in 10 hours? no, not 17:00, but 5:00. Why? Because what we do is we take 7+10, and divide by 12, 1 remainder 5. We take the remainder, and that’s our answer.
Now, we know that 7 = 1 + 2 + 4, right?
So, 112^7 = 112^1 * 112^2 * 112^4. 112^1 = 112, mod 187 = 112.
112^2 = 12544 mod 187 = 15
112^4 = (112^2)^2 = 157351936 mod 187 = 38
112*15*38=63840 mod 187 = 73. So, C=73.
They send you the message 73. How do you know what it was? you can’t figure that out using just e and N, it’s impossible. You need to know a special number, d. d is determined using p and q. So, it all becomes simpler now.
(d * e) mod ((p-1) * (q-1)) = 1. Simplified, that becomes (d * 7) mod 160 = 1.
Using something called “Euclids’ Algorithm”, determining d is simple. It turns out that in this case, d = 23.
Now, M=C^d Mod N. or, M = 73^23 mod 187.
23 = 1 + 2 + 4 + 16
73 * 93 * 47 * 103 = 32865549 mod 187 = 112 = M.
This was actually a fairly simple example. Most companies that use RSA use values of q and p that are larger than 1 with 100 ‘0’s after it, making N larger than 1 with 10,000 ‘0’s after it.
I know that there are only 4 parts to this, but I will soon be creating another series, The Cracker’s Guide to Cryptography.
Filed under: Extras, Hacks, How-To, Monthly Spl., Techies | 7 Comments