FONT SIZE : AAA
The overall structure of the DES algorithm is shown in Figure 19.1.
The core algorithm is repeated 16 times with a different subkey for each round. These subkeys are 48 bits long and are generated from the original 56-bit key. The algorithm was converted directly to VHDL using a functional decomposition style (i.e., functions were created to represent each equivalent function in DES).
The first stage in this design was to create an entity and an architecture with the required inputs and outputs and a single process containing the overall algorithm. This resulted in the VHDL outline here:
library ieee;
use ieee.std_logic_1164.all;
entity DES is
port (
plaintext : in std_logic_vector(1 to 64);
key : in std_logic_vector(1 to 64);
encrypt : in std_logic;
go : in std_logic;
ciphertext : out std_logic_vector(1 to 64);
done : out std_logic
);
end;
architecture behavior of DES is
subtype vec56 is std_logic_vector(1 to 56);
.
subtype vec64 is std_logic_vector(1 to 64);
begin
process
begin
wait until go = 1;
done <= 0;
wait for 0 ns;
ciphertext <=
des_core(plaintext, key_reduce(key), encrypt);
done <= 1;
end process;
end;
This process is a direct implementation of the main DES routine. The only implementation-specific feature is that the model waits for the signal go to be raised before
Figure 19.1 Overall structure of the DES algorithm.
starting processing and it raises the signal done at the end of processing, implementing a basic handshaking protocol.
This algorithm requires the two functions key_reduce and des_core. The former strips the parity bits from the key and the latter then implements the whole DES algorithm. The key_reduce function reduces the key from 64 to 56 bits and permutes the bits to form the initial state of the subkey:
function key_reduce(key : in vec64) return vec56 is
−−moods inline
begin
return
key(57) & key(49) & key(41) & key(33) &
.
key(28) & key(20) & key(12) & key(4);
end;
The compiler directive –moods inline causes the synthesizer to inline the function. This allows the optimizer more scope for optimization of the circuit. The des_core function applies the basic DES algorithm 16 times on a slice of the data using a different subkey on each iteration:
function des_core
−−moods inline
(plaintext : vec64;
key : vec56;
encrypt : std_logic)
return vec64
is
variable data : vec64;
variable working_key : vec56 := key;
begin
data := initial_permutation(plaintext);
for round in 0 to 15 loop
working_key :=
key_rotate(working_key,round,encrypt);
data := data(33 to 64) &
(f(data(33 to 64),key_compress(working_key))
xor
data(1 to 32));
end loop;
return
final_permutation(data(33 to 64) & data(1 to 32));
end;
The DES algorithm is made up of the key transformation functions key_rotate and key_compress, and the data transformation functions initial_permutation, f and final_permutation.
The data transformations initial_permutation and final_permutation are simply hard-wired bit-swapping routines implemented using concatenation.
function initial_permutation(data : vec64) return vec64 is
begin
−−moods inline
return
data(58) & data(50) & data(42) & data(34) &
.
data(31) & data(23) & data(15) & data(7);
end;
function final_permutation(data : in vec64) return vec64 is
begin
−−moods inline
return
data(40) & data(8) & data(48) & data(16) &
.
data(49) & data(17) & data(57) & data(25);
end;
The f function is the main data transform, which is applied 16 times to the rightmost half, a 32-bit slice, of the data path. It takes as its second argument a 48-bit subkey generated by the key_compress function.
function f(data : vec32; subkey : vec48) return vec32 is
begin
−−moods inline
return permute(substitute(expand(data) xor
subkey));
end;
The function first takes the 32-bit slice of the datapath and expands it into 48 bits using the expand function. The expand function is again just a rearrangement of bits; input bits are replicated in a special pattern to expand the 32-bit input to the 48-bit output.
function expand(data : vec32) return vec48 is
begin
−−moods inline
return
data(32) & data(1) & data(2) &
.
data(31) & data(32) & data(1);
end;
This expanded word is then exclusive-ORed with the subkey and fed into a substitute block. This substitutes a different 4-bit pattern for each 6-bit slice of the input pattern (remember that the original input has been expanded from 32 bits to 48 bits, so there are eight substitutions in all). The substitution also has the effect of reducing the output back to 32 bits again. The
substitute algorithm first splits the input 48 bits into eight 6-bit slices. Each slice is then used to lookup a substitution pattern for that 6-bit input. This structure is known as the S-block. In the initial implementation, a single ROM is used to store all the substitution patterns. The substitution combines a block index with the input data to form an address, which is then used to lookup the substitution value in the S-block ROM. This address calculation is encapsulated in the smap function.
function smap(index : vec3; data : vec6) return vec4 is
−−moods inline
type S_block_type is
array(0 to 511) of natural range 0 to 15;
constant S_block : S_block_type :=
−−moods ROM
(
14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7,
.
2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11
);
begin
return
vec4(to_unsigned(S_block(to_integer(unsigned(
index & data(1) & data(6) & data(2 to 5)))), 4));
end;
The eight substitutions are carried out by the eight calls to smap in the substitute function.
function substitute(data : vec48) return vec32 is
−−moods inline
begin
return
smap("000",data(1 to 6)) &
.
smap("111",data(43 to 48));
end;
The final stage of the datapath transform is the permute function, which is another bit-swapping routine:
function permute (data : in vec32) return vec32 is
−−moods inline
begin
return
data(16) & data(7) & data(20) & data(21) &
.
data(22) & data(11) & data(4) & data(25);
end;
These functions define the whole of the datapath part of the algorithm.
The encryption key also needs to be transformed a number of times—specifically, before each data transformation, the key is rotated and then a smaller subkey is extracted by selecting 48 of the 56 bits of the key. The rotation is the most complicated part of the key transformation. The 56-bit key is split into two halves and each half rotated by 0, 1, or 2 bits depending on which round of the DES algorithm is being implemented. The direction of the rotation is to the left during encryption and to the right during decryption. The algorithm is split into two functions: do_rotate which, as the name suggests, does the rotation, and key_rotate which calls do_rotate twice, once for each half of the key. The do_rotate function uses a ROM to store the rotate distances for each round, numbered from 0 to 15:
function do_rotate
−−moods inline
(key : in vec28;
round : natural range 0 to 15;
encrypt : std_logic)
return vec28 is
type distance_type is
array (natural range 0 to 15) of integer range 0 to 2;
constant encrypt_shift_distance : distance_type :=
−−moods ROM
(1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1);
constant decrypt_shift_distance : distance_type :=
−−moods ROM
(0, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1);
variable result : vec28;
begin
if encrypt = 1 then
result :=
vec28(unsigned(key) rol
encrypt_shift_distance(round));
else
result :=
vec28(unsigned(key) ror
decrypt_shift_distance(round));
end if;
return result;
end;
The key_rotate function simply calls the previous function twice:
function key_rotate
−−moods inline
(key : in vec56;
round : natural range 0 to 15;
encrypt : std_logic)
return vec56 is
begin
return do_rotate(key(1 to 28),round,encrypt) &
do_rotate(key(29 to 56),round,encrypt);
end;
Finally, the key compression function key_compress selects 48 of the 56 bits to pass to the S-block algorithm.
function key_compress(key : in vec56) return vec48 is
begin
−−moods inline
return
key(14) & key(17) & key(11) & key(24) &
.
key(50) & key(36) & key(29) & key(32);
end;
Manufacturer:Xilinx
Product Categories:
Lifecycle:Obsolete -
RoHS: No RoHS
Manufacturer:Xilinx
Product Categories:
Lifecycle:Obsolete -
RoHS:
Manufacturer:Xilinx
Product Categories: FPGAs (Field Programmable Gate Array)
Lifecycle:Obsolete -
RoHS:
Manufacturer:Xilinx
Product Categories:
Lifecycle:Obsolete -
RoHS:
Manufacturer:Xilinx
Product Categories:
Lifecycle:Obsolete -
RoHS: No RoHS
Support
