Method and system for performing permutations using permutation instructions based on butterfly networks

Abstract

The present invention provides permutation instructions which can be used in software executed in a programmable processor for solving permutation problems in cryptography, multimedia and other applications. The permute instructions are based on a Benes network comprising two butterfly networks of the same size connected back-to-back. Intermediate sequences of bits are defined that an initial sequence of bits from a source register are transformed into. Each intermediate sequence of bits is used as input to a subsequent permutation instruction. Permutation instructions are determined for permitting the initial source sequence of bits into one or more intermediate sequence of bits until a desired sequence is obtained. The intermediate sequences of bits are determined by configuration bits. The permutation instructions form a permutation instruction sequence of at least one instruction. At most 21gr / m permutation instructions are used in the permutation instruction sequence, where r is the number of k-bit subwords to be permuted, and m is the number of network stages executed in one instruction. The permutation instructions can be used to permute k-bit subwords packed into an n-bit word, where k can be 1, 2, . . . , or n bits, and k*r=n.

Description

BACKGROUND OF THE INVENTION [0001] 1. Field of the Invention [0002] The present invention relates to a method and system for performing arbitrary permutations of a sequence of bits in a programmable processor by determining a permutation instruction based on butterfly networks. [0003] 2. Description of the Related Art [0004] The need for secure information processing has increased with the increasing use of the public internet and wireless communications in e-commerce, e-business and personal use. Typical use of the internet is not secure. Secure information processing typically includes authentication of users and host machines, confidentiality of messages sent over public networks, and assurances that messages, programs and data have not been maliciously changed. Conventional solutions have provided security functions by using different security protocols employing different cryptographic algorithms, such as public key, symmetric key and hash algorithms. [0005] For encrypting larg...

AI Technical Summary

Benefits of technology

"The present invention provides permutation instructions that can be used in software for solving permutation problems in both cryptography and multimedia. These instructions can be used in a programmable processor to perform fast cryptography and fast multimedia processing. The permutation instructions can be added to existing processors or used in the design of new processors or coprocessors. The method uses a Benes interconnection network to perform the permutations by executing a certain number of stages with the permute instructions. The permutation instructions are determined by intermediate sequences of bits and form a permutation instruction sequence. The method can be scaled for performing permutations of 2n bits in which subwords are packed into two or more registers. Overall, the invention provides a flexible and efficient solution for performing permutations in software."

Problems solved by technology

This implementation may yield a larger size due to more vertical tracks used.

Images