Algorithm 8.6.4. Ceasar shift the letter ch.
1. Convert ch to a number between 0 and 25.
2. Add the shift to that number.
3. Divide that number % 26.
4. Convert the resulting number back to a character.
Section 8.6 Example: The Cipher Class Hierarchy
Suppose we wish to design a collection of cipher classes, including a Caesar cipher and a transposition cipher.
Because the basic operations used in all forms of encryption are the same, both the
Caesar class and the Transpose class will have methods to encrypt and decrypt messages, where each message is assumed to be a string of words separated by spaces. These methods will take a String of words and translate each word using the encoding method that is appropriate for that cipher.
encrypt: Take a sentence and encode each word. decrypt: take a sentence and decode each word.
In addition to
encrypt() and decrypt(), each cipher class will need polymorphic encode and decode methods, which take a single word and encode or decode it according to the rules of that particular cipher.
encode: Take a word and encode it. decode: take a word and decode it.
Subsection 8.6.1 Class Hierarchy
From a design perspective the
encrypt() and decrypt() methods will be the same for every class: They simply break the message into words and encode or decode each word.
However, the
encode() and decode() methods will be different for each different cipher. The Caesar.encode() method should replace each letter of a word with its substitute, whereas the Transpose.encode() method should rearrange the letters of the word. Given these considerations, how should we design this set of classes?
Because all of the various ciphers will have the same methods, it will be helpful to define a common
Cipher superclass (Figure 8.6.1), which will encapsulate those features that the individual cipher classes have in common—the encrypt(), decrypt(), encode(), and decode() methods.
Some of these methods can be implemented in the
Cipher class itself. For example, the encrypt() method should take a message in a String parameter, encode each word in the message, and return a String result. The following method definition will work for any cipher:
public String encrypt(String s) {
StringBuffer result = new StringBuffer("");
StringTokenizer words = new StringTokenizer(s);// Tokenize
while (words.hasMoreTokens()) { // Encode each word
result.append(encode(words.nextToken()) + " ");
}
return result.toString(); // Return result
} // encrypt()
This method creates a local
StringBuffer variable, result, and uses StringTokenizer to break the original String into its component words. It uses the encode() method to encode the word, appending the result into result. The result is converted back into a String and returned as the encrypted translation of s, the original message.
On the other hand, the polymorphic
encode() method cannot be implemented within Cipher, because unlike the encrypt() method, which is the same for every Cipher subclass, the encode() method will be different for every subclass.
So, by declaring the
encode() method as abstract, we will leave its implementation up to the Cipher subclasses. Thus, within the Cipher class, we would define encode() and decode() as follows:
// Abstract methods
public abstract String encode(String word);
public abstract String decode(String word);
Subsection 8.6.2 Class Design: Cipher
Listing 8.6.2 provides the full definition of the
Cipher class. The abstract encode() and decode() methods will be implemented by Cipher’s subclasses.
abstract Cipher class.import java.util.*;
public abstract class Cipher {
public String encrypt(String s) {
StringBuffer result = new StringBuffer(""); // Use a StringBuffer
StringTokenizer words = new StringTokenizer(s); // Break s into words
while (words.hasMoreTokens()) { // For each word in s
result.append(encode(words.nextToken()) + " "); // Encode it
}
return result.toString(); // Return the result
} // encrypt()
public String decrypt(String s) {
StringBuffer result = new StringBuffer(""); // Use a StringBuffer
StringTokenizer words = new StringTokenizer(s); // Break s into words
while (words.hasMoreTokens()) { // For each word in s
result.append(decode(words.nextToken()) + " "); // Decode it
}
return result.toString(); // Return the decryption
} // decrypt()
public abstract String encode(String word); // Abstract methods
public abstract String decode(String word);
} // Cipher
Note again that
encrypt() and decrypt() call encode() and decode(), respectively. Java’s dynamic binding mechanism will take care of invoking the appropriate implementation of encode() or decode(), depending on what type of cipher is involved.
Subsection 8.6.3 Algorithm Design: Shifting Characters
The
Caesar class (Listing 8.6.3) extends Cipher and implements its own version of encode() and decode().
Caesar class.public class Caesar extends Cipher {
public String encode(String word) {
StringBuffer result = new StringBuffer(); // Initialize a string buffer
for (int k = 0; k < word.length(); k++) { // For each character in word
char ch = word.charAt(k); // Get the character
ch = (char)('a' + (ch -'a'+ 3) % 26); // Perform caesar shift
result.append(ch); // Append it to new string
}
return result.toString(); // Return the result as a string
} // encode()
public String decode(String word) {
StringBuffer result = new StringBuffer(); // Initialize a string buffer
for (int k = 0; k < word.length(); k++) { // For each character in word
char ch = word.charAt(k); // Get the character
ch = (char)('a' + (ch - 'a' + 23) % 26); // Perform reverse shift
result.append(ch); // Append it to new string
}
return result.toString(); // Return the result as a string
} // decode()
} // Caesar
The
encode() method takes a word and returns the result of shifting each of the word’s letters. How do we do that? Fortunately, because char data in Java are represented as 16-bit integers. we can use some arithmetic to perform the shift.
For example, the character ’h’ has an ASCII code of 104. Adding 3 gives 107, the ASCII code for ’k’, which is shifted 3 characters to the right of ’h’.
The problem is this doesn’t always work so simply. For example, the ASCII code for ’y’ is 121. Adding 3 gives 124, the ASCII code for ’|’, which is not our desired result. To fix this, what we need to do is “wrap around” to the beginning of the alphabet, so that ’y’ gets shifted into ’b’.
In order to accomplish this wrap around we need to do some modular arithmetic. The alphabet has 26 letters and for any positive integer N, N % 26 will always give a number between 0 and 25. If we number the letters ’a’ to ’z’ as 0 to 25, then ’y’ would be 24. Adding 3 gives 27 and 27 % 26 would give 1, which is the letter ’b’. Thus, if we can convert the letters to numbers between 0 and 25, we can use simple arithmetic to perform the shift. This leads to the following algorithm.
For step one of this algorithm we can convert any letter ’a’ to ’z’ into a number 0 to 25 simply by subtracting the letter ’a’ from it:
'a' - 'a' = 0
'b' - 'a' = 1
'c' - 'a' = 2
...
'z' - 'a' = 25
Adding the shift and dividing % 26 gives us a number between 0 and 25. To convert that back into a letter, we can just add the letter ’a’ to it and use the
(char) cast operator to convert it to a character.
If we combine these steps, we get the following expression for shifting
ch by 3:
(char)('a' + (ch -'a'+ 3) % 26)
which breaks down as follows:
ch -'a' // Convert to 0 to 25
(ch -'a'+ 3) // Add shift
(ch -'a'+ 3) % 26 // Divide % 26
('a' + (ch -'a'+ 3) % 26) // Add 'a'
(char)('a' + (ch -'a'+ 3) % 26) // Cast back into a letter
To summarize, we can shift any character by 3 if we map it into the range 0 to 25, then add 3 to it mod 26, then map that result back into the range ’a’ to ’z’.
The algorithm for the reverse shift in the
decode() method is similar. Accept in this case the reverse Caesar shift is done by shifting by 23, which is \(26-3\text{.}\) If the original shift is 3, we can reverse that by shifting an additional 23. Together this gives a shift of 26, which will give us back our original letter.
See this code in action below.
Activity 8.6.1.
Run the code below. Change the text in main to another lowercase string and try again. This code will only work with lowercase letters.
Subsection 8.6.4 Class Design: Transpose
The
Transpose class (Listing 8.6.5) is structured the same as the Caesar class. It implements both the encode() and decode() methods. The key element here is the transpose operation, which in this case is a simple reversal of the letters in the word. Thus, “hello” becomes “olleh”. This is very easy to do when using the StringBuffer.reverse() method.
The
decode() method is even simpler, because all you need to do in this case is call encode(). Reversing the reverse of a string gives you back the original string.
Transpose classpublic class Transpose extends Cipher {
// encode() reverses and returns a word
public String encode(String word) {
StringBuffer result = new StringBuffer(word);
return result.reverse().toString();
} // encode()
public String decode(String word) {
return encode(word); // Just call encode
} // decode
} // Transpose
Subsection 8.6.5 Testing and Debugging
TestEncrypt class.public class TestEncrypt {
public static void main(String argv[]) {
Caesar caesar = new Caesar();
String plain = "this is the secret message"; // Here's the message
String secret = caesar.encrypt(plain); // Encrypt the message
System.out.println(" ********* Caesar Cipher Encryption *********");
System.out.println("PlainText: " + plain); // Display the results
System.out.println("Encrypted: " + secret);
System.out.println("Decrypted: " + caesar.decrypt(secret));// Decrypt
Transpose transpose = new Transpose();
secret = transpose.encrypt(plain);
System.out.println("\n ********* Transpose Cipher Encryption *********");
System.out.println("PlainText: " + plain); // Display the results
System.out.println("Encrypted: " + secret);
System.out.println("Decrypted: " + transpose.decrypt(secret));// Decrypt
} // main()
} // end TestEncrypt
It creates a
Caesar cipher and a Transpose cipher and then encrypts and decrypts the same sentence using each cipher. If you run this program, it will produce the following output:
********* Caesar Cipher Encryption *********
PlainText: this is the secret message
Encrypted: wklv lv wkh vhfuhw phvvdjh
Decrypted: this is the secret message
********* Transpose Cipher Encryption *********
PlainText: this is the secret message
Encrypted: siht si eht terces egassem
Decrypted: this is the secret message
See this code in action below.
Activity 8.6.2.
Run the code below. Change the plain variable in main to another lowercase string and try again. This code will only work with lowercase letters.
Exercises Self-Study Exercises
1. Caesar Shift.
Modify the
Caesar class so that it will allow various sized shifts to be used, instead of just a shift of size 3. (Hint: Use an instance variable in the Caesar class to represent the shift, add a constructor to set it, and change the encode method to use it.)
2. Transpose Rotate.
Modify
Transpose.encode() so that it uses a rotation instead of a reversal. That is, a word like “hello” should be encoded as “ohell” with a rotation of one character. (Hint: use a loop to append the letters into a new string)
You have attempted of activities on this page.
