The Research Of Bit Permutation Networks And Applications In Cryptographic Processors

Bit permutation is an irreplaceable way to achieve diffusion and is widely used in many block ciphers. But as a typical bit-level operation, bit permutation operation is identified as the only one that is not well-supported on the existing processors. The performance of software implemented cryptopraphic functions is hampered by bit permutation operation which has not been optimized in a processor's instruction set architecture.This thesis investigates the characteristics and implementation techniques of bit permutation operation in block ciphers. A new class of permutation instructions based on the LPS interconnection network which can be used to perform arbitrary permutation of N bits within log₂N cycles is proposed to address the bit permutation problem. In order to fit in the existing datapath of typical processors, it has the same format as many other instructions, which have two source registers and one destination register. The instruction coding is quite simple and can permute 2N bits on N-bit systems. Only two LPS stages are needed to implement the basic permutation instruction. For the purpose of greater efficiency, this thesis proposes a different class instruction which requires three operands and one result feed back. It can achieve arbitrary N-bit permutation within [log₂N/2] cycles and needs four LPS stages at the circuit level.Based on VLIW architecture, a specific permutaion instructions for coprocessor for block ciphers is proposed, which is based on Batcher network or Benes network. The circuit implementation of the instructions is 10.2% of the method of using N N:1 multiplexers. A method to solve multi-bit subword permutation problems is also proposed.