Signed document transmission system

• US 4,625,076 A
• Filed: 03/11/1985
• Issued: 11/25/1986
• Est. Priority Date: 03/19/1984
• Status: Expired due to Term

• Current Assignee: Nippon Telegraph and Telephone Corporation
• Original Assignee: Nippon Telegraph and Telephone Corporation
• Inventors: Miyaguchi, Shoji, Okamoto, Tatsuaki, Shiraishi, Akira, Kawaoka, Tsukasa
• Primary Examiner(s): Cangialosi, Salvatore
• Assistant Examiner(s): Lewis, Aaron J.
• Application Number:
  US06/710,253
• Time in Patent Office: 624 Days
• Field of Search: 178/22.11, 178/22.09, 178/22.08
• US Class Current: 713/176
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3093 involving Lattices or polynomial equations, e.g. NTRU scheme
• CPC Class Codes: H04L 9/3249 using RSA or related signature schemes, e.g. Rabin scheme

Abstract

On the transmitting side, a signature corresponding to a document to be transmitted is generated using a random number and the document as variables and on the basis of a congruent polynomial of second or higher degree with respect to the random number, secret key information and public key information produced based on the secret key information. The signature and the document are transmitted in digital form. On the receiving side, the congruent polynomial is operated using the received signature and document in place of the random number and the document employed on the transmitting side, and the validity of the received signature and document is verified on the basis of the result of the operation and the public key information.

Claims

1. A signed document transmission method comprising the steps of:

determining, on the transmitting side, integer values W and V satisfying

space="preserve" listing-type="equation">Z≦

Wpq+Vε

δ

<

Z+δ

for

space="preserve" listing-type="equation">Z=-g(m)-{f(x, m)(mod n)}

where ε and

δ

are public keys, p and q are secret keys of prime numbers, n is a public key given by n=p² q, x is a random number, m is a document to be transmitted, g(m) is an arbitrary function with respect to m, f(x, m) is a polynomial given by ##EQU19## and f_i (m) is an arbitrary function with respect to m;

generating a signature S as given by S=x+ypq, where y is an integer given by a congruent division y=W/F'"'"'(X,n) (mod p), and f'"'"'(x, m) is a differentiation of f(x, m) with respect to x;

transmitting the document m and the signature S;

obtaining, on the receiving side, a congruent polynomial f(S, m) (mod n) using the signature S in place of x in the polynomial f(x, m), and the document m and the public key n; and

verifying the validity of the received document m and the signature S when ##EQU20## is satisfied, where [A] represents the greatest integer equal to or smaller than A.

4. A signed document transmission system according to claim 1 wherein the public key δ

is selected within a range as given by 1≦

δ

≦

θ

(n^2/3), where θ

(n^2/3) indicates the order of n^2/3.

5. A signed document transmission system according to claim 4 wherein the public key ε

is selected as ε

=θ

(n^1/3), where θ

(n^1/3) indicates the order of n^1/3.

6. A signed document transmission method according to claim 5 wherein the function g(m) is -M, M being the document m hashed by a function h(m);

and the congruence polynomial f(x, m) is f(x).

13. A signed document transmission method according to any one of claims 1, 2, 4, 5, 10, 11 or 12 wherein on the transmitting side the document to be transmitted is subjected to a hashing process to produce a hashed document;

the hashed document is used in place of the document for the generation of the signature;

the signature and the non-hashed document are transmitted;

on the receiving side the received document is subjected to the same hashing process as that used on the transmitting side, to produce a hashed received document; and

the hashed received document is used in place of the received document for verification of the signature.

14. A signed document transmission method according to any one of claims 1, 2, 6, 7 or 10 wherein the secret keys p and q are selected so that p>

q.

15. A signed document transmission method according to any one of claims 1, 2, 6, 7 or 10 wherein the secret keys p and q are selected so that p<

q.

16. A signed document transmission method according to claim 13 wherein the procedure for the signature generation is repeated on the transmitting side until the same condition as that for the signature verification on the receiving side is satisfied.

17. A signed document transmission method according to claim 16 wherein pq-φ

is used as the public key δ

, where φ

is a random number of the order of pq/10.

18. A signed document transmission method according to claim 15 wherein pq+φ

is used as the public key δ

, where φ

is a random number of the order of pq/10.

19. A signed document transmission method according to any one of claims 1, 2, 6, 7 or 10 wherein γ

=θ

(n/T) (where T is a value approximately in the range of 10¹⁰ to 10³⁰) is provided as a public key, and when the received signature S is not between Y and n-γ

on the receiving side, the result of verification is ignored.

20. A signed document transmission method according to any one of claims 1, 2, 7 or 10 wherein the secret keys p and q and the random number x bear the relationship 1≦

x≦

pq-1.

21. A signed document transmission method according to any one of claims 1, 2, 6, 7 or 10 wherein the random number x takes a value greater than pq-1 and the result of x+ypq is subjected to modulus n to obtain the signature S.

22. A signed document transmission method according to any one of claims 1, 2, 6, 7 or 10 wherein the degree α

of the congruence polynomial with respect to the random number x is selected to be a value which meets a condition n^1/α

≅

1.

23. A signed document transmission method according to claim 1 or 2 wherein the public key δ

is given as a power of 2 and the verification on the receiving side is performed by checking whether a predetermined number of consecutive bits are "0" which starts at a predetermined bit position of the binary value of the operation result obtained by the congruent polynomial.

2. A signed document transmission method comprising the steps of:

determining, on the transmitting side, an integer value W in accordance with the expression ##EQU21## where δ

is a public key, p and q are secret keys of prime numbers, n is a public key given by n=p² q, x is a random number, m is a document to be transmitted, g(m) is an arbitrary function with respect to m, f(x, m) is a polynomial given by ##EQU22## and f_i (m) is an arbitrary function with respect to m, and [A] represents the smallest integer equal to or greater than A;

generating a signature S as given by S=x+ypq, where y is an integer given by a congruent division y=W/f'"'"'(x, m) (mod p), and f'"'"'(x, m) is a differentiation of f(x, m) with respect to x;

transmitting the document m and the signature S;

obtaining, on the receiving side, a congruent polynomial f(S, m) (mod n) using the signature S in place of x in the polynomial f(x, m), and the document m and the public key n; and

verifying the validity of the received document m and the signature S when an inequality equivalent to

space="preserve" listing-type="equation">-g(m)≦

f(S, m)(mod n)<

-g(m)+δ

is satisfied.

7. A signed document transmission method according to claim 2 wherein the public key δ

is on the order of n^2/3, the function g(m) is -M, M being the document m hashed by a function h(m), f(x, m)=f(x) and the integer W is given by ##EQU24## [A] indicating the smallest integer equal to or larger than A.

8. A signed document transmission method according to claim 7 wherein on the receiving side, it is checked whether h(m)≦

f(S)(mod n)<

h(m)+δ

or 0≦

-h(m)+{f(S)(mod n)}<

δ

is satisfied or not, and when the condition is satisfied, the received signature and document are verified to be valid.

9. A signed document transmission method according to claim 7 wherein on the receiving side, an operation [-h(m)+{f(S)(mod n)}] is performed and it is checked whether the result of operation is zero or not, and if so, the received signature and document are verified to be valid.

10. A signed document transmission method according to claim 2 wherein the public key δ

is on the order of n^2/3, the function g(m) is -a (where a is an integer in the range of 0≦

a≦

n-δ

), the congruent polynomial f(x, m) is x² +m² and the integer W is given by ##EQU25## [A] indicating the smallest integer equal to or larger than A.

11. A signed document transmission method according to claim 10 wherein on the recieving side, it is checked whether a condition a≦

(S² +m²)(mod n)<

a+δ

or 0≦

-a+{(S² +m²)(mod n)}<

δ

is satisfied, and if it is, the received signature and document are verified to be valid.

12. A signed document transmission method according to claim 10 wherein an operation ##EQU26## is performed and it is checked whether the result of operation is zero, and if it is, the received signature and document are verified to be valid.

3. A signed document transmission method comprising the steps of

determining, on the transmitting side, an integer value W based on g(m) and a congruent polynomial f(x, m) (mod n), where x is an integer random number, m is a document to be transmitted, n is a public key given by n=p² q, p and q are secret keys of prime numbers, g(m) is an arbitrary function with respect to m, f(x, m) is a polynomial given to ##EQU23## is an arbitrary function with respect to m, and I is an integer equal to or greater than 2;

generating a signature S as given by S=x+ypq, where y is a congruent division of W and a differentiation f'"'"'(x, m) of f(x, m) with respect to x;

transmitting the document m and the signature S;

obtaining, on the receiving side, a congruent polynomial f(S, m) (mod n) using the signature S in place of x in the polynomial f(x, m), and the document m and the public key n; and

verifying the validity of the document m and the signature S based on the calculation results of F(S, m) (mod n) and g(m).

24. A signed document transmission system comprising:

a p-setting register for setting a secret key p (a prime number);

a q-setting register for setting a secret key q (a prime number);

a first multiplier for multiplying the outputs p and q of the p- and the q-setting registers to obtain pq;

an n-generator for providing a public key n=p² q obtained by an operation based on the outputs p and q of the p- and the q-setting registers;

a first hash processor for hashing a document m to be transmitted to obtain a hashed document M;

a random number generator for generating a random number x;

a first congruent polynomial operating unit for performing a modulo-n operation of a polynomial f(x) of second or higher degree using the random number x as a variable;

a subtractor for obtaining the difference between the output of the first congruent polynomial operating unit and the hashed document M from the first hash processor;

a divider for dividing the output of the subtractor by the output pq from the first multiplier;

a round-up operating unit for obtaining the smallest integer equal to or larger than the output value of the divider;

a second congruent polynomial operating unit supplied with the random number x from the random number generator, for performing a modulo-n operation of a differential value of the polynomial f(x);

a congruent divider for dividing the output W of the round-up operating unit, to modulus p, by the output of the second congruent polynomial operating unit;

a second multiplier for multiplying the output y of the congruent divider and the output pq of the first multiplier;

an adder for adding together the output ypq of the second multiplier and the random number from the random number generator to obtain their sum as a signature S;

means for transmitting the signature S and the document m;

means for receiving the transmitted signature S and document m;

an n-setting register for setting the public key n;

a δ

-setting register for setting a public key δ

of the order of n^2/3 ;

a third congruent polynomial operating unit for performing a modulo-n operation of the polynomial f(x) using the received signature S instead of the random number;

a second hash processor for hashing the received document by the same method as that used by the first hash processor to obtain hashed data M; and

a comparator supplied with the result of the operation f(S)(mod n) from the third congruent polynomial operating unit, the hashed data M from the second hash processor and the output δ

from the δ

-setting register, for deciding whether they meet a condition M≦

f(x)(mod n)<

M+δ and

, when it is satisfied, producing information to that effect.

25. A signed document transmission system comprising:

a p-setting register for setting a secret key p (a prime number);

a q-setting register for setting a secret key q (a prime number);

a first multiplier for multiplying the outputs p and q from the p- and the q-setting registers to obtain pq;

an n-generator for generating a public key n=p² q obtained by an operation based on the outputs p and q from the p- and the q-setting registers;

a first hash processor for obtaining a hashed document M by hashing a document m to be transmitted;

a random number generator for generating a random number x;

a first congruent polynomial operating unit for performing a modulo-n operation of a polynomial f(x)(mod n) of second or higher degree using the random number x as a variable;

a subtractor for obtaining the difference between the output of the first congruent polynomial operating unit and the hashed document M from the first hash processor;

a first ε

-setting register for setting a public key ε

of the order of n^1/3 ;

a first δ

-setting register for setting a public key δ

of the order between 1 and n^1/3 ;

a W-operating unit supplied with the output Z of the subtractor, the output pq of the first multiplier, the output ε

of the first ε

-setting register and the output δ

of the first δ

-setting register, for obtaining W which meets the following conditions

space="preserve" listing-type="equation">Z≦

Wpq+Vε

δ

<

Z+δ

space="preserve" listing-type="equation">Z=-g(m)-{f(x)(mod n)};

a round-up operating unit for obtaining the smallest integer equal to or larger than the output value of the W-operating unit;

a second congruent polynomial operating unit supplied with the random number x from the random number generator, for performing a modulo-p operation of a differential value of the polynomial f(x);

a congruent divider for dividing the output W of the W-operating unit by the output of the second congruent polynomial operating unit to modulus p;

a second multiplier for multiplying the output y of the congruent divider and the output pq of the first multiplier;

an adder for adding together the output ypq of the second multiplier and the random number x from the random number generator to obtain a signature S;

means for transmitting the signature S and the document m;

means for receiving the transmitted signature S and document m;

an n-setting register for setting the public key n;

a second ε

-setting register for setting the public key ε

;

a second δ

-setting register for setting the public key δ

;

a third congruent polynomial operating unit for performing a modulo-n operation of the polynomial f(X) using the received signature S instead of the random number x;

a second hash processor for hashing the received document by the same method as that used by the first hash processor to obtain hashed data M;

a second subtractor for obtaining the difference, f(S)(mod n)-M, between the output M of the second hash processor and the output f(S)(mod n) of the third congruent polynomial operating unit;

a divider for dividing the output of the second subtractor by the output δ

of the second δ

-setting register;

a round-up operating unit for obtaining the smallest integer equal to or larger than the output of the divider;

a residue operating unit for performing a modulo-ε

operation of the output of the round-up operating unit by the output ε

of the second ε

-setting register; and

a circuit for deciding whether the output of the residue operating unit is zero or not and for outputting the decision result.