-[ 0x0D ]-------------------------------------------------------------------- -[ DES ]--------------------------------------------------------------------- -[ by Bran & Muad ]---------------------------------------------------SET-20- Hace algun tiempo una personita me pidio por irc que le contara como iba el algoritmo DES, pero como se podia alargar mucho me propuso que se lo contara por mail. Total, que ya que voy a escribirlo me he decidido a mandarlo aqui, hasta puede que alguien lo lea y todo :-) Un poco de historia... El algoritmo DES con 64 bits en el bloque de datos y 56 bits de clave ha sido uno de los mas famosos y mas utilizados. Se basa en la estructura feistel, inventada por Horst Feistel de IBM a principios de los 70. Esta estructura implica multiples pasadas con funciones no lineales sobre la mitad de los datos, haciendo a la salida un XOR con la otra mitad. La gran ventaja de este sitema es su facilidad para invertir el proceso y poder desencriptar. En estos momentos este algoritmo no se considera inabordable, de hecho es posible obtener la clave por fuerza bruta, en enero de este año (1999) se consiguio la clave en menos de 23 horas usando computacion distribuida con hardware especializado. Aun asi, es interesante conocer su funcionamiento puesto que los nuevos DES que van saliendo se basan en el mismo sistema. A grandes rasgos, el algoritmo se basa en ir procesando cadenas de 64 bits mediante tablas de permutaciones y XORs. Las permutaciones se encargan de cambiar las posiciones de los bits, y los XORs alteran los datos mediante los bits de la clave. Al grano... Primero se les hace una permutacion tanto a los 64 bits de datos como a la clave. Despues se procesa mediante 16 iteraciones sobre los datos, que vendran modificadas por una rotacion a izquierda y una permutacion de los bits de la clave en cada iteracion. Con eso conseguimos que los cambios provocados por la clave sean distintos en cada iteracion, cupi?? esquemita... 64 bits datos 56 bits clave | | v v Permutacion inicial Permuted choice 1 | | v K1 v Iteracion 1 <----------- Permuted choice 2 <--------- Rotacion a izquierda v K2 v Iteracion 2 <----------- Permuted choice 2 <--------- Rotacion a izquierda v v ................................................................ v K15 v Iteracion 15 <---------- Permuted choice 2 <--------- Rotacion a izquierda v K16 v Iteracion 16 <---------- Permuted choice 2 <--------- Rotacion a izquierda | v swap de 32 bit | v Permutacion inicial invertida | v 64 bits encriptados Lo del swap es simplemente intercambiar los 32 bits de mayor peso de la cadena (usease, los de mas a la izquierda) con los de menor peso (derecha). Hasta ahora facil, no?? :-) Funcionamiento de las permutaciones: Las permutaciones cambian la posicion de los bits segun unas tablas, y algunas ademas cambian el tamaño de la salida. Las permutaciones que expanden la salida logicamente tendran que duplicar algunos bits de la entrada, mientras que las que contraen, no utilizaran todos los bits de la cadena de entrada. ejemplo de permutacion con expansion con letras... -entrada (5 letras): abcde -tabla Posicion en la salida 1 2 3 4 5 6 Posicion en la entrada 2 4 1 3 5 2 -salida (6 letras): bdaceb La tabla se lee cogiendo las parejas de numeros en vertical: en la posicion 1 de la salida va la pos 2 de la entrada en la posicion 2 de la salida va la pos 4 de la entrada en la posicion 3 de la salida va la pos 1 de la entrada en la posicion 4 de la salida va la pos 3 de la entrada en la posicion 5 de la salida va la pos 5 de la entrada en la posicion 6 de la salida va la pos 2 de la entrada Todas las tablas se aplican de esta forma, excepto la tabla S, que es "algo" mas complicadilla.... ;-) Funcionamiento de la generacion de claves: Despues de la primera permutacion (choice 1) la clave se parte en dos cadenas con los 28 bits de mayor peso por un lado y los de menor peso por otro. A cada una de estas dos cadenas son a las que se les hacen las rotaciones a izquierda. El numero de bits que hemos de rotar tambien depende de una tabla, que nos dara ese numero dependiendo de la iteracion en la que nos encontremos. Despues se vuelven a juntar las dos cadenas de 28 bits y con ellas hacemos la permutacion con concentracion (choice 2), con lo que generamos los valores de las K (48 bits). /* en cuestiones de implementacion, como las 16 versiones de la clave se van a usar por cada 64 bits de datos, lo normal es generarlas antes y guardarlas en algun rincon. A los resultados de los shifts mas las permutaciones les llamaremos K1, K2,...,K16 */ Ahora toca otra vez algoritmo... Antes hemos visto el general, pero lo realmente gordo pasa dentro de cada iteracion, no se si sere capaz de dibujar un esquema... :-) El caso es que dentro de las iteraciones se aplican unas cuantas permutaciones y XORs. 32b izquierda i 32b derecha i Ki | -----------'| | | / v | | / Permutacion/expansion (E) | | / | 48 bits | | / v 48 bits | | / XOR <---------------------' | / | 48 bits | / v | / Sustitucion (S) | / | 32 bits | / v | / Permutacion (P) | / | 32 bits | / v --/----------------------> XOR / | 32 bits v v 32b izquierda i+1 32b derecha i+1 Funcionamiento de la sustitucion (tabla S): A ver... tenemos 48 bits en la entrada. Esos 48 bits se agrupan en grupos de 6 bits. A cada uno de esos grupos le aplicamos una tabla 4x16 de la siguiente forma (con los bits numerados 1-2-3-4-5-6): Con el numero formado por los bits 1-6 en binario seleccionamos la fila de la tabla. ej: 123456 (numeros de los bits) 101011 (6 bits) | | \ / 11 (bits 1,6) 11(binario) equivale a 3(decimal), asi que cogemos la fila 3. Con en numero formado por los bits 2-3-4-5 en binario seleccionamos la columna en la tabla. Lo mismo de arriba, pero ahora obtendremos un numero entre 0 y 15. ej: 123456 (numeros de los bits) 101011 (6 bits) |||| 0101 (bits 2,3,4,5) 0101(binario) equivale a 5(decimal), asi que cogemos la columna 5. Cada posicion de la tabla tiene un numero entre 0 y 15, con lo que se puede representar en binario como un numero de 4 bits. Con esto tenemos que para cada grupo de 6 bits obtenemos 4 bits, asi que concatenando los grupos de 4 bits al final tenemos un resultado de 32 bits. Despues de hacer el bucle de 16 iteraciones sobre los datos, hacemos un swap para intercambiar los 16 bits de la parte alta de los datos con los de la parte baja. Y por ultimo deshacer la permutacion inicial. Con esto tenemos a la salida un churro macabro de 64 bits. Bien, pues ya hemos llegado a la mitad, ya tenemos los datos encriptados y podemos enviarselos a quien corresponda. Por suerte este tipo de algoritmos se invierten sin necesidad de complicarse mucho la vida (siempre que tengas la clave, claro ;-) Para desencriptar seguimos el mismo metodo: Cogemos el churro macabro en grupos de 64 bits y los vamos procesando con el algoritmo, exactamente igual que en el proceso de encriptacion. La diferencia esta en que esta vez aplicaremos las 16 K en sentido inverso, o sea, la primera K en aplicarse sera la K16 (obtenida tras 16 rotaciones de la clave) y la ultima K que aplicaremos sera la K1 (obtenida con una sola rotacion de la clave principal). 64 bits datos encriptados 56 bits clave | | v v Permutacion inicial Permuted choice 1 | | v K16 K1 v Iteracion 1 <------ . <------ Permuted choice 2 <---- Rotacion a izquierda v K15 . K2 v Iteracion 2 <------ . <------ Permuted choice 2 <---- Rotacion a izquierda v . v ................................................................ v K2 . K15 v Iteracion 15 <----- . <------ Permuted choice 2 <---- Rotacion a izquierda v K1 . K16 v Iteracion 16 <----- . <------ Permuted choice 2 <---- Rotacion a izquierda | v swap de 32 bit | v Permutacion inicial invertida | v 64 bits desencriptados ... y si todo ha ido bien, ya tenemos otra vez los datos originales. (aplausos... ;-) Alguna pregunta?? no?? Bueno, por si acaso aqui esta mi email y el de Bran... muad@mixmail.com bbrraann@mixmail.com Bibliografia: Lawrie Brown, A Current Perspective on Encryption Algorithms http://www.adfa.edu.au/~lpb/papers/unz99.html W. Stallings, "Cryptography and Network Security - Principles and Practice" Prentice-Hall <++> des/des56.c /**********************************************************************/ /* des56.c */ /**********************************************************************/ /* Implementacio de l'algorisme d'encriptacio DES amb clau de 56 bits */ /* */ /* Autors: Bran, Muad */ /* */ /* Escriu per el resultat d'encriptar/desencriptar */ /* Us: des56 */ /* */ /* Comentaris: */ /* L'algorisme processa blocs de 8 bytes aixi que quan no pot */ /* obtindre'ls tots plenem els bytes buits amb 0s. */ /**********************************************************************/ /* includes ***********************************************************/ #include #include #include /* prototips **********************************************************/ void aplicaT(char*T,int nbits,unsigned char*entrada,unsigned char*eixida); // aplica una taula inline void aplicaS(int ntaula,unsigned int nfila,unsigned int ncol, unsigned char res[4]); // aplica la taula S (és especial ;-( ) inline void desplaca1(unsigned char clau[4], int ndesp); inline void desplaca2(unsigned char clau[4], int ndesp); // left shift de les dues parts de la clau inline void nova_clau(unsigned char clau[8],unsigned char vclaus[16][7]); // genera el vector de claus void printbits(unsigned char* cadena,int nchars); // rutina de debugging inline void comput(unsigned char esquerra[4],unsigned char dreta[4], unsigned char clau[7]); // rutina d'implementació de l'algorisme DES /* taules **************************************************************/ char IP[64]={ 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}; char IP_1[64]={ 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}; char E[48]={ 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}; char P[32]={ 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}; char S1[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}}; char S2[4][16]={ {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}}; char S3[4][16]={ {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}}; char S4[4][16]={ {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}}; char S5[4][16]={ {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}}; char S6[4][16]={ {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}}; char S7[4][16]={ {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,14,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}}; char S8[4][16]={ {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}}; char OP1[56]={ 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}; char OP2[48]={ 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}; char despl[16]={1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1}; /* funcions *******************************************************/ /******************************************************************/ /* aplicaT - Aplica una taula de permutacions */ /******************************************************************/ void aplicaT(char*T,int nbits,unsigned char*entrada,unsigned char*eixida) { unsigned char byteaux; int cont; memset(eixida,0,(nbits/8)+((nbits%8)>1)*sizeof(char)); for (cont=0;cont=8) { res[0]=1; valor-=8; } if (valor>=4) { res[1]=1; valor-=4; } if (valor>=2) { res[2]=1; valor-=2; } if (valor>=1) res[3]=1; } /*****************************************************************/ /* desplaca1 - Left Shift (Part esquerra) */ /*****************************************************************/ inline void desplaca1(unsigned char clau[4], int ndesp) { unsigned int cont,aux,aux0; clau[3]&=240; //11110000 Posem 0 als quatre ultims bits. for (cont=0;cont<4;cont++) { aux=((unsigned int)clau[cont])<=128); } fprintf(stderr,"\n"); } /****************************************************************/ /* comput - realitza l'algorisme d'encriptació/desencriptació */ /****************************************************************/ inline void comput(unsigned char esquerra[4],unsigned char dreta[4], unsigned char clau[7]){ int cont; unsigned char bitsS[32]; unsigned char byteaux; unsigned char auxexp[6],auxsub[4],auxper[4]; aplicaT(E,48,dreta,auxexp); //////// Expansion/Ppermutation (E table) for (cont=0;cont<6;cont++) //////// XOR auxexp[cont]=auxexp[cont]^clau[cont]; for (cont=0;cont<8;cont++) //////// Substitution/choice (S-box) aplicaS(cont,(unsigned int) // S s'aplica en grups de 6 bits (unsigned char)((auxexp[(6*cont+0)/8]&(1<<(7-(6*cont+0)%8)))>0)*2^ (unsigned char)((auxexp[(6*cont+5)/8]&(1<<(7-(6*cont+5)%8)))>0), (unsigned int) // (bit 0)*2 + (bit 5) (unsigned char)((auxexp[(6*cont+1)/8]&(1<<(7-(6*cont+1)%8)))>0)*8^ (unsigned char)((auxexp[(6*cont+2)/8]&(1<<(7-(6*cont+2)%8)))>0)*4^ (unsigned char)((auxexp[(6*cont+3)/8]&(1<<(7-(6*cont+3)%8)))>0)*2^ (unsigned char)((auxexp[(6*cont+4)/8]&(1<<(7-(6*cont+4)%8)))>0), // (bit 1)*8 + (bit 2)*4 + (bit 3)*2 + (bit 4) &bitsS[4*cont]); memset(auxsub,0,4*sizeof(char)); for (cont=0;cont<32;cont++) { if (bitsS[cont]) { byteaux=1<<(7-(cont%8)); auxsub[cont/8]|=byteaux; } } aplicaT(P,32,auxsub,auxper); /////// Permutation (P table) for (cont=0;cont<4;cont++) { auxper[cont]^=esquerra[cont];/////// XOR esquerra[cont]=dreta[cont]; /////// XChange dreta[cont]=auxper[cont]; } } /****************************************************************/ /* PROGRAMA PRINCIPAL */ /****************************************************************/ main(int argc,char* argv[]) { char cadena[256]; char encriptar; unsigned char bits[48]; int cont,len; unsigned char aux[4],clau[8]; unsigned char caracters[8],caracters_nous[8],vclaus[16][7]; if (argc!=3||(!strcmp(argv[1],"e")&&!strcmp(argv[1],"d"))) { fprintf(stderr," Us: %s \n",argv[0]);; fprintf(stderr," e: encriptar\n"); fprintf(stderr," d: desencriptar\n"); fprintf(stderr," clau: clau (màx. 7 caràcters)\n"); exit(-1); } strncpy((char*)clau,argv[2],7); nova_clau(clau,vclaus); memset(caracters,0,8*sizeof(char)); len=fread(caracters,1*sizeof(char),8,stdin); while (len!=0) { aplicaT(IP,64,caracters,caracters_nous); //// Initial Permutation (IP) for(cont=0;cont<16;cont++) { if (argv[1][0]=='e') comput(&caracters_nous[0],&caracters_nous[4],vclaus[cont]); else comput(&caracters_nous[0],&caracters_nous[4],vclaus[15-cont]); } memcpy(aux,&caracters_nous[0],4*sizeof(char));//// XChange memcpy(&caracters_nous[0],&caracters_nous[4],4*sizeof(char)); memcpy(&caracters_nous[4],aux,4*sizeof(char)); aplicaT(IP_1,64,caracters_nous,caracters);//// Inverse Initial P. (IP¯¹) fwrite(caracters,1*sizeof(char),8,stdout); memset(caracters,0,8*sizeof(char)); len=fread(caracters,1*sizeof(char),8,stdin); } fflush(stdout); close(0); close(1); exit(0); } <-->