| An Introduction to Cribbing Isomophs, Gaussian Elimination and The Hidden Markov Model |

|

Abstract
While looking into cryptography and the building blocks that make up ciphers and theory, a mix of time and effort has produced concrete methods of cryptanalysis to identify the temporal pattern recognitions and algorithms necessary to decrypt cipher-text back to its plaintext root. This paper will look at the process of cribbing isomorphs to reveal the plaintext message, Gaussian Elimination and the process of back substitution, and the Hidden Markov Model to view visible output to that which was once hidden.
Table of Contents Introduction 2 Cribbing Isomorphs 3 The Hidden Markov Model 4 Gaussian Elimination 5 Conclusion 6

Introduction
In any cryptanalysts toolbox, there are a number of methods at their dispense which can aid in the deciphering of crypto-text messages back into their native plaintext message. Since the dawn of man, ways have been invented to hide secret information in an attempt to keep secret an intent, hide a plan, cover up a bad deed or whisper softly over distances. Encryption has proven the means to get this data over a medium and ensure that the integrity of the message arrives intact. Many times this information is intercepted and then the deciphering process begins. By knowing a certain amount about a message, cryptanalysts are able to piece the remaining message together by using cribbing, algorithms and back substitution methods to aid in revealing the unknown plaintext. This paper will examine Cribbing Isomorphs, Gaussian Elimination, and The Hidden Markov Model to give the reader a better understanding on how each works together in deciphering cipher-text.
Cribbing Isomorphs
In order to understand just what, “Cribbing Isomorphs” means, we first need to understand what the terms are referring to. In cryptography, cribbing refers to a process of inferring key and plaintext messages from cipher-text, based on partial knowledge of the plaintext. (Konheim, 2007) It is determined that with a partial knowledge of plaintext, crypto-text messages can be deduced by using the cribbing technique. Isomorphs are two like objects, in this case mono-alphabetic text, that exhibit the same or similar structure. Isomorphism can be defined as, “a bijective map f such that both f and its inverse f-1 are homeomorphisms.” (Wikipedia, 2011) In other words, if two objects are considered isomorphic, the properties which are true in the first, are also true in the second. For example, zwipqw and scenic are isomorphs of one another. So what we are going to be looking at is the process of taking one object and its inverse and inferring key and plaintext information from given cipher-text.
The Cribbing process consists of a number of steps of which some go beyond the scope of this basic introduction. The process includes arranging the cipher-text into fixed rows and blocks. The following is an example of what a 100 letter cipher looks like written in rows of 25 and in blocks of 5. Ciphertxt1.1 higmt | livmr | kqiww | ekiwa | mxlsy | xeors | aroic | mwehm | jjmgy | pxxew | oxlex | xeoiw | erepc | wmwer | hwomp | pjsvc | syxsh | igmtl | ivtvs | tivpc |

The subject of the plaintext is the difficulty in deciphering a sentence on deciphering. We begin by looking at a program that takes:
Input: cipher text, crib
Output: isomorphs or crib will look for possible cribs in the ciphertxt1.1 that include DECIPHER, KEY, MESSAGE, ANALYSIS. The following table lists the isomorphs possible of the crib DECIPHER in ciphertxt1.1. DECIPHER | higmtliv |

DECIPHER | higmtliv | gmtlivmr | qiwwekiw | iwwekiwa | eorsaroi | pxxewoxl | xewoxlex | higmtliv | |
Next through the process of statistical analysis or what is termed the X^2 - Test of A Hypothesis we can better understand the probabilities and frequencies of these letters occurring in words, examine the high-frequency cipher-text letters and begin pruning. Using x^2 scores we choose the letters with the highest probability and begin substitution to reveal partial plaintext. DECIPHER | higmtliv |

DECIP | HERIr | kqEww | ekEwa | IxHsy | xeors | aroEc | IweDI | jjICy | pxxew | oxHex | xeoEw | erepc | wIwer | DwoIp | pjsRc | syxsD | ECIPH | ERPRs | PERpc |

Through the process of isomorphs with the other words, frequency analysis, and mono-alphabetic substitution one can take the next steps in decrypting the message.
The Hidden Markov Model
A hidden Markov model is a statistical Markov model in which the system being modeled is assumed to be a Markov process with unobserved hidden states. (Wikipedia, 2011) This brief synopsis of the hidden Markov model defines it as a state that is not directly visible, yet the output which is dependent on that state has become visible. These hidden processes such as the key generating the cipher-text are unknown but what is known is the output or the cipher-text. Hidden Markov Model or HMM can be applied to cryptanalyze a monoalphabetic substitution.
Of key importance is the idea that an HMM is a finite model that determines a probability distribution over an infinite number of sequences. HMM is composed of a different states that may match positions within a structure of columns with multiple alignments. These states emit symbols according to emission probabilities and are interconnected by state-transition probabilities. From the beginning state, a sequence is generated by moving from state to state until the end state is reached. Each or these previous states emit symbols according to that states probability distribution. (Eddy, 1996)
Starting with the basic Markov property, we look into The Forward-Backward Recursion to test the probability of producing the sequence at a given time during a specific state. All calculations are done to get closer to the solution. When HMM is being used as a tool to cryptanalyse a monoalphabetic substitution: * The observed states y for the cipher-text * The hidden states x form the plaintext, and * q is the unknown monalphabetic substitution
Cryptanalysis estimates the maximum likelihood estimate (MLE) of q (and x) given y. (Konheim, 2007)
The Hidden Markov Model makes many assumptions for instance that the next state is dependent only on the current state when actually the next state may depend on past n states. Also that the state transition probabilities are independent of the time at which the transition takes place. (Warakagoda, 1996)
Gaussian Elimination
Another tool in the cryptanalyst toolkit is a method of elimination named after Carl Friedrich Gauss called Gaussian elimination. Gaussian elimination is an algorithm that solves systems of linear equations. Gaussian elimination works by reducing a system to either a triangular or echelon form and if neither of the reductions work then the result is a degenerate equation with no solution. The second part of the process uses back substitution and applies it to either the triangular or echelon form. Reduction in the primary step condenses a matrix to row echelon form using row operations while the second function of the algorithm reduces the matrix to reduced row echelon form, or row canonical form. The algorithm works like this: X + Y + Z = 0 eq1 Step 1 for eq1 and eq2 get rid of x to get eq4
2x – 2y + 3z = 13 eq2 Step 2 for eq1 and eq3 get rid of x to get eq 5
-5y – y – z = -8 eq3 Step 3 for eq4 and eq5 get rid of y
Step 1 -2 (x + y + z = 0) = -2x – 2y -2z = 0 2x – 2y +3z = 13 = 2x – 2y – 2z = 13 -4y + z = 13 eq4
Step 2 5 (x + Y +z = 0) = 5x + 5y +5z = 0 -5y – y – z = -8 = -5x – y – z = 0 4y + 4z = -8 eq5
Step 3 -4y +z = 13 4y +4z = -8 5z = 5 z = 1 now plug into eq4 4 – 4y + z = 18 -4y + 1 = 13 -4y = 12 y = -3 now plug into eq1 x + y + z = 0 x -3 +1 = 0 x = 2 gives solution of (2, -3, 1)
This is one form for solving for variables using Gaussian Elimination.
Conclusion

There are several methods when dealing with monoalphabetic ciphers to come to an educated guess about the output of the plaintext. Through cribbing isomorphs, using HMM and the Gaussian Elimination algorithm, cryptanalysts have managed to take the guesswork out of decryption. Substitution, frequency testing, inversing, elimination and recursion give an educated cryptanalyst the tools they need to crack the code. By the way, if you manage to crib the rest of the cipher text in section one, let me know what you got.

Bibliography
Eddy, S. R. (1996). Hidden Markov models. Retrieved January 16, 2011, from zbit.uni-tuebingen.de: http://www.zbit.uni-tuebingen.de/pas/ws10/material/HMM_SeanEddy2002.pdf
Konheim, A. G. (2007). Computer Security and Cryptography. New Jersey: John Wiley & Sons, Inc.
Warakagoda, N. (1996, May 10). Assumptions in the theory of HMMs. Retrieved January 16, 2011, from jedliklphy.bme.hu: http://jedlik.phy.bme.hu/~gerjanos/HMM/node5.html#SECTION00230000000000000000
Wikipedia. (2011, January 5). Isomorphism. Retrieved January 16, 2011, from Wikipedia, The Free Encyclopedia: http://en.wikipedia.org/wiki/Isomorphism