22-02-2013, 02:55 PM
lassical Ciphers and their Cryptanalysis
lassical Ciphers.pdf (Size: 162.13 KB / Downloads: 20)
Introduction to Cryptography
• Terms and Concepts
– Cryptography: Performing encryption and decryption
– Encryption: the process of transforming a message so that its meaning
is not obvious
– Decryption: the process of transforming an encrypted message back
into its original, normal form
– Cryptosystem: A system for encryption and decryption
– Plaintext: Original, unencrypted, form of a message
– Ciphertext: The encrypted form of a message
– Formal notation: We seek a cryptosystem for which P = D(E(P)), where
P is the Plaintext, E is the Encryption rule, C = E(P) is the ciphertext, D
is the Decryption rule.
Cryptanalysis
• Cryptanalysis is the process of breaking an encryption.
• A cryptanalyst can attempt to do any or all six of the following:
– Break a single message
– Recognize patterns in encrypted messages, to be able to break
subsequent ones by applying a straightforward decryption algorithm
– Infer some meaning regarding the communication (for example, the
length of the communication, the frequency of the communication)
– Deduce the key to break subsequent messages easily
– Find weaknesses in the implementation or the environment of use of
encryption
– Find general weaknesses in an encryption algorithm, without
necessarily having intercepted any messages
• A cryptanalyst would work with a variety of pieces of information:
– Encrypted messages, known encryption algorithms, intercepted
plaintext, data items known or suspected to be in a ciphertext message,
mathematical and/or statistical tools and techniques, properties of
languages, computers, etc
Substitution Ciphers
• Idea: Use a correspondence table and substitute a character or symbol for
each character of the original message
• Goal of substitution is Confusion: an attempt to make it difficult for a
cryptanalyst or an intruder to determine how a message and key were
transformed into ciphertext.
• Caesar Cipher
– Each letter is translated to the letter a fixed number of times after it in the
alphabet table
– Caesar cipher uses shift by 3.
Cryptanalysis of the Caesar Cipher
• On a closer look at the result of applying Caesar’s encryption technique to
“TREATY IMPOSSIBLE”, we get the following clues from the ciphertext
even if did not know the plaintext:
– The break in between the two words is preserved in the ciphertext
– Double letters are preserved (SS is translated to vv)
– When a letter is repeated, it maps to the same ciphertext as before (look at
letters T, I, E in the plaintext)
• Consider you are given the following ciphertext and you want to determine
the plaintext: “wklv phvvdjh lv qrw wrr kdug wr euhdn”
– As a start, assume that the coder was lazy, and has allowed the blank space to
be translated to itself. Hence, the message has actually been enciphered with a
27-symbol alphabet: A through Z and a blank-space separating the words.
– If this assumption is true, knowing where the spaces helps to find out what are
the small words.
– The English language has very few short words like am, is, to, be, he, she, we,
and, you, are, and so on.
• There is a strong clue in the repeated r of the word wrr.
– Two very common three-letter words having the pattern xyy are see and too;
other less common possibilities are add, odd and off. Try the more common
word first.
One-Time Pads
• The key size is as long as the message to be encrypted.
• The key is a non-repeating, arbitrarily long series of unpredictable
(random) numbers, to which both sender and receiver, but nobody
else has access.
• One-time pad is the only theoretically unbreakable cipher, because:
– If the random numbers are truly unpredictable and non-repeating, there
is no way to tell how a particular plaintext character was enciphered.
Even if it is known that A is enciphered to W this time, that gives no
knowledge about the encipherment of the next A or the plaintext
character that follows A.
Cryptanalysis of Book Ciphers
• The probability that a given character in the plaintext is any one of E,
A, O, T, N or I is close to 50%.
• Similarly, the probability that a given character in the key (taken from
a book) is any one of E, A, O, T, N or I is close to 50%.
• Hence, the probability of the ciphertext being one of the six
characters is 0.5 * 0.5 = 25%.
• To break the cipher, assume that each letter of the ciphertext comes
from a situation in which the plaintext letter (row selector) and the
key letter (column selector) are both one of the six most frequent
letters.