Published:
December 7, 2004
By Richard G. Baldwin
Java Programming, Notes # 727
First in a series
This is the first lesson in a series designed to teach you something about the inner workings of cryptography using Java. Hopefully, when you finish studying the lessons in this series, you will have learned a little about what goes on "under the hood" when you apply a cryptographic process.
Not a lesson on JCE
The lessons in this series do not provide instructions on how to use the Java Cryptography Extension (JCE). The purpose of this series is to teach you how to implement common cryptography algorithms for small cases directly in Java.
Not intended for production use
The programs that I will provide and explain in this series of lessons are not intended to be used for production cryptography. If you need to do cryptography using Java, you should use Sun's Java Cryptography Extension (JCE).
The programs that I will provide in this series are intended to help you to experiment with and to learn about various cryptographic algorithms and to gain a better understanding of how they work, and why they do what they do.
Viewing tip
You may find it useful to open another copy of this lesson in a separate browser window. That will make it easier for you to scroll back and forth among the different figures and listings while you are reading about them.
Theoretical basis and practical implementation
I will provide some of the theoretical basis for cryptographic algorithms while discussing the lessons in this series. In addition, I will show you how to implement several common cryptographic algorithms in Java.
I will also discuss and illustrate some of the modern uses of cryptography, such as the use of digital signatures.
Cryptography in one form or another has been around throughout history. Even in pre-biblical times, governments had a need to exchange messages in secret.
What is cryptography?
According to Wikipedia, "Cryptography ... is, traditionally, the study of means of converting information from its normal, comprehensible form into an incomprehensible format, rendering it unreadable without secret knowledge — the art of encryption."
Spies, diplomats, etc.
Confirming what I alluded to earlier, Wikipedia tells us, "In the past, cryptography helped ensure secrecy in important communications, such as those of spies, military leaders, and diplomats."
New uses in modern times
Bringing the field of cryptography up to date, Wikipedia tells us, "In recent decades, the field of cryptography has expanded its remit in two ways. Firstly, it provides mechanisms for more than just keeping secrets: schemes like digital signatures and digital cash, for example. Secondly, cryptography has come to be in widespread use by many civilians who do not have extraordinary needs for secrecy, although typically it is transparently built into the infrastructure for computing and telecommunications, and users are not aware of it."
What is cryptanalysis?
Although this series of lessons won't involve cryptanalysis in any significant way, it won't hurt to learn the meaning of the term anyway. Wikipedia tells us, "The study of how to circumvent the use of cryptography is called cryptanalysis, or codebreaking. Cryptography and cryptanalysis are sometimes grouped together under the umbrella term cryptology, encompassing the entire subject. In practice, "cryptography" is also often used to refer to the field as a whole; crypto is an informal abbreviation."
Secure communications
The lessons in this series will present and explain programs that implement cryptographic algorithms intended to achieve secure communications between two parties. These algorithms fall into two broad categories:
The first several lessons will deal with public key cryptography. Subsequent lessons will deal with symmetric key cryptography.
What's the difference?
Many modern approaches to data encryption operate by passing the data along with an (often secret) key value through a mathematical transformation. Paraphrasing Wikipedia from above, the transformation converts the information from its normal comprehensible form into an incomprehensible form rendering it unreadable to persons who don't have access to a secret key.
Operating in the reverse direction, decryption passes the encrypted data (cipher data) along with a secret key value through a mathematical transformation, converting the encrypted data back into a comprehensible form.
The difference is in the use of the keys
The difference between public (asymmetric) and symmetric key cryptography basically has to do with how the keys are used.
With symmetric key cryptography, a single secret key is used both to encrypt and to decrypt the data. Thus, both parties to the communication must have access to the same secret key value. The distribution and management of such secret keys can be problematic, and has probably been a source of work for spies throughout history.
With asymmetric key cryptography, there are two keys. One is used to encrypt the data and the other is used to decrypt the data. Thus, one of the keys (the encryption key) can be publicly known without compromising secrecy so long as the other key (the decryption key) is held secret. This leads to the common name of public key cryptography.
Many of the key-management and distribution problems associated with symmetric key cryptography are alleviated through the use of public key cryptography.
The RSA algorithm
This and the next several lessons will deal with a particular asymmetric key algorithm known as the RSA algorithm. This algorithm is named after the original authors, R.L. Rivest, A. Shamir, and L. Adleman.
If this lesson sparks your interest in cryptography, you will most certainly want to read their paper describing the algorithm in full.
Key management
In their paper, the authors point out that "... publicly revealing an encryption key does not thereby reveal the corresponding decryption key.
One consequence of this is a significant easing of key management problems relative to symmetric key cryptography. For example, couriers or other secure means are not needed to exchange keys. The sender of the message can encipher the message using the intended recipient's public encryption key. However, only the intended recipient can decipher the message using his private and secret decryption key.
Message signing and digital signatures
A second important consequence is that a message can be "signed" using a privately held key. The signature can be verified using the corresponding publicly revealed key.
I will discuss the Java implications of this in the next lesson in this series.
The mathematical process
Here is the author's brief description of the mathematical encryption process embodied in the RSA algorithm:
"A message is encrypted by representing it as a number M, raising M to a publicly specified power e, and then taking the remainder when the result is divided by the publicly specified product, n, of two large secret prime numbers p and q. Decryption is similar; only a different, secret, power d is used."
As you will see, Java is particularly well suited to the implementation of this process through the use of methods of the BigInteger class.
What about security?
I will defer the question of security to the authors of the algorithm and others who have published material in this area. However, the authors do point out that "The security of the system rests in part on the difficulty of factoring the published divisor, n." Thus, in practice, parameters should be used that cause the value of n to be very large with a large number of pairs of factors.
(The programs that I will provide in this lesson are for instructional purposes only, and do not support large values of n. Therefore, you should not use them to encrypt your confidential data and expect your secrets, such as credit card numbers, to be secure from attack.)
Creating the keys
The RSA encryption algorithm consists of two major parts. One part involves performing the mathematical operations required to create the two keys, e and d, and the divisor n. Although not difficult to program, this is the most obscure part from the viewpoint of understanding the algorithm. This operation only has to be done once to establish the public/private key pair and the divisor for each individual user.
Using the keys
The second part involves using the two keys and the divisor to encipher and decipher messages. This must be done for each message, and therefore is an area where computational efficiency may be of concern.
The programs that I will provide to perform this operation have not been optimized for efficiency. Rather, they were written for instructional purposes only. As mentioned earlier, you should not attempt to use these programs for production cryptography. If you need a Java program to do public-key cryptography, you should develop that program using Sun's Java Cryptography Extension.
Which approach is most efficient?
I have read that symmetric algorithms tend to be more computationally efficient than asymmetric algorithms for cases involving large amounts of data. I can neither confirm nor deny that. However, I am aware that in some business transactions involving large amounts of data, an asymmetric approach is used first to distribute a secret symmetric key to both parties and the encryption/decryption process then switches to the use of a symmetric key algorithm.
The first of four programs
I will present and discuss four programs in this lesson. The first program named Rsa07 will illustrate the RSA algorithm from a very intuitive viewpoint requiring no knowledge of advanced mathematics or advanced numerical methods. This approach should be understandable by anyone having a basic knowledge of Java programming. This program uses long arithmetic and is therefore very limited in the size of problems that it can handle due to arithmetic overflow issues.
The second program named Rsa08
The second program is essentially a conversion of the first program from long arithmetic to BigInteger arithmetic. This eliminates the issue of arithmetic overflow and introduces you to the use of the BigInteger class.
With this program, the maximum size problem that you can solve depends on how long you are willing to wait for a solution to develop. On my computer, a few seconds are required to reach a solution for n = 77. I have never had the patience to wait for the solution for n = 399.
Realistically speaking, even a value for n of 399 is a very small problem for real-world cryptography. The inefficiency of this intuitive solution points out the need for using the more sophisticated computational approach provided by the authors of the RSA algorithm.
The third program named Rsa01
The third program extends and completes a small example that is presented in incomplete form by the original authors of the RSA algorithm.
This program uses predetermined keys and a Java implementation to encrypt and decrypt a short message with a block size of 4 and n equal to 2773. This program introduces and explains the issue of message coding and decoding and uses a fairly restrictive character set consisting of the space character and the twenty-six upper-case alphabetic characters.
The fourth program named Rsa03
The fourth program is more general and includes the ability to compute and apply the encryption keys for a character set that includes ninety-five of the most commonly used text characters. The version of the program that I will explain is purposely limited to a block size and key length of six characters.
(Note that a six-character key length is quite small from a security viewpoint. People who analyze the security aspects of the RSA algorithm like to talk about block sizes and key lengths of 100 or more characters for acceptable security.)
This program uses a Java implementation of the algorithm provided by the original authors of the RSA algorithm for the computation of the keys e and d and for the common divisor n.
This program is suitable for experimenting with different block sizes, different divisors, different values for the keys, etc.
The next lesson in this series will extend the fourth program to support the concept of digital signatures.
The first program
The purpose of the program named Rsa07 is to illustrate the RSA algorithm from a very intuitive viewpoint requiring no knowledge of advanced mathematics or advanced numerical methods. As mentioned earlier, this approach should be understandable by anyone having a basic knowledge of Java programming.
Simultaneous equations
I will begin my discussion of this program by describing an analogous situation in a different field. The analogy is the determination of the unknown values in a set of simultaneous equations.Most people who work in a technical field know how to solve for the unknowns in a set of three simultaneous equations with three unknowns. There are several ways to do this. Many of those people are familiar with a solution involving matrix inversion commonly referred to as the use of determinants.
Matrix inversion is a solution
Once a person understands that you can solve three simultaneous equations using matrix inversion, it's not much of a stretch for the same person to also understand that you can also solve much larger sets of simultaneous equations using matrix inversion. Thus, that person has an intuitive knowledge of how to solve for the unknowns in large sets of simultaneous equations involving many more unknowns.
The difference is in the doing
However, there is a very large difference between having an intuitive knowledge of how to solve a set of fifty simultaneous equations using matrix inversion and actually doing it. Inverting the 3x3 matrix required to solve the small problem is much different from inverting the 50x50 matrix required to solve the larger problem. The 3x3 matrix can be inverted using pencil, paper, and a procedure that most of us learned in high school. Inverting the 50x50 matrix requires more sophisticated tools. In all probability, that person will need to consult a textbook or other reputable source to learn how to invert large matrices.
In addition, even though the person may learn to implement the algorithm to invert the larger matrix, without a great deal of study, it is unlikely that the person will ever really understand why it work the way that it does.
The important point
The important point is, even though that person may never fully understand how the algorithm for inverting the large matrix works, the fact that the person has developed an intuitive knowledge of how to solve the small problem using matrix inversion causes the person to also have an intuitive knowledge of how to solve the larger problem. The large-matrix inversion algorithm is nothing more than a tool to help the person achieve a solution for a problem for which he already has an intuitive understanding.
Why am I telling you this?
Unless you have a penchant for advanced mathematics, you may never truly understand how the RSA algorithm, as presented by the original authors, actually works, particularly with respect to the creation of the keys and the divisor. However, my hope is to give you an intuitive understanding of how the RSA algorithm works based on the first two programs. The first program explains the algorithm using an approach that should be understandable by anyone having a fundamental knowledge of Java program. This program is clearly limited to the solution of small problems due to arithmetic overflow issues.
A little more Java knowledge is required
The second program extends the first program by using a particular Java class named BigInteger to eliminate the problem of arithmetic overflow. Otherwise, the second program behaves just like the first.
(In theory, at least, you could use the second program to find the keys for an RSA system of any size if your computer is fast enough and if you have enough patience. However, you may be measuring solution times on the order of years of computer time to develop keys for problems sufficiently large to provide reasonable cryptographic security. In other words, the second program is very useful for instructional purposes, but is impractical for developing actual RSA systems.)
Once you gain the intuitive understanding of how the RSA algorithm works, you can move on to the third and fourth programs, which use the original authors' procedure for creating keys and divisors. You can think of this procedure much the same way that you think of a large-matrix inversion program; simply as a tool for solving a large problem in a reasonable amount of time
Will discuss in fragments
As is usually the case, I will discuss and explain these programs in fragments. Complete listings of all four programs are presented in Listing 45 through Listing 48 near the end of the lesson.
The program named Rsa07
Before getting into the code for the program, the screen output produced by
the program is shown in Figure 1.
n = 14 Range for m: 0 to 13 Range for e: 0 to 13 Range for d: 0 to 13 Allowable keys d:11-e:5 d:13-e:7 d:5-e:11 d:7-e:13 Figure 1 |
I will refer back to this figure while discussing the behavior of this program.
Fundamental RSA behavior
The most fundamental concept in the RSA algorithm is shown in Figure 2.
Given a message (or portion of a message)
represented by an integer value m, the message
can be encrypted into a cipher value by applying
the following transformation:
c = (m^e)%n
where ^ is the exponentiation operator
% is the modulus operator
e is the encryption key
n is an integer constant divisor
Given the cipher value which is represented by
the integer value c, the cipher can be
transformed back into the original message value
by applying the following transformation:
m = (c^d)%n
where d is the decryption key
n is the same integer constant divisor
Figure 2 The RSA algorithm |
Encryption and decryption are not difficult
As you can see, the encryption and decryption transformations are not computationally difficult. In fact, they are especially easy using the BigInteger class in Java, (which may have been designed with applications such as this in mind).
The difficult part
The difficult part is determining the correct values for e, d, and n for message values and key lengths on the order of 100 digits. The first program named Rsa07 will illustrate a relatively easy iterative approach to determining those values for message values having a maximum of two digits.
(As indicated earlier, the purpose is to give you an intuitive understanding of the concepts involved in order to prepare you for the more abstract approach that is used to solve larger problems.)
A simple and intuitive solution
This program provides a very simple and intuitive solution of the RSA encryption algorithm. The program uses iteration along with trial-and-error to determine all of the non-duplicate values for e and d that can be used in combination to encrypt and decrypt message values ranging from 0 through n-1 inclusive when n has a value of 14. Both e and d are constrained to have values of 13 or less.
Reciprocal pairs
Referring back to the screen output shown in Figure 1, you will note that the four allowable combinations for e and d occur as two reciprocal pairs. This confirms that either key can be used to encrypt with the other key being use to decrypt.
Note that this program purposely excludes from the output all combinations of d and e for which d equals e.
The program was tested using SDK 1.4.2 under WinXP.
The main method
The controlling class and the main method for Rsa07 begin in Listing 1.
class Rsa07{
public static void main(String[] args){
long e;//encryption key
long d;//decryption key
long n = 14;//fixed divisor
long c;//encrypted value
long x;//decrypted value
Vector base = new Vector();
Vector temp = new Vector();
|
The code in Listing 1 simply declares variables that will be used later, and populates some of them. In particular, the value for n is set to 14 and remains at that value throughout the execution of the program.
Display the setup information
Listing 2 displays the setup information shown at the top of Figure 1.
System.out.println("n = " + n);
System.out.println(
"Range for m: 0 to " + (n - 1));
System.out.println(
"Range for e: 0 to " + (n - 1));
System.out.println(
"Range for d: 0 to " + (n - 1));
|
Triple nested loops
Listing 3 shows the beginning of a structure of three nested loops that try all combinations of m, d, and e (for the ranges shown in Figure 1) to determine which combinations satisfy the conditions specified in Figure 2.
Those combinations of d and e that satisfy the conditions for every value of m are retained. All other combinations are discarded. In addition, combinations that satisfy the conditions but for which d is equal to e are also discarded.
for(long m = 1; m < n; m++){
for(e = 2; e < n; e++){
c = applyRSA(m,e,n);
|
Practical considerations
Listing 3 shows the beginnings of the loops for m and e. There is no need to begin the outer loop with m equal to 0. The algorithm will always produce an output of 0 for a message value of 0.
We aren't interested in values of either 0 or 1 for e. Raising any non-zero message value to a power of 0 produces 1. Raising a message value to a power of 1 produces the message value, which is not very interesting from an encryption viewpoint. If a message were encrypted using a value of 1 for e, the encrypted message would look just like the unencrypted message.
Things get more interesting in the third line of Listing 3. This line invokes the method named applyRSA passing m, e, and n as parameters.
The applyRSA method
The applyRSA method is shown in its entirety in Listing 4. This method applies the RSA encryption algorithm to an input value using an input key and an input divisor. It returns the encrypted result as type long.
(This is the part of the program that has the potential for arithmetic overflow if the program is run using large values of n.)
static long applyRSA(long val,long exp,long n){
long temp = val;
for(int cnt = 0; cnt < (exp - 1); cnt++){
temp *= val;
if(val >= (Long.MAX_VALUE/val - 1)){
System.out.println(
"Arithmetic overflow probable.");
System.out.println(
"Terminating program.");
System.exit(1);
}//end if
}//end for loop
//Compute the modulus of the modified input
// value using n as a modulus divisor.
return temp % n;
}//end applyRSA
|
Discussion of the code
The applyRSA method begins by using a for loop to raise the value of val to the power given by exp. During each iteration, the method checks for the potential of arithmetic overflow during the next iteration. If arithmetic overflow is probable during the next iteration, the program prints an error message and terminates.
When the loop terminates normally, indicating that val has been raised to the correct power, the method uses the modulus operator to divide by n, discard the quotient, and return the remainder as type long.
Used for either encryption or decryption
This method can be used to execute either of the formulas shown in Figure 2. If the input parameters are m, e, and n, the method encrypts the message value into a cipher value. If the inputs are c, d, and n, the method decrypts a cipher value into a message value.
Test all values of d
Returning to the code in the main method, the innermost loop of the three loops begins in Listing 5.
for(d=2;d < n;d++){
x = applyRSA(c,d,n);
|
The purpose of this loop is to test all possible values of d in the specified range to see if a given value of d, along with the current values of e and m (previously established by the two outer loops) will satisfy the conditions given in Figure 2.
The code in Listing 5 invokes the applyRSA method to decrypt the current cipher value using the current value of d. If this value of d is a valid decryption key, the value returned from the applyRSA method will match the current message value of m.
A process of elimination
The values of e and d that are valid encryption and decryption keys for all values of m are obtained through a process of elimination. This process needs to begin with a list containing all possible combinations of d and e within the specified ranges for d and e.
As it turns out, this list can be produced by processing a message value of 1. The value 1 raised to any power is 1. The value 1 modulus n is also 1. Therefore, all combinations of d and e will successfully encrypt and decrypt a message value of 1.
Test the output against the message value
The code in Listing 6 is the beginning of a pair of nested if statements. If the decrypted output x is not equal to the message value m, then this value of d is not a valid decryption key and everything following within the loop is skipped.
if(x == m){
if(m == 1 && d != e){
base.add(
"d:" + d + "-" + "e:" + e);
|
However, if x is equal to m, then a test is performed to determine if this test was performed on a message value of 1. If so, the values for d and e are encoded into a String and added to a Vector object referred to by the reference variable named base. When the first pass of the outer loop for m equal to 1 has completed processing, this vector will contain all combinations of d and e.
When m is not equal to 1
Listing 7 shows the else clause that goes with the if statement in Listing 6. This code is executed if x equals m but m is not equal to 1.
}else if(d != e){
temp.add(
"d:" + d + "-" + "e:" + e);
}//end else
}//end if(x == m)
}//end for loop on d
}//end for loop on e
|
The code in Listing 7 saves only those combinations of d and e that successfully encrypt and decrypt this value of m. The successful combinations are stored in a Vector object referred to by a reference variable named temp.
The process of elimination
The contents of this Vector will later be matched to the contents of the Vector referred to by base. Any combination contained in base that is not also contained in temp will be removed from base. After all values of m have been processed, only those combinations of d and e that successfully encrypt and decrypt all values of m will remain in base.
Listing 7 also signals the end of the for loop on d and the for loop on e.
Invoke the andVectors method
At this point, control is still within the outer for loop on m.
If the value of m is greater than 1, the code in Listing 8 invokes the method named andVectors to remove all combinations of d and e from base that are not contained in temp. When all values of m have been processed, the only remaining values for d and e that will be contained in base will be those values of e and d that are valid encryption and decryption keys for all values of m.
if(m > 1){
andVectors(base,temp);
}//end if
//Initialize a new empty temp Vector for
// processing the next value of m.
temp = new Vector();
}//end for loop on m
|
A new empty temp Vector
The code in Listing 8 also instantiates a new empty temp Vector object that used to process the next value of m.
Listing 8 also signals the end of the outer loop on m. If all values of m have been processed, control will transfer to Listing 10, which will display the remaining combinations of d and e in the base vector. Otherwise, control will return to the top of the loop and the next value for m will be processed.
The andVectors method
This method, which is shown in Listing 9, performs a logical and operation between the base vector and the temp vector, removing all combinations of d and e from base that are not also contained in temp. This leaves only those elements in base that are contained in both base and temp.
static void andVectors(
Vector base,Vector temp){
Iterator iter = base.iterator();
while(iter.hasNext()){
//Get next element from base.
Object str = iter.next();
//Test to see if temp contains a matching
// element. Remove the element from base
// if there is no match.
if(!temp.contains(str)){
iter.remove();
}//end if
}//end while
}//end andVectors
|
The code in Listing 9 is straightforward, and the comments should make the code self explanatory. Therefore, I won't discuss that code further.
Display the final results
Returning now to the discussion of main, after all values for m have been processed, the code in Listing 10 displays the combinations of d and e that remain in the base vector. The display format is shown in Figure 1.
System.out.println("Allowable keys");
Iterator iter = base.iterator();
while(iter.hasNext()){
String str = (String)iter.next();
System.out.println(str);
}//end while
}//end main
|
Once again, the code in Listing 10 is straightforward so I won't discuss it further.
Listing 10 also signals the end of the main method and the end of the program named Rsa07.
Different values for n
If you decide to run this program for different values of n, you should note that there is no valid solution for some values of n. In that case, the list of allowable keys presented by the program will simply be blank.
I have also noticed that for some values of n, the code that checks for potential arithmetic overflow throws an ArithmeticException: / by zero. However, since it didn't throw the error for the value of n that I was primarily interested in, and because that situation doesn't occur in the improved version (Rsa08) I didn't bother to find and fix that problem. If that proves to be a problem for you, I recommend that you experiment with Rsa08 instead of Rsa07.
The program named Rsa08
The output produced by the program named Rsa08 is shown in Figure 3.
n = 77 Range for m: 0 to 76 Range for e: 0 to 76 Range for d: 0 to 76 Allowable keys d:13-e:7 d:43-e:7 d:73-e:7 d:41-e:11 d:71-e:11 d:7-e:13 d:37-e:13 d:67-e:13 d:23-e:17 d:53-e:17 d:49-e:19 d:17-e:23 d:47-e:23 d:59-e:29 d:61-e:31 d:13-e:37 d:43-e:37 d:73-e:37 d:11-e:41 d:71-e:41 d:7-e:43 d:37-e:43 d:67-e:43 d:23-e:47 d:53-e:47 d:19-e:49 d:17-e:53 d:47-e:53 d:29-e:59 d:31-e:61 d:13-e:67 d:43-e:67 d:73-e:67 d:11-e:71 d:41-e:71 d:7-e:73 d:37-e:73 d:67-e:73 Figure 3 |
Considerably different output
As you can see, this output is considerably different from the output produced by the program named Rsa07 shown in Figure 1 (although the overall format of the two outputs is the same). To begin with, the output in Figure 3 corresponds to a value of 77 for n whereas the output in Figure 1 corresponds to a value of 14 for n. In addition, the ranges for m, e, and d in Figure 3 extend from 0 through 76 inclusive whereas the ranges for the same items in Figure 1 extend from 0 to 13 inclusive.
The biggest difference
Perhaps the biggest difference is the increase in the number of allowable key combinations in Figure 3 as compared to Figure 1. For the set of parameters shown in Figure 3, there are 38 allowable key combinations as compared to only two for the parameters in Figure 1. This increase derives solely from the increased value for n and the increased range for m, e, and d.
Elimination of arithmetic overflow problems
The computational structure of the two programs is the same. However, Rsa08 uses BigInteger arithmetic (as opposed to long arithmetic) to eliminate the arithmetic overflow issue that is a limiting factor for Rsa07.
In theory, you could run this program for as large a value of n as you may desire. However, if you use a very large value of n, the program will require an exceptionally long time to produce a solution. Therefore, using this program for large values of n is not practical.
Excludes output for e equal to d
As with the program named Rsa07, this program purposely excludes all combinations of d and e for which d equals e. Also, as was mentioned regarding Rsa07, the solutions occur in reciprocal value pairs. So there are really only 19 unique combinations of d and e in the output shown in Figure 3.
The BigInteger class
The primary difference between this program and the program named Rsa07 is the use of the methods of the BigInteger class to perform arithmetic and to maintain integer values. In comparison, all of the integer arithmetic in Rsa07 is performed using type long.
As I mentioned in the discussion for Rsa07, that program is subject to arithmetic overflow for values of n above about 14. In theory, the use of BigInteger arithmetic in this program eliminates the possibility of such arithmetic overflow.
What does Sun have to say?
Here is part of what Sun has to say about the BigInteger class:
"Immutable arbitrary-precision integers. All operations behave as if BigIntegers were represented in two's-complement notation (like Java's primitive integer types). BigInteger provides analogues to all of Java's primitive integer operators, and all relevant methods from java.lang.Math. Additionally, BigInteger provides operations for modular arithmetic, GCD calculation, primality testing, prime generation, bit manipulation, and a few other miscellaneous operations."
Some of the extra methods mentioned by Sun in the above quotation are exactly what the doctor ordered for the type of programming being done here. (It is almost as if Sun defined the BigInteger class with cryptography in mind.)
Program conversion
The conversion of the program named Rsa07 to the program Rsa08 mainly involved the substitution of BigInteger method calls for the integer operations in Rsa07.
Because the control structure of this program, which you will find in Listing 46 near the end of the lesson, is essentially the same as the control structure of Rsa07, I won't discuss this program in detail. Rather, I will simply highlight some of the code that illustrates the use of the BigInteger class.
Variable declarations
I will begin with the declaration of variables and the population of some of those variables in main as shown in Listing 11.
BigInteger e;//encryption key
BigInteger d;//decryption key
BigInteger n = new BigInteger("77");
BigInteger c;//encrypted value
BigInteger x;//decrypted value
BigInteger bigOne = new BigInteger("1");
|
Operations on objects
A couple of things are worthy of note in Listing 11. First, BigInteger is the name of a class rather than the name of a primitive type. Therefore, all BigInteger operations are operations on objects rather than operations on primitives.
For example, to initialize the variable named n in Listing 11, it was necessary to instantiate a new object of the BigInteger class. That object's reference was assigned to the reference variable named n.
Further, when the object was instantiated, it was initialized using an integer value of 77 expressed as a String.
Input and output for BigInteger objects
As a practical matter, the input and output to BigInteger objects is in the form of strings of numeric characters of arbitrary length (or arrays of bytes as an alternative to strings).
(While it is possible to extract an int value from a BigInteger object, it is very likely that the value will be too large to fit in either an int or a long and you will simply end up with garbage. Therefore, you need to be extremely careful when you do that.
To extract the contents of a BigInteger object as a string of numeric characters of arbitrary length, simply invoke the toString method on the object.)
A BigInteger object is immutable
In case you are unfamiliar with the term immutable, this means that once you have populated a BigInteger object, its contents cannot be modified. If you need to change the encapsulated value, you simply need to replace the current object with a new object that encapsulates the new value.
The bigOne variable
Many of the operations in this program involve adding or subtracting a value of 1 from a BigInteger object. Therefore, Listing 11 instantiates a BigInteger object that encapsulates the integer value 1 and assigns its reference to the reference variable named bigOne. This will save a lot of typing later on.
The subtract method
Listing 12 illustrates the use of the subtract method of the BigInteger class to subtract the contents of one BigInteger object from another BigInteger object.
System.out.println("n = " + n);
System.out.println("Range for m: 0 to "
+ (n.subtract(bigOne)));
System.out.println("Range for e: 0 to "
+ (n.subtract(bigOne)));
System.out.println("Range for d: 0 to "
+ (n.subtract(bigOne)));
|
The first statement in Listing 12 simply displays the value encapsulated in the BigInteger object referred to by the reference variable named n. This produces the first line of output shown in Figure 3.
The remaining three statements in Listing 12 subtract a value of 1 from the BigInteger objects referred to by n and display the result as a part of a larger overall print statement. The four statements in Listing 12 produce the first four lines of output text shown in Figure 3.
Setting up a for loop
Listing 13 illustrates the use of the methods of the BigInteger class to construct the beginnings of a pair of nested for loops. These loops iterate for all values of m from 1 to n-1 and for all values of e from 2 to n-1.
(Compare Listing 13 with Listing 3 to see how BigInteger programming compares with simple integer programming using type long.)
for(BigInteger m = new BigInteger("1");
m.compareTo(n) < 0; m = m.add(bigOne)){
for(e = new BigInteger("2");
e.compareTo(n) < 0; e = e.add(bigOne)){
c = applyRSA(m,e,n);
|
The compareTo method
The ability to perform relational operations on BigInteger objects involves the use of the compareTo method. Here is part of what Sun has to say about that method:
"Compares this BigInteger with the specified BigInteger. This method is provided in preference to individual methods for each of the six boolean comparison operators (<, ==, >, >=, !=, <=). The suggested idiom for performing these comparisons is: (x.compareTo(y) <op> 0), where <op> is one of the six comparison operators."
This is the syntax used in the conditional clauses in the for loops in Listing 13. Listing 13 also illustrates the use of the add method to increment the loop counters.
Compare the two programs
If you do a side-by-side comparison of the code for Rsa07 in Listing 45 and Rsa08 in Listing 46, you should have no difficulty understanding the remainder of the code in the program named Rsa08.
(Note that the code in Rsa08 makes use of some other interesting methods of the BigInteger class, such as modPow, which I will discuss in conjunction with the program named Rsa01.)
Once again, if you decide to experiment with different values for n, you should use the program named Rsa08 for such experimentation in order to avoid the arithmetic overflow issues manifested by Rsa07.
The program named Rsa01
As explained earlier, this program extends and completes a small example that is presented in incomplete form by the original authors of the RSA algorithm. This program uses predetermined keys and a Java implementation to encrypt and decrypt a short message with a block size of 4 and n equal to 2773.
This program introduces and explains the issue of message coding and decoding and uses a fairly restrictive character set consisting of the space character and the twenty-six upper-case alphabetic characters.
The program output
A complete listing of this program is shown in Listing 47 near the end of the lesson. The program was tested using Sun's Java SDK 1.4.2 under WinXP, producing the output shown in Figure 4.
(Note that the plainText or input text string was extended by one space character to make it evenly divisible by 4.)
p: 47 q: 59 n: 2773 d: 157 e: 17 plainText ITS ALL GREEK TO ME encodedText 0920190001121200071805051100201500130500 cipherText 0948234210841444266323900778077402191655 decipheredText 0920190001121200071805051100201500130500 outputText ITS ALL GREEK TO ME Figure 4 |
Encoding and decoding the message text
Up to this point in this lesson, I haven't discussed anything about the text of the message being encrypted and decrypted. The RSA encryption algorithm is described in Figure 2, and is based solely on the use of a numeric input to produce a numeric output. Therefore, to make use of the RSA algorithm, you must devise a way to encode the text of your message into numeric form before encryption. You must then decode the numeric output from the decryption process using a reverse methodology to produce the original text of the message.
(Note however that there may be filler characters at the end of the decrypted message. This is one approach to dealing with the reality that the length of the encoded version of the message may not be an even multiple of the block size.)
Stream ciphers versus block ciphers
Now that I have mentioned the block size, I need to provide some background information to explain what I mean. Here is a little of what Wikipedia has to say on the subject:
"... ciphers can be broadly grouped into block ciphers and stream ciphers. Stream ciphers encrypt one bit at a time, in contrast to a block cipher, which operates on a group of bits (a "block") of a certain length all in one go."
You can follow the links in the above quotation to learn more about the two types of ciphers.
RSA as a block cipher
As I understand it, the RSA algorithm must be implemented as a block cipher if the original message is of any significant length. As mentioned above, the original text message must be encoded into a string of digits. In my implementation, the string of digits is subdivided into equal length segments of length blockSize.
One such segment forms the message referred to as m in Figure 2. The entire encryption process involves applying the RSA algorithm separately to each of the message segments produced by subdividing the encoded message into blocks.
Two constraints on the common divisor n
The value of the integer constant divisor referred to by n in Figure 2 must have the same number of digits as the blockSize. In addition, the value of n must be larger than the largest possible value of any message m shown in Figure 2.
The encoding scheme for Rsa01
The encoding scheme for Rsa01 is simple and straightforward. The scheme supports 27 characters consisting of a space character and the 26 upper-case characters in the alphabet. The space character is replaced by 00, the A is replaced by 01, the Z is replaced by 26, etc.
Predetermined keys and divisor
The blockSize is 4. Therefore the integer value of a message m can range from 0000 to 2626 inclusive.
The program uses the predetermined values for n, d, and e shown near the top of Figure 4.
The theoretical basis for this program as well as a description of the
example encryption problem are provided by the original authors of
the RSA algorithm at:
http://theory.lcs.mit.edu/~rivest/rsapaper.pdf
This program provides a Java implementation of the encrypting and deciphering
operations described in the author's Small Example
using p, q, n, d, and e given in that example at the above URL.
The main method
The code fragment shown in Listing 14 shows the beginning of the class and the beginning of the main method.
class Rsa01{
public static void main(String[] args){
BigInteger p = new BigInteger("47");
BigInteger q = new BigInteger("59");
BigInteger n = p.multiply(q);
BigInteger d = new BigInteger("157");
BigInteger e = new BigInteger("17");
String plainText = "ITS ALL GREEK TO ME";
|
The first five statements in Listing 14 establish predetermined values from the original author's website encapsulated in BigInteger objects.
The sixth statement in Listing 14 establishes a plainText string, which will be processed by the program, producing the output shown in Figure 4.
Miscellaneous material
The first four statements in Listing 15 declare some strings that will be populated later by the program. The next five statements display the values shown in the first five lines of text in the output shown in Figure 4.
String encodedText = "";
String cipherText = "";
String decipheredText = "";
String outputText = "";
System.out.println("p: " + p);
System.out.println("q: " + q);
System.out.println("n: " + n);
System.out.println("d: " + d);
System.out.println("e: " + e);
Rsa01 obj = new Rsa01();
|
The final statement in Listing 15 instantiates an object of the class and stores its reference in the reference variable named obj.
Deal with potential end-effect problems
For a blockSize of 4, this program processes the characters in the encoded text four characters at a time. The plainText message in this example contains 19 characters. Using the encoding scheme described earlier, the encoded version of the plainText message would be 38 characters long.
Because 38 is not evenly divisible by the blockSize value of 4, this results in a problem that must be dealt with either at this point or later. I chose to deal with it at this point to avoid having to deal with it later.
Append a space character
The code in Listing 16 appends a space character onto the end of the plainText message to cause its length to be an even number of characters. Then when it is encoded as described above, the number of characters in the encoded text will be evenly divisible by the blockSize value of 4.
(Note that this problem could be dealt with after encoding just as well as dealing with it before encoding.)
while(plainText.length()%4 != 0){
//Append a space character on the end
plainText += " ";
}//end while
System.out.println(
"plainText\n" + plainText);
|
The code in Listing 16 also displays the extended plainText method as the seventh line of output text in Figure 4.
Encode the text message
Listing 17 invokes the encode method to encode the extended plainText method. Then Listing 17 displays the encoded text producing the ninth line of text shown in Figure 4.
(Note that the text has not been encrypted at this point. It has simply been encoded into numeric format in preparation for encrypting it using the RSA algorithm.)
encodedText = obj.encode(plainText);
System.out.println(
"encodedText\n" + encodedText);
|
The encode method
Setting the main method aside temporarily, Listing 18 shows the encode method in its entirety.
String encode(String plainText){
byte[] textChars = plainText.getBytes();
String temp = "";
String encodedText = "";
//Build the encoded text string two numeric
// characters at a time. Each plainText
// character is converted to two numeric
// characters according to the relationships
// given above.
for(int cnt = 0; cnt < plainText.length();
cnt++){
temp = String.valueOf(
textChars[cnt] - 'A' + 1);
//Handle the special case of a space
// character.
if(temp.equals("-32")) temp = "00";
//Convert all single-character numeric
// values to two characters with a leading
// zero, as in 09.
if(temp.length() < 2) temp = "0" + temp;
encodedText += temp;
}//end for loop
return encodedText;
}//end encode
|
The purpose of the encode method is to encode a plain text message into numeric format where:
(Note that this encoding scheme supports only space characters and upper-case alphabetic characters.)
The code in Listing 18 implements a simple substitution approach and shouldn't require further explanation. The String that is returned by this method will be encrypted using the RSA algorithm.
Encrypt the encoded text
Listing 19 invokes the doRSA method to encrypt the encoded text. Then it displays the encrypted result as the eleventh line of text in Figure 4.
cipherText = obj.doRSA(encodedText,e,n);
System.out.println(
"cipherText\n" + cipherText);
|
The doRSA method
The doRSA method applies the RSA algorithm to an input string of numeric characters using a specified exponent exp and a specified modulus operator n. The input string is provided as the first input parameter to the method. The values of the exponent and the modulus operator are provided as the second and third input parameters.
This method can be used to encrypt or to decrypt the input string depending on whether the exponent is an encryption key or a decryption key.
The method is hard coded to apply the algorithm for a fixed block size of four characters. Thus, this is not a general-purpose RSA method that can be applied for different block sizes.
(I will provide a more general-purpose version of the method that allows for different block sizes in the next program.)
Let's see some code
Once again setting the main method aside temporarily, Listing 20 shows the beginning of the doRSA method.
String doRSA(String inputString,
BigInteger exp,BigInteger n){
BigInteger block;
BigInteger output;
String temp = "";
String outputString = "";
|
The code in Listing 20 declares and initializes some variables that will be used later.
Process one block at a time
Listing 21 shows the beginning of a for loop that iterates and processes the incoming string by subdividing the string into one block of four characters during each iteration.
for(int cnt = 0; cnt < inputString.length();
cnt += 4){
temp = inputString.substring(cnt,cnt + 4);
block = new BigInteger(temp);
|
The code in Listing 21 gets the next block of four characters and uses them to initialize a new BigInteger object that treats the four character substring as an integer.
(This is where the program gets into trouble and throws an exception if the length of the incoming string is not divisible by 4. In that case, the partial block at the end causes the invocation of the substring method to throw a StringIndexOutOfBoundsException.)
The meaning of the data in block
At this point, the value encapsulated in the BigInteger object referred to by block is analogous to either the value of the message m or the value of the cipher c shown in the explanation of the algorithm in Figure 2.
Raise the block to the power exp
Referring back to Figure 2, the next step is to invoke the modPow method of the BigInteger class to:
This is shown in Listing 22.
output = block.modPow(exp,n); |
The modPow method
This is one of the methods of the BigInteger class that is particularly useful for this type of processing. This method raises this to the exp power, divides the result by n, and returns the remainder.
The magnitude of the remainder
For this case, the message substring encapsulated by block must be a positive integer less than or equal to 2626. Given that n is 2773, the resulting value must be less than 2773 (the remainder can never be greater than the divisor).
Convert remainder to four-character string
For our purposes, we need to convert the remainder to a four-character string inserting leading zeros if necessary. This is accomplished in a somewhat brute force manner shown in Listing 23.
temp = output.toString();
if(temp.length() == 3){
temp = "0" + temp;
}else if(temp.length() == 2){
temp = "00" + temp;
}else if(temp.length() == 1){
temp = "000" + temp;
}//end else if
|
Concatenate to produce the output string
Finally, the statement at the bottom of the for loop in Listing 24 builds the output string four characters at a time by concatenating the results of processing each block of four input characters to the output string.
outputString += temp;
}//end for loop
return outputString;
}//end doRSA
|
When all of the four-character blocks in the input string have been processed, the doRSA method terminates returning the output string.
An encryption operation
When the incoming string is the encoded text message and the incoming parameter named exp is the encryption key, the output is the cipher text shown in the eleventh line of text in Figure 4.
A decryption operation
When the incoming string is the cipher text and the incoming parameter named exp is the decryption key, the output is the deciphered encoded text shown in the thirteenth line in Figure 4.
(Note that the thirteenth line of text matches the encoded text shown in the ninth line in Figure 4.)
Decipher the cipher text
Returning now to the main method, Listing 25 passes the cipherText along with the decryption key d and the common divisor n to the doRSA method to decrypt the encrypted message.
decipheredText = obj.doRSA(cipherText,d,n);
System.out.println(
"decipheredText\n" + decipheredText);
|
Listing 25 displays the result in the thirteenth line in Figure 4. As mentioned earlier, this line of text matches the ninth line of text in Figure 4 which is the encoded message text prior to encryption.
Decode the message
Finally, Listing 26 invokes the decode method to transform the encoded message text back to raw text Listing 26 also displays the result producing the last line of text in Figure 4. As expected, this line of text matches the seventh line of text which was the original plain text message with an extra space appended to the end to handle the end-effect problem.
outputText = obj.decode(decipheredText);
System.out.println(
"outputText\n" + outputText);
}//end main
|
The decode method
The decode method is straightforward, simply reversing the encoding process implemented by the encode method. You can view the decode method in its entirety in the complete listing of program Rsa01 in Listing 47 near the end of the lesson.
The program named Rsa03
IMPORTANT: THIS PROGRAM IS DESIGNED SPECIFICALLY FOR INSTRUCTIONAL PURPOSES. IT WILL NOT EXECUTE PROPERLY FOR BLOCK SIZES AND KEYS GREATER THAN 6 CHARACTERS IN LENGTH.
This program is a significant update to Rsa01. This update makes the program more general. Everything spawns from a specification of the block size. In addition, this program includes the computation of the encryption and decryption keys using a procedure described by the authors of the RSA algorithm.
The encoding and decoding approach used in this program supports the 95 ASCII characters between space and tilde (~) inclusive.
The screen output
This program uses the RSA algorithm along with the computed keys and common
divisor to encrypt and decrypt a message containing 23 characters using a block
size of 4 producing the output shown in Figure 5.
p: 19 q: 503 n: 9557 phi: 9036 e: 17 d: 7973 plainText 0123 89!@ abcd ABCD EF~- encodedText 161718190024250132006566676800333435360037389413 cipherText 831382420004363732998462293181478621167049176719 decipheredText 161718190024250132006566676800333435360037389413 outputText 0123 89!@ abcd ABCD EF~- Figure 5 |
Experimentation
You can experiment with different block sizes by changing the value of the variable named blockSize and recompiling (as long as you don't cause the block size to be greater than 6).
You can experiment with different encryption and decryption keys as well as a different common divisor by changing the value of the variable named e and recompiling.
You can also produce a different decryption key k and a different common divisor n by changing the initial value of p and recompiling.
This program should not be used for production purposes. If you need a Java encryption program for production use, you should develop it using Sun's JCE API.
See the theoretical basis for RSA at: http://theory.lcs.mit.edu/~rivest/rsapaper.pdf
Another good reference is at: http://www.math.mtu.edu/mathlab/COURSES/holt/dnt/phi4.html
Key reversal
Note that you can reverse the use of the two keys for encryption and decryption and get the same results. In other words, it doesn't matter which key you use to encrypt the message into cipher text as long as you use the other key to decrypt the cipher text.
Simultaneous conditions
In order for this algorithm to work correctly, it is necessary for the value of n to be greater than the maximum value of an encoded data block. It is also necessary for the number of characters in the value of n to be less than or equal to the block size. If the program is unable to satisfy both conditions simultaneously, it terminates with an error message.
The program output
This program was tested using SDK 1.4.2 and WinXP. The program produces the output shown in Figure 5.
The Rsa03 class
The controlling class for the program named Rsa03 begins in Listing 27.
class Rsa03{
static class Params{
BigInteger p = new BigInteger("0");
BigInteger q = new BigInteger("0");
BigInteger n = new BigInteger("0");
BigInteger d = new BigInteger("0");
BigInteger e = new BigInteger("15");
BigInteger phi = new BigInteger("0");
BigInteger max;
}//end inner class Params
|
Listing 27 defines a static class named Params inside the class named Rsa03. The purpose of this class is to create an object that serves as a container for the two keys, the modulus operand, and several other important parameters. It was made static so that it can be instantiated from inside the static main method.
The main method
The main method begins in Listing 28.
public static void main(String[] args){
Params par = new Params();
String plainText = "0123 89!@ abcd ABCD EF~";
//Strings to be populated by the program.
String encodedText = "";
String cipherText = "";
String decipheredText = "";
String outputText = "";
int blockSize = 4;
if(blockSize % 2 != 0){
System.out.println(
"blockSize must be even");
System.exit(1);
}//end if
String maxEncodedString = "";
for(int cnt = 0; cnt < blockSize; cnt += 2){
maxEncodedString += "94";
}//end for loop
par.max = new BigInteger(maxEncodedString);
|
The code in Listing 28 is straightforward. It does the following:
Get initial value for p
If you visit the theoretical basis published by the original authors of the RSA algorithm, you will see that the process of computing the keys requires the product of two prime numbers, p and q, whose product, n, must be greater than the largest possible value of a data block.
(In addition, the number of characters in the product must not be greater than the block size in order for the algorithm to work properly.)
Listing 29 computes an initial value for p. There is nothing special about the approach used to get the initial value in Listing 29. In fact, it might be preferable to use a random number generator to produce this initial value. The final value for p will be a prime number close to this value.
par.p = par.max.divide(
new BigInteger("502"));
Rsa03 obj = new Rsa03();
|
Listing 29 also instantiates an object of the class and saves its reference in the reference variable named obj.
Get and display keys
Listing 30 invokes the getKeys method to get and then to display the values of the keys, e and d, and other important parameters in the first six lines of Figure 5.
obj.getKeys(par,blockSize);
System.out.println("p: " + par.p);
System.out.println("q: " + par.q);
System.out.println("n: " + par.n);
System.out.println("phi: " + par.phi);
System.out.println("e: " + par.e);
System.out.println("d: " + par.d);
|
The getKeys method
The getKeys method is new to this program. It was not included in any of the previous three programs. This method implements the algorithm published by the original authors of the RSA method for computing the public and private keys, e and d, as well as the common divisor, n, as described in Figure 2.
I will make no attempt in this lesson to explain how and why this algorithm works for producing e, d, and n. Rather, I will simply walk you through the code that implements the steps described by the authors.
Code for the getKeys method
Putting the main method aside temporarily, the getKeys method begins in Listing 31. As you can see, this method receives a reference to the container object for the keys and other parameters along with the block size as parameters.
The method begins by instantiating a BigInteger object that encapsulates the value 1.
void getKeys(Params par,int blockSize){
//A frequently used constant
BigInteger bigOne = new BigInteger("1");
while(!(par.p.isProbablePrime(1000))){
par.p = par.p.add(bigOne);
}//end while loop
|
Needed, two prime numbers
Then the getKeys method initiates the process of selecting two prime numbers, p and q, such that the following two conditions are satisfied where max is the maximum possible data value in a data block:
The first task is to get a prime number close to the initial value for p produced in Listing 29. The method uses this incoming initial value for p and then iterates by increasing the value of p until a highly-probable prime number is found.
The isProbablePrime method
As far as I can tell, there is no method to determine with absolute certainty whether or not the value of a BigInteger is prime. However, the BigInteger class provides the isProbablePrime method, which makes it possible to determine within a specified level of uncertainty whether or not a given BigInteger value is a prime number.
(The larger the value passed to the method, the longer the method takes to execute, and the greater is the certainty that the number is prime if the method returns true.)
This is the method used in the loop in Listing 31 to get a probable prime number for p that is close to the initial value for p.
Get a prime number for q
The next step is to get a prime number for q that satisfies the two conditions listed earlier. This process begins in Listing 32.
String firstQ =
"" + (par.p.subtract(bigOne));
par.q = new BigInteger(firstQ);
|
Listing 32 makes a first guess for the value of q as being one less than the current prime value of p. This value will be modified through iteration until a value is found that satisfies the conditions listed earlier, or it is concluded that those conditions cannot be satisfied.
Satisfy the block size constraint on n
Without regard for whether or not q is prime, Listing 33 gets a value for q for which the number of digits in the product p*q doesn't exceed the block size. This is done by successively halving the value for q until the condition is satisfied.
Then Listing 33 divides the value of q by 2 one more time to allow some room for incrementing the value of q later.
par.n = par.p.multiply(par.q);
while(par.n.toString().length() > blockSize){
par.q = par.q.divide(new BigInteger("2"));
par.n = par.p.multiply(par.q);
}//end while
par.q = par.q.divide(new BigInteger("2"));
|
Now get a prime number for q
The current value of q satisfies one of the two required conditions, but may not be a prime number. Listing 34 gets the next prime number that is smaller than the current value of q.
while(!(par.q.isProbablePrime(1000))){
par.q = par.q.subtract(bigOne);
}//end while loop
|
Satisfy the condition n > max
Now we have prime values for p and q such that the number of characters in p*q is less than or equal to the block size. Next we need to confirm that the product of p and q is greater than the maximum possible value for a data block. This accomplished in Listing 35 by successively increasing the value of q by 1 until the condition is met.
(Note, however, that this adjustment could violate the previously satisfied condition involving the number of characters and the block size.)
par.n = par.p.multiply(par.q);
while(par.n.compareTo(par.max) <= 0){
//Get a larger prime value for q
par.q = par.q.add(bigOne);
while(!(par.q.isProbablePrime(1000))){
par.q = par.q.add(bigOne);
}//end while loop
//Compute the new value for n and go back
// to the top and test again.
par.n = par.p.multiply(par.q);
}//end while loop
|
Confirm that both conditions are met
Listing 36 confirms that both conditions are still being met. If not, the program terminates with an error message.
if((par.n.toString().length() > blockSize)
|| (par.n.compareTo(par.max) <= 0)){
System.out.println(
"Required conditions are not met");
System.exit(1);
}//end if
|
Three more steps
There are three more steps required to compute e, d, and n as described in Figure 2. The next step is to compute a value referred to by the original authors as phi (although it is described by those authors using the Greek character for phi in their paper).
This computation is straightforward as shown in Listing 37.
//Compute phi, as (p - 1)*(q - 1).
BigInteger pPrime = par.p.subtract(bigOne);
BigInteger qPrime = par.q.subtract(bigOne);
par.phi = pPrime.multiply(qPrime);
Listing 37
|
Greatest common denominator
The next step is to find a value for e such that the greatest common denominator of e and phi is equal to 1. This is accomplished using the gcd method of the BigInteger class as shown in Listing 38.
//Compute e. First guess is incoming
// value.
while(!par.e.gcd(par.phi).equals(bigOne)){
par.e = par.e.add(bigOne);
}//end while loop
Listing 38
|
The gcd method is straightforward enough, so I will simply refer you to the Sun documentation to read about it.
The mod inverse method
The final step is to compute the value of d using the modInverse method of the BigInteger class as shown in Listing 39.
//Compute the value for d
par.d = par.e.modInverse(par.phi);
}//end getKeys
|
Obscure steps
Listing 39 also signals the end of the getKeys method.
The purpose of these three final steps in the getKeys method may seem somewhat obscure. If you really want to understand how and why they accomplish what they do, you can read the mathematical derivation of the algorithm provided by the original authors of the RSA algorithm.
Alternatively, you can take it on faith that they successfully developed a mathematical solution to the same problem that we solved using brute force trial and error iteration in the programs named Rsa07 and Rsa08. Hopefully, even if you don't understand the mathematical solution, you do have an intuitive understanding of the solution based on those two programs.
The screen output
The first six lines of text in Figure 5 show the values produced by the invocation of the getKeys method in this program.
Adjust the message length
Returning to the main method, the code in Listing 40 forces the plain text message length to be a multiple of half the block size to avoid the end-effect problems discussed earlier.
while(plainText.length()%(blockSize/2) != 0){
plainText += "-";
}//end while
System.out.println(
"plainText\n" + plainText);
|
In this case, I purposely extended the message with dashes so that the extension would be visible in the screen output. Listing 40 also displays the extended message as shown in Figure 5.
Encode the plain text
Listing 41 encodes the plain text into numeric format to prepare it for encryption using the RSA algorithm and displays the encoded result in Figure 5.
encodedText = obj.encode(plainText);
System.out.println(
"encodedText\n" + encodedText);
|
The encode method
The encode method that is invoked in Listing 41 to encode the plain text message is very similar to the method having the same name in the program named Rsa01. The main difference is that this version supports ninety-five characters extending from the space character to the tilde (~) character in the ASCII character set.
The purpose of this version of the encode method is to encode a plain text message into numeric format where:
The code used to accomplish this is straightforward and won't be discussed in detail. You can view that code in Listing 48 near the end of the lesson.
Encrypt the encoded message
Listing 42 invokes the doRSA method to encrypt the encoded text and displays the encrypted message as the twelfth line of output in Figure 5.
Note that this invocation of the method receives the encryption key e an incoming parameter.
//Encrypt the encoded text and display the
// result.
cipherText = obj.doRSA(encodedText,par.e,
par.n,blockSize);
System.out.println(
"cipherText\n" + cipherText);
|
The doRSA method
This version of the doRSA method is very similar to the version that I explained in conjunction with the program named Rsa01 beginning in Listing 20. The primary difference is that the previous version was hard-coded to work on a block size of 4. This version receives the block size as an incoming parameter and uses that value as a variable.
Because of the similarity of the two versions, I won't discuss this version in detail. You can view the method in Listing 48 near the end of the lesson.
Decrypt the encrypted message
The code in Listing 43 invokes the doRSA method again, passing the decryption key d as a parameter to decrypt the encrypted message.
decipheredText = obj.doRSA(cipherText,par.d
,par.n,blockSize);
System.out.println(
"decipheredText\n" + decipheredText);
|
Listing 43 also displays the decrypted message as the fourteenth line of output in Figure 5. Note that the decrypted message exactly matches the encoded text in the tenth line in Figure 5 as would be expected.
Decode the message
Listing 44 invokes the decode method to transform the message from numeric format back to plain text. Listing 44 also displays the resulting text as the last line in Figure 5. As you can see, the result is an exact match for the extended plain text message shown in the eighth line of Figure 5.
outputText = obj.decode(decipheredText);
System.out.println(
"outputText\n" + outputText);
}//end main
|
Listing 44 also signals the end of the main method and the end of the program.
The decode method
The decode method simply reverses the transformation performed by the encode method discussed earlier. The code in the decode method is straightforward and doesn't merit a detailed discussion here. You can view the decode method in its entirety in Listing 48 near the end of the lesson.I encourage you to copy, compile and run the following programs that are provided in this lesson:
Experiment with the programs, making changes and observing the results of your changes.
Above all, have fun and use these programs to learn as much as you can about the theory behind and the mechanics of public key cryptography as implemented using Java.
In this lesson, I explained the general philosophy of public key cryptography. I also provided four sample programs that illustrate various aspects of public key cryptography through the use of the RSA algorithm.
The first two programs were designed to give you an intuitive understanding of the RSA algorithm.
The third program provides a Java implementation of a small example that is presented in incomplete form by the RSA algorithm's authors.
The fourth program is a more general implementation of the RSA algorithm.
The next lesson in this series will explain the use of public key cryptography for the creation and use of digital signatures for the signing of messages.
Future lessons will explain the use of symmetric key cryptography using Java.
Complete listings of the programs discussed in this lesson are provided in Listing 45 through Listing 48 below.
A disclaimer
The programs that I am providing and explaining in this series of lessons are not intended to be used for production cryptography. If you need to do cryptography using Java, you should use Sun's Java Cryptography Extension (JCE).
The programs that I am providing were developed solely for instructional purposes. They are intended to help you to experiment with and to learn about various cryptographic algorithms and to gain a better understanding of how they work, and why they do what they do.
/*File Rsa07.java
Copyright 2004, R.G.Baldwin
The purpose of this program is to provide a very
simple and intuitive explanation of the RSA
encryption algorithm. This program uses
iteration to determine all of the non-duplicate
values for e and d that can be used in
combination to encrypt and decrypt message values
ranging from 0 through 13 inclusive when n has a
value of 14. Both e and d are constrained to
have values of 13 or less.
Tested using SDK 1.4.2 under WinXP.
The program output is:
n = 14
Range for m: 0 to 13
Range for e: 0 to 13
Range for d: 0 to 13
Allowable keys
d:11-e:5
d:13-e:7
d:5-e:11
d:7-e:13
Note that the program purposely excludes all
combinations for which d equals e.
Note that these four combinations occur as two
reciprocal pairs. This confirms the notion that
either key can be used to encrypt with the other
key being use to decrypt.
************************************************/
import java.util.*;
class Rsa07{
public static void main(String[] args){
long e;//encryption key
long d;//decryption key
long n = 14;//fixed divisor
long c;//encrypted value
long x;//decrypted value
Vector base = new Vector();
Vector temp = new Vector();
System.out.println("n = " + n);
System.out.println(
"Range for m: 0 to " + (n - 1));
System.out.println(
"Range for e: 0 to " + (n - 1));
System.out.println(
"Range for d: 0 to " + (n - 1));
//Iterate for all values of m from 1 to 13.
// No need to include 0 because 0 raised to
// any power is 0.
for(long m = 1; m < n; m++){
//Iterate for all values of e from 2 to 13.
// No need to include 1 because raising the
// message to the first power is not
// interesting.
for(e = 2; e < n; e++){
//Compute the cipher value c for the
// current value of m and the current
// value of e.
c = applyRSA(m,e,n);
//Search for all values of d that will
// successfully decrypt the cipher value.
for(d=2;d < n;d++){
//Decipher c using current value of d
x = applyRSA(c,d,n);
//Test for correct decyphered value.
if(x == m){
//Enable the following statement to
// see intermediate results.
//System.out.println(
// "Success, d=" + d + " e=" + e
// + " " + "m=" + m + " " + "c="
// + c + " " + "x=" + x);
if(m == 1 && d != e){
//Raising 1 to any power produces
// 1. Therefore, all combinations
// of d and e will successfully
// encrypt and decrypt a message
// value of 1. Store all
// combinations of d and e in the
// base Vector where they will be
// systematically eliminated as the
// remaining values of m are
// processed.
base.add(
"d:" + d + "-" + "e:" + e);
}else if(d != e){
//Store only those combinations of
// d and e that will successfully
// encrypt and decrypt this value
// of m in the Vector named temp.
// The contents of this Vector
// will be matched to the contents
// of base. Any combination
// contained in base that is not
// also contained in temp will be
// removed from base. After all
// values of m have been processed,
// only those combinations of d and
// e that successfully encrypt and
// decrypt all values of m will
// remain in base.
temp.add(
"d:" + d + "-" + "e:" + e);
}//end else
}//end if(x == m)
}//end for loop on d
}//end for loop on e
if(m > 1){
//Remove all elements from base that are
// not also contained in temp.
andVectors(base,temp);
}//end if
//Initialize a new empty temp Vector for
// processing the next value of m.
temp = new Vector();
}//end for loop on m
//After all values for m have been processed,
// display the remaining combinations of d
// and e in base.
System.out.println("Allowable keys");
Iterator iter = base.iterator();
while(iter.hasNext()){
String str = (String)iter.next();
System.out.println(str);
}//end while
}//end main
//-------------------------------------------//
//This method tests each element in base to see
// if it is contained in temp. If not, the
// element is removed from base. This
// effectively performs an and operation
// between base and temp leaving only those
// elements in base that are contained in both
// base and temp.
static void andVectors(
Vector base,Vector temp){
Iterator iter = base.iterator();
while(iter.hasNext()){
//Get next element from base.
Object str = iter.next();
//Test to see if temp contains a matching
// element. Remove the element from base
// if there is no match.
if(!temp.contains(str)){
iter.remove();
}//end if
}//end while
}//end andVectors
//-------------------------------------------//
//This method applies the RSA encryption
// algorithm to an input value using an input
// key and an input divisor. It returns the
// result as type long.
static long applyRSA(long val,long exp,long n){
long temp = val;
//Raise the input value to the exp power.
// Could use Math.pow method but might suffer
// a loss of accuracy when converting result
// from double to long.
for(int cnt = 0; cnt < (exp - 1); cnt++){
temp *= val;
if(val >= (Long.MAX_VALUE/val - 1)){
System.out.println(
"Arithmetic overflow probable.");
System.out.println(
"Terminating program.");
System.exit(1);
}//end if
}//end for loop
//Compute the modulus of the modified input
// value using n as a modulus divisor.
return temp % n;
}//end applyRSA
//-------------------------------------------//
}//end class Rsa07
Listing 45
|
/*File Rsa08.java
Copyright 2004, R.G.Baldwin
The purpose of this program is to provide a very
simple and intuitive explanation of the RSA
encryption algorithm. This program uses
iteration to determine all of the non-duplicate
values for e and d that can be used in
combination to encrypt and decrypt message values
ranging from 0 through n-1 inclusive. Both e and
d are constrained to have values less than n.
This update to Rsa07 uses BigInteger rather than
long arithmetic to avoid arithmetic overflow and
to allow for the solution of larger problems than
can be solved using Rsa07. Otherwise, the
algorithm used by this program is the same as the
algorithm used by Rsa07.
Thus, this program provides an introduction to
the use of BigInteger arithmetic. You can solve
problems for values of n greater than is the
case with Rsa07. However, if you make n much
larger than 77, be prepared to wait quite a while
for the solution to develop.
Note that there is no valid solution for some
values of n. In that case, the list of allowable
keys presented by the program will simply be
blank.
Tested using SDK 1.4.2 under WinXP.
The program output for n = 77 is:
n = 77
Range for m: 0 to 76
Range for e: 0 to 76
Range for d: 0 to 76
Allowable keys
d:13-e:7
d:43-e:7
d:73-e:7
d:41-e:11
d:71-e:11
d:7-e:13
d:37-e:13
d:67-e:13
d:23-e:17
d:53-e:17
d:49-e:19
d:17-e:23
d:47-e:23
d:59-e:29
d:61-e:31
d:13-e:37
d:43-e:37
d:73-e:37
d:11-e:41
d:71-e:41
d:7-e:43
d:37-e:43
d:67-e:43
d:23-e:47
d:53-e:47
d:19-e:49
d:17-e:53
d:47-e:53
d:29-e:59
d:31-e:61
d:13-e:67
d:43-e:67
d:73-e:67
d:11-e:71
d:41-e:71
d:7-e:73
d:37-e:73
d:67-e:73
Note that the program purposely excludes all
combinations for which d equals e.
As was discussed in Rsa07, the solutions occur
in reciprocal value pairs.
************************************************/
import java.util.*;
import java.math.BigInteger;
class Rsa08{
public static void main(String[] args){
BigInteger e;//encryption key
BigInteger d;//decryption key
//Fixed divisor
BigInteger n = new BigInteger("77");
BigInteger c;//encrypted value
BigInteger x;//decrypted value
//Commonly used constant
BigInteger bigOne = new BigInteger("1");
Vector base = new Vector();
Vector temp = new Vector();
System.out.println("n = " + n);
System.out.println("Range for m: 0 to "
+ (n.subtract(bigOne)));
System.out.println("Range for e: 0 to "
+ (n.subtract(bigOne)));
System.out.println("Range for d: 0 to "
+ (n.subtract(bigOne)));
//Iterate for all values of m from 1 to n-1.
// No need to include 0 because 0 raised to
// any power is 0.
for(BigInteger m = new BigInteger("1");
m.compareTo(n) < 0; m = m.add(bigOne)){
//Iterate for all values of e from 2 to
// n-1. No need to include 1 because
// raising the message to the first
//power is not interesting.
for(e = new BigInteger("2");
e.compareTo(n) < 0; e = e.add(bigOne)){
//Compute the cipher value c for the
// current value of m and the current
// value of e.
c = applyRSA(m,e,n);
//Search for all values of d from 2 to
// n-1 that will successfully decrypt
// the cipher value.
for(d = new BigInteger("2");
d.compareTo(n) < 0;d = d.add(bigOne)){
//Decipher c using current value of d
x = applyRSA(c,d,n);
//Test for correct deciphered value.
if(x.compareTo(m) == 0){//if(x == m)
if((m.compareTo(bigOne) == 0)
&& (d.compareTo(e) != 0)){
//Raising 1 to any power produces
// 1. Therefore, all combinations
// of d and e will successfully
// encrypt and decrypt a message
// value of 1. Store all
// combinations of d and e in the
// base Vector where they will be
// systematically eliminated as the
// remaining values of m are
// processed.
base.add("d:" + d.toString() + "-"
+ "e:" + e.toString());
}else if(d.compareTo(e) != 0){
//Store only those combinations of
// d and e that will successfully
// encrypt and decrypt this value
// of m in the Vector named temp.
// The contents of this Vector
// will be matched to the contents
// of base. Any combination
// contained in base that is not
// also contained in temp will be
// removed from base. After all
// values of m have been processed,
// only those combinations of d and
// e that successfully encrypt and
// decrypt all values of m will
// remain in base.
temp.add("d:" + d.toString() + "-"
+ "e:" + e.toString());
}//end else
}//end if(x == m)
}//end for loop on d
}//end for loop on e
if(m.compareTo(bigOne) > 0){//if(m > 1)
//Remove all elements from base that are
// not also contained in temp.
andVectors(base,temp);
}//end if
//Initialize a new empty temp Vector for
// processing the next value of m.
temp = new Vector();
}//end for loop on m
//After all values for m have been processed,
// display the remaining combinations of d
// and e in base.
System.out.println("Allowable keys");
Iterator iter = base.iterator();
while(iter.hasNext()){
String str = (String)iter.next();
System.out.println(str);
}//end while
}//end main
//-------------------------------------------//
//This method tests each element in base to see
// if it is contained in temp. If not, the
// element is removed from base. This
// effectively performs an and operation
// between base and temp leaving only those
// elements in base that are contained in both
// base and temp.
static void andVectors(
Vector base,Vector temp){
Iterator iter = base.iterator();
while(iter.hasNext()){
//Get next element from base.
Object str = iter.next();
//Test to see if temp contains a matching
// element. Remove the element from base
// if there is no match.
if(!temp.contains(str)){
iter.remove();
}//end if
}//end while
}//end andVectors
//-------------------------------------------//
//This method applies the RSA encryption
// algorithm to an input value using an input
// key and an input divisor. It returns the
// result as type BigInteger.
static BigInteger applyRSA(BigInteger val,
BigInteger exp,
BigInteger n){
//Raise the input value to the exp power,
// divide by n, throw away the quotient, and
// return the remainder..
return val.modPow(exp,n);
}//end applyRSA
//-------------------------------------------//
}//end class Rsa08
Listing 46
|
/*File Rsa01.java
Copyright 2004, R.G.Baldwin
This program illustrates a very simple example
of encrypting and deciphering using the RSA
algorithm.
See the theoretical basis at:
http://theory.lcs.mit.edu/~rivest/rsapaper.pdf
This program implements the encrypting and
deciphering in the Small Example using p, q,
n, d, and e given in that example at the
above URL.
Another good reference is at:
http://www.math.mtu.edu/mathlab/COURSES/holt/dnt
/phi4.html
Tested using SDK 1.4.2 and WinXP. This program
produces the following output:
p: 47
q: 59
n: 2773
d: 157
e: 17
plainText
ITS ALL GREEK TO ME
encodedText
0920190001121200071805051100201500130500
cipherText
0948234210841444266323900778077402191655
decipheredText
0920190001121200071805051100201500130500
outputText
ITS ALL GREEK TO ME
Note that the plainText string was extended by
one space character to make it evenly divisible
by 4.
************************************************/
import java.math.BigInteger;
class Rsa01{
public static void main(String[] args){
//Values from original author's web page.
// See URL in above comments.
BigInteger p = new BigInteger("47");
BigInteger q = new BigInteger("59");
BigInteger n = p.multiply(q);
BigInteger d = new BigInteger("157");
BigInteger e = new BigInteger("17");
String plainText = "ITS ALL GREEK TO ME";
//Strings to be populated by the program.
String encodedText = "";
String cipherText = "";
String decipheredText = "";
String outputText = "";
System.out.println("p: " + p);
System.out.println("q: " + q);
System.out.println("n: " + n);
System.out.println("d: " + d);
System.out.println("e: " + e);
Rsa01 obj = new Rsa01();
//Force the plainText length to be a multiple
// of half the block size to avoid end-effect
// problem later.
while(plainText.length()%4 != 0){
//Append a space character on the end
plainText += " ";
}//end while
System.out.println(
"plainText\n" + plainText);
//Encode the plain text into numeric format
// and display the result.
encodedText = obj.encode(plainText);
System.out.println(
"encodedText\n" + encodedText);
//Encrypt the encoded text and display the
// result.
cipherText = obj.doRSA(encodedText,e,n);
System.out.println(
"cipherText\n" + cipherText);
//Decipher the cipherText and display the
// result. Should match the encoded text
// above with the possibility of extra
// characters to represent spaces at the
// end.
decipheredText = obj.doRSA(cipherText,d,n);
System.out.println(
"decipheredText\n" + decipheredText);
//Decode back to plain text and display the
// result. Should match the input plainText
// with the possibility of extra space
// characters at the end.
outputText = obj.decode(decipheredText);
System.out.println(
"outputText\n" + outputText);
}//end main
//-------------------------------------------//
//The purpose of this method is to encode a
// plain text message into numeric format
// where:
// space = 00
// A = 01
// B = 02
// C = 03
// ...
// J = 10, etc.
// Note that this encoding method supports only
// space characters and upper-case alphabetic
// characters.
String encode(String plainText){
byte[] textChars = plainText.getBytes();
String temp = "";
String encodedText = "";
//Build the encoded text string two numeric
// characters at a time. Each plainText
// character is converted to two numeric
// characters according to the relationships
// given above.
for(int cnt = 0; cnt < plainText.length();
cnt++){
temp = String.valueOf(
textChars[cnt] - 'A' + 1);
//Handle the special case of a space
// character.
if(temp.equals("-32")) temp = "00";
//Convert all single-character numeric
// values to two characters with a leading
// zero, as in 09.
if(temp.length() < 2) temp = "0" + temp;
encodedText += temp;
}//end for loop
return encodedText;
}//end encode
//-------------------------------------------//
//The purpose of this method is to reverse the
// encoding process implemented by the encode
// method, converting a string of numeric
// characters back to a text string containing
// space characters and upper-case alphabetic
// characters.
String decode(String encodedText){
String temp = "";
String decodedText = "";
for(int cnt = 0; cnt < encodedText.length();
cnt += 2){
temp = encodedText.substring(cnt,cnt + 2);
//Convert two numeric text characters to a
// value of type int.
int val = Integer.parseInt(temp);
//Convert int value to an ASCII character
// value for the space character and the
// upper-case alphabetic characters.
if(val == 0){
val = 32;//blank
}else{
val += ('A' -1);
}//end else
//Convert the ASCII character values to
// numeric String values and build the
// output String one character at a time.
decodedText += String.valueOf((char)val);
}//end for loop
return decodedText;
}//end decode
//-------------------------------------------//
//Apply the RSA algorithm to an input string
// using the exponent exp and the modulus
// operator n, which are provided as input
// parameters. This method can be used to
// encrypt or to decipher the input string
// depending on whether the exponent is an
// encryption key or a decryption key. Apply
// the algorithm for a block size of four
// characters. This block size is based on the
// known number of characters in the modulus
// operator n, and may not be appropriate
// for other modulus operators. Thus, this is
// not a general-purpose RSA method.
String doRSA(String inputString,
BigInteger exp,BigInteger n){
BigInteger block;
BigInteger output;
String temp = "";
String outputString = "";
//Iterate and process one block at a time.
for(int cnt = 0; cnt < inputString.length();
cnt += 4){
//Get the next block of four characters
// and encapsulate them in a BigInteger
// object.
temp = inputString.substring(cnt,cnt + 4);
block = new BigInteger(temp);
//Raise the block to the power exp, apply
// the modulus operand n, and save the
// remainder. This is the essence of the
// RSA algorithm.
output = block.modPow(exp,n);
//Convert the numeric result to a
// four-character string, appending leading
// zeros as necessary.
temp = output.toString();
if(temp.length() == 3){
temp = "0" + temp;
}else if(temp.length() == 2){
temp = "00" + temp;
}else if(temp.length() == 1){
temp = "000" + temp;
}//end else if
//Build the outputString four characters at
// a time. Each character in the
// inputString results in one character in
// the outputString. Referring back to the
// plainText string, encryption produces
// two output characters for each character
// in the plainText string after extending
// the plainText string to make it
// divisible by four if necessary.
outputString += temp;
}//end for loop
return outputString;
}//end doRSA
//-------------------------------------------//
}//end class Rsa01
Listing 47
|
/*File Rsa03.java
Copyright 2004, R.G.Baldwin
IMPORTANT: THIS PROGRAM IS DESIGNED SPECIFICALLY
FOR INSTRUCTIONAL PURPOSES. IT CANNOT BE USED
FOR BLOCK SIZES AND KEYS GREATER THAN 6
CHARACTERS IN LENGTH.
This is a significant update to Rsa01. This
update makes the program more general.
Everything spawns from a specification of the
block size. For example, this program includes
the computation of the encryption and
deciphering keys in addition to the modulus
operand n.
The encoding and decoding approach used in this
program supports the 95 ASCII characters between
space and tilde (~) inclusive.
This program uses the RSA algorithm to encrypt
and decipher a message containing 23 characters
using a block size of 4 producing the results
shown below.
You can experiment with different block sizes
by changing the value of the variable named
blockSize and recompiling.
You can experiment with different encryption
and deciphering keys as well as a different
modulus operand by changing the value of
the variable named e and recompiling.
You can also produce a different deciphering
key and a different modulus operand by changing
the initial value of p and recompiling.
This program should not be used for production
purposes. If you need a Java program for
production use, you should develop it using Sun's
JCE API.
See the theoretical basis for RSA at:
http://theory.lcs.mit.edu/~rivest/rsapaper.pdf
Another good reference is at:
http://www.math.mtu.edu/mathlab/COURSES/holt/dnt
/phi4.html
Tested using SDK 1.4.2 and WinXP. This program
produces the following output:
p: 19
q: 503
n: 9557
phi: 9036
e: 17
d: 7973
plainText
0123 89!@ abcd ABCD EF~-
encodedText
161718190024250132006566676800333435360037389413
cipherText
831382420004363732998462293181478621167049176719
decipheredText
161718190024250132006566676800333435360037389413
outputText
0123 89!@ abcd ABCD EF~-
Also note that you can reverse the use of the
two keys and get the same results. In other
words, it doesn't matter which key you use to
encrypt the message into cipherText as long
as you use the other key to decipher the
cipherText.
In order for this algorithm to work correctly, it
is necessary for the value of n to be greater
than the maximum value of an encoded data block.
It is also necessary for the number of characters
in the value of n to be less than or equal to the
block size. If the program is unable to satisfy
both conditions simultaneously, it terminates
with an error message.
************************************************/
import java.math.BigInteger;
class Rsa03{
//This is a static inner class whose sole
// purpose is to create an object that serves
// as a container for several important
// parameters. It was made static so that
// it can be instantiated from within main.
static class Params{
BigInteger p = new BigInteger("0");
BigInteger q = new BigInteger("0");
BigInteger n = new BigInteger("0");
BigInteger d = new BigInteger("0");
BigInteger e = new BigInteger("15");
BigInteger phi = new BigInteger("0");
BigInteger max;
}//end inner class Params
public static void main(String[] args){
//Instantiate an object in which to store
// parameters.
Params par = new Params();
//Test data.
String plainText = "0123 89!@ abcd ABCD EF~";
//Strings to be populated by the program.
String encodedText = "";
String cipherText = "";
String decipheredText = "";
String outputText = "";
//Set blockSize and make certain that it is
// divisible by 2.
int blockSize = 4;
if(blockSize % 2 != 0){
System.out.println(
"blockSize must be even");
System.exit(1);
}//end if
//Get and save the maximum value of an
// encoded string for the specified block
// size and the encoding format used.
String maxEncodedString = "";
for(int cnt = 0; cnt < blockSize; cnt += 2){
maxEncodedString += "94";
}//end for loop
par.max = new BigInteger(maxEncodedString);
//Create an initial value for p. The final
// value for p will be a prime close to this
// value. Could use a random number
// generator here to cause this value to be
// random.
par.p = par.max.divide(
new BigInteger("502"));
//Instantiate an object of this class
Rsa03 obj = new Rsa03();
//Get and display the key values along with
// the other parameter values.
obj.getKeys(par,blockSize);
System.out.println("p: " + par.p);
System.out.println("q: " + par.q);
System.out.println("n: " + par.n);
System.out.println("phi: " + par.phi);
System.out.println("e: " + par.e);
System.out.println("d: " + par.d);
//Force the plainText length to be a multiple
// of half the block length to avoid
// end-effect problems later.
while(plainText.length()%(blockSize/2) != 0){
//Append a visible character on the end.
// A space would probably be better, but
// I wanted to be able to see the extension
// character for illustration purposes.
// Remember, this code is intended for
// illustration of the algorithm and is
// not intended for production use.
plainText += "-";
}//end while
System.out.println(
"plainText\n" + plainText);
//Encode the plain text into numeric format
// and display the result. Note that
// encoding is not the same as encrypting.
// Encoding simply prepares the message
// for encryption by converting it to a
// numeric representation.
encodedText = obj.encode(plainText);
System.out.println(
"encodedText\n" + encodedText);
//Encrypt the encoded text and display the
// result.
cipherText = obj.doRSA(encodedText,par.e,
par.n,blockSize);
System.out.println(
"cipherText\n" + cipherText);
//Decipher the cipherText and display the
// result. Should match the encoded text
// above.
decipheredText = obj.doRSA(cipherText,par.d
,par.n,blockSize);
System.out.println(
"decipheredText\n" + decipheredText);
//Decode back to plain text and display the
// result. Should match the input plainText
// with the possibility that extra characters
// were added at the end.
outputText = obj.decode(decipheredText);
System.out.println(
"outputText\n" + outputText);
}//end main
//-------------------------------------------//
//The purpose of this method is to create the
// encryption and decryption keys, e and d,
// along with the modulus operator, n, and
// some other important parameters.
void getKeys(Params par,int blockSize){
//A frequently used constant
BigInteger bigOne = new BigInteger("1");
//Select two prime numbers, p and q, such
// that n = p*q > max and the number of
// characters in n is <= blockSize, where
// max is the maximum possible data value in
// a data block.
//Use the incoming first guess for p and then
// iterate by increasing the value of p until
// a highly-probable prime number is
// found.
while(!(par.p.isProbablePrime(1000))){
par.p = par.p.add(bigOne);
}//end while loop
//Make the first guess for q one less than p
// and then iterate until a highly-probable
// prime number is found for q that satisfies
// the two conditions given above.
String firstQ =
"" + (par.p.subtract(bigOne));
par.q = new BigInteger(firstQ);
//First, without regard for prime, get a
// value for q for which the number of
// digits in the product p*q doesn't exceed
// the block size. Do this by successively
// halving the value for q until the
// condition is satisfied.
par.n = par.p.multiply(par.q);
while(par.n.toString().length() > blockSize){
par.q = par.q.divide(new BigInteger("2"));
par.n = par.p.multiply(par.q);
}//end while
//Divide q by 2 one more time to allow for
// incrementing later on.
par.q = par.q.divide(new BigInteger("2"));
//The current value of q satisfies one of
// the required conditions, but may not be
// a prime number. Get the next prime number
// smaller than the current value of q.
while(!(par.q.isProbablePrime(1000))){
par.q = par.q.subtract(bigOne);
}//end while loop
//Now we have a prime value for q that
// satisfies one of the two required
// conditions. Compute the current value
// for n and start working to confirm or
// satisfy the other condition.
par.n = par.p.multiply(par.q);
//Confirm that p*q > max. If not, increase
// the value of q until the condition is met.
// This adjustment could violate the first
// condition.
while(par.n.compareTo(par.max) <= 0){
//Get a larger prime value for q
par.q = par.q.add(bigOne);
while(!(par.q.isProbablePrime(1000))){
par.q = par.q.add(bigOne);
}//end while loop
//Compute the new value for n and go back
// to the top and test again.
par.n = par.p.multiply(par.q);
}//end while loop
//Confirm that both conditions are still
// being met. If either condition is not
// being met, terminate the program.
if((par.n.toString().length() > blockSize)
|| (par.n.compareTo(par.max) <= 0)){
System.out.println(
"Required conditions are not met");
System.exit(1);
}//end if
//Compute phi, as (p - 1)*(q - 1).
BigInteger pPrime = par.p.subtract(bigOne);
BigInteger qPrime = par.q.subtract(bigOne);
par.phi = pPrime.multiply(qPrime);
//Compute e. First guess is incoming
// value.
while(!par.e.gcd(par.phi).equals(bigOne)){
par.e = par.e.add(bigOne);
}//end while loop
//Compute the value for d
par.d = par.e.modInverse(par.phi);
if(blockSize > 6)System.exit(0);
}//end getKeys
//-------------------------------------------//
//The purpose of this method is to encode a
// plain text message into numeric format
// where:
// space = 32 - 32 = 0
// A = 65 - 32 = 33
// ...
// Z = 90 - 32 = 58
// ...
// a = 97 - 32 = 65
// ...
// ~ = 126 - 32 = 94
//Note that this encoding method supports all
//of the ASCII characters from space through
// tilde (~) inclusive.
String encode(String plainText){
byte[] textChars = plainText.getBytes();
String temp = "";
String encodedText = "";
//Build the encoded text string two numeric
// characters at a time. Each plainText
// character is converted into two numeric
// characters according to the relationships
// given above.
for(int cnt = 0; cnt < plainText.length();
cnt++){
temp = String.valueOf(
textChars[cnt] - ' ');
//Convert all single-character numeric
// values to two characters with a leading
// zero, as in 09.
if(temp.length() < 2) temp = "0" + temp;
encodedText += temp;
}//end for loop
return encodedText;
}//end encode
//-------------------------------------------//
//The purpose of this method is to reverse the
// encoding process implemented by the encode
// method, converting a string of numeric
// characters back to a text string containing
// the ASCII characters from space through
// tilde.
String decode(String encodedText){
String temp = "";
String decodedText = "";
for(int cnt = 0; cnt < encodedText.length();
cnt += 2){
temp = encodedText.substring(cnt,cnt + 2);
//Convert two numeric text characters to a
// value of type int.
int val = Integer.parseInt(temp) + 32;
//Convert the ASCII character values to
// numeric String values and build the
// output String one character at a time.
decodedText += String.valueOf((char)val);
}//end for loop
return decodedText;
}//end decode
//-------------------------------------------//
//Apply the RSA algorithm to an input string
// using the exponent exp and the modulus
// operator n, which are provided as input
// parameters. This method can be used to
// encrypt or to decipher the input string
// depending on whether the exponent is an
// encryption key or a decryption key. Apply
// the algorithm for the block size given by
// the incoming parameter named blockSize.
String doRSA(String inputString,
BigInteger exp,
BigInteger n,
int blockSize){
BigInteger block;
BigInteger output;
String temp = "";
String outputString = "";
//Iterate and process one block at a time.
for(int cnt = 0; cnt < inputString.length();
cnt += blockSize){
//Get the next block of characters
// and encapsulate them in a BigInteger
// object.
temp = inputString.substring(
cnt,cnt + blockSize);
block = new BigInteger(temp);
//Raise the block to the power exp, apply
// the modulus operand n, and save the
// remainder. This is the essence of the
// RSA algorithm.
output = block.modPow(exp,n);
//Convert the numeric result to a
// four-character string, appending leading
// zeros as necessary.
temp = output.toString();
while(temp.length() < blockSize){
temp = "0" + temp;
}//end while
//Build the outputString blockSize
// characters at a time. Each character
// in the inputString results in one
// character in the outputString.
outputString += temp;
}//end for loop
return outputString;
}//end doRSA
//-------------------------------------------//
}//end class Rsa03
Listing 48
|
Copyright 2004, Richard G. Baldwin. Reproduction in whole or in part in any form or medium without express written permission from Richard Baldwin is prohibited.
Richard has participated in numerous consulting projects, and he frequently provides onsite training at the high-tech companies located in and around Austin, Texas. He is the author of Baldwin's Programming Tutorials, which has gained a worldwide following among experienced and aspiring programmers. He has also published articles in JavaPro magazine.
In addition to his programming expertise, Richard has many years of practical experience in Digital Signal Processing (DSP). His first job after he earned his Bachelor's degree was doing DSP in the Seismic Research Department of Texas Instruments. (TI is still a world leader in DSP.) In the following years, he applied his programming and DSP expertise to other interesting areas including sonar and underwater acoustics.
Richard holds an MSEE degree from Southern Methodist University and has many years of experience in the application of computer technology to real-world problems.
-end-