DES-Functions.html

DES functions

maymk@slu.edu

A collection of procedures used in DES

>

To execute DES we need to define quite a number of functions. It seems best to collect them on one worksheet so they can all be loaded in at once.

The first 4 sections of functions are needed to be able to step through a single round of DES. They deal with form conversion, applying permutations, using XOR, and reading s-boxes.

The next section of functions produces the f function, so that a round may be done in closer to a single step. These first 5 sections let you through most of the DES Example worksheet that looks at encoding a single block.

The last three sections of functions are designed to do operations as a single procedure, so that you can focus on modes of operating DES rather than on the functioning with a single block. Of those 3 sections, the first deals with key expansion, the second deals with encrypting and decrypting with DES, and the third deals with converting a longer message between an ASCII string and a vector of 8-byte hex words.

Conversion between different data types

The first section of code contains functions to convert to hex or binary and keep the correct length

>      #When we convert a decimal equivalent to hex, we want 2-digit hex
hex2digit := x -> if x < 16 then cat(`0`,convert(x,hex))
                  else convert(x,hex) fi:
  #We want to convert an ASCII string of up to 8 characters to a
  #64 bit binary string.
bin64 := proc(shortstring)
  local temp,l1,missing,i, binstr:
  temp := convert(shortstring,bytes):
  l1 := max(1,length(shortstring)):
  binstr := convert(convert( cat(seq(hex2digit(temp[i]),i=1..l1)),
                      decimal,hex),binary):
  missing := 64 -length(binstr):
  cat(seq(`0`,i=1..missing),binstr):
end:
  #We want to convert an ASCII string of up to 8 characters to a
  #16 character hex string.
ASCII2hex16 := proc(shortstring)
  local temp,l1,missing,i, hexstr:
  temp := convert(shortstring,bytes):
  l1 := max(1,length(shortstring)):
  hexstr := cat(seq(hex2digit(temp[i]),i=1..l1)):
  missing := 16 -length(hexstr):
  cat(seq(`0`,i=1..missing),hexstr):
end:
  #We want to convert an hex string of up to 16 characters to a
  #64 bit binary string.
bin64hex := proc(hexstring)
  local temp,l1,missing,i, binstr:
  l1 := 16 - max(1,length(hexstring)):
  temp := cat(seq("0",i=1..l1),hexstring):
  binstr := convert(convert( temp,decimal,hex),binary):
  missing := 64 -max(1,length(binstr)):
  cat(seq("0",i=1..missing),binstr):
end:
  #The contents of s-boxes should be converted to 4 bit binary
fourbitbin := decnum ->
     substring(convert(convert(decnum+16,binary),string),2..5):

String permutations and XORing

We want functions to do the various permutation expansions.

> PC1onKey := binstr -> cat(seq(substring(binstr,PC1[i]),i=1..56)):
PC2onKey := binstr -> cat(seq(substring(binstr,PC2[i]),i=1..48)):
expander := binstr -> cat(seq(substring(binstr,E[i]),i=1..48)):
InitPerm := binstr -> cat(seq(substring(binstr,IP[i]),i=1..64)):
FinalPerm := binstr -> cat(seq(substring(binstr,IPI[i]),i=1..64)):
PPerm := binstr -> cat(seq(substring(binstr,P[i]),i=1..32)):

We need to be able to do XOR on 64, 48, and 32 bit strings.
We would also like to be able to XOR two 64 bit strings that are given in hex format.

>    XOR := (a,b) -> if (a=b) then "0" else "1" fi:
xorNbits := proc(a,b,N)
  local aString, bString:
  aString := convert(a,string):
  bString := convert(b,string):
  cat(seq(XOR(substring(aString,i), substring(bString,i)),i=1..N)):
end:
xor64 := (a,b) -> xorNbits(a,b,64):
xor48 := (a,b) -> xorNbits(a,b,48):
xor32 := (a,b) -> xorNbits(a,b,32):

xor64hex := proc(a,b)
  local binab, hexab, i, l:
  binab := xor64(bin64hex(a),bin64hex(b)):
  hexab := convert(convert(parse(binab),decimal,binary),hex):
  l := 16 - length(hexab):
  cat(seq("0",i=1..l),hexab):
end:

SBoxes and the f function

To do the s-box substitutions, we want to be able to cut the 48 bit word into a vector of 6 bit words. Since we have made the SBox a list of tables with 4 bit entries indexed by 6 bit strings, looking up SBox values is straightforward.

>    prodbs := proc(binstr)
  local bvec,i:
  bvec := linalg[vector](8):
  for i from 1 to 8 do
    bvec[i] := substring(binstr,i*6-5..i*6):
  od:
  convert(bvec,list):
end:

We now want a single function that corresponds to the f function discussed in class and in the text. It should takes a round key and a half word, expand the half word and xor with the round key, then cut the 48 bit result into 8 6 bit strings that are used for SBox look ups. The results are concatenated together and permuted according to the rule.

>    fcomb := proc(ri, ki)
  local t1,t2, t3, vec1, vec2, i:
  t1 := xor48(ki,expander(ri)):
  vec1 := prodbs(t1):
  vec2 := linalg[vector](8,[seq(SBox[i][vec1[i]],i=1..8)]):
  t2 := cat(seq(vec2[i],i=1..8)):
  t3 := PPerm(t2):
end:

One line commands

When we are ready to look at using DES on more than 64 bits of information at a time we want to be able to do key expansion and DES encryption with single commands.

keyexpander takes a hex string as input and produces a list of the 16 subkeys.

>    keyexpander := proc(hexstring)
  local keybin, binlength, keybin64, PC1key, c, d, key, i:
  keybin:= convert(convert(hexstring,decimal,hex),binary):
  binlength := length(keybin):
  keybin64 := cat(seq(`0`,i=1..(64-binlength)),keybin):
  PC1key := PC1onKey(keybin64):
  c := linalg[vector](17): d := linalg[vector](17):
  key := linalg[vector](16):
  c[1] := substring(PC1key,1..28): d[1]:=substring(PC1key,29..56):
  for i from 2 to 17 do
     c[i] := cat(substring(c[i-1],keyshifts[i-1]+1..28),
                 substring(c[i-1],1..keyshifts[i-1])):
     d[i] := cat(substring(d[i-1],keyshifts[i-1]+1..28),
                 substring(d[i-1],1..keyshifts[i-1])):
  od:
  for i from 1 to 16 do
    key[i] := convert(PC2onKey(cat(c[i+1],d[i+1])),string);
  od:
  key := convert(key,list):
end:

The command qdDEShex (qd for quick and dirty) uses DES and a vector of subkeys to encode a hex input. The input should be no more than 16 hex digits long.

The command qdDESASCII encodes an ASCII string that is no more than 8 characters long.

The command unDEShex decodes a hex string.

>    qdDEShex := proc(hexstring,keyvec)
local bin2, R, i, keytriv,code1,code2, code3, l1:
keytriv := cat(seq(`0`,j=1..48));
bin2 := InitPerm(bin64hex(hexstring));
R := linalg[vector](18):
R[2] := substring(bin2,33..64);
R[1] := substring(bin2,1..32);
for i from 1 to 16 do
   R[i+2] := xor32(R[i],fcomb(R[i+1],keyvec[i]));
od:
code1 := cat(R[18],R[17]);
code2 := FinalPerm(code1);
code3 := convert(convert(parse(code2),decimal,binary),hex);
l1 := length(code3);
cat(seq("0",i=1..(16-l1)),code3);
end:
unDEShex := proc(hexstring,keyvec)
local bin2, R, i, keytriv,code1,code2, code3, l1:
keytriv := cat(seq("0",j=1..48));
bin2 := InitPerm(bin64hex(hexstring));
R := linalg[vector](18):
R[17] := substring(bin2,33..64);
R[18] := substring(bin2,1..32);
for i from 1 to 16 do
   R[17-i] := xor32(R[19-i],fcomb(R[18-i],keyvec[17-i]));
od:
code1 := cat(R[1],R[2]);
code2 := FinalPerm(code1);
code3 := convert(convert(parse(code2),decimal,binary),hex);
l1 := length(code3);
cat(seq("0",i=1..(16-l1)),code3);
end:
qdDESASCII := proc(ASCIIstring,keyvec)
local bin2, R, i, keytriv,code1,code2, code3, l1:
keytriv := cat(seq("0",j=1..48));
bin2 := InitPerm(bin64(ASCIIstring));
R := linalg[vector](18):
R[2] := substring(bin2,33..64);
R[1] := substring(bin2,1..32);
for i from 1 to 16 do
   R[i+2] := xor32(R[i],fcomb(R[i+1],keyvec[i]));
od:
code1 := cat(R[18],R[17]);
code2 := FinalPerm(code1);
code3 := convert(convert(parse(code2),decimal,binary),hex);
l1 := length(code3);
cat(seq("0",i=1..(16-l1)),code3);
end:

More data type conversions

If we are going to use DES on a longer message, we want to convert the message from an ASCII string to a vector of hex words with each word being 16 characters long.

>      #When we convert a decimal equivalent to hex, we want 2-digit hex
hex2digit := x -> if x < 16 then cat(`0`,convert(x,hex))
                  else convert(x,hex) fi:
asciistrtohexword := proc(messagestring)
  local stringofhex, lenofstr, roundlen, padding, wordlen, temp, j, i, k:
    #First we convert the ASCII string to a list of decimal equivalents
    #Then we convert thedecimal numbers to 2 place hex equivalents
  lenofstr := length(messagestring);
  stringofhex := map(hex2digit, convert(messagestring,bytes)):
    #Time to compute the appropriate lengths
  roundlen := lenofstr + 7 - (lenofstr + 7 mod 8);
  padding := roundlen - lenofstr:
  wordlen := roundlen/8:
    #Now we put togehter hex words
  temp := linalg[vector](wordlen):
  for i from 1 to (wordlen -1) do
    temp[i] := cat(seq(stringofhex[j],j=(i*8-7)..i*8)):
  od:
  temp[wordlen] :=cat(seq(stringofhex[j], j=(roundlen-7)..lenofstr),
                    seq(`00`,k=1..padding)):
    #Finally we convert the vector to a list
  convert(temp,list):
end:
hexwordtoasciistr := proc(wordlist)
  local l1, temp, i, j, vec1:
  vec1 := convert(wordlist,array):
  l1 := linalg[vectdim](wordlist):
  temp := linalg[vector](8*l1):
  for i from 1 to l1 do
    for j from 1 to 8 do
      temp[j+8*(i-1)] := substring(wordlist[i],2*j-1..2*j):
    od:
  od:
  temp := convert(temp,list):
  convert(map(convert,temp,decimal,hex),bytes):
end:

Saving constants and functions

Rather than rerunning the DES constants and DES functions worksheets each time we can save the functions and constants in a file named DES.m. This file will be created in the same directory as the Maple application.

> save
SBox, PC1, PC2, keyshifts, IP, E, P, IPI,
hex2digit, bin64, ASCII2hex16, bin64hex, fourbitbin,
PC1onKey, PC2onKey, expander, InitPerm, FinalPerm, PPerm,
XOR, xorNbits, xor64, xor48, xor32, xor64hex,
prodbs, fcomb, keyexpander, qdDEShex, unDEShex,
qdDESASCII,
hex2digit, asciistrtohexword, hexwordtoasciistr,
`DES.m`;

Next you need to execute the worksheet on DES Key Expansion

>