------------------------------------------------------------------------------
-  000  000  000                                 C O O K I E C R K ' 2 0 0 0 -
-  0  0 0   0      Data                                                      -
-  0  0 00  000        Encryption                Temat: Implementacja DES'a  -
-  0  0 0      0                 Standard        Autor: ZetX                 -
-  000  000 000                                                              -
------------------------------------------------------------------------------


Spis tresci :

-1- Wstepniak
-2- Algorytm
-3- Implementacja :)
-4- Inne 


-1- Wstep do DES'a
Ten kto czytal co nie co o szyfrowaniu w roznych ksiazkach lub w tekstach
Beanusa mogl popasc w pewne zniechecenie z braku namacalnych dowodow dotycza-
cych kryptografi. Teoria to jedno, a praktyka to drugie. Praktyka czyli imple-
mentacja. Mimo, ze niektore algorytmy sa zapisane bardzo skomplikowanie (przy-
najmniej na pierwszy rzut oka) to po glebszej analizie mozna je zrozumiec i
napisac program, ktory bedzie sie nim poslugiwal.
Standard to standard, wiec pomyslalem, ze najlepiej od niego zaczac... wiec
pokusilem sie o programowe opracowanie algorytmu DES. Poza tym kazdy kto choc
troche zaglebil sie w temat kryptografi slyszal o tym algorytmie - ponoc kie-
dys byl nie do zlamania (przynajmniej w krotkim czasie i za mala kase - czytaj
txt Beanusa o DES'ie). Nie bede sie dalej rozpisywal lejac wode i przejde do
konkretow, dodam tylko, ze implementacja bedzie wykonana w jezyku C++.
Aha! Wazna rzecz... operacje sa przeprowadzane na bitach. Hmmm... myslalem jak
to zorganizowac w prosty sposob w C++ i wymyslilem - stowrzylem strukture
jedno-bitowa, a potem odpowiednio ich tablice, np. 64-elementowa - czyli daje
to 64 bity :)
Jak ktos zna prostrzy sposob to niech do mnie sie zglosi... bardzo mi na tym
zalezy, bo wiadomo - bity mniej zajmuja niz 64 intiger'y :)
(oczywiscie tekst do szyfrowania jest podawany w charach [znakach], ale potem
nastepuje moja wlasna konwersja na tablice bitow... spojrzcie w kod i przeana-
lizujcie. Moze cos da sie zrobic czybciej?)


-2- Algorytm
DES zajmuje sie szyfrowaniem 64-bitowych blokow danych przy pomocy 64-bitowe-
go klucza. Zaraz, zaraz!- Ktos tam krzyknie - Przeciez w ksiazce jest napisa-
ne, ze klucz ma 56-bitow... jezeli jednak dobrze sie wczytamy mozemy dostrzec,
gdzie tkwi przeklamanie.
Otoz DES rozpoczyna prace z kluczem o dlugosci 64-bitow, lecz po pierwszej pe-
rmutacji nastpuje redukcja do owych 56-bitow, gdyz z podstawowego klucza wy-
rzucane zostaja bity parzystosci. Bity te znajduja sie na pozycjach:
8,16,24,32,40,48,56,64 - ktorych indeksy sa opuszczone w pierwszej tablicy
permutacji klucza (tab. PC_1).
OK. Wyjasnilismy male niescislosci i przejdzmy do dzialania.
Cala implementacje proponuje rozpoczac od generacji kluczy - jest ich 16 i po-
wstaja w lekko skomplikowany sposob.
----
Moze ktos zastanawiac sie co oznacza permutacja wzgledem tablicy, wiec najle-
piej wyjasnic to na przykladzie - zalozmy, ze mamy:
tablice liczb A={10,12,23,67,32,16}
indeksy w tab. :  1  2  3  4  5  6
tablice permutacji po indeksach B={3,6,2,1,4,5}

to permutacja C=B(A)={23,16,12,10,67,32}
oczywiscie moze sie tak zdazyc, ze w tab. permutacji powtarzaja sie indeksy-
-co bedzie mialo miejsce w algorytmie.
----
Generacje kluczy rozpoczyna permutacja 64-bitowego klucza wzgledem PC_1 co
daje nam 56-bitowy klucz bez bitow parzystosci.
Nastepnie dzielimy te 56 bity na dwie czesci C i D, ktore maja po 28 bitow.
                                  K = CD
nasze C i D sa poczatkowymi warotsciami tak jak ten klucz wiec mozemy nadac
im indeksy 0:
                              K(0) = C(0)D(0)
by stworzyc pierwszy i kolejne klucze - K(1)...K(16) nalezy przesunac cykli-
cznie C i D w lewo o odpowiednia ilosc bitow podana w ponizszej tablicy, stad:

          C(i) = Left_Shift(C(i-1))     D(i) = Left_Shift(D(i-1))

nr. klucza | ilosc L_S
    1      |    1
    2      |    1
    3      |    2
    4      |    2
    5      |    2
    6      |    2
    7      |    2
    8      |    2
    9      |    1
    10     |    2
    11     |    2
    12     |    2
    13     |    2
    14     |    2
    15     |    2
    16     |    1



po przesunieciu laczymy w jedna calosc C(i)D(i) i permutujemy wzgledem tabli-
cy PC_2:
                              K(i) = PC_2(C(i)D(i))

Takim oto sposobem przebrnelismy przez generowanie kluczy potrzebnych do szy-
forwania bloku danych.

Zajmnijmy sie teraz naszmymi 64-bitami przygotowanymi do zaszyfrowania.
Oznaczmy nasz blok bitow duza litera T.
Tutaj tez rozpoczynamy od permutacji, ale wzgledem tablicy IP, ktora jednak
nie powoduje zmniejszenia naszego bloku, tylko zamiane bitow miejscami.
Tak wiec ciagle posiadamy 64 bity, ktore rozbijamy na dwie rowne sobie czesci:
               L - left(lewa) oraz R - right(prawa)
mamy:
                           T(i) = L(i)R(i)

i - oznacza liczbe kolejnych iteracji (bedzie ich 16 - takich samych, z malym
    wyjatkiem w ostatniej z nich)

W kolejnych iteracjach (krokach) nasza lewa i prawa strona 64-bitowgo bloku
bedzie ulegac zmianom wzgledem rownan:

                           L(i) = R(i-1)

                 R(i) = L(i-1) XOR f(R(i-1),K(i))

f - jest fukncja, ktora opisze ponizej
XOR - jest roznica symetryczna przeprowadzona na L(i-1) i wyniki f-cji f

Widzimy, ze f-cja dziala na dwoch argumentach : R(i-1) oraz K(i), poniewaz be-
dziemy chcieli te argumeny XORowac, wiec nalezy rozszerzyc 32-bitowe R(i-1) do
wielkosci klucza - czyli do 48-bitow.
Rozszerzenie polega na przeprowadzeniu permutacji wzgledem tablicy E, czego
wynik mozna juz poddac operacji XOR i wynik rozdzielic na bloki:

                 E(R(i-1) XOR K(i) = B(1)B(2)...B(8)

B(i) (i=1,2,...,8) sa to bloki 6-bitowe, latwo przeliczyc 6x8=48
Kazdy blok sklada sie z pojedynczych bitow oznaczonych mala litera "b"

                  B(i) = b(1)b(2)b(3)b(4)b(5)b(6)

Dla kazdego bloku B(i) istnieje tablica podstawien S(i). Zadanie polega na
okresleniu z jakiego WIERSZA i KOLUMNY tablicy S(i) wybrac podstawienie dla
bloku B(i) i tak:
bity b(1)b(6) - wiersz
bity b(2)b(3)b(4)b(5) - kolumna

np. B(1) = 110110
b(1)=1  \
         ---> b(1)b(6)=10   czyli   2
b(6)=0  /

b(2)=1 \
b(3)=0  \
         ---> b(2)b(3)b(4)b(5)=1011   czyli   11
b(4)=1  /
b(5)=1 /

wiesz=2   kolumna=11

Wartosciami kazdej tablicy S(i) sa 4-bitowe liczby, wiec w miejsce 6-bitowych
blokow B(1)B(2)...B(6) (48 bitow) jest wstawiany ciag 32-bitowy, ktory doda-
tkowo podlega permutacji wzgledem tablicy P. Ostatecznie mamy 32 bity postaci:

                  Z = P( S1(B1)S2(B2)...S(8)(B8) )

(  mala zmian ze wzgledu na czytelnosc S1(B1) = S(1)(B(1))  )

Ostateczne Z jest wynikiem naszej f-cji, wiec nalezy teraz przejsc do XORowa-
nia :

                        R(i) = L(i-1) XOR Z

i tak 16 razy - za kazdym razem uzywamy innego klucza...

Jak widac podczas kolejnych iteracji L i R sa zamieniane miejscami, ale
nie podczas ostatniej (ta mala roznica) i koncowy wynik to:

                              R(16)L(16)

ktory ulega ostatecznej permutacji wzgledem tablicy IP_1

                        Y = IP_2( R(16)L(16) )

Nasz Y jest zaszyfrowanym T przy pomocy DES'a : Y = DES(T)

Algorytm deszyfrujacy jest identyczny z mala roznica (bardzo logiczna jak
mozna zauwazyc) - rozpoczynamy go od klucza K(16) a konczymy na K(1).



-3- Implementacja
//Start programu

/*
Szyforawnie DES'em
autor: ZetX/CookieCrK
*/

#include <conio.h>
#include <stdio.h>

struct bit{
  unsigned int b:1;
};

bit bity[64],tempX[64],tempY[32],L[32],R[32],ER[48],SB[32];
bit k64[64],k56[56];
bit keys[16][48];

int IP[]=
{ 58,50,42,34,26,18,10,2,
  60,52,44,36,28,20,12,4,
  62,54,46,38,30,22,14,6,
  64,56,48,40,32,24,16,8,
  57,49,41,33,25,17, 9,1,
  59,51,43,35,27,19,11,3,
  61,53,45,37,29,21,13,5,
  63,55,47,39,31,23,15,7};

int IP_1[]=
{ 40,8,48,16,56,24,64,32,
  39,7,47,15,55,23,63,31,
  38,6,46,14,54,22,62,30,
  37,5,45,13,53,21,61,29,
  36,4,44,12,52,20,60,28,
  35,3,43,11,51,19,59,27,
  34,2,42,10,50,18,58,26,
  33,1,41, 9,49,17,57,25};

int E[]=
{ 32, 1, 2, 3, 4, 5,
  4, 5, 6, 7, 8, 9,
  8, 9,10,11,12,13,
  12,13,14,15,16,17,
  16,17,18,19,20,21,
  20,21,22,23,24,25,
  24,25,26,27,28,29,
  28,29,30,31,32, 1};

int P[]=
{ 16, 7,20,21,
  29,12,28,17,
  1,15,23,26,
  5,18,31,10,
  2, 8,24,14,
  32,27, 3, 9,
  19,13,30, 6,
  22,11, 4,25};

int Si[8][4][16]=
{
{{14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7},
 {0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8},
 {4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0},
 {15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13}},
{{15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10},
 {3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5},
 {0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15},
 {13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9}},
{{10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8},
 {13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1},
 {13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7},
 {1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12}},
{{7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15},
 {13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9},
 {10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4},
 {3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14}},
{{2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9},
 {14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6},
 {4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14},
 {11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3}},
{{12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11},
 {10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8},
 {9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6},
 {4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13}},
{{4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1},
 {13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6},
 {1,4,11,13,12,3,7,14,10,15,6,8,0,5,9,2},
 {6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12}},
{{13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7},
 {1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2},
 {7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8},
 {2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11}}
};

int PC_1[]=
{ 57,49,41,33,25,17, 9,
   1,58,50,42,34,26,18,
  10, 2,59,51,43,35,27,
  19,11, 3,60,52,44,36,
  63,55,47,39,31,23,15,
   7,62,54,46,38,30,22,
  14, 6,61,53,45,37,29,
  21,13, 5,28,20,12, 4};

int PC_2[]=
{ 14,17,11,24, 1, 5,
   3,28,15, 6,21,10,
  23,19,12, 4,26, 8,
  16, 7,27,20,13, 2,
  41,52,31,37,47,55,
  30,40,51,45,33,48,
  44,49,39,56,34,53,
  46,42,50,36,29,32};

int CD[]={1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1};

void na_bity(unsigned char znaki[],bit tab[],int n)
{					//f-cja laduje do tablicy n*8-bitow bity z tablicy n-znakow
 unsigned char shift;			        //char z ustawionym jednym bitem
 bit temp;				     		  	     //pojedynczy bit
 for (int poz=0;poz<n;poz++)		     //jest 8 znakow (8*8b=64b)
 {
  for (int i=7,j=0,zx=1;i>-1;i--,j++,zx=1)   //przesuwanie od lewej do prawej
  {					     //wiec od 7 bitu do zerowego
   for (int k=0;k<i;k++)		     //liczymy potege bitu
    zx*=2;
   shift=znaki[poz]&zx;		     	     //w znaku pozostawiamy jeden bit
   temp.b=shift>>i;			     //po przesunieciu zapis bitu
   tab[poz*8+j]=temp;			     //teraz bit do tablicy
  }
 }
}

void na_chary(bit tab[],unsigned char znaki[],int n)
{
 unsigned char shift;
 for (int poz=0;poz<n;poz++)
 {
  char temp=0;
  if (tab[poz*8+7].b) temp+=1;
  if (tab[poz*8+6].b) temp+=2;
  if (tab[poz*8+5].b) temp+=4;
  if (tab[poz*8+4].b) temp+=8;
  if (tab[poz*8+3].b) temp+=16;
  if (tab[poz*8+2].b) temp+=32;
  if (tab[poz*8+1].b) temp+=64;
  if (tab[poz*8].b) temp+=128;
  znaki[poz]=temp;
 }
}

void k1_k16()
{
 bit saveC,saveD;
 int zm;
 for (int i=0;i<56;i++)
 {
  k56[i]=k64[PC_1[i]-1];	//w k56 podstawowy klucz do tworzenia k1..k16
 }
 for (int k=0;k<16;k++)
 {
  zm=CD[k];
  while (zm)
  {
   saveC=k56[0];
   saveD=k56[28];
   for (int i=0;i<28;i++)
   {
    k56[i]=k56[i+1];
	 k56[i+28]=k56[i+28+1];
   }
   k56[27]=saveC;
   k56[55]=saveD;
   zm--;
  }
  for (int i=0;i<48;i++)
   keys[k][i]=k56[PC_2[i]-1];
 }
}

void des(bit blok[],int krypt)	//krypt=0 - szyfrowanie ; 1 - deszyfrowanie
{
 int end=1;
 for (int i=0;i<64;i++)
 {
  tempX[i]=blok[IP[i]-1];	//pierwsza permutacja ciagu 8 bajtow  (IP)
 }
 for (i=0;i<64;i++)
 {
  blok[i]=tempX[i];
 }
 for (i=0;i<32;i++)
 {
  L[i]=blok[i];			//L0
  R[i]=blok[i+32];		//R0
 }
 if (krypt==0) i=0;
 if (krypt==1) i=15;
 do
 {
  bit tempL[32];
  for (int j=0;j<32;j++)
  {
   tempL[j]=L[j];		//tempL=L(i-1)
   L[j]=R[j];			//L(i)=R(i-1)
  }
  for (j=0;j<48;j++)
  {
   ER[j]=R[E[j]-1];		//ER(i-1) - 48 bitow
   ER[j].b^=keys[i][j].b;	//ER(i-1) XOR K(i) = B1..B8
  }

  for (j=0;j<8;j++)		      //B(j)
  {
   int wiersz=0,kolumna=0,_4bity=0;
   if (ER[j*6].b) wiersz+=2;          //b1
   if (ER[j*6+5].b) wiersz+=1;        //b6
   if (ER[j*6+1].b) kolumna+=8;       //b2
   if (ER[j*6+2].b) kolumna+=4;       //b3
   if (ER[j*6+3].b) kolumna+=2;       //b4
   if (ER[j*6+4].b) kolumna+=1;       //b5
   _4bity=Si[j][wiersz][kolumna];
   bit temp;
   int shift=0;
   for (int x=3,y=0,zx=1;x>-1;x--,y++,zx=1)  //przesuwanie od lewej do prawej
   {					     //wiec od 4 bitu do zerowego
    for (int k=0;k<x;k++)		     //liczymy potege bitu
     zx*=2;
    shift=_4bity&zx;		     	     //w znaku pozostawiamy jeden bit
    temp.b=shift>>x;			     //po przesunieciu zapis bitu
    SB[j*4+y]=temp;		     	     //teraz bit do tablicy
   }
  }
  for (int k=0;k<32;k++)
  {
   tempY[k]=SB[P[k]-1];			     //P(S1(B1)..S8(B8))
  }
  for (k=0;k<32;k++)
  {
   SB[k]=tempY[k];
   R[k].b=tempL[k].b^SB[k].b;		     //R(i)=L(i-1) XOR f(R(i-1),K(i))
  }
  if (krypt==0) i++;
  if (krypt==1) i--;
  if (i==-1) end--;
  if (i==16) end--;
 }
 while (end);

 for (i=0;i<32;i++)
 {
  blok[i]=R[i];			//R16
  blok[i+32]=L[i];		//L16
 }
 for (i=0;i<64;i++)
 {
  tempX[i]=blok[IP_1[i]-1];	//druga permutacja ciagu 8 bajtow (IP-1)
 }
 for (i=0;i<64;i++)
 {
  blok[i]=tempX[i];
 }
}

void main()
{
 unsigned char tbl[8]={'C','o','o','k','i','e','C','K'};
 unsigned char k[8]={'k','l','u','c','z','D','E','S'};
 clrscr();
 na_bity(k,k64,8);
 k1_k16();			//kluczymy
 printf("\ntxt org:");
 for (int i=0;i<8;i++)
  printf("%c",tbl[i]);
 for (i=0;i<64;i++)
  bity[i].b=0;                   //przydalo by sie wyzerowac tablice bitow :)
 na_bity(tbl,bity,8);
 des(bity,0);                   //szyfrujemy
 na_chary(bity,tbl,8);
 printf("\ntxt des:");
 for (i=0;i<8;i++)
  printf("%c",tbl[i]);
 des(bity,1);                   //deszyfrujemy
 na_chary(bity,tbl,8);
 printf("\ntxt roz:");
 for (i=0;i<8;i++)
  printf("%c",tbl[i]);
 getch();
}
//Koniec...tu ciac i kompilowac pod BC (ja 3.1)
(pamietajcie o bibliotekach... nie dolaczalem, bo oszczedzam miejsce)


-4- Inne
Materialy - "Kryptografia i ochrona danych" Dorothy E. Robling Denning
            (i znajomosc C++)
  W W W   - http://www.cookiecrk.org
  e-mail  - zetx@go2.pl


P.S.
algorytm nie jest doskonaly... ;), wiec czekam na wszelkie sugestie... a moze
ktos chce inne? np. RSA - to juz fajniejsze bo z kluczem jawnym, ale jest
maly problem... (jak zapewne wiadomo...) DUZE liczby pierwsze - hmmm...


greetZ: A.A. (ktoz to moze byc ;)) & members of CookieCrK :)
