Segment 2.1: Shift Ciphers and Modular Arithmetic .


85 views
Uploaded on:
Category: Fashion / Beauty
Description
Particular Arithmetic . In evaluation school, we initially figured out how to partition numbers.Example 1: Consider Determine the remainder and rest of this division and compose the outcome as a mathematical statement.. . Arrangement:. The past sample shows an extraordinary instance of the division calculation which we state next. Before expressing this calculation, review that the whole numbers are the numbers in the accompanying set:I
Transcripts
Slide 1

Area 2.1: Shift Ciphers and Modular Arithmetic Practice HW from Barr Textbook (not to submit) p.66 # 1, 2, 3-6, 9-12, 13, 15

Slide 2

Modular Arithmetic In review school, we initially figured out how to partition numbers. Case 1: Consider Determine the remainder and rest of this division and compose the outcome as a condition.

Slide 3

Solution:

Slide 4

The past case shows an exceptional instance of the division calculation which we state next. Before expressing this calculation, review that the whole numbers are the numbers in the accompanying set: Integers:

Slide 5

Division calculation Let m be a positive whole number ( m > 0) and let b be any number. At that point there is precisely one sets of numbers q (called the remainder ) and r (called the rest of with the end goal that where .

Slide 6

various essential enthusiasm for this class will be the rest of we acquire the division of two numbers. We will discover the rest of regularly that we utilize an exceptional term that is utilized to portray its calculation. This is done in the accompanying definition.

Slide 7

Definition We say that r is equivalent to b MOD m , composed as b MOD m , if r is the whole number rest of b isolated by m . We characterize the variable m as the modulus .

Slide 8

Example 2: Determine 25 MOD 7, 31 MOD 5, 26 MOD 2, and 5 MOD 7. Arrangement:

Slide 10

Note : In the division calculation, the rest of is non-negative, that is, . This reality implies that while doing secluded number juggling that we will never get a negative leftover portion . To process b MOD m when b < 0 accurately, we should dependably search for the biggest number that m equally isolates that is not as much as b . The following case outlines this reality.

Slide 11

Example 3: Compare registering 23 MOD 9 with - 23 MOD 9. Arrangement:

Slide 13

Doing Modular Arithmetic For Larger Numbers With A Calculator To do measured number-crunching with an adding machine, we utilize the reality from the division calculation that and comprehend for the rest of acquire

Slide 14

Truncated Quotient (hack digits to right of decimal) We put this outcome in division scene design as takes after: Remainder

Slide 15

Example 4 : Compute 1024 MOD 37: Solution:

Slide 16

Example 5 : Compute 500234 MOD 10301 Solution:

Slide 17

Example 6 : Compute - 3071 MOD 107 Solution:

Slide 18

Generalization of Modular Arithmetic In number hypothesis, secluded math has a more formal representation which we now give a brief portrayal of. This thought can be communicated with the accompanying case.

Slide 19

Example 7: Suppose we need to discover an answer for the condition b MOD 7 = 4 Solution:

Slide 21

The numbers from Example 7 that give a rest of 4 MOD 7 speaks to a compatibility class . We characterize this thought all the more correctly in the accompanying definition.

Slide 22

Definition Let m be a positive whole number (the modulus of our number-crunching). Two whole numbers an and b are said to be compatible modulo m if a-b is distinct by m . We compose (note the lower case "mod")

Slide 23

Note The past definition can be considered all the more casually as takes after. We say that if an and b give a similar whole number leftover portion when isolated by m . That is, if r = a MOD m = b MOD m .

Slide 24

Example 8: Illustrate why . Arrangement:

Slide 26

The last case shows that when the capitalized MOD documentation is utilized, we are occupied with just the particular whole number leftover portion when a number is partitioned by a modulus. The lowercase mod documentation with the documentation is utilized when we are searching for an arrangement of numbers that have a similar whole number leftover portion when separated by a modulus. In this class, we will essentially utilize the MOD documentation.

Slide 27

*Note: When considering b MOD m , since , the just conceivable leftovers are This causes the remnants to "wrap" around when performing particular number-crunching. This next case represents this thought.

Slide 28

Example 9: Make a table of y qualities for the condition y = ( x + 5 ) MOD 9 Solution:

Slide 31

Modular Equation Addition Prop. Tackling conditions (and congruences) if measured number-crunching is like illuminating conditions in the genuine number framework. That is, if then and for any number k .

Slide 32

Example 10: Make a rundown of five answers for mod 8 Solution:

Slide 35

Basic Concepts of Cryptography is the specialty of transmitting data in a mystery way. We next portray a portion of the fundamental wording and ideas we will use in this class including cryptography.

Slide 36

Plaintext – the real undisguised message (more often than not an English message) that we need to send. Ciphertext – the mystery camouflaged message that is transmitted. Encryption (encipherment) – the way toward changing over plaintext to ciphertext. Unscrambling (decipherment) – procedure of changing over ciphertext back to plaintext.

Slide 37

Notation speaks to every single conceivable leftover portion in a MOD framework, that is, For speaking to our letters in order, we utilize a MOD 26 framework

Slide 38

MOD 26 Alphabet Assignment Used to play out a coordinated correspondence between the letters in order letters and the components of this set.

Slide 39

Monoalphabetic Ciphers Monoalphabetic Ciphers are substitution figures in which the reporters concur on an improvement (stage) of the letters in order. In this class, we analyze 3 fundamental sorts of monoalphabetic figures

Slide 40

Types of Monoalphabetic Ciphers 1. Shift Ciphers (canvassed in Section 2.1) 2. Relative Ciphers (canvassed in Section 2.2) 3. Substitution Ciphers (canvassed in Section 2.3)

Slide 41

Shift Ciphers If x is a numerical plaintext letter, we encipher x by figuring the Enciphering equation for Shift Ciphers MOD 26, where k is in Here y will be the numerical ciphertext letter. *Note: k is known as the key of the figure and speaks to the move sum.

Slide 42

Example 11: The Caesar figure , created by Julius Caesar is a move figure given by MOD 26 Note that the key k = 3. MOD 26

Slide 43

Use the Caesar figure to make a figure letters in order. At that point utilize it to encipher the message "RADFORD". Arrangement: To make the figure letters in order, we substitute the MOD 26 letters in order task number for every letter into the Caesar move figure recipe and ascertain the comparing ciphertext letter number as takes after:

Slide 45

This gives the relating correspondence between the plain and ciphertext letter sets Using the above table, we can encipher the message "RADFORD" as takes after Hence, the ciphertext is "UDGIRUG" . █

Slide 46

In the last case we didn\'t need to make the whole plain and ciphertext letter sets to encipher the message. We could rather simply utilized the move figure recipe y = ( x+3 ) MOD 26 straightforwardly. The Caesar figure is only an uncommon instance of a move figure with a key of k = 3. In a general move figure, the key k can be any an incentive in a MOD 26 framework, that is, any incentive in the set

Slide 47

Example 12: Encipher the message "SEINFELD" utilizing a 12 move figure. Arrangement:

Slide 49

Deciphering Shift Ciphers Given a key k , plaintext letter number x , and ciphertext letter number y , we disentangle as takes after: y = ( x + k ) MOD 26

Slide 50

Deciphering recipe for move figures x = ( y – k ) MOD 26 where y is the numerical ciphertext letter, x is the numerical plaintext letter, and k is the key of the figure (the move sum). *Note: In the decoding shift figure recipe, – k MOD 26 can be changed over to its proportionate positive shape by finding a positive leftover portion.

Slide 51

Example 13: Suppose we got the ciphertext "YLUJLQLD" that was encoded utilizing a Caesar figure (move ). Disentangle this message. Arrangement:

Slide 54

Example 14: Decipher the message "EVZCJZXDFE" that was enciphered utilizing a 17 move figure. Arrangement: Using the move figure equation y = ( x + k ) MOD 26, we see that the key for this figure must be k = 17 . Consequently the recipe gets to be y = ( x + 17 ) MOD 26

Slide 55

Recall in this equation that x speaks to the letters in order task number for the plaintext and y speaks to the letter set task number for the figure content. Since we need to interpret the above figure content, we should explain the above condition for x . Improving first gives: x + 17 = y MOD 26

Slide 56

To fathom for x , we should subtract 17 from both sides. This gives: x = ( y – 17) MOD 26 (*) Since – 17 MOD 26 = 9 (this can be registered essentially by taking –17 + 26 = 9), we can compose condition (*) as: x = ( y + 9) MOD 26 (**)

Slide 57

Either conditions (*) or (**) can be utilized to decode the message. We will utilize condition (**). Taking every letter of the figure content "EVZCJZXDFE" and utilizing the MOD 26 letter set task, we get:

Slide 58

Hence, the plaintext is "NEIL SIGMON". █

Slide 59

Cryptanalysis of Shift Ciphers As the last two cases represent, one must know the key k utilized as a part of a move figure while unraveling a message. This prompts to a vital question. How might we translate a message in a move figure on the off chance that we don\'t have the foggiest idea about the key k ? Cryptanalysis is the way toward attempting to break a figure by discovering its key. Cryptanalysis by and large is not a simple issue. The more secure a figure is, the harder it is to cryptanalyze. We will soon observe that a move figure is not exceptionally secure and is generally simple to break.

Slide 60

Methods for Breaking a Shift Cipher Knowing x = ( y – k ) MOD 26, we can

Recommended
View more...