Abstract:
A modular exponentiation calculation apparatus obtains a first RNS representation of a value Cp dp ×B mod p based on an RNS representation of a remainder value Cp=C mod p and a remainder value dp=d mod (p−1), obtains a second RNS representation of a value Cq dq ×B mod q based on an RNS representation of a remainder value Cq=C mod q and a remainder value dq=d mod (p−1), obtains a third RNS representation of an integer m′ congruent with C d  mod (p×q) based on both the first and second RNS representations, and obtains m=C d  mod (p×q) based on a value of the integer m′ obtained by converting the third RNS representation into a binary representation.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS  
         [0001]    This application is based upon and claims the benefit of priority from the prior Japanese Patent Application No. 2001-013565, filed Jan. 22, 2001, the entire contents of which are incorporated herein by reference.  
         BACKGROUND OF THE INVENTION  
         [0002]    1. Field of the Invention  
           [0003]    The present invention relates to a modular exponentiation calculation apparatus and modular exponentiation calculation method for obtaining m=C d  mod (p×q) with respect to object data C and independent parameters p, q, d.  
           [0004]    2. Description of the Related Art  
           [0005]    There has been proposed an algorithm and a hardware for uniting and realizing modular multiplication as a basic element for realizing algorithm (modular exponentiation calculation) of a public key cryptography with Montgomery multiplication based on a residue number system (RNS) representation which enables a parallel processing of integer operation (addition/subtraction/multiplication). This will be referred to as RNS Montgomery multiplication.  
           [0006]    The residue number system representation (RNS representation) will be described. For many types of public key cryptography such as an RSA cryptography, a multiple-precision integer is utilized to perform conversion, and a radix representation in which a radix is 2, so-called binary representation, is usually utilized in the representation of the multiple-precision integer. For another representation, a method of preparing a pluraity of moduli a 1 , a 2 , . . . , a n , and representing an integer x by a set of remainder values x 1 , x 2 , . . . , x n  by these moduli as in the following equations is utilized.  
           
         x 
         1 
         =x mod a 
         1  
       
           
         x 
         2 
         =x mod a 
         2  
       
           . . .  
           
         x 
         n 
         =x mod a 
         n  
       
           [0007]    This representation method is called an RNS representation.  
           [0008]    A group of moduli for use in the RNS representation will hereinafter be referred to as a base. Moreover, an element number n of the base will be referred to as a base size. The base “a” having a base size of n is represented as follows.  
             a={a   1   , a   2   , . . . , a   n } 
           [0009]    In the RNS representation, positive integers prime to one another are usually used, and Chinese remainder theorem guarantees that the positive integer less than a product of elements of the base can uniformly be represented by the RNS representation. That is, when the base is a={a 1 , a 2 , . . . , a n }, and the product of elements of the base “a” is A=a 1 ×a 2 ×. . . ×a n , the positive integer less than A can be represented by the RNS representation using the base “a”.  
           [0010]    In the following, n integers x subjected to the RNS representation using the base “a” are represented by &lt;x&gt; a  (sometimes represented by &lt;x&gt; in which the base is omitted). That is, the following results.  
             &lt;x&gt;   a =( x   a1   , x   a2   , . . . , x   an )=( x mod a   1   , x mod a   2   , . . . , x mod a   n )  
           [0011]    Additionally, when two types of bases are used in the following operation, with respect to bases a={a 1 , a 2 , . . . , a n1 } and b={b 1 , b 2 , . . . , b n2 }, a∪b denotes a combination of {a 1 , a 2 , . . . , a n1 } and {b 1 , b 2 , . . . , b n2 }, and &lt;x&gt; a∪b  denotes the RNS representation of x by the base a∪b (i.e., &lt;x&gt; a∪b  denotes a combination of &lt;x&gt; a =(x mod a 1 , x mod a 2 , . . . , x mod a n1 ) and &lt;x&gt; b =(x mod b 1 , x mod b 2 , . . . , x mod b n2 ). Moreover, in the following description, for the sake of convenience two types of bases will be described as n1=n2=n. Additionally, n1, n2 do not have to be equal to n.  
           [0012]    The RNS representation is advantageous in that addition, subtraction, and multiplication can easily be carried out using the product “A” of all the elements of the base. That is, desired results are obtained as results of independent addition, subtraction, and multiplication of the respective elements by the respective moduli as follows.  
             &lt;x&gt;   a   +&lt;y&gt;   a =( x   a1   +y   a1   , x   a2   +y   a2   , . . . , x   an   +y   an )  
             &lt;x&gt;   a   −&lt;y&gt;   a =( x   a1   −y   a1   , x   a2   −y   a2   , . . . , x   an   −y   an )  
             &lt;x&gt;   a   ×&lt;y&gt;   a =( x   a1   ×y   a1   , x   a2   ×y   a2   , . . . , x   an   ×y   an )  
           [0013]    Additionally, the above operations will be referred to as RNS addition, RNS subtraction, and RNS multiplication, respectively. A left side is mod A, and respective terms of a right side are mod a 1 , mod a 2 , . . . , mod a n .  
           [0014]    Therefore, n operations can be processed in parallel. When n operation units are prepared, all the operations are processed in parallel, and a fast processing is realized. Even when the number of prepared operation units is less than n, an operation speed can be enhanced in proportional to the number of units of 1 to n.  
           [0015]    RNS Montgomery multiplication and RNS Montgomery exponentiation will next be described.  
           [0016]    The RNS Montgomery multiplication is a method of applying a method called Montgomery multiplication to the operation in the RNS representation with respect to multiplication &lt;x&gt; a∪b ×&lt;y&gt; a∪b  with a remainder in mudulus N, and is generally carried out in the following procedure.  
           [0017]    The RNS Montgomery multiplication is represented by MM(&lt;x&gt; a∪b , &lt;y&gt; a∪b , N, a∪b).  
           [0018]    Here, inputs are &lt;x&gt; a∪b , &lt;y&gt; a∪b , N. Additionally, x and y are both less than 2N.  
           [0019]    Bases are a, b. Additionally, x, y, N are all less than A, and less than B.  
           [0020]    An output is &lt;w&gt; a∪b . Additionally, w=(x×y×B −1  mod N)+N. Moreover, there is not +N in some case.  
           [0021]    &lt;Processing Content&gt; 
           [0022]    step-M-0: &lt;−N −1 &gt; b  is calculated.  
           [0023]    step-M-1: &lt;s&gt; a =&lt;x&gt; a ×&lt;y&gt; a  is calculated.  
           [0024]    step-M-2: &lt;s&gt; b &lt;x&gt; b ×&lt;y&gt; b  is calculated.  
           [0025]    step-M-3: &lt;t&gt; b =&lt;s&gt; b ×&lt;−N −1 &gt; b  is calculated.  
           [0026]    step-M-4: &lt;t&gt; b  is base-converted to &lt;t&gt; a .  
           [0027]    step-M-5: &lt;u&gt; a =&lt;t&gt; a ×&lt;N&gt; a  is calculated.  
           [0028]    step-M-6: &lt;v&gt; a &lt;s&gt; a +&lt;u&gt; a  is calculated.  
           [0029]    step-M-7: &lt;w&gt; a =&lt;v&gt; a ×&lt;B −1 &gt; a  is calculated.  
           [0030]    step-M-8: &lt;w&gt; a  is base-converted to &lt;w&gt; b .  
           [0031]    Additionally, in the above procedure, the base conversion of the step-M-4 or step-M-8 is a processing for obtaining the RNS representation by another base (e.g., RNS representation &lt;t&gt; a  by a base “a”) of a certain integer corresponding to the RNS representation by a certain base (e.g., integer t corresponding to RNS representation &lt;t&gt; b  by the base “b”).  
           [0032]    An RNS Montgomery multiplier can also realize a fast processing by increasing the operation unit for performing the processing in parallel.  
           [0033]    Moreover, there has been proposed a method of repeatedly performing the RNS Montgomery multiplication (repeatedly utilizing the RNS Montgomery multiplier) to perform an exponentiation calculation; and constituting a cryptography processing of an RSA cryptography. This exponentiation calculation method will be referred to as the RNS Montgomery exponentiation. The RNS Montgomery exponentiation is generally carried out in the following procedure.  
           [0034]    The RNS Montgomery exponentiation is represented by MEXP (&lt;x&gt; a∪b , d, N, a∪b).  
           [0035]    Here, an input is &lt;x&gt; a∪b , exponent (binary representation) is d=(d k , d k−1 , . . . , d 1 ), and modulus is N. Additionally x&lt;2N.  
           [0036]    Bases are a, b. Additionally, x, N are both less than A, and less than B.  
           [0037]    An output is &lt;y&gt; a∪b . Additionally, y=x d ×B −(d−1)  mod N.  
           [0038]    &lt;Processing Content&gt; 
           [0039]    step-E-1: i=k is set. &lt;y&gt; a∪b =&lt;B&gt; a∪b  is set.  
           [0040]    step-E-2: &lt;y&gt; a∪b =MM (&lt;y&gt; a∪b , &lt;y&gt; a∪b , N, a∪b) is calculated.  
           [0041]    step-E-3: If d i =1, &lt;y&gt; a∪b =MM (&lt;y&gt; a∪b , &lt;x&gt; a∪b , N, a∪b) is calculated. If d i ≠1, nothing is carried out (nop).  
           [0042]    step-E-4: i=i−1 is set.  
           [0043]    step-E-5: If i=0, the procedure ends. If i≠0, the procedure returns to step-E-2.  
           [0044]    Additionally, in the above procedure, MM( ) in the step-E-2 and step-E-3 denotes the aforementioned RNS Montgomery multiplication.  
           [0045]    A CRT modular exponentiation calculation will next be described.  
           [0046]    For the RSA cryptography, with respect to a public key (N, e), and secret key (d, p, q), a plaintext m is enciphered into a ciphertext C with C=m e  mod N, and the ciphertext C is deciphered into the plaintext m with m=C d  mod N. Here, an exponentiation calculation method which utilizes secret prime factors p, q of a modulus N as the public key to efficiently execute decipherment, that is, which utilizes a Chinese remainder theorem (CRT) is known. This exponentiation calculation method will be referred to as the CRT modular exponentiation calculation.  
           [0047]    &lt;CRT Modular Exponentiation Calculation Procedure&gt; 
           [0048]    step-C-1: d p =d mod (p−1)  
           [0049]    d q =d mod (q−1)  
           [0050]    step-C-2: C p =C mod p  
           [0051]    C q =C mod q  
           [0052]    step-C-3: m p =C p   dp  mod p  
           [0053]    m q =C q   dq  mod q  
           [0054]    step-C-4: m=m p ×(q −1  mod p)×q+m q×(p   −1  mod q)×p (mod N)  
           [0055]    Additionally, in the above procedure, since parameters d p , d q , (q −1  mod p), (p −1  mod q) depend only on the secret key, the parameters are generally calculated beforehand and stored as a part of the secret key.  
           [0056]    Noting that a dominant portion of a calculation amount of the CRT modular exponentiation calculation corresponds to two modular exponentiation calculations of the step-C-3, and the modular exponentiation calculation is proportional to a cube of a size of the modulus, it is seen that the calculation amount of the modular exponentiation calculation in the binary representation and CRT modular exponentiation calculation is about ¼ (={fraction (2/8)}). Additionally, when the modular exponentiation calculation of the step-C-3 is simultaneously executed in two calculation circuits, a calculation time can be expected to be reduced to about ⅛.  
           [0057]    However, a concrete method for realizing the CRT modular exponentiation calculation of the step-C-1 to step-C-4 by the RNS Montgomery multiplication has not been realized, and it has been difficult to raise a speed of the modular exponentiation calculation of a large integer such as RSA decipherment (secret conversion).  
         BRIEF SUMMARY OF THE INVENTION  
         [0058]    According to the present invention, there is provided a modular exponentiation calculation apparatus or modular exponentiation calculation method in which a modular exponentiation calculation is efficiently executed.  
           [0059]    According to an embodiment of the present invention, a modular exponentiation calculation apparatus which utilizes a residue number system representation by a first base and a second base including sets of a plurality of integers with respect to object data C and parameters p, q, d (all integers included in both the bases are mutually primary, a product “A” of all the integers of the first base is A&gt;p, A&gt;q, a product “B” of all the integers of the second base is B&gt;p, B&gt;q, and A×B&gt;C) to obtain a calculation result m=C d  mod (p×q), the apparatus comprising:  
           [0060]    a first processing unit configured to obtain a residue number system representation of a value Cp dp ×B mod p or a value with p added thereto based on a residue number system representation of a remainder value Cp=C mod p by p of the data C and a remainder value dp=d mod (p−1) by (p−1) of the parameter d;  
           [0061]    a second processing unit configured to obtain a residue number system representation of a value Cq dq ×B mod q or a value with q added thereto based on a residue number system representation of a remainder value Cq=C mod q by q of the data C and a remainder value dq=d mod (p−1) by (q−1) of the parameter d;  
           [0062]    a third processing unit configured to obtain a residue number system representation of an integer m′ congruent with C d  mod (p×q) based on both the residue number system representations obtained by the first and second processing units; and  
           [0063]    a fourth processing unit configured to obtain the calculation result m based on a value of the integer m′ obtained by converting the residue number system representation obtained by the third processing unit into a binary representation. 
       
    
    
     BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWING  
       [0064]    [0064]FIG. 1 is a diagram showing a functional constitution example of a modular exponentiation calculation apparatus according to a first embodiment of the present invention;  
         [0065]    [0065]FIG. 2 is a flowchart showing one example of a processing procedure of the calculation apparatus of FIG. 1;  
         [0066]    [0066]FIG. 3 is a diagram showing an internal constitution example relating to each operation unit of the calculation apparatus of FIG. 1;  
         [0067]    [0067]FIG. 4 is a part of the flowchart showing another example of the processing procedure of the calculation apparatus according to the embodiment in FIG. 2;  
         [0068]    [0068]FIG. 5 is a diagram showing an internal constitution example relating to each operation unit of the modular exponentiation calculation apparatus according to another embodiment;  
         [0069]    [0069]FIG. 6 is a diagram showing a functional constitution example of the modular exponentiation calculation apparatus according to still another embodiment;  
         [0070]    [0070]FIG. 7 is a diagram showing an internal constitution example relating to each operation unit of the modular exponentiation calculation apparatus according to still further embodiment; and  
         [0071]    [0071]FIG. 8 is an explanatory view of an enciphering system using the above embodiments. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0072]    An embodiment of a modular exponentiation calculation apparatus or method according to the present invention will now be described with reference to the accompanying drawings.  
         [0073]    First Embodiment  
         [0074]    [0074]FIG. 1 shows a functional constitution diagram of a calculation apparatus according to one embodiment of the present invention.  
         [0075]    A calculation apparatus  1  of the present embodiment comprises an RNS operator  12  for calculating an RNS represented integer; an operator  14  for performing an auxiliary operation in a binary representation; an input/output unit  11  for performing input/output with the external device; and a controller  13  for controlling the entire constitution.  
         [0076]    The RNS operator  12  includes an RNS inverse element calculator  122 ; RNS Montgomery multiplier  123 ; RNS Montgomery exponentiation calculator  124 ; RNS multiplier  125 ; RNS adder  126 ; first representation converter (binary representation to RNS representation)  127 ; second representation converter (RNS representation to binary representation)  128 ; and storage  121 .  
         [0077]    The auxiliary operator  14  in the binary representation includes a remainder calculator  141 ; and adder/subtracter  142 .  
         [0078]    In the aforementioned operation units, the RNS operator  12  occupies a greater part in scale.  
         [0079]    The storage  121  is constituted, for example, of ROM and RAM for storing bases utilized in the RNS representation, parameters calculated beforehand and stored in the apparatus, and the like.  
         [0080]    The RNS Montgomery multiplier  123  performs the aforementioned RNS Montgomery multiplication of step-M-0 to step-M-8.  
         [0081]    The RNS Montgomery exponentiation calculator  124  performs the aforementioned Montgomery exponentiation of step-E-1 to step-E-5.  
         [0082]    The RNS multiplier  125  performs the aforementioned RNS multiplication.  
         [0083]    The RNS adder  126  performs the aforementioned RNS addition.  
         [0084]    The first representation converter  127  converts a binary representation to an RNS representation.  
         [0085]    The second representation converter  128  converts the RNS representation to the binary representation.  
         [0086]    Additionally, these are described in detail, for example, in Document 1 “Cox-Rower Architecture for Fast Parallel Montgomery Multiplication”, Kawamura, Koike, Sano, and Shimbo, EUROCRYPT 2000 LNCS 1807, pp. 523-538, 2000.  
         [0087]    The RNS inverse element calculator  122  calculates &lt;−x −1 &gt; a  using &lt;x&gt; a  as an input. That is, −x i   −1  is calculated from x i  with respect to each base a i  and element x i  of &lt;x&gt; a  (mod a i ). Concretely, the calculation is executed in the following procedure.  
         [0088]    &lt;Inverse Element Calculation in Base a i &gt; 
         [0089]    step 0: Carmichael function λ(a i ) is calculated with respect to the base a i , and stored in the storage  121 . A concrete equation of Carmichael function λ is represented as follows. This calculation is described in “Contemporary Cryptography”, Sangyo Tosyo, p. 16, authored by Tatsuaki Okamoto, Hirotsuke Yamamoto. A bit size of λ(a i ) is not more than a bit size of a i .  
         [0090]    The following is [Fermat small theorem].  
         [0091]    Assuming that a prime number is p, a p−1 ≡1(mod p) is established with respect to an arbitrary integer a∈Z p  other than 0.  
         [0092]    Based on this theorem Euler function ψ(n) with respect to an integer n is the number of elements of Z* n . For examples when p, q have different odd numbers of elements, ψ(p)=p−1, ψ(p e )=p e−1 (p−1), ψ(pq)=(p−1) (q−1).  
         [0093]    Carmichael function λ(n) with respect to the integer n is defined as follows. When n=2 eo p e1   1 , . . . , p er   r  (p 1 , . . . , p r  have different odd numbers of elements)  
               λ        (   n   )       =     LCM        (       λ        (     2   eo     )       ,     ψ        (     p   1     e                 1       )       ,   …              ,     ψ        (     p   r   er     )         )                     λ        (     2   t     )       =         2     t   -   1                     if                 t     &lt;   3                 =         2     t   -   2                     if                 t     ≧   3                                 
 
         [0094]    With respect to all x(&lt;a i ) prime to modulus a i , x λ(ai) =1 (mod a i ) is obtained. Here, the input x is assumed as secret keys p, q (prime numbers) or a product N (product of two prime numbers) of an RSA cryptography. Then, these are necessarily prime to the modulus a i .  
         [0095]    step 1: x i   −1 =x i   λ(ai)−1  is calculated by modular multiplication in the operation unit (mod a i ).  
         [0096]    step 2:−x i   −1 =a i −x i   −1  is calculated.  
         [0097]    In the above calculation, in the step 1, the bit size of the Carmichael function λ(a i ) is not more than the bit size of a i . Therefore, when the number of words of the operation unit is set to 32 bits, the number of modular multiplication is 64 or less.  
         [0098]    In the remainder calculator  141 , a dividend x and divisor y of the binary representation are inputted, and x mod y is calculated. This calculation procedure can be executed by usual division, and described, for example, in “The art of computer programming”, Addison Wesley Longman, Inc., pp. 342-345 authored by Donald E. Knuth. The calculation amount is substantially the same as that of x1×x2.  
         [0099]    The adder/subtracter  142  performs binary addition/subtraction.  
         [0100]    The calculation apparatus  1  combines the following RNS operations and executes CRT exponentiation.  
         [0101]    RNS Montgomery multiplication &lt;z&gt;=MM(&lt;x&gt; a∪b , &lt;y&gt; a∪b , p, a∪b)  
         [0102]    Here, z=x×y×B −1  mod p, or  
           z =( x×y×B   −1    mod p ) +p.    
         [0103]    RNS Montgomery exponentiation &lt;z&gt;=MEXP(&lt;x&gt; a∪b , e, p, a∪b)  
         [0104]    Here, z=x e ×B −(e−1)  mod p, or  
           z =( x   e   ×B   −(e−1)    mod p ) +p.    
         [0105]    RNS multiplication &lt;z&gt;=MUL(&lt;x&gt; a , &lt;y&gt; a , a)  
         [0106]    Here, z=x×y mod A (multiplication of x and y in the base “a”).  
         [0107]    RNS addition &lt;z&gt;=ADD(&lt;x&gt; a , &lt;y&gt; a , a)  
         [0108]    Here, z=x+y mod A (addition of x and y in the base “a”).  
         [0109]    A last argument (a, a∪b, and the like) in the RNS operation denotes the base utilized in the RNS representation. Assuming that a value of the product of elements of the base “a” is A, and a value of the product of elements of the base “b” is B, a value of the product of elements of the base a∪b is A×B. Outputs of the RNS Montgomery multiplication and RNS Montgomery exponentiation are z&lt;A and z&lt;B.  
         [0110]    As described above, in the RNS Montgomery multiplication and RNS Montgomery exponentiation, only a value of modulus p sometimes has a large result from a property of the Montgomery multiplication. That is, MM(&lt;x&gt;, &lt;y&gt;, p, a∪b)&lt;2p and MEXP(&lt;x&gt; a∪b , e, p, a∪b)&lt;2p. When the modulus p is fixed, the output of the RNS Montgomery multiplication or the RNS Montgomery exponentiation is less than 2p, but this output can be inputted to the RNS Montgomery multiplication or the RNS Montgomery exponentiation as it is.  
         [0111]    The following parameters are stored beforehand in the calculation apparatus  1 .  
         [0112]    Pre-registered parameters: base “a”, base “b”, product “A” of elements of the base “a”, product “B” of elements of the base “b”, product “A”×“B” of all elements of the bases “a” and “b”, “B 2 ”, “&lt;B −1 &gt; a ”.  
         [0113]    Additionally, as a relation of a parameter size in the bases “a”, “b” and CRT exponentiation, at least p&lt;A, q&lt;A, and p&lt;B, q&lt;B are necessary. As a result, with respect to N=p×q, at least N&lt;A×B.  
         [0114]    Here, the parameters inputted to the calculation apparatus  1  from the outside in order to execute the CRT exponentiation are as follows.  
         [0115]    External input parameters: ciphertext C, d p =d mod (p−1), d q =d mod (q−1), N (=p×q), p, q, inverse element pinv=p −1  mod q in the modulus q of p, inverse element qinv=q −1  mod p in the modulus p of q  
         [0116]    [0116]FIG. 2 shows one example of a processing procedure of the CRT exponentiation in the calculation apparatus  1 . Moreover, FIG. 3 shows an internal constitution example relating to each operation unit of the calculation apparatus  1 .  
         [0117]    Step S 0 : The external input parameters C, dp, dq, N. p, q, pinv, qinv are inputted.  
         [0118]    In the following procedure, in steps S 1 -p to S 9 -p, and S 1 -q to S 9 -q, and also in either corresponding step S 1 -p or S 1 -q, similar operation relating to two prime factors p and q of N is executed.  
         [0119]    Step S 1 -p: The first representation converter  127  is utilized to convert the binary representation p to the RNS representation &lt;p&gt; by the base a∪b (=&lt;p&gt; a  ∪&lt;p&gt; b ={p mod a 1 , p mod a 2 , . . . , p mod a n } ∪ {p mod b 1 , p mod b 2 , . . . , p mod b n }).  
         [0120]    Step S 1 -q: The first representation converter  127  is utilized to convert the binary representation q to the RNS representation &lt;q&gt; by the base a∪b (=&lt;q&gt; a  ∪&lt;q&gt; b ={q mod a 1 , q mod a 2 , . . . , q mod a n } ∪ {q mod b 1 , q mod b 2 , . . . , q mod b n }) by the base a∪b.  
         [0121]    Step S 2 -p: The RNS inverse element calculator  122  is utilized to calculate &lt;−p −1 &gt; b  from &lt;p&gt; b  obtained by the step S 1 -p.  
         [0122]    Step: S 2 -q: The RNS inverse element calculator  122  is utilized to calculate &lt;−q −1 &gt; b  from &lt;q&gt; b  obtained by the step S 1 -q.  
         [0123]    Step S 3 -p: The remainder calculator  141  is utilized to calculate bp=B 2  mod p, and the first representation converter  127  is utilized to convert bp to the RNS representation &lt;bp&gt;by the base a∪b from the binary representation.  
         [0124]    Step S 3 -q: The remainder calculator  141  is utilized to calculate bq=B 2  mod q, and the first representation converter  127  is utilized to convert bq to the RNS representation &lt;bq&gt; by the base a∪b from the binary representation.  
         [0125]    Step S 4 -p: The first representation converter  127  is utilized to convert pinv to the RNS representation &lt;pinv&gt; by the base a∪b from the binary representation.  
         [0126]    Step S 4 -q: The first representation converter  127  is utilized to convert qinv to the RNS representation &lt;qinv&gt; by the base a∪b from the binary representation.  
         [0127]    Step S 5 -p: The remainder calculator  141  is utilized to calculate Cp=C mod p, and the first representation converter  127  is utilized to convert Cp to the RNS representation &lt;Cp&gt; by the base a∪b from the binary representation.  
         [0128]    Step S 5 -q: The remainder calculator  141  is utilized to calculate Cq=C mod q, and the first representation converter  127  is utilized to convert Cq to the RNS representation &lt;Cq&gt; by the base a∪b from the binary representation.  
         [0129]    Step S 6 -p: The RNS Montgomery multiplier  123  is utilized to calculate &lt;Cp′&gt;=MM(&lt;Cp&gt;, &lt;bp&gt;, p, a∪b).  
         [0130]    &lt;Processing Content with use of the Aforementioned Algorithm&gt; 
         [0131]    step-M-1: &lt;s&gt; a =&lt;Cp&gt; a ×&lt;bp&gt; a  is calculated.  
         [0132]    step-M-2: &lt;s&gt; b =&lt;Cp&gt; b ×&lt;bp&gt; b  is calculated.  
         [0133]    step-M-3: &lt;t&gt; b =&lt;s&gt; b ×&lt;−p −1 &gt; b  is calculated.  
         [0134]    step-M-4: &lt;t&gt; b  is base-converted to &lt;t&gt; a .  
         [0135]    step-N-5: &lt;u&gt; a =&lt;t&gt; a ×&lt;p&gt; a  is calculated.  
         [0136]    step-M-6: &lt;v&gt; a =&lt;s&gt; a +&lt;u&gt; a  is calculated.  
         [0137]    step-M-7: &lt;Cp′&gt; a =&lt;v&gt; a ×&lt;B −1 &gt; a  is calculated.  
         [0138]    step-M-8: &lt;Cp′&gt; a  is base-converted to &lt;Cp′&gt; b .  
         [0139]    Thereby, RNS representation &lt;Cp′&gt; corresponding to either Cp′=C×B mod p or Cp′=(C×B mod p)+p is obtained.  
         [0140]    Step S 6 -q: The RNS Montgomery multiplier  123  is utilized to calculate &lt;Cq′&gt;=MM(&lt;Cq&gt;, &lt;bq&gt;, q, a∪b). Additionally, when the aforementioned algorithm is utilized, the processing content is constituted by replacing p with q in the processing content of the step S 6 -p.  
         [0141]    Thereby, RNS representation &lt;Cq′&gt; corresponding to either Cq′=C×B mod q or Cq′=(C×B mod q)+q is obtained.  
         [0142]    Step S 7 -p: The RNS Montgomery exponentiation calculator  124  is utilized to calculate &lt;mp′&gt;=MEXP(&lt;Cp′&gt;, dp, p, a∪b).  
         [0143]    &lt;Processing Content with use of the Aforementioned Algorithm&gt; 
         [0144]    step-E-1: i=k is set. &lt;y&gt; a∪b =&lt;B&gt; a∪b  is set.  
         [0145]    step-E-2: &lt;y&gt; a∪b =MM(&lt;y&gt; a∪b , &lt;y&gt; a∪b , p, a∪b) is calculated.  
         [0146]    step-E-3: If dp i =1, &lt;y&gt; a∪b =MM(&lt;y&gt; a∪b , &lt;Cp′&gt; a∪b , p, a∪b) is calculated. If dp i ≠1, nothing is processed (nop).  
         [0147]    Here, dp i  is a value of a lower i-th bit in binary representation (dp k , dp k−1 , . . . , dp 1 ) of dp.  
         [0148]    step-E-4: i=i−1 is set.  
         [0149]    step-E-5: If i=0, the procedure ends. If i≠0, the procedure returns to the step-E-2.  
         [0150]    Thereby, RNS representation &lt;mp′&gt; corresponding to mp′=Cp dp ×B mod p or mp′=(Cp dp ×B mod p)+p is obtained.  
         [0151]    Step S 7 -q: The RNS Montgomery exponentiation calculator  124  is utilized to calculate &lt;mq′&gt;=MEXP(&lt;Cq′&gt;, dq, q, a∪b). Additionally, when the aforementioned algorithm is utilized, the processing content is constituted by replacing p with q in the processing content of the step S 7 -p.  
         [0152]    Thereby, RNS representation &lt;mq′&gt;corresponding to either mq′=Cq dq ×B mod q or mq′=(Cq dq ×B mod q)+q is obtained.  
         [0153]    Step S 8 -p: The RNS Montgomery multiplier  123  is utilized to calculate &lt;tp&gt;=MM(&lt;mp′&gt;, &lt;q −1  mod p&gt;, p, a∪b).  
         [0154]    &lt;Processing Content with use of the Aforementioned Algorithm&gt; 
         [0155]    step-M-1: &lt;s&gt; a =&lt;mp′&gt; a ×&lt;qinv&gt; a  is calculated.  
         [0156]    step-M-2: &lt;s&gt; b =&lt;mp′&gt; b ×&lt;qinv&gt; b  is calculated.  
         [0157]    step-M-3: &lt;t&gt; b =&lt;s&gt; b ×&lt;−p −1 &gt; b  is calculated.  
         [0158]    step-M-4: &lt;t&gt; b  is base-converted to &lt;t&gt; a .  
         [0159]    step-M-5: &lt;u&gt; a =&lt;t&gt; a ×&lt;p&gt; a  is calculated.  
         [0160]    step-M-6: &lt;v&gt; a =&lt;s&gt; a +&lt;u&gt; a  is calculated.  
         [0161]    step-M-7: &lt;tp&gt; a =&lt;v&gt; a ×&lt;B −1 &gt; a  is calculated.  
         [0162]    step-M-8: &lt;tp&gt; a  is base-converted to &lt;tp&gt; b .  
         [0163]    Thereby, the RNS representation &lt;tp&gt; corresponding to either tp=Cp dp ×q −1  mod p or tp=(Cp dp ×q −1  mod p)+p is obtained.  
         [0164]    Step S 8 -q: The RNS Montgomery multiplier  123  is utilized to calculate &lt;tq&gt;=MM(&lt;mq′&gt;, &lt;p −1  mod q&gt;, q, a∪b). Additionally, when the aforementioned algorithm is utilized, the processing content is constituted by replacing p with q in the processing content of the step S 8 -p.  
         [0165]    Thereby, the RNS representation &lt;tq&gt; corresponding to either tq=Cq dq ×p −1  mod q or tq=(Cq dq ×p −1  mod q)+q is obtained.  
         [0166]    Step S 9 -p: The RNS multiplier  125  is utilized to calculate &lt;up&gt;=MUL(&lt;tp&gt;, &lt;q&gt;, a∪b).  
         [0167]    Thereby, the RNS representation &lt;up&gt; corresponding to up=tp×q mod (A×B) is obtained.  
         [0168]    Step S 9 -q: The RNS multiplier  125  is utilized to calculate &lt;uq&gt;=MUL(&lt;tq&gt;, &lt;p&gt;, a∪b).  
         [0169]    Thereby, the RNS representation &lt;uq&gt; corresponding to uq=tq×p mod (A×B) is obtained.  
         [0170]    Step S 10 : The RNS adder  126  is utilized to calculate &lt;m′&gt;=ADD(&lt;up&gt;, &lt;uq&gt;, a∪b).  
         [0171]    Thereby, the RNS representation &lt;m′&gt; corresponding to m′=up+uq mod (A×B) is obtained.  
         [0172]    Step  11 : The second representation converter  128  is utilized to convert &lt;m′&gt; to the binary representation m′ from the RNS representation (base a∪b).  
         [0173]    Here, m′ is not less than N in some case. Therefore, when m′ is not less than N, the adder/subtracter  142  performs a processing for setting the value to be less than N.  
         [0174]    Step S 12 : m′ is copied to m (stored).  
         [0175]    Step S 13 : m′=m′−N is calculated.  
         [0176]    Step S 14 : It is determined whether or not m′&lt;0. Unless m′&lt;0, the procedure returns to the step S 12 . If m′&lt;0, the procedure comes out of a loop and shifts to step S 15 .  
         [0177]    Step S 15 : m is outputted, and the procedure is ended.  
         [0178]    Additionally, instead of the steps S 12  to S 15 , for example, other procedure such as steps S 21  to S 24  of FIG. 4 may be used.  
         [0179]    Moreover, instead of inputting N from the outside, the adder/subtracter  142  may obtain N by p×q.  
         [0180]    In the procedure, in the steps S 5 -p, S 6 -p and steps S 5 -q, S 6 -q, Cp′=C×B mod p (+p) and Cq′=C×B mod q (+q) are calculated, and the processing corresponds to the aforementioned processing of the step-C-2 in the usual CRT exponentiation.  
         [0181]    The processing of the steps S 7 -p and S 7 -q corresponds to the processing of step-C-3 in the usual CRT exponentiation.  
         [0182]    The processing of the steps S 8 -p, S 9 -p, S 8 -q, S 9 -q, S 10  corresponds to the processing of step-C-4 in the aforementioned usual CRT exponentiation. Here, the processing of the step-C-4 can be modified as follows, and this respect is utilized.  
             m   =                  mp   ×     (       q     -   1          mod                 p     )     ×   q     +     mq   ×     (       p     -   1          mod                 q     )     ×   p                                    {     mp   ×     (       q     -   1          mod                 p     )        mod                 p     }     ×   q     +       {     mq   ×     (       p     -   1          mod                 q     )        mod                 q     }     ×     p        (     mod                 N     )                                       
 
         [0183]    q) mod q}×p (mod N)  
         [0184]    If there is no addition error of p and q in the RNS Montgomery multiplication, m′ as a result of the step S 11  has a relation of m′&lt;2N in the CRT modular exponentiation calculation. Therefore, if the addition error is considered, m′&lt;4N results. Therefore, it is necessary to subtract 3N at maximum from m′, and a necessary correction is performed in the steps S 12  to S 14 . Since m′ is converted to a binary number, it is easy to determine a positive/negative sign. This processing corresponds to the procedure for obtaining the remainder value in the modulus N in the processing of step-C-4 in the usual CRT exponentiation described in the product.  
         [0185]    Each calculation step of the CRT modular exponentiation calculation can be executed using an operation function which can be executed by the RNS operator  12 . Particularly the RNS Montgomery exponentiation of the steps S 7 -p and S 7 -q occupies a large part of the calculation processing, and it is important to utilize a sum group a∪b as a base in which bases a, b slightly larger than moduli p, q are used.  
         [0186]    The calculation amount of the RNS Montgomery multiplication can be evaluated by the calculation amount of the base conversion executed in the multiplication. This processing requires the multiplication of the word size by an order of a base size n, when one base element is considered. Furthermore, this processing is executed for all base elements in the base to be converted. Therefore, the calculation amount of the RNS Montgomery multiplication is of the order of square of the base size n. Moreover, the calculation amount of the RNS Montgomery exponentiation corresponds to that of a processing for repeating the RNS Montgomery multiplication by a bit size L_e of the exponent. Therefore, the calculation amount of the RNS Montgomery exponentiation is O(n 2 ×L_e).  
         [0187]    Concretely, for example, an RSA cryptography of 1024 bits is assumed. In this case, each of secret key d, N and ciphertext C is of 1024 bits. Therefore, when this is executed in the Montgomery exponentiation in the RNS representation as in a conventional method, the base a′ (and b′) for use has the number of elements  33  (=1024/32 (word size)+1) at minimum. On the other hand, each of values Cp, Cq obtained by reducing secret keys dp, dq, p, q, C utilized in the CRT exponentiation as described in the embodiment by the moduli p, q is of 512 bits. Therefore, the base “a” (and “b”) to be utilized has the number of elements  17  (=512/32 (word size)+1) at minimum. It is most efficient for the processing time to utilize the minimum base element number. On this assumption, the calculation amount of the modular exponentiation calculation by the CRT is compared with that of the modular exponentiation calculation which does not use the CRT. The calculation amount of the RNS Montgomery multiplication of a case in which the CRT is used is ¼ of the calculation amount in a case in which the CRT is not used. The size of the exponent in the case in which the CRT is used is ½ of the calculation amount in the case in which the CRT is not used. When the CRT is used, it is necessary to calculate the RNS Montgomery exponentiation twice. Therefore, as a whole, according to the CRT modular exponentiation calculation, RSA deciphering operation can be realized with a processing amount of about ¼ as compared with the conventional RNS Montgomery exponentiation. Moreover, when the RNS Montgomery exponentiation is simultaneously executed in two circuits, the RSA deciphering operation can be realized at a processing amount of about ⅛ as compared with the conventional RNS Montgomery exponentiation.  
         [0188]    As described above, according to the present embodiment, when the operation utilizing the Chinese remainder theorem, operation utilizing a residue number system, and Montgomery operation are united, the modular exponentiation calculation can be more efficiently executed.  
         [0189]    Other embodiments will be described hereinafter.  
         [0190]    In the procedure of FIG. 2, the procedure of the steps S 1 -p to S 5 -p may be performed in any order except that the step S 2 -p follows the step S 1 -p (the remainder calculator  141  and representation converter  127  are set to be processable in parallel, and a whole or a part of the processing may be performed in parallel).  
         [0191]    Moreover, in the procedure of FIG. 2, in the steps S 1 -p and S 1 -q corresponding to the steps S 1 -p to S 9 -p and S 1 -q to S 9 -q, similar operations relating to two prime factors p and q of N are executed. For the operation of S 1 -p to S 9 -p, S 1 -q to S 9 -q, p and q parts may be executed by turns. Alternatively, after all the p parts are executed, all q parts may be executed. In the latter case, since storing/retrieving an intermediate variable to/from a memory decreases, an efficiency may be enhanced.  
         [0192]    Furthermore, the p and q parts may also be processed in a pipeline manner.  
         [0193]    Additionally, when a whole or a part of the corresponding operation unit is set to be processable in parallel, the p and q parts can also be executed in parallel. The internal constitution example relating to each operation unit of the calculation apparatus  1  in a case in which the p and q parts are separately described is shown in FIG. 5.  
         [0194]    Moreover, for example, all of the RNS Montgomery multiplier  123 , RNS Montgomery exponentiation calculator  124 , RNS multiplier  125 , and RNS adder  126 , only the RNS Montgomery multiplier  123  and RNS Montgomery exponentiation calculator  124 , or only the RNS Montgomery exponentiation calculator  124  are set so that the processing of p parts and q parts can be performed in parallel.  
         [0195]    Of course, each operation unit can perform a parallel calculation derived from the RNS operation and raise the speed. In this case, the operation with respect to all the elements of the base can be constituted to be executed simultaneously, and the operation with respect to some elements of the base (e.g., the number of elements corresponding to a factor of an integer indicating the base size) can be constituted to be executed at the same time.  
         [0196]    Moreover, in the aforementioned embodiment, an example in which pinv=p −1  mod q, qinv=q −1  mod p are inputted from the external device has been described, but these may be calculated from p, q. In this case, as shown in FIG. 6, as an auxiliary operation unit in the binary representation, in addition to the remainder calculator  141  and adder/subtracter  142 , an inverse element calculator  143  may further be disposed.  
         [0197]    In the inverse element calculator  131 , integer x of the binary representation and value y of the modulus are inputted to calculate x −1  mod y. This calculation is often executed by an algorithm called the extended Euclidean algorithm. The calculation is described, for example, in “The art of computer programming”, Addison Wesley Longman, Inc., pp. 342-345 authored by Donald E. Knuth. In general, the calculation amount corresponds to a calculation amount of about ten modular multiplication operations having a size of y.  
         [0198]    Furthermore, the example in which dp=d mod (p−1), dq=d mod (q−1) are inputted from the outside has been described above in the constitution example, but may be calculated from p, q. The calculation can be performed by the remainder calculator  141 .  
         [0199]    An internal constitution example relating to each operation unit of the calculation apparatus  1  in which pinv, qinv, dp, dq are calculated from p, q is shown in FIG. 7.  
         [0200]    Additionally, for the external input parameters (ciphertext C, dp=d mod (p−1), dq=d mod (q−1), N(p=p×q), p, q, pinv=p −1  mod q, qinv=q −1  mod p), the parameters other than the ciphertext C are parameters corresponding to the secret key of RSA. It is also possible to store all or some of the parameters in the calculation apparatus  1 . In this case, the ciphertext C and key identification information necessary for selecting a key parameter group in the calculation apparatus  1  may be inputted.  
         [0201]    Moreover, the calculation shown in the steps S 1 -p to S 4 -p and steps S 1 -q to S 4 -q of FIG. 2 depends only on secret keys (p, q, pinv, qinv) of the RSA. However, the ciphertext C by the RSA differs with a session, but the RSA secret key is not changed very much (there can be a system in which the RSA secret key is unchanged).  
         [0202]    Then, a result obtained by executing the steps S 1 -p to S 4 -q is stored. As long as the same RSA secret key is used, the steps S 1 -p to S 4 -q are skipped, and the result stored beforehand is utilized to perform the processing of and after the step S 5 -p. When the RSA secret key is changed, the steps S 1 -p to S 4 -q may be executed anew.  
         [0203]    Furthermore, when the RSA secret key is managed by the key identification information, the result may be associated with the key identification information and stored.  
         [0204]    Additionally, when the RSA secret key is single and unchanged, only C is inputted from the outside, and the data (p, q, N, &lt;p&gt;, &lt;q&gt;, &lt;−p −1 &gt; b , &lt;−q −1 &gt; b , &lt;bp&gt;, &lt;bq&gt;, &lt;pinv&gt;, &lt;qinv&gt;, &lt;bp&gt;, &lt;bq&gt;) depending only on the RSA secret key may be stored beforehand in the storage.  
         [0205]    Moreover, when there are a plurality of RSA secret keys, only the C and key identification information are inputted from the outside. The data (p, q, N, &lt;p&gt;, &lt;q&gt;, &lt;−p −1 &gt; b , &lt;−q −1 &gt; b , &lt;bp&gt;, &lt;bq&gt;, &lt;pinv&gt;, &lt;qinv&gt;, &lt;bp&gt;, &lt;bq&gt;) depending only on the RSA secret key is associated with the key identification information, and stored beforehand in the storage. The data corresponding to the key identification information inputted from the outside may be read from the storage and used.  
         [0206]    Furthermore, when two types of bases are used, with respect to the bases a={a 1 , a 2 , . . . , a n1 } and b={b 1 , b 2 , . . . , b n2 }, n1=n2 =n has been described, but it is also possible to set n1≠n2.  
         [0207]    Additionally, the above-described embodiments can be applied to a communication system using an RSA cryptography, such as shown in FIG. 8. It is more effective to apply the present invention to a decryption (m=C d  mod N) which needs more calculation amount than an encryption. But, the encryption (C=m e  mod N) is represented by an equation similar to that of the decryption. Of course, the present invention can also be applied to the encryption (e.g., a case in which the apparatus having the secret key performs the encryption). In this case, in the above description, the plaintext m is inputted instead of the ciphertext C, and the exponent e may be used instead of the exponent d.  
         [0208]    Hardware and software constitutions of the calculation apparatus will next be described.  
         [0209]    The present embodiment has been described assuming that the present calculation apparatus (deciphering apparatus or enciphering apparatus) is realized by hardware, but it is also possible to realize the apparatus as software.  
         [0210]    When the apparatus is constituted as hardware, the apparatus is formed, for example, as a semiconductor apparatus, and is mounted as an operation board or card in calculators such as a personal computer in one mode. When the calculator uses OS, a driver for the operation device may be incorporated in the OS and used in the other mode. Moreover, it is also possible to form the apparatus as the semiconductor apparatus, and to dispose the apparatus in apparatuses such as AV equipment and household electric appliances.  
         [0211]    When the apparatus is realized by software, the apparatus can be implemented as program for allowing a computer to execute predetermined means (for allowing the computer to function as the predetermined means, or for allowing the computer to realize the predetermined function). Alternatively, the apparatus can also be implemented as a computer readable recording medium in which the program is recorded. Needless to say, it is also possible to utilize various fast techniques such as a multi-processor and pipeline processing.  
         [0212]    According to the present invention, when the operation utilizing the Chinese remainder theorem, the operation utilizing the residue number system, and Montgomery operation are united, the modular exponentiation calculation can more efficiently be executed.  
         [0213]    While the description above refers to particular embodiments of the present invention, it will be understood that many modifications may be made without departing from the spirit thereof. The accompanying claims are intended to cover such modifications as would fall within the true scope and spirit of the present invention. The presently disclosed embodiments are therefore to be considered in all respects as illustrative and not restrictive, the scope of the invention being indicated by the appended claims, rather than the foregoing description, and all changes that come within the meaning and range of equivalency of the claims are therefore intended to be embraced therein. For example, other constitutions obtained by replacing a part of the illustrated constitution with another part, omitting a part of the illustrated constitution, adding another function or element to the illustrated constitution, or combining the constitutions are also possible. Moreover, another constitution logically equivalent to the illustrated constitution, another constitution including a part logically equivalent to the illustrated constitution, another constitution logically equivalent to a main part of the illustrated constitution, and the like are also possible. Furthermore, another constitution which achieves the same or similar object as the object of the illustrated constitution, another constitution which produces the same or similar effect as that of the illustrated constitution, and the like are also possible.  
         [0214]    Additionally, it is possible to appropriately combine and implement various variations relating to various constituting parts described in the embodiment of the present invention.  
         [0215]    Moreover, the mode for carrying out the present invention contains/includes various viewpoints, stages, concepts, and categories such as an invention as an individual apparatus, invention relating to two or more associated apparatuses, invention as a whole system, invention relating to constituting parts inside the individual apparatus, and invention of a corresponding method.  
         [0216]    Therefore, the present invention can be extracted from a content disclosed in the content described in the embodiment of the present invention without limiting the present invention to the illustrated constitution.  
         [0217]    The present invention is not limited to the aforementioned modes, and can variously be modified and implemented in the technical scope.  
         [0218]    Moreover, the present invention can also be implemented as a computer readable recording medium in which a program for allowing a computer to execute predetermined means, allowing the computer to function as predetermined means, or allowing the computer to realize a predetermined function is recorded.