Section 8.5. Example: The Cipher Class Hierarchy
8.5. Example: The Cipher Class HierarchySuppose 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 appropriate for that cipher. Therefore, 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 the particular cipher.
Problem decomposition 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 (Fig. 8.13). Cipher will encapsulate the features that the individual cipher classes have in commonthe encrypt(), decrypt(), encode(), and decode() methods. Figure 8.13. A hierarchy of cipher classes. The Cipher class implements operations common to all ciphers. The Caesar and TRanspose classes implement functions unique to those kinds of ciphers. 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. If we define encrypt() in the superclass, it will be inherited by all of Cipher's subclasses. Thus, if we define Caesar and transpose as
Inheritance public class Caesar extends Cipher { ... } public class Transpose extends Cipher { ... } instances of these classes will be able to use the encrypt() method.
On the other hand, the polymorphic encode() method cannot be implemented within Cipher. This is because, unlike the encrypt() method, which is the same for every Cipher subclass, the encode() method will be different for every subclass. However, by declaring the encode() method as abstract, we can 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); 8.5.1. Class Design: CaesarFigure 8.14 provides the full definition of the Cipher class. The encode() and decode() methods are declared abstract. They are intended to be implemented by Cipher's subclasses. Figure 8.14. The abstract Cipher class.
Note again that encrypt() and decrypt(), which are implemented in Cipher, invoke encode() and decode(), respectively, which are declared in Cipher but implemented in Cipher's subclasses. Java's dynamic-binding mechanism will take care of invoking the appropriate implementation of encode() or decode(), depending on what type of object is involved. For example, if caesar and TRanspose are Caesar and transpose objects, respectively, then the following calls to encrypt() will cause their respective encode() methods to be invoked: caesar.encrypt("hello world"); // Invokes caesar.encode() transpose.encrypt("hello world"); // Invokes transpose.encode()
encode() and decode() are polymorphic When caesar.encrypt() is called, it will in turn invoke caesar.encode()that is, it will call the encode() method implemented in the Caesar class. When transpose.encrypt() is invoked, it will in turn invoke transpose.encode(). In this way, each object can perform the encoding algorithm appropriate for its type of cipher.
Method polymorphism 8.5.2. Algorithm Design: Shifting CharactersThe Caesar class is defined as an extension of Cipher (Fig. 8.15). The only methods implemented in Caesar are encode() and decode(). The encode() method takes a String parameter and returns a String result. It takes each character of its parameter (word.charAt(k)) and performs a Caesar shift on the character. Note how the shift is done: ch = (char)('a' + (ch -'a'+ 3) % 26); // Caesar shift Figure 8.15. The Caesar class.
Recall from Chapter 5 that char data in Java are represented as 16-bit integers. This enables us to manipulate characters as numbers. Thus, to shift a character by 3, we simply add 3 to its integer representation. For example, suppose that the character (ch) is h, which has an ASCII code of 104 (see Table 5.13). We want to shift it by 3, giving k, which has a code of 107. In this case, we could simply add 3 to 104 to get the desired result. However, suppose that ch was the character y, which has an ASCII code of 121. If we simply add 3 in this case, we get 124, a code that corresponds to the symbol "|" which is not our desired result. Instead, we want the shift in this case to "wrap around" to the beginning of the alphabet, so that y gets shifted into b. In order to accomplish this we need to do some modular arithmetic.
Character conversions Let us suppose that the 26 characters a to z were numbered 0 through 25, so that a corresponds to 0, b to 1, and so on up to z as 25. If we take any number N and divide it (modulo 26), we would get a number between 0 and 25. Suppose, for example, y were numbered 24. Shifting it by 3 would give us 27, and 27 % 26 would give us 1, which corresponds to b. So if the a to z were numbered 0 through 25, then we can shift any character within that range by using the following formula: (ch + 3) % 26 // Shift by 3 with wraparound To map a character in the range a to z onto the integers 0 to 25, we can simply subtract a from it: 'a' - 'a' = 0 'b' - 'a' = 1 'c' - 'a' = 2 ... 'z' - 'a' = 25 Finally, we simply map the numbers 0 through 25 back to the characters a to z to complete the shift operation: (char)('a' + 0) = 'a' (char)('a' + 1) = 'b' (char)('a' + 2) = 'c' ... (char)('a' + 25) = 'z' Note the use here of the cast operator (char) to convert an integer into a char. To summarize, we can shift any character by 3 if we map it into the range 0 to 25, then add 3 to it modulo 26, then map the result back into the range a to z. Thus, shifting y would go as follows: (char)('a' + (ch -'a'+ 3) % 26) // Perform Caesar shift (char)('a' + ('y' - 'a' +3) % 26) // on 'y' (char)(97 + (121 - 97 + 3) % 26) // Map 'y' to 0..25 (char)(97 + (27 % 26)) // Shift by 3, wrapping around (char)(97 + 1) // Map result back to 'a' to 'z' (char)(98) // Convert from int to char 'b'
Modular arithmetic Note that in decode() a reverse Caesar shift is done by shifting by 23, which is 26 - 3. If the original shift is 3, we can reverse it by shifting an additional 23. Together this gives a shift of 26, which will give us back our original string. 8.5.3. Class Design: transposeThe transpose class (Fig. 8.16) 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 reverse() method from the StringBuffer class. 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. Figure 8.16. The transpose class.
8.5.4. Testing and DebuggingFigure 8.17 provides a simple test program for testing Cipher and its subclasses. 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 Figure 8.17. The 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() } // TestEncrypt class |
Self-Study Exercises
| Exercise 8.11 | Modify the Caesar class so that it will allow various-sized shifts to be used. (Hint: Use an instance variable to represent the shift.) |
| Exercise 8.12 | 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. |
EAN: 2147483647
Pages: 275