Ring arithmetic method, system, and apparatus

• US 20030044004A1
• Filed: 02/05/2002
• Published: 03/06/2003
• Est. Priority Date: 05/02/2001
• Status: Active Grant

• Current Assignee: Ncipher Security Limited
• Original Assignee: nCipher Corporation Limited (Thales SA)
• Inventors: Datta, Rajat, Stein, Kyle, Mitchell, Oscar, Blakley, George Robert
• Granted Patent: US 7,218,734 B2
• Time in Patent Office: Days
• US Class Current: 380/28
• CPC Class Codes: G01N 2035/00247 Microvalves
• CPC Class Codes: G01N 2035/00574 Means for distributing beads
• CPC Class Codes: G06F 13/1647 with interleaved bank access
• CPC Class Codes: G06F 7/72 using residue arithmetic
• CPC Class Codes: G06F 7/723 Modular exponentiation G06F7/724, G06F7/727, G06F7/728 take precedence
• CPC Class Codes: G06F 7/727 Modulo N arithmetic, with N being either (2**n)-1,2**n or (2**n)+1, e.g. mod 3, mod 4 or mod 5 G06F7/728 takes precedence
• CPC Class Codes: G06F 7/728 using Montgomery reduction
• CPC Class Codes: G11C 7/1066 Output synchronization
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 63/0272 Virtual private networks
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/166 at the transport layer
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes

Abstract

A data encryption method performed with ring arithmetic operations using a residue number multiplication process wherein a first conversion to a first basis is done using a mixed radix system and a second conversion to a second basis is done using a mixed radix system. In some embodiments, a modulus C is be chosen of the form 2^w−L, wherein C is a w-bit number and L is a low Hamming weight odd integer less than 2^(w−1)/2. And in some of those embodiments, the residue mod C is calculated via several steps. P is split into 2 w-bit words H₁ and L₁. S₁ is calculated as equal to L₁+(H₁2^x1)+(H₁2^x2)+ . . . +(H₁2^xk)+H₁. S₁ is split into two w-bit words H₂ and L₂. S₂ is computed as being equal to L₂+(H₂2^x1)+(H₂2^x2)+ . . . +(H₂2^xk)+H₂. S₃ is computed as being equal to S₂+(2^x1+ . . . +2^xk+1). And the residue is determined by comparing S₃ to 2^w. If S₃<2^w, then the residue equals S₂. If S₃>2^w, then the residue equals S₃−2^w.

Claims

A1. A1. A method of encrypting data comprising:

performing a ring arithmetic function on numbers, including;

using a residue number multiplication process;

converting to a first basis using a mixed radix system; and

converting to a second basis using a mixed radix system.

A2. A2. The method of claim A1, wherein the ring arithmetic function includes multiplication.

A3. A3. The method of claim A1, wherein the ring arithmetic function includes addition.

A4. A4. The method of claim A1, wherein the ring arithmetic function includes subtraction.

A5. A5. The method of claim A1, wherein the data is encrypted using asymmetric encryption.

A6. A6. The method of claim A1, wherein the data is encrypted using symmetric encryption.

A7. A7. The method of claim A1, further comprising:

choosing a modulus C for modular calculations;

wherein the modulus C is w-big; and

wherein the modulus C is w-heavy.

A8. A8. The method of claim A7, wherein the modulus C is of the form 2 w −

L; and

wherein L is a low Hamming weight odd integer less than 2<sup>(w−

1</sup>)^/2.

A9. A9. The method of claim A8, further comprising:

calculating the modulus C by a process including;

splitting P into 2 w-bit words H₁ and L₁;

calculating S₁=L₁+(H₁ 2^x2)+(H₁ 2^x2)+ . . . +(H₁2^xk)+H₁;

splitting S₁ into two w-bit words H₂ and L₂;

computing S₂=L₂+(H₂ 2^x1)+(H₂ 2^x2)+ . . . +(H₂ 2^xk) +H₂;

computing S₃=S₂+(2^x1+ . . . +2^xk+1);

determining the modulus C by comparing S₃ to 2^w, wherein the modulus C

=S₂ if S_{3 <}

2^w, and wherein the modulus C=S_{3 =}2^w if S_{3 ≧}

2^w; and

wherein the modulus C is a residue.

A10. A10. The method of claim A1, further comprising:

choosing a modulus C for modular calculations;

wherein the modulus C is w-little; and

wherein the modulus C is w-light.

A11. A11. The method of claim A10,

wherein the modulus C is of the form 2^w+L;

and

wherein the modulus C has a Hamming weight close to 1.

B1. B1. A method of encrypting data comprising the steps of:

choosing a first basis (m₁, m₂, . . . m_t);

choosing a second basis (m_t+1, m_t+2, . . . m_2t);

calculating a product M=M₁M₂ . . . m_t;

calculating a product W=m_t+1m_t+2 . . . m_2t; and

calculating a product ABM<sup>−

1</sup> mod p, wherein the calculating a product ABM<sup>−

1</sup> mod p includes;

computing Q mod M in the first basis such that AB+Qp=RM for some integral value R;

converting Q to the second basis, Q mod W; and

computing R in the second basis, R mod W, wherein R=(AB +Qp)M<sup>−

1</sup> mod W and R mod p=ABM<sup>−

1</sup> mod p.

B2. B2. The method of claim B1, further comprising converting R to the first basis, R mod M.

B3. B3. The method of claim B2, further comprising:

a second iteration of the method of claim B2;

and

wherein R is used as input to the subsequent iteration.

B4. B4. The method of claim B1, wherein the data is encrypted using asymmetric encryption.

B5. B5. The method of claim B1, wherein the data is encrypted using symmetric encryption.

C1. C1. A method of encrypting data comprising:

choosing a modulus C for modular calculations;

wherein the modulus C is w-big; and

wherein the modulus C is w-heavy.

C2. C2. The method of claim C1,

wherein the modulus C is of the form 2^w−

L; and

wherein L is a low Hamming weight odd integer less than 2<sup>(w−

1</sup>)².

C3. C3. The method of claim C2, further comprising:

calculating the modulus C by a process including;

splitting P into 2 w-bit words H₁ and L₁;

calculating S₁=L₁+(H₁2^x1)+(H₁2^x2)+ . . . +(H₁ 2^xk)+H₁;

splitting S₁ into two w-bit words H₂ and L₂;

computing S₂=L₂+(H₂ 2^x1)+(H₂ 2^x2)+ . . . +(H₂2^xk)+H₂;

computing S₃=S₂+(2^x1+ . . . +2^xk+1);

determining the modulus C by comparing S₃ to 2^w, wherein the modulus C

=S₂ if S₃<

2^w, and wherein the modulus C=S₃−

2^w if S₃>

2^w; and

wherein the modulus C is a residue.

D1. D1. A method of encrypting data comprising:

choosing a modulus C for modular calculations;

wherein the modulus C is w-little; and

wherein the modulus C is w-light.

D2. D2. The method of claim D1,

wherein the modulus C is of the form 2^w+L;

and

wherein the modulus C has a Hamming weight close to 1.

E1. E1. A method of hashing data comprising:

performing a ring arithmetic function on numbers, including;

using a residue number multiplication process;

converting to a first basis using a mixed radix system; and

converting to a second basis using a mixed radix system.

E2. E2. The method of claim E1, wherein the ring arithmetic function includes multiplication.

E3. E3. The method of claim E1, wherein the ring arithmetic function includes addition.

E4. E4. The method of claim E1, wherein the ring arithmetic function includes subtraction.

E5. E5. The method of claim E1, further comprising:

choosing a modulus C for modular calculations;

wherein the modulus C is w-big; and

wherein the modulus C is w-heavy.

E6. E6. The method of claim E5,

wherein the modulus C is of the form 2^w−

L; and

wherein L is a low Hamming weight odd integer less than 2<sup>(w−

1</sup>)/².

E7. E7. The method of claim E6, further comprising

calculating the modulus C by a process including:

splitting P into 2 w-bit words H₁ and L₁;

calculating S₁=L₁+(H₁ 2^x2)+(H₁ 2^x2) + . . . +(H₁ 2^xk)+H₁;

splitting S₁ into two w-bit words H₂ and L₂;

computing S₂=L₂+(H₂ 2^x1)+(H₂ 2^x2)+ . . . +(H₂ 2^xk)+H₂;

computing S₃=S₂+(2^x1+ . . . +2^xk+1);

determining the modulus C by comparing S₃ to 2^w, wherein the modulus C

=S₂ if S_{3 <}

2^w, and wherein the modulus C=S_{3 −}

2^w if S₃>

2^w; and

wherein the modulus C is a residue.

E8. E8. The method of claim E7, wherein the method of hashing data comprises a method of cryptographic hashing.

E9. E9. The method of claim E1, further comprising:

choosing a modulus C for modular calculations;

wherein the modulus C is w-little; and

wherein the modulus C is w-light.

E10. E10. The method of claim E9,

wherein the modulus C is of the form 2^w+L;

and

wherein the modulus C has a Hamming weight close to 1.