Discussion on The Vigenère Cipher

anithareddy

Week4Lecture1.pptx

Home >Computer Science homework help >Discussion on The Vigenère Cipher

Fundamentals of Cryptography Week 4

Agenda

Week 4 Overview

Reading

Lecture

Discussion Question

Components of Cryptography

Week 5 Pre-view

Week 4 Overview

Reading – Chapter 3 – Components of Cryptography

Lecture – You are watching/listening to it now!

Week 4 Overview

Discussion Question 2

Primary Response: Primary Discussion Response is due by Wednesday (11:59:59pm Eastern Time Zone (ET))

Peer Response(s): Peer Response(s) are due by Sunday (11:59:59pm ET)

Primary Task Response:

Please provide a detailed response to the below to include specific details and examples.

What is the Vigenère Cipher?

How does it work?

Although the Vigenère cipher was an improvement upon previous historical encryption techniques, it is still vulnerable. How would an attacker break a Vigenère-style cipher?

Week 4 Overview

Try your hand!

1. Encrypt the below message using the Vigenère cipher.

NOW IS THE TIME FOR ALL GOOD MEN TO COME TO THE AID OF THEIR COUNTRY.

2. Decrypt the below message using the Vigenère cipher. The passphrase is ‘crypto.’

Vyc Kbugecgx Qkgftk kcj btosnfntw pa dyiasorrxvwce Zatwuv bt Owivltks ke rwx 16hj tccmitp

3. Create a Vigenère cipher of your own and see who can crack it! Toward the end of the week, provide the solution to your cipher.Peer Response(s): Read the responses from your peers, attempt to crack the cipher codes presented and offer a constructive critique or additional information that adds substantively to the discussions. Be sure to acknowledge any outside sources you use.

Categories of Cryptosystems

Two-way cryptography -

Organization of Cryptosystems

Two-Way Cryptography

Symmetric

Asymmetric

Steganography

Message Integrity Controls

Stream

Block

Factoring the Product of Large Primes

Discreet Logarithms

Two-way Cryptography

Example of two-way encryption

In two-way encryption, data or information was decoded to a new format but it can be completely converted back to the original value. This is use to authoring other parties to read the message through the encryption key. Sometimes, developer use two-way encryption to encrypt some configuration data.

Two-way Cryptography

There are many algorithm for encrypt/decrypt, the popular function are DES, AES…etc. Below code implement AES encryption in python language:

Steganography

Art of hiding information

Plaintext hidden/disguised

Prevents a third party from knowing that a secret message exists

Traditionally accomplished in a number of ways:

Physical techniques

Null ciphers

Null Cipher

Example Cipher text:

News Eight Weather: Tonight increasing snow. Unexpected precipitation smothers eastern towns. Be extremely cautious and use snowtires especially heading east. The highway is not knowingly slippery. Highway evacuation is suspected. Police report emergency situations in downtown ending near Tuesday.

Taking the first letter in each word successively yields the real message: "Newt is upset because he thinks he is President."

Image-based Steganography

RGB* values altered to contain a message

File sizes are identical

Different hash values

E1089197693F6C4C26E0033F8C8AF00C

57694B77DCB55C543C6C0BA8E1FF2D17

Digital Watermarking

Digital watermarks are visible or invisible markings embedded within a digital file to indicate copyright or other handling instructions, or to embed a fingerprint to detect unauthorized copying and distribution of images

Invisible watermarks are embedded into the data in such a way that the changes made to the pixel are perceptually not noticed. Invisible watermarks are used as evidence of ownership and to detect misappropriated images.

Substitution and Transposition

Cryptography

Substitution

Simple

Polyalphabetic

Transposition

Scytale

Running Key

Codes

Substitution Ciphers

Four-square

Playfair

Caesar Cipher:

Shift (rotate) alphabet (move letters three spaces)

A B C D E F ... BAD

D E F G H I ... EDG

Scramble alphabet:

Substitute one letter for another

A B C D E F ... BAD

Q E Y R T M ... EQR

The simple substitution cipher is a cipher that has been in use for many hundreds of years (an excellent history is given in Simon Singhs 'the Code Book'). It basically consists of substituting every plaintext character for a different ciphertext character. It differs from the Caesar cipher in that the cipher alphabet is not simply the alphabet shifted, it is completely jumbled.

The simple substitution cipher offers very little communication security, and it will be shown that it can be easily broken even by hand, especially as the messages become longer (more than several hundred ciphertext characters).

Substitution Ciphers

Four-square

The Four-square cipher encrypts pairs of letters (like playfair), which makes it significantly stronger than substitution ciphers etc. since frequency analysis becomes much more difficult.

Felix Delastelle (1840 - 1902) invented the four-square cipher, first published in a book in 1902. Delastelle was most famous for his invention of several systems of polygraphic substitution ciphers including bifid, trifid, and the four-square cipher.

The four-square cipher uses four 5 by 5 matrices arranged in a square. Each of the 5 by 5 matrices contains 25 letters, usually the letter 'j' is merged with 'i' (wikipedia says 'q' is omitted, it is not very important since both q and j are rather rare letters). In general, the upper-left and lower-right matrices are the "plaintext squares" and each contain a standard alphabet. The upper-right and lower-left squares are the "ciphertext squares" and contain a mixed alphabetic sequence.

The ciphertext squares can be generated using a keyword (dropping duplicate letters), then fill the remaining spaces with the remaining letters of the alphabet in order. Alternatively the ciphertext squares can be generated completely randomly. The four-square algorithm allows for two separate keys, one for each of the two ciphertext matrices.

The four-square cipher can be easily cracked with enough ciphertext. It is quite simple to determine the key if both plaintext and ciphertext are known, and for this reason guessing parts of the plaintext is a very effective way of cracking this cipher. If a portion of the plaintext is known or can be guessed this should be exploited first to determine as much of the key as possible, then more guessing can be applied or other techniques described below.

Compared to the Playfair cipher, a four-square cipher will not show reversed ciphertext digraphs for reversed plaintext digraphs (e.g. the digraphs AB BA would encrypt to some pattern XY YX in Playfair, but not in four-square). This, of course, is only true if the two keywords are different. Another difference between four-square and Playfair which makes four-square a stronger encryption is the fact that double letter digraphs will occur in four-square ciphertext.

The four-square cipher is a stronger cipher than Playfair, but it is more cumbersome because of its use of two keys and preparing the encryption/decryption sheet can be time consuming. Given that the increase in encryption strength afforded by four-square over Playfair is marginal and that both schemes are easily defeated if sufficient ciphertext is available, Playfair was much more common.

Substitution Ciphers

Playfair

The Playfair cipher was the first practical digraph substitution cipher. The scheme was invented in 1854 by Charles Wheatstone, but was named after Lord Playfair who promoted the use of the cipher. The technique encrypts pairs of letters (digraphs), instead of single letters as in the simple substitution cipher. The Playfair is significantly harder to break since the frequency analysis used for simple substitution ciphers does not work with it. Frequency analysis can still be undertaken, but on the 25*25=625 possible digraphs rather than the 25 possible monographs. Frequency analysis thus requires much more ciphertext in order to work. For a tutorial on breaking Playfair with a simulated annealing algorithm, see Cryptanalysis of the Playfair Cipher.

It was used for tactical purposes by British forces in the Second Boer War and in World War I and for the same purpose by the Australians during World War II. This was because Playfair is reasonably fast to use and requires no special equipment. A typical scenario for Playfair use would be to protect important but non-critical secrets during actual combat. By the time the enemy cryptanalysts could break the message the information was useless to them [1].

Substitution Ciphers – Playfair continued

From Kahn's 'The CodeBreakers’:

Perhaps the most famous cipher of 1943 involved the future president of the U.S., J. F. Kennedy, Jr. On 2 August 1943, Australian Coastwatcher Lieutenant Arthur Reginald Evans of the Royal Australian Naval Volunteer Reserve saw a pinpoint of flame on the dark waters of Blackett Strait from his jungle ridge on Kolombangara Island, one of the Solomons. He did not know that the Japanese destroyer Amagiri had rammed and sliced in half an American patrol boat PT-109, under the command of Lieutenant John F. Kennedy, United States Naval Reserve. Evans received the following message at 0930 on the morning of the 2 of August 1943:

Polyalphabetic Ciphers – Vigenère Cipher

This is a simple substitution cipher that uses multiple alphabets rather than just one

Encrypt the plaintext ‘FEEDBACK’ using a key of 3241

Vigenère Cipher

The Vigenère square or Vigenère table, also known as the tabula recta, can be used for encryption and decryption.

What is now known as the Vigenère cipher was originally described by Giovan Battista Bellaso in his 1553 book La cifra del. Sig. Giovan Battista Bellaso.

He built upon the tabula recta of Trithemius, but added a repeating "countersign" (a key) to switch cipher alphabets every letter. Whereas Alberti and Trithemius used a fixed pattern of substitutions, Bellaso's scheme meant the pattern of substitutions could be easily changed simply by selecting a new key. Keys were typically single words or short phrases, known to both parties in advance, or transmitted "out of band" along with the message. Bellaso's method thus required strong security for only the key. As it is relatively easy to secure a short key phrase, say by a previous private conversation, Bellaso's system was considerably more secure.[

Blaise de Vigenère published his description of a similar but stronger autokey cipher before the court of Henry III of France, in 1586. Later, in the 19th century, the invention of Bellaso's cipher was misattributed to Vigenère. David Kahn in his book The Codebreakers lamented the misattribution by saying that history had "ignored this important contribution and instead named a regressive and elementary cipher for him [Vigenère] though he had nothing to do with it".

The Vigenère cipher gained a reputation for being exceptionally strong. Noted author and mathematician Charles Lutwidge Dodgson (Lewis Carroll) called the Vigenère cipher unbreakable in his 1868 piece "The Alphabet Cipher" in a children's magazine.

In 1917, Scientific American described the Vigenère cipher as "impossible of translation".[5] This reputation was not deserved. Charles Babbage is known to have broken a variant of the cipher as early as 1854; however, he didn't publish his work.[6]

Kasiski entirely broke the cipher and published the technique in the 19th century. Even before this, though, some skilled cryptanalysts could occasionally break the cipher in the 16th century.

The Vigenère cipher is simple enough to be a field cipher if it is used in conjunction with cipher disks.[7] The Confederate States of America, for example, used a brass cipher disk to implement the Vigenère cipher during the American Civil War. The Confederacy's messages were far from secret and the Union regularly cracked their messages. Throughout the war, the Confederate leadership primarily relied upon three key phrases, "Manchester Bluff", "Complete Victory" and, as the war came to a close, "Come Retribution".

Gilbert Vernam tried to repair the broken cipher (creating the Vernam-Vigenère cipher in 1918), but, no matter what he did, the cipher was still vulnerable to cryptanalysis. Vernam's work, however, eventually led to the one-time pad, a theoretically unbreakable cipher.

Vigenère Cipher

Confederate cipher wheel, captured at the surrender of Mobile, Alabama, in May 1865 – National Cryptologic Museum

One-time Pads (OTPs)

It may be surprising to the reader that there exist simple ``perfect'' encryption methods, meaning that there is a mathematical proof that cryptanalysis is impossible. The term ``perfect'' in cryptography also means that after an opponent receives the ciphertext he has no more information than before receiving the ciphertext.

The simplest of these perfect methods is called the one-time pad.

The keys are the same size (length) as the plaintext message, and the keys must be randomly generated for this scheme to be truly effective

It is the requirement for randomness that makes OTPs particularly challenging to generate, since the best that we can typically achieve when generating such pads using computer processors are pseudo-random values.

he One-Time Pad starts with a random sequence of letters for the standard text (which is the key in this case). Suppose for example one uses RQBOPS as the standard text, assuming these are 6 letters chosen completely at random, and suppose the message is the same. Then encryption uses the same method as with the Beale Cipher, except that the standard text or key is not a quotation from English, but is a random string of letters.

Standard text (random key): RQBOPS Message: ATTACK Encrypted message: RJUORC So, for example, the third column uses the letter B, representing a rotation of 1, to transform the plaintext letter T into the ciphertext letter U. The receiver must have the same random string of letters around for decryption: RQBOPS in this case. As the important part of this discussion, I want to show that this method is perfect as long as the random standard text letters are kept secret. Suppose the message is GIVEUP instead of ATTACK. If one had started with random letters LBYKXN as the standard text, instead of the letters RQBOPS, then the encryption would have taken the form:

Standard text (random key): LBYKXN Message: GIVEUP Encrypted message: RJUORC The encrypted message (ciphertext) is the same as before, even though the message is completely different. An opponent who intercepts the encrypted message but knows nothing about the random standard text gets no information about the original message, whether it might be ATTACK or GIVEUP or any other six-letter message. Given any message at all, one could construct a standard text so that the message is encrypted to yield the ciphertext RJUORC. An opponent intercepting the ciphertext has no way to favor one message over another. It is in this sense that the one-time pad is perfect.

In this century spies have often used one-time pads. The only requirement is text (the pad) of random letters to use for encryption or decryption. (In fact, even now I would not want to be found in a hostile country with a list of random-looking letters.) The party communicating with the spy must have exactly the same text of random letters. This method requires the secure exchange of pad characters: as many such characters as in the original message. In a sense the pad behaves like the encryption key, except that here the key must be as long as the message. But such a long key defeats a goal of cryptography: to reduce the secrecy of a long message to the secrecy of a short key. If storage and transmission costs keep dropping, the one-time pad might again become an attractive alternative.

Codes

A group of navy ships is operating under conditions of radio silence to avoid detection by the enemy

Maneuvering signals and comments are communicated by flag signals

A separate flag is used for each letter

To send a paragraph of information would be a real workout for the signalmen, so codes are used to minimize the effort and time involved; for instance, the letters BZ are the signal that the addressee performed well or did a good job

Transposition Ciphers

Columnar – rearranging the message in a table

Plaintext “This is an example of transposition”

Ciphertext “tsaonihamfstinptpiselrooixeasn”

Key: grid shape and reading direction

Example: the Spartan Scytale

In transposition ciphers, the letters of the message are simply rearranged, effectively generating an anagram.

In order for transposition to be effective, the rearrangement of letters needs to follow a straightforward system, one that has been previously agreed by the sender and receiver, but kept secret from the enemy. In this section we explore two types of transposition: the rail fence cipher and the Latin Square.

The rail fence cipher involves writing the message such that alternate letters are written on separate upper and lower lines. The sequence of letters on the upper line is then followed by the sequence on the lower line, to create the final encrypted message.

The Latin Square is an intriguing example of a transposition cipher. It is made up of a series of 5-letter words arranged in a square, found on the walls of Roman villas in Pompeii and Cirencester.

The square reads 'rotas opera tenet arepo sator', which roughly means 'he who guides the plough sows the seed'. You might notice that the square is highly symmetrical - it can be read left to right, right to left, upwards or downwards.

However, this harmless symmetrical motto disguises a much more important message, which can be found by transposing the letters. An example of the Latin Square, displayed at the Manchester Museum, University of Manchester, is shown on the right.

Modern Cryptanalysis

Levels of Attack:

Ciphertext only (cryptanalyst sees only the enciphered text)

Plaintext attack (cryptanalyst has both the enciphered text and the clear message that it came from)

Chosen plaintext attack (cryptanalyst can chose the clear message that is enciphered, as often as needed)

Chosen ciphertext attack (cryptanalyst can chose ciphertexts to be deciphered as often as necessary, but is not given the key(s)).

The "philosophy" of modern cryptanalysis is embodied in Kerckhoffs' principle, which was formulated in the book La cryptographie militaire (1883) by the Dutch philologist Jean Guillaume Hubert Victor François Alexandre Auguste Kerckhoffs von Nieuwenhof, as he is called in all his full glory.

Kerckhoffs' Principle: The security of a cryptosystem must not depend on keeping secret the crypto-algorithm. The security depends only on keeping secret the key.

Week 5 Overview

Reading – Chapter 4 – Algorithms and Ciphers

Lecture

Quiz 3

dark

On a

ptuf

NeQj

Data Block

Cryptosystem

Cipher Block

Ciphertext

Key

Questions?