Secret communication and authentication scheme based on public key cryptosystem using N-adic expansion

Claim 2

The method of claim 1, further comprising the step of: forming the plaintext at the sender side by placing a random number of a bit length similar to that of the first public key n at a top of plaintext data.

Claim 3

An encryption method for generating a ciphertext corresponding to a plaintext based on an n-adic public key cryptosystem using a first secret key formed by two prime numbers p and q, a second secret key d, a first public key n = pq , a second public key e, and a number of partial blocks k which is an integer greater than or equal to 2, the method comprising the steps of: dividing the plaintext into k plaintext blocks of a block size within a range of a residue class of n; forming a k-digit n-adic number by sequentially coupling the plaintext blocks so that different digits of the n-adic number correspond to different plaintext blocks; and obtaining the ciphertext as an e-th power of the n-adic number in modulo n k .

Claim 4

An article of manufacture, comprising: a computer usable medium having computer readable program code means embodied therein for causing a computer to function as an encryption device for generating a ciphertext corresponding to a plaintext based on an n-adic public key cryptosystem using a first secret key formed by two prime numbers p and q, a second secret key d, a first public key n = pq , a second public key e, and a number of partial blocks k which is an integer greater than or equal to 2, the computer readable program code means including: first computer readable program code means for causing said computer to divide the plaintext into k plaintext blocks of a block size within a range of a residue class of n; second computer readable program code means for causing said computer to form a k-digit n-adic number by sequentially coupling the plaintext blocks so that different digits of the n-adic number correspond to different plaintext blocks; and third computer readable program code means for causing said computer to obtain the ciphertext as an e-th power of the n-adic number in modulo n k .

Claim 5

An encryption device for generating a ciphertext corresponding to a plaintext based on an n-adic public key cryptosystem using a first secret key formed by two prime numbers p and q, a second secret key d, a first public key n = pq , a second public key e, and a number of partial blocks k which is an integer greater than or equal to 2, the device comprising: a plaintext division unit for dividing the plaintext into k plaintext blocks of a block size within a range of a residue class of n; a data coupling unit for forming a k-digit n-adic number by sequentially coupling the plaintext blocks so that different digits of the n-adic number correspond to different plaintext blocks; and an encryption unit for obtaining the ciphertext as an e-th power of the n-adic number in modulo n k .

Claim 6

A decryption method for recovering a plaintext corresponding to a ciphertext based on an n-adic public key cryptosystem using a first secret key formed by two prime numbers p and q, a second secret key d, a first public key n = pq , a second public key e, and a number of partial blocks k which is an integer greater than or equal to 2, the method comprising the steps of: obtaining a lowest digit M ⊘ of an n-adic number expressing the plaintext, by calculating a d-th power of the ciphertext in modulo n; sequentially obtaining upper digits M i (1 ≤ i ≤ k-1) of the n-adic number by solving linear modular equations based on the lowest digit M ⊘ of the n-adic number in modulo n; and recovering the plaintext by sequentially concatenating the lowest digit M ⊘ and the upper digits M i of the n-adic number.

Claim 7

The method of claim 6, wherein at the sequentially obtaining step, the ciphertext is taken to be in a form of an e-th power Of the n-adic number in which different digits of the n-adic number correspond to different plaintext blocks dividing the plaintext, and the e-th power of the n-adic number is expanded into a form of a (k-1)-th degree polynomial of n where coefficients of the (k-1)-th degree polynomial are expressed as polynomial functions with the plaintext blocks as variables, and the sequentially obtaining step further includes the steps of: sequentially calculating values of the coefficients from a lower degree coefficient to a higher degree coefficient, according to the ciphertext and already obtained lower digits of the n-adic number; and sequentially determining the upper digits of the n-adic number by solving the linear modular equations in modulo n, using calculated values of the coefficients.

Claim 8

The method of claim 7, wherein the calculated values of the coefficients are stored in a coefficient table, and the sequentially determining step refers to the calculated values of the coefficients as stored in the coefficient table.

Claim 9

The method of claim 6, wherein the sequentially obtaining step sequentially obtains the upper digits M 1 to M k-1 recursively by using an identical mapping or formula for obtaining each M i from M ⊘ to M i-1 by solving a linear modular equation in modulo n, using the lowest digit M ⊘ , the first public key n, the second public key e, the ciphertext C and the number of partial blocks k as inputs.

Claim 10

An article of manufacture, comprising: a computer usable medium having computer readable program code means embodied therein for causing a computer to function as a decryption device for recovering a plaintext corresponding to a ciphertext based on an n-adic public key cryptosystem using a first secret key formed by two prime numbers p and q, a second secret key d, a first public key n = pq , a second public key e, and a number of partial blocks k which is an integer greater than or equal to 2, the computer readable program code means including: first computer readable program code means for causing said computer to obtain a lowest digit M ⊘ of an n-adic number expressing the plaintext, by calculating a d-th power of the ciphertext in modulo n; second computer readable program code means for causing said computer to sequentially obtain upper digits M i (1 ≤ i ≤ k-1) of the n-adic number by solving linear modular equations based on the lowest digit M ⊘ of the n-adic number in modulo n; and third computer readable program code means for causing said computer to recover the plaintext by sequentially concatenating the lowest digit M ⊘ and the upper digits M i of the n-adic number.

Claim 11

A decryption device for recovering a plaintext corresponding to a ciphertext based on an n-adic public key cryptosystem using a first secret key formed by two prime numbers p and q, a second secret key d, a first public key n = pq , a second public key e, and a number of partial blocks k which is an integer greater than or equal to 2, the device comprising: a lowest digit decryption unit for obtaining a lowest digit M ⊘ of an n-adic number expressing the plaintext, by calculating a d-th power of the ciphertext in modulo n; an upper digit decryption unit for sequentially obtaining upper digits M i (1 ≤ i ≤ k-1) of the n-adic number by solving linear modular equations based on the lowest digit M ⊘ of the n-adic number in modulo n; and a data concatenation unit for recovering the plaintext by sequentially concatenating the lowest digit M ⊘ and the upper digits M i of the n-adic number.

Claim 12

The device of claim 11, wherein at the upper digit decryption unit, the ciphertext is taken to be in a form of an e-th power of the n-adic number in which different digits of the n-adic number correspond to different plaintext blocks dividing the plaintext, and the e-th power of the n-adic number is expanded into a form of a (k-1)-th degree polynomial of n where coefficients of the (k-1)-th degree polynomial are expressed as polynomial functions with the plaintext blocks as variables, and the upper digit decryption unit further includes: a coefficient calculation unit for sequentially calculating values of the coefficients from a lower degree coefficient to a higher degree coefficient, according to the ciphertext and already obtained lower digits of the n-adic number; and an upper digit calculation unit for sequentially determining the upper digits of the n-adic number by solving the linear modular equations in modulo n, using calculated values of the coefficients.

Claim 13

The device of claim 12, wherein the coefficient calculation unit further includes a coefficient table for storing the calculated values of the coefficients, and the upper digit calculation unit refers to the calculated values of the coefficients as stored in the coefficient table.

Claim 14

The device of claim 11, wherein the upper digit decryption unit sequentially obtains the upper digits M 1 to M k-1 recursively by using an identical mapping or formula for obtaining each M i from M ⊘ to M i-1 by solving a linear modular equation in modulo n, using the lowest digit M ⊘ , the first public key n, the second public key e, the ciphertext C and the number of partial blocks k as inputs.

Claim 15

An authentication method based on an n-adic public key cryptosystem using a first secret key formed by two prime numbers p and q, a second secret key d, a first public key n = pq , a second public key e, and a number of partial blocks k which is an integer greater than or equal to 2, the method comprising the steps of: generating an authenticator h(M) from an authentication message M at an authentication message generating side; generating a lowest digit h(C) ⊘ of an encrypted n-adic authenticator h(C) by applying a calculation using the first public key n and the second secret key d to the authenticator h(M) at the authentication message generating side; sequentially generating upper digits h(C) i (1 ≤ i ≤ k-1) of the encrypted n-adic authenticator h(C) by using the lowest digit h(C) ⊘ at the authentication message generating side; generating an encrypted authenticator by sequentially concatenating the lowest digit h(C) ⊘ and the upper digits h(C) i of the encrypted n-adic authenticator h(C) at the authentication message generating side; transmitting the encrypted authenticator and the authentication message M from the authentication message generating side to an authentication message verifying side; obtaining a decrypted authenticator by applying a calculation using the first public key n and the second public key e to the encrypted n-adic authenticator h(C) obtained from the encrypted authenticator at the authentication message verifying side; and verifying an authenticity of the authentication message M by using the decrypted authenticator and the authentication message M at the authentication message verifying side.

Claim 16

An authentication message generation method for generating an encrypted authenticator corresponding to an authenticator h(M) based on an n-adic public key cryptosystem using a first secret key formed by two prime numbers p and q, a second secret key d, a first public key n = pq , a second public key e, and a number of partial blocks k which is an integer greater than or equal to 2, the method comprising the steps of: generating a lowest digit h(C) ⊘ of an encrypted n-adic authenticator h(C) as a d-th power of the authenticator h(M) in modulo n; sequentially obtaining upper digits h(C) i (1 ≤ i ≤ k-1) of the encrypted n-adic authenticator h(C) by solving linear modular equations based on the lowest digit h(C) ⊘ of the encrypted n-adic authenticator h(C) in modulo n; and generating the encrypted authenticator by sequentially concatenating the lowest digit h(C) ⊘ and the upper digits h(C) i of the encrypted n-adic authenticator h(C).

Claim 17

The method of claim 16, wherein at the sequentially obtaining step, the authenticator h(M) is taken to be in a form of an e-th power of the encrypted n-adic authenticator h(C) in which different digits of the encrypted n-adic authenticator h(C) correspond to different authenticator blocks dividing the encrypted authenticator, and the e-th power of the encrypted n-adic authenticator h(C) is expanded into a form of a (k-1)-th degree polynomial of n where coefficients of the (k-1)-th degree polynomial are expressed as polynomial functions with the authenticator blocks as variables, and the sequentially obtaining step further includes the steps of: sequentially calculating values of the coefficients from a lower degree coefficient to a higher degree coefficient, according to the authenticator h(M) and already obtained lower digits of the encrypted n-adic authenticator h(C); and sequentially determining the upper digits of the encrypted n-adic authenticator h(C) by solving the linear modular equations in modulo n, using calculated values of the coefficients.

Claim 18

The method of claim 17, wherein the calculated values of the coefficients are stored in a coefficient table, and the sequentially determining step refers to the calculated values of the coefficients as stored in the coefficient table.

Claim 19

The method of claim 16, wherein the sequentially obtaining step sequentially obtains the upper digits h(C) 1 to h(C) k-1 recursively by using an identical mapping or formula for obtaining each h(C) i from h(C) ⊘ to h(C) i-1 by solving a linear modular equation in modulo n, using the lowest digit h(C) ⊘ , the first public key n, the second public key e, the authenticator h(M) and the number of partial blocks k as inputs.

Claim 20

An article of manufacture, comprising: a computer usable medium having computer readable program code means embodied therein for causing a computer to function as an authentication message generation device for generating an encrypted authenticator corresponding to an authenticator h(M) based on an n-adic public key cryptosystem using a first secret key formed by two prime numbers p and q, a second secret key d, a first public key n = pq , a second public key e, and a number of partial blocks k which is an integer greater than or equal to 2, the computer readable program code means including: first computer readable program code means for causing said computer to generate a lowest digit h(C) ⊘ of an encrypted n-adic authenticator h(C) as a d-th power of the authenticator h(M) in modulo n; second computer readable program code means for causing said computer to sequentially obtain upper digits h(C) i (1 ≤ i ≤ k-1) of the encrypted n-adic authenticator h(C) by solving linear modular equations based on the lowest digit h(C) ⊘ of the encrypted n-adic authenticator h(C) in modulo n; and third computer readable program code means for causing said computer to generate the encrypted authenticator by sequentially concatenating the lowest digit h(C) ⊘ and the upper digits h(C) i of the encrypted n-adic authenticator h(C).

Claim 21

An authentication message generation device for generating an encrypted authenticator corresponding to an authenticator h(M) based on an n-adic public key cryptosystem using a first secret key formed by two prime numbers p and q, a second secret key d, a first public key n = pq , a second public key e, and a number of partial blocks k which is an integer greater than or equal to 2, the device comprising: a lowest digit encryption unit for generating a lowest digit h(C) ⊘ of an encrypted n-adic authenticator h(C) as a d-th power of the authenticator h(M) in modulo n; an upper digit encryption unit for sequentially obtaining upper digits h(C) i (1 ≤ i ≤ k-1) of the encrypted n-adic authenticator h(C) by solving linear modular equations based on the lowest digit h(C) ⊘ of the encrypted n-adic authenticator h(C) in modulo n; and a data concatenation unit for generating the encrypted authenticator by sequentially concatenating the lowest digit h(C) ⊘ and the upper digits h(C) i of the encrypted n-adic authenticator h(C).

Claim 22

The device of claim 21, wherein at the upper digit encryption unit, the authenticator h(M) is taken to be in a form of an e-th power of the encrypted n-adic authenticator h(C) in which different digits of the encrypted n-adic authenticator h(C) correspond to different authenticator blocks dividing the encrypted authenticator, and the e-th power of the encrypted n-adic authenticator h(C) is expanded into a form of a (k-1)-th degree polynomial of n where coefficients of the (k-1)-th degree polynomial are expressed as polynomial functions with the authenticator blocks as variables, and the upper digit encryption unit further includes: a coefficient calculation unit for sequentially calculating values of the coefficients from a lower degree coefficient to a higher degree coefficient, according to the authenticator h(M) and already obtained lower digits of the encrypted n-adic authenticator h(C); and an upper digit calculation unit for sequentially determining the upper digits of the encrypted n-adic authenticator h(C) by solving the linear modular equations in modulo n, using calculated values of the coefficients.

Claim 23

The device of claim 22, wherein the coefficient calculation unit further includes a coefficient table for storing the calculated values of the coefficients, and the upper digit calculation unit refers to the calculated values of the coefficients as stored in the coefficient table.

Claim 24

The device of claim 21, wherein the upper digit encryption unit sequentially obtains the upper digits h(C) 1 to h(C) k-1 recursively by using an identical mapping or formula for obtaining each h(C) i from h(C) ⊘ to h(C) i-1 by solving a linear modular equation in modulo n, using the lowest digit h(C) ⊘ , the first public key n, the second public key e, the authenticator h(M) and the number of partial blocks k as inputs.

Claim 25

An authentication message verification method for verifying an authenticity of an authentication message M from an encrypted authenticator based on an n-adic public key cryptosystem using a first secret key formed by two prime numbers p and q, a second secret key d, a first public key n = pq , a second public key e, and a number of partial blocks k which is an integer greater than or equal to 2, the method comprising the steps of: sequentially coupling authenticator blocks dividing the encrypted authenticator to obtain an encrypted n-adic authenticator h(C) so that different digits of the encrypted n-adic authenticator h(C) correspond to different authenticator blocks; obtaining a decrypted authenticator h(M) as an e-th power of the encrypted n-adic authenticator h(C) in modulo n k ; obtaining an authenticator h(M)' by hashing the authentication message M; and comparing the decrypted authenticator h(M) and the authenticator h(M)', and judging that an authentication is success when the decrypted authenticator h(M) and the authenticator h(M)' match or that an authentication is failure otherwise.

Claim 26

An article of manufacture, comprising: a computer usable medium having computer readable program code means embodied therein for causing a computer to function as an authentication message verification method for verifying an authenticity of an authentication message M from an encrypted authenticator based on an n-adic public key cryptosystem using a first secret key formed by two prime numbers p and q, a second secret key d, a first public key n = pq , a second public key e, and a number of partial blocks k which is an integer greater than or equal to 2, the computer readable program code means including: first computer readable program code means for causing said computer to sequentially couple authenticator blocks dividing the encrypted authenticator to obtain an encrypted n-adic authenticator h(C) so that different digits of the encrypted n-adic authenticator h(C) correspond to different authenticator blocks; second computer readable program code means for causing said computer to obtain a decrypted authenticator h(M) as an e-th power of the encrypted n-adic authenticator h(C) in modulo n k ; third computer readable program code means for causing said computer to obtain an authenticator h(M)' by hashing the authentication message M; and fourth computer readable program code means for causing said computer to compare the decrypted authenticator h(M) and the authenticator h(M)', and judge that an authentication is success when the decrypted authenticator h(M) and the authenticator h(M)' match or that an authentication is failure otherwise.

Claim 27

An authentication message verification device for verifying an authenticity of an authentication message M from an encrypted authenticator based on an n-adic public key cryptosystem using a first secret key formed by two prime numbers p and q, a second secret key d, a first public key n = pq , a second public key e, and a number of partial blocks k which is an integer greater than or equal to 2, the device comprising: a data coupling unit for sequentially coupling authenticator blocks dividing the encrypted authenticator to obtain an encrypted n-adic authenticator h(C) so that different digits of the encrypted n-adic authenticator h(C) correspond to different authenticator blocks; an authenticator decryption unit for obtaining a decrypted authenticator h(M) as an e-th power of the encrypted n-adic authenticator h(C) in modulo n k ; an authentication message hashing unit for obtaining an authenticator h(M)' by hashing the authentication message M; and a matching judgement unit for comparing the decrypted authenticator h(M) and the authenticator h(M)', and judging that an authentication is success when the decrypted authenticator h(M) and the authenticator h(M)' match or that an authentication is failure otherwise.

Claim 28

A secret communication method based on an n-adic public key cryptosystem using a secret key formed by two prime numbers p and q, a public key n = pq , and a number of partial blocks k which is an integer greater than or equal to 2, the method comprising the steps of: expressing a plaintext in a form of a k-digit n-adic number at a sender side; obtaining a ciphertext in which the plaintext is encrypted by applying a calculation using the public key n and the number of partial blocks k to the n-adic number, and transmitting the ciphertext from the sender side to a receiver side; receiving the ciphertext and decrypting a lowest digit of the n-adic number from the ciphertext by using the public key n and the secret key p, q at the receiver side; sequentially decrypting upper digits of the n-adic number by using a decrypted value of the lowest digit of the n-adic number at the receiver side; and recovering the plaintext by using decrypted values of respective digits of the n-adic number at the receiver side.

Claim 29

The method of claim 28, further comprising the step of: forming the plaintext at the sender side by placing a random number of a bit length similar to that of the first public key n at a top of plaintext data.

Claim 30

An encryption method for generating a ciphertext corresponding to a plaintext based on an n-adic public key cryptosystem using a secret key formed by two prime numbers p and q, a public key n = pq , and a number of partial blocks k which is an integer greater than or equal to 2, the method comprising the steps of: dividing the plaintext into k plaintext blocks of a block size within a range of a residue class of n; forming a k-digit n-adic number by sequentially coupling the plaintext blocks so that different digits of the n-adic number correspond to different plaintext blocks; and obtaining the ciphertext as a square of the n-adic number in modulo n k .

Claim 31

An article of manufacture, comprising: a computer usable medium having computer readable program code means embodied therein for causing a computer to function as an encryption device for generating a ciphertext corresponding to a plaintext based on an n-adic public key cryptosystem using a secret key formed by two prime numbers p and q, a public key n = pq , and a number of partial blocks k which is an integer greater than or equal to 2, the computer readable program code means including: first computer readable program code means for causing said computer to divide the plaintext into k plaintext blocks of a block size within a range of a residue class of n; second computer readable program code means for causing said computer to form a k-digit n-adic number by sequentially coupling the plaintext blocks so that different digits of the n-adic number correspond to different plaintext blocks; and third computer readable program code means for causing said computer to obtain the ciphertext as a square of the n-adic number in modulo n k .

Claim 32

An encryption device for generating a ciphertext corresponding to a plaintext based on an n-adic public key cryptosystem using a secret key formed by two prime numbers p and q, a public key n = pq , and a number of partial blocks k which is an integer greater than or equal to 2, the device comprising: a plaintext division unit for dividing the plaintext into k plaintext blocks of a block size within a range of a residue class of n; a data coupling unit for forming a k-digit n-adic number by sequentially coupling the plaintext blocks so that different digits of the n-adic number correspond to different plaintext blocks; and an encryption unit for obtaining the ciphertext as a square of the n-adic number in modulo n k .

Claim 33

A decryption method for recovering a plaintext corresponding to a ciphertext based on an n-adic public key cryptosystem using a secret key formed by two prime numbers p and q, a public key n = pq , and a number of partial blocks k which is an integer greater than or equal to 2, the method comprising the steps of: obtaining a lowest digit M ⊘ of an n-adic number expressing the plaintext, by solving simultaneous modular equations for finding a number whose square in modulo p and whose square in modulo q are both equal to the ciphertext; sequentially obtaining upper digits M i (1 ≤ i ≤ k-1) of the n-adic number by solving linear modular equations based on the lowest digit M ⊘ of the n-adic number in modulo n; and recovering the plaintext by sequentially concatenating the lowest digit M ⊘ and the upper digits M i of the n-adic number.

Claim 34

The method of claim 33, wherein at the sequentially obtaining step, the ciphertext is taken to be in a form of a square of the n-adic number in which different digits of the n-adic number correspond to different plaintext blocks dividing the plaintext, and the square of the n-adic number is expanded into a form of a (k-1)-th degree polynomial of n where coefficients of the (k-1)-th degree polynomial are expressed as polynomial functions with the plaintext blocks as variables, and the sequentially obtaining step further includes the steps of: sequentially formulating the linear modular equations with the plaintext blocks as variables in modulo n, according to the ciphertext and already obtained lower digits of the n-adic number; and sequentially determining the upper digits of the n-adic number by solving the linear modular equations in modulo n.

Claim 35

The method of claim 33, wherein the sequentially obtaining step sequentially obtains the upper digits M 1 to M k-1 recursively by using an identical mapping or formula for obtaining each M i from M ⊘ to M i-1 by solving a linear modular equation in modulo n, using the lowest digit M ⊘ , the public key n, the ciphertext C and the number of partial blocks k as inputs.

Claim 36

An article of manufacture, comprising: a computer usable medium having computer readable program code means embodied therein for causing a computer to function as a decryption device for recovering a plaintext corresponding to a ciphertext based on an n-adic public key cryptosystem using a secret key formed by two prime numbers p and q, a public key n = pq , and a number of partial blocks k which is an integer greater than or equal to 2, the computer readable program code means including: first computer readable program code means for causing said computer to obtain a lowest digit M ⊘ of an n-adic number expressing the plaintext, by solving simultaneous modular equations for finding a number whose square in modulo p and whose square in modulo q are both equal to the ciphertext; second computer readable program code means for causing said computer to sequentially obtain upper digits M i (1 ≤ i ≤ k-1) of the n-adic number by solving linear modular equations based on the lowest digit M ⊘ of the n-adic number in modulo n; and third computer readable program code means for causing said computer to recover the plaintext by sequentially concatenating the lowest digit M ⊘ and the upper digits M i of the n-adic number.

Claim 37

A decryption device for recovering a plaintext corresponding to a ciphertext based on an n-adic public key cryptosystem using a secret key formed by two prime numbers p and q, a public key n = pq , and a number of partial blocks k which is an integer greater than or equal to 2, the device comprising: a lowest digit decryption unit for obtaining a lowest digit M ⊘ of an n-adic number expressing the plaintext, by solving simultaneous modular equations for finding a number whose square in modulo p and whose square in modulo q are both equal to the ciphertext; an upper digit decryption unit for sequentially obtaining upper digits M i (1 ≤ i ≤ k-1) of the n-adic number by solving linear modular equations based on the lowest digit M ⊘ of the n-adic number in modulo n; and a data concatenation unit for recovering the plaintext by sequentially concatenating the lowest digit M ⊘ and the upper digits M i of the n-adic number.

Claim 38

The device of claim 37, wherein at the upper digit decryption unit, the ciphertext is taken to be in a form of a square of the n-adic number in which different digits of the n-adic number correspond to different plaintext blocks dividing the plaintext, and the square of the n-adic number is expanded into a form of a (k-1)-th degree polynomial of n where coefficients of the (k-1)-th degree polynomial are expressed as polynomial functions with the plaintext blocks as variables, and the upper digit decryption unit sequentially obtains the upper digits of the n-adic number by: sequentially formulating the linear modular equations with the plaintext blocks as variables in modulo n, according to the ciphertext and already obtained lower digits of the n-adic number; and sequentially determining the upper digits of the n-adic number by solving the linear modular equations in modulo n.

Claim 39

The device of claim 37, wherein the upper digit decryption unit sequentially obtains the upper digits M 1 to M k-1 recursively by using an identical mapping or formula for obtaining each M i from M ⊘ to M i-1 by solving a linear modular equation in modulo n, using the lowest digit M ⊘ , the public key n, the ciphertext C and the number of partial blocks k as inputs.

Claim 40

An authentication method based on an n-adic public key cryptosystem using a secret key formed by two prime numbers p and q, a public key n = pq , and a number of partial blocks k which is an integer greater than or equal to 2, the method comprising the steps of: generating an authenticator h(M) from an authentication message M at an authentication message generating side; generating a lowest digit h(C) ⊘ of an encrypted n-adic authenticator h(C) by applying a calculation using the public key n and th secret key p, q to the authenticator h(M) at the authentication message generating side; sequentially generating upper digits h(C) i (1 ≤ i ≤ k-1) of the encrypted n-adic authenticator h(C) by using the lowest digit h(C) ⊘ at the authentication message generating side; generating an encrypted authenticator by sequentially concatenating the lowest digit h(C) ⊘ and the upper digits h(C) i of the encrypted n-adic authenticator h(C) at the authentication message generating side; transmitting the encrypted authenticator and the authentication message M from the authentication message generating side to an authentication message verifying side; obtaining a decrypted authenticator by applying a calculation using the public key n and the number of partial blocks k to the encrypted n-adic authenticator h(C) obtained from the encrypted authenticator at the authentication message verifying side; and verifying an authenticity of the authentication message M by using the decrypted authenticator and the authentication message M at the authentication message verifying side.

Claim 41

An authentication message generation method for generating an encrypted authenticator corresponding to an authenticator h(M) based on an n-adic public key cryptosystem using a secret key formed by two prime numbers p and q, a public key n = pq , and a number of partial blocks k which is an integer greater than or equal to 2, the method comprising the steps of: generating a lowest digit h(C) ⊘ of an encrypted n-adic authenticator h(C) by solving simultaneous modular equations for finding a number whose square in modulo p and whose square in modulo q are both equal to the ciphertext; sequentially obtaining upper digits h(C) i (1 ≤ i ≤ k-1) of the encrypted n-adic authenticator h(C) by solving linear modular equations based on the lowest digit h(C) ⊘ of the encrypted n-adic authenticator h(C) in modulo n; and generating the encrypted authenticator by sequentially concatenating the lowest digit h(C) ⊘ and the upper digits h(C) i of the encrypted n-adic authenticator h(C).

Claim 42

The method of claim 41, wherein at the sequentially obtaining step, the authenticator h(M) is taken to be in a form of a square of the encrypted n-adic authenticator h(C) in which different digits of the encrypted n-adic authenticator h(C) correspond to different authenticator blocks dividing the encrypted authenticator, and the square of the encrypted n-adic authenticator h(C) is expanded into a form of a (k-1)-th degree polynomial of n where coefficients of the (k-1)-th degree polynomial are expressed as polynomial functions with the authenticator blocks as variables, and the sequentially obtaining step further includes the steps of: sequentially formulating the linear modular equations with the authenticator blocks as variables in modulo n, according to the authenticator h(M) and already obtained lower digits of the encrypted n-adic authenticator h(C); and sequentially determining the upper digits of the encrypted n-adic authenticator h(C) by solving the linear modular equations in modulo n.

Claim 43

The method of claim 41, wherein the sequentially obtaining step sequentially obtains the upper digits h(C) 1 to h(C) k-1 recursively by using an identical mapping or formula for obtaining each h(C) i from h(C) ⊘ to h(C) i-1 by solving a linear modular equation in modulo n, using the lowest digit h(C) ⊘ , the public key n, the authenticator h(M) and the number of partial blocks k as inputs.

Claim 44

An article of manufacture, comprising: a computer usable medium having computer readable program code means embodied therein for causing a computer to function as an authentication message generation device for generating an encrypted authenticator corresponding to an authenticator h(M) based on an n-adic public key cryptosystem using a secret key formed by two prime numbers p and q, a public key n = pq , and a number of partial blocks k which is an integer greater than or equal to 2, the computer readable program code means including: first computer readable program code means for causing said computer to generate a lowest digit h(C) ⊘ of an encrypted n-adic authenticator h(C) by solving simultaneous modular equations for finding a number whose square in modulo p and whose square in modulo q are both equal to the ciphertext; second computer readable program code means for causing said computer to sequentially obtain upper digits h(C) i (1 ≤ i ≤ k-1) of the encrypted n-adic authenticator h(C) by solving linear modular equations based on the lowest digit h(C) ⊘ of the encrypted n-adic authenticator h(C) in modulo n; and third computer readable program code means for causing said computer to generate the encrypted authenticator by sequentially concatenating the lowest digit h(C) ⊘ and the upper digits h(C) i of the encrypted n-adic authenticator h(C).

Claim 45

An authentication message generation device for generating an encrypted authenticator corresponding to an authenticator h(M) based on an n-adic public key cryptosystem using a secret key formed by two prime numbers p and q, a public key n = pq , and a number of partial blocks k which is an integer greater than or equal to 2, the device comprising: a lowest digit encryption unit for generating a lowest digit h(C) ⊘ of an encrypted n-adic authenticator h(C) by solving simultaneous modular equations for finding a number whose square in modulo p and whose square in modulo q are both equal to the ciphertext; an upper digit encryption unit for sequentially obtaining upper digits h(C) i (1 ≤ i ≤ k-1) of the encrypted n-adic authenticator h(C) by solving linear modular equations based on the lowest digit h(C) ⊘ of the encrypted n-adic authenticator h(C) in modulo n; and a data concatenation unit for generating the encrypted authenticator by sequentially concatenating the lowest digit h(C) ⊘ and the upper digits h(C) i of the encrypted n-adic authenticator h(C).

Claim 46

The device of claim 45, wherein at the upper digit encryption unit, the authenticator h(M) is taken to be in a form of a square of the encrypted n-adic authenticator h(C) in which different digits of the encrypted n-adic authenticator h(C) correspond to different authenticator blocks dividing the encrypted authenticator, and the square of the encrypted n-adic authenticator h(C) is expanded into a form of a (k-1)-th degree polynomial of n where coefficients of the (k-1)-th degree polynomial are expressed as polynomial functions with the authenticator blocks as variables, and the upper digit encryption unit sequentially obtains the upper digits of the encrypted n-adic authenticator h(C) by: sequentially formulating the linear modular equations with the authenticator blocks as variables in modulo n, according to the authenticator h(M) and already obtained lower digits of the encrypted n-adic authenticator h(C); and sequentially determining the upper digits of the encrypted n-adic authenticator h(C) by solving the linear modular equations in modulo n.

Claim 47

The device of claim 45, wherein the upper digit encryption unit sequentially obtains the upper digits h(C) 1 to h(C) k-1 recursively by using an identical mapping or formula for obtaining each h(C) i from h(C) ⊘ to h(C) i-1 by solving a linear modular equation in modulo n, using the lowest digit h(C) ⊘ , the public key n, the authenticator h(M) and the number of partial blocks k as inputs.

Claim 48

An authentication message verification method for verifying an authenticity of an authentication message M from an encrypted authenticator based on an n-adic public key cryptosystem using a secret key formed by two prime numbers p and q, a public key n = pq , and a number of partial blocks k which is an integer greater than or equal to 2, the method comprising the steps of: sequentially coupling authenticator blocks dividing the encrypted authenticator to obtain an encrypted n-adic authenticator h(C) so that different digits of the encrypted n-adic authenticator h(C) correspond to different authenticator blocks; obtaining a decrypted authenticator h(M) as a square of the encrypted n-adic authenticator h(C) in modulo n k ; obtaining an authenticator h(M)' by hashing the authentication message M; and comparing the decrypted authenticator h(M) and the authenticator h(M)', and judging that an authentication is success when the decrypted authenticator h(M) and the authenticator h(M)' match or that an authentication is failure otherwise.

Claim 49

An article of manufacture, comprising: a computer usable medium having computer readable program code means embodied therein for causing a computer to function as an authentication message verification method for verifying an authenticity of an authentication message M from an encrypted authenticator based on an n-adic public key cryptosystem using a secret key formed by two prime numbers p and q,a public key n = pq , and a number of partial blocks k which is an integer greater than or equal to 2, the computer readable program code means including: first computer readable program code means for causing said computer to sequentially couple authenticator blocks dividing the encrypted authenticator to obtain an encrypted n-adic authenticator h(C) so that different digits of the encrypted n-adic authenticator h(C) correspond to different authenticator blocks; second computer readable program code means for causing said computer to obtain a decrypted authenticator h(M) as a square of the encrypted n-adic authenticator h(C) in modulo n k ; third computer readable program code means for causing said computer to obtain an authenticator h(M)' by hashing the authentication message M; and fourth computer readable program code means for causing said computer to compare the decrypted authenticator h(M) and the authenticator h(M)', and judge that an authentication is success when the decrypted authenticator h(M) and the authenticator h(M)' match or that an authentication is failure otherwise.

Claim 50

An authentication message verification device for verifying an authenticity of an authentication message M from an encrypted authenticator based on an n-adic public key cryptosystem using a secret key formed by two prime numbers p and q, a public key n = pq , and a number of partial blocks k which is an integer greater than or equal to 2, the device comprising: a data coupling unit for sequentially coupling authenticator blocks dividing the encrypted authenticator to obtain an encrypted n-adic authenticator h(C) so that different digits of the encrypted n-adic authenticator h(C) correspond to different authenticator blocks; an authenticator decryption unit for obtaining a decrypted authenticator h(M) as a square of the encrypted n-adic authenticator h(C) in modulo n k ; an authentication message hashing unit for obtaining an authenticator h(M)' by hashing the authentication message M; and a matching judgement unit for comparing the decrypted authenticator h(M) and the authenticator h(M)', and judging that an authentication is success when the decrypted authenticator h(M) and the authenticator h(M)' match or that an authentication is failure otherwise.