Published: February 8, 2005
By Richard G. Baldwin
Java Programming, Notes # 728
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.
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:
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.
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:
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.
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:
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 = |
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:
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:
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:
String aliceEncodedText =
obj.encode(message);
String aliceDigitalSignature =
obj.doRSA(aliceEncodedText,aliceKeys.d,
aliceKeys.n,blockSize);
System.out.println(
"Alice's digital signature\n"
+ 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 message\n"
+ 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.
I encourage you to copy, compile and run the following programs that are provided in this lesson:
Experiment with the programs, making changes and observing the results of your changes.
Above all, have fun and use these programs to learn as much as you can about the theory behind and the mechanics of digital signatures using public key cryptography as implemented using Java.
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.
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 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 signature\n"
+ 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 message\n"
+ 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.
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-