US5787178A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Computerized method for signing a message
Assignee: Deutsche Telekom AG
•
Filing: 1996-04-12
•
Granted: 1998-07-28
•
Expires: 2016-04-12
Abstract
Abstract A computerized method for signing a message, where a secret key is used for signing and the signature can be tested with the help of a public key, provides for the public key to be a number n that is the product of two large prime numbers p and q; the secret key includes at least one of the two prime numbers; a polynomial is created in the form P(x)=x k +a k-1 x k-1 + . . . +a 1 x+a 0 , whose coefficients a k-1 . . . a 0 are formed from the message, 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 defined. The zeros are combined into one or more solutions z of the equation P(x) mod n=0, and the random number and the solution z or selected solutions z are added as the signature to the message.
Inventors
- 👤 Joerg Schwenk
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 16:35
CPC Classifications
H; H04; H04L; H04L9/00; H04L9/30; H04L9/3006; H04L9/3026; H04L9/32; H04L9/3247; H04L2209/00; H04L2209/26
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
185 words
A method generating a digital signature and using the Signature to sign an electronic message, wherein a microprocessor uses a secret key for signing and the signature can be tested by an other microprocessor with the help of a public key, the public key being a number n that is the product of two prime numbers p and q, and the secret key including at least one of the two prime numbers p and q, the method comprising the steps of: forming a polynomial of the form P(x)=x k +a k-1 x k-1 + . . . +a 1 x+a 0 , where the coefficients a k-1 . . . a 0 are formed from the message by taking into account a random number, deriving additional polynomials P(x) mod p and P(x) mod q; determining, zeros in respective finite fields GF(p) and GF(q) of the additional polynomials P(x) mod p and P(x) mod q; finding at least one solution z of the equation P(x) mod n=0 by using the zeros; and joining the random number and the at least one solution z to the message.
Claim 2
Independent Claim
185 words
A method generating a digital signature and using the Signature to sign an electronic message, wherein a microprocessor uses a secret key for signing and the signature can be tested by an other microprocessor with the help of a public key, the public key being a number n that is the product of two prime numbers p and q, and the secret key including at least one of the two prime numbers p and q, the method comprising the steps of: forming a polynomial of the form P(x)=x k +a k-1 x k-1 + . . . +a 1 x+a 0 , where the coefficients a k-1 . . . a 0 are formed from the message by taking into account a random number, deriving additional polynomials P(x) mod p and P(x) mod q; determining, zeros in respective finite fields GF(p) and GF(q) of the additional polynomials P(x) mod p and P(x) mod q; finding at least one solution z of the equation P(x) mod n=0 by using the zeros; and joining the random number and the at least one solution z to the message.
Claim 3
Dependent Claim
48 words
The method as recited in claim 1 wherein the steps of forming the polynomial, deriving the additional polynomials and determining the zeros of the additional polynomials are repeated if necessary with another random number until each additional polynomial has at least one zero in its respective finite field.
Claim 4
Dependent Claim
51 words
The method as recited in claim 1 wherein the steps of creating the polynomial, deriving the additional polynomials and determining the zeros of the additional polynomials are repeated if necessary with another random number until both additional polynomials have at least a predetermined number of zeros in the respective finite field.
Claim 5
Dependent Claim
31 words
The method as recited in claim 1 wherein the solution z is calculated from the zeros of the additional polynomials by using an extended Euclidean algorithm and the Chinese Remainder theorem.
Claim 6
Dependent Claim
9 words
The method as recited in claim 1 wherein k>2.
Claim 7
Dependent Claim
11 words
The method as recited in claim 1 wherein log 2 n≈500.
Claim 8
Dependent Claim
31 words
The method as recited in claim 1 further comprising the step of verifying the signed message by determining whether the at least one solution z satisfies the equation P(z) mod n=0.
Claim 9
Dependent Claim
22 words
The method as recited in claim 1 further comprising the step of storing a list of public keys in the other microprocessor.
Claim 10
Dependent Claim
30 words
The method as recited in claim 1 further comprising the steps of storing at least one secret key in the microprocessor and accessing the secret key by entering a password.
Claim 11
Independent Claim
187 words
A method for generating a digital signature and using the signature to sign an electronic message, wherein a microprocessor uses a secret key for signing and the signature can be tested by an other microprocessor with the help of a public key, the public key being a number n that is the product of two prime numbers p and q, and the secret key including at least one of the two prime numbers p and q, the method comprising the steps of: forming a polynomial of the forming P(x)=x k +a k-1 x k-1 + . . . +a 1 x+a 0 , where the coefficients a k-1 . . . a 0 are formed from the message and the coefficient a 0 is a random number, deriving additional polynomials P(x) mod p and P(x) mod q; determining zeros in respective finite fields GF(p) and GF(q) of the polynomials P(x) mod p and P(x) mod q; finding at least one solution z of the equation P(x) mod n=0 by using the zeros; and joining the random number and the at least one solution z to the message.
Claim 12
Independent Claim
187 words
A method for generating a digital signature and using the signature to sign an electronic message, wherein a microprocessor uses a secret key for signing and the signature can be tested by an other microprocessor with the help of a public key, the public key being a number n that is the product of two prime numbers p and q, and the secret key including at least one of the two prime numbers p and q, the method comprising the steps of: forming a polynomial of the forming P(x)=x k +a k-1 x k-1 + . . . +a 1 x+a 0 , where the coefficients a k-1 . . . a 0 are formed from the message and the coefficient a 0 is a random number, deriving additional polynomials P(x) mod p and P(x) mod q; determining zeros in respective finite fields GF(p) and GF(q) of the polynomials P(x) mod p and P(x) mod q; finding at least one solution z of the equation P(x) mod n=0 by using the zeros; and joining the random number and the at least one solution z to the message.
Claim 13
Dependent Claim
26 words
The method as recited in claim 10 wherein the message is divided into blocks forming the individual coefficients a k-1 . . . a 1 .
Claim 14
Dependent Claim
48 words
The method as recited in claim 10 wherein the steps of forming the polynomial, deriving the additional polynomials and determining the zeros of the additional polynomials are repeated if necessary with another random number until each additional polynomial has at least one zero in its respective finite field.
Claim 15
Dependent Claim
51 words
The method as recited in claim 10 wherein the steps of creating the polynomial, deriving the additional polynomials and determining the zeros of the additional polynomials are repeated if necessary with another random number until both additional polynomials have at least a predetermined number of zeros in the respective finite field.
Claim 16
Dependent Claim
31 words
The method as recited in claim 10 wherein the solution z is calculated from the zeros of the additional polynomials by using an extended Euclidean algorithm and the Chinese Remainder theorem.
Claim 17
Dependent Claim
9 words
The method as recited in claim 10 wherein k≧2.
Claim 18
Dependent Claim
11 words
The method as recited in claim 10 wherein log 2 n≈500.
Claim 19
Dependent Claim
32 words
The method as recited in claim 10 further comprising the step of verify in the signed message by determining whether the at least one solution z satisfies the equation P(z) mod n=0.
Claim 20
Dependent Claim
22 words
The method as recited in claim 10 further comprising the step of storing a list of public keys in the other microprocessor.
Claim 21
Dependent Claim
30 words
The method as recited in claim 10 further comprising the steps of storing at least one secret key in the microprocessor and accessing the secret key by entering a password.
Claim 22
Dependent Claim
28 words
The method as recited in claim 1 further comprising the step of transmitting the message and at least one solution z from the microprocessor to the other microprocessor.
References Cited (Backward Citations)
EP0157258A2
Cited
US4625076A
Cited
US5231668A
Cited
US5220606A
Cited
US5442707A
Cited
US5263085A
Cited
US5373561A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-07-27 | 2002-01-26 | 2002-07-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-07-27 | 2006-01-26 | 2006-07-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-07-27 | 2010-01-26 | 2010-07-28 | $7700.00 | Window Closed / Lapsed |