Developer.com content and product recommendations are editorially independent. We may make money when you click on links to our partners. Learn More.
Java Programming, Notes # 728
- Preface
- Background Information
- Preview
- Discussion and Sample Code
- Run the Programs
- Summary
- What’s Next
- Complete Program Listings
Preface
A simple protocol
A variety of protocols are available for the use of public-key cryptography
and digital signatures to protect the authenticity, integrity, and
confidentiality of a message. This lesson explains a simple and easily
understood protocol. Future lessons will explain more sophisticated
protocols.
Second in a series
This is the second lesson in a series designed to teach you
something about the inner workings of cryptography using Java.
The previous lesson was entitled
Public Key
Cryptography 101 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
without the use of a cryptography API.
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 production 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
and secure hash algorithms and to gain a better understanding of how they work, and why
they do what they do. In addition, the lessons in this series are intended
to help you understand some of the common uses of cryptography such as the use
of digital signatures.
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
and secure hash algorithms in Java.
I will also discuss and illustrate some of the modern uses of
cryptography, such as the use of digital signatures, which is the
primary topic of this and the next several lessons.
Supplementary material
I recommend that you also study the other lessons in my extensive collection
of online Java tutorials. You will find those lessons published at
Gamelan.com. However, as of
the date of this writing, Gamelan doesn’t maintain a consolidated index of my
Java tutorial lessons, and sometimes they are difficult to locate there. You
will find a consolidated index at
www.DickBaldwin.com.
Background
Information
Cryptography in one form or another has been around throughout
history. Please see the previous lesson entitled
Public Key
Cryptography 101 Using Java for some
background information on cryptography.
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.”
Secure communications
The lessons in this series will present and explain programs that
implement cryptographic and secure hash 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.
Please see the previous lesson entitled
Public Key
Cryptography 101 Using Java for a discussion of
the difference between the two.
Asymmetric or public key cryptography
This lesson deals with asymmetric or public key cryptography.
With asymmetric key cryptography, there are two keys. One key 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 disclosed 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.
Sometimes the roles are switched
Actually the concept that the encryption key is public and the
decryption key is secret isn’t always correct. As you will
see in this lesson, either key can be used to encrypt the data provided
that the other key is used to decrypt the data. It is very important,
however, that one of the keys be kept secret. For purposes of digital
signing of messages, the secret key is used to encrypt the message
or a portion thereof and the public key is used to decrypt it.
The RSA algorithm
This lesson deals 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. Please see the
previous lesson entitled
Public Key
Cryptography 101 Using Java to gain a basic understanding of the RSA
algorithm.
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 encrypt the message using the intended
recipient’s public encryption key. However, only the intended
recipient can decrypt the message using her 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.
In other words, a message that is encrypted using the sender’s secret key can
be decrypted by anyone having access to the sender’s public key. The
significance of such an operation is that only the holder of the secret key
could have encrypted the message. While the contents of the message are
not held secret in this case, the identity of the sender is clearly established
as someone having access to the secret key.
The primary topic of this lesson is the digital signing of
both plain text and encrypted messages.
Preview
Two different programs
I will present and discuss two different programs in this
lesson. The first program named Rsa04 will illustrate the
digital signing of an unencrypted message using an encrypted digital
signature.
The second program named Rsa05 will illustrate the digital
signing of an encrypted message.
Three important aspects
There are at least three important aspects of electronic
communication:
- Authentication: Confirming the identities of the parties involved.
- Confidentiality: Making certain that only authorized
parties can understand the message, even if it is intercepted by
unauthorized persons. - Integrity: Confirming that the content of the message wasn’t
modified during transmission.
The first program named Rsa04 will illustrate a scenario
where only
authentication and integrity are of concern. In this
scenario, there is no need to be concerned about the public disclosure
of the content of a message.
The second program named Rsa05 involves a scenario where all
three aspects are important. In this case, it is also necessary
to keep the content of each message confidential.
Discussion and
Sample Code
The program named Rsa04
IMPORTANT: THIS PROGRAM USES PREDETERMINED KEYS THAT WERE
DESIGNED FOR A BLOCK SIZE OF 4. THEREFORE, IT WILL WORK CORRECTLY
ONLY FOR A BLOCK SIZE OF 4.
The purpose of this program is to illustrate the digital signing
of an unencrypted message along with the later verification of the
signature and the validation of the message by the recipient of the message.
This program illustrates how to validate (or fail to validate) both the
authenticity and the integrity of the message.
Alice and Bob
The comments in this program reflect a scenario based on two
fictitious people named Alice and Bob. This scenario is commonly
used in discussions of digital signatures.
The scenario
Alice needs to send a digitally signed unencrypted message
to Bob. The message needs to be digitally signed so that Bob can be
confident that the message that he received was sent by Alice and was
not sent by someone pretending to be Alice. In other words, Bob
needs to be able to authenticate the message. In addition, Bob
needs to be able to confirm the integrity of the message.
(For example, the message could be an order from Alice to Bob
for the purchase of ten file cabinets. Bob needs to be certain
that Alice really did sign and send the purchase order before he ships
the file cabinets. Otherwise, the order may have been sent by
someone pretending to be Alice, in which case, Bob probably won’t get
paid for the shipment. Bob also needs to confirm that Alice
really did order ten file cabinets and that the quantity in her
purchase order was not modified during transit. Otherwise, he may ship
more or fewer than she wants.)
Key management
In order to accomplish the desired result, Alice needs to create a
pair of asymmetric keys. She will hold one of the keys secret and
will provide the other key to Bob. We will refer to the secret
key as Alice’s private key, and will refer to the key that she gives to
Bob as her public key.
(Alice needs to provide the public key to Bob in a way that
causes him to be confident that the public key was actually provided by
Alice and was not provided by someone pretending to be Alice.
Otherwise, his later use of the public key to decrypt the digital
signature won’t authenticate that the message was actually sent by
Alice.)
Block size, encoding, and decoding
In addition, for this simple implementation, Alice needs to notify Bob as to the block size for
which the keys were designed. The two of them need to agree on an
encoding/decoding methodology for transforming messages back and forth
between a text format and a numeric format.
(Recall that the RSA algorithm can only be used with messages
expressed in a numeric format.)
You can read about most of these topics in the previous lesson
entitled
Public Key
Cryptography 101 Using Java.
Create a digital signature
Alice begins by creating a digital signature. The digital
signature is created by encoding and encrypting the entire text message
using Alice’s private key and the RSA algorithm.
(Bob can later decrypt the digital signature using Alice’s
public key.)
Message digests as an alternative
As described above, the approach used by this program is to create a
digital signature that is an encrypted version of the entire text
message. This can be wasteful of communication resources, particularly for long
messages. In this implementation, the length of the digital signature is twice the
length of the text version of the message. A more efficient
approach for long messages would be to apply another mathematical algorithm to the message,
which will produce something called a message digest.
A fingerprint
The message-digest algorithm takes an arbitrary amount of input message data
and produces a fixed-length output that represents the message data.
The fixed-length version is commonly referred to as a digest or
a
fingerprint. While it is not guaranteed that digests for two
different messages will be different, the probability that two
different messages will produce the same digest is extremely small.
Using this approach, Alice would encode and encrypt the digest and use the
resulting string of numeric characters as the digital signature instead of
encrypting the entire message for use as a digital signature. If her
message is a long message, this will save communications resources (but will also require an extra computational step at
each end of the communication between Alice and Bob).
This lesson won’t deal with message digests. That is a topic
for a future lesson.
Sign and send the message
Now let’s return to the original scenario were Alice creates the digital
signature by encrypting the entire message using her private key. Alice signs the message by appending the digital signature
onto the end of the unencrypted message. According to a previous agreement
between Alice and Bob, she uses an underscore
character as the delimiter to separate the text portion of the message from the digital signature.
(Bob will use the delimiter later to separate the text portion
of the message from the digital signature. There is nothing magic
about an underscore character. Any mutually agreed upon character
could be used as a delimiter provided that it is a character that won’t
appear elsewhere in the message.)
Then Alice sends the signed message to Bob.
(Note that there are ways to avoid having to use a delimiter that
involve encoding the length of the original message in the overall message.)
Separate and decrypt the digital signature
When Bob receives the signed message, he separates the encrypted digital signature from the text portion
of the message using the underscore character as the delimiter between
the two. Then he decrypts the digital signature using Alice’s
public key and decodes the result. This should produce a plain text
version of the digital signature.
Test the signature for validity
According to a previous agreement between Alice and Bob, the plain text
version of the digital signature should exactly match the text portion
of the message. Bob compares the text version of the digital
signature with the text portion of the message. If they match exactly,
he concludes that the message was actually sent by Alice, (or by
someone having access to her private key). Also because they
match, he concludes that the message was not modified in transit.
If they fail to match, the actual source or the content of the
message is questionable.
Message digests
In the event that Alice and Bob had agreed to authenticate and
confirm the integrity of the message based on the use of an encrypted
message digest as the digital signature, Bob’s validation procedure
would be a little more complicated.
Bob would extract, decrypt and decode the digital signature as
before. He would also need to use the same algorithm used by
Alice and create a digest of the text portion of the message. He
would then compare his version of the digest with the decrypted and
decoded version of the digital signature. If they matched
exactly, he would conclude with a high degree of confidence that the
message was sent by Alice and that it had not been modified in
transit.
Key reversal
Note that you can reverse the values of the two keys and get the
same results. In other words, it doesn’t matter which key you use to
sign the message as long as you use the other key to decrypt the
digital signature. However, for the protocol to achieve the desired
result, it is imperative that Alice maintain the secrecy of the key that she
uses to encrypt the digital signature.
Support for 95 text characters
This program supports the ninety-five ASCII characters from space
(32) through ~ (126) inclusive for use in the message. (However,
because the underscore character is used as a delimiter, it is not available for
use elsewhere in the message.)
Predetermined keys
The program uses predetermined values shown in Figure 1 for the
following:
- Alice’s public key, e
- Alice’s private key, d
- Alice’s common divisor, n
A disclaimer
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
Java Cryptography Extension (JCE) .
Theoretical background
See the theoretical basis for the RSA algorithm 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
The program output
The program was tested using SDK 1.5 and WinXP, producing the
output shown in Figure 1.
Alice's keys: Figure 1 |
Note that line breaks were manually entered into the above text to
force it fit into this narrow publication format.
I will refer back to Figure 1 frequently during the discussion of
this program.
The class named Rsa04
The beginning of the class and the beginning of the main method is
shown in Listing 1.
class Rsa04{
|
The definition of the class named Rsa04 begins with the
definition of a static internal class named Keys. The
sole purpose of the Keys class is to create an object that
serves as a container for the keys. The class was made static so
that it can be instantiated from within main. The Keys
class contains predetermined values for the two keys, e and d, and the
common divisor n used by the RSA algorithm.
The key named e will be used as a public key and the key named d
will be used as a private key
The main method begins by instantiating an object of the Keys
class containing the predetermined keys as shown in Listing 1.
The test message
Listing 2 instantiates a String object that will be signed
and sent by Alice to Bob.
String message = "Hello Bob, how are you?"; |
Set the block size
Listing 3 sets the blockSize to 4. As mentioned
earlier, because this program uses predetermined keys that were
designed for a block size of 4, changing blockSize to any other
value will cause this program to fail.
int blockSize = 4; |
Listing 3 also instantiates an object of the controlling class and
displays the contents of the Keys object. This produces
the first four lines of output in Figure 1.
Extend text message if necessary
As you learned in the previous lesson entitled
Public Key
Cryptography 101 Using Java, the length of
the encoded text must be evenly divisible by blockSize.
while(message.length()%(blockSize/2) != 0){
|
Listing 4 forces the message length to be a multiple of half the
block size to avoid end-effect problems later. (The encoding process
used later produces two encoded numeric characters for each character in the
original message.) The text message
is extended by appending dash characters if it is necessary to extend
the message.
(Note that a more sophisticated approach to extending the message is
often used wherein the values of the characters used to extend the message
indicate the number of required extension characters. This makes it
possible to remove the extension later in an unambiguous manner. I
extended the message using dash characters for simplicity.)
Listing 4 also displays the extended message producing the fifth and sixth
lines of output in Figure 1.
Encode the message
The first part of the program is presented from Alice’s
viewpoint. She begins by invoking the encode method in
Listing 5 to encode the text message into numeric format in order to
get it ready for RSA encryption.
String encodedMsg = obj.encode(message); |
The encode method
The encode method used by this program is essentially the
same as the method having the same name in one of the programs that I
explained in the previous lesson entitled
Public Key
Cryptography 101 Using Java.
As mentioned earlier, this method supports the encoding of the
ninety-five ASCII characters extending from the space character to the
tilde (~) character inclusive.
Because I explained this method in the previous lesson, I won’t
discuss it further here. You can view the encode method along with
all of the other methods in this program in Listing 27 near the end of this
lesson.
Create the digital signature
Alice invokes the doRSA method in Listing 6 to create a
digital signature by encrypting the encoded message using her private
key.
String signature = obj.doRSA( |
Listing 6 also displays the digital signature as the seventh and eighth lines in
Figure 1.
(As you can see, the length of the digital signature is twice
the length of the text version of the message. This illustrates
that for long messages there may be bandwidth benefits in encrypting a
shorter digest of the message for use as the digital signature instead
of encrypting the entire message.)
The doRSA method
The doRSA method used in this program is essentially the same as the
method having the same name that I explained in the previous lesson entitled
Public Key
Cryptography 101 Using Java. Therefore, I won’t discuss it further here.
Sign the message
Alice signs the message in Listing 7 by appending the digital
signature onto the message. She identifies the beginning of the
digital signature by the presence of an underscore character.
(The underscore character is used to separate the message from the
digital signature.)
String signedMsg = message + "_" + signature; |
Listing 7 also displays the digitally signed message producing the
output shown in lines 9, 10, and 11 in Figure 1.
(Note that a line break was manually inserted into line 10 in
Figure 1 to force the material to fit in this narrow publication
format.)
Send the message to Bob
At this point, the digitally signed message is ready for Alice to
send to Bob, which she does. From this point forward, the program
viewpoint switches from Alice’s viewpoint to Bob’s viewpoint.
Extract the message text from the signed
message
In Listing 8, Bob extracts the message text from the signed message
based on the location of the underscore character.
String extractedMsgText = |
Listing 8 also displays the message text as lines 12 and 13 in Figure
1. As you would expect, it matches the beginning of Alice’s
signed message shown in line 10 of Figure 1.
Extract the digital signature from the
signed message
Bob uses the location of the underscore character to extract and
display the encrypted digital signature in Listing 9. This produces the
output shown in lines 14 and 15 in Figure 1.
String extractedSignature = |
Decrypt, decode, and display the digital signature
In Listing 10, Bob uses Alice’s public key and the doRSA method to
decrypt the encrypted digital signature. Then he decodes the decrypted
signature by
invoking the decode method. Finally, he displays the result, producing the output
shown in lines 16 and 17 in Figure 1.
String decipheredSignature = |
As you can see from a visual comparison, the result matches the original
extended message shown in line 6 in Figure 1. It also matches the plain
text portion of the message shown in line 10 of Figure 1.
The decode method
The decode method used here is essentially the same as the method having the
same name that I explained in the previous lesson entitled
Public Key
Cryptography 101 Using Java.
Therefore, I won’t discuss that method further her.
Make an automated comparison
A visual comparison is OK for a short message such as this one.
However, if the message were longer, Bob would need a better way to make the
comparison in order to confirm that the decoded digital signature matches the
plain text portion of the message. He accomplishes this using the
equals method of the String class in Listing 11.
if(extractedMsgText.equals(decodedSignature)) |
A validation message
After making the comparison, the code in Listing 11 displays a message
indicating whether or not the digital signature is valid. If the decoded
digital signature exactly matches the plain text portion of the message, the
signature is valid. Otherwise, it is invalid. The result is shown in
the last line in Figure 1.
Conclusions regarding the program named Rsa04
If the digital signature is valid, Bob can conclude that the message was sent
by Alice (or someone having access to her private key). Thus, the
message has been authenticated, confirming the identities of the parties
involved.
Bob can also conclude that the message was not modified by someone else
during transmission (unless that person had access to Alice’s private key),
thus validating the integrity of the message.
On the other hand, if the digital signature is deemed to be invalid, Bob must
conclude that either the authenticity or the integrity of the
message is questionable.
The program named Rsa05
The program named Rsa05 is somewhat more complicated than the previous
program named Rsa04.
The program output
Before getting into the program details, let’s take a look at the program
output, as shown in Figure 2.
Alice's key values: e: 17 d: 3869 n: 9617 Bob's key values: e: 17 d: 7973 n: 9557 Extended message: Hello Bob, how are you?- Alice's digital signature 645654360346008475874713831303624383162618484532 Extended signed message: Hello Bob, how are you?-_645654360346008475874713 831303624383162618484532- Alice's encrypted signed message 3775134981462442655548020315575049268515315878533 1311740103502891756418117565793881488682309495851 7257280481681561515172572873118819371637165132096 2 Bob's deciphered and decoded message: Hello Bob, how are you?-_645654360346008475874713 831303624383162618484532- Extracted message text: Hello Bob, how are you?- Extracted digital signature: 645654360346008475874713831303624383162618484532 Deciphered and decoded digital signature: Hello Bob, how are you?- Valid signature Figure 2 |
Note that line breaks were manually entered into the above text to force it
to fit into this narrow publication format.
I will refer back to Figure 2 frequently during the discussion of this
program.
IMPORTANT: BECAUSE THIS PROGRAM USES PREDETERMINED KEYS THAT WERE DESIGNED
FOR A BLOCK SIZE OF 4, IT WILL WORK CORRECTLY ONLY FOR A BLOCK SIZE OF 4.
A different scenario
The program named Rsa05 simulates a somewhat different scenario from
the scenario simulated by Rsa04.
The purpose of this program is to illustrate the signing of an encrypted
message along with the later decrypting of the message and the verification of
the signature by the recipient.
The comments in this program make use of the scenario of Alice and Bob, which
is common in discussions of the RSA encryption algorithm.
The supported character set
This program supports all of the ASCII characters from space (32) through ~
(126) inclusive. Thus, all of these characters may be used in the message.
(Once again, however, the underscore character is used as a delimiter, so it
cannot be used elsewhere in the message.)
Precomputed keys
This program uses two sets of precomputed key values for:
- The public key e.
- The private key d.
- The modulus operand n.
One set of keys belongs to Alice. The other set belongs to Bob.
Note that you can reverse the values of the public and private keys and the
result will be the same so long as the keys are properly managed. You can
encrypt with either key value so long as you decrypt using the other key value.
Finally, the scenario
Alice needs to send a signed encrypted message to Bob.
(Maybe Alice and Bob have a romantic interest in one another and she doesn’t want Bob’s wife
to be able to read her message.)
A digital signature
Alice uses the RSA algorithm to create a digital signature for an unencrypted
message. The digital signature is an encrypted version of the original
message. She uses her private key to encrypt the original message in order
to create the digital signature. Bob can later decrypt the digital
signature using her public key.
Alice signs the message by appending the digital signature onto the end of
the unencrypted message, with the signature being delimited from the unencrypted
message by an underscore character.
(Bob will use the underscore character later to separate the message
from the digital signature.)
Encrypting the signed message
Then Alice uses Bob’s public key to encrypt the entire signed message
including the digital signature.
(The digital signature has now been encrypted twice, once using
Alice’s private key and once again using Bob’s public key.)
Bob’s wife cannot read the message in this condition (unless she has
access to his private key). However,
encryption using Bob’s public key by Alice makes it possible for Bob to decrypt the
signed encrypted message using his private key.
Bob reads the message
Bob receives the encrypted message and decrypts (and decodes) it using his private key. At
this point, he can view the unencrypted version of the message text along with
the still encrypted digital signature.
(The digital signature has been encrypted twice, once using Alice’s
private key and once using Bob’s public key. However at this point,
the digital signature has been decrypted only once using Bob’s private key,
so it is still not readable.)
Decrypt the digital signature
Bob uses the position of the underscore character to separate the message
text from the still encrypted digital signature. Then he uses Alice’s
public key to decrypt (and decode) the digital signature. He compares the result with
the unencrypted message text. If they match, this verifies that the
message was actually sent by Alice (or someone who had access to Alice’s
private key).
Objectives achieved
Thus Alice was able to send a confidential message to Bob, which could be read
only by Bob (or by someone having access to Bob’s private key).
Further, bob was able to confirm that the message was actually sent by Alice
(or someone having access to Alice’s private key) and that the message was
not modified in transient. Therefore, all three of the following
objectives were met:
- Authentication: Confirming the identities of the parties
involved. - Confidentiality: Making certain that only authorized parties can
understand the message, even if it is intercepted by unauthorized persons. - Integrity: Confirming that the content of the message wasn’t
modified during transmission.
If the unencrypted digital signature doesn’t match the text of the message,
the source or the integrity of the message is in question.
A disclaimer
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
Java Cryptography Extension (JCE).
Theoretical background
See the theoretical basis for the RSA algorithm 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
This program was tested using SDK 1.5 and WinXP.
The class named Rsa05
Listing 12 shows the beginning of the class named Rsa05.
class Rsa05{
static class Keys{
BigInteger n;
BigInteger d;
BigInteger e;
}//end inner class Keys
|
Listing 12 also defines a static inner class named Keys, whose sole purpose is to create an object that serves as a container for
the keys.
The class was made static so that it could be instantiated from within main.
The main method
The beginning of the main method is shown in Listing 13.
public static void main(String[] args){
//Instantiate and populate an object
// containing precomputed keys for Alice.
Keys aliceKeys = new Keys();
aliceKeys.n = new BigInteger("9617");
aliceKeys.d = new BigInteger("3869");
aliceKeys.e = new BigInteger("17");
//Instantiate and populate an object
// containing precomputed keys for Bob.
Keys bobPar = new Keys();
bobPar.n = new BigInteger("9557");
bobPar.d = new BigInteger("7973");
bobPar.e = new BigInteger("17");
|
The code in Listing 13 instantiates and populates two objects of the Keys
class to contain the precomputed keys for Alice and Bob. The precomputed
keys for Alice are stored in the object referred to by aliceKeys.
Similarly, the precomputed keys for Bob are stored in the object referred to by
bobPar.
Create test message, set block size, etc.
The code in Listing 14 creates the test message that Alice will sign,
encrypt, and send to Bob.
//Original test message.
String message = "Hello Bob, how are you?";
//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
//Instantiate an object of this class.
Rsa05 obj = new Rsa05();
|
Listing 14 also sets the block size to 4 and instantiates an object of the
Rsa05 class.
Display the precomputed key values
Listing 15 displays the precomputed key values for Alice and Bob.
//Display Alice's keys.
System.out.println("Alice's key values:");
System.out.println("e: " + aliceKeys.e);
System.out.println("d: " + aliceKeys.d);
System.out.println("n: " + aliceKeys.n);
//Display Bob's keys.
System.out.println("Bob's key values:");
System.out.println("e: " + bobPar.e);
System.out.println("d: " + bobPar.d);
System.out.println("n: " + bobPar.n);
|
The code in Listing 15 produces the first eight lines of output text in
Figure 2.
Adjust the message length
The code in Listing 16 forces the message length to be a multiple of half the
block length. Because the encoding technique, which converts the message
to numeric form, creates two encoded characters for every character in the
message, this forces the length of the encoded message to be a multiple of the
block length.
while(message.length()%(blockSize/2) != 0){
//Append a visible character on the end.
message += "-";
}//end while
System.out.println(
"Extended message:n" + message);
|
If the length of the original message is not a multiple of half the block
length, the code in Listing 16 appends visible dash (-) characters to the end of
the message to achieve the required length.
The code in Listing 16 also displays the extended message, producing the text
shown in lines 9 and 10 in Figure 1. So far, this program is tracking
right along with the previously-discussed program named Rsa04.
Create and display the digital signature
Following this, Alice creates the digital signature
by:
- Encoding the extended message into numeric format by invoking the
encode method. (This is the same encode method discussed
earlier. You can view the method in Listing 28 near the end of the
lesson.) - Encrypting the encoded extended message by invoking the doRSA
method and passing her private key as one of the parameters to the method.
(Once again, this the same doRSA method discussed earlier.
You can also view this method in Listing 28 near the end of the lesson.)
String aliceEncodedText =
obj.encode(message);
String aliceDigitalSignature =
obj.doRSA(aliceEncodedText,aliceKeys.d,
aliceKeys.n,blockSize);
System.out.println(
"Alice's digital signaturen"
+ aliceDigitalSignature);
|
The above operations are shown in Listing 17.
Finally, the code in Listing 17 displays Alice’s digital signature, producing
lines 11 and 12 in Figure 2.
Sign the message
In Listing 18, Alice signs the message by appending the digital signature
onto the end of the message.
String aliceSignedMsg =
message + "_" + aliceDigitalSignature;
|
Alice uses an underscore character to physically separate the digital
signature from the message. Bob will use this underscore character later
to identify the end of the message and the beginning of the digital signature.
Prepare for encryption
Up to this point, this program has been very similar to the previous program
named Rsa04. However, the two programs diverge significantly at
this point. Recall that Alice needs to send the message to Bob in such a
way that it can only be read by Bob, or by someone having access to Bob’s
private key. To accomplish this, Alice will encrypt the signed message
using Bob’s public key.
In preparation for encrypting the signed message, Alice forces the length of
the signed message to be a multiple of one-half the block length in Listing 19.
Once again, Listing 19 appends visible dash (-) characters onto the end of the
signed message, if necessary, to achieve the required length.
while(aliceSignedMsg.length()%(blockSize/2)
!= 0){
//Append a visible character on the end.
aliceSignedMsg += "-";
}//end while
System.out.println(
"Extended signed message:n"
+ aliceSignedMsg);
|
Listing 19 also displays the extended signed message, producing lines 13, 14,
and 15 in Figure 2.
(Note that a line break was manually inserted into line 14 in Figure 2
to force the material to fit in this narrow publication format. In
addition, line breaks were manually inserted into several subsequent lines
in Figure 2 for the same purpose.)
Encode the signed message
Following this, Alice invokes the encode method to encode the signed
message into numeric format in preparation for encryption. This is shown
in Listing 20.
String aliceEncodedMsg = obj.encode(
aliceSignedMsg);
|
Encrypt the signed encoded message
Then Alice invokes the doRSA method to encrypt the signed encoded
message using Bob’s public key, as shown in Listing 21.
String aliceCipherText = obj.doRSA(
aliceEncodedMsg,bobPar.e,
bobPar.n,blockSize);
System.out.println(
"Alice's encrypted signed messagen"
+ aliceCipherText);
|
Only Bob or someone having access to Bob’s secret key will be able to
decrypt and read the signed message.
Listing 21 also displays the encrypted signed message, producing lines 16
through 20 in Figure 2.
(Once again, line breaks were manually inserted in the encrypted
version to force it to fit in this narrow publication format.)
Increased bandwidth required
It might be worth noting that the extending, signing, encoding, and
encryption of the original message containing 23 characters resulted in an
encrypted signed message containing 147 characters. Thus in this case, the
length of the message that was transmitted was approximately six times the
length of the original message.
A factor of three increase in length
The signing of the message extended its length by almost a factor of 3.
For very long messages, the use of a message digest for the creation of the digital
signature could reduce this factor significantly. However, for short
messages such as this one, the use a message digest would provide very little
improvement in the extension factor.
An additional factor of two increase in length
The encryption of the signed message increased the length again by
approximately a factor of 2, resulting in an overall increase in the length by
approximately a factor of 6.
Thus, there is a price to pay in terms of required transmission bandwidth for
signing and encrypting a message.
Send the message
Up to this point, the program has been written from Alice’s viewpoint.
At this point, Alice sends the signed encrypted message to Bob, and the program
viewpoint switches to Bob’s viewpoint.
Decrypt and decode the signed encrypted message
Bob begins by invoking the doRSA method, using his private key to
decrypt the signed encrypted message, as shown in Listing 22. Then he
invokes the decode method to decode the message from numeric format back
into text format. This is also shown in Listing 22.
String bobDecipheredMsg = obj.doRSA(
aliceCipherText,bobPar.d,
bobPar.n,blockSize);
String bobDecodedMsg = obj.decode(
bobDecipheredMsg);
System.out.println(
"Bob's deciphered and decoded message:n"
+ bobDecodedMsg);
|
Listing 22 also displays the decoded signed message producing the output text
shown in lines 21 through 23 in Figure 2. As you might expect, the result
is identical to Alice’s extended signed message shown earlier in lines 13, 14,
and 15 of Figure 2.
Separate the message from the digital signature
In Listing 23, Bob uses the position of the underscore character to extract
the message text from the signed message. This produces the output shown
in lines 24 and 25 in Figure 2. As might be expected, this matches Alice’s
extended message text shown in line 10 in Figure 2.
String bobMsgText = bobDecodedMsg.substring(
0,bobDecodedMsg.indexOf('_'));
System.out.println(
"Extracted message text:n"
+ bobMsgText);
|
At this point, however, Bob can’t be certain that the message was actually
sent by Alice, or if it was sent by Alice, that it wasn’t modified somewhere
along the way. In order to confirm the authenticity and integrity of the
message, he needs to decrypt the digital signature and compare the result with
the message produced by Listing 23.
Extract and display the digital signature
In Listing 24, Bob uses the position of the underscore character to extract
the digital signature from the signed message. He knows that because of
the use of the RSA algorithm to produce the digital signature, it can
consist only of the numeric characters from 0 through 9. He removes any
dash (-) characters at the end that were placed there by Alice to cause the signed
message length to be a multiple of half the block length before she encrypted
the message using Bob’s public key.
String receivedSignature =
bobDecodedMsg.substring(
bobDecodedMsg.indexOf('_') + 1);
while(receivedSignature.endsWith("-")){
receivedSignature =
receivedSignature.substring(
0,receivedSignature.length()-1);
}//end while
System.out.println(
"Extracted digital signature:n"
+ receivedSignature);
|
Then Listing 24 displays the extracted digital signature, producing the
output shown in lines 26 and 27 in Figure 2. As might be expected, the
digital signature received by Bob matches the digital signature created by Alice
and displayed earlier in lines 11 and 12 of Figure 2.
Decrypt and decode the digital signature
Finally, Bob decrypts the digital signature using Alice’s public key.
He decodes and displays the result producing the output shown in lines 28 and 29
of Figure 2.
String decipheredSignature =
obj.doRSA(receivedSignature,aliceKeys.e
,aliceKeys.n,blockSize);
String decodedSignature = obj.decode(
decipheredSignature);
System.out.println(
"Deciphered and decoded digital signature:n"
+ decodedSignature);
|
Make a visual comparison
For this short message, Bob can visually compare the result with the
extracted message text shown earlier in line 25 of Figure 2. Since the two
are exactly the same, Bob can conclude not only that the encrypted signed
message was sent by Alice (or someone having access to her private key)
but also that the message was not modified in transit. However, had the
two failed to compare favorably, either the authenticity or the integrity
of the message would have been in question.
Make an automated comparison
For a long message, Bob might need some help in making the comparison.
Listing 26 uses the equals method of the String class to
automatically compare the extracted message text (line 25 in Figure 2)
with the decoded signature (line 29 in Figure 2).
if(bobMsgText.equals(decodedSignature)){
System.out.println("Valid signature");
}else{
System.out.println("Invalid signature");
}//end else
}//end main
|
Depending on the result of the comparison, the code in Listing 26 either
validates or refuses to validate the authenticity and integrity of the message,
producing the output shown in the last line in Figure 2.
End of program discussion
Listing 26 also signals the end of the main method and the end of the
discussion of the program named Rsa05. All of the methods referred
to but not discussed in detail above were previously discussed in the lesson entitled
Public Key
Cryptography 101 Using Java. These methods can be viewed in Listing 27
and Listing 28 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:
- Rsa04
- Rsa05
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 digital signatures
using public key cryptography as implemented using Java.
Summary
There are numerous protocols that can be used along with public key
cryptography and digital signatures to validate the authenticity and integrity
of a message.
In this lesson, I explained one of those protocols for the use of digital
signatures. Two scenarios were explained. In the first scenario, it
was necessary to validate the authenticity and integrity of a message, but there
was no requirement to keep the contents of the message secret. In the
second scenario, it was necessary to keep the contents of the message secret in
addition to validating the authenticity and integrity of the message.
What’s Next?
The next lesson in this series will teach you how to create message digests
using the secure hash algorithm known as SHA-1. A subsequent lesson will
show how to use a message digest for the creation of a digital signature.
Complete Program
Listings
Complete listings of the programs discussed in this lesson are
provided in Listing 27 and Listing 28 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 production 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 cryptosystems and
to gain a better understanding of how they work, and why they do what
they do.
/*File Rsa04.java |
/*File Rsa05.java
Copyright 2004, R.G.Baldwin
IMPORTANT: BECAUSE THIS PROGRAM USES
PREDETERMINED KEYS THAT WERE DESIGNED FOR A BLOCK
SIZE OF 4, IT WILL WORK CORRECTLY ONLY FOR A
BLOCK SIZE OF 4.
The purpose of this program is to illustrate the
signing of an encrypted message along with the
later deciphering of the message and the
verification of the signature by the recipient.
The comments in this program make use of the
scenario of Alice and Bob, which is common in
discussions of the RSA encryption algorithm.
This program supports all of the ASCII characters
from space (32) through ~ (126) inclusive to be
used in the message.
This program uses two sets of precomputed key
values for:
The public key e.
The private key d.
The modulus operand n.
One set of keys belongs to Alice. The other set
belongs to Bob.
Note that you can reverse the values of the
public and private keys and the result will be
the same so long as the keys are properly
managed. You can encrypt with either key value
so long as you decrypt using the other key
value.
Here is the scenario illustrated by this program:
Alice needs to send a signed encrypted message to
Bob. She uses the RSA algorithm to create a
digital signature for an unencrypted message.
The digital signature is an encrypted version of
the same message that she encrypts using her
private key. Bob can later decipher the
digital signature using her public key.
Alice signs the message by appending the digital
signature onto the end of the unencrypted
message, with the signature being delimited from
the message by an underscore character. Bob
needs to know how the two are delimited so that
he can extract the digital signature from the
deciphered signed message later.
Then Alice uses Bob's public key to encrypt the
entire signed message including the digital
signature. This makes it possible for Bob to
decipher the signed message using his private
key.
Bob receives the encrypted message and deciphers
it using his private key. At this point, he can
view the unencrypted version of the message text
along with the still encrypted digital signature.
(The digital signature had actully been encrypted
twice, once using Alice's private key and once
using Bob's public key.)
Bob separates the message text from the still
encrypted digital signature.
Then Bob uses Alice's public key to decipher the
digital signature and compares the result with
the unencrypted message text. If they match,
this verifies that the message was actually sent
by Alice (or someone who has access to her
private key). If they don't match, the actual
source of the message is in question.
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 the RSA algorithm
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.5 and WinXP. This program
produces the following output:
Alice's key values:
e: 17
d: 3869
n: 9617
Bob's key values:
e: 17
d: 7973
n: 9557
Extended message:
Hello Bob, how are you?-
Alice's digital signature
645654360346008475874713831303624383162618484532
Extended signed message:
Hello Bob, how are you?-_645654360346008475874713
831303624383162618484532-
Alice's encrypted signed message
3775134981462442655548020315575049268515315878533
1311740103502891756418117565793881488682309495851
7257280481681561515172572873118819371637165132096
2
Bob's deciphered and decoded message:
Hello Bob, how are you?-_645654360346008475874713
831303624383162618484532-
Extracted message text:
Hello Bob, how are you?-
Extracted digital signature:
645654360346008475874713831303624383162618484532
Deciphered and decoded digital signature:
Hello Bob, how are you?-
Valid signature
Note that line breaks were manually entered into
the above text to force it fit into this narrow
publication format.
************************************************/
import java.math.BigInteger;
class Rsa05{
//This is a static inner class whose sole
// purpose is to create an object that serves
// as a container for keys. It was made static
// so that it can be instantiated from within
// main.
static class Keys{
BigInteger n;
BigInteger d;
BigInteger e;
}//end inner class Keys
public static void main(String[] args){
//Instantiate and populate an object
// containing precomputed keys for Alice.
Keys aliceKeys = new Keys();
aliceKeys.n = new BigInteger("9617");
aliceKeys.d = new BigInteger("3869");
aliceKeys.e = new BigInteger("17");
//Instantiate and populate an object
// containing precomputed keys for Bob.
Keys bobPar = new Keys();
bobPar.n = new BigInteger("9557");
bobPar.d = new BigInteger("7973");
bobPar.e = new BigInteger("17");
//Original test message.
String message = "Hello Bob, how are you?";
//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
//Instantiate an object of this class.
Rsa05 obj = new Rsa05();
//Display Alice's keys.
System.out.println("Alice's key values:");
System.out.println("e: " + aliceKeys.e);
System.out.println("d: " + aliceKeys.d);
System.out.println("n: " + aliceKeys.n);
//Display Bob's keys.
System.out.println("Bob's key values:");
System.out.println("e: " + bobPar.e);
System.out.println("d: " + bobPar.d);
System.out.println("n: " + bobPar.n);
//Force the message length to be a multiple
// of half the block length to avoid
// end-effect problems later.
while(message.length()%(blockSize/2) != 0){
//Append a visible character on the end.
message += "-";
}//end while
System.out.println(
"Extended message:n" + message);
//Alice encodes the extended message into
// numeric format.
String aliceEncodedText =
obj.encode(message);
//Alice creates a digital signature by
// encrypting the encoded message using her
// private key.
String aliceDigitalSignature =
obj.doRSA(aliceEncodedText,aliceKeys.d,
aliceKeys.n,blockSize);
System.out.println(
"Alice's digital signaturen"
+ aliceDigitalSignature);
//Alice signs the message by appending the
// digital signature onto the message. She
// identifies the beginning of the digital
// signature by the presence of an
// underscore character.
String aliceSignedMsg =
message + "_" + aliceDigitalSignature;
//Alice forces the signed message length to
// be a multiple of half the block length to
// avoid end-effect problems later.
while(aliceSignedMsg.length()%(blockSize/2)
!= 0){
//Append a visible character on the end.
aliceSignedMsg += "-";
}//end while
System.out.println(
"Extended signed message:n"
+ aliceSignedMsg);
//Alice encodes the signed message to get it
// ready for encryption.
String aliceEncodedMsg = obj.encode(
aliceSignedMsg);
//Alice encrypts the signed message using
// Bob's public key.
String aliceCipherText = obj.doRSA(
aliceEncodedMsg,bobPar.e,
bobPar.n,blockSize);
System.out.println(
"Alice's encrypted signed messagen"
+ aliceCipherText);
//Alice sends the cipherText to Bob. Bob
// deciphers the message using his private
// key.
String bobDecipheredMsg = obj.doRSA(
aliceCipherText,bobPar.d,
bobPar.n,blockSize);
//Bob decodes the deciphered message.
String bobDecodedMsg = obj.decode(
bobDecipheredMsg);
System.out.println(
"Bob's deciphered and decoded message:n"
+ bobDecodedMsg);
//Bob extracts the message text and the
// digital signature from the decoded
// signed message based on the location of
// the underscore character.
String bobMsgText = bobDecodedMsg.substring(
0,bobDecodedMsg.indexOf('_'));
System.out.println(
"Extracted message text:n"
+ bobMsgText);
String receivedSignature =
bobDecodedMsg.substring(
bobDecodedMsg.indexOf('_') + 1);
//Bob removes any dashes at the end of the
// digital signature that were put there by
// Alice to force the signed message length
// to be a multiple of half the block size.
while(receivedSignature.endsWith("-")){
receivedSignature =
receivedSignature.substring(
0,receivedSignature.length()-1);
}//end while
System.out.println(
"Extracted digital signature:n"
+ receivedSignature);
//Bob deciphers and decodes the digital
// signature using the Alice's public key.
// The result should match the text portion
// of the signed message.
String decipheredSignature =
obj.doRSA(receivedSignature,aliceKeys.e
,aliceKeys.n,blockSize);
String decodedSignature = obj.decode(
decipheredSignature);
System.out.println(
"Deciphered and decoded digital signature:n"
+ decodedSignature);
//Bob compares the decoded digital signature
// with the message text in the signed
// message and displays a message indicating
// whether or not the signature is valid.
if(bobMsgText.equals(decodedSignature)){
System.out.println("Valid signature");
}else{
System.out.println("Invalid signature");
}//end else
}//end main
//-------------------------------------------//
//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 message){
byte[] textChars = message.getBytes();
String temp = "";
String encodedText = "";
//Build the encoded text string two numeric
// characters at a time. Each message
// character is converted into two numeric
// characters according to the relationships
// given above.
for(int cnt = 0; cnt < message.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 Rsa05
|
Copyright 2005, 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-
