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

Game Play AI with Tic-Tac-Toe Example

In Gaming AI engine you have many ways for implementation but you have few strategic , you can calculate the current situation and play the best move , or estimate it based on thinking of the sequential of all possible movements, this is typically what happen in chess playing in particular, you spend a lot of time estimating the sequential of the all possible movement..

Another factor that affect the AI strategy which is the number of steps prediction ability and the more the number of future steps calculation the best AI engine results but the slower response (and difficult for programming)

Let's take Tic-Tac-Toe Game as a good simple example:

1) Non-predictive AI engine:
-We instantiate AI engine
-Update current border pieces positions
-Get the suggested move which is the best for current situation but not the best as strategic planning..

Note: For board gaming you need to represent the board by double array and the value of each item represent the current piece on it, in case of XO we can use 0 as empty 1 for X and 2 for O , for Chess it would be more complex , so you may need to have schema : 0 = empty ,1x = white piece (11=King, 12=Queen , 13=Rock,14=Horse,...), 2x = Black piece (21=King, 22=Queen , 23=Rock, 24=Horse,...)

public GameAI(int [][] box,int winValue,int lossValue,int levelOfAI) {
this.box=box;
this.winValue=winValue;
this.lossValue=lossValue;
this.levelOfAI=levelOfAI;
}

public int[][] play (){
//try to win the game
if(tryToWin()) return box;
//try to prevent him from win
if(tryToPreventLoss()) return box;
//try to play in the center
if(tryToCenteralize()) return box;
return box;
}

where try to win try to identify places to put the coin to win, while try to prevent loss try to identify certain places where the other user can win if left , and the third one try to centralize for the best wining options and it handle certain centralize problems according to the AI level you can skip certain conditions so it can be beaten by the user.

Also this AI engine can be used for suggested movement by the user by inverting the instantiation of win-Value and loss-Value.

2) Predictive AI engine:
-We instantiate AI engine
-Update current border pieces positions
-Get the suggested move based on predicted movement, so the suggested move is the best move for the number of predicted movement.

The predictive engine use the heuristic search algorithm to find the best movement, in case of XO we have the heuristic defined as :

E(n) = Hx(n) - HO(n) suppose the user play with the X piece
where
Hx(n) = Number of lines that can be completed by the X player
Ho(n) = Number of lines that can be completed by the O player

Example:



Hx(1)=number of line can be completed by X to win = red lines = 8 lines
Ho(1)=number of line can be completed by O to win = green lines = 4 lines
So E(1) = 8 - 4 = 4 and no other location of the X piece will give better heuristic value.

Another example:



Hx(1)=number of line can be completed by X to win = red lines = 8 lines
Ho(1)=number of line can be completed by O to win = green lines = 6 lines
So E(1) = 8 - 6 = 2 So if X-player select this location he will loss 2 advantage points over the O-player..

The Min-Max means you select the maximum for the current play and minimum for the next play (minimum for me = max for the opponent) then the max , min ,...etc.. until predictive steps ends up.

In the current tree, we will estimate the play for 2 future movement for the best current move for O player after the X played into the center, this is similar to what human brain calculate usually (So we will select max for the current play from the next level tree, then the minimum , ...etc..)



(Click on the image to enlarge)

NOTE:Consider the reflection of pieces position so the selected corner position for example, have 4 possible values, this is usually selected by random generation to make a difference in each playing movement, so whenever the X-player place the piece at the center the O-player should play a piece on one of the 4 corners..