section21shiftciphersandmodulararithmetic21节移位密码和模块化的算术

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: Zm = 0, 1, 2, m-1. (the remainders) Z26 = 0, 1, 2, 3, , 25 We use Z26 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 exampl