### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Introduction To Cryptography CS 35500

Purdue

GPA 3.68

### View Full Document

## 49

## 0

## Popular in Course

## Popular in ComputerScienence

This 81 page Class Notes was uploaded by Nick Rowe on Saturday September 19, 2015. The Class Notes belongs to CS 35500 at Purdue University taught by Staff in Fall. Since its upload, it has received 49 views. For similar materials see /class/208086/cs-35500-purdue-university in ComputerScienence at Purdue University.

## Reviews for Introduction To Cryptography

### 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: 09/19/15

Introduction to Cryptography CS 355 Lecture 4 The Vigen re Cipher CS 355 Fall 2005 Lecture 4 Lecture Outline Vigenere cipher Attacks on Vigenere Kasisky Test Index of Coincidence Frequency analysis CS 355 Fall 2005 Lecture 4 2 Towards the Polyalphabctic Substitution Ciphers Main weaknesses of monoalphabetic substitution ciphers each letter in the ciphertext corresponds to only one letter in the plaintext letter Idea for a stronger cipher 1460 s by Alberti use more than one cipher alphabet and switch between them when encrypting different letters Developed into a practical cipher by Vigenere published in 1586 CS 355 Fall 2005 Lecture 4 3 The Vigen re Cipher Definition Given m a positive integer P C 226 and K k1 k2 km a key we define Encryption ekp1 p2 pm p1k1 p2k2pmkm mod 26 Decryption dkc1 c2 cm c1k1 c2k2 cm km mod 26 Example Plaintext CRYPTOGRAPHY Key LUCKLUCKLUCK Ciphertext NLAZEI IBLJ J CS 355 Fall 2005 Lecture 4 Security of Vigenere Cipher Vigenere masks the frequency with which a 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 CS 355 by a Vigenere cipher is a collection of as many shift ciphe are letters in the key Fall 2005 Lecture 4 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 how CS 355 Fall 2005 Lecture 4 6 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 3 length C Kasisky test Index of coincidence Friedman CS 355 Fall 2005 Lecture 4 Kasisky Test Note two identical segments of plaintext will be encrypted to the same ciphertext if the they occur in the text at the distance A A20 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 CS 355 Fall 2005 Lecture 4 Example of the Kasisky Test Key KINGKINGKINGKINGKINGKING PT thesunandthemaninthemoon CT DPRYEVNTNBUKWIAOXBUKWWBT CS 355 Fall 2005 Lecture 4 9 Index of Coincidence Friedman CS 355 Informally Measures the probability that two random elements of the nletters string x are iden cal Definition Suppose x x1x2xn is a string of n alphabetic characters Then lcx the index of coincidence is 10x Px 39 Fall 2005 Lecture 4 10 Index of Coincidence cont Reminder binomial coefficient k kn k Consider the plaintext x and f0 f1 f25 are the frequencies with which A B Z appear in x and p0 p1 p25 are the probabilities with which A B Z appear in x We want to compute lcx CS 355 Fall 2005 Lecture 4 11 Index of Coincidence cont We can choose two elements out of the string of size n in ways For each i there are ways of choosing the elements to be i 2 S f s s 2 22 21203 1 2f S 2 Cx n 10nn1 z 102 ngi K2 CS 355 Fall 2005 Lecture 4 Index of Coincidence of English For English 8 25 and Iq can be estimated Letter pi Letter pi 061 V7 010 070 023 002 001 008 020 040 001 024 067 139 25 10 x Z pf 0065 i0 CS 355 Fall 2005 Lecture 4 Finding the Key Length y y1y2yn m is the key length Y1 lt72ym2 yn m2 gt Y2 ym CS 355 Fall 2005 Lecture 4 14 Guessing the Key Length If m is the key length then the text looks like English text i225 10yl pr 20065 Vlsis m i0 If m is not the key length the text looks like random text and 10 z Xi 26 x 220038 i O 2 6226 CS 355 Fall 2005 Lecture 4 15 Summary Vigenere cipher is vulnerable once the key length is found a cryptanalyst can apply frequency analysis CS 355 Fall 2005 Lecture 4 16 Recommended Reading for This Lecture Trappe amp Washington Section 23 The Code Book Chapter 2 CS 355 Fall 2005 Lecture 4 17 Coming Attractions Enigma Machine Recommended Reading Trappe amp Washington 212 The Code Book Chapters 3 amp 4 CS 355 Fall 2005 Lecture 4 CS355 08355 Cryptography Lecture 2 Shift cipher substitution cipher Vigenere cipher Lecture 2 Fall 2008 Course Information CS355 Meetings TTh130245 LWSN B134 Professor contact info Office 2142J Email crisncs Office hours by appointment TA Camille Gaspard Office LWSN B116 Office hours TTh 300 400 PM Email cgaspardcs Class webpage httphomesceriaspurdueeducrisncoursesc5355Fal2008 Lecture 2 Fall 2008 Class Attendance Slides will be available before lecture but they do not include all details class attendance is strongly recommended Email me if you must miss lectures If you miss a lecture it is your responsibility to find out what happened in class Please join the mailing list cs355cs CS355 Lecture 2Fal 2008 Grading Policy CS355 Written Assignments 5 Projects 3 Midterm Exam Final Exam Class Participation Lecture 2 Fall 2008 20 20 20 30 10 Homework Homework must by TYPED IF IT S NOT TYPED WE DO NOT GRADE IT Homework is due in class at 130 If you use extra days you can email it use PDF format Homework will be returned in class at 130 You must work alone on the written homework CS355 Lecture 2Fal 2008 Extra Days Every student has 5 extra days for all the written assignments and 2 extra days for individual programming projects YOU DECIDE HOW TO USE THEM Email me and the TA with name and number of extra days used for an assignment 1 minute late counts as 1 extra day After using your extra days no late homework or project will be accepted CS355 Lecture 2Fal 2008 Exams CS355 Midterm proposed date week Oct 7 9 Final check university web page We will have a review of the material before midterm and final Final covers all the material studied all semester Exam problems are similar with homework and test also what you learn through the programming projects You will receive a practice final Lecture 2 Fall 2008 Programming Projects CS355 Three programming projects First two you must work alone Last one you must work in pairs More information will come Purpose of the projects is to offer a glimpse of what is means to design and implement secure protocols Lecture 2 Fall 2008 Academic Integrity Purdue University Academic Integrity httpwwwpu rd ueed uODOSosrrcon ductcodehtm Class policy httpwwwceriaspurdueeduhomess pafcpolicyhtm CS355 Lecture 2Fall 2008 QUESTIONS CS355 Lecture 2Fall 2008 10 Today and next week simple ciphers enigma onetime pad perfect secrecy chapter 2 book CS355 Lecture 2Fall 2008 17 Shift Cipher A substitution cipher The Key Space 1 25 Encryption given a key K each letter in the plaintext P is replaced with the K th letter following corresponding number shift right Decryption given K shift left History K 3 Caesar39s cipher CS355 Lecture 2Fal 2008 Shift Cipher An Example CS355 ABCDEFGHIJKL MNO PQR S TUVWXYZ 0 12345678910111213141516171819202122 232425 P CRYPTOGRAPHYISFUN K 11 C NCJAVZRCLASJTDQFY Ce 2 211mod2613e N R171711m0d26 2 C N9 13 1311 mod 26249 Y Lecture 2 Fall 2008 13 Shift Cipher Cryptanalysis Can an attacker find K YES exhaustive search key space is small lt 26 possible keys Once K is found very easy to decrypt CS355 Lecture 2Fall 2008 14 General Monoalphabetical Substitution Cipher The key space all permutations dz A B C Z Encryption given a key as each letter X in the plaintext P is replaced with 713X Decryption given a key as each letter Y in the cipherext P is replaced with n1Y Example ABCDEFGHIJKLMNOPQRSTUVWXYZ l39FBADCZHWYGOQXSVTRNMSKJIPFEU BECAUSE a AZDBJSZ CS355 Lecture 2Fal 2008 Strength of the General Substitution Cipher Exhaustive search is infeasible key space size is 26 z 41026 Dominates the art of secret writing throughout the first millennium AD Thought to be unbreakable by many backthen CS355 Lecture 2Fall 2008 16 Cryptanalysis of Substitution Ciphers Frequency Analysis Basic ideas Each language has certain features frequency of letters or of groups of two or more letters Substitution ciphers preserve the language features Substitution ciphers are vulnerable to frequency analysis attacks CS355 Lecture 2Fall 2008 17 Frequency of Letters in English abcdefghijklmnopqrstuvwxyz CS355 Lecture 2Fall 2008 18 Other Frequency Features of English Vowels which constitute 40 of plaintext are often separated by consonants Letter A is often found in the beginning of a word or second from last Letter is often third from the end of a word Letter Q is followed only by U And more CS355 Lecture 2Fall 2008 19 Substitution Ciphers Cryptanalysis The number of different The cipher text is examined for CS355 ciphertext characters or combinations are counted to determine the frequency ofusage patterns repeated series and common combinations Replace ciphertext characters with possible plaintext equivalents using known language characteristics Lecture 2 Fall 2008 20 Frequency Analysis History Discovered by the Arabs earliest known description of frequency analysis is in a book by the ninthcentury scientist aIKindi Rediscovered or introduced from the Arabs in the Europe during the Renaissance Frequency analysis made substitution cipher insecure CS355 Lecture 2Fall 2008 21 Improve the Security of Substitution Cipher Using nulls eg using numbers from 1 to 99 as the ciphertext alphabet some numbers representing nothing are inserted randomly Deliberately misspell words eg Thys haz thi ifekkt off diztaughting thi baans off frikwenseas Homophonic substitution cipher each letter is replaced by a variety of substitutes These make frequency analysis more difficult but not impossible CS355 Lecture 2Fall 2008 22 Summary Shift ciphers are easy to break using brute force attacks they have small key space Substitution ciphers preserve language features and are vulnerable to frequency analysis a acks CS355 Lecture 2Fal 2008 23 Towards the Polyalphabetic Substitution Ciphers Main weaknesses of monoalphabetic substitution ciphers each letter in the ciphertext corresponds to only one letter in the plaintext letter Idea for a stronger cipher 1460 s by Alberti use more than one cipher alphabet and switch between them when encrypting different letters Developed into a practical cipher by Vigenere published in 1586 CS355 Lecture 2Fall 2008 24 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 02 Cm c1k1 02k2 cm km mod 26 Example Plaintext CRYPTOGRAPHY Key LUCKLUCKLUCK Ciphertext NLAZEI IBLJ J CS355 Lecture 2Fall 2008 25 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 dif cult Any message encrypted by a Vigenere cipher is a collection of as many shift cipher are letters in the key Lecture 2 Fall 2008 26 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 how CS355 Lecture 2Fal 2008 27 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 Index of coincidence Friedman CS355 Lecture 2Fall 2008 28 Kasisky Test Note two identical segments of plaintext will be encrypted to the same ciphertext if the 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 2Fal 2008 Example of the Kasisky Test Key KINGKINGKINGKINGKING KING PT thesunandthemaninthe moon CT DPRYEVNTNBUKWIAOXBUK WWBT CS355 Lecture 2Fall 2008 30 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 Icx Pxz x1 Lecture 2 Fall 2008 31 Index of Coincidence cont Reminder binomial coefficient 1 n k kn k Consider the plaintext x and c0 c1 c25 are the number of occurrences with which A B Z appear in x and p0 p1 p25 are the probabilities with which A B Z appear in x We want to compute Icx Pxz x1 CS355 Lecture 2Fall 2008 32 Begin Math CS355 Lecture 2Fall 2008 33 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 2 Fall 2008 34 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 setA 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 UEZUU E 2PrE i1 CS355 Lecture 2Fall 2008 35 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 2Fall 2008 36 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 CS355 Lecture 2Fall 2008 37 End Math CS355 Lecture 2 Fall 2008 38 Index of Coincidence cont We can choose two elements out of the string of size n in ways For each i there are Ci ways of choosing the elements to be i 2 Cx i0 z0 N i THIS IS AN APPROXIMATION F N is VERY BIG CS355 Lecture 2Fall 2008 39 Example IC of a String Consider the text THE INDEX OF COINCIDENCE S SCICl 1 Cx lnn 1 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 2Fal 2008 40 Example IC of a Language For English 8 25 and pi can be estimated 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 219 0065 i0 C8355 Lecture 2Fall 2008 41 Find the Key Length Index of coincidence Friedman CS355 Lecture 2Fall 2008 42 Finding the Key Length q q1q2qn m is the key length lt lt W qn m1 m2 qn m2 CS355 gt Y1 gtY2 Lecture 2 Fall 2008 ym 43 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 i25 1 1 1 I z 226x 0038 0 226 262 26 CS355 Lecture 2Fall 2008 44 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 2Fall 2008 45 Summary Vigenere cipher is vulnerable once the key length is found a cryptanalyst can apply frequency analysis CS355 Lecture 2Fal 2008 46 Recommended Reading for This Lecture Chapter 21 23 24 CS355 Lecture 2Fall 2008 47 08355 Cryptography Lecture 4 Cryptanalysis of Vigenere cipher CS355 Lecture 4 Spring 2007 1 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 p1k1a p2k2quotpmkm mOd 26 Decryption dkc1 c2 cm c1k1 czk2 cm km mod 26 Example Plaintext CRYPTOGRAPHY Key LUCKLUCKLUCK Ciphertext NLAZEI IBLJ J 08355 Lecture 4 Spring 2007 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 are letters in the key Lecture 4 Spring 2007 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 how CS355 Lecture 4 Spring 2007 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 Index of coincidence Friedman CS355 Lecture 4 Spring 2007 Kasisky Test Note two identical segments of plaintext will be encrypted to the same ciphertext if the 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 4 Spring 2007 Example of the Kasisky Test Key KINGKINGKINGKINGKING KING PT thesunandthemaninthe moon CT DPRYEVNTNBUKWIAOXBUK WWBT CS355 Lecture 4 Spring 2007 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 Icx Pxz x1 Lecture 4 Spring 2007 Index of Coincidence cont CS355 Reminder binomial coefficient n 1139 k kn k Consider the plaintext x and c0 c1 c25 are the number of occurrences with which A B Z appear in x and p0 p1 p25 are the probabilities with which A B Z appear in X We want to compute Icx Pxz x1 Lecture 4 Spring 2007 Index of Coincidence cont We can choose two elements out of the string of size n in ways For each i there are Ci ways of choosing the elements to be i 2 Cx i0 z0 N i THIS IS AN APPROXIMATION F N is VERY BIG 08355 Lecture 4 Spring 2007 Index of Coincidence of English For English 8 25 and pi can be estimated 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 219 0065 i0 C8355 Lecture 4 Spring 2007 11 Example Consider the text THE INDEX OF COINCIDENCE S SCICl 1 Cx lnn 1 There are 21 characters so N 21 S 25 IC 32 21 43 1O 1O 32 32 21 1O 10 2120 34420 00809 C8355 Lecture 4 Spring 2007 12 Finding the Key Length q q1q2qn m is the key length lt lt W qn m1 m2 qn m2 CS355 gt Y1 gtY2 Lecture 4 Spring 2007 ym Guessing the Key Length If m is the key length then the text looks like English text i25 Cyl 219 0065 Vlsism If m is not the key length the text looks like random text and 25 1 1 1 I z 226gtlt 0038 C 226 262 26 08355 Lecture 4 Spring 2007 14 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 4 Spring 2007 15 Summary Vigenere cipher is vulnerable once the key length is found a cryptanalyst can apply frequency analysis CS355 Lecture 4 Spring 2007

### 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

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I made $350 in just two days after posting my first study guide."

#### "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!"

#### "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.