Java Programming, Notes # 727
- Preface
- Background Information
- Preview
- Discussion and Sample Code
- Run the Programs
- Summary
- What’s Next
- Complete Program Listings
Preface
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.
Background Information
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:
- Public (asymmetric) key cryptography
- Symmetric key cryptography
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.)
Preview
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.
Discussion and Sample
Code
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 3×3 matrix required
to solve the small problem is much different from inverting the 50×50 matrix
required to solve the larger problem. The 3×3 matrix can be inverted using
pencil, paper, and a procedure that most of us learned in high school.
Inverting the 50×50 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(
"plainTextn" + 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(
"encodedTextn" + 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:
- space = 00
- A = 01
- B = 02
- C = 03
- …
- Z = 26
(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(
"cipherTextn" + 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:
- Raise the value encapsulated in the object
referred to by block to the power exp and to - Compute the modulus
using the divisor n, saving the remainder in the BigInteger object
referred to by output
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(
"decipheredTextn" + 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(
"outputTextn" + 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:
- Instantiates an object of the class Params in which to store the
parameters. - Creates a test message string containing characters from the full range
of the 95 characters supported by the encoding method. - Declares some variables to be populated later by the program.
- Sets the block size and makes certain that it is divisible by 2.
- Gets and saves the maximum value of an encoded string for the specified block size and the encoding format used.
For example, for a block size of 4, the maximum value would be 9494.
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:
- n = p*q > max
- The number of characters in n is <= blockSize
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(
"plainTextn" + 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(
"encodedTextn" + 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:
- space = 00
- A = 33
- …
- Z = 58
- …
- a = 65
- …
- ~ = 94
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(
"cipherTextn" + 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(
"decipheredTextn" + 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(
"outputTextn" + 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.
Run the Programs
I encourage you to copy, compile and run the following programs that are
provided in this lesson:
- Rsa07
- Rsa08
- Rsa01
- Rsa03
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.
Summary
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.
What’s Next?
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 Program Listings
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(
"plainTextn" + plainText);
//Encode the plain text into numeric format
// and display the result.
encodedText = obj.encode(plainText);
System.out.println(
"encodedTextn" + encodedText);
//Encrypt the encoded text and display the
// result.
cipherText = obj.doRSA(encodedText,e,n);
System.out.println(
"cipherTextn" + 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(
"decipheredTextn" + 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(
"outputTextn" + 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(
"plainTextn" + 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(
"encodedTextn" + encodedText);
//Encrypt the encoded text and display the
// result.
cipherText = obj.doRSA(encodedText,par.e,
par.n,blockSize);
System.out.println(
"cipherTextn" + 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(
"decipheredTextn" + 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(
"outputTextn" + 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.
About the author
Richard Baldwin
is a college professor (at Austin Community College in Austin, TX) and
private consultant whose primary focus is a combination of Java, C#, and
XML. In addition to the many platform and/or language independent benefits
of Java and C# applications, he believes that a combination of Java, C#,
and XML will become the primary driving force in the delivery of structured
information on the Web.
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-
