An Introduction To Cryptography Part I

Docs that have proven to be a staple in understanding computer/network security. This is not an inclusive forum and nothing ipublished will tell you how to 0wn someone, these docs will help you understand how you got 0wnd.
Post Reply
telcontar
31337 Martial Artist
Posts: 1898
Joined: Sat Feb 21, 2004 8:38 am
Location: /etc/login.defs
Contact:

An Introduction To Cryptography Part I

Post by telcontar » Mon Dec 13, 2004 2:10 pm

-An Introduction To Cryptography-
Part I

by telcontar
------------------------------

Originally written for and released at
http://www.hackerthreads.org

The First Installment of:

An Introduction to Cryptology

o An Introduction to Cryptography: Part I
o An Introduction to Cryptography: Part II*
o An Introduction to Cryptography: Part III*
o An Introduction to Cryptanalysis: Part I*

* - not finished and/or posted

--------------------

Disclaimer

This article may be redistributed as you will; on the conditions that it's reproduced in it's entirety i.e. proper credits and any sources (where and if applicable) throughout this set of papers, are given.

Contents

o Foreword
o Introduction
o What? Why?
o A Basic Overlook and Some Terminology
o Ecryption Methods And Keys
1. Substitution
2. Transposition
3. The Ceaser Cipher
4. Keys
o Cryptographic Algorithms.
1. Symmetric Key Algorithms
1.1 Stream and Block Ciphers
2. Asymmetric (Public) Key Algorithms
o Conclusion.
1. With an Overview of Part II


Foreword

I'm aware that we already have a Cryptography Tutorial at htd0rg but I felt that it wasn't as good (both in content and the written quality) as it probably should be.
Please note that this Tutorial is meant for Novices/Complete Beginners to the world of Cryptology (although only Cryptography is dealt with in this part) but it still might be worth reading.


Introduction

Here, a _basic_ introduction to the process of Cryptography will be given and the fundamental ideas behind it.
The key aim of this paper (NB: Paper 1 ;) ) is to equip the reader with the knowledge of the basic workings of Cryptography and to make hopefully make future parts of this paper more 'accessible' (not that they will be terribly complicated, but it would be preferable if you were familiar with the basics first).



Crypto What?

Cryptography is basically made up of the processes of scrambling (encrypting) readable data, sending it and then unscrambling it.

Cryptology on the other hand is the collective term for both Cryptography and Cryptanalysis. Cryptanalysis is concerned with trying to work out the original message without any knowledge of the methods used to encrypt the data e.g. a hacker or some NSA hotshot.

Why Encryption?

There's one reason and one reason alone that Encryption exits; the need to keep data secret. By data I mean anything from letters, bank details, passwords, anything that you would find preferable if it were not read by others.

Encryption, or the process of encrypting, basically means the conversion of readable text to garbelled text which is unreadable to all but the receiver who will have the information on how to read it; i.e. decrypt it.

Encrypting data isn't a new thing invented because of the information super-highway, it's been around for a very long time. In fact, one of the earliest recorded uses of encryption is that of Julius Ceaser. In those days the only way to send messages was to get a messenger to take a note/letter to the receiver. Obviously this was very insecure and so Ceaser decided to encrypt his messages so that none but the receiver could read them. To anyone else who intercepted it would read only as gibberish as they didn't know the method to turn it into a readable form i.e. decrypt it.



Encryption Methods and Some Terminology

There are two basic methods used to Encrypt data; Symmetric Key Algorithms and Asymmetric Key Algorithms. However, we'll take a look at these some more near the end of the paper. We will first go through some of the very basic encryption methods and terminology.

Here's a very basic overlook on how text is encrypted and then decrypted.


===============================================
~ Plaintext --> {Encryption Algorithm} --> Ciphertext

--> {Decryption Algorithm} --> Plaintext ~
===============================================


Firstly, you have your original message/letter/whatever. This is called the Plaintext, i.e. text that is readable to anyone.

Then, to encrypt the data, an Encrypting Algorithm must be applied to the text. This is basically a series of operations on the characters of the data, eg a mathematical formula, a series of functions, whatever you want to think of it as. This usually compromises of various Substitutions and Transpositions on the Plaintext. We will look at these processes later on.

The result of applying the Encryption Algorithm to the Plaintext is the Ciphertext. This is the masked Plaintext, unreadable and hence, secure.

Now, there is no point in having your data securely hidden in Ciphertext if your recipient cannot read it and so to get the Ciphertext back into readable form (Plaintext) the Decryption Algorithm must be applied. In effect this is the Encryption algorithm backwards or rather, applying the opposite mathematical functions that were used in the Encryption Algorithm.

The result? The Plaintext has been safely disguised and delivered to the receiver in a readable form.

Encryption Algorithms And Keys

Obviously Encryption algorithms vary massively, in both complexity and methods but two basic underlying ideas exist in all Encryption Algorithms. These are the processes of Substitution and Transposition (mentioned briefly earlier).


Substitution:

As the name suggests this is simply the process of substituting letters of the Plaintext (the original, readable data) with other letters/numbers/symbols.
For example, the letter 'e' could be encrypted as 'j', the letter 'f' would be 'k' and so on.
Or the letter 'A' could be the number '1', 'B' would be '2' etc.

Julius Ceasers' encryption technique, known as 'The Ceaser Cipher' is an example of such an algorithm.


Transposition:

This method involves actually shuffling or moving the Plaintext around, for example manipulating the Plaintext so that it reads diagonally, vertically, backwards in either rows, squares, rectangles or any other shape/form that you want.

Perhaps the simpleist method of this is called 'Rail Fencing' where the Plaintext is written diagonally and the Cipher text is therefore read of as a single row.

Take, for example this Plaintext ..

diy or die security

Processing (enciphering) (Rail Fencing) ...

d y r i s c r t
i o d e e u i y

Ciphertext ...

dyriscrtiodeeuiy

This of course is very simple and easily breakable.

However a more common way to 'encrypt' the data is to write the original Plaintext in some form of a Matrix and manipulate it (note: not like you would when working to get a matrix of numbers to reduced echeleon form or anything, you'll see).

Our 'Matrix' ...

d i y o r
d i e s e
c u r i t
y a d r j <- note the last 4 letters are just there to fill up our Matrix.

We could then just have our Ciphertext as

ddcyiiua ... retj

however this is still extremely easy and your Ciphertext wouldn't be Cipher for very long. By mixing up the order that we write out our Ciphertext we can make things (a little bit) more complicated. So, we write out the second column first, then the third, then the first, then the fifth and lastly the fourth giving our Ciphertext ...

iiuayerdddcyretjosir


The Ceaser Cipher

As already mentioned this is a one of the earliest known uses of a Substitution Algorithm. Originally this method took a letter from the Plaintext message and replaced it with the letter three places from it in the alphabet i.e. a became d, b became e, and so on.

Taking our previous example

diy or die security

becomes

glbruglhvhfxulwb

Therefore we know the Ceaser Algorithm as;

The Cipher Character is obtained from the Encryption of the Plaintext letter 'P'.
So, CC = P + 3
Reader wrote:But wait? (Even though this is a very simple example) I thought encryption was meant to be secure? Doesn't everyone knowing the Algorithm defeat the point of keeping data secure? Surely any attacker could easily change this to a Decryption Algorithm and get my original data???!!!
True, true, and yet these encryption algorithms are available for widespread use and yet millions of people use encrypt their data safely and successfully every day.
Reader wrote:How?!
Simple, Keys. Both Symmetric and Asymmetric [key] Algorithms, rely, funnily enough, on the use of Keys.

A Key is a part of the equation, or the series of operations that is applied to the Plaintext, that can be assigned a value upon the sole discretion of the whoever is wanting to encrypt the data and is known only to that person (unless they are sending it to a friend and not just storing it on their PC, in which case the receiver must know the key. We will look at Algorithms in which the receiver doesn't need to same key in just a minute).
Reader wrote:Ok, got it, but where does this key thing fit in Encryption Algorithm X?
Ok, well, take the Ceaser Cipher, where we substitute each letter with the letter three places ahead of it in the alphabet. But the Algorithm can be used for any amount of places, so, more generally the equation for it could be

CC = P + K

Where 'K' can be any number that you wish, and is, in essence your key. See how they work now?

The Algorithm is available for everyone to see, everyone and anyone can use it but as a Key is part of it then it is secure because any potential attacker will not have the whole Algorithm that was used to encrypt it.
However, as you might have noticed, in this particular case there are only 25 possible keys (yes, 25 ;) ) available and thus it is easily 'brute forced' by any malcontented being. But no matter, the point is to show that by using Keys an Algorithm can be available for inspection/use by anyone and still remain a secure method for protecting your data (I know not in this case but think bigger).

In larger, more complex Encryption Algorithms there are many, many, possible keys (not to mention more than one key as well) so naturally your Plaintext would be much more secure.

Lastly, there are a few more terms that you will need to be familiar with;

Most Encryption methods can be split into two main categories, sure there are derivatives but fundamentally there are two types of Algorithms.


Symmetric Key-Based Algorithms

Symmetric, or Secret Key, Algorithms use one Key to both encrypt and decrypt the Plaintext. The Key must remain a secret otherwise your data is compromised.

There are two types of Symmetric Key Algorithms; Block and Stream.

Block Ciphers: This method separates your Plaintext in different chunks (Blocks) and encrypts them separately.

Stream Ciphers: This method encrypts your data by on a byte-by-byte or bit-by-bit basis.


Asymmetric Key-Based Algorithms

Also called Public Key Algorithms, Asymmetric Algorithms use two keys to keep your data secure. One key for encrypting, and the other for decrypting. The keys are known as the Public and Private Keys.
(NB: Public Key: The key that you would share with your friends. Private Key: Key that you take to your grave.)

Traditionally, the Public key is used to encrypt the Plaintext and the Private key is used to decrypt it, however some Algorithms (more on an example of this in Part II) allow either key to be used for encryption with the other being used for decryption. The idea being that someone encrypting the data will not know how to decrypt it and the person decrypting it will not know how the Plaintext was encrypted.

Both of these keys must be mathematically 'related' as the encryption algorithm can subtly change depending on which key is provided as the key for the encryption Algorithm.
So the use of the public key for encrypting would not give the same Ciphertext (Remember Scrambled Plaintext!) that would be calculated if the Private Key was used in the encryption Algorithm.


Conclusion

This concludes Part I of my introduction to Cryptography. Yes, it was very basic and some what dry but hopefully you'll find the next installment more interesting, it will certainly be longer.


An Overview of Part II (NOTE: not everything may be included: this is subject to change)

In Part II we will look at;

o A 'middle ground' between Symmetric and Asymmetric Algorithms, introducing The 'Hybrid' Encryption method.

o Algorithms, both Asymmetric and Symmetric (and our new friend the Hybrid), used to implement Encryption in the real world. These include all the popular and hip Algorithms that you may have heard of: DES, RSA, PGP, Blowfish etc.

o Message Digest Functions - Their uses and different variations.

#############################################################################

-telcontar


telcontar [AT] hackerthreads [dot] org

--------------------------

Feedback is appreciated.

-telly

-edit-

Sorry for the loss of formatting
Last edited by telcontar on Sun Dec 19, 2004 3:55 pm, edited 2 times in total.
Fate favours the well prepared ...

Code: Select all

(A + 3, N - 1, X)

User avatar
Net Battle Bot
Owns you
Posts: 1816
Joined: Fri Jun 04, 2004 6:44 am
Location: Groom Lake

Post by Net Battle Bot » Tue Dec 14, 2004 2:18 am

Major General O'Neill wrote:All I got there was Matrix, and those movies confused me very much
:wink: Good work - a nice introduction for beginners.
Without practice one cannot prove; without proof one cannot be trusted; without trust one cannot be respected.

User avatar
B-Con
Challenge Winner [1x]
Posts: 2679
Joined: Thu Apr 22, 2004 4:19 pm
Location: UC Davis
Contact:

Post by B-Con » Tue Dec 14, 2004 2:56 am

good job, man :D
- "Cryptographically secure linear feedback shift register based stream ciphers" -- a phrase that'll get any party started.

- Why know the ordinary when you can understand the extraordinary?

User avatar
NoUse
time traveller
Posts: 2624
Joined: Thu Aug 28, 2003 10:46 pm
Location: /pr0n/fat

Post by NoUse » Wed Dec 15, 2004 5:48 pm

Good job d00d!
And I will strike down upon thee with great vengeance and furious anger
those who would attempt to poison and destroy my brothers.
And you will know my name is the Lord
when I lay my vengeance upon thee.

telcontar
31337 Martial Artist
Posts: 1898
Joined: Sat Feb 21, 2004 8:38 am
Location: /etc/login.defs
Contact:

Post by telcontar » Sat Dec 18, 2004 6:28 pm

Thanks, but I can never tell NoUse when you're being sarcastic or .. just sarcastic .. ;)

Part Two will be along shortly.
Fate favours the well prepared ...

Code: Select all

(A + 3, N - 1, X)

User avatar
meat1oaf
WebMASTA
Posts: 808
Joined: Thu Mar 11, 2004 2:12 pm
Location: Anywhere but here
Contact:

Post by meat1oaf » Sat Dec 18, 2004 9:32 pm

very nice...
The problem with being better than everyone else is that people tend to assume that you're pretentious.

User avatar
GhostHawk
Ex-Mod
Posts: 1447
Joined: Wed Jul 30, 2003 12:10 am
Contact:

Post by GhostHawk » Sat Dec 18, 2004 9:51 pm

I'm more attracted to you than ever now telly. :-)

-Ghost Hawk
Opinions are like ass holes, everyone has one. It is also my opinion, that I am an ass hole.

User avatar
det`
Apprentice
Posts: 45
Joined: Tue Jul 20, 2004 3:39 am
Contact:

Post by det` » Sun Jan 02, 2005 5:49 pm

very nice. i knew nothing about cyptography until now
VirusScan 1.0 - "Windows found: Remove it? (Y/N)"

Post Reply