Ring arithmetic method, system, and apparatus

• US 7,853,014 B2
• Filed: 02/27/2007
• Issued: 12/14/2010
• Est. Priority Date: 05/02/2001
• Status: Expired due to Fees

• Current Assignee: Ncipher Security Limited
• Original Assignee: nCipher Corporation Limited (Thales SA)
• Inventors: Stein, Kyle, Mitchell, Oscar, Blakley, George Robert, Datta, Rajat
• Primary Examiner(s): PYZOCHA, MICHAEL J
• Application Number:
  US11/712,227
• Publication Number:
  US 20070206784A1
• Time in Patent Office: 1,386 Days
• Field of Search: 380/28, 380/30, 708/491
• 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

1. A method of encrypting data, comprising:

choosing a modulus C for modular calculations, wherein C is a w-bit number, and wherein the modulus C is selected from the group consisting of (a) w-big and w-heavy, and (b) w-little and w-light; and

using the modulus to encrypt data through a process involving a ring arithmetic function;

wherein the modulus C is calculated by a process including

(a) splitting a number P<

2^2w into 2 w-bit words H₁ and L₁;

(b) calculating S₁=L₁+(H₁2^x1)+(H₁2^x2)+ . . . +(H₁2^xk)+H₁, wherein (w−

3)/2>

x₁>

x₂>

. . . >

x_k>

0 and k<

<

w;

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

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

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

(f) determining the modulus C by comparing S₃ to 2w, wherein the modulus C=S₂ if S₃<

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

2^w if S₃≧

2^w;

wherein the modulus C is a residue.

2. The method of claim 1, wherein the modulus C is of the form 2^w−

L, and wherein L is a low Hamming weight odd integer less than 2^(w-1)/2.

3. The method of claim 1, wherein the modulus C is of the form 2^w+L, and wherein the modulus C has a Hamming weight close to 1.

4. The method of claim 1, wherein the method of encrypting data comprises a method of cryptographic hashing.

5. The method of claim 1, wherein the modulus C is w-big and w-heavy.

6. The method of claim 1, wherein the modulus C is w-little and w-light.

7. The method of claim 1, wherein C=2^w−

2^x1−

2^x2−

. . . −

2^xk−

1, wherein (w−

3)/2>

x₁>

x₂>

. . . >

x_k>

0, and wherein k>

>

w.

8. The method of claim 1, further comprising:

choosing a first basis (m₁, m₂, . . . m_t) and a second basis (m_t+1, m_t+2, . . . m_2t), wherein m₁, . . . m_2t are moduli;

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 for n-bit numbers A and B by (a) computing Q mod M in the first basis such that AB+Qp=RM for some integral value R and for a number p which is prime relative to M and W;

(b) converting Q to the second basis, Q mod W; and

(c) 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.

9. The method of claim 8 wherein, for i=1 to 2t, 2^k−

1≦

m_i≦

2^k, and wherein m₁, . . . , m_2t are pairwise mutually prime.

10. The method of claim 9, wherein t≧

(n+1)/k, where n is the bit length of the numbers being multiplied.

11. The method of claim 1, further comprising:

performing a ring arithmetic function on numbers, including (a) using a residue number multiplication process, (b) converting to a first basis using a mixed radix system, and (c) converting to a second basis using a mixed radix system.

12. A method of encrypting data, comprising:

choosing a modulus C for modular calculations, wherein C is a w-bit number, and wherein the modulus C is selected from the group consisting of (a) w-big and w-heavy, and (b) w-little and w-light; and

using the modulus to encrypt data through a process involving a ring arithmetic function;

wherein the method further comprises

choosing a first basis (m₁, m₂, . . . m_t) and a second basis (m_t+1, m_t+2, . . . m_2t), wherein m₁, . . . , m_2t are moduli,

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 for n-bit numbers A and B by (a) computing Q mod M in the first basis such that AB+Qp=RM for some integral value R and for a number p which is prime relative to M and W;

(b) converting Q to the second basis, Q mod W; and

(c) 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.

13. The method of claim 12, further comprising:

performing a ring arithmetic function on numbers, including (a) using a residue number multiplication process, (b) converting to a first basis using a mixed radix system, and (c) converting to a second basis using a mixed radix system.

14. The method of claim 12, 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)/2</sup>.

15. The method of claim 12, wherein the modulus C is of the form 2^w+L, and wherein the modulus C has a Hamming weight close to 1.

16. The method of claim 12, wherein the method of encrypting data comprises a method of cryptographic hashing.

17. The method of claim 12, wherein the modulus C is w-big and w-heavy.

18. The method of claim 12, wherein the modulus C is w-little and w-light.

19. The method of claim 12, wherein C=2^w−

2^x1−

2^x2−

. . . −

2^xk−

1, wherein (w−

3)/2>

x₁>

x₂>

. . . >

x_k>

0, and wherein k>

>

w.

20. The method of claim 12 wherein, for i=1 to 2t, 2^k−

1≦

m_i≦

2^k, and wherein m₁, . . . , m_2t are pairwise mutually prime.

21. The method of claim 20, wherein t≧

(n+1)/k, where n is the bit length of the numbers being multiplied.

22. The method of claim 21, wherein p is an n-bit number, and wherein p is a prime number.

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

24. The method of claim 12, wherein the step of calculating a product ABM⁻

1 mod p is performed iteratively and includes at least first and second subsequent iterations, and wherein the value of R calculated in the first iteration is utilized as the input value of R in the second iteration.

25. The method of claim 12, wherein the data is encrypted using asymmetric encryption.

26. The method of claim 12, wherein the data is encrypted using symmetric encryption.

27. The method of claim 12, further comprising:

performing a ring arithmetic function on numbers, including (a) using a residue number multiplication process, (b) converting to a first basis using a mixed radix system, and (c) converting to a second basis using a mixed radix system.