Modular multiplication method and the system for processing data

Abstract

To markedly improve the computational speed of AxB modulo N computation as compared with the prior-art Baker's method where A denotes a multiplicand; B denotes a multiplier; and N denotes a modulus, the number of multiply-additions and division (modular) substractions is reduced on the basis of any given same higher radix number r. In practice, the modular subtracters c(k)N are previously determined on the basis of the partial products b(k-1)A at the succeeding processing stage (k-1) to reduce the absolute value of the partial remainder R(k) down to a value less than a modulus N, so that bit overflow from a predetermined computational range can be prevented. For instance, when the partial product b(k)A at the succeeding processing stage (k-1) is large, the modular subtracter c(k)N at the current stage (k) is also determined large. Further, the most significant bit of the multiplicand A is eliminated by transforming the multiplicand A from a range within [0, N-1] to a range [-N/2, N/2] to reduce the absolute value of the partial product. This is necessary to apply the same radix number r to both the partial products and the modular subtracters.

What is claimed is: 
     
       1. A method of executing a modular multiplication of A×B modulo N by a cryptographic data processing computer system provided with registers, an arithmetic unit, and a controller for controlling computational operations of variables stored in the registers by the arithmetic unit, where A denotes a multiplicand stored in a first register, B denotes a multiplier stored in a second register, and N denotes a modulus stored in a third register, which comprises the steps of: (a) transforming A from Aε[0, N] to Aε[-N/2, N/2] by the arithmetic unit, where ε denotes a set of integers obtained by the arithmetic unit;   (b) setting the number of bits n of each variable of A, B or N by the controller;   (c) initializing a remainder R by the controller;   (d) determining the number of repeated processing stages k as k← n/r' +1 by the controller where r denotes a radix number r≡2 r'  (r'≧1);  n/r'  denotes a maximum integer less than n/r'; and ← denotes a substitution;   (e) updating a partial remainder R and forming a partial multiplier b and a partial quotient c both within a range of -r/2≦b, c≦r/2 by a carry save adder in the arithmetic unit;   (f) progressing a present stage (k) as k←k-1 by the controller;   (g) checking whether the present stage (k) is zero by the controller;   (h) if the stage (k) is not zero, returning to the above step (e) by the controller; and   (i) if the stage (k) is zero, transforming a final partial remainder R into a solution of A×B modulo N by a carry propagation adder in the arithmetic unit.   
     
     
       2. The method of claim 1, wherein the step of transforming A in step (a) comprises the steps of: (i) comparing an absolute multiplicand |A| with a half divisor N/2 as |A|≦N/2 or |A|.tbd.N/2 by a comparator in the arithmetic unit;   (ii) if |A|≦N/2 or |A|≳N/2, proceeding to step (b) in claim 1 by the controller; and   (iii) if |A|>N/2, substituting A-N for A as A←A-N by the arithmetic unit, and proceeding to step (b) in claim 1 by the controller.   
     
     
       3. The method of claim 2, wherein the step of comparing |A| with a half modulus N/2 in step (a) comprises the steps of: (i) comparing 2A-N with zero as 2A-N<0, where A denotes the original multiplicand A within a range of N>A≧0 by the comparator in the arithmetic unit; and   (ii) if 2A-N<0, proceeding to step (b) in claim 22 by the controller; and   (iii) if 2A-N≧0, substituting A-N for A as A←A-N by the arithmetic unit, and proceeding to step (b) in claim 1 by the controller.   
     
     
       4. The method of claim 2, wherein the step of comparing |A| with a half modulus in step (a) comprises the steps of: (i) comparing 2A top  -N top  with zero as 2A top  -N top  <0 by the comparator of the arithmetic unit, where A top  denotes higher significant bits of the multiplicand A more than a specified bit within a range of N<A≧0, and N top  denotes higher significant bits of the modulus N more than the same specified bit; and   (ii) if 2A top  -N top  <0, proceeding to step (b) in claim 1 by the controller; and   (iii) if 2A top  -N top  ≧0, substituting A-N for A as A←A-N by the arithmetic unit, and proceeding to step (b) in claim 1 by the controller.   
     
     
       5. The method of claim 1, wherein the step of setting the number of bits n of each variable of A, B, or N in step (b) comprises the step of setting n as n←log 2  N+1 by the controller, where log 2  N denotes a maximum integer less than log 2  N. 
     
     
       6. The method of claim 1, wherein when a bit length of the modulus of the modular multiplication is a fixed value n o , the step of setting the number of bits n of each variable of A, B, or N in step (b) comprises the steps of: (i) checking whether the current processing has already been executed when the modular multiplication is executed repeatedly by the controller;   (ii) if the current processing is not the first repeated processing, directly proceeding to step (c) in claim 1 by the controller; and   (iii) if the current processing is the first repeated processing, substituting n o  for n as n←n o , N×2 m  for N as N←N×2 m , and A×2 m  for A as A←A×2 m  by the arithmetic unit, where the original N is determined as 2 n-m  <N≧2 n-m-1 , and m denotes an integer.   
     
     
       7. The method of claim 1, wherein when the remainder R is defined in an ordinary form in step (c), R is initialized as R←0 by the controller. 
     
     
       8. The method of claim 1, wherein when the remainder R is defined in redundant representation form as R≡R s  +2R c  in step (c), both the R s  and R c  are initialized as R s  ←0 and R c  ←0 by the controller, where R s  denotes a remainder sum and R c  denotes a remainder carry. 
     
     
       9. The method of claim 1, wherein the step of updating the partial remainder R and forming the partial multiplier b and partial quotient c in steps (e) to (i) comprises the steps of: (i) forming a present stage partial multiplier b(k) by the arithmetic unit;   (ii) updating a succeeding stage partial remainder R(k-1) by the present stage partial remainder R(k) and the present stage partial multiplier b(k) as R(K-1)←rR(k)+b(k)A by the carry save adder of the arithmetic unit;   (iii) forming a succeeding stage partial multiplier b(k-1) by the arithmetic unit;   (iv) forming the present stage partial quotient c(k) by the arithmetic unit;   (v) further updating the succeeding stage partial remainder R(k-1) by the succeeding stage remainder R(k-1) and the present stage partial modular subtracter c(k)N as R(k-1)←R(k-1)-c(k)N by the carry save adder of the arithmetic unit;   (vi) progressing the present stage (k) as k←k-1 by the controller;   (vii) checking whether the present stage (k) is zero by the controller;   (viii) if the present stage (k) is not zero, returning to the above step (b) by the controller; and   (ix) if the present stage (k) is zero, returning to step (i) in claim 1 by the controller.   
     
     
       10. The method of claim 9, wherein the partial multiplier b(k) is formed by the arithmetic unit on the basis of the multiplier B in accordance with the following expression as ##EQU11## where b(k) lies within a range of -r/2≦b(k)≦r/2, and r denotes a radix number, and  x  denotes a maximum integer less than x. 
     
     
       11. The method of claim 10, wherein when the radix number is r and the multiplier B is a series of bits of B[n], B[n-1], . . . B[1], the partial multiplier b(k) is formed by the arithmetic unit on the basis of the multiplier B as follows: ##EQU12## where r≡2r, r'≧1; B[i]=0; i>n or i<1; B[i]=1 and i<n if B has a minus sign. 
     
     
       12. The method of claim 11, wherein when the radix number is 4 and the multiplier B is a series of bits of B[n], B[n-1], . . . B[1], the partial multiplier b(k) is formed by the arithmetic unit on the basis of the multiplier B as follows:   b(k)←-2B[2k]+[2k-1]+B[2k-2]     where B[i]=0; i>n or i<1; B[i]=1 and i>n if B has a minus sign.   
     
     
       13. The method of claim 10, wherein when the radix number is 4 and the multiplier B is formed in redundant representation form as B=B s  +2B c , where B s  denotes a multiplier sum and B c  denotes a multiplier carry, the partial multiplier b(k) is formed by the arithmetic unit on the basis of two functions f s  and f c  as follows:   b(k)←f.sub.s (B.sub.s [2k]B.sub.c [2k-1] and B.sub.s [2k-1]B.sub.c [2k-2])+f.sub.c (B.sub.s [2k-2]B.sub.c [2k-3] and B.sub.s [2k-3]B.sub.c [2k-4])     
     
     
       14. The method of claim 13, wherein values of f c  and f s  is selected by the controller on the basis of the following reference table in combination of B s  [2k]B c  [2k-1] and B s  [2k-1] B c  [2k-2],   ______________________________________                                    
(f.sub.c, f.sub.s)                                                        
          B [2k-1]B [2k-2]                                                
[2k]B [2k-1]                                                              
            00      01        11    10                                    
______________________________________                                    
00          0, 0    0, 1      1, -2 0, 1                                  
01          1, -2   1, -1     x     x                                     
11          1, 0    1, 1      x     x                                     
10          1, -2   1, -1     1, 0  1, -1                                 
______________________________________                                    
     where x denotes that functions (f c , f s ) do not have a value.   
     
     
       15. The method of claim 13, wherein the function f c  and f s  is computed by the arithmetic unit by ##EQU13## where V denotes the logical sum; · denotes the logical product; ⊕ denotes the exclusive OR, and  --  denotes negation. 
     
     
       16. The method of claim 9, wherein the partial quotient c(k) is formed by the arithmetic unit by defining following comparative indices l 1  (b(k-1)), l -1  (b(k-1)) immediately after the multiplicand A has been transformed, as follows: ##EQU14## where b(k-1) ε{-r/2, -r/2+1, . . . , -1, 0, 1, . . . r/2-1, r/2} where ε denotes the set of integers and i denotes an i-th bit from the least significant bit, and determining the present stage partial quotient c(k) as follows:   c(k)=i, if l.sub.i N<R(k-1)≦l.sub.-i+1 N       c(k)=o, if l.sub.-1 N≦R(k-1)≦l.sub.1 N       c(k)=-i, if l.sub.-i-1 N≦R(k-1)<l.sub.i N.     
     
     
       17. The method of claim 16, wherein the partial quotient c(k) is formed by the arithmetic unit by defining the comparative indices l i  (b(k-1)) and l -i  (b(k-1)) on the basis of A top , N top , and R top  having the same specified number of higher significant bits and by comparing R top  with the boundary indices such as l i  N or l -i  N. 
     
     
       18. The method of claim 1, wherein the step of updating the partial remainder R and forming the partial multiplier b and modulus c in step (e) comprises the steps of: (i) initializing a preceding stage partial quotient c(k+1) to zero as c(k+1)←0 by the controller;   (ii) forming a present stage partial multiplier b(k) by the arithmetic unit;   (iii) updating a succeeding stage partial remainder R(k-1) by a present stage partial remainder R(k), a preceding stage partial quotient c(k+1) and a present stage partial multiplier b(k) as R(k-1)←r{R(k)-c(k+1)N}+b(k)A by the carry save adder of the arithmetic unit;   (iv) forming a succeeding stage partial multiplier b(k-1) by the arithmetic unit;   (v) forming a present stage partial quotient c(k) by the arithmetic unit;   (vi) progressing the present stage (k) as k←k-1 by the controller;   (vii) checking whether the present stage (k) is zero by the controller;   (viii) if the present stage (k) is not zero, returning to the above step (iii) by the controller; and   (ix) if the present stage (k) is zero, returning to step (i) of claim 22 by the controller, and wherein in step (i) of claim 22 the final partial remainder R is updated by the final partial remainder R(0) and the partial quotient c(1) as R(0)←R(0)-c(1)N by the carry save adder in the arithmetic unit.   
     
     
       19. The method of claim 1, wherein the step of transforming the final stage partial remainder R into a solution of A×B modulo N in step (i) comprises the steps of: (i) checking whether the final stage partial remainder R(0) is used as a multiplicand A for a succeeding modular multiplication computation by the controller;   (ii) if R(0) is used, substituting the remainder R(0) for A as A←R(0) by the arithmetic unit;   (iii) if R(0) is not used, checking whether R(0)≧0 by the controller;   (iv) if R(0)≧0, ending the processing stage by the controller; and   (v) if R(0)<0, substituting R(0) and the modulus N for R(0) as R(0)←R(0)+N by the arithmetic unit, before ending the processing stage.   
     
     
       20. The method of claim 16, wherein the partial quotient c(k) is formed by the arithmetic unit by the steps of: (i) determining i=|R|/ N +1, where |R|/ N  denotes a maximum integer less than |R|/N;   (ii) checking whether R(k-1)≧0;   (iii) if R(k-1)≧0, checking whether l i  ≦R(k-1)/N;   (iv) if l i  ≦R(k-1)/N, determining c(k)=i;   (v) if l i  >R(k-1)/N in step (iii) above, determining c(k)=i-1;   (vi) if R(k-1)<0 in step (ii) above, checking whether |l -i  |≦|R(k-1)|/N;   (vii) if |l -i  |≦|R(k-1)|/N, determining c(k)=-i; and   (viii) if |l -i  |>|R(k-1)|/N, determining c(k)=-i+1.   
     
     
       21. The method of claim 1, wherein when a bit length of the modulus of the modular multiplication is a fixed volume, the step of transforming the final stage partial remainder R into a solution of A×B modulo N in step (i) of claim 1 comprises the steps of: (i) checking whether the final stage partial remainder R(0) is used as a multiplicand A for a succeeding modular multiplication computation by the controller;   (ii) if R(0) is used, substituting R(0) for A as A←R(0) without changing N by the arithmetic unit;   (iii) checking whether the final stage partial remainder R(0) is used as a multiplier B for the succeeding modular multiplication computation by the controller;   (iv) if R(0) is determined to be used in step (iii) above, substituting a final stage remainder R(0)/2 m  for B as B←R(0)/2 m  and further substituting R(0)/2 m  for R(0) as R(0)←R(0)/2 m  by the arithmetic unit;   (v) if R(0) is determined not to be used in step (iii) above, substituting R(0)/2 m  for R(0) as R(0)←R(0)/2 m  by the arithmetic unit;   (vi) if R(0) is determined not to be used in step (i) above, checking whether R(0)≧0 by the controller;   (vii) if R(0)≧0, substituting R(0)/2 m  for R(0) as R(0)←R(0)/2 m , ending the processing stage by the arithmetic unit;   (viii) if R(0)<0, substituting R(0)+N for R(0) as R(0)←R(0)+N and further R(0)/2 m  for R(0) as R(0)←R(0)/2 m  by the arithmetic unit, ending the processing stage.