ECE 575 Data Security & Cryptography
Hardware Implementation of IDEA
(International Data Encryption Algorithm)
- Project Description Abstract Report
-
The International Data Encryption Algorithm (IDEA) was developed in Zurich, Switzerland
by James Massey and Xuejia Lai and published in 1990. It operates on 64-bit plaintext and
ciphertext blocks with a 128-bit key. IDEA is used by the popular program Pretty Good Privacy (PGP)
to encrypt files and electronic mail. Unfortunately, wider use of IDEA has been hampered by a
series of software patents on the algorithm, which is currently held until 2011 by Ascom-Tech AG
in Solothurn, Switzerland. MediaCrypt offers a royalty-free license for non-commercial use.
IDEA is somewhat different from the rest of the symmetric key encryption algorithms in that it uses
algebraic operations completely and does without table lookup methods. It employs a modified 4-word
Feistel style round function system. The strength of IDEA lies in its modulo multiplication
operations and therefore, it relies heavily on modular inversion.
My project is broken up into 5 parts, which are the IDEA core, the key schedulers for encryption and
decryption, the modular multiplier and the modular inverter. They are explained as follows:
- IDEA Core (idea_core.vhd) Block Diagram
Datapath
The sequential design of the IDEA core demonstrates the
functionality of IDEA. It performs an encryption operation
on 64 bits of plaintext given a 128-bit key. The key is
held at the input for 9 clock cycles in order to obtain
the correct ciphertext at the output.
For decryption, the ciphertext is given as an input. However,
the key is held for an unaccounted number of clock cycles
in order to get the resulting plaintext. This is due to the
hardware computation of the inverse of the sub-keys.
- Encryption Key Scheduler (key_enc.vhd)
IDEA partitions the original 128-bit key into eight 16-bit
sub-blocks that are directly used as the first eight key
sub-blocks. The 128-bit key is then rotationally shifted
left by 25 bits, after which the resulting 128-bit block
is again partitioned to produce another eight 16-bit key
sub-blocks.
- Decryption Key Scheduler (key_dec.vhd)
IDEA partitions the original 128-bit key into eight 16-bit
sub-blocks. The 128-bit key is then rotationally shifted
left by 25 bits, after which the resulting 128-bit block
is again partitioned to produce another eight 16-bit key
sub-blocks. These key sub-blocks are inverted/rearranged
with respect to key_enc.vhd to produce the decryption key schedule.
- Modular Multiplier (mult_mod.vhd)
The strength of IDEA lies in this combinational module of
multiplication modulo 2^16+1 (or mod 65537). Zeros are treated as
2^16 = 0x10000.
In order to account for converting modulo 2^16 to modulo 2^16+1,
the 34-bit vector exhibits a very interesting property: Any bits
that appear past 2^16 will contribute to subtracting the 34-bit
vector mod 2^16 to produce the result. Hence, if a=34-bit vector,
the result would be mod(a,2^16)-floor(a/2^16)+b where b is the
correction bit that is determined from a negative subtraction result.
This MATLAB code illustrates that property: modexample.m
- Modular Inverter/Divider (inv_mod.vhd)
This module finds the multiplicative inverse of a sub-key mod 2^16+1.
The inverse always exists since 2^16+1 is relatively prime for all
numbers 1 to 2^16 (0 is treated as 2^16).
This multiplicative inverter is essentially a modular divider based on
the extended binary Euclidean GCD plus-minus algorithm presented by
Naofumi Takagi in his paper "A VLSI Algorithm for Modular Division Based
on the Binary GCD Algorithm".
The algorithm is laid out in this MATLAB code: inverse.m
- Demonstration Encryption.jpg Decryption.jpg
-
- Download idea.tar.gz
- Unzip: % gunzip idea.tar.gz
- Untar: % tar -xvf idea.tar
- Simulate encryption: % source encrypt
- Simulate decryption: % source decrypt
Simulation results tally with Irwin Yoon's results: result2.txt
- Synthesis Results
-
- References
-