### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Class Note for CSCI 124 with Professor Vora at GW (11)

### View Full Document

## 23

## 0

## Popular in Course

## Popular in Department

This 7 page Class Notes was uploaded by an elite notetaker on Saturday February 7, 2015. The Class Notes belongs to a course at George Washington University taught by a professor in Fall. Since its upload, it has received 23 views.

## Reviews for Class Note for CSCI 124 with Professor Vora at GW (11)

### 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/07/15

CSCI 124224 Discrete Structures 11 Modular Arithmetic Poorvi L Vora We start with three simple examples from cryptography to illustrate the need for the mathematics of what is known as modem algebra We then de ne modular arithmetic The cryptographic problem we examine in this set of notes is as follows Alice the sender wishes to communicate secretly with Bob the receiver That is she does not wish anyone else to overhear the conversation or read the letter There is a communication channel linking them 7 such as a phone line a data link or a postal service The channel is typically insecure Alice encrypts her message using a key known only to Bob and uses the insecure communication link to send him the encrypted message Bob uses the key to decrypt the message 1 The Shift Cipher One of the rst known ciphers is the shift cipher from the times of Julius Caesar In this cipher the letters from A through Z are associated with the numbers 0 through 25 The key is a letter too and is similarly associated with a number Encryption is performed letter by letter by adding the key to each letter in the plaintext message to get the corresponding letter in the ciphertext This is best explained through an example Example 1 Encrypt the sentence IS CLASS OVER YET with the shift cipher key E Decrypt the result Solution Convert the letters in the sentence to their numerical values IS CLASS OVER YET 81821101818142141724419 To encrypt add the value of the key 4 12226154222218258212823 Convert back mwgpewwszivcix To decrypt with knowledge of the key subtract 4 from each ciphertext symbol First convert to numbers 12226154222218258212823 Then subtract 4 818211018181421417224419 Then convert back to letters IS CLASS OVER YET CSCI 124 and CSCI 224VoIaGWU 2 Example 2 Decrypt the following ciphertext without knowing the key mjrmjrmjrtjpmwjvo Solution Try every possible key nksnksnksukqnkap oltoltoltvlroylxq pmupmupmuwmspzmyr qnvqnvqnvxntqanzs rowrowrowyourboat Thus a brute force attack requiring a number of steps that is half the size of the keyspace 13 in Example 2 on average would result in success at determining the key The shift cipher is hence extremely weak and is not used in realworld cryptography today One may wish to make a bruteforce attack somewhat more dif cult One step towards doing this is to use a different key with each letter in the string Another is to use multiplication instead of addition 2 Vigenere Cipher In this cipher the key is a string of symbols that is repeated It can be as long as the message Example 3 Encrypt the plaintext message HO HO HO AND A BOTTLE OF RUM using the Vigenere cipher and the key CHRISTMAS Solution The message in numbers is 71471471401330114191911414172012 The key in numbers repeated to form a string as long as the message is 27178181912018271781819120182717 The ciphertext in numbers is 9 2124 22 25 3371213 212 8 315 27137113041614 359 2219 In letters the ciphertext is JVYWZHMNVCI Unfortunately for this method to be secure the key needs to be as long as the message As the key needs to be sent securely from the sender to the receiver this is often very impractical 3 The Af ne Cipher For this cipher a number I is encrypted as ax b where a and b form the key CSCI 124 and CSCI 224VoIaGWU 3 Example 4 Encrypt the sentence IS CLASS OVER YET with the af ne cipher a 3 and b 0 Can you decrypt the result Solution Convert the letters in the sentence to their numerical values IS CLASS OVER YET 81821101818142141724419 Multiply by 3 24 542 6 337 0 2 2 Convert back y c g h a c c How would one decrypt with knowledge of the key If one divided by 3 that would not always give an integer In this case what does it mean to divide by 3 To understand this we need to understand better the mathematical structure behind the numbers we ve assigned to the alphabet 4 Modular Arithmetic In assigning numbers to the alphabet it seems that we are saying that 2 is the same as 28 which is the same as 54 That is we are saying that two numbers are the same if their difference is divisible by 26 We need not restrict ourselves to 26 and can generalize this to any number m De nition 1 a E b mod m if and only if ml 12 7 a If a E b mod m we say a is congruent to b modulo m For example 3 E 10 mod 71 E 3 mod 2 5 E 74 mod 9 etc Recall the de nition of equivalence relations in CS 123 An equivalence was something like an equality but not quite an equality In fact an equivalence is exactly what we ve been using Theorem E mod m is an equivalence relation Proof It is o Re exive a E abecause mla 7 a 0 o Symmetric aEb mlazia bakmf0TkEZ abikmf0Tik Z mKaib bEa CSCI 124 and CSCI 224VoIaGWU 4 o Transitive Suppose a E b E c a E b Tnl b 7 a bakmf0Tk Z and 1236 Tnlc7b gtCblmf0TlEZ and combining the above equations caklTnf0T kZEZ Tnlc7a gt0EC Note that 10 3 17 24 87 are congruent among themselves modulo 7 because 87 7 17 or 17 7 10 or 24 7 87 are all divisible by 7 In fact numbers are congruent among themselves when their remainders are the same on division by Tn To examine this further we rst need a simple fact Theorem without proof Let TL and Tn be two integers There exist unique integers q and T such that TL an T and 0 g T lt Tn T is often denoted TL Tem Tn From the examples it appears that the equivalence partitions the set of integers into Tn sets each consisting of integers with the same remainder when divided by Tn For example the equivalence Tnod 26 partitions the set of integers into 26 sets which we may number A through Z A 7 527 7267 07 267 527 B 7 517 7257 17 277 537 Z m 7 21712551 77 m We can show this formally Theorem a E b ltgt a Tem Tn b Tem Tn For example 10 Tnod 7 3 Also 74 Tnod 7 3 and 87 Tnod 7 317 Tnod 7 3 that is 10 E 74 Tnod 7 10 E 87 Tnod 7 etc CSCI 124 and CSCI 224VoIaGWU 5 Proof Suppose a qam Ta and b qu Tb where Ta d rem m and n b rem m aEb mlb7a mlqb7qam7quota7rb 7mlt Ta739rb ltm gtml7 a77 b 7mltTa7Tbltm ra7rb 0 n Tb and Ta Tb 5 7 a 4b 7 4am Ta 7 Tb 5 7 a 4b 7 Wm gtmlb7a aEb Now we see that while doing any modulo m operations on two numbers say a and c we can get the same result by doing the operations on two other numbers say b and d congruent to d and c respectively That is instead of a number a modulo m we can take any element from its representative class modulo m Hence operations modulo m are operations on the entire class representing the respective numbers and not on the individual numbers themselves Theorem lfd E bmodm andc E dmod m then aCEbdmodm agtlt CEbdeodm Proof lfd qamrathenb qura lfc qcmTcthend qdmrd a cmodm qa qcm Ta To mad m Ta T0 mod m Further 12 dmodm Qb qdm Ta To mad m Ta T0 mod m acmodm CSCI 124 and CSCI 224VoIaGWU 6 a X 5 mod m qam M qcm T0 mod m Qaqcm 4a qcm Ta l c mod m Ta l c mod m Further b X d mod m Qbm Ta qum Tc mod m qudm 11 4dm Tan mod m Ta l c mod m axcmodm We pick the easiest number to use to represent the class modulo m of integer a the remainder When a is divided by m De nition 2 a MOD m a ram m Thus lOMOD733MOD73 12MOD75 73MOD74andsoon Zm denotes the set of all remainders modulo m With the additive and multiplicative operations modulo m De nition 3 Zm 0 l 2 7 l With operations m and Xm addition and multiplication modulo m respec tively resulting in numbers expressed MOD m 5 The Shift Cipher over Zm We are now in a position to understand the shift cipher and generalize it to Zm for any m lts encryption and decryption rules are EKZZmHZm Ky gmK dKZZmHZm dKggiKMODm Ex amples o m 26 Z25 represents the English alphabet Where each letter is represented by a number MOD 26 o m 8 Z3 represents the set of all bytes represented as numbers MOD 8 o m 2 Z2 is the set of all bits represented as numbers MOD 2 CSCI 124 and CSCI 224VoraGWU 6 The Af ne Cipher over Zm We can also generalize the af ne cipher to Zm for any m We get the following encryption and decryption rules 6K Zm A Zm eKg a Xm z m b dszmHZm dKlt9gt 7 In the next module we try to abstract the commonalities between the operations in the shift and af ne ciphers

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

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

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

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