资源描述
Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Section 2.1:Shift Ciphers and Modular Arithmetic,The purpose of this section is to learn about modular arithmetic,which is one of the fundamental mathematical concepts we will need to implement the cryptographical techniques that we will study this semester.Afterwards,we will introduce basic concepts in cryptography and illustrate a basic cryptographic involving shift ciphers,Section 2.1:Shift Ciphers and Modular Arithmetic,Modular Arithmetic,In grade school,we first learned how to divide numbers.(Let div stand for division),Example1,:Consider 40 div 3.Determine the quotient and remainder and write the result as an equation.,Answer:40 div 3=13*3 R 1 where R stands for remainder or 13*3+1,Basic Arithmetic Properties,In the previous example we used what is called the,division algorithm,to obtain the answer.,The integers are the numbers-4,-3,-2,-1,0,1,2,3,4,A number of primary interest in this class will be the remainder r that we obtain when we divide two numbers.,Definition:,We say that r is equal to b MOD m,written r=b MOD m,if r is the integer remainder of b divided by m.We define the variable m as the,modulus,.,Example 2,:Determine 25 MOD 7,31 MOD 5,26 MOD 2,and 5 MOD 7,Answers:4,1,0,5,Section 2.1:Shift Ciphers and Modular Arithmetic,Note:In the division algorithm,the remainder r is non-negative,that is r,0.This fact means that when doing modular arithmetic we will never obtain a negative remainder.To compute b MOD m when b 0 correctly,we must always look for the largest number that m evenly divides that is less than b.The next example illustrates this fact.,Example 3,:Compare computing 23 MOD 9 and-23 MOD 9.,Answers:5,4,Section 2.1:Shift Ciphers and Modular Arithmetic,Doing Modular Arithmetic For Larger Numbers With A Calculator:,For b MOD m,calculate(int)(b div m),call this q.,On the TI-83 the int function is under MATH-NUM-5:,compute b qm.This gives r.,Or in one step:r=b int(b/m)*m,Examples 4-6,:,Compute 1024 MOD 37,answer:25,Compute 500234 MOD 10301,answer:5786,Compute-3071 MOD 107,answer:32,Section 2.1:Shift Ciphers and Modular Arithmetic,Generalization of Modular Arithmetic,In number theory,modular arithmetic has a more formal representation.This idea can be expressed with an example:,Example 7:Find solutions b to the equation b MOD 7=4(solution worked below),another words,what numbers when divided by 7 have a remainder of 4.,The easiest one is 4 itself.All other answers are multiples of 7 away from these.,The solution set is b=-10,-3,4,11,18,Section 2.1:Shift Ciphers and Modular Arithmetic,Definition:Let m be a positive integer(the modulus of our arithmetic).Two integers a and b are said to be congruent modulo m if a b is divisible by m.We write a,b mod m.(note the lower case mod),Example 8:Illustrate why 25 11 mod 7,answer:11 mod 7=4=25 mod 7,When the uppercase MOD is used,we are interested in only the specific integer remainder r when a number is divide by a modulus.The lowercase mod notation with the is used when we are looking for a set of numbers that have the same integer remainder when divided by a modulus.In this class,we will primarily use the MOD notation,Section 2.1:Shift Ciphers and Modular Arithmetic,When considering b MOD m,since 0 r m,the only possible remainders are 0,1,2,3,m-1.This causes the remainders to“wrap around when performing modular arithmetic.,Example 9:Make a table of y-values for the equation:y=(x+5)MOD 9,Rules:(if a b mod m),1.a+k (b+k)mod m,2.a k (b k)mod m,Example 10:Make a list of five solutions to x+7 2 MOD 8.,Answer:The solutions are x=(-7+2)mod 8 -5 mod 8.,Since 3 -5 mod 8(3 is the remainder)then 5 solutions are 3,11,19,-5,-13.,All solutions are of the form 3 mod 8,Section 2.1:Shift Ciphers and Modular Arithmetic,Basic Concepts of Crytography,Cryptography-is the art of transmitting information in a secret manner.,Plaintext,the undisguised message that we want to send.,Ciphertext,the secret disguised message that is transmitted.,Encryption,(encipherment)the process of converting plaintext to ciphertext.,Decryption,(decipherment)the process of converting ciphertext back to plaintext.,Notation:Z,m,=0,1,2,m-1.(the remainders),Z,26,=0,1,2,3,25,We use Z,26,to represent our alphabet.In setting up a one to one correspondence we have the,Alphabet Assignment,Section 2.1:Shift Ciphers and Modular Arithmetic,Monoalphabetic Ciphers Substitution ciphers.The correspondents(those sending messages)agree upon a rearrangement(permutation)of the alphabet.,We will consider 3 basic ciphers of this type:,Shift cipher section 2.1,Affine cipher section 2.2,Substitution cipher section 2.3,Section 2.1:Shift Ciphers and Modular Arithmetic,Shift Ciphers:All the plaintext letters are assigned a corresponding letter that has been shifted k units.,For example if k=3(the Caesar Cipher)then the plaintext letter A becomes the Ciphertext letter D,B becomes E,and so on.,The Shift Cip
展开阅读全文