Computerized Method for Signing a Message

The present invention concerns a process for electronically signing a digitized message, wherein a secret key is used for signing and the signature can be tested with a public key.

The general principle of a signature method is described, for example, in IEEE Transactions on Information Theory, vol. IT-22, November 1976, pages 644 to 654. A concrete embodiment of this principle--also known as the RSA method--was described for the first time in Communications of the ACM, vol. 27, no. 27, February 1978, pages 120 to 126. Using the secret key, a signature is generated for the data set transmitted, whereupon each individual receiver can then use the public key to test the authenticity and origin of this signature.

The known RSA method is based on the mathematical problem of factoring such numbers, in other words, determining the factors of the numbers.

The object of this invention is to enable practical implementation of the signature and its verification in the simplest possible manner and at a high speed.

This object is achieved according to this invention by

providing a public key as a number n that is the product of two large prime numbers p and q,

providing a secret key including at least one of the two prime numbers,

forming a polynomial of the form P(x)=x.sup.k +a.sub.k-1 x.sup.k-1 + . . . +a.sub.1 x+a.sub.0 whose coefficients a.sub.k-1 . . . a.sub.0 are formed from the message by taking into account a random number,

this polynomial is used to derive additional polynomials P(x) mod p and P(x) mod q whose zeros in the respective finite fields GF(p) and GF(q) are determined,

combining the zeros to form one or more solutions z of the equation P(x) mod n=0 and

adding the random number and the solution z or selected solutions z to the message as the signature.

In the event no zeros can be found in the respective finite field for one or both of the additional polynomials, a refinement provides for the steps of creating the polynomial, deriving the additional polynomials and determining the zeros of the additional polynomials to be repeated with another random number if necessary until both of the zeros thus determined are in the respective finite field.

A very high degree of security is achieved especially when each of the two additional polynomials has at least two different zeros in the respective finite field. For this reason another refinement of the method according to this invention provides for the creation of the polynomial, the derivation of the additional polynomials and the determination of the zeros of the additional polynomials to be repeated if necessary with another random number until both additional polynomials have at least a given number of zeros in the respective finite field.

If the zeros of P(x) mod p are d.sub.1 and d.sub.2 and those of P(x) mod q are e.sub.1 and e.sub.2, the signature of the message will include the random number plus the two numbers .alpha..multidot.p.multidot.e.sub.1 +.beta..multidot.q.multidot.d.sub.1 and .alpha..multidot.p.multidot.e.sub.2 +.beta..multidot.q.multidot.d.sub.2, where .alpha..multidot.p+.beta..multidot.q=1 is a multiple sum representation of the number 1 that can be calculated with the help of an extended Euclidean algorithm.

A method of forming coefficients that is especially advantageous when the calculations are repeated with different random numbers is achieved with another refinement of this invention where the coefficient a.sub.0 is formed by the random number and the other coefficients of the polynomial are derived from the message using certain steps. The other coefficients can be formed, for example, by the fact that the certain steps include dividing the message into blocks and assigning the blocks to the individual coefficients.

An advantageous embodiment of the process according to this invention includes calculating the solution z from the zeros of the additional polynomials by using the extended Euclidean algorithm and the Chinese Remainder theorem.

This method is secure when k.gtoreq.2. The number n should be as large as possible for security reasons. A compromise between security and extensive computation that is favorable with regard to the current requirements is obtained with log.sub.2 n.apprxeq.500.

A quick and simple test of the signature created with the method according to this invention is possible by determining whether the number P(z) mod n is equal to zero. With several zeros per each additional polynomial, the signature can be tested by determining whether each of the numbers P(z) mod n is equal to zero.

An advantageous terminal for a telecommunications network includes providing a program containing the steps necessary for the process according to this invention which are executed by a computer.

In one embodiment of the terminal according to this invention, operation in receiving a signed message is facilitated by the fact that a list of the public keys belonging to the given senders of messages can be stored.

Another embodiment of the terminal according to this invention makes it easy to sign a message that is to be sent by providing one or more secret keys that can be stored and retrieved by entering a password and then used for a message to be sent.

The method according to this invention may be applied in a variety of ways, for example, to legal and contract texts or any messages in business and official communications that result in legal liability and therefore must also be signed by hand in conventional written communications. Such text documents can be interpreted as a binary number with the value m. The integer n to be used as the public key is the product of two large prime numbers p and q. At least one of these is known, but only to the sender.

The following figures are provided:

FIG. 1 shows a flowchart of the method of the present invention.

In a preferred embodiment of this invention, in order to sign a message m, it is broken down into blocks a.sub.k-1, . . . , a.sub.1 to the extent that the blocks are interpreted as numbers smaller than n. As shown in FIG. 1, a random number a.sub.0 is selected at step 102 for signing the message m, and the polynomial P(x)=x.sup.k +a.sub.k-1 x.sup.k-1 + . . . +a.sub.1 x +a.sub.0 is formed at step 104 and from it are derived the polynomials P(x) mod p and P(x) mod q which are tested for the zeros in the finite fields GF(p) and GF(q) at step 106. For example, this can be accomplished with the help of the probabilistic algorithm described by Ben-Or: "Probabilistic algorithms in finite fields," Proc. IEEE FOCS 1981, pages 394-398. With a probability of more than 1/2 at least one solution is obtained that can be combined, with a probability of more than 1/4, using the Chinese Remainder theorem, to find at least one solution z of the equation P(x) mod n=0, as shown at step 108. The signature of the message m then includes the random number a.sub.0 and the number z with the property P(z) mod n=0, as shown at step 110.

To test the signature, the polynomial P(x) is formed in the same way as in signing, although the number a.sub.0 is derived from the signature. Then the signature is tested with the number z from the signature to determine whether the equation P(z) mod n=0 is satisfied. The security of the process according to this invention is comparable to that of the RSA method. If each of the two additional polynomials has at least two different zeros, the process can be modified so that its security is equivalent to the difficulty of factoring the number n. A person seeking to forge the signature must find a solution to the equation P(x) mod n=0, or could also factor the number n with a probabilistic method.

The method according to this invention is described below on the basis of a numerical example, where the numbers selected are small for the sake of simplicity. It is assumed that the two prime numbers are p=1237 and q=5683, so the public key is n=7029871.

To sign the message m=12345673891012, the message is divided into two blocks a.sub.2 =1234567 and a.sub.1 =3891012. Choosing a random number in FIG. 1, yields a.sub.0 =2473865, so the following polynomial can be formed block 104:

from which the following two polynomials can be derived:

and

Each of these polynomials has exactly one solution:

With the extended Euclidean algorithm, this yields:

With the help of this representation, a zero z of the equation P(x) mod n=0 can be constructed by calculating the number -2683.multidot.p.multidot.z.sub.q +584.multidot.q.multidot.z.sub.p mod n=5519314 with the help of the Chinese Remainder theorem. The signed message is then:

The verification of the signature by a receiver is performed after reconstructing the polynomial P(x) with the help of the first two components of the signed message. For x=5519314 and n=7029871, this polynomial is then calculated as follows and compared with 0:

The above described signature method may be performed by a sending microprocessor of a terminal and the verification by a receiving microprocessor of a terminal. In addition, the Chinese remainder theorem calculations could, be performed not only by the sending microprocessor itself, but also by a special apparatus associated with the sending microprocessor, for example that described in U.S. Pat. No. 4,709,345, which is hereby expressly incorporated by reference herein. Commonly-assinged U.S. Patent application Ser. No. 08/630,701, filed on Apr. 12, 1996, is hereby expressly incorporated by reference herein.