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

• US 6,259,790 B1
• Filed: 08/08/1997
• Issued: 07/10/2001
• Est. Priority Date: 08/09/1996
• Status: Expired due to Fees

• Current Assignee: Nippon Telegraph and Telephone Corporation
• Original Assignee: Nippon Telegraph and Telephone Corporation
• Inventors: Takagi, Tsuyoshi, Naito, Shozo
• Primary Examiner(s): Barron, Jr., Gilberto
• Assistant Examiner(s): Leaning, Jeffrey Scott
• Application Number:
  US08/907,852
• Time in Patent Office: 1,432 Days
• Field of Search: 380/30, 380/28
• US Class Current: 380/30
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3249 using RSA or related signature schemes, e.g. Rabin scheme

Abstract

A secret communication and authentication scheme based on a public key cryptosystem in which a decryption speed is improved while maintaining a security level. In the RSA type secret communication, a plaintext is expressed in a form of a k-digit base n number and a ciphertext is obtained by applying a calculation using the first public key n and the second public key e to the base n number and transmitted. Then, from the received ciphertext, a lowest digit of the base n number is decrypted by using the first public key n and the second secret key d, upper digits of the base n number are sequentially decrypted by using a decrypted value of the lowest digit of the base n number at the receiver side, and the plaintext is recovered by using decrypted values of respective digits of the base n number. The Rabin type secret communication can also be realized by the similar scheme. Moreover, the same principle of the base n pubic key cryptosystem can also be used in realizing the RSA type or the Rabin type Authentication.

Claims

1. A secret communication method based on a base n 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:

expressing a plaintext in a form of a k-digit base n number at a sender side;

obtaining a ciphertext in which the plaintext is encrypted by applying a calculation using the first public key n and the second public key e to the base n number, and transmitting the ciphertext from the sender side to a receiver side;

receiving the ciphertext and decrypting a lowest digit of the base n number from the ciphertext by using the first public key n and the second secret key d at the receiver side;

sequentially decrypting upper digits of the base n number by using a decrypted value of the lowest digit of the base n number at the receiver side; and

recovering the plaintext by using decrypted values of respective digits of the base n number at the receiver side.

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.

3. An encryption method for generating a ciphertext corresponding to a plaintext based on a base n 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 base n number by sequentially coupling the plaintext blocks so that different digits of the base n number correspond to different plaintext blocks; and

obtaining the ciphertext as an e-th power of the base n number in modulo n^k.

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 a base n 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 base n number by sequentially coupling the plaintext blocks so that different digits of the base n 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 base n number in modulo n^k.

5. An encryption device for generating a ciphertext corresponding to a plaintext based on a base n 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 base n number by sequentially coupling the plaintext blocks so that different digits of the base n number correspond to different plaintext blocks; and

an encryption unit for obtaining the ciphertext as an e-th power of the base n number in modulo n^k.

6. A decryption method for recovering a plaintext corresponding to a ciphertext based on a base n 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 a base n 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 base n number by solving linear modular equations based on the lowest digit M

of the base n number in modulo n; and

recovering the plaintext by sequentially concatenating the lowest digit M and

the upper digits M_i of the base n number.

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 base n number in which different digits of the base n number correspond to different plaintext blocks dividing the plaintext, and the e-th power of the base n 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 base n number; and

sequentially determining the upper digits of the base n number by solving the linear modular equations in modulo n, using calculated values of the coefficients.

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.

9. The method of claim 6, wherein the sequentially obtaining step sequentially obtains the upper digits M₁ to M_k−

1 recursively by using an identical mapping or formula for obtaining each M_i from M

to M<sub>i−

1</sub> 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.

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 a base n 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 a base n 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 base n number by solving linear modular equations based on the lowest digit M

of the base n 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 base n number.

11. A decryption device for recovering a plaintext corresponding to a ciphertext based on a base n 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 a base n 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_l (1≦

i≦

k−

1) of the base n number by solving linear modular equations based on the lowest digit M

of the base n 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 base n number.

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 base n number in which different digits of the base n number correspond to different plaintext blocks dividing the plaintext, and the e-th power of the base n 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 base n number; and

an upper digit calculation unit for sequentially determining the upper digits of the base n number by solving the linear modular equations in modulo n, using calculated values of the coefficients.

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.

14. The device of claim 11, wherein the upper digit decryption unit sequentially obtains the upper digits M₁ to M_k−

1 recursively by using an identical mapping or formula for obtaining each M_i from M

to M<sub>i−

1</sub> 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.

15. An authentication method based on a base n 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 S

of an encrypted base n authenticator S 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 S_i (1≦

i≦

k−

1) of the encrypted base n authenticator S by using the lowest digit S

at the authentication message generating side;

generating an encrypted authenticator by sequentially concatenating the lowest digit S and

the upper digits S_i of the encrypted base n authenticator S 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 base n authenticator S 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.

16. An authentication message generation method for generating an encrypted authenticator corresponding to an authenticator h(M) based on a base n 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 S

of an encrypted base n authenticator S as a d-th power of the authenticator h(M) in modulo n;

sequentially obtaining upper digits S_i (1≦

i≦

k−

1) of the encrypted base n authenticator S by solving linear modular equations based on the lowest digit S

of the encrypted base n authenticator S in modulo n; and

generating the encrypted authenticator by sequentially concatenating the lowest digit S and

the upper digits S_i of the encrypted base n authenticator S.

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 base n authenticator S in which different digits of the encrypted base n authenticator S correspond to different authenticator blocks dividing the encrypted authenticator, and the e-th power of the encrypted base n authenticator S 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 base n authenticator S; and

sequentially determining the upper digits of the encrypted base n authenticator S by solving the linear modular equations in modulo n, using calculated values of the coefficients.

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.

19. The method of claim 16, wherein the sequentially obtaining step sequentially obtains the upper digits S₁ to S_k−

1 recursively by using an identical mapping or formula for obtaining each S_i from S

to S<sub>i−

1</sub> by solving a linear modular equation in modulo n, using the lowest digit S

, the first public key n, the second public key e, the authenticator h(M) and the number of partial blocks k as inputs.

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 a base n 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 S

of an encrypted base n authenticator S 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 S_i (1≦

i≦

k−

1) of the encrypted base n authenticator S by solving linear modular equations based on the lowest digit S

of the encrypted base n authenticator S 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 S and

the upper digits S_i of the encrypted base n authenticator S.

21. An authentication message generation device for generating an encrypted authenticator corresponding to an authenticator h(M) based on a base n 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 S

of an encrypted base n authenticator S as a d-th power of the authenticator h(M) in modulo n;

an upper digit encryption unit for sequentially obtaining upper digits S_i (1≦

i≦

k−

1) of the encrypted base n authenticator S by solving linear modular equations based on the lowest digit S

of the encrypted base n authenticator S in modulo n; and

a data concatenation unit for generating the encrypted authenticator by sequentially concatenating the lowest digit S and

the upper digits S_i of the encrypted base n authenticator S.

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 base n authenticator S in which different digits of the encrypted base n authenticator S correspond to different authenticator blocks dividing the encrypted authenticator, and the e-th power of the encrypted base n authenticator S 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 base n authenticator S; and

an upper digit calculation unit for sequentially determining the upper digits of the encrypted base n authenticator S by solving the linear modular equations in modulo n, using calculated values of the coefficients.

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.

24. The device of claim 21, wherein the upper digit encryption unit sequentially obtains the upper digits S₁ to S_k−

1 recursively by using an identical mapping or formula for obtaining each S_i from S

to S<sub>i−

1</sub> by solving a linear modular equation in modulo n, using the lowest digit S

, the first public key n, the second public key e, the authenticator h(M) and the number of partial blocks k as inputs.

25. An authentication message verification method for verifying an authenticity of an authentication message M from an encrypted authenticator based on a base n 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 base n authenticator S so that different digits of the encrypted base n authenticator S correspond to different authenticator blocks;

obtaining a decrypted authenticator h(M) as an e-th power of the encrypted base n authenticator S 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.

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 a base n 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 base n authenticator S so that different digits of the encrypted base n authenticator S 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 base n authenticator S 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.

27. An authentication message verification device for verifying an authenticity of an authentication message M from an encrypted authenticator based on a base n 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 base n authenticator S so that different digits of the encrypted base n authenticator S correspond to different authenticator blocks;

an authenticator decryption unit for obtaining a decrypted authenticator h(M) as an e-th power of the encrypted base n authenticator S 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.

28. A secret communication method based on a base n 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 base n 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 base n number, and transmitting the ciphertext from the sender side to a receiver side;

receiving the ciphertext and decrypting a lowest digit of the base n 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 base n number by using a decrypted value of the lowest digit of the base n number at the receiver side; and

recovering the plaintext by using decrypted values of respective digits of the base n number at the receiver side.

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.

30. An encryption method for generating a ciphertext corresponding to a plaintext based on a base n 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 base n number by sequentially coupling the plaintext blocks so that different digits of the base n number correspond to different plaintext blocks; and

obtaining the ciphertext as a square of the base n number in modulo n^k.

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 a base n 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 base n number by sequentially coupling the plaintext blocks so that different digits of the base n 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 base n number in modulo n^k.

32. An encryption device for generating a ciphertext corresponding to a plaintext based on a base n 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 base n number by sequentially coupling the plaintext blocks so that different digits of the base n number correspond to different plaintext blocks; and

an encryption unit for obtaining the ciphertext as a square of the base n number in modulo n^k.

33. A decryption method for recovering a plaintext corresponding to a ciphertext based on a base n 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 a base n 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 base n number by solving linear modular equations based on the lowest digit M

of the base n number in modulo n; and

recovering the plaintext by sequentially concatenating the lowest digit M and

the upper digits M_i of the base n number.

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 base n number in which different digits of the base n number correspond to different plaintext blocks dividing the plaintext, and the square of the base n 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 base n number; and

sequentially determining the upper digits of the base n number by solving the linear modular equations in modulo n.

35. The method of claim 33, wherein the sequentially obtaining step sequentially obtains the upper digits M₁ to M_k−

1 recursively by using an identical mapping or formula for obtaining each M_i from M

to M<sub>i−

1</sub> 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.

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 a base n 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 a base n 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 base n number by solving linear modular equations based on the lowest digit M

of the base n 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 base n number.

37. A decryption device for recovering a plaintext corresponding to a ciphertext based on a base n 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 a base n 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 base n number by solving linear modular equations based on the lowest digit M

of the base n 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 base n number.

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 base n number in which different digits of the base n number correspond to different plaintext blocks dividing the plaintext, and the square of the base n 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 base n 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 base n number; and

sequentially determining the upper digits of the base n number by solving the linear modular equations in modulo n.

39. The device of claim 37, wherein the upper digit decryption unit sequentially obtains the upper digits M₁ to M_k−

1 recursively by using an identical mapping or formula for obtaining each M_i from M

to M<sub>i−

1</sub> 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.

40. An authentication method based on a base n 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 S

of an encrypted base n authenticator S by applying a calculation using the public key n and the secret key p, q to the authenticator h(M) at the authentication message generating side;

sequentially generating upper digits S_i (1≦

i≦

k−

1) of the encrypted base n authenticator S by using the lowest digit S

at the authentication message generating side;

generating an encrypted authenticator by sequentially concatenating the lowest digit S and

the upper digits S_i of the encrypted base n authenticator S 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 base n authenticator S 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.

41. An authentication message generation method for generating an encrypted authenticator corresponding to an authenticator h(M) based on a base n 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 S

of an encrypted base n authenticator S 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 S_i (1≦

i≦

k−

1) of the encrypted base n authenticator S by solving linear modular equations based on the lowest digit S

of the encrypted base n authenticator S in modulo n; and

generating the encrypted authenticator by sequentially concatenating the lowest digit S and

the upper digits S_i of the encrypted base n authenticator S.

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 base n authenticator S in which different digits of the encrypted base n authenticator S correspond to different authenticator blocks dividing the encrypted authenticator, and the square of the encrypted base n authenticator S 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 base n authenticator S; and

sequentially determining the upper digits of the encrypted base n authenticator S by solving the linear modular equations in modulo n.

43. The method of claim 41, wherein the sequentially obtaining step sequentially obtains the upper digits S₁ to S_k−

1 recursively by using an identical mapping or formula for obtaining each S_i from S

to S<sub>i−

1</sub> by solving a linear modular equation in modulo n, using the lowest digit S

, the public key n, the authenticator h(M) and the number of partial blocks k as inputs.

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 a base n 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 S

of an encrypted base n authenticator S 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 S_i (1≦

i≦

k−

1) of the encrypted base n authenticator S by solving linear modular equations based on the lowest digit S

of the encrypted base n authenticator S 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 S and

the upper digits S_i of the encrypted base n authenticator S.

45. An authentication message generation device for generating an encrypted authenticator corresponding to an authenticator h(M) based on a base n 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 S

of an encrypted base n authenticator S 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 S_i (1≦

i≦

k−

1) of the encrypted base n authenticator S by solving linear modular equations based on the lowest digit S

of the encrypted base n authenticator S in modulo n; and

a data concatenation unit for generating the encrypted authenticator by sequentially concatenating the lowest digit S and

the upper digits S_i of the encrypted base n authenticator S.

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 base n authenticator S in which different digits of the encrypted base n authenticator S correspond to different authenticator blocks dividing the encrypted authenticator, and the square of the encrypted base n authenticator S 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 base n authenticator S 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 base n authenticator S; and

sequentially determining the upper digits of the encrypted base n authenticator S by solving the linear modular equations in modulo n.

47. The device of claim 45, wherein the upper digit encryption unit sequentially obtains the upper digits S₁ to S_k−

1 recursively by using an identical mapping or formula for obtaining each S_i from S

to S<sub>i−

1</sub> by solving a linear modular equation in modulo n, using the lowest digit S

, the public key n, the authenticator h(M) and the number of partial blocks k as inputs.

48. An authentication message verification method for verifying an authenticity of an authentication message M from an encrypted authenticator based on a base n 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 base n authenticator S so that different digits of the encrypted base n authenticator S correspond to different authenticator blocks;

obtaining a decrypted authenticator h(M) as a square of the encrypted base n authenticator S 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.

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 a base n 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 base n authenticator S so that different digits of the encrypted base n authenticator S 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 base n authenticator S 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.

50. An authentication message verification device for verifying an authenticity of an authentication message M from an encrypted authenticator based on a base n 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 base n authenticator S so that different digits of the encrypted base n authenticator S correspond to different authenticator blocks;

an authenticator decryption unit for obtaining a decrypted authenticator h(M) as a square of the encrypted base n authenticator S 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.