Nova Patents
EP0157258B1

Signed document transmission system

Abstract

This record has no abstract on file.

EP0157258B1, drawing sheet 1
Sheet 1 of 117

Term

Term ended

Expired 15 March 2005, 21.5 years ago.

  1. Priority
  2. Filed
  3. Granted
  4. Expired
  5. Today

32 claims: 19 independent, 13 dependent

  1. 1
    A signed document transmission method comprising the steps of:determining, on the transmitting side, integer values W and V satisfying where E and 6 are public keys, p and q are secret keys of prime numbers, n is a public key given by n = p 2 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 where l ≧ 2 and f ;(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 is satisfied, where represents the greatest integer equal to or smaller than A.
  2. 2
    A signed document transmission method comprising the steps of:determining, on the transmitting side, an integer value W in accordance with the expression where p and q are secret keys of prime numbers, n is a public key given by n = p 2 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 where l ≧ 2 and f ;(m) is an arbitrary function with respect to m, and 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 -g(m) ≦ f(S, m) (mod n) -g(m) + δ is satisfied, where 6 is a public key.
  3. 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 2 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 f i (m) is an arbitrary function with respect to m, and l 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).
  4. 13
    A signed document transmission method according to any one of claims 1, 2, 4, 5, 10, 11 or 12, wherein hashed document to be transmitted is used for the generation of the signature, the signature and the non-hashed document are transmitted and the received document is similarly hashed for verification on the receiving side.
  5. 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.
  6. 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.
  7. 19
    A signed document transmission method according to any one of claims 1, 2, 6, 7 or 10, wherein γ = 8(n/T) (where T is a value approximately in the range of 10 10 to 10 30 ) is provided as a public key, and when the received signature S is not between γ and n - γ on the receiving side, the result of verification is ignored.
  8. 20
    A signed document transmission method according to any one of claims 1, 2, 6, 7 or 10, wherein the secret keys p and q and the random number x bear the relationship 1 ≦ x ≦ pq - 1.
  9. 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 1 ≦ x ≦ pq - 1 and the result of x + ypq is subjected to modulus n to obtain the signature S.
  10. 22
    A signed document transmission method according to any one of claims 1, 2, 6, 7 or 10, wherein the degree a of the congruent polynomial with respect to the random number x is selected to be a value which meets a condition n 1/α ≈ 1.
  11. 24
    A signed document transmission system comprising:a p-setting register (11) for setting a secret key p (a prime number);a q-setting register (12) for setting a secret key q (a prime number);a first multiplier (14) for multiplying the outputs p and q of the p- and the q-setting registers to obtain pq;an n-generator (13) for providing a public key n = p 2 q obtained by an operation based on the outputs p and q of the p- and the q-setting registers;a first hash processor (45) for hashing a document m to be transmitted to obtain a hashed document M;a random number generator (17) for generating a random number x;a first congruent polynomial operating unit (44) 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 (22) 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 (23) for dividing the output of the subtractor by the output pq from the first multiplier;a round-up operating unit (24) for obtaining the smallest integer equal to or larger than the output value of the divider;a second congruent polynomial operating unit (46) supplied with the random number x from the random number generator (17), for performing a modulo-n operation of a differential value of the polynomial f(x);a congruent divider (47) 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 (28) for multiplying the output y of the congruent divider and the output pq of the first multiplier;and adder (29) 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 (32) for setting the public key n;a 6-setting register (33) for setting a public key 6 of the order of n 2/3 ;a third congruent polynomial operating unit (48) 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 (49) 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 (41) supplied with the result of the operation f(S) (mod n) from the third congruent polynomial operating unit (48), the hashed data M from the second hash processor and the output 6 from the δ-setting register, for deciding whether they meet a condition M f(x) (mod n) M + 6 and, when it is satisfied, producing information to that effect.
  12. 25
    A signed document transmission system comprising:a p-setting register (11) for setting a secret key p (a prime number);a q-setting register (12) for setting a secret key q (a prime number);a first multiplier (14) for multiplying the outputs p and q from the p- and the q-setting registers to obtain pq;an n-generator (13) for generating a public key n = p 2 q obtained by an operation based on the outputs p and q from the p- and the q-setting registers;a first hash processor (45) for obtaining a hashed document M by hashing a document m to be transmitted;a random number generator (17) for generating a random number x;a first congruent polynomial operating unit (44) 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 (22) 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 (52) for setting a public key ∈ of the order of n 1/3 ;a first δ-setting register (53) for setting a public key δ of the order between 1 and n 1/3 ;a W-operating unit (51) 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 a second congruent polynomial operating unit (46) 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 (47) 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 (28) for multiplying the output y of the congruent divider and the output pq of the first multiplier;an adder (29) 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 (32) for setting the public key n;a second E -setting register (56) for setting the public key E ;a second δ-setting register (33) for setting the public key δ;
  13. 26
    a third congruent polynomial operating unit (48) for performing a modulo-n operation of the polynomial f(x) using the received signature S instead of the random number x;
  14. 27
    a second hash processor (49) for hashing the received document by the same method as that used by the first hash processor to obtain hashed data M;
  15. 28
    a second subtractor (52) 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;
  16. 29
    a divider (53) for dividing the output of the second subtractor by the output δ of the second δ-setting register;
  17. 30
    a round-down operating unit (54) for obtaining the largest integer equal to or smaller than the output of the divider;
  18. 31
    a residue operating unit (55) for performing a modulo- E operation of the output of the round-up operating unit by the output ∈ of the second ∈-setting register;and
  19. 32
    a circuit (57) for deciding whether the output of the residue operating unit is zero or not and for outputting the decision result.
Independent claims19