Signed document transmission system

Claim 2

A signed document transmission system comprising the processes of: generating, on the transmitting side, a signature corresponding to a document to be transmitted using a random number and the document as variables and on the basis of a congruence polynomial of second or higher order with respect to the random number, secret key information and public key information prepared based on the secret key information; transmitting the signature along with the document; and verifying, on the receiving side, the validity of the received document and signature on the basis of the result of operation of the congruence polynomial performed using the received signature and document in place of the random number and the document used on the transmitting side and the public key information based on the secret key information.

Claim 3

A signed document transmission system according to claim 1 wherein the secret key information includes two secret keys of prime numbers p and q; the public key information includes a public key n = p 2 q; the operation of the congruence polynomial is a modulo-n operation; and the public key information further includes a public key 6 defined as 1 6 δ ≦ θ(n 2/3 ), where θ(n 2/3 ) indicates the order of n 2 / 3 .

Claim 4

A signed document transmission system according to claim 2 wherein the public key information further includes a public key ε = θ(n 1/3 ); an integer W is obtained which meets the following conditions:

Claim 5

where m is the document to be transmitted, g(m) is an arbitrary function with respect to m and where I ≧ 2, f i (m) is an arbitrary function with respect to m, x is the random number and f(x, m) is the congruence polynomial; the integer W is subjected to a modulo-p division by a differentiation value f'(x, m) with respect to x in f(x, m); and letting the result of division be represented by y, the signature S is obtained in the form of x + ypq.

Claim 6

where m is the document to be transmitted, g(m) is an arbitrary function with respect to m and where I ≧ 2, f i (m) is an arbitrary function with respect to m, x is the random number and f(x, m) is the congruence polynomial; the integer W is subjected to a modulo-p division by a differentiation value f'(x, m) with respect to x in f(x, m); and letting the result of division be represented by y, the signature S is obtained in the form of x + ypq.

Claim 7

A signed document transmission system according to claim 3 wherein on the receiving side, when the modulo -c residue of is zero, the received signature and document are verified to be valid, └A┘ indicating the greatest integer equal to or smaller than A.

Claim 8

A signed document transmission system according to claim 4 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).

Claim 9

A signed document transmission system according to claim 3 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 └A┘ indicating the smallest integer equal to or larger than A.

Claim 10

A signed document transmission system according to claim 6 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)} < 6 is satisfied or not, and when the condition is satisfied, the received signature and document are verified to be valid.

Claim 11

A signed document transmission system according to claim 6 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.

Claim 12

A signed document transmission system according to claim 3 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 - 6), the congruence polynomial f(x, m) is x 2 + m 2 and the integer W is given by └A┘ indicating the smallest integer equal to or larger than A.

Claim 13

A signed document transmission system according to claim 9 wherein on the receiving side, it is checked whether a condition a ≦ (S 2 + m 2 )(mod n) < a + δ or 0 ≦ -a + {(S 2 + m 2 )(mod n)} < δ is satisfied or not, and if so, the received signature and document are verified to be valid.

Claim 14

A signed document transmission system according to claim 9 wherein an operation 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.

Claim 15

A signed document transmission system according to any one of claims 1 to 4 and 7 to 11 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.

Claim 16

A signed document transmission system according to any one of claims 2, 3, 5, 6 and 9 wherein the secret keys p and q are selected so that p > q.

Claim 17

A signed document transmission system according to any one of claims 2, 3, 5, 6 and 9 wherein the secret keys p and q are selected so that p < q.

Claim 18

A signed document transmission system according to claim 14 wherein the procedure for the signature generation is repeated on the transmitting side until the condition for the signature verification on the receiving side is satisfied.

Claim 19

A signed document transmission system according to claim 15 wherein pq - Ø is used as the public key 6, where ø is a random number of the order of pq/10.

Claim 20

A signed document transmission system according to claim 14 wherein pq + Ø is used as the public key 6, where Ø is a random number of the order of pq/10.

Claim 21

A signed document transmission system according to claim 14 wherein y = 6(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 y and n - y on the receiving side, the result of verification is ignored.

Claim 22

A signed document transmission system according to any one of claims 2, 4, 7, 8, 10 and 11 wherein y = 0(n/T) (where T is a value approximately in the range of 10 10 to 1030) is provided as a public key, and when the received signature S is not between y and n - y on the receiving side, the result of verification is ignored.

Claim 23

A signed document transmission system according to any one of claims 2, 5, 6 and 9 wherein the secret keys p and q and the random number x bear such a relationship as 1 ≦ x S pq - 1.

Claim 24

A signed document transmission system according to any one of claims 5, 6 and 9 wherein the random number x takes a value smaller than 1 ≦ x ≦ pq - 1 and the operation x + ypq is performed to modulus n to obtain the signature S.

Claim 25

A signed document transmission system according to any one of claims 2, 5, 6 and 9 wherein the degree a of the congruence polynomial with respect to the random number x is selected to be a value which meets a condition n 1/α < 1.

Claim 26

A signed document transmission system according to claim 1 or 3 wherein the public key information 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 congruence polynomial.

Claim 27

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 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 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 congruence polynomial operating unit for performing a modulo-n operation of a congruence 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 congruence 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 congruence 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 congruence 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 congruence 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 6-setting register for setting a public key δ of the order of n 2/3 ; a third congruence polynomial operating unit for performing a modulo-n operation of the congruence 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 by the first hash processor to obtain hashed data M; and comparator supplied with the result of operation f(S)(mod n) from the third congruence polynomial operating unit, the hashed data M from the second hash processor and the output δ from the 6-setting register, for deciding whether they meet a condition M S f(x)(mod n) < M + δ and, when it is satisfied, producing information to that effect.

Claim 28

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 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 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 congruence polynomial operating unit for performing a modulo-n operation of a congruence 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 congruence 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 congruence 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 congruence 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 congruence 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 6-setting register for setting a public key δ of the order of n 2/3 ; a third congruence polynomial operating unit for performing a modulo-n operation of the congruence 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 by the first hash processor to obtain hashed data M; and comparator supplied with the result of operation f(S)(mod n) from the third congruence polynomial operating unit, the hashed data M from the second hash processor and the output δ from the 6-setting register, for deciding whether they meet a condition M S f(x)(mod n) < M + δ and, when it is satisfied, producing information to that effect.

Claim 29

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 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 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 congruence polynomial operating unit for performing a modulo-n operation of a congruence 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 congruence 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 6-setting register for setting a public key 6 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 6 of the first 6-setting register, for obtaining W which meets the following conditions: 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 congruence 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 congruence polynomial f(x); a congruent divider for dividing the output W of the W-operating unit by the output of the second congruence 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 e-setting register for setting the public key e; a second 6-setting register for setting the public key 6; a third congruence polynomial operating unit for performing a modulo-n operation of the congruence 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 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 congruence polynomial operating unit; a divider for dividing the output of the second subtractor by the output 6 of the second 6-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- E operation of the output of the round-up operating unit by the output ε of the second ε-setting register; and a deciding circuit for deciding whether the output of the residue operating unit is zero or not and for outputting the decision result.

Claim 30

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 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 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 congruence polynomial operating unit for performing a modulo-n operation of a congruence 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 congruence 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 6-setting register for setting a public key 6 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 6 of the first 6-setting register, for obtaining W which meets the following conditions: 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 congruence 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 congruence polynomial f(x); a congruent divider for dividing the output W of the W-operating unit by the output of the second congruence 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 e-setting register for setting the public key e; a second 6-setting register for setting the public key 6; a third congruence polynomial operating unit for performing a modulo-n operation of the congruence 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 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 congruence polynomial operating unit; a divider for dividing the output of the second subtractor by the output 6 of the second 6-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- E operation of the output of the round-up operating unit by the output ε of the second ε-setting register; and a deciding circuit for deciding whether the output of the residue operating unit is zero or not and for outputting the decision result.