Cryptography

01Dec06

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):

ABCDEFGHIJKLMNOPQRSTUVWXYZ
BCDEFGHIJKLMNOPQRSTUVWXYZA

So the message:

The quick brown fox jumped over the lazy dogs

would read

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:

UIFRVJDLCSPXOGPYKVNQFEPWFSUIFMBAZEPHT

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)

ABCDEFGHIJKLMNOPQRSTUVWXYZ
GHASEITYBDWCVPLOKUFJXQZNMR

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
becomes
JYEKXBAWHULZPILNDXVOESLQEUJYEVGRMOLTF

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:

PlainAlphabet:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
CipherAlphabet1:
GHASEITYBDWCVPLOKUFJXQZNMR
CipherAlphabet2:
ZXFGCNHMILODPWJQAVRSTBEUKY

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:
GXAGENTMBLWDVWLQKVFSXBZUMY
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:

==ABCDEFGHIJKLMNOPQRSTUVWXYZ
A|BCDEFGHIJKLMNOPQRSTUVWXYZA
B|CDEFGHIJKLMNOPQRSTUVWXYZAB
C|DEFGHIJKLMNOPQRSTUVWXYZABC
D|EFGHIJKLMNOPQRSTUVWXYZABCD
E|FGHIJKLMNOPQRSTUVWXYZABCDE
F|GHIJKLMNOPQRSTUVWXYZABCDEF
G|HIJKLMNOPQRSTUVWXYZABCDEFG
H|IJKLMNOPQRSTUVWXYZABCDEFGH
I|JKLMNOPQRSTUVWXYZABCDEFGHI
J|KLMNOPQRSTUVWXYZABCDEFGHIJ
K|LMNOPQRSTUVWXYZABCDEFGHIJK
L|MNOPQRSTUVWXYZABCDEFGHIJKL
M|NOPQRSTUVWXYZABCDEFGHIJKLM
N|OPQRSTUVWXYZABCDEFGHIJKLMN
O|PQRSTUVWXYZABCDEFGHIJKLMNO
P|QRSTUVWXYZABCDEFGHIJKLMNOP
Q|RSTUVWXYZABCDEFGHIJKLMNOPQ
R|STUVWXYZABCDEFGHIJKLMNOPQR
S|TUVWXYZABCDEFGHIJKLMNOPQRS
T|UVWXYZABCDEFGHIJKLMNOPQRST
U|VWXYZABCDEFGHIJKLMNOPQRSTU
V|WXYZABCDEFGHIJKLMNOPQRSTUV
W|XYZABCDEFGHIJKLMNOPQRSTUVW
X|YZABCDEFGHIJKLMNOPQRSTUVWX
Y|ZABCDEFGHIJKLMNOPQRSTUVWXY
Z|ABCDEFGHIJKLMNOPQRSTUVWXYZ

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

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.
—begin encryption—

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.

—end encryption—

—begin decryption—

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.

—end decryption—

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.



7 Responses to “Cryptography”

  1. Hey great site or is this a blog? Google indexes in blog searches. I will have to bookmark it. I just started my blog that won’t teach as much as just elaborate on my interests: kites, cryptography (my interest is Voynich Manuscript), microbrew beer, mysticism, etc. Name it, if is offbeat I’ve probably studied it or am about to! My blog is leisuremaster.blogspot.com but I’m not expecting anyone to stop by. Last week I commented on the Voynich Manuscript. It appears to be still unsolved and I think I’ve found a peculiarity that no one has discovered. I study the Voynich like my wife does Sudoku puzzles. Got a comment? Drop a line back…

  2. 3 rfxyq

    Hans Sachs making shoes and Hans Folz shaving the burgomaster dot
    hwntai game*
    to take a friend by the hand in passing and at length are seen

  3. nature to which his imagination does not give a poetic hue dot But the
    free mike18 movie*
    at the same time not painless excitement dot They had been conversing

  4. 5 kiran

    hello friends is there any way to find the shift value in caeser cipher.plz tell me

  5. iqyow byfxcumz rkntszp ehwxc ezio cevq unjcd

  6. oyzpse zsbhqwgcu dkbzgip divyhkzb zcbuavq jximubal dbsjcinw


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: