Transcript MAT 1000 - Wayne State University

MAT 1000
Mathematics in Today's World
Winter 2015
Last Time
We looked at the number of issues a parity-check sums
system can detect
Today
We take a look at cryptography.
Cryptography
Cryptography: The study of methods to make
and break secret codes. The process of coding
information to prevent unauthorized use is
called encryption
https://www.youtube.com/watch?v=zdA__2tKoI
U
What do we do with Secret messages?
• Encrypt: Change the letters of the message
•
so that it cannot be read
Decrypt: Take an encrypted message and
return the letters back to normal
Types of Ciphers
• Caesar Cipher
• Decimation Cipher
• Linear Cipher
• Vigenere Cipher
Caesar Cipher
• Used by Julius Caesar to send messages to
•
•
•
the troops
Shifts the letters of the alphabet by s units
(Caesar used a shift of s=3)
ABCDEFGHIJKLMNOPQRSTUVWXYZ
DEFGHIJKLMNOPQRSTUVWXYZABC
To Encrypt
• Write the Alphabet down
• Under each letter write the letter of the
•
•
alphabet that is s units later in the alphabet.
Notice: If s=3, A will have a D below it since
D is 3 letters after A.
Take your message and change each letter
to the associated letter below it (from above)
To Decrypt
• Use the grid from encryption and replace
each letter with the letter above it
• Notice that A would encrypt as D and D
would decrypt as A
Example
Modular Arithmetic
• Notice that s is just a number
• Each letter of the alphabet can also be given
•
a number…A:0 B:1 C:2…Z:25
A shift of 3 would take A to D, but 0+3=3
which is the number associated to D.
• We could add the shift to each of the
•
associated numbers to encrypt a Caesar shift
Problem: What do we do with Y? 24+3=27
Modular Arithmetic
• Before, we just repeated the Alphabet
• 26 would go to A, 27 to B, 28 to C…
• Notice that we now have that A is associated
•
•
•
to 0 and 26, B to1 and 27, C to 2 and 28
0 and 26 have remainder 0 when dividing by
26 (number of letters in the alphabet)
1 and 27 have remainder 1 when dividing by
26
2 and 28 have remainder 2
Modular Arithmetic
•
•
•
•
•
•
•
Like the days of the week, we see that some things are cyclic
To identify numbers, we compare their remainders when dividing by
some number n
We say that this is working mod n
There are 7 days in the week, so we could work mod 7
15, 22, 29, 36 all have the same remainder when dividing by 7 (they
have remainder 1) so we say that 15, 22, 29 and 36 are all the same
mod 7.
Notice that 15, 22, 29, 36 days from now it will be Tuesday…so they
really are same
The remainder measures how far past an even number of weeks 15,
22, 29, 36 went.
Caesar Shift
• For the Caesar shift we could work mod 26
• Assign to each letter their respective
numbers:
A:0 F:5 K:10 P:15 U:20 Z:25
B:1 G:6 L:11 Q:16 V:21
C:2 H:7 M:12 R:17 W:22
D:2 I:8 N:13 S:18 X:23
E:4 J:9 O:14 T:19 Y:24
Caesar Shift
• To encrypt with a shift of s add s to the
•
•
•
number associated to each letter and replace
with the letter associated to the sum (mod
25).
To decrypt: subtract s
Notice, with decryption we can get negatives.
The remainder must always be positive…To
find the actual remainder for a negative
number n: let r be the mod 26 representative
of |n|, then the actual remainder is 26-r
Examples