Caesar Cypher

manivar_813

Stallings_8e_Accessible_fullppt_03.html

Home >Information Systems homework help >Caesar Cypher

Cryptography and Network Security:Principles and Practice

Eighth Edition

Chapter 3

Classical Encryption Techniques

Front Cover: Cryptography and Network Security: Principles and Practice, Eighth Edition by Stallings

Definitions(1 of 2)

Plaintext

–An original message

Ciphertext

–The coded message

Enciphering/encryption

–The process of converting from plaintext tociphertext

Deciphering/decryption

–Restoring the plaintext from the ciphertext

Definitions(2 of 2)

Cryptography

–The area of study of the many schemes used forencryption

Cryptographic system/cipher

–A scheme

Cryptanalysis

–Techniques used for deciphering a message withoutany knowledge of the enciphering details

Cryptology

–The areas of cryptography and cryptanalysis

Figure 3.1 Simplified Model ofSymmetric Encryption

The simplified model illustrates flow, with steps listed below • Cap X from data block open parens plaintext close parens points as input to encryption algorithm with secret key cap K, shared by sender and recipient • Transmitted cipher text cap Y equals cap E open parens cap K, cap X close parens to decryption algorithm with K as secret key. • From this an arrow pointing to the right labelled as cap X equals cap D open parens K, cap Y close to data block open parens plaintext output close parens.

Symmetric Cipher Model

There are two requirements for secure use of conventionalencryption:

–A strong encryption algorithm
–Sender and receiver must have obtained copies of thesecret key in a secure fashion and must keep the keysecure

Figure 3.2 Model of SymmetricCryptosystem

A model illustrates flow with steps summarized below. • X leads from message source to encryption algorithm, which receives input from key source. • Y=E(K, X) leads to decryption algorithm, with flow also to cryptanalyst, which produces X hat and K hat. • The key source also sends K through secure channel to decryption algorithm. • Decryption algorithm sends X to destination.

Cryptographic Systems

Characterized along three independent dimensions:

The type of operations used for transforming plaintext tociphertext

–Substitution
–Transposition

The number of keys used

–Symmetric, single-key, secret-key, conventionalencryption
–Asymmetric, two-key, or public-key encryption

The way in which the plaintext is processed

–Block cipher
–Stream cipher

Cryptanalysis and Brute-Force Attack

Cryptanalysis

–Attack relies on the nature of the algorithm plus someknowledge of the general characteristics of theplaintext
–Attack exploits the characteristics of the algorithm toattempt to deduce a specific plaintext or to deduce thekey being used

Brute-force attack

–Attacker tries every possible key on a piece ofciphertextuntil an intelligible translation into plaintext isobtained
–On average, half of all possible keys must be tried toachieve success

Table 3.1 Types of Attacks onEncrypted Messages

Type of Attack	Known to Cryptanalyst
Ciphertext Only	Encryption algorithm Ciphertext
Known Plaintext	Encryption algorithm Ciphertext One or more plaintext–ciphertext pairs formed with the secret key
Chosen Plaintext	Encryption algorithm Ciphertext Plaintext message chosen by cryptanalyst, together with its correspondingciphertextgenerated with the secret key
Chosen Ciphertext	Encryption algorithm Ciphertext Ciphertext chosen by cryptanalyst, together with its corresponding decryptedplaintext generated with the secret key
Chosen Text	Encryption algorithm Ciphertext Plaintext message chosen by cryptanalyst, together with its correspondingciphertextgenerated with the secret key Ciphertext chosen by cryptanalyst, together with its corresponding decryptedplaintext generated with the secret key

Encryption Scheme Security

Unconditionally secure

–No matter how much time an opponent has, it isimpossible for him or her to decrypt theciphertextsimply because the required information is not there

Computationally secure

–The cost of breaking the cipher exceeds the value ofthe encrypted information
–The time required to break the cipher exceeds theuseful lifetime of the information

Brute-Force Attack

Involves trying every possible key until an intelligibletranslation of theciphertextinto plaintext is obtained
On average, half of all possible keys must be tried toachieve success
To supplement the brute-force approach, some degree ofknowledge about the expected plaintext is needed, andsome means of automatically distinguishing plaintext fromgarble is also needed

Strong Encryption

The termstrongencryptionrefers to encryption schemesthat make it impractically difficult for unauthorized personsor systems to gain access to plaintext that has beenencrypted
Properties that make an encryption algorithm strong are:

–Appropriate choice of cryptographic algorithm
–Use of sufficiently long key lengths
–Appropriate choice of protocols
–A well-engineered implementation
–Absence of deliberately introduced hidden flaws

Substitution Technique

Is one in which the letters of plaintext are replaced by otherletters or by numbers or symbols
If the plaintext is viewed as a sequence of bits, thensubstitution involves replacing plaintext bit patterns withciphertextbit patterns

Caesar Cipher

Simplest and earliest known use of a substitution cipher
Used by Julius Caesar
Involves replacing each letter of the alphabet with theletter standing three places further down the alphabet
Alphabet is wrapped around so that the letter following Zis A

plain: meet me after the toga party

cipher: PHHW PH DIWHU WKH WRJD SDUWB

Caesar Cipher Algorithm

Can define transformation as:

a b c d e f g hij k l m n o p q r s t u v w x y z

D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

Mathematically give each letter a number

b c d e f g hij 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

Algorithm can be expressed as:

c = E(3, p) = (p + 3) mod (26)

A shift may be of any amount, so that the general Caesar algorithm is:

C = E(k , p ) = (p + k ) mod26

Where k takes on a value in the range 1 to 25; the decryption algorithm issimply:

p = D(k , C ) = (C − k ) mod26

Figure 3.3 Brute-Force Cryptanalysisof Caesar Cipher

The table shows the Brute-Force Cryptanalysis of Caesar Cipher with the encryption and decryption text using 25 keys.

Sample of Compressed Text

Figure 3.4Sample of Compressed Text

MonoalphabeticCipher

Permutation

–Of a finite set of elementsSis an ordered sequence ofall the elements ofS, with each element appearingexactly once

If the “cipher” line can be any permutation of the 26alphabetic characters, then there are 26! orgreater than4 x 1026possible keys

–This is 10 orders of magnitude greater than the keyspace for DES
–Approach is referred to as amonoalphabeticsubstitutioncipher because a single cipher alphabet isused per message

Figure 3.5 Relative Frequency ofLetters in English Text

A graph plots the relative frequency (%) for each letter in the English alphabet.

MonoalphabeticCiphers

Easy to break because theyreflect the frequency data of theoriginal alphabet
Countermeasure is to providemultiple substitutes(homophones) for a single letter
Digram

–Two-letter combination
–Most common isth

Trigram

–Three-letter combination
–Most frequent isthe

PlayfairCipher

Best-known multiple-letter encryption cipher
Treatsdigramsin the plaintext as single units andtranslates these units intociphertextdigrams
Based on the use of a 5×5 matrix of letters constructedusing a keyword
Invented by British scientist Sir Charles Wheatstone in1854
Used as the standard field system by the British Army inWorld War I and the U.S. Army and other Allied forcesduring World War II

PlayfairKey Matrix

Fill in letters of keyword (minus duplicates) from left to rightand from top to bottom, then fill in the remainder of thematrix with the remaining letters in alphabetic order
Using the keyword MONARCHY:

M	O	N	A	R
C	H	Y	B	D
E	F	G	I/J	K
L	P	Q	S	T
U	V	W	X	Z

Figure 3.6 Relative Frequency ofOccurrence of Letters

The approximate data for each curve are summarized below. • A horizontal line at 0.32 represents random polyalphabetic • The curve for plaintext falls from (0, 1.0) through (8, 0.32) to (26, 0) • The curve for Playfair falls from (0, 0.7) through (12.5, 0.32) to (26, 0) • The curve for Vignere falls form (0, 0.57) through (10.5, 0.32) to (26, 0.12).

Hill Cipher

Developed by the mathematician Lester Hill in 1929
Strength is that it completely hides single-letter frequencies

–The use of a larger matrix hides more frequencyinformation
–A 3 x 3 Hill cipher hides not only single-letter but alsotwo-letter frequency information

Strong against aciphertext-only attack but easily brokenwith a known plaintext attack

Polyalphabetic Ciphers

Polyalphabetic substitution cipher

–Improves on the simplemonoalphabetictechnique byusing differentmonoalphabeticsubstitutions as oneproceeds through the plaintext message

All these techniques have the following features incommon:

–A set of relatedmonoalphabeticsubstitution rules isused
–A key determines which particular rule is chosen for agiven transformation

VigenèreCipher

Best known and one of the simplest polyalphabeticsubstitution ciphers
In this scheme the set of relatedmonoalphabeticsubstitution rules consists of the 26 Caesar ciphers withshifts of 0 through 25
Each cipher is denoted by a key letter which is theciphertextletter that substitutes for the plaintext letter a

Example ofVigenèreCipher

To encrypt a message, a key is needed that is as long asthe message
Usually, the key is a repeating keyword
For example, if the keyword isdeceptive, the message “weare discovered save yourself” is encrypted as:

key:deceptivedeceptivedeceptive

plaintext:wearediscoveredsaveyourself

ciphertext: ZICVTWQNGRZGVTWAVZHCQYGLMGJ

VigenèreAutokeySystem

A keyword is concatenated with the plaintext itself toprovide a running key
Example:

key:deceptivewearediscoveredsav

plaintext:wearediscoveredsaveyourself

ciphertext: ZICVTWQNGKZEIIGASXSTSLVVWLA

Even this scheme is vulnerable to cryptanalysis

–Because the key and the plaintext share the samefrequency distribution of letters, a statistical techniquecan be applied

VernamCipher

Figure 3.7VernamCipher

A diagram has plaintext (p sub i) and cryptographic bit stream (k sub i), from key stream generator, each leading to X O R operation. Then cipher text (c sub i) leads to another X O R operation, meeting another cryptographic bit steam (k sub i) from a key stream generator, resulting in output plaintext (p sub i). Two diagrams illustrate a three-rotor machine, with fast rotor on the left, medium rotor in the middle, and slow rotor on the right. Letters A through Z are listed in order down the columns, aligned with numbers on the left and right sides of each rotor. The left numbers are in order and the right numbers appear to be in random order. Matching numbers within the rotors are connected. The direction of motion is shown extending down into the top of the rotors. Between the two machines, the numbers in the medium rotor and slow rotor are in the same order. From the initial setting to the setting after one keystroke, the numbers in the fast rotor are moved one letter down, such that the numbers at A are now at B and the numbers at Z are now at A. Three connections within the rotors, beginning at A, B, and C, respectively, for each machine, are summarized below.

One-Time Pad

Improvement toVernamcipherproposed by an Army SignalCorp officer, JosephMauborgne
Use a random key that is aslong as the message so thatthe key need not be repeated
Key is used to encrypt anddecrypt a single message andthen is discarded
Each new message requires anew key of the same length asthe new message

Scheme is unbreakable

–Produces random outputthat bears no statisticalrelationship to theplaintext
–Because theciphertextcontains no informationwhatsoever about theplaintext, there is simplyno way to break the code

Difficulties

The one-time pad offers complete security but, in practice, has twofundamental difficulties:

–There is the practical problem of making large quantities ofrandom keys

Any heavily used system might require millions of randomcharacters on a regular basis

–Mammoth key distribution problem

For every message to be sent, a key of equal length is neededby both sender and receiver

Because of these difficulties, the one-time pad is of limited utility

–Useful primarily for low-bandwidth channels requiring very highsecurity

The one-time pad is the only cryptosystem that exhibitsperfectsecrecy(see Appendix F)

Rail Fence Cipher

Simplest transposition cipher
Plaintext is written down as a sequence of diagonals andthen read off as a sequence of rows
To encipher the message “meet me after the toga party”with a rail fence of depth 2, we would write:

m e m a t r h t g p r y

e t e f e t e o aat

Encrypted message is:

MEMATRHTGPRYETEFETEOAAT

Row Transposition Cipher

Is a more complex transposition
Write the message in a rectangle, row by row, and read themessage off, column by column, but permute the order ofthe columns

–The order of the columns then becomes the key to thealgorithm

Key:4 3 1 2 5 6 7

Plaintext: a tta c k p

o s t p o n e

d u n til t

w o a mx y z

Ciphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ

Summary

Present an overview of the main concepts of symmetriccryptography
Explain the difference between cryptanalysis and brute-force attack
Understand the operation of amonoalphabeticsubstitutioncipher

Understand the operation of a polyalphabetic cipher
Present an overview of the Hill cipher

Copyright