October 2, 2014
Hot Topics:
RSS RSS feed Download our iPhone app

Digital Signatures 101 using Java

  • February 8, 2005
  • By Richard G. Baldwin
  • Send Email »
  • More Articles »

Java Programming, Notes # 728


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:
e: 17
d: 3869
n: 9617
Alice's extended message:
Hello Bob, how are you?-
Alice's digital signature
645654360346008475874713831303624383162618484532
Alice's signed message:
Hello Bob, how are you?-_645654360346008475874713
831303624383162618484532
Bob's extracted message text:
Hello Bob, how are you?-
Bob's extracted digital signature:
645654360346008475874713831303624383162618484532
Bob's decoded digital signature:
Hello Bob, how are you?-
Bob's conclusion: Valid signature

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{
static class Keys{
BigInteger n = new BigInteger("9617");
BigInteger d = new BigInteger("3869");
BigInteger e = new BigInteger("17");
}//end inner class Keys

public static void main(String[] args){
//Instantiate an object containing
// keys.
Keys keys = new Keys();

Listing 1

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?";

Listing 2

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;

//Instantiate an object of this class
Rsa04 obj = new Rsa04();

//Display the key values
System.out.println("Alice's keys:");
System.out.println("e: " + keys.e);
System.out.println("d: " + keys.d);
System.out.println("n: " + keys.n);

Listing 3

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){
message += "-";
}//end while
System.out.println(
"Alice's extended message:\n"
+ message);

Listing 4

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);

Listing 5

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(
encodedMsg,keys.d, keys.n,blockSize);

System.out.println(
"Alice's digital signature\n"
+ signature);

Listing 6

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;

System.out.println(
"Alice's signed message:\n"
+ signedMsg);

Listing 7

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 =
signedMsg.substring(
0,signedMsg.indexOf('_'));

System.out.println(
"Bob's extracted message text:\n"
+ extractedMsgText);

Listing 8

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 =
signedMsg.substring(
signedMsg.indexOf('_') + 1);
System.out.println(
"Bob's extracted digital signature:\n"
+ extractedSignature);

Listing 9

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 =
obj.doRSA(extractedSignature,keys.e
,keys.n,blockSize);

String decodedSignature = obj.decode(
decipheredSignature);
System.out.println(
"Bob's decoded digital signature:\n"
+ decodedSignature);

Listing 10

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))
{
System.out.println(
"Bob's conclusion: Valid signature");
}else{
System.out.println(
"Bob's conclusion: Invalid signature");
}//end else

}//end main

Listing 11

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

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");

Listing 13

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

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);

Listing 15

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);

Listing 16

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 signature\n"
                        + aliceDigitalSignature);

Listing 17

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;

Listing 18

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

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);

Listing 20

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);

Listing 21

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

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);

Listing 23

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);

Listing 24

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);

Listing 25

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

Listing 26

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
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 unencrypted message along with the
later verification of the signature by the
receiver of the message.

The comments in this program reflect the
scenario of Alice and Bob, which is common in
discussions of RSA.

Alice needs to send a signed unencrypted message
to Bob. The message needs to be signed so that
Bob can be confident that the message that he
received was sent by Alice and not by someone
pretending to be Alice.

First Alice creates a digital signature by
encrypting the message using her private key and
the RSA algorithm. Bob can later decipher the
digital signature using Alice's public key.

Then Alice signs the message by appending the
digital signature onto the end of the unencrypted
message using an underscore character as the
delimiter between the text portion of the message
and the digital signature. Bob will need the
delimiter later to separate the text portion of
the message from the digital signature.

Then Alice sends the signed message to Bob.

Bob separates the text portion of the message
from the digital signature. Then he deciphers
the digital signature using Alice's public key.
The result should match the text portion of the
message.

Bob then compares the deciphered version of the
digital signature with the text portion of the
message. If they match, he concludes that the
message was actually sent by Alice, or by someone
having access to her private key. If they fail
to match, the actual source of the message is in
question.

This program supports all of the ASCII characters
from space (32) through ~ (126) inclusive to be
used in the message.

This program uses predetermined values for the
following:
Alice's public key, e
Alice's private key, d
Alice's modulus operand, n

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 keys:
e: 17
d: 3869
n: 9617
Alice's extended message:
Hello Bob, how are you?-
Alice's digital signature
645654360346008475874713831303624383162618484532
Alice's signed message:
Hello Bob, how are you?-_645654360346008475874713
831303624383162618484532
Bob's extracted message text:
Hello Bob, how are you?-
Bob's extracted digital signature:
645654360346008475874713831303624383162618484532
Bob's decoded digital signature:
Hello Bob, how are you?-
Bob's conclusion: Valid signature

Note that line breaks were manually entered into
the above text to force it fit into this narrow
publication format.

Also note that you can reverse the values of the
two keys and get the same result. In other
words, it doesn't matter which key you use to
sign the message as long as you use the other
key to decipher the digital signature.
************************************************/
import java.math.BigInteger;

class Rsa04{
//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. It contains precomputed values for
// the two keys, e and d, and the modulus
// operand n.
//
// e is the public key
// d is the private key
static class Keys{
BigInteger n = new BigInteger("9617");
BigInteger d = new BigInteger("3869");
BigInteger e = new BigInteger("17");
}//end inner class Keys

public static void main(String[] args){
//Instantiate an object containing
// keys.
Keys keys = new Keys();

//Raw test message.
String message = "Hello Bob, how are you?";

//Set blockSize
int blockSize = 4;

//Instantiate an object of this class
Rsa04 obj = new Rsa04();

//Display the key values along with the
// modulus operand.
System.out.println("Alice's keys:");
System.out.println("e: " + keys.e);
System.out.println("d: " + keys.d);
System.out.println("n: " + keys.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(
"Alice's extended message:\n"
+ message);

//Alice encodes the message into numeric
// format.
String encodedMsg = obj.encode(message);

//Alice creates a digital signature by
// encrypting the encoded message using her
// private key.
String signature = obj.doRSA(
encodedMsg,keys.d, keys.n,blockSize);
System.out.println(
"Alice's digital signature\n"
+ signature);

//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 signedMsg = message + "_" + signature;
System.out.println(
"Alice's signed message:\n"
+ signedMsg);

//Alice sends the message go Bob. At the
// receiving end, Bob extracts the message
// text and the digital signature from the
// signed message based on the location of
// the underscore character.
String extractedMsgText =
signedMsg.substring(
0,signedMsg.indexOf('_'));
System.out.println(
"Bob's extracted message text:\n"
+ extractedMsgText);
String extractedSignature =
signedMsg.substring(
signedMsg.indexOf('_') + 1);
System.out.println(
"Bob's extracted digital signature:\n"
+ extractedSignature);

//Bob deciphers and decodes the digital
// signature using Alice's public key. The
// result should match the plain text portion
// of the signed message.
String decipheredSignature =
obj.doRSA(extractedSignature,keys.e
,keys.n,blockSize);

String decodedSignature = obj.decode(
decipheredSignature);
System.out.println(
"Bob's 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(extractedMsgText.equals(decodedSignature))
{
System.out.println(
"Bob's conclusion: Valid signature");
}else{
System.out.println(
"Bob's conclusion: 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 encodedMsg = "";

//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;
encodedMsg += temp;
}//end for loop
return encodedMsg;
}//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 encodedMsg){
String temp = "";
String decodedText = "";
for(int cnt = 0; cnt < encodedMsg.length();
cnt += 2){
temp = encodedMsg.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 Rsa04

Listing 27

/*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


Listing 28


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.

Baldwin@DickBaldwin.com

-end-






Comment and Contribute

 


(Maximum characters: 1200). You have characters left.

 

 


Sitemap | Contact Us

Rocket Fuel