Transcript Section 2.1: Shift Ciphers and Modular Arithmetic

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 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 Cipher
• Let x be a numerical plaintext letter (ex: x = 0 when the plaintext letter is A)
• Let k be an element of Z26. k is called the key of the cipher and represents the shift
amount.
• Then y = (x + k) mod 26, where y is the numerical ciphertext letter.
– The Caesar Cipher table
• Encipher the message “Radford”.
– Note: In ASCII the letter A has an ASCII number of 65. We could write a
program that does the shift cipher for us. The basic formula would be y = (x – 65
+ 3) MOD 26 (where x is the numerical ASCII value of the letter). Everything
works great except for the letters X, Y, and Z. We would need a control structure
to ensure that these last three letters become A, B, and C, respectively.
– The Caesar Cipher is just a special case of the shift cipher with the key k = 3. In
general k can be any number in the set {0, 1, 2, …, 25}. (Of course for k = 0, the
cipher text and plaintext are the same.)
– Example 12: Encipher the message SEINFELD using a 12 shift cipher. (link to
solution below)
• Answer…
Section 2.1: Shift Ciphers and
Modular Arithmetic
• Deciphering Shift Ciphers
– Given a key k, plaintext letter number x, and
ciphertext letter number y:
•
•
•
•
•
y = (x + k) MOD 26 (note: y = y MOD 26)
Subtract k from both sides
(y – k) MOD 26 = x MOD 26 = x. Therefore,
x = (y – k) MOD 26
Note: - k can be replaced with + m where m + k = 26.
– Example 13: Suppose k = 3 and the ciphertext =
“YLUJLQLD”. Decipher the message.
– Example 14: Decipher the message “EVZCJZXDFE”
that was enciphered using a 17 shift cipher…
Section 2.1: Shift Ciphers and
Modular Arithmetic
• As the last two examples illustrate, one must know the key k used in
a shift cipher when deciphering a message. This leads to an
important question. How can we decipher a message in a shift
cipher if we do not know the key k? Cryptanalysis is the process of
trying to break a cipher by finding its key. Cryptanalysis in general is
not an easy problem. The more secure a cipher is, the harder it is to
cryptanalyze. We will soon see that a shift cipher is not very secure
and is relatively easy to break.
• Methods for Breaking a Shift Cipher
– Since x = (y – k) Mod 26, we can test all 26 possibilities. One of them
will work.
– Frequency analysis: Uses the fact that the most frequently occurring
letters in ciphertext produced by shift cipher has a good chance of
corresponding to the most frequently occurring letters in the standard
English alphabet. The most frequently occurring letters in English are
E, T, A, O, I, N, S.
• Frequency Table
• Two Letter Combinations
• Three Letter Combinations…!