Patent Publication Number: US-9432180-B2

Title: Method and system for a programmable parallel computation and data manipulation accelerator

Description:
RELATED APPLICATIONS 
     Benefit is claimed to U.S. Provisional Patent Application Ser. No. 61/493,172 filed Jun. 3, 2011, entitled “Method and System for a Programmable Parallel Computation and Data Manipulation Accelerator,” which is incorporated by reference herein. 
     This application is related to U.S. patent application Ser. No. 13/487,296 filed on Jun. 4, 2012, entitled “Method and System for Embedded High Performance Reconfigurable Firmware Cipher,” which is also incorporated by reference herein. 
    
    
     FIELD OF THE INVENTION 
     This generally relates to cryptographic calculations and more particularly to computational acceleration of general discrete mathematical operations. 
     BACKGROUND 
     Modern cryptography, the practice and study of securing information, operates using algorithms which often require a large number of arithmetic computations of varying complexity. These cryptographic computations are essential to many security services such as authentication, confidentiality, and integrity. 
     A variety of algorithms are used to implement cryptographic functionality. Some of these algorithms contain complex arithmetic steps requiring comparatively long processing times. Conventional cryptographic algorithm acceleration methods typically attempt to accelerate one particular cryptographic algorithm at a time through specially designed hardware interfaced with software through a custom set of instructions programmed into a processor. Therefore, while conventional methods focus on a particular algorithm, conventional systems are not designed to have the general capability to accelerate multiple different algorithms using a single method or system. 
     Some recent research has attempted to identify generic acceleration instructions which are independent of any algorithm. However, they lack tight integration within the processing environment, and they lack the computational power for significant improvements in the computational efficiency of the algorithm. 
     Encryption algorithms utilize the ability to mix, or “permute,” incoming data by remapping the data, or portions thereof, to the output. Such mappings often separate the distinctive properties of diffusion and confusion to varying degrees. While conventional bit permuters which support diffusion related computations are located outside of the Arithmetic Logic Unit (“ALU”), the digital circuit that performs arithmetic and logic operations, rather than integrated within the ALU, Conventional acceleration circuits do not tightly couple and integrate both diffusion and confusion principles. 
     Many conventional systems maintain only one copy of each individual bit in a single location. Many acceleration strategies do this so that hardwired circuits can route multiple instances of those values to combinational logic efficiently. However, this hardwiring by its nature limits the general applicability of such circuits to a wide variety of algorithms. 
     Similarly, by only maintaining one copy of each bit, these systems ensure that where a bit is required for multiple calculations, the single copy of that bit may be only available to one calculation at a time, requiring the calculations to be performed in serial rather than in parallel, elongating processing time for the algorithm 
     Further, maintaining a single copy of each individual bit in a conventional system located without tightly integrating its location within the computational circuitry forces additional software to preparations of the data input, slowing input/output (“I/O”) processing associated with the desired computation. 
     By treating the required instruction set as a generic bit permuter, conventional systems offer limited capabilities and throughput speed. Finally, the lack of integration of diffusion related permutations with confusion related calculations requires the programmer to provide separate instructions to perform the actual computation increasing the input/output processing requirements, limiting the parallelization and pipe-lining potential, and wasting further time and man-hours. 
     Accordingly, there is a desire for a computation and data manipulation accelerator which overcomes these and other related problems. 
     SUMMARY 
     A method in a data processing system is provided for accelerating a cryptographic algorithm calculation comprising inputting data bits into a butterfly network, and permuting the data bits in the butterfly network based on a predetermined calculation. The method further comprises outputting the permuted data bits from the butterfly network to a look up table, and transforming the inputted permuted data bits in the look up table based on the predetermined calculation. The method also comprises outputting the transformed data bits from the look up table. 
     A data processing system is provided for accelerating a cryptographic protocol calculation, comprising a butterfly network configured to input data bits, permute the data bits in the butterfly network based on a predetermined calculation, and output the permuted data bits from the butterfly network to a look up table. The data processing system further comprises a look up table configured to input the permuted data bits from the butterfly network, transform the inputted permuted data bits in the look up table based on the predetermined calculation, and output the transformed data bits from the look up table. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates an exemplary embodiment of a programmable parallel computation and data manipulation accelerator made in accordance with methods and systems consistent with the present invention. 
         FIG. 2  illustrates steps in an exemplary method for use of a programmable parallel computation and data manipulation accelerator in accordance with methods and systems consistent with the present invention. 
         FIG. 3  illustrates steps in an exemplary alternate method for use of a programmable parallel computation and data manipulation accelerator in accordance with methods and systems consistent with the present invention. 
         FIG. 4  illustrates steps in an exemplary alternate method for use of a programmable parallel computation and data manipulation accelerator in accordance with methods and systems consistent with the present invention. 
     
    
    
     DETAILED DESCRIPTION 
     Methods and systems in accordance with the present invention provide a programmable parallel computation and data manipulation accelerator that may be used, for example, in cryptographic calculations. Methods and systems in accordance with the present invention allow acceleration of a broad variety of cryptographic algorithms and/or portions of algorithms, these methods and systems are not algorithm specific. This system comprises a butterfly and inverse butterfly multiplexing permuter network and a lookup table. In some implementations, this system may be implemented on an application specific integrated circuit (“ASIC”) within the cryptographic development processing engine (“CDPE”). In some implementations, multiple processors may be arranged to a bank of instances of this assembly in a tightly integrated approach allowing all of the processors to accelerate portions of computations specific to their independent processes or to support coordinated parallelization of a particular algorithm. In some implementations, this system may allow replication of input registers, “expansion,” so that an individual bit may be used in multiple calculations in parallel, accelerating completion of the cryptographic algorithm. In some implementations the system may allow “diffusion” of the expanded bits through the system&#39;s butterfly and inverse butterfly network. In some implementations the system may allow “confusion” of the resulting bits through the system&#39;s lookup table. In some implementations, the system may allow completion of a computation within an algorithm within one clock cycle, the time between two adjacent pulses of the oscillator that sets the tempo of the computer processor. 
       FIG. 1  illustrates an exemplary embodiment of a programmable parallel computation and data manipulation accelerator made in accordance with methods and systems consistent with the present invention. It should be understood that the specific numbers of bits provided in the discussion of  FIG. 1  are used by way of example only, one of ordinary skill in the art will readily see that any suitable alternate numbers of bits may be used. The user may identify an algorithm which the user would like performed quicker. The algorithm may be, for example, a cryptographic algorithm such as the Advance Encryption Standard (AES), RC-4, or a hash algorithm such as MD-5, SHA-256, or a Cyclic Redundancy Check (CRC). Other algorithms may be used. The user may input the bits of this algorithm, for example as one 32 bit word, into the system using ARC  146 , an embedded system processor. The input 32 bits may then be copied into input registers R 0   100 , R 1   102 , R 2   104 , R 3   106 , R 4   108 , R 5   110 , R 6   112 , and R 7   114 , creating 8 copies of the input data in a process called “expansion,” facilitating parallel performance of computations which use the same bit. In the example of  FIG. 1 , the 32 bit word sent from ARC  146  is copied serially into R 0   100 , R 1   102 , R 2   104 , R 3   106 , R 4   108 , R 5   110 , R 6   112 , and R 7   114  so that each of these input registers contains an identical copy of the original 32 bit word. It should be understood that alternate implementations may comprise any number of input registers. The 8 input registers are then directly sensed, and the entire 256 bit matrix is output by the 8 input registers. This 256 bit output may be routed into the Butterfly and Inverse Butterfly Network  134  comprising Bfly  136 , Reg  138 , IBfly  140 , and Reg  142 . The butterfly and inverse butterfly network is programmed using ARM  144 , an embedded system processor. The user may identify an algorithm or part of an algorithm, for example a single calculation, the user wishes the system to perform and load that algorithm or part of an algorithm onto ARM  144 . As part of that loading process, specific bits or groups of bits, for example 1024 bits for a 1024 bit configuration memory, may be loaded into configuration memory Config  148  and/or Config  150 , these bits corresponding to the algorithm the user will be running. Those bits will ultimately be read by either Bfly  136  (for bits in Config  148 ) or IBfly  138  (for bits in Config  150 ) to facilitate proper connection of pathways through the permuter circuit. 
     Once the 256 bit output from the 8 input registers is in the butterfly and inverse butterfly network, the system performs “diffusion” of the data. The butterfly and inverse butterfly network “permutes” the various bits, changing their locations within the registers based on how the user has configured the network to run the desired algorithm. In some implementations, this permutation of bits may be done in parallel. In some implementations, the 256 bit output may then be divided into bytes, 8 bit words. In other implementations, the output from the diffusion process may be divided into “nibbles,” 4 bit words (as opposed to the 8 bit bytes). 
     The 32 byte output from the diffusion process then undergoes a process known as “confusion.” Each of the 32 bytes is fed, in parallel with the other bytes, into Lookup Table  152 . Lookup Table  152 , like the butterfly and inverse butterfly network, is also programmed and loaded by ARM  144 . Lookup Table  152  is loaded with the appropriate number of bits, for example 256 bits, and uses any 8-bit Boolean function to change each byte into one bit based on the Boolean function. These 32 computed bits are written to a single 32-bit register (in the case of 8-bit output from the BFLY/IBFLY permutation) which is then available to the ARM as the result of the desired computation. Alternatively, the system may route the 256 bit output from the 8 input registers down Fly Bypass Path  116  and then, one 32 bit word each, through output registers R 8   118 , R 9   120 , R 10   122 , R 11   124 , R 12   126 , R 13   128 , R 14   130 , and R 15   132 , for completion of a calculation. At this point, the process follows the same process as for the lookup table. 
     In some implementations, the butterfly and inverse butterfly network and the Lookup Table  152  may be used separately, in parallel. In these implementations, the initial input data load to undergo the confusion process via Lookup Table  152  is copied into alternate input registers R 16   154 , R 17   156 , R 18   158 , R 19   160 , R 20   162 , R 21   164 , R 22   166  and R 23   168 . Then, data loaded onto these 8 alternate input registers is routed directly to Lookup Table  152  without undergoing diffusion in the butterfly and inverse butterfly network. 
       FIG. 2  illustrates steps in an exemplary method for use of a programmable parallel computation and data manipulation accelerator in accordance with methods and systems consistent with the present invention. First, the user identifies a specific algorithm which the user wishes to accelerate (step  200 ). The user programs the system to perform the chosen algorithm through the system processors, for example by programming it into ARM  144  and ARC  146  of  FIG. 1  (step  202 ). Further, the user programs the Butterfly and Inverse Butterfly Network  134  and the Lookup Table  152 , according to the algorithm the user desires to accelerate, using ARM  144  (step  204 ). The system performs the expansion process, copying the input data into the input registers, for example input registers R 0   100 , R 1   102 , R 2   104 , R 3   106 , R 4   108 , R 5   110 , R 6   112 , and R 7   114  of  FIG. 1  (step  206 ). The expanded bits are routed to the system&#39;s Butterfly and Inverse Butterfly Network, for example Butterfly and Inverse Butterfly Network  134  of  FIG. 1  (step  208 ). In the system&#39;s Butterfly and Inverse Butterfly Network, the system performs diffusion on the data, permuting the various bits to different locations within the various input registers based on the programmed network configuration (step  210 ). The diffused data exits the system&#39;s Butterfly and Inverse Butterfly Network and is divided into either bytes or nibbles (step  212 ). Finally, these bytes or nibbles are routed into the system&#39;s lookup table, for example Lookup Table  152  of  FIG. 1  (step  214 ). 
       FIG. 3  illustrates steps in an exemplary alternate method for use of programmable parallel computation and data manipulation accelerator in accordance with methods and systems consistent with the present invention. First, the user identifies a specific algorithm which the user wishes to accelerate (step  300 ). The user programs the system to perform the chosen algorithm through the system processors, for example by programming it into ARM  144  and ARC  146  of  FIG. 1  (step  302 ). The system performs the expansion process, copying the input data into the input registers, for example input registers R 0   100 , R 1   102 , R 2   104 , R 3   106 , R 4   108 , R 5   110 , R 6   112 , and R 7   114  of  FIG. 1  (step  304 ). Finally, the expanded bits from the input registers bypass the system&#39;s Butterfly and Inverse Butterfly Network, for example via Fly Bypass Path  116  of  FIG. 1 , and are routed to the system&#39;s output registers, for example output registers R 8   118 , R 9   120 , R 10   122 , R 11   124 , R 12   126 , R 13   128 , R 14   130 , and R 15   132  (step  306 ). 
       FIG. 4  illustrates steps in an exemplary alternate method for use of a programmable parallel computation and data manipulation accelerator in accordance with methods and systems consistent with the present invention. First, the user identifies a specific algorithm which the user wishes to accelerate (step  400 ). In this implementation, the butterfly and inverse butterfly network and the lookup table may be used separately, which may provide for two different algorithms being accelerated at the same time or two different portions of the same algorithm being accelerated at essentially the same time. The user programs the system to perform the chosen algorithm through the system processors, for example by programming it into ARM  144  and ARC  146  of  FIG. 1  (step  402 ). The system performs expansion on the input registers, for example, input registers R 0   100 , R 1   102 , R 2   104 , R 3   106 , R 4   108 , R 5   110 , R 6   112 , and R 7   114  of  FIG. 1  (step  404 ). Simultaneously, the system performs expansion on the alternate input registers, for example alternate input registers R 16   154 , R 17   156 , R 18   158 , R 19   160 , R 20   162 , R 21   164 , R 22   166 , and R 23   168  of  FIG. 1  (step  406 ). The expanded bits from the input registers bypass the system&#39;s Butterfly and Inverse Butterfly Network, for example via Fly Bypass Path  116  of  FIG. 1 , and are routed to the system&#39;s output registers, for example output registers R 8   118 , R 9   120 , R 10   122 , R 11   124 , R 12   126 , R 13   128 , R 14   130 , and R 15   132  (step  408 ). Simultaneously, the expanded bits from the alternate input registers are converted into bytes or nibbles and routed into the system&#39;s lookup table, for example Lookup Table  152  of  FIG. 1  (step  410 ). 
     The foregoing description of various embodiments provides illustration and description, but is not intended to be exhaustive or to limit the invention to the precise form disclosed. Modifications and variations are possible in light of the above teachings or may be acquired from practice in accordance with the present invention. It is to be understood that the invention is intended to cover various modifications and equivalent arrangements included within the spirit and scope of the appended claims.