here.
Introduction
My introduction to Cryptography was "MAT 8790: Cryptography" during Villanova's Summer Session 2007. The text for this course was Cryptography: Theory and Practice by Douglas Stinson. During this course I found myself writing Java programs to explore the algorithms discussed and to sharpen my programming skills. By the end of the course I had a couple of the simple cipher systems implemented in a "uniform" way. By uniform I mean that the APIs for the cipher system adhered to a Java interface and could be invoked in the same fashion. To those familiar with object oriented programming concepts, I had implemented a Strategy pattern for Stinson's cryptosystems.
The project lay dormant until I saw it as an opportunity to release it as an educational tool, and seek credit for an independent study. Thus was born the Crypto Applet project.
To make it educational, I tried to implement several simple ciphers that a high school student could absorb without difficulty: Shift, Affine, and Substitution. Hopefully the student's interest would be piqued to the point that she may investigate the RSA and ElGamal ciphers, and the mathematics behind them. The applet's demo pane permits the student to interact with the ciphers by entering parameters for the encryption key and various plaintext strings to encrypt with the cipher. The plaintext and ciphertext values can be displayed "alphabetically," as per Stinson, or numerically. A numerical display shows the inner workings of the encryption algorithm more clearly than the alphabetical display.
In the course of the project I learned a great deal about the cipher algorithms, the Java math library, the Java swing library, and HTML coding. I will share some insights by visiting each cipher and discuss what I learned doing the implementation.
I also released all source code under the Academic Free License v.3.0. I choose this one from the many Open Source license choices, because AFL has an academic orientation. Feel free to download the source into the Eclipse IDE and read the source code.
Program Technology and Architecture
The applet consists of two jar files: 1) the crypto "engine" (crypto.jar) 2) the Graphical User Interface (GUI) written in Java Swing (cryptogui.jar). I first considered writing this as a pure web application (servlets, jsp's, etc.) but was discouraged by the fact that I would have to find a host that would run the web application. Villanova's IT department (UNIT) does not provide this service to students; however, they do provide content space with few restrictions. This made the choice of Swing/applet for me, although at the start I did not know Swing programming. I also knew that any user of the application would have to have the Java 5.0 run-time system loaded into their browser program. This imposes a barrier to potential users who would have to upgrade to this level of the Java run-time.
The crypto engine can be run standalone from the command line but it doesn't support user interaction. My first step in providing a user interface was not to implement a GUI in Swing. I had developed the engine with pre-defined encryption key parameters and needed to extend the engine with parameter setting routines. So I implemented a command line interface (cryptoui.jar) to the engine wherein I could perfect the entry and validation of parameters and exception handling. Since this runs from the command line, it is not part of the applet, but it was a worthwhile stepping stone. When the command line version was working properly I undertook the more complex Swing programming. This resulted in the applet version.
Here is the HTML for the applet invocation:
<applet code="ciphergui.CipherApplet.class" name="Crypto Applet"
archive="crypto.jar,cryptogui.jar"
width=620 height=450 codebase="crypto">
<param name="bgcolor" value="ffffff">
<param name="fontcolor" value="000000">
Your browser is not Java enabled.
</applet>
As you can see there's not a lot to it, however, I have to make several points.
The HTML page with the above code references a nested folder called "crypto." This is where the two jar files reside on the server. The entry point for the applet is the CipherApplet class which must be referenced by package name.
The applet displays both html (Introduction, Theory panes) and text (code panes) within Swing components. The html and text content can be stored on the server and referenced as external to the Java code. This meant however, that if someone wanted to run the applet on their own server, say after making an enhancement, they had to replicate the content from the original server. To avoid this, I embedded the html and text within the jar file itself and used Java APIs to load it. Below is an example of how the Intro pane is displayed:
JEditorPane htmlCode = new JEditorPane();
htmlCode.setContentType("text/html");
htmlCode.setEditable(false);
try {
InputStreamReader br = new InputStreamReader(getClass().getResourceAsStream("html/intro.html"));
htmlCode.read(br, null);
br.close();
} catch (FileNotFoundException e1) {
e1.printStackTrace();
} catch (IOException e1) {
e1.printStackTrace();
}
The critical API is getResourceAsString which reads from a folder nesting within the jar file itself.
I will have more to say about Java Swing programming later.
On the Difficulty of Naming Things
I've been a software engineer my entire career and will attest to what I believe is the most difficult task – inventing good names during programming. This is especially true for object-oriented programming where a good design for a class is that fact that the class does one and only one thing. Now this project is small enough that I feel that I did adhere at least to this design principle. However, I will admit that I've been inconsistent in my naming.
I treat "crypto" and "cipher" interchangeably throughout the program. I think cipher predominates, but the package names and project names still say "crypto." Please forgive my inconsistency.
Also I wish I had named "CryptoUI " as "CryptoCLI" where CLI means "Command Line Interface." As it stands "CryptoUI" maybe easily confused with "CryptoGUI."
Converting Letters to Numbers
There are two utility classes ConvertAlphabet and ConvertTrigramAlphabet whose job is to translate between alphabetic representation and numeric representation.
ConvertAlphabet is used by the simple ciphers which operate on values in the limited range of 0 to 25.
ConvertTrigramAlphabet is used by RSA and ElGamal ciphers which operate on larger values. It is imperative that these ciphers convert groups of letters (three letters to a trigram) before the ciphers operate on them. If you simply let RSA and ElGamal operate on individual values in the range 0 to 25 the encrypted values are just a one-for-one scrambling of the plaintext value to cipher value. The numeric values must be large in absolute value and for this reason a trigram mapping is used. As explained in the applet's Introduction page the triplet "dog" is mapped to the numeric value 2398 as follows:
| d | => | 3*(26)2 | = | 2028 |
| o | => | 14*(26)1 | = | 364 |
| g | => | 6*(26)0 | = | + 6 |
| 2398 |
I also had to deal with the fact that the entire plaintext value must be a multiple of three. I had the choice of truncated an extra character or two, or padding the string with a character or two. I chose the latter using a 'b' (think 'blank') for the pad character.
I noticed in the course of the project that the complex algorithms produce encrypted values that are larger than any input or output values. This is shown in the values related to the string "dog" where the encrypted value is not a three, but a four character string, "BLND."
This forced me to re-implement the routine int2Trigram routine. The old and new versions are shown.
/**
* Convert an int to a trigram value. Example: 3*26^2 + 14*26 + 6 = 2398 =>
* "dog"
*
* @deprecated
*/
private static String int2Trigram_old(int val) {
int i0, i1, i2;
i0 = val / 676; // 676 = 26^2
val = val - (i0 * 676);
i1 = val / 26;
val = val - (i1 * 26);
i2 = val;
return "" + int2Char(i0) + int2Char(i1) + int2Char(i2);
}
/**
* Convert an int to a trigram value. Example: 3*26^2 + 14*26 + 6 = 2398 => "dog"
*
* @param val numeric value to convert to a trigram.
*/
private static String int2Trigram(int val) {
StringBuffer buf = new StringBuffer();
int divisor = 26;
int b = 0;
int i;
for (i=0; val>0 i<3; i++)
{
b = val % 26;
buf.append((char) (b + (int) 'a'));
val = val / divisor;
}
return buf.reverse().toString();
}
This proves another programming adage first espoused by the rock band Jethro Tull: "Nothing Is Easy."
Shift Cipher
The Shift cipher is the simplest of the ciphers. For this reason I chose this as the example in the introduction. The encryption algorithm is straightforward:
public int[] encrypt(int[] ba) {
int len = ba.length;
int[] cipher_ba = new int[len];
for (int i=0; i < len; i++)
{
cipher_ba[i] = (ba[i] + SHIFT) % 26;
}
return cipher_ba;
}
Programming Notes:
- The parameter ba contains the numeric values for the plaintext to be encyrpted.
- A new array cipher_ba holds the numeric values following the encryption.
- '%' is the modulus operator in Java.
The decryption algorithm is almost as straightforward; however, Java performs signed arithmetic on int (integer) values. So the result of the modulus operator may be a negative number.
public int[] decrypt(int[] ba) {
int len = ba.length;
int mod;
int[] plain_ba = new int[len];
for (int i=0; i < len; i++)
{
mod =(ba[i] - SHIFT) % 26;
// Java modular arithmetic is signed so convert negative residues.
mod = mod < 0 ? mod+26 : mod;
plain_ba[i] = mod;
}
return plain_ba;
}
Programming Notes:
- The conditional operator, ?: , acts like an in-line if statement. Following '?' is the true value; following ':' is the false value.
Affine Cipher
The Affine cipher is a little more sophisticated than the Shift cipher. I won't present the encryption/decryption algorithm, but will comment on the parameter entry. Parameter entry is made in the GUI part of the applet. The Affine cipher just validates that A, the multiplicative factor, is relatively prime to 26. And that B, the shift factor, is between 0 and 25 inclusive.To validate A, and to find its inverse modulus 26, I pre-calculated all of the numbers that are relatively prime to 26 and their inverses. Show below is the validation.
private final int[] validA = { 0, 1, 0, 3, 0, 5, 0, 7, 0, 9, 0, 11, 0, 0,
0, 15, 0, 17, 0, 19, 0, 21, 0, 23, 0, 25 };
private final int[] validAInverse = { 0, 1, 0, 9, 0, 21, 0, 15, 0, 3, 0,
19, 0, 0, 0, 07, 0, 23, 0, 11, 0, 5, 0, 17, 0, 25 };
/**
* Validate and set the multiplicative value for the cipher.
*
* @param valA is the candidate multiplicative value. It must be relatively prime to 26.
* @throws IllegalArgumentException.
*/
public void setA(int valA) throws IllegalArgumentException
{
if (valA < 0 valA > 25)
{
throw new IllegalArgumentException("A value must be in [0..25]");
}
if (validA[valA] == 0)
{
throw new IllegalArgumentException("A value must be relatively prime to 26");
}
A = valA;
A_INVERSE = validAInverse[valA];
}
I could have used the Euclidean Algorithm to determine if A is relatively prime to 26 and another algorithm to find its inverse, but a table lookup works fine. This demonstrates the classic time/space tradeoff that one encounters in computer programming frequently.
Substitution Cipher
The reader should be familiar with Substitution cipher as it is the familiar cryptogram puzzle found in newspapers. The only tricky part of its implementation was inputting the permutation that is to be used as the encryption key. "That's simple," I thought, "just have the user type the 26 letters of the alphabet in random order and use that as the permutation."
Well, I wanted to give feedback while the user was typing so my first implementation was to display a label after the input field showing the letters that had not been entered. This works fine if the user works methodically from left to right, but as I tested the implementation, I found that I sometimes used the mouse to reposition the cursor. This wrecked havoc (as did use of CTRL-C, and CTRL-V) on the implementation as I soon discovered that I had to implement a word processor in order to echo the unused characters accurately. So in the second implementation, I waited until the entire permutation is entered before validating it.
A good way to verify the implementation is to enter a permutation (just following the keyboard left to right from top to bottom) and then enter the alphabet as the string to encrypt. You will see something like this.
RSA Cipher
RSA is the first cipher that introduces high order mathematics. The algorithm requires two large prime numbers to be entered by the user. Validation of the primes and RSA algorithm implementation are made ridiculously simple by the Java BigInteger library. When I discovered the methods of this library I realized that it was designed with RSA in mind. The methods I use for validation, encryption, and decryption are:
- isProbablePrime
- multiply
- modInverse
- modPow
The encryption and decryption algorithms are each implemented in only 12 lines of code!
El Gamal Cipher
When I first encountered the El Gamal cipher I dismissed it for commercial purposes because, by design, it doubles the length of the ciphertext value. Since ciphers are intended for communication purposes, this means the transmission must be twice the length, say of an RSA ciphertext. After working with El Gamal I now see that this negative can be viewed as a positive since the use of a random variable makes the cipher that more difficult to decrypt.
In addition to the encryption keys there is a random value, called K, that is used by the encryption/decryption algorithm. In my first implementation I had the user enter this value and use it repeatedly. Then I realized that I could get closer to a one-time pad by having this value represent the seed to a random number generator. This seed is given to the Java Random library and as each trigram is encrypted, a new K value is generated by the Random class.
Another interesting aspect is that a primitive element (root) of the private key, called ALPHA, must be validated. My implementation is simply to generate powers of the element modulus P until finally (and this is guaranteed) it is equal to 1:
If ALPHA is a primitive root then the power is one less than the prime P.
public void setALPHA(int alpha) throws IllegalArgumentException
{
// Validate that alpha is a primitive element for A.
BigInteger valAlpha = new BigInteger(Integer.toString(alpha));
// Here we have alpha^1
BigInteger valAlphaPower = valAlpha;
int pow;
for (pow = 2; pow < p; pow++) {
valAlphaPower = valAlphaPower.multiply(valAlpha);
BigInteger val = valAlphaPower.mod(P);
if (val.equals(BigInteger.ONE)) {
break;
}
}
if (pow < p - 1) {
throw new IllegalArgumentException("ALPHA must be a primitive root for P");
}
ALPHA = alpha;
BigInteger valBETA = (new BigInteger(Integer.toString(alpha))).modPow(A, P);
BETA = valBETA.intValue();
}
This implementation proves to be computationally intensive and pins the processor for a few seconds. See how long it takes on your machine with these values:
- P = 31847
- A = 7899
- ALPHA =5
- SEED=1234
I will have more to say about this computation in the Swing Programming section.
Swing Programming
As I mentioned I did not know any Swing programming at the beginning of this project. I did have experience developing GUI programs in Visual Basic so "event driven" programming was in my background.
I bought an eleven hundred page O'Reilly book titled Java Swing that was no help whatsoever since it was too low-level. I found the tutorials and sample code on Sun's website to be most useful. The tool that really saved the day was the Visual Editor plugin for Eclipse. This plugin is barely maintained by the Eclipse community, but it still works like a charm. You will have difficulty finding a version compatible with Ganymede.
The most challenging area of the GUI programming was the validation of the parameters with the goal of giving feedback to the user. Swing generates an event when the Enter key is pressed, the only event that the program initially responded to. I immediately discovered that I, myself, was using the Tab key to move between fields, so I decided to program a Tab event the same as an Enter event. Then the first time I observed another user (my son) interact with the program, he used the mouse to move from field to field! I never implemented the mouse event, but I did give feedback in the form of a check mark to indicate that the parameter has been validated. Hopefully, this conditions the user to use the correct input technique.
The very last parameter validation that I implemented was the primitive element for ElGamal encryption. I was hoping to find an efficient algorithm for this but ended up with a brute force enumeration of powers. This is disconcerting to the user because all of the other parameters are validated almost instantaneously (thanks again to BigInteger!).
I thought of changing the label for ALPHA entry to "WAIT...WAIT…" below:
private void actionALPHAPerform() {
String aVal = jTextALPHA.getText();
String aError = null;
int val = 0;
try {
val = Integer.parseInt(aVal);
jLabelALPHA.setText("WAIT...WAIT");
cipher.setALPHA(val);
} catch (NumberFormatException ex) {
aError = "Please enter a number.";
} catch (IllegalArgumentException ex) {
aError = ex.getMessage();
}
if (null != aError) {
jTextALPHA.selectAll();
ShowParmValid.ShowParmInacceptable(jLabelALPHAError, aError);
}
else {
ShowParmValid.ShowParmAcceptable(jLabelALPHAError);
jTextSEED.requestFocus();
}
}
This change had no effect whatsoever. Why? Some investigation led to this passage in the Swing documentation:
By the way, applets that use Swing components must be implemented as subclasses of JApplet, and components should be added to the JApplet content pane, rather than directly to the JApplet. As for any applet, you should never perform time-consuming initialization in the init() or start() method; instead, you should start a thread that performs the time-consuming task.
This passage indirectly hints at the need for starting a separate thread on which to call the setALPHA method. This I will leave as an enhancement to the reader; however, if you download the code and see incomprehensible thread creation logic in this area, than you can assume that I have risen to the challenge myself.
Finally I want to comment on the HTML displayed within the JEditorPane class. My first implementation was to display scanned images of the Cryptosystem descriptions from Stinson's book. I sought permission from the publisher Chapman & Hall/CRC but was told that these images could only be displayed on a password protected website. This was too restrictive so I translated the image content to HTML version 3.2 (HTML4 was not allowed due to the fact that JEditorPane implements only v. 3.2). Note that it is the applet that renders the HTML displayed on the screen, not your (hopefully more modern) browser.
To demonstrate what HTML v3.2 looks like here is some of the HTML for ElGamal theory:
<b>Cryptosystem: ElGamal Public-Key</b>
<br><br>
Let <font face="Georgia"><i>p</i></font>, be a prime such that the <body>Discrete Logarithm</b>
problem in <font face="Georgia">(Z<sub>p</sub><sup>*</sup>,⋅)</font> is infeasible,
and let α ∈ <font face="Georgia">Z<sub>p</sub><sup>*</sup></font> be a primitive element.
Let <font face="Georgia"><i>P = Z<sub>p</sub><sup>*</sup></i></font>,
<font face="Georgia"><i>C = Z<sub>p</sub><sup>*</sup> x Z<sub>p</sub><sup>*</sup></i></font>
, and define
<br><br>
<div align="center"> <font face="Georgia">
<i>K</i> = {(p,α,a,β) : β ≡ α<sup>a</sup> (mod p)}</font>.
</div>
<br><br>
The values <font face="Georgia">p, α</font> and <font face="Georgia">β</font> are the public key,
and <font face="Georgia">a</font> is the private key.
This is not the most readable and maintainable HTML, but it will do in a pinch.
Tools
I used the following tools to develop the Crypto Applet:
- Eclipse (Ganymede version)
- Visual Editor plugin (org.eclipse.ve)
- Mathematica v.7 Student Edition
- Microsoft FrontPage 2003 Ed.
I used Mathematica to check the program's calculations, especially when I received unexpected results.
FrontPage is the University approved tool for deploying content to the student's website.
Conclusion
I hope you enjoy the Crypto applet in its current form but I will immediately suggest these improvements:
- More educational content
- Addition of new ciphers
- Conversion to a plugin architecture
The first two bullets are self-explanatory. A plugin architecture would permit the dynamic binding of new ciphers at run-time. You would prove yourself to be a first-class Java programmer by implementing this architecture.
Comments and feedback are welcome.
Bibliography
Castro, E. (2003). HTML for the World Wide Web (5th Edition). Berkeley: Peachpit Press.
Eckstein, R., Loy, M., & Wood, D. (1998). Java Swing. Sebastopol: O'Reilly & Associates.
Flanagan, D. (2005). Java in a Nutshell (5th Edition). Sebastopol: O'Reilly Media.
Flanagen, D. (2000). Java Examples in a Nutshell (2nd Edition). Sebastopol: O'Reilly & Associates.
Sierra, K., & Bates, B. (2005). Head First Java (2nd Edition). Sebastopol: O'Reilly Media.
Stinson, D. (2006). Cryptography: Theory and Practice (Third Edition). Boca Raton: Chapman & Hall/CRC.
This is quite good documentation and I am trying to learn from the code and may consult some of the cited sources.
ReplyDeleteI would think that pasting a couple of snippets from Stinson would be allowed by "fair use" without regard to the publisher's (unreasonable?) restrictions.