Granted Patent B2

US 7,233,970 · App. 10/078,252 · Granted Jun 19, 2007

Abstract

Claims (129)

1. An apparatus for performing exponentiations, comprising:

a set of computational devices containing first and second subsets, wherein the first subset has a plurality of members which are chained together such that the devices of the first subset can operate both independently and as members of a first computational chain, and wherein the second subset has a plurality of members which are chained together such that the devices of the second subset can operate both independently and as members of a second computational chain distinct from said first computational chain; and

a chaining controller adapted to instruct the first subset of devices to act as a first computational chain when the apparatus is required to perform an exponentiation of a first size, and being further adapted to instruct the second subset of devices to act as a second computational chain when the apparatus is required to perform an exponentiation of a second size distinct from said first size;

wherein each computational device is adapted to perform 1024-bit exponentiation, wherein said chaining controller is adapted to instruct the first subset of devices to act as a first computational chain when the apparatus is required to perform 2048-bit exponentiation, and wherein said chaining controller is adapted to instruct the second subset of devices to act as a second computational chain when the apparatus is required to perform 4096-bit exponentiation.

2. The apparatus of claim 1 , further comprising a hardware state controller for each computational device of the first computational chain, wherein each hardware state controller includes replicated fanout control logic.

3. The apparatus of claim 2 , wherein the replicated fanout control logic is configured to allow computational devices of the first computational chain to chain without delay due to high fanout.

4. The apparatus of claim 2 , wherein the replicated fanout control logic is configured such that state machines of the first computational chain sequence efficiently.

5. The apparatus of claim 1 , wherein each computational device further comprises a custom multiplier datapath, and wherein each custom multiplier datapath is configured so that the length of its longest wire is short.

6. The apparatus of claim 5 , wherein the custom multiplier datapaths of chained computational devices are physically mirrored to each other so that the wire length between the two is short.

7. The apparatus of claim 5 , wherein the custom multiplier datapath has a serpentine layout so that the wire length between the most separated adjacent data locations is short.

8. The apparatus of claim 1 , wherein the number of computational devices in the set of computational devices equals 2 k , and wherein k is a non-negative integer.

9. The apparatus of claim 8 , wherein k equals 2.

10. The apparatus of claim 8 , wherein each computational device is adapted to exponentiate a 512-bit number.

11. The apparatus of claim 1 , wherein the number of computational devices in the first computational chain equals 2 k wherein k is a positive integer.

12. The apparatus of claim 11 , further comprising:

a second computational chain;

wherein the second subset includes at least two computational devices, wherein the chaining controller is configured to instruct the second subset to operate as a second computational chain, and wherein no computational device of the first computational chain is part of the second computational chain.

13. The apparatus of claim 1 , wherein each computational device in said set of computational devices further comprises:

a cleave/merge engine;

wherein the cleave/merge engine is configured to:

receive AA, which is a 2 w-bit number;

calculate A 1 and A 2 , which are two w-bit numbers based on AA; and

output A 1 and A 2 ;

wherein the cleave/merge engine is also configured to:

receive B 1 and B 2 , which are two w-bit numbers;

calculate BB, which is a 2 w-bit number based on B 1 and B 2 ; and output BB;

wherein exponentiation of AA yields BB;

wherein exponentiation of A 1 yields B 1 ;

wherein exponentiation of A 2 yields B 2 ; and

wherein w is a positive integer.

14. The apparatus of claim 13 , wherein A 1 and A 2 are calculated from AA, and BB is calculated from B 1 and B 2 , using a scalable Chinese Remainder Theorem implementation.

15. The apparatus of claim 14 ,

wherein each computational device is adapted to perform 1024-bit exponentiation;

wherein, if 2048-bit exponentiation is required, the chaining controller causes the first computational chain to comprise two exponentiators; and

wherein, if 4096-bit exponentiation is required, the chaining controller causes the first computational chain to comprise four exponentiators.

16. The apparatus of claim 1 , wherein said chaining controller is adapted to implement a flexible chaining algorithm.

17. The apparatus of claim 1 , wherein the first computational chain comprises two computational devices, and wherein the second computational chain comprises four computational devices.

18. The apparatus of claim 1 , wherein at least some of the computational devices in the first computational chain are also in the second computational chain.

19. A method for encrypting/decrypting data comprising:

providing a 1024-bit number X; and

encrypting/decrypting X by

loading X into session memory,

cleaving X mod P to compute X P ,

cleaving X mod Q to compute X Q ,

exponentiating Xp to compute C P ,

exponentiating XQ to compute C Q ,

merging C P and C Q to compute C, wherein C is a 1024-bit number, and

retrieving C from the session memory;

wherein the method further comprises (a) selecting one of a plurality of session controllers; (b) setting the busy bit for the one session controller; and (c) clearing the busy bit for the one session controller.

20. The method of claim 19 , further comprising:

selecting two session controllers of 32 available session controllers;

setting the busy bits for the two session controllers

wherein loading argument X into session memory includes:

loading part of the argument X into the session memory of one of the two session controllers;

loading the remainder of the argument X into the session memory of the other of the two session controllers;

wherein the argument X is a 2048-bit number;

wherein C is a 2048-bit number; and

clearing the busy bits for the two session controllers.

21. The method of claim 19 , further comprising:

selecting four session controllers of 32 available session controllers;

setting the busy bits for the four session controllers

wherein loading argument X into session memory includes:

loading a first part of the argument X into the session memory of a first of the four session controllers;

loading a second part of the argument X into the session memory of a second of the four session controllers;

loading a third part of the argument X into the session memory of a third of the four session controllers;

loading the remaining of the argument X into the session memory of a fourth of the four session controllers;

wherein the argument X is a 4096-bit number;

wherein C is a 4096-bit number; and

clearing the busy bits for the four session controllers.

22. The method of claim 19 ,

wherein the cleaving X mod P comprises:

setting A[513:0]=X[1023:510];

calculating Z[1026:0]=A[513:0]×μP[512:0], wherein μP[512]=1;

setting B[513:0]=Z[1026:512];

setting C[513:0]=X[513:0];

calculating Y[1025:0]=B[513:0]×P[511:0];

setting D[513:0]=Y[513:0];

calculating E[513:0]=C[513:0]−D[513:0];

if E>P then calculating E=E−P;

if E>P then E =E−P; and

setting X P =E[511:0] as the result of the cleaving X mod P, whereby X P equals X mod P; and

wherein the cleaving X mod Q comprises:

setting A[513:0]=X[1023:510];

calculating Z[1026:0]=A[513:0]×μQ[512:0], wherein μQ[512]=1;

setting B[513:0]=Z[1026:512];

setting C[513:0]=X[513:0];

calculating Y[1025:0]=B[513:0]×Q[511:0];

setting D[513:0]=Y[513:0];

calculating E[513:0]=C[513:0]−D[513:0];

if E>Q then calculating E=E−Q;

if E>Q then E=E−Q; and

setting X Q =E[511:0] as the result of the cleaving X mod Q, whereby X Q equals X mod Q.

23. The method of claim 19 , wherein merging C P and C Q to compute C comprises:

if C P >P then calculating C P =C P −P;

if C Q >Q then calculating C Q =C Q −Q;

calculating A[512:0]=C Q [511:0]−C P [511:0];

if A<0 then calculating A[511:0]=A[511:0]+Q[511:0];

calculating B[1023:0]=A[511:0]×P −1 [511:0];

calculating D[511:0]=Cleave B[1023:0] mod Q[511:0], wherein μQ[512]=1;

calculating E[1023:0]=D[511:0]×P[511:0];

calculating C[1023:0]=E[1023:0]+Cp[511:0]; and

wherein C[1023:0] is the result of merging C P and C Q .

24. The method of claim 19 , wherein X is data which is to be encrypted.

25. The method of claim 19 , wherein X is data which is to be decrypted.

26. The method of claim 19 , wherein the session controller selected is one 32 available session controllers.

27. A device for performing computations, comprising:

a plurality of exponentiators; and

a chaining controller adapted to arrange a first group of said exponentiators into a first computational chain when the device is required to process exponentiations of a first size, and being further adapted to arrange a second group of said exponentiators into a second computational chain when the device is required to process exponentiations of a second size distinct from said first size;

wherein the memories of said plurality of exponentiators map into a single global address.

28. The device of claim 27 , wherein said plurality of exponentiators operate independently when the device is required to process exponentiations of a third size distinct from said first and second sizes.

29. The device of claim 27 , wherein said third size is 1K.

30. The device of claim 27 , wherein said first size is 4K.

31. The device of claim 27 , wherein said second size is 2K.

32. The device of claim 27 , wherein the first and second groups are mutually exclusive.

33. The device of claim 27 , wherein said device is adapted to perform RSA exponentiations.

34. The device of claim 27 , wherein each of said plurality of exponentiators is adapted to simultaneously process eight 1K exponentiations, four 2K exponentiations, or two 8K exponentiations.

35. The device of claim 27 , wherein said chaining controller is a direct memory access controller which is adapted to load arguments and control information into the internal memory and registers of said plurality of exponentiators.

36. The device of claim 35 , wherein said chaining controller is further adapted to retrieve exponentiation results from the memory of said plurality of exponentiators.

37. The device of claim 35 , wherein said chaining controller is further adapted to retrieve exponentiation results from the memory of said plurality of exponentiators via a single burst-capable thirty-two bit bus interface.

38. The device of claim 35 , wherein each of said plurality of exponentiators comprises a plurality of session controllers, and wherein each of said plurality of session controllers is adapted to process separate exponentiations concurrently.

39. The device of claim 38 , wherein each of said plurality of exponentiators comprises a single set of computation hardware shared between the plurality of session controllers in a pipelined manner.

40. The device of claim 27 , wherein each of said plurality of exponentiators is independently connected to said chaining controller.

41. A device for performing computations, comprising:

a plurality of exponentiators, wherein each of said plurality of exponentiators is adapted to simultaneously process eight 1K exponentiations, four 2K exponentiations, or two 8K exponentiations; and

a chaining controller adapted to arrange a first group of said exponentiators into a first computational chain when the device is required to process exponentiations of a first size, and being further adapted to arrange a second group of said exponentiators into a second computational chain when the device is required to process exponentiations of a second size distinct from said first size.

42. A device for performing computations, comprising:

a plurality of exponentiators; and

a chaining controller adapted to arrange a first group of said exponentiators into a first computational chain when the device is required to process exponentiations of a first size, and being further adapted to arrange a second group of said exponentiators into a second computational chain when the device is required to process exponentiations of a second size distinct from said first size;

wherein said chaining controller is a direct memory access controller which is adapted to load arguments and control information into the internal memory and registers of said plurality of exponentiators, wherein each of said plurality of exponentiators comprises a plurality of session controllers, and wherein each of said plurality of session controllers is adapted to process separate exponentiations concurrently.

Assignments (8)