FORM -2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENTS RULES, 2003
COMPLETE SPECIFICATION
(See Section 10 and Rule 13)
A SYSTEM AND METHOD FOR DESIGNING DIGITAL
SIGNATURE SCHEMES BASED ON MESSAGE
PREPROCESSING FUNCTIONS
TATA CONSULTANCY SERVICES LIMITED,
an Indian Company of Nirmal Building, 9th Floor, Nariman Point, Mumbai - 400 021,
Maharashtra, India.
The following specification particularly describes the invention and the manner in which
it is to be performed

FIELD OF THE INVENTION
The present invention relates to the field of cryptography.
Particularly, the present invention relates to designing of digital signatures schemes based on Message pre-processing functions.
DEFINITIONS OF TERMS USED IN THE SPECIFICATION
The term 'Digital Signature' or 'Digital Signature Scheme (DSS)' in this specification relates to a mechanism for determining the authenticity of a message, financial transaction and cases where there is a necessity to detect forgery or tampering.
The term 'Message' in this specification relates to any digital information including transactions, emails, documents and like which need to be secured.
The term 'Signature Primitives' in this specification relates to known systems used for creating and verifying digital signatures for instance RSA-PSS, PKCS # 1 vl.5 and the like.
These definitions are in addition to those expressed in the art.
BACKGROUND OF THE INVENTION AND PRIOR ART
Digital signatures are mechanisms which ensure secure online transactions. They give the receiver the assurance that the source of a message or information is authentic.

Typically, a digital signature consists of three parts namely key generation, signing of the message/generating a signature for the message and verification of the signature attached to the message. There are various techniques known in the art for implementation of digital signatures. The University of California has a U.S. patent, which covers the signature-formatting methods commonly known as Probabilistic Signature Scheme (PSS) and PSS with message recovery. RSA lab encourages using RSA-PSS protocol for digital signature applications.
In cryptography, RSA is an algorithm for public-key cryptography. It is the first algorithm known to be suitable for signing as well as encryption, and one of the first great advances in public key cryptography. RSA was named after the RSA public key cryptography algorithm, which was in turn was named after the initials of its co-inventors: Ron Rivest, Adi Shamir, and Len Adleman. RSA-based signature scheme was developed in 1991 as part of RSA Laboratories' Public-Key Cryptography Standards (PKCS). In this scheme, described in the PKCS #1 vl.5 document, a simple padding format (embedding) is applied to the hash value to produce a message representative. The PKCS #1 vl.5 signature scheme has held up to scrutiny over the past decade and is widely deployed, though no formal proof of the scheme's security is known. Most digital certificates in the Secure Socket Layer (SSL) protocol, for instance, are signed with PKCS #1 vl.5.
In 2007, National Institute of Standard and Technology (NIST) introduced randomized hashing methods in digital signature schemes. This recommendation specifies a method to enhance the security of the

cryptographic hash functions used in digital signature applications by randomizing the messages that are signed.
Apart from the aforementioned techniques which are now standards for generation and verification of digital signatures, there have been attempts in the prior art to generate robust and tamper proof digital signatures.
European Patent 1083700 describes a Hybrid digital signature schemein which a message is divided in to a first portion that is hidden and is recovered during verification, and a second portion that is visible and is required as input for the verification algorithm. A first signature component is generated by encrypting the first portion alone. An intermediate component is formed by combining the first component and the visible portion and cryptographically hashing them. A second signature component is then formed using the intermediate component and the signature comprises the first and second components with the visible portion. A verification of the signature combine's a first component derived only from the hidden portion of the message with the visible portion and produces a hash of the combination. The computed hash is used together with publicly available information to generate a bit string corresponding to, the hidden portion. If the required redundancy is present the signature is accepted and the message is reconstructed from the recovered bit string and the visible portion.
United States Patent Number .5604804 describes a method for certifying
public keys of a digital signature scheme in a communications system. The
secure communications system is one in which there are at least two levels
of authorities. A user presents a piece of data to an intermediate level

authority, who upon verifying the data, causes an issuing authority to issue a certificate that the piece of data posses a given property. Although the certificate is made compact by not having it contain a public key of the intermediate authority, nonetheless, information is stored in order to keep the intermediate authority accountable.
United States Patent Number 5537475 describes an efficient digital signature algorithm. It discloses a digital signature scheme wherein the signature of a message M relative to a public key is computed by means of a secret key. The scheme begins by having the user select a number x independent of M. This step may occur off-line and before there is any knowledge of the particular, message M to be signed. To sign the message, the routine computes a description of a function G which is dependent on the message M, and then applies the function G to x to produce a string z. The routine outputs z and a description of a second function F as the desired signature of the message M. Thus according to the invention a signature of the message is obtained by applying to an independent argument x a function dependent on M. This operation provides enhanced efficiency and security over the prior art and facilitates use of the scheme to allow multiple users of a secure communications system to share the same public key; alternatively, the scheme is useful for generating short certificates of public keys used in such systems.
United States Patent Application Number 20050262353 describes digital signatures including identity-based aggregate signatures. The disclosure allows multiple identity-based digital signatures to be merged into a single identity-based "aggregate" digital signature. This identity-based aggregate

signature has a shorter bit-length than the concatenation of the original un-aggregated identity-based signatures. The identity-based aggregate signature can be verified by anyone who obtains the public keys of one or more Private Key Generators (PKGs), along with a description of which signer signed which message. The verifier does not need to obtain a different public key for each signer, since the signature scheme is "identity-based"; the number of PKGs may be fewer than the number of signers.
European patent number 1063813 describes a public key encryption with digital signature scheme. An encryption and digital signature method which has been disclosed reuses an encryption ephemeral key pair from an encryption process in a digital signature process. The reuse of the encryption ephemeral key pair in the digital signature process advantageously results in reduced byte size of the digital signature and reduction of costly computation overhead. The disclosure is based on the El Gamal encryption scheme and the Nyberg-Rueppel signature scheme.
United States Patent Number 7096365 describes digital signatures. The disclosure relates to the generation of digital signatures by the use of which the legal binding nature of a digital signature is enhanced. For this, .an expanded digital signature is created which, in addition to the hash, contains other information, in particular information identifying the hardware and software environment used in generating the signature.
United States Patent Application 20080148055 describes a Fast RSA signature verification. An RSA message signature can be verified by verifying that se mod n=F(m, n). If a value K, defined as K=se div n is computed in advance "and provided as an input to the" computing device

verifying the signature, the signature verification can be significantly faster. To avoid transmission of, and mathematical operations on, large values of K, which can themselves be inefficient, the RSA public exponent e can be selected to be relatively small, such as e=2 or e=3 K is based on publicly available information and can be calculated by the computing device signing the message, or by an intermediate computing device, and transmitted to the device verifying the signature without impacting security.
United States Patent number 7058808 describes a method for making a blind RSA-signature and apparatus therefor. The essence is in that when making a digital blind RSA-signature, a new technique for blinding an initial data by a RSA-encryption and corresponding. technique for unblinding the signed blinded data are employed, which gives a possibility to use an unlimited number of kinds of the signature in electronic systems of the mass scale service.
United States Patent number 7231040 describes multiprime RSA public key cryptosystem. The disclosure improves public key encryption and decryption schemes that employ a composite number formed from three or more distinct primes. The encryption or decryption tasks may be broken down into sub-tasks to obtain encrypted or decrypted sub-parts that are then combined using a form of the Chinese Remainder Theorem to obtain the encrypted or decrypted value. Parallel encryption/decryption architecture is disclosed to take advantage of the method.
United States Patent number 6084965 describes an identification scheme, a digital signature scheme giving message recovery and a digital signature scheme with appendix. In processing and transmitting information, a

transmitting counterpart of a transmission message is confirmed. The unauthorized modification of the message is confirmed and transmitting behavior is detected, thereby providing the reliable information service, United States Patent number 7036014 describes a Probabilistic signature scheme. One preferred signing routine requires one RSA decryption plus some hashing, verifications require one RSA encryption plus some hashing, and the size of the signature preferably is the size of the modulus. Given an ideal underlying hash function, the scheme is not only provably secure, but has security tightly related to the security of the RSA.
United States Patent number 713176 describes signatures with confidential message recovery. A method for digitally signing an electronic document is disclosed which includes generating an electronic document to be signed and notifying an authorized signer to sign the electronic document. The method includes validating if the user is the authorized signer for the electronic document by comparing the received identification and the password with a digital certificate of the authorized signer stored in a database. Additionally, the disclosure includes obtaining an-image including a digital signature of the authorized signer from a database and resizing the image and inserting the resized image into the signature area of the electronic document if the user is the authorized signer.
United States Patent Application number 20090085780 describes a method for preventing and detecting hash collisions of data during the data transmission. A means for avoiding hash collisions by means of message pre-processing function to increase randomness and reduce redundancy of an input message whereby hash collisions are avoided when it is applied before

hashing any message and the message pre-processing function comprises four steps like shuffling of bits, compression T-function and LFSR which steps increase the entropy of the input message at the end of four rounds, the output becomes more random.
However, the above disclosures involve complex computations which increase the system overhead, complexity and time. These disclosures do not reuse the existing digital signature schemes to enhance and provide robust
and tamper proof systems.
Therefore, there is a need for a secure, more robust, tamper-proof system for providing digital signatures and enhancing security.
OBJECT OF THE INVENTION
lt is an object of the present invention to provide a system and method for generation of secure and tamper proof digital signatures.
It is another object of the present invention to provide a system which enhances the efficiency of signature primitives known in the art to create robust digital signatures.
It is yet another object of the present invention to provide a system which is secure, more robust and tamper-proof using minimum computational overheads.
It is still another object of the present invention to provide an adaptable system which incorporates existing signature primitives to generate secure, more robust, tamper-proof digital signatures.

SUMMARY OF THE INVENTION
In accordance with the present invention, there is provided a system for creation of secure and tamper proof messages using message preprocessing and predetermined signature primitives, the system comprising:
• input means adapted to receive a message which is to be digitally signed;
• message preprocessing means adapted to process the message and further adapted to provide a preprocessed message, the message preprocessing means having:
i. a random value generator adapted to receive the message and further adapted to provide preprocessed message value based on predetermined signature primitive being used and the message;
• signature means adapted to receive the preprocessed message and produced a signed message using the predetermined signature primitives; and
• verification means adapted to verify the signed message using the message preprocessing means to detect message forgery.
Preferably, in accordance with this invention, the signature unit employs
signature primitives selected from the group of primitives consisting of
. RSA-PSS system, PKCS #1 vl.5 system and Message Randomization
system.

Preferably, in accordance with this invention, the preprocessed message value can be selected from a group of values consisting of a random message, a random salt value and a random value.
In accordance with the present invention, there is provided a method for creation of secure and tamper proof messages using message preprocessing and predetermined signature primitives, the method comprising the following steps:
• receiving a message which is to be digitally signed;
• generating a random preprocessing message value;
• preparing a preprocessed message using the random preprocessed message value;
• providing the preprocessed message to the pre-determined signature primitive;
• signing the preprocessed message ; and
• verifying the signed message.
Typically, in accordance with this invention, the step of verifying the signed message includes the step of verifying the message using a verification primitive and message preprocessing functions.
BRIEF DESCRIPTION OF THE ACCOMPANYING DRAWINGS
The invention will now be described in relation to the accompanying drawings, in which:

FIGURE 1 illustrates a schematic of the system for designing digital signature schemes based on Message Preprocessing (MP) functions, in accordance with the present invention;
FIGURE 2 illustrates the steps involved in the signature primitive of RSS-PSS with MP function produced by the system, in accordance with the present invention;
FIGURE 3 illustrates the steps involved in the verification primitive of RSS-PSS with MP function produced by the system, in accordance with the present invention;
FIGURE 4 illustrates the steps involved in the EMSA-PSS signature primitive through MP function produced by the system, in accordance with the present invention;
FIGURE 5 illustrates the steps involved in the Message Randomization signature primitive through MP function produced by the system, in accordance with the present invention; and
FIGURE 6 illustrates the steps for designing digital signature schemes based on Message Preprocessing (MP) functions, in accordance with the present invention.
DETAILED DESCRIPTION
The invention will now be described with reference to the embodiments
. shown in the accompanying drawings. The. embodiments do not limit the
scope and ambit of the invention. The description relates purely to the

exemplary preferred embodiments of the invention and its suggested
application.
According to this invention, there is envisaged a system for providing tamper-proof digital signatures using message preprocessing functions with digital signature primitives.
It has been found, upon investigating applications of Message Preprocessing (MP) in Digital Signature Scheme (DSS), that there are many signature schemes which have identified a role of MP in RSA-PSS (Probabilistic Signature Scheme), PKCS #1 vl.5 and Randomized Hashing digital signatures without affecting interoperability issues. In these signature schemes, message preprocessing of a given message is typically passed into a message digest means/ hashing means guided by a hash algorithm that produces a fixed length hash value which can be verified by the corresponding verification means guided by a verification algorithm equipped with a message preprocessing means. If the verification primitive means does not have a message preprocessing means, it checks the message integrity without performing MP operations.
According to the system of this invention, the verification means guided by
the verification algorithm not only examines hash values, but also analyzes
message pre processing performed by the message pre processing means.
Hence, there are analytical proofs provided that signature schemes with
message preprocessing are more secure.
The rationale behind using MP in DSS is to avoid message tampering. An approach of MP in DSS provides:

(i) assurance about the authenticity of the signed data;
(ii) authentication to the identity of an entity; and
(iii) determines that the software, or firmware has not been modified.
In accordance with this invention, message preprocessing is performed prior to signing of a message using digital signature primitives. The system is adaptable and can work in conjunction with any of the digital signature primitives to prevent forgery. FIGURE 1 shows a schematic of the present invention for designing digital signature schemes based on Message Preprocessing (MP) functions.
The system comprises input means 100 which receives a message which is to be is to be digitally signed. This received message is passed to the message preprocessing means 102 to process the message and further provide a preprocessed message. The message preprocessing means 102 includes a random value generator (not shown in the figures) which receives the" "message and provides a preprocessed message value based on predetermined signature primitive being used and the type of message. The preprocessed message value can be a random message, a random salt value, a random value and the like based on the digital signature primitive requirement.
This preprocessed message is then given to a signature means 104 which uses its standard operational procedures which are techniques known in the art to perform operations like hashing, encryption and the like on the preprocessed message to produce a signed message / encoded message.

This message is verified by a verification means 106 to detect message forgery. The verification means utilizes the message preprocessing means 102 to verify the signature and determine the authenticity of the message. In accordance with this invention, the message processing functions has been worked with three primitives namely RSA-PSS system, PKCS #1 vl.5 system and Message Randomization system to generate secure, robust and tamper proof messages. The three Digital signature schemes are describes as . follows:
DSS 1 using RSA-PSS system: Instead of sending a message directly to RSA-PSS based signature means 104, there is supplied a random message generated by the message preprocessing means 102 and its random value generator, in accordance with this invention, to a hash function of the RSA-PSS primitive system. Then the signature primitive transforms the random message to produce the signed message. Further, the verification primitive means doubly checks the signature using message preprocessing means 102 in order to avoid message forgery.
DSS 2 using PKCS #1 vl.5 system: A random salt value is generated, typically by the random value generator in accordance with this invention, using the message preprocessing means 102 and the generated salt depends on a given input message. Then the salt value is passed into PKCS #1 vl.5 digital signature system based signature means 104 in which the standard encoding means is employed for encoding operation which follows EMSA-. PSS method.
DSS 3 using Message Randomization system: A random value rv, by a random value generator of the message preprocessing means 102 for a given

message is generated. This rv value is used to randomize the message which . is passed into FIPS 180-3 approved digital signature schemes based signature means 104. Message Randomization process using MP is similar to NIST SP 800-106, but the difference occurs in the encoding format of the encoding means.
The aforementioned digital signal primitives such as the RSA-PSS system, the PKCS #1 v 1.5 system, the Message Randomization system are used with the message preprocessing system and functions to provide new, tamper proof corresponding digital signatures, however the proposed system can be worked with any other DSS as well. The three digital signal primitives are described in detail herein below:
1. RSA-PSS digital signature scheme
The steps involved in the RSA-PSS DSS with Message Preprocessing are seen in FIGURE 2. RSA-PSS follows the "hash-then-sign" paradigm. Let M || MP(M) be signed by the RSA-PSS, where MP is the message preprocessing of a message M. A signature is computed on the message M\\ MP(M) in four steps: l. Apply a message preprocessing algorithm MP, by means of the
message preprocessing means,to the message M to produce a value
MP(M);
2. Apply a one-way hash function, by means of the hash functioning means, to the message M \ \ MP(M) to produce a hash value mHash.
3. Use a division means to Divide the message M into recoverable and non-recoverable messages; and

4. Engage an encoding means to Transform the hash value mHash and recoverable message into an encoded message EM.
Apply a signature primitive to the encoded message EM using the private key to produce the signature S. This can be expressed in equation form as S = SigPrim (private key, Transform (Hash (M || MP(M)) recoverable message)), where SigPrim denotes the signature primitive.
With the RSA cryptosystem, this is the classic for S = EMd mod n where (n, d) is the private key, and EM and S are considered as integers.
As seen in Figure 2, the step presented by 200 is the preprocessing message function added in accordance with this invention. This step generates a random message which is further used by this primitive to generate an
encode message.
Assuming that the encoded message can be recovered from the signature, which is the case for described here, the signature is verified in five steps (as shown in FIGURE 3 of the accompanying drawings):
1. Apply a verification means primitive to the signature S to recover the encoded message EM;
2. Find out the message M from recoverable and non-recoverable messages;
3. Apply a message preprocessing algorithm MP, by means of the message preprocessing means, to the message M to produce a value MP(M);

4. Apply a one-way hash function, by means of a hash functioning
means, to M.|| MP(M) to produce a hash value mHash; and
5. Determine whether the encoded message EM is a valid transform of
the hash value mHash and recoverable message.
The step 3 of verification primitive involves the message preprocessing function to produce the random message MP, in accordance with this invention. This is represented by reference numeral 300 of figure 3.
2. PKCS #1 v1.5 digital signature scheme
The steps involved in the PKCS #1 vl.5 DSS with Message Preprocessing are seen in FIGURE 4.
In the PKCS #1 vl.5 signature scheme, a random salt value, by means of a random value generator, is added to the hash value. The proposed signature scheme shows that this random salt is taken to be the hash of message pre processing Hash(MP(M)). Referring to FIGURE 4 of the accompanying drawings, the system is explained as under:
1. Engage a random value generator to Compute a salt = Hash(MP(M)) and mHash = Hash(M);
2. Apply a padding means to Concatenate fixed padding, mHash, and salt to form a string M'
3. Apply the hash function means for hash functioning the string M' to compute a hash value H;
4. Using the padding means to Concatenate fixed padding and the salt value to form a data block DB;

5. Apply the mask generation function, using the mask generation means, to the string M' to compute a mask value dbMask;
6. Use a first computation means for Exclusive-or the mask value dbMask with the data block DB to compute a string mask;and
7. Apply a second computation means to Concatenate maskedDB, the hash value H, and fixed padding to compute the encoded message EM.
To determine whether an encoded message EM is a valid transformation of a given hash value mHash, one simply reverses steps 7 to 4 to recover the salt value and original hash value H, then repeats steps 2 and 3 to see if the hash value is correct. In addition to the hash value one has to verify the salt value supplied by the sender. If the salt value is same, then the verification algorithm is perfect. This method is also known as EMSA-PSS. The step 1
represented by reference numeral 400 of Figure 4 represents the message pre
i ■■
processing function added to this primitive in accordance with the present
. .invention.
3. Randomized Hashing digital signature schemes
The steps involved in the Randomized Hashing with Message Preprocessing are seen in FIGURE 5. The reference numeral 500 of Figure 5 shows the random value generated by the message reprocessing function and is provided to this primitive in accordance with the present invention. Thus, the message preprocessing functions in accordance with the present invention provides a randomized message value which is further given to primitive digital signature schemes to generate tamper proof messages.

To generate a digital signature for a message, the message is hashed by using one of the approved hashing means guided by a hashing algorithm [FIPS 180-3] first, and then signing the resulting hash Value using one of the Approved digital signature means guided by a digital signature algorithm [FIPS 186-3]. The technique specified in this proposed signature scheme depends upon a random variable that could be generated from a message preprocessing function. A random value rv obtained from the message preprocessing of a message is used to randomize the message.
To use the entire random value string without reducing its length an encoded
message string EM is produced as follows:
EM = MP(M) || padding || padding length, where MP(M) is the message
preprocessing of the original message M, padding is a string of zero bits, and
padding_ length is a string of 16 bits that indicates the length of the padding.
When padding is not required (i.e., the length of M plus the length of
padding _length is at least as long as the random value), padding is the
-1 ■•'..-■'
empty string; in this case, padding _length is a string of 16 zero bits. The
i
message preprocessing method is described as follows:
Inputs to message randomization method:
M: an input message
MP(M): the message preprocessing of M
Taking a random bit string rv generated from the message preprocessing function
Output from the message randomization method: MR: a randomized message


...
Three different possibilities of computing rv are as follows:

Random variable (rv) Advantage
rv = Hash(MP(M)) It is a difficult task to
an attacker on finding
H(M')=:H(MP(M)) such
that M'=MP(M) for a
given message M.
rv - Hash ( M || MP(M) It is a hard problem to
) find Hash( M || MP(M)
) - Hash( M' || MP(M))
for different messages
M and M'
rv=MP(M) Output of message pre
processing (MP)
function is random
TECHNICAL ADVANTAGES
The technical advancements of the present invention include providing a system and method for generating secure, more robust, tamper-proof digital signature schemes,
The envisaged system proposes incorporation of 'message preprocessing' as an initial step before processing of'a message by any existing signature primitives for signing. This enables generation of tamper proof signatures and also increases the efficiency of the existing signature primitives.

The. envisaged system increases the security of the messages as the verification of the generated signatures requires the inputs from the message preprocessing stage, thus, preventing forgery.
Additionally, the proposed system is adaptable and can work in conjunction with any of the existing signature systems to enhance the security and
authenticity of a message.
Furthermore, the proposed system involves minimum computational overheads and thus provides a cost effective, adaptable mechanism for creating efficient and reliable Digital Signature Schemes.
The robust, secure and tamper proof digital signatures generated by the present invention find a number of applications in Information Security. Some specific areas such as Multiple signature protocols, Digital Identity, Access Control, Multifactor Authentication and E-voting
While considerable emphasis has been placed herein on the components and component parts of the preferred embodiments, it will be appreciated that many embodiments can be made and that many changes can be made in the preferred embodiments without departing from the principles of the invention. These and other changes in the preferred embodiment as well as other embodiments of the invention will be apparent to those skilled in the art from the disclosure herein, whereby it is to be distinctly understood that the foregoing descriptive matter is to be interpreted merely as illustrative of the invention and not as a limitation. -

WE CLAIM:
1. A system for creation of secure and tamper proof messages using message preprocessing and predetermined signature primitives, said system comprising:
• input means adapted to receive a message which is to be digitally signed;
• message preprocessing means adapted to process said message and further adapted to provide a preprocessed message, said message preprocessing means having:
i. a random value generator adapted to receive said message and further adapted to provide preprocessed message value based on predetermined signature primitive being used and said message;
• signature means adapted to receive said preprocessed message and produce a signed message using said predetermined signature primitives; and.
• verification means adapted to verify said signed message using said message preprocessing means to detect message forgery.
2. The system as claimed in claim 1, wherein said signature unit employs signature primitives selected from the group of primitives consisting of RSA-PSS system, PKCS #1 vl.5 system and Message Randomization system.

3. The system as claimed in claim 1, wherein said preprocessed message value is selected from a group of values consisting of a random message, a random salt value and a random value.
4. A method for creation of secure and tamper proof messages using message preprocessing and predetermined signature primitives, said method comprising the following steps:

• receiving a message which is to be digitally signed;
• generating a random preprocessing message value;
• preparing a preprocessed message using said random preprocessed message value;
• providing said preprocessed message to the pre-determined signature primitive;
• signing the preprocessed message ; and
• verifying the signed message.
5. The method as claimed in claim 4, wherein the step of verifying the
signed message includes the step of verifying the message using a
verification primitive and message preprocessing functions.