Abstract:
A cipher communication method by public key cryptosystem, being provably secure and highly efficient, wherein a sender generates ciphertext within a sender device using a receiver&#39;s public key and sends the ciphertext over a communication line, and a receiver decrypts the ciphertext using a secret key. For n=p d q (p and q are prime integers, and pq is k bits), a plaintext space is set to be a subset of an open set (0,2 k−2 ) and small residue groups, and an algorithm is formed so that the relationship among solutions of plural second-order equations can be clarified. This has enabled security to be proved by equivalence with the difficulty of the problem of prime factorization, and has achieved faster decryption processing, compared with conventional methods.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    The present invention relates to a cipher communication method and a key sharing method that uses public key cryptosystem.  
           [0002]    Various public key encryption schemes have been so far proposed. Of these, a method described in document 1, “R. L. Rivest, A. Shamir, L. Adleman: A method for obtaining digital signatures and public-key cryptosystems, Commun. of the ACM, Vol. 21, No.2, pp. 120-126, 1978” is the most famous and most practically used public key cryptosystem. Additionally, methods using elliptic curves, described in document 2 “V. S. Miller: Use of Elliptic Curves in Cryptography, Proc. of Crypto &#39;85, LNCS218, Springer-Verlag, pp. 417-426 (1985)”, and document 3 “N. Koblitz: Elliptic Curve Cryptosystems, Math. Comp., 48, 177, pp. 203-209 (1987)”, etc., are known as efficient public key cryptosystems.  
           [0003]    Known encryption methods provably secure against chosen plaintext attacks include those described in: document 4 “M. O. Rabin: Digital Signatures and Public-Key Encryptions as Intractable as Factorization, MIT, Technical Report, MIT/LCS/TR-212 (1979); document 5 “T. ElGamal: A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, IEEE Trans. On Information Theory, IT-31, 4, pp. 469-472 (1985)”; document 6 “S. Goldwasser and S. Micali: Probabilistic Encryption, JCSS, 28, 2, pp. 270-299 (1984)”; document 7 “M. Blum and S. Goldwasser: An Efficient probabilistic public-key encryption scheme which hides all partial information, Proc. of Crypto &#39;84, LNCS196, Springer-Verlag, pp.289-299 (1985); document 8 “S. Goldwasser and M. Bellare: Lecture Notes on Cryptography, http:/www-cse.ucsd.edu/users/mihir/(1997)”; and document 9 “T. Okamoto and S. Uchiyama: A New Public-Key Cryptosystem as Secure as Factoring, Proc. of Eurocrypt &#39;98, LNCS1403, Springer Verlag, pp. 308-318 (1998)”. Known encryption methods provably secure against chosen ciphertext attacks include those described in: document 10 “D. Dolve, C. Dwork and M. Naor: Non-malleable cryptography, In 23 rd  Annual ACM Symposium On Theory of Computing, pp. 542-552 (1991)”; document 11 “M. Naor and M. Yung: Public-key cryptosystems provably secure against chosen ciphertext attacks, Proc. of STOC, ACM Press, pp. 427-437 (1990)”; document 12 “M. Bellare and P. Rogaway, Optimal Asymmetric Encryption How to Encrypt with RSA, Proc. of Eurocrypt &#39;94, LNCS950, Springer Verlag, pp. 92-111 (1994)”; and document 13 “R. Cramer and V. Shoup: A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack, Proc. of Crypto98, LNCS1462, Springer-Verlag, pp. 13-25 (1998)”.  
           [0004]    In document 14 “M. Bellare, A. Desai, D. Pointcheval and P. Rogaway.: Relations Among Nations of Security for Public-Key Encryption Schemes, Proc. of Crypto &#39;98, LNCS1462, Springer Verlag, pp. 26-45 (1998)”, there is shown the equivalence between IND-CCA2 (indistinguishable against adaptive chosen ciphertext attacks) and NM-CCA2 (non-malleable against adaptive chosen ciphertext attacks). Presently, public key cryptosystem satisfying this condition is considered to be the most secure.  
         SUMMARY OF THE INVENTION  
         [0005]    The present invention provides a public key encryption method that is provably secure and excellent in the efficiency of encryption and decryption processing.  
           [0006]    The present invention first provides a public key encryption method that is provably OW-CPA (unidirectional for chosen plaintext attacks), under the assumption that the prime factorization problem is computationally intractable. The present invention also provides a public key encryption method that is provably IND-CCA2 (or NM-CCA2) which is based on this method.  
           [0007]    These encryption methods are smaller in the number of modular multiplications required in encryption and decryption processing than conventional methods, enabling high-speed processing.  
           [0008]    Also, the present invention provides an encryption method and a decryption method using public key cryptosystem which produce a small amount of computational load in encrypting send data and decrypting encrypted data and enables high-speed processing for devices with limited computational capability such as portable information processing equipment, a key distribution method and a key sharing method using these methods, and programs, devices, or systems that implement the methods.  
           [0009]    The present invention is performed as follows.  
           [0010]    (1) As n=p d q (d is an odd number satisfying d&gt;1), for the bit length k of pq, a small plaintext space is selected so as to be an open set (0, 2 k−2 ).  
           [0011]    (2) On a residue group modulo a composite number (a number consisting of products of plural mutually different prime integers), there are four or more square roots, and by putting the solutions of these square roots to good use, n can be factorized into prime integers. Taking advantage of this fact, the public key encryption method of the present invention builds a procedure for encryption and decryption so as to be provably secure for chosen plaintext attacks(OW-CPA), under the assumption that the problem of prime factorization is intractable.  
           [0012]    (3) For a public key encryption method by the above (1) and (2), the transformation method described in the document 12 is executed for transformation into a method having more powerful security, under the assumption that (ideal) random functions are publicized.  
           [0013]    As one concrete method,  
           [0014]    [Key Generation] 
           [0015]    a secret key (private key) (p,q,β) satisfying  
           [0016]    p, q: prime integers, p≡3 (mod 4), q≡3 (mod 4)  
           [0017]    βεZ, αβ≡1 (mod lcm(p−1,q−1))  
           [0018]     is generated, and a public key (n,k,k 0 ,k 1 ,α,G,H) satisfying  
           [0019]    n=p d q (d&gt;1 is odd)  
           [0020]    k, k 0 , k 1 : k is a binary length of pq, and k 0 , k 1  are positive integers with k&gt;k 0 −k 1 −2.  
           [0021]    αεZ  
           [0022]    G: {0,1} k     0   →{0,1} k−k     0     −2    
           [0023]    H: {0,1} k−k     0     −2 →{0,1} k     0      
           [0024]     is generated.  
           [0025]    [Encryption] 
           [0026]    A sender device computes  
             x =( m   0   k     1     ⊙G ( r ))∥( r⊙H ( m   0   k     1     ⊙G ( r ))) 
           [0027]    where a circled dot denotes “exclusive OR” 
           [0028]    for plaintext m (mε{0,1} 1 ,1=k−k 0 −k 1 −2) and a random number r(rε{0,1} k0 },  
             C=x   2nα  mod  n   
           [0029]     further computes  
           [0030]    and further computes Jacobi&#39;s symbol a=(x/n), and sends ciphertext (C,a) to the receiver device.  
           [0031]    [Decryption] 
           x     1   ,   p       =       C         (     p   +   1     )        β                   q     -   1         4          mod                 p       ,     
            x     1   ,   q       =       C         (     q   +   1     )        β                   p     -   d         4          mod                 q                             
 
           [0032]    The receiver device computes  
           [0033]    from the ciphertext (C,a), using a receiver&#39;s secret key (private key) (p,q,β),  
           [0034]    and computes y that satisfies (y/n)=a and 0&lt;y&lt;2 k−2  of φ(x 1,p ,x 1,q ), φ(−x 1,p ,x 1,q ), φ(x 1,p ,−x 1,q ), and φ(−x 1,p ,−x 1,q ), where φ denotes ring isomorphism mapping from Z/(p)×Z/(q) to Z/(pq) by the Chinese remainder theorem. Furthermore,  
           [0035]    when  
           y=s∥t (sε{0,1} k−k     0     −2 , tε{0,1} k     0   ) 
           [0036]     the receiver device computes  
             z=G ( H ( s )⊙ t )⊙ s,   
           [0037]    [0037]       m   =     {             [   z   ]     l               if              [   z   ]       k   1       =     0     k   1                   “   reject   ”         otherwise                                   
           [0038]     and decrypts the plaintext m by  
           [0039]     where [a] k  and [a] k  denote first k-bits and last k-bits of a, respectively.  
           [0040]    These and other benefits are described throughout the present specification. A further understanding of the nature and advantages of the invention may be realized by reference to the remaining portions of the specification and the attached drawings. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0041]    Preferred embodiments of the present invention will be described in detail based on the followings, wherein:  
         [0042]    [0042]FIG. 1 is a diagram showing the system configuration of embodiments of the present invention;  
         [0043]    [0043]FIG. 2 is a diagram showing the internal configuration of a sender device in embodiments of the present invention;  
         [0044]    [0044]FIG. 3 is a diagram showing the internal configuration of a receiver device in embodiments of the present invention;  
         [0045]    [0045]FIG. 4 is a diagram showing the internal configuration of a storage medium with a computing function in embodiments of the present invention;  
         [0046]    [0046]FIG. 5 is a diagram showing the outline of a first embodiment example;  
         [0047]    [0047]FIG. 6 is a diagram showing the outline of a sixth embodiment example;  
         [0048]    [0048]FIG. 7 is a diagram showing the outline of a seventh embodiment example;  
         [0049]    [0049]FIG. 8 is a diagram showing the outline of a ninth embodiment example;  
         [0050]    [0050]FIG. 9 is a diagram showing the outline of an eleventh embodiment example; and  
         [0051]    [0051]FIG. 10 shows comparisons between the method of an eleventh embodiment example (α=β=1) and a typical practical public key encryption method in efficiency (the number of modular products) and security. 
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0052]    Hereinafter, embodiment examples of the present invention will be described with reference to the accompanying drawings.  
         [0053]    As shown in FIG. 1, a system of embodiment examples of the present invention includes a sender device  100  and a receiver device  200 . Further, the sender device  100  and the receiver device are connected over a communication line  300 .  
         [0054]    As shown in FIG. 2, the sender device includes a random number generating unit  101 , an exponentiation unit  102 , an operation unit  103 , a modulo calculation unit  104 , a memory  105 , a communication device  106 , and an input device  107 .  
         [0055]    As shown in FIG. 3, the receiver device  200  includes a key generating unit  201 , an exponentiation unit  202 , a modulo calculation unit  203 , an operation unit  204 , a memory  205 , and a communication device  206 .  
         [0056]    As shown in FIG. 4, a storage medium with a computing function  400  includes an exponentiation unit  401 , a modulo calculation unit  402 , an operation unit  403 , a memory  404 , an output device  405 , a plaintext creating unit  406 , and a random number generating unit  407 .  
         [0057]    Any of the sender device  100 , the receiver device  200 , and the storage medium with a computing function  400  can be constructed using a computer having a CPU and a memory. Any of the random number generating unit, the key generating unit, the power computing unit, the modulo calculation unit, the plaintext creating unit, and the random number generating unit may be constructed with dedicated hardware or as a program running on an operation unit (CPU). The programs are embodied on computer-readable media such as portable storage media and communication media on a communication line, and are stored in a computer memory through the media.  
       First Embodiment Example  
       [0058]    In the present embodiment example, a message sender A sends send data m to a receiver B over cipher communications.  
         [0059]    [0059]FIG. 1 shows the system configuration of the present embodiment example. FIG. 5 outlines this embodiment example.  
         [0060]    1. Key Generation Processing  
         [0061]    The receiver B in advance generates secret information (p,q,β) satisfying  
         [0062]    p, q: prime integers, p≡3 (mod 4), q≡3 (mod 4)  
         [0063]    βεZ, αβ≡1 (mod lcm(p−1,q−1))  
         [0064]    by using the key generating unit  201  within the receiver device  200 , generates public information (n,k,α) (k denotes the bit length of pq) satisfying  
         [0065]    n=p d q (d&gt;1 is odd)  
         [0066]    k: binary length of pq  
         [0067]    αεZ  
         [0068]    and outputs the public information over the communication line  300  to send it to the sender device  100  or publicize it. The public information can be publicized using a known method such as, e.g., registration to a third party (public information managing institution). Other information is stored in the memory  205 .  
         [0069]    2. Encryption and Decryption Processing  
         [0070]    (1) The sender A computes  
           C=m   2nα  mod  n   
         [0071]    by using the operation unit  103 , the power computing unit  102 , and the modulo calculation unit  104  within the sender device  100  for plaintext m (0&lt;m&lt;2 K−2 ).  
         [0072]    Furthermore, the sender A obtains the above public information from the receiver B and computes Jacobi&#39;s symbol a=(m/n) using the operation unit  103  within the sender device  100  (the definition and computation method of the Jacobi&#39;s symbol are described in, e.g., Teiji Takagi, “Elementary Number System”, Iwanami Shoten, Publishers).  
         [0073]    Furthermore, the sender A sends ciphertext (C,a) to the receiver device  200  of the receiver B over the communication line  300 , using the communication device  106 .  
           m     1   ,   p       =       C         (     p   +   1     )        β                   q     -   1         4          mod                 p       ,     
            m     1   ,   q       =       C         (     q   +   1     )        β                   p     -   d         4          mod                 q                             
 
         [0074]    (2) The receiver B computes from the ciphertext (C,a), using the above described secret information (p,q,β) held, and the power computing unit  202 , the modulo calculation unit  203 , and the operation unit  204  within the receiver device  200 , and regards as the plaintext m any of φ(m 1,p ,m 1,q ), φ(−m 1,p ,m 1,q ), φ(m 1,p , m 1,q ), and φ(−m 1,p ,−m 1,q ) that satisfies (x/n)=a and 0&lt;x&lt;2 k−2 , where φ denotes ring isomorphism mapping from Z/(p)×Z/(q) to Z/(pq) by the Chinese remainder theorem.  
         [0075]    In the above described public key encryption method, with α and β each set equal to 1, by deleting α and β from public key and secret key respectively, key information in the method of the present embodiment example can be reduced.  
         [0076]    Secret keys p and q can also be generated from expressions p=2p′+1 and q=2q′+1, where p′ and q′ are prime integers.  
         [0077]    In the public key encryption method of the present embodiment example, the value of d (d&gt;1) is changeable depending on a system. Thereby, where the bit length of plaintext m is always small, decryption processing can be performed rapidly by increasing the range of d in a range in which prime factorization of n is intractable.  
         [0078]    According to a method in the present embodiment example, for example, when d=3, it can be proved that perfect decryption is impossible, under the assumption that the problem of prime factorization of n is intractable. Namely, if an algorithm for solving the problem of prime factorization of n is available, the algorithm could be used to form an algorithm for perfect decryption.  
       Second Embodiment Example  
       [0079]    In this embodiment example, a, which is part of ciphertext in the first embodiment example, is used as a public key.  
         [0080]    [0080]FIG. 1 shows the system configuration of this embodiment example.  
         [0081]    1. Key Generation Processing  
         [0082]    The receiver B in advance generates secret information (p,q,β)  
         [0083]    satisfying  
         [0084]    p, q: prime integers, p≡3 (mod 4), q≡3 (mod 4)  
         [0085]    βεZ, αβ≡1 (mod lcm(p−1,q−1))  
         [0086]    by using the key generating unit  201  within the receiver device  200 , generates public information (n,k,α,a) (k denotes the bit length of pq)  
         [0087]    n=p d q (d&gt;1is odd)  
         [0088]    k: binary length of pq  
         [0089]    αεZ  
         [0090]    αε{−1,1} 
         [0091]    satisfying  
         [0092]    and outputs the public information over the communication line  300  to send it to the sender device  100  or publicize it. The public information can be publicized using a known method such as, e.g., registration to a third party (public information managing institution). Other information is stored in the memory  205 .  
         [0093]    2. Encryption and Decryption Processing  
         [0094]    (1) The sender A computes  
           C=m   2nα  mod  n   
         [0095]    by using the operation unit  103 , the power computing unit  102 , and the modulo calculation unit  104  within the sender device  100  for plaintext m (0&lt;m&lt;2 K−2 ) satisfying a=(m/n).  
         [0096]    Furthermore, the sender A sends ciphertext C to the receiver device  200  of the receiver B over the communication line  300 , using the communication device  106 .  
         [0097]    (2) The receiver B computes  
           m     1   ,   p       =       C         (     p   +   1     )        β                   q     -   1         4          mod                 p       ,     
            m     1   ,   q       =       C         (     q   +   1     )        β                   p     -   d         4          mod                 q                             
 
         [0098]    from the ciphertext (C,a), using the above described secret information (p,q,β) held, and the power computing unit  202 , the modulo calculation unit  203 , and the operation unit  204  within the receiver device  200 , and regards as the plaintext m any of φ(m 1,p ,m 1,q ), φ(−m 1,p ,m 1,q ), φ(m 1,p ,−m 1,q ), and φ(−m 1,p ,−m 1,q ) that satisfies (x/n)=a and 0&lt;x&lt;2 k−2 , where φ denotes ring isomorphism mapping from Z/(p)×Z/(q) to Z/(pq) by the Chinese remainder theorem.  
         [0099]    In the above described public key encryption method, with α and β each set equal to 1, by deleting α and β from public key and secret key respectively, key information in the method of the present embodiment example can be reduced.  
         [0100]    Secret keys p and q can also be generated from expressions p=2p′+1 and q=2q′+1, where p′ and q′ are prime integers.  
         [0101]    In the public key encryption method of the present embodiment example, the value of d (d&gt;1) is changeable depending on a system. Thereby, where the bit length of plaintext m is always small, decryption processing can be performed rapidly by increasing the range of d in a range in which prime factorization of n is intractable.  
       Third Embodiment Example  
       [0102]    In this embodiment example, a description will be made of a method of creating plaintext m so as to include check information for checking whether message text to be sent to a receiver from a sender has been correctly decrypted. It can be proved that the public key encryption method in the first and second embodiment examples is unidirectional for chosen plaintext attacks, but it is not secure against chosen ciphertext attacks. Accordingly, message text to be sent to a receiver from a sender is transformed into plaintext m whose contents are provided with predetermined redundancy, the plaintext m is encrypted by the method described in the first embodiment example (or second embodiment example), and the receiver decrypts the plaintext m by the method of the first embodiment example (or second embodiment example) and checks the predetermined redundancy (if the predetermined redundancy is not provided, it is considered that decryption was not performed correctly).  
         [0103]    As another method, message text to be sent to a receiver from a sender is transformed into plaintext m whose contents are provided with a predetermined, meaningful message, the plaintext m is encrypted by the method described in the first embodiment example (or second embodiment example), and the receiver decrypts the plaintext m by the method of the first embodiment example (or second embodiment example) and checks the contents of the predetermined, meaningful message (if the contents of the predetermined, meaningful message do not match, it is considered that decryption was not performed correctly).  
         [0104]    These methods provide the public key encryption method of the first and second embodiment examples with some degree of security against chosen ciphertext attacks (a method of proving security against chosen ciphertext attacks will be described in embodiment examples).  
       Fourth Embodiment Example  
       [0105]    In this embodiment example, a description will be made of a key sharing method for sharing an identical value between a sender and a receiver, using public information generated by the receiver.  
         [0106]    1. Key Generation Processing  
         [0107]    The receiver B in advance generates secret information (p,q,β)  
         [0108]    p, q: prime integers, p≡3 (mod 4), q≡3 (mod 4)  
         [0109]    βεZ, αβ≡1 (mod lcm(p−1,q−1))  
         [0110]    satisfying  
         [0111]    by using the key generating unit  201  within the receiver device  200 , generates public information (n,k,α,f) (k denotes the bit length of pq)  
         [0112]    satisfying  
         [0113]    n=p d q (d&gt;1 is odd)  
         [0114]    k: binary length of pq  
         [0115]    αεZ  
         [0116]    f: one-way function  
         [0117]    and outputs the public information over the communication line  300  to send it to the sender device  100  or publicize it. The public information can be publicized using a known method such as, e.g., registration to a third party (public information managing institution). Other information is stored in the memory  205 .  
         [0118]    2. Key Distribution Processing  
         [0119]    (1) The sender A computes  
           C=m   2nα  mod  n   
         [0120]    by using the operation unit  103 , the power computing unit  102 , and the modulo calculation unit  104  within the sender device  100  for plaintext m (0&lt;m&lt;2 K−2 ).  
         [0121]    Furthermore, the sender A obtains the above public information from a third party or the receiver B and computes Jacobi&#39;s symbol a=(m/n) using the operation unit  103 .  
         [0122]    Furthermore, the sender sends ciphertext (C,a) to the receiver device  200  of the receiver B over the communication line  300 , using the communication device  106 .  
         [0123]    Also, the sender computes shared key K=f(m) using the operation unit  103  and the modulo calculation unit  104  within the sender device  100  from a unidirectional function f, which is public information.  
           m     1   ,   p       =       C         (     p   +   1     )        β                   q     -   1         4          mod                 p       ,     
            m     1   ,   q       =       C         (     q   +   1     )        β                   p     -   d         4          mod                 q                             
 
         [0124]    (2) The receiver B computes  
         [0125]    from the ciphertext (C,a), using the above described secret information (p,q,β) held, and the power computing unit  202 , the modulo calculation unit  203 , and the operation unit  204  within the receiver device  200 , and regards as the plaintext m any of φ(m 1,p ,m 1,q ), φ(− 1,p ,m 1,q ), φ(m 1,p ,−m 1,q ), and φ(−m 1,p ,−m 1,q ) that satisfies (x/n)=a and 1&lt;x&lt;2 k−2 , where φ denotes ring isomorphism mapping from Z/(p)×Z/(q) to Z/(pq) by the Chinese remainder theorem. Furthermore, the receiver B computes shared key K=f(m) using the operation unit  204 , from the unidirectional function f, which is public information.  
         [0126]    In the above described public key encryption method, with α and β each set equal to 1, by deleting α and β from public key and secret key respectively, key information in the method of the present embodiment example can be reduced.  
         [0127]    Secret keys p and q can also be generated from expressions p=2p′+1 and q=2q′+1, where p′ and q′ are prime integers.  
         [0128]    In the public key encryption method of the present embodiment example, the value of d (d&gt;1) is changeable depending on a system. Thereby, where the bit length of plaintext m is always small, decryption processing can be performed rapidly by increasing the range of d in a range in which prime factorization of n is intractable.  
       Fifth Embodiment Example  
       [0129]    In this embodiment example, a, which is part of ciphertext in the first embodiment example, is used as a public key.  
         [0130]    [0130]FIG. 1 shows the system configuration of this embodiment example.  
         [0131]    1. Key Generation Processing  
         [0132]    The receiver B in advance generates secret information (p,q,β)  
         [0133]    satisfying  
         [0134]    p, q: prime integers, p≡3 (mod 4), q≡3 (mod 4)  
         [0135]    βεZ, αβ≡1 (mod lcm(p−1,q−1))  
         [0136]    by using the key generating unit  201  within the receiver device  200 , generates public information (n,k,α,a,f) (k denotes the bit length of pq)  
         [0137]    n=p d q (d&gt;1 is odd)  
         [0138]    k: binary length of pq  
         [0139]    αεZ  
         [0140]    αε{−1,1} 
         [0141]    f: one-way function  
         [0142]    satisfying  
         [0143]    and outputs the public information over the communication line  300  to send it to the sender device  100  or publicize it. The public information can be publicized using a known method such as, e.g., registration to a third party (public information managing institution). Other information is stored in the memory  205 .  
         [0144]    2. Key Distribution Processing  
         [0145]    (1) The sender A computes  
           C=m   2nα  mod  n   
         [0146]    by using the operation unit  103 , the power computing unit  102 , and the modulo calculation unit  104  within the sender device  100  for plaintext m (0&lt;m&lt;2 K−2 ) satisfying a=(m/n) (a=(m/n) denotes Jacobi&#39;s symbol).  
         [0147]    Furthermore, the sender sends ciphertext C to the receiver device  200  of the receiver B over the communication line  300 , using the communication device  106 .  
         [0148]    Also, the sender computes shared key K=f(m) using the operation unit  103  and the modulo calculation unit  104  from the unidirectional function f, which is public information.  
         [0149]    (2) The receiver B computes  
           m     1   ,   p       =       C         (     p   +   1     )        β                   q     -   1         4          mod                 p       ,     
            m     1   ,   q       =       C         (     q   +   1     )        β                   p     -   d         4          mod                 q                             
 
         [0150]    from the ciphertext C, using the above described secret information (p,q,β) held, and the power computing unit  202 , the modulo calculation unit  203 , and the operation unit  204  within the receiver device  200 , and regards as the plaintext m any of φ(m 1,p ,m 1,q ), φ(− 1,p ,m 1,q ), φ(m 1,p ,−m 1,q ), and φ(−m 1,p ,−m 1,q ) that satisfies (x/n)=a and 0&lt;x&lt;2 k−2 , where φ denotes ring isomorphism mapping from Z/(p)×Z/(q) to Z/(pq) by the Chinese remainder theorem. Furthermore, the receiver B computes shared key K=f(m) using the operation unit  204 , from the unidirectional function f, which is public information.  
         [0151]    In the above described public key encryption method, with α and β each set equal to 1, by deleting α and β from public key and secret key respectively, key information in the method of the present embodiment example can be reduced.  
         [0152]    Secret keys p and q can also be generated from expressions p=2p′+1 and q=2q′+1, where p′ and q′ are prime integers.  
         [0153]    In the public key encryption method of the present embodiment example, the value of d (d&gt;1) is changeable depending on a system. Thereby, where the bit length of plaintext m is always small, decryption processing can be performed rapidly by increasing the range of d in a range in which prime factorization of n is intractable.  
       Sixth Embodiment Example  
       [0154]    In this embodiment example, a description will be made of how the storage medium with a computing function  400  which has poor computation capability such as an IC card computes ciphertext C, using the sender device  100  having high computation capability in the first to fifth embodiment examples. FIG. 6 outlines this embodiment example.  
         [0155]    The storage medium with a computing function  400  generates plaintext m (0&lt;m&lt;2 K−2 ), using the plaintext creating unit  406 . Furthermore, the storage medium with a computing function  400   
           C   1   =m   2α  mod  n   
         [0156]    computes  
         [0157]    using the power computing unit  401  and the modulo calculation unit  402  from the public keys α and n, and outputs it to the input device  107  of the sender device  100  from the output device  405 .  
         [0158]    The sender device  100  uses the power computing unit  202  and the  
           C=C   1   n  mod  n   
         [0159]    modulo calculation unit  203  to compute ciphertext C by  
       Seventh Embodiment Example  
       [0160]    In this embodiment example, by the transformation method described in the document 12 (described in “Prior Art”), the public key encryption method of the first embodiment example is transformed into a public key encryption method provably secure against adaptive chosen ciphertext attacks.  
         [0161]    [0161]FIG. 1 shows the system configuration of this embodiment example. FIG. 7 outlines this embodiment example.  
         [0162]    1. Key Generation Processing  
         [0163]    The receiver B in advance generates secret information (p,q,β)  
         [0164]    satisfying  
         [0165]    p, q: prime integers, p≡3 (mod 4), q≡3 (mod 4)  
         [0166]    βεZ, αβ≡1 (mod lcm(p−1,q−1))  
         [0167]    by using the key generating unit  201  within the receiver device  200 , generates public information (n,k,k 0 ,k 1 ,α,G,H) (k denotes the bit length of pq) satisfying  
         [0168]    n=p d q (d&gt;1 is odd)  
         [0169]    k, k 0 , k 1 : k is a binary length of pq, and k 0 , k 1  are positive integers with k&gt;k 0 −k 1 −2.  
         [0170]    αεZ  
         [0171]    G: {0,1} k     0   →{0,1} k−k     0   −2  
         [0172]    H: {0,1} k−k     0     −2 →{0,1} k     0      
         [0173]    and outputs the public information over the communication line  300  to send it to the sender device  100  or publicize it. The public information can be publicized using a known method such as, e.g., registration to a third party (public information managing institution). Other information is stored in the memory  205 .  
         [0174]    2. Encryption and Decryption Processing  
         [0175]    (1) The sender A selects a random number r(rε{0,1} k0 } for plaintext m (mε{0,1} 1   , 1=k−k   0 −k 1 −2) by using the random number generating unit  101 , uses the operation unit  103  within the sender device  100  to compute  
           x =( m   0   k     1     ⊙G ( r ))∥( r⊙H ( m   0   k     1     ⊙G ( r ))) 
         [0176]    and further uses the operation unit  103 , the power computing unit  102 ,  
           C=x   2nα  mod  n   
         [0177]    and the modulo calculation unit  104  to compute  
         [0178]    Furthermore, the sender A obtains the above public information from a third party or the receiver B and computes Jacobi&#39;s symbol a=(x/n) using the operation unit  103 .  
         [0179]    Furthermore, the sender A sends ciphertext (C,a) to the receiver device  200  of the receiver B over the communication line  300 , using the communication device  106 .  
         [0180]    (2) The receiver B computes  
           x     1   ,   p       =       C         (     p   +   1     )        β                   q     -   1         4          mod                 p       ,     
            x     1   ,   q       =       C         (     q   +   1     )        β                   p     -   d         4          mod                 q                             
 
         [0181]    from the ciphertext (C,a), using the above described secret information (p,q,β) held, and the power computing unit  202 , the modulo calculation unit  203 , and the operation unit  204  within the receiver device  200 , and computes y that satisfies (y/n)=a and 0&lt;y&lt;2 k−2  of φ(−x 1,p ,x 1,q ), φ(−x 1,p ,x 1,q ), φ(x 1,p ,−x 1,q ), and φ(−x 1,p ,−x 1,q ), where φ denotes ring isomorphism mapping from Z/(p)×Z/(q) to Z/(pq) by the Chinese remainder theorem.  
         [0182]    Furthermore, when  
         y=s∥t ({dot over (s)}ε{0,1} k−k     0     −2 , tε{0,1} k     0   )  
           z=G ( H ( s )⊙ t )⊙ s,   
         [0183]    the operation unit  204  is used to compute  
       m   =     {             [   z   ]     l               if              [   z   ]       k   1       =     0     k   1                   “   reject   ”         otherwise                                 
 
         [0184]    and by  
         [0185]    the plaintext m is decrypted, where [a] k  and [a] k  denote first k-bits and last k-bits of a, respectively.  
         [0186]    By using the above described method, for example, when d=3, it can be proved by equivalence with the difficulty of the problem of prime factorization of n that the public key encryption method is provably secure against adaptive chosen ciphertext attacks (Proved for general trapdoor substitutions in the document 12).  
         [0187]    According to the method of the present embodiment example, decryption processing is performed on a multiplication ring decided from a residue ring modulo pq, which is smaller than n, thereby achieving faster processing in comparison with conventional methods.  
         [0188]    In the above described public key encryption method, with α and β each set equal to 1, by deleting α and β from public key and secret key respectively, key information in the method of the present embodiment example can be reduced.  
         [0189]    Secret keys p and q can also be generated from expressions p=2p′+1 and q=2q′+1, where p′ and q′ are prime integers.  
         [0190]    In the public key encryption method of the present embodiment example, the value of d (d&gt;1) is changeable depending on a system. Thereby, where the bit length of plaintext m is always small, decryption processing can be performed rapidly by increasing the range of d in a range in which prime factorization of n is intractable.  
       Eighth Embodiment Example  
       [0191]    In this embodiment example, a, which is part of ciphertext in the seventh embodiment example, is used as a public key.  
         [0192]    [0192]FIG. 1 shows the system configuration of this embodiment example.  
         [0193]    1. Key Generation Processing  
         [0194]    The receiver B in advance generates secret information (p,q,β)  
         [0195]    p, q: prime integers, p≡3 (mod 4), q≡3 (mod 4)  
         [0196]    βεZ, αβ≡1 (mod lcm(p−1,q−1))  
         [0197]    satisfying  
         [0198]    by using the key generating unit  201  within the receiver device  200 , generates public information (n,k,k 0 ,k 1 ,α,a,G,H) satisfying  
         [0199]    n=p d q (d&gt;1 is odd)  
         [0200]    k,k 0 ,k 1 εZ: k is a binary length of pq, and k 0 ,k 1  are positive integers with k&gt;k 0 −k 1 −2.  
         [0201]    αεZ  
         [0202]    αε{−1,1} 
         [0203]    G: {0,1} k     0   →{0,1} k−k     0     −2    
         [0204]    H: {0,1} k−k     0     −2 →{0,1}   0     
         [0205]    and outputs the public information over the communication line  300  to send it to the sender device  100  or publicize it. The public information can be publicized using a known method such as, e.g., registration to a third party (public information managing institution). Other information is stored in the memory  205 .  
         [0206]    2. Encryption and Decryption Processing  
         [0207]    (1) The sender A selects a random number r(rε{0,1} k0 } for plaintext m (mε{0,1} 1   , 1=k−k   0 −k 1 −2) by using the random number generating unit  101 , uses the operation unit  103  within the sender device  100  to compute the following expression satisfying a=(x/n)  
           x =( m   0   k     1     ⊙G ( r ))∥( r⊙H ( m   0   k     1     ⊙G ( r ))) 
         [0208]    and further uses the operation unit  103 , the power computing unit  102 , and the modulo calculation unit  104  within the sender device  100  to compute  
           C=x   2nα  mod  n.   
         [0209]    Furthermore, the sender A obtains the above public information from a third party or the receiver B and computes Jacobi&#39;s symbol a=(x/n) using the operation unit  103 .  
         [0210]    Furthermore, the sender A sends the ciphertext C to the receiver device  200  of the receiver B over the communication line  300 , using the communication device  106 .  
         [0211]    (2) The receiver B computes  
           x     1   ,   p       =       C         (     p   +   1     )        β                   q     -   1         4          mod                 p       ,     
            x     1   ,   q       =       C         (     q   +   1     )        β                   p     -   d         4          mod                 q                             
 
         [0212]    from the ciphertext C, using the above described secret information (p,q,β) held, and the power computing unit  202 , the modulo calculation unit  203 , and the operation unit  204  within the receiver device  200 , and computes y that satisfies (y/n)=a and 0&lt;y&lt;2 k−2  of φ(x 1,p ,x 1,q ), φ(−x 1,p ,x 1,q ), φ(x 1,p ,−x 1,q ), and φ(−x 1,p ,−x 1,q ), where φ denotes ring isomorphism mapping from Z/(p)×Z/(q) to Z/(pq) by the Chinese remainder theorem.  
         [0213]    Furthermore, when  
         y=s∥t (sε{0,1} k−k     0     −2 , tε{0,1} k     0   )  
           z=G ( H ( s )⊙ t )⊙ s,   
         [0214]    the operation unit  204  is used to compute  
       m   =     {             [   z   ]     l               if              [   z   ]       k   1       =     0     k   1                   “   reject   ”         otherwise                                 
 
         [0215]    and by  
         [0216]    the plaintext m is decrypted, where [a] k  and [a] k  denote first k-bits and last k-bits of a, respectively.  
         [0217]    In the above described public key encryption method, with α and β each set equal to 1, by deleting α and β from public key and secret key respectively, key information in the method of the present embodiment example can be reduced.  
         [0218]    Secret keys p and q can also be generated from expressions p=2p′+1 and q=2q′+1, where p′ and q′ are prime integers.  
         [0219]    In the public key encryption method of the present embodiment example, the value of d (d&gt;1) is changeable depending on a system. Thereby, where the bit length of plaintext m is always small, decryption processing can be performed rapidly by increasing the range of d in a range in which prime factorization of n is intractable.  
       Ninth Embodiment  
       [0220]    In this embodiment example, a description will be made of how the storage medium with a computing function  400  which has poor computation capability such as an IC card computes ciphertext C, using the sender device  100  having high computation capability in the seventh and eighth embodiment examples. FIG. 8 outlines this embodiment example.  
         [0221]    The storage medium with a computing function  400  generates plaintext m (mε{0,1} 1   , 1=k−k   0 −k 1 −2), using the plaintext creating unit  406 . Furthermore, the storage medium with a computing function  400  generates a random number r (rε{0,1} k0 } using the random number  
           x =( m   0   k     1     ⊙G ( r ))∥( r⊙H ( m   0   k     1     ⊙G ( r ))) 
         [0222]    generating unit  407  and uses the operation unit  403  to compute  
         [0223]    from functions G and H. Furthermore, the storage medium with a computing function  400  computes  
           C   1   =x   2α  mod  n   
         [0224]    using the power computing unit  401  and the modulo calculation unit  402  from the public keys α and n, and outputs it to the input device  107  of the sender device  100  from the output device  405 .  
         [0225]    The sender device  100  uses the power computing unit  102  and the modulo calculation unit  104  to compute ciphertext C by  
           C=C   1   n  mod  n   
       Tenth Embodiment  
       [0226]    In this embodiment, a description will be made of a public key encryption method which is a variant of the public key encryption methods of the first to fifth embodiment examples and the seventh and eighth embodiment examples, and is not provably secure but is excellent in the efficiency of encryption and decryption processing.  
         [0227]    In the first to fifth embodiment examples, the operation unit  103  within the sender device  100  is used to compute the ciphertext C by  
           C=m   2α  mod  n   
         [0228]    In the first to fifth embodiment examples, the power computing unit  202 , the modulo calculation unit  203 , and the operation unit  204  within the receiver device  200  are used to compute m 1,p  and m 1,q  from the ciphertext C by  
           m     1   ,   p       =       C         (     p   +   1     )        β                   q     -   1         4          mod                 p       ,     
            m     1   ,   q       =       C         (     q   +   1     )        β                   p     -   d         4          mod                 q                             
 
         [0229]    In the seventh and eighth embodiment examples, the operation unit  103  within the sender device  100  is used to compute the ciphertext C by  
           C=x   2α  mod  n   
         [0230]    and in the seventh and eighth embodiment examples, the power computing unit  202 , the modulo calculation unit  203 , and the operation unit  204  within the receiver device  200  are used to compute m 1,p  and m 1,q  from the ciphertext C by  
           m     1   ,   p       =       C         (     p   +   1     )        β                   q     -   1         4          mod                 p       ,     
            m     1   ,   q       =       C         (     q   +   1     )        β                   p     -   d         4          mod                   q   .                               
 
       Eleventh Embodiment  
       [0231]    In this embodiment, a description will be made of the case where identification information a is omitted in the seventh and eighth embodiments.  
         [0232]    In this case, the sender A selects a random number r(rε{0,1} k0 } for plaintext m (mε{0,1} 1 , 1=k−k 0 −k 1 −2) by using the random number generating unit  101 , uses the operation unit  103  within the sender device  
           x =( m   0   k     1     ⊙G ( r ))∥( r⊙H ( m   0   k     1     G ( r ))) 
         [0233]    [0233] 100  to compute  
         [0234]    and further uses the operation unit  103 , the power computing unit  102 , and the modulo calculation unit  104  within the sender device  100  to compute  
           C=x   2nα  mod  n   
         [0235]    Furthermore, the sender A sends the ciphertext C to the receiver device  200  of the receiver B over the communication line  300 , using the communication device  106 .  
         [0236]    The receiver B computes  
           x     1   ,   p       =       C         (     p   +   1     )        β                   q     -   1         4          mod                 p       ,     
            x     1   ,   q       =       C         (     q   +   1     )        β                   p     -   d         4          mod                 q                             
 
         [0237]    from the ciphertext C, using the above described secret information (p,q,β) held, and the power computing unit  202 , the modulo calculation unit  203 , and the operation unit  204  within the receiver device  200 , and for each of y 1 (x 1,p ,x 1,q ), y 2 (−x 1,p ,x 1,q ), y 3 (x 1,p ,−x 1,q ), and y 4 (−x 1,p ,−x 1,q ), when y i =s i ∥t i  (s i ε{0,1} k−k     0     −2 , t i ε{0,1} k     0   , 1≦i≦4)  
           z   i   =G ( H ( s   i )⊙ t   i )⊙ s   i  (1≦i≦4), 
         [0238]    uses the operation unit  204  to compute  
         [0239]    and decrypts the plaintext m by  
       m   =     {             [   z   ]     l               if              [   z   ]       k   1       =     0     k   1                   “   reject   ”         otherwise                                 
 
         [0240]    φ denotes ring isomorphism mapping from Z/(p)×Z/(q) to Z/(pq) by the Chinese remainder theorem. [a] k  and [a] k  denote first k-bits and last k-bits of a, respectively.  
         [0241]    [0241]FIG. 10 shows comparisons between the method of the eleventh embodiment example and a typical practical public key encryption method in efficiency (the number of modular products) and security. In the comparisons in FIG. 10, α and β each are set equal to 1. Many of data in FIG. 10 are quoted from the document 9.  
       Twelfth Embodiment Example  
       [0242]    In this embodiment example, a description will be made of a public key encryption method by which a public key encryption method described in the document 4 is subjected to a transformation method described in the document 12 to further increase the efficiency of decryption processing.  
         [0243]    [0243]FIG. 1 shows the system configuration of this embodiment example. FIG. 9 outlines this embodiment example.  
         [0244]    1. Key Generation Processing  
         [0245]    The receiver B in advance generates secret information (p i ,β) (1≦i≦h) satisfying  
         [0246]    p i : prime integers (p i ≡3 (mod 4), 1≦i≦h)  
         [0247]    βεZ, αβ≡1 (mod lcm(p−1,q−1))  
         [0248]    by using the key generating unit  201  within the receiver device  200 , generates public information (n,k,k 0 ,k 1 ,α,G,H) satisfying  
         [0249]    n=π i=1   h p i    
         [0250]    k, k 0 , k 1 εZ: k is a bay length of n, and k 0 , k 1  are positive integers with k&gt;k 0 −k 1 −2.  
         [0251]    G: {0,1} k     0   →{0,1} k−k     0      
         [0252]    H: {0,1} k−k     0   →{0,1} k     0      
         [0253]    and outputs the public information over the communication line  300  to send it to the sender device  100  or publicize it. The public information can be publicized using a known method such as, e.g., registration to a third party (public information managing institution). Other information is stored in the memory  205 .  
         [0254]    2. Encryption and Decryption Processing  
         [0255]    The sender A selects a random number r(rε{0,1} k0 } for plaintext m If (mε{0,1} 1 ,1=k−k 0 −k 1 −2) by using the random number generating unit  101  within the sender device  100  to compute  
           x =( m   0   k     1     ⊙G ( r ))∥( r⊙H ( m   0   k     1     ⊙G ( r ))) 
         [0256]    and further obtains the above public information from a third party or the receiver B and uses the operation unit  103 , the power computing unit  102 , and the remainder computing unit  104  to compute  
           C=x   2α  mod  n   
         [0257]    Furthermore, the sender A sends the ciphertext C to the receiver device  200  of the receiver B over the communication line  300 , using the communication device  106 .  
         [0258]    3. Decryption Processing  
         x   i     =       C         (       p   i     +   1     )        β     4          mod                   p   i                             
 
         [0259]    The receiver B computes  
         [0260]    from the ciphertext C, using the above described secret information (p i ,β) (1≦i≦h) held, and the power computing unit  202 , the modulo calculation unit  203 , and the operation unit  204  within the receiver device  200 , and for 2 h  pieces of {φ(e 1 x 1 ,e 2 x 2 , . . . ,e h x h )|e 1 , . . . ,e h ε{−1,1}},  
           y   i   =s   i   ∥t   i (s i ε{0,1} k−k     0   , t i ε{0,1} k     0   , 1≦i≦2 h ) 
         [0261]    when  
           z   i   =G ( H ( s )⊙ t   i )⊙ s   i  (1≦i≦2 h ) 
         [0262]    uses the operation unit  204  to compute  
       m   =     {               [   z   ]     l               if              [   z   ]       k   1       =     0     k   1                   “   reject   ”         otherwise         .                             
 
         [0263]    and decrypts the plaintext m by  
         [0264]    φ denotes ring isomorphism mapping from Z/(p 1 )×Z/(p 2 )× . . . ×Z/(p h ) to Z/(n) by the Chinese remainder theorem. [a] k  and [a] k  denote first k-bits and last k-bits of a, respectively.  
         [0265]    In the above described public key encryption method, with α and β each set equal to 1, by deleting α and β from public key and secret key respectively, key information in the method of the present embodiment example can be reduced.  
         [0266]    By sending identification information such as the magnitudinous relationship of x and n/2, Jacobi&#39;s symbol (x/n) together with the ciphertext (or by creating x according to identification information specified by the public information), efficiency can be increased in decrypting of correct plaintext from 2 h  pieces of {φ(e 1 x 1 ,e 2 x 2 , . . . ,e h x h )|e 1 , . . . ,e h ε{−1,1}}.  
         [0267]    The method of this embodiment example solves the difficult problem of unique decryption, under the assumption that, with the conventional public key encryption method described in the document 4, security is provable in the case where n, which is part of public key, is the product of there or more mutually different prime integers.  
         [0268]    Although the embodiment examples have been described in a general form that a sender and a receiver perform cipher communications using their respective devices, the present invention is actually applied to various systems.  
         [0269]    For example, in an electronic shopping system, a sender is a user and a sender device is a computer such as a personal computer, while a receiver is a retail shop and a receiver device is a computer such as a personal computer. In this case, orders for user products and the like are often encrypted in common key cipher, and an encryption key used at that time is encrypted by the methods of the embodiment examples and sent to the device of the retail shop.  
         [0270]    In an electronic mail system, respective devices are computers such as personal computers, sender&#39;s messages are often encrypted in common key cipher, and an encryption key used at that time is encrypted by the methods of the embodiment examples and sent to a receiver computer.  
         [0271]    The present invention is applicable to other various systems in which conventional public key encryption methods are used.  
         [0272]    Although computations in the embodiment examples are performed by the CPU executing programs within memory, besides by programs, data may be exchanged between a hard-wired computing unit and other computing units, and the CPU.  
         [0273]    According to the present invention, there can be provided a public key encryption method and a key sharing method that are secure against chosen plaintext attacks, and the most powerful adaptive chosen ciphertext attacks, and enable high-speed processing, and devices and a system applying the methods.  
         [0274]    The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense. It will, however, be evident that various modifications and changes may be made thereto without departing from the broader spirit and scope of the invention as set forth in the claims.