Tuesday, August 17, 2010

Cryptography 1

"Classical Cryptography"

Some Basic Terminology
*plaintext - original message
*ciphertext - coded message
*cipher - algorithm for transforming plaintext to ciphertext
*key - info used in cipher known only to sender/receiver
*encipher (encrypt) - converting plaintext to ciphertext
*decipher (decrypt) - recovering plaintext from ciphertext
*cryptography - study of encryption principles/methods
*cryptanalysis (codebreaking) - study of principles/ methods of deciphering
*ciphertext without knowing key
*cryptology - field of both cryptography and cryptanalysis

We have 2 big categories in cryptography private key (single key) or public key (double key) all classical cryptography fall into the private key where a key exist and we need to keep it private between the sender and reciver only .. We will discuss the public key with the modern cryptography..

Let's discuss the Classical Cryptography: this include 3 types ; substitution where some letters replace by others , transposition where exchange some letters positions and the 3rd type is one time pad where the letter changed totally by manipulating them the key..

A) Classical Substitution Ciphers:

-letters of plaintext are replaced by other letters or by numbers or symbols
1.Caesar Cipher:
Replaces each letter by 3rd letter (or k shifted letter)
example:
meet me after the toga party
PHHW PH DIWHU WKH WRJD SDUWB
Mathematically give each letter a number (a=0,.....z=25)
a b c d e f g h i j k l m n o p q r s t u v w x y z
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

then have Caesar cipher as:
c = E(p) = (p + k) mod (26)
p = D(c) = (c – k) mod (26)

2.Monoalphabetic Cipher:
Rather than just shifting the alphabet ,could shuffle (jumble) the letters arbitrarily
each plaintext letter maps to a different random ciphertext letter hence key is 26 letters long

Plain: abcde fghij klmno pqrst uvwxyz
Cipher: DKVQF IBJWP ESCXH TMYAU OLRGZN

Plaintext: if we wish to replace letters
Ciphertext: WI RF RWAJ UH YFTSDVF SFUUFYA

now have a total of 26! = 4 x 1026 keys with so many keys, might think is secure but would be !!!WRONG!!! problem is language characteristics=Language Redundancy and Cryptanalysis:
letters are not equally commonly used in English E is by far the most common letter followed by T,R,N,I,O,A,S other letters like Z,J,K,Q,X are fairly rare



3.Playfair Cipher:
one approach to improving security was to encrypt multiple letters the Playfair Cipher is an example a 5X5 matrix of letters based on a keyword fill in letters of selected keyword,fill rest of matrix with other letters eg. using the keyword MONARCHY



Plaintext is encrypted two letters at a time
-If a pair is a repeated letter, insert filler like 'X’.
e.g. BALLOON will be treated as: BA LX LO ON
-If the plaintext has an odd number of characters, a 'X' letter is appended to the end of plaintext.
-Encryption:
* If both letters m1 and m2 fall in the same row, then c1 and c2 replace each with letter to the right of m1 and m2, respectively.



* If both letters fall in the same column, replace each with the letter below it



* Otherwise each letter is replaced by the letter in the same row and in the column of the other letter of the pair.

And Reverse this in decryption.

4.Vigenère Cipher:
basically multiple caesar ciphers ,key is multiple letters long K = k_(1) k_(2) ... k_(d)
based on a Vigenère Tableau

Plaintext THIS PROC ESSCANAL SOBE EXPRES SED
Keyword CIPH ERCI PHERCIPH ERCI PHERCI PHE
Ciphertext VPXZ TIQK TZWTCVPS WFDM TETIGA HLH


(Vigenère Tableau)

B) Classical Transposition Ciphers:
Letters positions exchanged using a key by which we can decrypt the message by returning the letters to the original location.

1.Scytale cipher
:
a strip of paper was wound round a staff message written along staff in rows, then paper removed leaving a strip of seemingly random letters. not very secure as key was width of paper & staff



2.Geometric Figure
Write message following one pattern and read out with another
Example: I CAME I SAW I CONQUERED



3.Row Transposition ciphers:
In general write message in a number of columns and then use some rule to read off from these columns.
Key could be a series of number being the order to: read off the cipher; or write in the plaintext.
Also We can use a word, with letter order giving sequence: to write in the plaintext; or read off the cipher

Key (W): C O M P U T E R
Key (W): 1 4 3 5 8 7 2 6



C) One-Time Pad:
If a truly random key as long as the message is used, the cipher will be secure
called a One-Time pad is unbreakable since ciphertext bears no statistical relationship to the plaintext since for any plaintext & any ciphertext there exists a key mapping one to other can only use the key once though problems in generation & safe distribution of key.

Key is never re-used and generated from Unpredictable random numbers (physical sources, e.g. radioactive decay)

By either subtraction (in Traditional) and XOR (or modulo 2 addition) in modern.
Key=581295 , Plain=853759
-Encryption: (subtraction)
5 8 1 2 9 5
__

8 5 3 7 5 9
___________

7 3 8 5 4 6

-Decryption:
5 8 1 2 9 5
__
7 3 8 5 4 6
____________
8 5 3 7 5 9

-Encryption (XOR):
Plain 01010011000111
Key 00110011001100
_________________________
Cipher 01100000001011

-Decryption (XOR):
Cipher 01100000001011
Key 00110011001100
_________________________
Plain 01010011000111


Abstracted from Dr.Baha Hasan Lectures, AAST

No comments:

Post a Comment