Free Essay
Intro to Cribbing Isomophs
In:
Computers and Technology
Submitted By waughj
Words 1482
Pages 6
 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 ciphertext 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 cryptotext 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 ciphertext.
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 ciphertext, based on partial knowledge of the plaintext. (Konheim, 2007) It is determined that with a partial knowledge of plaintext, cryptotext messages can be deduced by using the cribbing technique. Isomorphs are two like objects, in this case monoalphabetic text, that exhibit the same or similar structure. Isomorphism can be defined as, “a bijective map f such that both f and its inverse f1 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 ciphertext.
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 ciphertext 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 highfrequency ciphertext 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 monoalphabetic 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 ciphertext are unknown but what is known is the output or the ciphertext. 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 statetransition 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 ForwardBackward 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 ciphertext * 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.unituebingen.de: http://www.zbit.unituebingen.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