From: nobody@REPLAY.COM (Anonymous)
Date: Sat, 28 Oct 95 05:50:17 PDT
To: cypherpunks@toad.com
Subject: EE Times on IDEA
Message-ID: <199510281250.NAA14958@utopia.hacktic.nl>
MIME-Version: 1.0
Content-Type: text/plain


Electronic Engineering Times
Oct 23, 1995 p. 66

T.R MADHUSUDAN SASTRY,
T. GANESAN, B.MADHUKAR
AND N. SRINIVASA

MOTOROLA INDIA ELECTRONICS Pvt. Ltd.
BANGALORE, INDIA

Time is right for a good, secure 'Idea'

Computers are the medium in which almost all of today's business deals and international transaction transpire. That calls for the development of secure systems, which protect data from being accessed by unautho-rized users. Digital Encryption Standard (DES) is a cipher system that uses a 64-bit-long secret key. With present comput-er technology, it is not difficult to break DES by trying all possible keys. That made cryptographers look for different encryption algorithms that take a long time for today's computers to break the code. The International Data Encryption Algorithm (Idea) is a private key-block ciphering scheme, which is computationally highly secure since it uses a 128-bit-long secret key. The brute force method of breaking the code, (trying all possible combinations as keys) would require 10^24 years for a chip that can test a billion keys per second. The design philosophy of Idea is to niix the operations from different algebraic groups to add confusion and di!
 ffusion to the input data. The operations are addition modulo, multiplication modulo, and exclusive OR (XOR).

We have implemented Idea in electronic-code-book (ECB) mode on the Motorola DSP 561xx family of processors. In ECB mode, a 64 bit input block is encrypted to generate a 64-bit output block that is transmitted to the receiver through insecure but error free channels. In Idea, all the algebraic operations work with 16-bit blocks of data. That makes the algorithm efficient on a 56 to DSP, which has a very good instructioln set to perform the addi-tion modulo 2^16, multiplication modulo 2^16 + 1 and 16-bit XOR operations.

The Idea is a block-cipher scheme in which the incoming data is divided into blocks of 64 bits and fed as input to the encryption algorithm (see figure). The 64 bit data X= (X1 X2 X3 . . . X64) is initially divided into 4 subblocks X1, X2, X3 and X4each of 16 bits. These four sub-blocks become input for the first round of operation. In each round, each subblock is added and multiplied under modulo fields with key subblocks, thus adding more confusion and diision.

The sequence of operations for the first round is given below; it's the same for all rounds of operations except for different key subblocks.

[1] Multiply X1 and Kl, (first key subblock Zl^l) under modulo 2^16 + 1
[2] Add X2 and K2 (Z2^1) under modulo 2^16
[3] Add X3 and K3 under modulo 2^16  
[4] Multiply X4 and K4 under modulo 2^16 + 1
[5] XOR the results of step 1 and step 3
[6] XOR the results of step 2 and step 4
[7] Multiply the results of step 5 and K5 under modulo 2^l6 + 1
[8] Add the results of step 6 and step 7
[9] Multiply the re sults of step 8 and K6 under modulo 2^16 + 1 .
[10] Add the results of step 7 and step 9 under modulo 2^16
[11] XOR the results of step 1 and step 9
[12] XOR the results of step 3 and step 9
[13] XOR the results of step 2 and step 10
[14] XOR the results of step 4 and step 10

The results of each round from steps 11, 12, 13, and 14 form the  input blocks for the second round of opera-
tion after swapping the two inner blocks (see figure). After eight rounds are over, the following transformation has to be done before taking output cipher text. It should be noted that swapping is not done for the
last round.

[1] Multiply X1 and the 49th key subblock K49 (Z1^9)
[2] Add X2 and the 50th key subblock to k50 (Z2^9)
[3] Add X3 and the 51st key subblock k51 (Z3^9)
[4] Multiply X4 and the 52nd key subblock K51(Z3^9)

The decryption algorithm is also exactly the same except for the change in the subblock keys. From each of the key subblocks in the encryption, either additive inverse or multipli
cative inverse is used. For example, the subblock key used to multiply this data subblock is re placed with its multiplicative inverse. Also the order in which that multiplicative and additive inverse occurs in the decryption algorithm takes care of the shuffling of the intermediate data subblocks.

As stated earlier the encryption key is 128 bits long. The 52 encryption subblock keys are derived from the encryption key, and the corresponding subblock keys are derived from the encryption-key subblocks. The key subblocks for the first round of encryption are derived by dividing the 128-bit-long key into 16-bit blocks. Then, for every next round, the encryption key is circularly shifted by 25 bits and then divided into 16-bit blocks to yield encryption-key subblocks. In the last round, only the first four key subblocks are generated.

The Idea can be implemented in all three modes of operation: ECB, output-feedback mode (OFB) and cipher-feedback mode (CFB). In ECB, the input is split into 64-bit blocks, encrypted and transmitted. In CFB, the output cipher text from one block of encryption is used to form part of in input block. And the output of the algorithm is XORed with the input plain text, and transmitted. Similarly, the feedback is taken after
the XORing operation. In thepresent implementation, only ECB mode is done, which is the fastest among the three.

Since all the operations are on 16-bit blocks, the powerful instruction set of 561xx can beused for efficient implementation. The modulo 2^16 + 1 multiplication operation is used many times, and it is computationally intensive when compared with XOR and modulo 2^16 addition. The fixed-point multiplication construction of 561xx can be utilized to perform 32-bit multiplication.

The modulo 2^16 addition operation can be done just by ignoring the carry of 16-bit addition in 561xx. The XOR operation is also supported in one instruction as in any other DSP processor. Hence all three algebraic operations can be implemented efficiently using the instruction set of 561xx

Again the decryption algorithm is exactly the same as the encryption algorithm, except, that the decryption-key sub block is used instead of encryption. The whole program can be reused for decryption by changing the input variables and output variables.

Circular shift 
The main computation in encryption-key subblock generation is the circular shift of the l28-bit-long key. The encryption key can be stored as eight words in memory. In the present implementation, instead of shifting the key circularly, the mask patterns are used to pick up suitable key subblocks. That is, the second set of eight key subblocks can be generated by picking up 16 bits from the ninth bit of the second word of the encryption key.                 

Hence, for each round, we need to multiply each encryption key word by a suitable mask pattern, and left shift it with a suitable number of bits. The left-shifting operation for any arbitrary number of bits can be performed using the integer multiplication. Storing the mask patterns can be eliminated by using the shifted version
of left-shift constants as right-shift constants. The left-shift constant is multiplied with the current encryption-key word, and the right-shift constant is multiplied with the next keyword, and both are combined to
generate one key subblock. The right-shift constants are gotten by right shifting the left shift constant by 1 bit, which considerably reduces the computation involved. The current implementation of Idea in ECB on Motorola's DSP 56166 running at 60 Mhz supports up to 625 kbits/second in full-duplex mode. That is 3.6
times faster than using the DES algorithm.