Patent ID: 7519644

Claim:
A finite field multiplication/reduction structure in an XZ Elliptic curve cryptographic system for communicating securely over an insecure communication channel of the type which communicates a message from a transmitter to a receiver in which an operand multiplication and a field reduction are formulated as a serial-serial computation, wherein the formula for least-to-most significant digit first multiplication is: R g * = x g + δ - δ R - δ X ⁢ y g + δ - δ R - δ Y ⁢ μ g + 2 ⁢ δ - δ X - δ Y - 2 ⁢ δ R + x g + δ - δ R - δ X ⁢ μ δ - δ X - δ R ⁢ ∑ j = 0 g + δ - δ R - 1 ⁢ y j - δ Y ⁢ μ j - δ Y + y g + δ - δ R - δ Y ⁢ μ δ - δ Y - δ R ⁢ ∑ i = 0 g + δ - δ R - 1 ⁢ x i - δ X ⁢ μ i - δ X + θ [ g + δ - δ R - δ θ ] ⁢ R g - δ R * [ 0 ] ⁢ μ g + δ - δ θ - 2 ⁢ δ R + θ [ g + δ - δ R - δ θ ] ⁢ μ δ - δ R ⁢ ∑ k = 0 g - δ R - 1 ⁢ R k * [ 0 ] ⁢ μ k + R g - δ R * [ 0 ] ⁢ μ - δ R ⁢ ∑ h = 0 g + δ - δ R - 1 ⁢ θ [ h - δ θ ] ⁢ μ h + μ - 1 ⁢ R g - 1 * ( 1 ) wherein the formula for most-to-least significant digit first multiplication is: R g = x d + δ X - g ⁢ y d + δ Y - g ⁢ μ 2 ⁢ ( d - g ) + δ X + δ Y + x d + δ X - g ⁢ μ d + δ X - g ⁢ ∑ j = 0 g - 2 ⁢ y d + δ Y - j - 1 ⁢ μ d + δ Y - j - 1 + y d + δ Y - g ⁢ μ d + δ Y - g ⁢ ∑ i = 0 g - 2 ⁢ x d + δ X - i - 1 ⁢ μ d + δ X - i - 1 + θ [ d + δ θ - g ] ⁢ R g - δ - 1 [ g - δ - 1 ] ⁢ μ d - δ - 1 + θ [ d + δ θ - g ] ⁢ μ d - g ⁢ ∑ k = 0 g - δ - 2 ⁢ R k [ k ] ⁢ μ k + R g - δ - 1 [ g - δ - 1 ] ⁢ μ g - δ - 1 ⁢ ∑ h = 0 g - 2 ⁢ θ [ d + δ θ - h - 1 ] ⁢ μ d - h - 1 + μ ⁢ ⁢ R g - 1 ( 2 ) wherein the formula for least-to-most significant digit first reduction is: R g * = W [ g ] + θ [ g + δ - δ R - δ θ ] ⁢ R g - δ R * [ 0 ] ⁢ μ g + δ - δ θ - 2 ⁢ δ R + θ [ g + δ - δ R - δ θ ] ⁢ μ δ - δ R ⁢ ∑ k = 0 g - δ R - 1 ⁢ R k * [ 0 ] ⁢ μ k + R g - δ R * [ 0 ] ⁢ μ - δ R ⁢ ∑ h = 0 g + δ - δ R - 1 ⁢ θ [ h - δ θ ] ⁢ μ h + μ - 1 ⁢ R g - 1 * ( 3 ) wherein the formula for most-to-least significant digit first reduction is: R g = W [ 2 ⁢ d + δ - g ] + θ [ d + δ θ - g ] ⁢ R g - δ - 1 [ g - δ - 1 ] ⁢ μ d - δ - 1 + θ [ d + δ θ - g ] ⁢ μ d - g ⁢ ∑ k = 0 g - δ - 2 ⁢ R k [ k ] ⁢ μ k + R g - δ - 1 [ g - δ - 1 ] ⁢ μ g - δ - 1 ⁢ ∑ h = 0 g - 2 ⁢ θ [ d + δ θ - h - 1 ] ⁢ μ d - h - 1 + μ ⁢ ⁢ R g - 1 ( 4 ) wherein 0≦g≦d+δ, x i and y i are the i th digits of the input operands to be multiplied, θ [i] is the i th digit of the reduction polynomial, W is the 2d-digits quantity to be reduced and W [g] is the g th digit of W, and wherein the computation for d+δ+1≦g≦2d+δ is formulated in an identical fashion except that the resultant feedback digits are not fed back but used as the output of the structure.