US5144574A — Modular multiplication method and the system for …

Claim 1

Independent Claim 267 words

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.

Claim 2

Independent Claim 267 words

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.

Claim 3

Dependent Claim 80 words

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.

Claim 4

Dependent Claim 88 words

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.

Claim 5

Dependent Claim 128 words

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.

Claim 6

Dependent Claim 52 words

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.

Claim 7

Dependent Claim 147 words

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.

Claim 8

Dependent Claim 27 words

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.

Claim 9

Dependent Claim 58 words

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.

Claim 10

Dependent Claim 196 words

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.

Claim 11

Dependent Claim 54 words

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.

Claim 12

Dependent Claim 64 words

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.

Claim 13

Dependent Claim 62 words

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.

Claim 14

Dependent Claim 80 words

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])

Claim 15

Dependent Claim 103 words

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.

Claim 16

Dependent Claim 41 words

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.

Claim 17

Dependent Claim 97 words

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.

Claim 18

Dependent Claim 68 words

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.

Claim 19

Dependent Claim 217 words

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.

Claim 20

Dependent Claim 116 words

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.

Claim 21

Dependent Claim 92 words

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.

Claim 22

Dependent Claim 242 words

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.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1995-09-01	1996-03-02	1996-09-01	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	1999-09-01	2000-03-02	2000-09-01	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2003-09-01	2004-03-02	2004-09-01	$7700.00	Window Closed / Lapsed

Modular multiplication method and the system for processing data

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag