Gauss
BANNED
- Joined
- Oct 31, 2014
- Messages
- 514
- Reaction score
- -1
- Country
- Location
One of the most important applications of congruences involves cryptology, which is the study of secret messages. One of the earliest known uses of cryptology was by Julius Caesar. He made messages secret by shifting each letter three letters forward in the alphabet (sending the last three letters of the alphabet to the first three). For instance, using this scheme the letter B is sent to E and the letter X is sent to A. This is an example of encryption, that is, the process of making a message secret. To express Caesar's encryption process mathematically, first replace each letter by an integer from 0 to 25, based on its position in the alphabet. For example, replace A by 0, K by 10, and Z by 25. Caesar's encryption method can be represented by the function f that assigns to the nonnegative integer p, p ≤ 25, the integer f(p) in the set {0, 1,2, ... , 25} with
f(p) = (p + 3) mod 26.
In the encrypted version of the message, the letter represented by p is replaced with the letter represented by (p + 3) mod 26.
EXAMPLE 1 What is the secret message produced from the message "MEET YOU IN THE PARK" using the Caesar cipher?
Solution: First replace the letters in the message with numbers. This produces
12 4 4 19 24 14 20 8 13 19 7 4 15 0 17 10.
Now replace each of these numbers p by f(p) = (p + 3) mod 26. This gives
15 7 7 22 1 17 23 11 16 22 10 7 18 3 20 13.
Translating this back to letters produces the encrypted message "PHHW BRX LQ WKH SDUN."
To recover the original message from a secret message encrypted by the Caesar cipher, the function f-I, the inverse of f, is used. Note that the function f-I sends an integer p from {1,2, ... , 25} to f-I(p) = (p - 3) mod 26. In other words, to find the original message, each letter is shifted back three letters in the alphabet, with the first three letters sent to the last three letters of the alphabet. The process of determining the original message from the encrypted message is called decryption. There are various ways to generalize the Caesar cipher. For example, instead of shifting each letter by 3, we can shift each letter by k, so that f(p) = (p + k) mod 26.
Such a cipher is called a shift cipher. Note that decryption can be carried out using
f-I(p) = (p - k) mod 26.
Obviously, Caesar's method and shift ciphers do not provide a high level of security. There are various ways to enhance this method. One approach that slightly enhances the security is to use a function of the form
f(p) = (ap + b) mod 26,
where a and b are integers, chosen such that f is a bijection. (Such a mapping is called an affine transformation.) This provides a number of possible encryption systems. The use of one of these systems is illustrated in Example 2.
EXAMPLE 2 What letter replaces the letter K when the function f(p) = (7p + 3) mod 26 is used for encryption?
Solution: First, note that 10 represents K. Then, using the encryption function specified, it follows that f(10) = (7·10 + 3) mod 26 = 21. Because 21 represents V, K is replaced by V in the encrypted message.
Caesar's encryption method, and the generalization of this method, proceed by replacing each letter of the alphabet by another letter in the alphabet. Encryption methods of this kind are vulnerable to attacks based on the frequency of occurrence of letters in the message. More sophisticated encryption methods are based on replacing blocks of letters with other blocks of letters. There are a number of techniques based on modular arithmetic for encrypting blocks of letters.
f(p) = (p + 3) mod 26.
In the encrypted version of the message, the letter represented by p is replaced with the letter represented by (p + 3) mod 26.
EXAMPLE 1 What is the secret message produced from the message "MEET YOU IN THE PARK" using the Caesar cipher?
Solution: First replace the letters in the message with numbers. This produces
12 4 4 19 24 14 20 8 13 19 7 4 15 0 17 10.
Now replace each of these numbers p by f(p) = (p + 3) mod 26. This gives
15 7 7 22 1 17 23 11 16 22 10 7 18 3 20 13.
Translating this back to letters produces the encrypted message "PHHW BRX LQ WKH SDUN."
To recover the original message from a secret message encrypted by the Caesar cipher, the function f-I, the inverse of f, is used. Note that the function f-I sends an integer p from {1,2, ... , 25} to f-I(p) = (p - 3) mod 26. In other words, to find the original message, each letter is shifted back three letters in the alphabet, with the first three letters sent to the last three letters of the alphabet. The process of determining the original message from the encrypted message is called decryption. There are various ways to generalize the Caesar cipher. For example, instead of shifting each letter by 3, we can shift each letter by k, so that f(p) = (p + k) mod 26.
Such a cipher is called a shift cipher. Note that decryption can be carried out using
f-I(p) = (p - k) mod 26.
Obviously, Caesar's method and shift ciphers do not provide a high level of security. There are various ways to enhance this method. One approach that slightly enhances the security is to use a function of the form
f(p) = (ap + b) mod 26,
where a and b are integers, chosen such that f is a bijection. (Such a mapping is called an affine transformation.) This provides a number of possible encryption systems. The use of one of these systems is illustrated in Example 2.
EXAMPLE 2 What letter replaces the letter K when the function f(p) = (7p + 3) mod 26 is used for encryption?
Solution: First, note that 10 represents K. Then, using the encryption function specified, it follows that f(10) = (7·10 + 3) mod 26 = 21. Because 21 represents V, K is replaced by V in the encrypted message.
Caesar's encryption method, and the generalization of this method, proceed by replacing each letter of the alphabet by another letter in the alphabet. Encryption methods of this kind are vulnerable to attacks based on the frequency of occurrence of letters in the message. More sophisticated encryption methods are based on replacing blocks of letters with other blocks of letters. There are a number of techniques based on modular arithmetic for encrypting blocks of letters.
