### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# 661 Class Note for CS 35500 with Professor Nita-Rotaru at Purdue

### View Full Document

## 17

## 0

## Popular in Course

## Popular in Department

This 28 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Purdue University taught by a professor in Fall. Since its upload, it has received 17 views.

## Similar to Course at Purdue

## Reviews for 661 Class Note for CS 35500 with Professor Nita-Rotaru at Purdue

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/06/15

08355 Cryptography Lecture 3 Cryptanalysis of Vigenere cipher CS355 Lecture 3Fall 2008 1 Hw1 due Thursday Sept 11 in class 130 PM Pr 1 due by email to the TA Sept 12 midnight 1159PM CS355 Lecture 3FaI 2008 The Vigenere Cipher Definition Given m a positive integer P C 226 and K k1 k2 km a key we define Encryption ekp1 p2 pm p1k1 p2k239pmkm mOd 26 Decryption dkc1 cm c1k1 02k2 cm km mod 26 Example Plaintext CRYPTOGRAPHY Key LUCKLUCKLUCK Ciphertext NLAZEI IBLJ J CS355 Lecture 3Fall 2008 Security of Vigenere Cipher Vigenere masks the frequency with which a CS355 character appears in a language one letter in the ciphertext corresponds to multiple letters in the plaintext Makes the use of frequency analysis more difficult Any message encrypted by a Vigenere cipher is a collection of as many shift ciphers as there are letters in the key Lecture 3 Fall 2008 Vigenere Cipher Cryptanalysis Find the length of the key Divide the message into that many shift cipher encryptions Use frequency analysis to solve the resulting shift ciphers CS355 Lecture 3FaI 2008 How to Find the Key Length For Vigenere as the length of the keyword increases the letter frequency shows less Englishlike characteristics and becomes more random Two methods to find the key length Kasisky test 5 Index of coincidence Friedman CS355 Lecture 3FaI 2008 Kasisky Test Note two identical segments of plaintext will be encrypted to the same ciphertext if they occur in the text at the distance A AEO mod m m is the key length Algorithm Search for pairs of identical segments of length at least 3 Record distances between the two segments A1 A2 m divides gcdA1 A2 CS355 Lecture 3FaI 2008 Example of the Kasisky Test Key KINGKINGKINGKINGKING KING PT thesunandthemaninthe moon CT DPRYEVNTNBUKWIAOXBUK WWBT CS355 Lecture 3Fall 2008 Another Example 0 Moonsunstarsmoonsunsmooth Key alfa MNSLSSTLWSMZTNSFSSMZTTHSWW 12 12 8 0 Key length divides 12 8 it s not 3 it s either 2 or 4 CS355 Lecture 3Fall 2008 Index of Coincidence Friedman CS355 Informally Measures the probability that two random elements of the nletters string x are identical Definition Suppose x x1x2xn is a string of n alphabetic characters Then Cx the index of coincidence is C x Pxl x1 Lecture 3 Fall 2008 10 Index of Coincidence cont n 1139 Reminder binomial coefficient kn k the number of ways that kthings can be 39chosen39 from a set of n things Consider the plaintext x of size n and c0 c1 c25 are the number of occurrences with which A B Z appear in x We want to compute C x Pxl x1 CS355 Lecture 3Fall 2008 11 Example Consider the text THE INDEX OF COINCIDENCE Whatare c0 c1 025 CS355 Lecture 3Fall 2008 12 Begin Math CS355 Lecture 3Fall 2008 13 Elements of Probability Theory CS355 A random experiment has an unpredictable outcome Definition The sample space S of a random phenomenon is the set of all outcomes for a given experiment Definition The event E is a subset of a sample space an event is any collection of outcomes Lecture 3 Fall 2008 14 Basic Axioms of Probability If E is an event PrE is the probability that event E occurs then a O s PrA s 1 for any set A in S b PrS 1 where S is the sample space c If E1 E2 En is a sequence of mutually exclusive events that is Ei Ej O for all i j then PrE1 UEZUUEn 2PrEl i1 CS355 Lecture 3Fall 2008 15 Probability More Properties If E is an event and PrE is the probability that the event E occurs then PrE 1 PrE where E is the complimentary event of E If outcomes in S are equally like then PrE E S where l denotes the cardinality of the set CS355 Lecture 3FaI 2008 16 Example Random throw of a pair of dice What is the probability that the sum is 3 Solution Each dice can take six different values 1 23456 The number of possible events value of the pair of dice is 36 therefore each event occurs with probability 136 Examine the sum 3 12 21 The probability that the sum is 3 is 236 What is the probability that the sum is 11 What is the probability that the sum is 12 CS355 Lecture 3FaI 2008 17 End Math CS355 Lecture 3 Fall 2008 18 Index of Coincidence cont We can choose two elements out of the string of size n in 1 ways J o For each i there are Ci ways of choosing the elements to be i 2 CS355 Lecture 3FaI 2008 19 Example IC of a String Consider the text THE INDEX OF COINCIDENCE S 2CiCi 1 Wm There are 21 characters so n 21 S 25 IC 32 21 43 10 10 32 32 21 10 10 2120 34420 00809 C8355 Lecture 3FaI 2008 20 Index of Coincidence for a Language In this case n is very big so we can make an approximation S S Ci 1 2 2 26ici 26139 S i0 z i0 n nn 1 n2 l 2 THIS IS AN APPROXIMATION lF n is VERY BIG ci also very big pi is the probability with which character i appears in the given language C x E CS355 Lecture 3Fall 2008 21 Example IC of a Language C8355 For English Letter pi Letter pi Letter pi Letter pi A 082 H 061 O 075 V 010 B 015 I 070 P 019 W 023 C 028 J 002 Q 001 X 001 D 043 K 008 R 060 Y 020 E 127 L 040 S 063 Z 001 F 022 M 024 T 091 G 020 N 067 U 028 i25 16 x 21912 0065 i0 Lecture 3 Fall 2008 22 Find the Key Length Index of coincidence Friedman CS355 Lecture 3Fall 2008 23 Finding the Key Length q q1q2qn m is the key length lt lt Q77 CS355 ql qm qnm139gt yl 72 qm2 qn m2 gt y2 12m qn gt ym Lecture 3 Fall 2008 24 Guessing the Key Length If m is the key length then the text looks like English text i25 Cyl z 219 0065 V1 5 i s m i0 If m is not the key length the text looks like random text and 25 1 1 1 2 10 26xgg0038 CS355 Lecture 3Fall 2008 25 Finding the Key if Key Length Known Consider vectors yi and look for the most frequent letter Check if mapping that letter to e will not result in unlikely mapping for other letters If that s not the case look at the shift of the mapping that represents the letter of the key Repeat for each vector CS355 Lecture 3Fall 2008 26 Summary Vigenere cipher is vulnerable once the key length is found a cryptanalyst can apply frequency analysis CS355 Lecture 3FaI 2008 27 Recommended Reading for This Lecture Chapter 21 23 24 CS355 Lecture 3Fall 2008 28

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.