Java Signing Messages using Redundancy Functions in Java

Signing Messages using Redundancy Functions in Java

Java Programming, Notes # 731


Preface

A series on cryptography in Java

This lesson is one in a series designed to teach you
about the inner workings of cryptography using Java. 
The first lesson was entitled
Public Key
Cryptography 101 Using Java
.  The previous lesson was entitled
Digital
Signatures using Message Digests with Java
.

Public key cryptography and the RSA algorithm

Let’s begin this lesson by recapping what you have learned so far in this
series.  In the first lesson entitled
Public Key
Cryptography 101 Using Java
, you learned about public key cryptography in
general, and you learned how to implement the RSA encryption algorithm in
Java in particular.  You also learned about the differences between symmetric and
asymmetric key cryptography.

Introduction to digital message signing

In the second lesson entitled
Digital
Signatures 101 using Java
, you learned how to use public-key
cryptography and a simple protocol to create digital signatures and to sign
messages.  The usual purpose of signing messages is to make it possible for
the receiving party to confirm both the authenticity and the integrity of a
received message.

Signing a message does not contribute to the preservation of the
confidentiality of the message.  However, you also learned how to use
public key cryptography in addition to message signing to preserve the
confidentiality of a signed message.

Message digests

In the third lesson entitled
Message Digests
101 using Java
, you learned about message digests. 
You also learned how to write Java programs that implement the SHA-1 message
digest algorithm.

Using message digests to sign messages

In the fourth lesson entitled
Digital
Signatures using Message Digests with Java
, you learned how to use the SHA-1 message
digest algorithm in conjunction with the RSA encryption algorithm to create and
use digital signatures that conserve communication bandwidth.

Purpose of this lesson

In this lesson, you will learn how to use redundancy functions in conjunction
with the RSA encryption algorithm to sign messages in order to reduce the
probability of message forgery.

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 dependence on 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 and explain in this series are intended to help
you to learn about and to experiment with various cryptosystems as implemented
in Java code.  They are designed to help you 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 to 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.

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

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 earlier 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 the digital
signing
of messages, the secret key is used to encrypt
some representation of the message 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.  Please see the earlier lesson entitled
Public Key
Cryptography 101 Using Java
to gain a basic understanding of the RSA
algorithm.

Message signing and digital signatures

In one of their papers, the authors of the RSA algorithm point out that “… publicly
revealing an encryption key does not thereby reveal the corresponding
decryption key.

An important consequence of this is that a message can be “signed”
using a privately held key.  The signature can be verified using the
corresponding publicly revealed key.

The need for redundancy functions

Consider the scenario involving Alice and Bob.  Alice needs to send a
message to Bob and to treat it in such a way that Bob can confirm that the
message was actually sent by her, and was not sent by someone else (a
forger)
pretending to be her.  This process is commonly referred to
as authentication.

Even after confirming that the message was actually sent by Alice, Bob needs
to confirm the integrity of the message.  In other words, he needs to
confirm that the message was not modified (purposely or otherwise) during transmission from Alice to Bob.

Why not just encrypt the message using Alice’s
private key?

At first blush, it would seem that Alice can accomplish this simply by
encrypting her message using her private key so that Bob (and anyone else)
can decrypt it using her public key.  After all, it would seem that if
Alice’s private key is truly secret, then no one else could possibly encrypt and
send a message which, when decrypted using Alice’s public key, would appear to
have been sent by her.

Don’t be fooled

However, the people who analyze things like this aren’t comfortable with that
assessment.  Recall that a message that has been encrypted using the RSA
algorithm is just a (potentially long) string of numeric characters. 
Therefore, it is just a number.

The people who know about these things seem to believe that a forger might
systematically generate random numbers and decrypt them using Alice’s public key
until he finds one that will decrypt and decode into a message that would be a
plausible message for Alice to have sent.  If the forger can find such a
number, he can send it to Bob pretending to be Alice and fool Bob into thinking
that the message was sent by Alice.  After all, when Bob decrypts it using
Alice’s public key and decodes the result, he sees a message that could have
been sent by Alice.

The forged message

For example, the forged message might read:

Meet me tonight.

Bob might be fooled by this message and might go to their regular meeting
place only to learn that he has been fooled when Alice doesn’t show up. 

(The private detective hired by Bob’s wife to gather
evidence about Bob’s affair with Alice might show up instead of Alice.  In
fact, the private detective may have been the forger who sent the forged
message to Bob in the first place in order to trick him into showing up for
a phony meeting with Alice.)

Redundancy functions to the rescue

As protection against such forgeries, Alice and Bob could have agreed in advance that every message sent by Alice
to Bob would be processed through a mutually agreed upon redundancy function
prior to encryption using Alice’s private key.  For example, Alice and Bob
might agree in advance that every message that is sent from Alice to Bob would consist of two
concatenated versions of the same message text as shown below:

Meet me tonight.Meet me tonight.

More difficult to forge

It would be much more difficult for the forger to find a random number that
would produce a message which is plausible and which would also match the
structure defined by the redundancy function.  This would greatly reduce
the risk that the forger could forge a message that would fool Bob into thinking
that the message was actually sent by Alice.

Good and poor redundancy functions

There are lots of discussions on various web sites regarding good redundancy
functions and poor redundancy functions.  In the final analysis, it seems
that a good redundancy function is a redundancy function that will produce a
message structure that would be very unlikely to be produced by using Alice’s
public key to decrypt a randomly generated number.

Preview

Although I can’t say whether it is a good redundancy function or a poor
redundancy function, the program named Rsa11 that I will explain in this
lesson illustrates the digital signing of an unencrypted message using a
redundancy function that causes every message sent by Alice to consist of two
concatenated versions of the same message text as shown above.

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, purposely or otherwise.

The program named Rsa11 illustrates 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.  I will have more to say later about how this
program could be upgraded to also provide for confidentiality later in this
lesson.

Discussion and
Sample Code

The program named Rsa11

IMPORTANT: BECAUSE THIS PROGRAM USES PREDETERMINED KEYS THAT WERE DESIGNED
FOR A BLOCK SIZE OF 12, IT WILL WORK CORRECTLY ONLY FOR A BLOCK SIZE OF 12.

The purpose of the program

The purpose of this program is to illustrate the use of redundancy functions
along with public-key cryptography to sign messages in such a way that the
person receiving the message can confirm the authenticity and the integrity of the
message.

No confidentiality

Even though the message is encrypted (using Alice’s private key), this program does not
provide for maintaining the confidentiality of the message. 
Anyone having access to Alice’s public key can decrypt and read the message. 
Preserving confidentiality would
require an additional encryption and decryption operation as discussed later.

Alice and Bob

The comments in the program use the scenario of Alice and Bob. Alice needs to
send a message to Bob.  She needs to treat the message in such a way that Bob can
later confirm that the message was actually sent by Alice, and was not sent by
someone pretending to be Alice.  Bob also needs to be able to confirm that the
message was not modified (purposely or otherwise) during the transmission of the message from Alice to
Bob.

Digital signature scheme with message recovery

The digital signature scheme that is illustrated by this program is commonly
called a digital signature scheme with message recovery.  This is
because the signature can be verified without knowing the original message that
was signed, and the signature verification produces a copy of the original
message.

Apply redundancy function

Alice begins by applying a redundancy function to her message.   The redundancy
function used in this program consists simply of concatenating the message onto
itself.  However, there are numerous other redundancy functions that could be
used by pre-agreement with Bob.

Extend the message for encryption

Then Alice extends the unencoded message causing its length to be a multiple of half the
block size in preparation for encryption using the RSA algorithm.  Since
encoding later will double the length of the message, this causes the length of
the encoded message to be a multiple of the block size as required by the RSA
encryption algorithm.

Specify length of original message

The last four characters in the pad that is added at the end of the message
to extend its length consist of four numeric characters that specify the length of the
original message.  All remaining characters in the pad consist of equal
characters (=).

Although including the length of the original message in the pad is not
necessary, it does make it easier for Bob to confirm the authenticity and
integrity of the message later.

(Most messages will require an
extension that is greater than or equal to four characters, so the inclusion of
these four characters at the end of the pad does not increase the length of the
message in most cases.)

Encode message into numeric format

Following this, Alice encodes the extended message into numeric format in
preparation for encrypting it.   The encoding scheme that Alice uses makes it
possible for the message to include all of the ASCII characters from the space
character to the tilde (~) character.   As mentioned above, this encoding process
doubles the length of the message.

Encrypt the message

Alice uses the RSA encryption algorithm to encrypt the encoded message using
her private key.   Bob can later decrypt the message using her
public key.

Send the message to Bob

Then Alice sends the encrypted message to Bob.

Decrypt and decode the message

Bob decrypts the message using Alice’s public key.  Then he decodes the message using the previously agreed-upon decoding
algorithm.

Get the message length and extract the original
message

Following this, Bob extracts the original message length from the end of the
decoded message.

(Note that the decoded message exhibits the result of Alice having
applied the redundancy function.  For this particular redundancy function, the decoded message contains two concatenated copies of the
original message text plus the required extension at the end.)

Then Bob uses the message length information to extract the original message
text from the
beginning of the decoded message.

Validate the message

Having agreed in advance on the redundancy function, Bob knows that he should
be able to compare the extracted message text with a substring of the decoded
message having an equal number of characters immediately following the extracted message and
get an exact match.  In other words, he knows that the decoded message
should contain two concatenated copies of the original message text.

Although it would be possible for Bob to perform this comparison visually, he
elects to automate the comparison process.  If there is a match, Bob will
conclude that the authenticity and the integrity of the message have been confirmed.  Otherwise, he concludes that
either the authenticity or the integrity of the message is suspect.

Confidentiality

As mentioned above, this program does not maintain the confidentiality of the
message.  Anyone having access to Alice’s public key can read the message.

If
Alice also needed to maintain confidentiality, she could encrypt the message
using Bob’s public key after she encrypts it using her private key.   Then only
Bob or someone having access to his private key could decrypt the message
and gain access to the version of the message that was encrypted using Alice’s
private key.

Predetermined key values

This program uses predetermined values for the following:

  • Alice’s public key, e
  • Alice’s private key, d
  • Alice’s modulus operand, n

The predetermined key values were designed to be used with the RSA algorithm
and a block size of 12.

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

The program output

This program produces the output shown in Figure 1.  Note that line
breaks were manually entered into Figure 1 to force the material to fit into this
narrow publication format.  I will frequently refer back to Figure 1 as I explain the
code in this program.

1. Alice's keys:
2. e: 17
3. d: 279263220413
4. n: 951386374109
5. Block size: 12
6. Alice's msg: Hello Bob, how are you?
7. Alice's msg with redundancy: Hello Bob, how ar
e you?Hello Bob, how are you?
8. Alice's extended msg: Hello Bob, how are you?H
ello Bob, how are you?====0023
9. Alice's encoded msg: 4069767679003479661200727
9870065826900897985314069767679003479661200727987
0065826900897985312929292916161819
10. Alice's encrypted msg: 6249959457456353354512
1866764635465214767698085962583373435382001645227
8218572814588502473073132340176706053
11. Bob's encoded msg: 40697676790034796612007279
8700658269008979853140697676790034796612007279870
065826900897985312929292916161819
12. Bob's decoded msg: Hello Bob, how are you?Hel
lo Bob, how are you?====0023
13. Bob's msg length: 23
14. Bob's extracted msg: Hello Bob, how are you?
15. Msg is valid
      
Figure 1

Discuss in fragments

As is my custom, I will discuss and explain this program by breaking it down
into fragments and explaining the fragments.  You can view the program in its entirety in
Listing 13
near the end of the lesson.

Much of the code in this program is either identical to or very
similar to code that I explained in the previous lesson entitled
Digital
Signatures using Message Digests with Java
and
earlier lessons in this series.  Therefore, I will simply refer you to
those lessons for discussion of the common code.

The Rsa11 and Keys classes

The class named Rsa11 begins in Listing 1.  This class begins
with the definition of a static class named Keys.  This code
is identical to code that I explained in the lesson entitled
Digital
Signatures using Message Digests with Java
, so I will
simply refer you to that lesson for an explanation.

class Rsa11{
  static class Keys{
    //Note, these key values were designed to
    // be used with a block size of 12
    BigInteger n = 
                  new BigInteger("951386374109");
    BigInteger d = 
                  new BigInteger("279263220413");
    BigInteger e = new BigInteger("17");
  }//end inner class Keys
Listing 1

Beginning of the main method

The main method begins in Listing 2.

  public static void main(String[] args){
    //Instantiate an object containing
    // keys.
    Keys aliceKeys = new Keys();
    //Test msg.
    String aliceMsg="Hello Bob, how are you?";
    //Set blockSize.
    int blockSize = 12;
    //Instantiate an object of this class
    Rsa11 obj = new Rsa11();
    //Display the key values along with the
    // modulus operand.
    System.out.println("1. Alice's keys:");
    System.out.println("2. e: " + aliceKeys.e);
    System.out.println("3. d: " + aliceKeys.d);
    System.out.println("4. n: " + aliceKeys.n);
    System.out.println("n5. Block size: " 
                                    + blockSize);
    
    //Display the message that Alice will sign 
    // and send to Bob.
    System.out.println("n6. Alice's msg: "
                                     + aliceMsg);
    //Get and save the length of the original
    // message.
    int origMsgLen = aliceMsg.length();
Listing 2

Once again, I will refer you to the previous lesson entitled
Digital
Signatures using Message Digests with Java
for an
explanation of the code in Listing 2.

Apply the redundancy function

Alice applies the redundancy function to the original message in Listing 3. 
The redundancy function used in this program simply concatenates the original
message text onto itself, creating a new message that is twice the length of the
original message.

    aliceMsg += aliceMsg;
    System.out.println(
             "n7. Alice's msg with redundancy: "
             + aliceMsg);
Listing 3

Listing 3 also displays the result of applying the redundancy function as
Line 7 in Figure 1.  Compare the output in Line 7 with the output in Line
6, which shows the original message.

Extend the message

Alice invokes the method named padTheMsg in Listing 4 to extend the
length of the message to a multiple of half the block size including four
characters at the end that specify the length of the original message.

    aliceMsg = obj.padTheMsg(
                aliceMsg,blockSize/2,origMsgLen);
    System.out.println(
                    "n8. Alice's extended msg: "
                    + aliceMsg);
Listing 4

Note that because the later process of encoding the message into numeric
format doubles the length of the message, this has the effect of causing the
length of the encoded message to be a multiple of the block size, as required by
the RSA encryption algorithm.

The method named padTheMsg

This method is identical to the method having the same name that was
explained in the lesson entitled
Digital
Signatures using Message Digests with Java
.  Therefore, I will refer you to
that lesson for a further explanation of the method.  You can view this
method, and all the methods used in this program in their entirety in Listing 13
near the end of this lesson.

The output

Listing 4 also displays the extended message producing Line 8 in Figure 1. 
As you can see, the pad at the end is made up of equal characters (=) and
four numeric characters indicating that the length of the original message was
23 characters.

Encode the message into numeric format

As explained in earlier lessons in this series, text messages must be
converted into numeric format prior to encryption using the RSA
encryption algorithm.  Alice invokes the encode method in Listing 5
to encode the message into numeric format.

I have explained the encode method in several previous lessons in this
series, so I will refer you to those lessons for an explanation of the encode
method at this point.

Suffice it to say that this encoding scheme makes it possible for the message
to contain any of the characters ranging from the space character to the tilde
(~) character in the ASCII table.

    String aliceEncodedMsg = 
                            obj.encode(aliceMsg);
    System.out.println(
                     "n9. Alice's encoded msg: "
                     + aliceEncodedMsg);
Listing 5

Listing 5 also displays the encoded message, producing the numeric output shown in
Line 9 in Figure 1.  The encoded message is now ready for encryption using
the RSA algorithm.

(Note that the length of the encoded message is 108 characters, which
is a multiple of the block size of 12, as required by the RSA encryption
algorithm.)

Encrypt the encoded message

Alice invokes the doRSA method in Listing 6 to encrypt the encoded
message using her private key.  The doRSA method has been
explained in previous lessons in this series.

    String aliceEncryptedMsg = obj.doRSA(
                         aliceEncodedMsg,
                         aliceKeys.d,aliceKeys.n,
                         blockSize);
    System.out.println(
                  "n10. Alice's encrypted msg: "
                  + aliceEncryptedMsg);
Listing 6

Because the message is encoded using Alice’s private key, it can later be decrypted
by Bob (or anyone else) using Alice’s public key.

Listing 6 also displays the encrypted message producing Line 10 in Figure 1.

Send the encrypted message to Bob

The statement in Listing 7 is intended to simulate the transmission of the
encrypted message from Alice to Bob.

    //*****************************************//
    String bobEncryptedMsg = aliceEncryptedMsg;
    //*****************************************//
Listing 7

Decrypt the message

Bob invokes the doRSA method to decrypt the message in Listing 8. 
He uses Alice’s public key to produce the encoded message.

    String bobEncodedMsg = obj.doRSA(
                                 bobEncryptedMsg,
                                 aliceKeys.e,
                                 aliceKeys.n,
                                 blockSize);
    System.out.println(
                      "n11. Bob's encoded msg: "
                      + bobEncodedMsg);
Listing 8

Listing 8 also displays the encoded message producing Line 11 in Figure 1. 
Compare Line 11 with Line 9 to confirm that Alice’s encoded message has been
correctly reproduced.

You can view the doRSA method in Listing 13 near the end of this
lesson, and read explanations of the method in previous lessons in this series.

Decode the message

Bob invokes the decode method to decode the message in Listing 9. 
You can view the decode method in Listing 13 and read explanations of the
method in previous lessons in this series.

    String bobDecodedMsg = obj.decode(
                                  bobEncodedMsg);
    System.out.println(
                      "n12. Bob's decoded msg: "
                      + bobDecodedMsg);
Listing 9

Listing 9 also displays the decoded message producing Line 12 in Figure 1. 
Compare Line 12 with Line 8 in Figure 1 to confirm that Alice’s extended message
has been correctly reproduced.  Bob now has access to Alice’s extended
message with redundancy as shown in Line 12.  Note that the last four
characters specify the length of the original message.

Extract original message length

Bob extracts the original message length from the end of the decoded message
in Listing 10.

    int bobMsgLen = Integer.parseInt(
                    bobDecodedMsg.substring(
                    bobDecodedMsg.length() - 4));
    System.out.println("n13. Bob's msg length: "
                       + bobMsgLen);
Listing 10

Listing 10 also produces Line 13 in Figure 1, indicating that the length of
the original message was 23 characters.

Extract the original message

Bob uses the original message length in Listing 11 to extract the first 23
characters of the decoded message.  On the basis of the previously agreed
upon redundancy function, this is the original message.

    String bobMsg = bobDecodedMsg.substring(
                                    0,bobMsgLen);
    System.out.println(
                    "n14. Bob's extracted msg: "
                    + bobMsg);
Listing 11

Listing 11 produces Line 14 in the output shown in Figure 1.  Compare
Line 14 with Line 6 in Figure 1 to confirm that the original message has been
successfully reproduced.

Confirm authenticity and integrity

Having agreed in advance on the redundancy function that was used by Alice to
construct the message, Bob knows that he should be able to compare the extracted
message text with a substring having an equal number of characters immediately
following the extracted message in the decoded message and get an exact match. 
If there is a match, he concludes that the authenticity and the integrity of the
message have been confirmed.  Otherwise, he concludes that either the
authenticity or the integrity is suspect.

While Bob could perform this comparison visually, he has elected to automate
the comparison as shown in Listing 12.

    if(bobMsg.equals(bobDecodedMsg.substring(
                      bobMsgLen,2 * bobMsgLen))){
      System.out.println("n15. Msg is valid");
    }else{
      System.out.println(
                       "n15. Msg is not valid");
    }//end else
  }//end main
Listing 12

Listing 12 produces the output shown in Line 15 in Figure 1.  The fact
that the message is deemed to be valid indicates that the message was
sent by Alice and was not sent by a forger pretending to be Alice.  Line 15
also indicates that the integrity of Alice’s message has been confirmed.

Run the Program

I encourage you to copy, compile and run the program named Rsa11 that
you will find in Listing 13.  Experiment with the program, making changes and observing the
results of your changes.

For example, you might want to experiment by replacing the redundancy function with a
different redundancy function of your own design.  You might also want to
experiment by decrypting and decoding a few thousand random numbers to see if
any of them produce plausible messages.  Another good experiment would be
to modify the redundancy function so that it doesn’t properly replicate the
original message and then view the final result shown in Line 15 of Figure 1.

In addition, you might want to upgrade the program so as to protect
the confidentiality of the message during transmission.

Above all, have fun and use this program to learn as much as you
can about the theory behind and the mechanics of digital signatures
using redundancy functions and 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.

I explained two of those protocols in earlier lessons.  In this lesson I
explained the use of redundancy functions which give rise to what is
commonly called a digital signature scheme with message recovery
With this scheme, the signature can be verified without knowledge of the
original message that was signed.  In addition, signature verification
produces a copy of the original message.

The scheme, as explained in this message, does not provide for protecting the
confidentiality of the message during transmission.  However,
confidentiality could be achieved if the sender were to encrypt the signed
message using the receiver’s public key prior to transmitting of the message. 
I leave the implementation of such encryption as an exercise for the reader.

Complete Program
Listing

A complete listing of the program discussed in this lesson is provided in
Listing 13 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 Rsa11.java
Copyright 2005, R.G.Baldwin
IMPORTANT:  BECAUSE THIS PROGRAM USES
PREDETERMINED KEYS THAT WERE DESIGNED FOR A BLOCK
SIZE OF 12, IT WILL WORK CORRECTLY ONLY FOR A
BLOCK SIZE OF 12.
The purpose of this program is to illustrate the 
use of redundancy functions along with public-key
cryptography to sign messages in such a way that 
the person receiving the message can confirm the 
authenticity and integrity of the message.
This program does not maintain the 
confidentiality of the message. That would 
require an additional encryption and decryption 
operation as discussed later.
The comments in the program use the scenario of 
Alice and Bob.  Alice needs to send a message to 
Bob.  She needs to treat the message in such a 
way that Bob can later confirm that the message 
was actually sent by Alice, and was not sent by 
someone pretending to be Alice.  He also needs to
be able to confirm that the message was not 
modified during the transmission of the message 
from Alice to Bob.
                                     
Alice begins by applying a redundancy function to
her message. The redundancy function used in this
program consists simply of concatenating the 
message onto itself. However, there are numerous 
other redundancy functions that could be used by 
prior agreement between Alice and Bob.
    
Then Alice extends the unencoded message length 
to a multiple of half the block size in 
preparation for encryption using the RSA 
algorithm. Since encoding later will double the 
length of the message, this causes the length of 
the encoded message to be a multiple of the block
size.
The last four characters in the pad that is added
at the end of the message to extend it consist of
four numeric characters that specify the length 
of the original message. All remaining characters
in the pad consist of equal characters (=). 
Although including the length of the original 
message is not necessary, it does make it easier 
for Bob to validate the authenticity and 
integrity of the message later. In addition, most
messages will require an extension that is 
greater than or equal to four characters, so the 
inclusion of these four characters at the end of 
the pad does not increase the length of the 
message in most cases.
    
Following this, Alice encodes the extended 
message into numeric format in preparation for 
encrypting it. The encoding scheme that Alice 
uses makes it possible for the message to include
all of the characters from the space character to
the tilde (~) character. As mentioned above, this
encoding process doubles the length of the 
message.
    
Alice uses the RSA encryption algorithm to 
encrypt the encoded message using her private 
key. Bob can later decrypt the message using her 
public key.
Then Alice sends the encrypted message to Bob.
    
Bob decrypts the message using Alice's public 
key.
    
Then he decodes the message using the previously 
agreed-upon decoding algorithm.
    
Following this, Bob extracts the original message
length from the end of the decoded message.
Note that the decoded message exhibits the result
of the redundancy function having been applied to
the original message by Alice. For this 
particular redundancy function, the decoded 
message contains two concatenated copies of the 
original message plus the required extension at 
the end.
Then Bob uses the message length to extract the 
original message from the beginning of the 
decoded message. 
Having agreed in advance on the redundancy 
function, Bob knows that he should be able to 
compare the extracted message text with a 
substring of the decoded message having an equal 
number of characters following the extracted 
message and get an exact match. If there is a 
match, he concludes that the authenticity and 
integrity of the message is confirmed. Otherwise,
he concludes that either the authenticity or the 
integrity or both are suspect.
As mentioned above, this program does not 
maintain the confidentiality of the message. 
Anyone having access to Alice's public key can 
read the message. If Alice also needed to 
maintain confidentiality, she could encrypt the 
message using Bob's public key after she encrypts
it using her private key. Then only Bob or 
someone having access to his private key could 
decrypt the message gaining access to the version
of the message that was encrypted using Alice's 
private key.
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.  Note that line
breaks were manually entered to force the 
material to fit in this narrow publication
format.
1. Alice's keys:
2. e: 17
3. d: 279263220413
4. n: 951386374109
5. Block size: 12
6. Alice's msg: Hello Bob, how are you?
7. Alice's msg with redundancy: Hello Bob, how ar
e you?Hello Bob, how are you?
8. Alice's extended msg: Hello Bob, how are you?H
ello Bob, how are you?====0023
9. Alice's encoded msg: 4069767679003479661200727
9870065826900897985314069767679003479661200727987
0065826900897985312929292916161819
10. Alice's encrypted msg: 6249959457456353354512
1866764635465214767698085962583373435382001645227
8218572814588502473073132340176706053
11. Bob's encoded msg: 40697676790034796612007279
8700658269008979853140697676790034796612007279870
065826900897985312929292916161819
12. Bob's decoded msg: Hello Bob, how are you?Hel
lo Bob, how are you?====0023
13. Bob's msg length: 23
14. Bob's extracted msg: Hello Bob, how are you?
15. Msg is valid
************************************************/
import java.math.BigInteger;
import java.security.*;
class Rsa11{
  //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{
    //Note, these key values were designed to
    // be used with a block size of 12
    BigInteger n = 
                  new BigInteger("951386374109");
    BigInteger d = 
                  new BigInteger("279263220413");
    BigInteger e = new BigInteger("17");
  }//end inner class Keys
  public static void main(String[] args){
    //Instantiate an object containing
    // keys.
    Keys aliceKeys = new Keys();
    //Test msg.
    String aliceMsg="Hello Bob, how are you?";
    //Set blockSize.
    int blockSize = 12;
    //Instantiate an object of this class
    Rsa11 obj = new Rsa11();
    //Display the key values along with the
    // modulus operand.
    System.out.println("1. Alice's keys:");
    System.out.println("2. e: " + aliceKeys.e);
    System.out.println("3. d: " + aliceKeys.d);
    System.out.println("4. n: " + aliceKeys.n);
    System.out.println("n5. Block size: " 
                                    + blockSize);
    
    //Display the message that Alice will sign 
    // and send to Bob.
    System.out.println("n6. Alice's msg: "
                                     + aliceMsg);
                                     
    //Get and save the length of the original
    // message.
    int origMsgLen = aliceMsg.length();
                                     
    //Alice applies a redundancy function, which
    // consists simply of concatenating the
    // message onto itself.
    aliceMsg += aliceMsg;
    System.out.println(
             "n7. Alice's msg with redundancy: "
             + aliceMsg);
    
    //Alice extends the message length to a
    // multiple of half the block size including
    // four char at the end that specify the
    // length of the original message.
    
    aliceMsg = obj.padTheMsg(
                aliceMsg,blockSize/2,origMsgLen);
    System.out.println(
                    "n8. Alice's extended msg: "
                    + aliceMsg);
    
    //Alice encodes the extended msg into
    // numeric format in preparation for
    // encrypting it.
    String aliceEncodedMsg = 
                            obj.encode(aliceMsg);
    System.out.println(
                     "n9. Alice's encoded msg: "
                     + aliceEncodedMsg);
    
    //Alice encrypts the encoded message using
    // her private key
    String aliceEncryptedMsg = obj.doRSA(
                         aliceEncodedMsg,
                         aliceKeys.d,aliceKeys.n,
                         blockSize);
    System.out.println(
                  "n10. Alice's encrypted msg: "
                  + aliceEncryptedMsg);
    
    //*****************************************//
    //Alice sends the encrypted message to Bob
    String bobEncryptedMsg = aliceEncryptedMsg;
    //*****************************************//
    
    //Bob decrypts the message using Alice's
    // public key.
    String bobEncodedMsg = obj.doRSA(
                                 bobEncryptedMsg,
                                 aliceKeys.e,
                                 aliceKeys.n,
                                 blockSize);
    System.out.println(
                      "n11. Bob's encoded msg: "
                      + bobEncodedMsg);
    
    //Bob decodes the message using the
    // agreed-upon decoding algorithm.
    String bobDecodedMsg = obj.decode(
                                  bobEncodedMsg);
    System.out.println(
                      "n12. Bob's decoded msg: "
                      + bobDecodedMsg);
    
    //Bob extracts the original message length
    // from the end of the decoded message
    int bobMsgLen = Integer.parseInt(
                    bobDecodedMsg.substring(
                    bobDecodedMsg.length() - 4));
    System.out.println("n13. Bob's msg length: "
                       + bobMsgLen);
    
    //Bob uses the msg length to extract the
    // original msg.
    String bobMsg = bobDecodedMsg.substring(
                                    0,bobMsgLen);
    System.out.println(
                    "n14. Bob's extracted msg: "
                    + bobMsg);
    
    //Having agreed in advance on the redundancy
    // function, Bob knows that he should be able
    // to compare the extracted msg text with a
    // substring having an equal number of
    // characters following the extracted msg in
    // the decoded msg and get an exact match. 
    // If there is a match, he concludes that the
    // authenticity and integrity of the message
    // is confirmed.  Otherwise, he concludes
    // that either the authenticity or the
    // integrity or both are suspect.
    if(bobMsg.equals(bobDecodedMsg.substring(
                      bobMsgLen,2 * bobMsgLen))){
      System.out.println("n15. Msg is valid");
    }else{
      System.out.println(
                       "n15. Msg is not valid");
    }//end else
  }//end main
  //-------------------------------------------//
  
  //This method pads a message such that the
  // final length is a multiple of block and the
  // last four bytes specify the origMsgLength.
  // All the remaining bytes in the pad are
  // filled with equal characters (=). The padded
  // message is returned as type String.
  private String padTheMsg(
          String msgIn,int block,int origMsgLen){
    byte[] msgData = msgIn.getBytes();
    int msgInLen = msgData.length;
    int tailLength = msgInLen%block;
    int padLength = 0;
    if((block - tailLength >= 4))
      padLength = block - tailLength;
    else 
      padLength = 2*block - tailLength;
      
    //Create a four-byte array containing
    // characters that indicate the length of
    // the original msg with leading zeros if
    // necessary.
    String msgLenAsStr = "" + origMsgLen;
    //Confirm number of characters.
    if((msgLenAsStr.length() > 4) 
                 || (msgLenAsStr.length() <= 0)){
      System.out.println(
                        "Message length error.");
      System.exit(0);
    }//end if
    
    //Prepend leading zeros if necessary
    if(msgLenAsStr.length() == 1){
      msgLenAsStr = "000" + msgLenAsStr;
    }else if(msgLenAsStr.length() == 2){
      msgLenAsStr = "00" + msgLenAsStr;
    }else if(msgLenAsStr.length() == 3){
      msgLenAsStr = "0" + msgLenAsStr;
    }else if(msgLenAsStr.length() == 1){
      msgLenAsStr = "000" + msgLenAsStr;
    }//end else
    
    //Create a four-byte array containing the
    // original message length as four numeric
    // characters with leading zeros.
    byte[] msgLenAsBytes = 
                          msgLenAsStr.getBytes();
      
    //Construct an array containing the bytes
    // required to make the padded message length
    // equal to a multiple of block
    byte[] thePad = new byte[padLength];
    //Populate the array with = characters. 
    // No need to put = characters in the last
    // four bytes.
    for(int cnt = 0;cnt < thePad.length - 4;
                                          cnt++){
      thePad[cnt] = '=';
    }//end for loop
    
    //Put the original message length at the end
    // of the pad.
    System.arraycopy(msgLenAsBytes,0,thePad,
                            thePad.length - 4,4);
    
    //Create an output array.
    byte[] output = 
                  new byte[msgInLen + padLength];
    //Populate the output array with the original
    // msgData concatenated with the pad.
    System.arraycopy(msgData,0,output,0,
                                       msgInLen);
    System.arraycopy(
       thePad,0,output,msgInLen,thePad.length);
       
    //Convert the output to a String and return
    // the String..
    String outputAsStr = new String(output);
    return outputAsStr;
  }//end padTheMsg
  //-------------------------------------------//
  
  //The purpose of this method is to encode a
  // plain text msg 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 msg){
    byte[] textChars = msg.getBytes();
    String temp = "";
    String encodedMsg = "";
    //Build the encoded text string two numeric
    // characters at a time.  Each msg
    // character is converted into two numeric
    // characters according to the relationships
    // given above.
    for(int cnt = 0; cnt < msg.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
  //-------------------------------------------//
  //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
  //-------------------------------------------//
  
  //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
  //-------------------------------------------//
}//end class Rsa11
Listing 13

 


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 have 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.

[email protected]

Latest Posts

Related Stories