miércoles, 6 de junio de 2007

DES y Triple-DES

El algoritmo DES está basado en el algoritmo Lucifer, diseñado por IBM a principios de los setenta. Después de algunas modificaciones de la NSA (National Security Agency), fué publicado en 1977 por el NBS (National Bureau of Standards), una sección del departamento de defensa de los EEUU.

DES utiliza claves de 56 bits y un cifrado de bloques de 64 bits.

Esquema general:

El algoritmo DES cifra la información por bloques, es decir, el texto en claro debe ser dividido en bloques de 64 bits que serán cifrados uno tras otro.

DES utiliza claves de 56 bits, aunque estas suelen distribuirse en forma de números de 64 bits. De estos 64 bits, uno de cada ocho, es utilizado como bit de paridad (64-8=56).

A grandes rasgos el algoritmo DES sigue el siguiente esquema:


Bloque de entrada 64 bits
        |
      -----
      | A |
      -----
        |
------------------
| 16 iteraciones |
------------------
        |
      -----
      | B |
      -----
        |
Bloque de salida 64 bits




La tabla de permutación A:
Después de recibir un bloque de entrada de 64 bits, el primer paso consiste en aplicar al bloque de entrada una permutación A mediante la tabla siguiente:

--------------------------
| Tabla de permutación A |
--------------------------
| 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 |
--------------------------


El primer bit de la entrada será colocado en la posición 58, el segundo bit en la posición 50 ...


La tabla de permutación B:
De la misma manera, después de las 16 iteraciones se realiza otra permutación mediante la tabla B:


--------------------------
| Tabla de permutación B |
--------------------------
| 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 |
--------------------------



El primer bit de la entrada será colocado en la posición 40, el segundo bit en la posición 8 ...

Las 16 iteraciones:
Después de la permutación A y antes de la B, el algoritmo DES realiza 16 iteraciones. Cada iteración realiza lo siguiente:
  1. Los 64 bits de entrada se dividen en dos partes de 32 bits.
  2. La mitad de la derecha (R) se introduce en una función (f) que se describirá más adelante.

  3. Se realiza un XOR entre la salida de la función y la parte izquierda (L).
  4. El resultado (32 bits) pasará a ser la parte derecha de la siguiente iteración, mientras que la parte derecha actual pasará a ser la parte izuierda.

    Li+1 = Ri

    Ri+1 = Li XOR f(Ri,K)



En la última iteración (i=16) no se realizará el paso 4.

La función F:
Ahora pasamos a describir la función f, veamos un esquema general:


D i-1
                               |
                               | 32 bits
                             -----
                             | C |
                             -----
                               | 48 bits
                               |
                      XOR --- K (48 bits)
                               |
                               |
--------------------------------------------------------------
||||||  ||||||  ||||||  ||||||  ||||||  ||||||  ||||||  ||||||
------  ------  ------  ------  ------  ------  ------  ------
| S1 |  | S2 |  | S3 |  | S4 |  | S5 |  | S6 |  | S7 |  | S8 |
------  ------  ------  ------  ------  ------  ------  ------
||||    ||||    ||||    ||||    ||||    ||||    ||||    ||||
------------------------------------------------------------
                               | 32 bits
                               |
                             -----
                             | P |
                             -----
                               | 32 bits
                               |


Los 32 bits de la parte derecha entran en la función f. El primer paso consiste en transformar la entrada de 32 bits a 48 bits mediante la tabla C.



--------------------------
| Tabla transformación C |
--------------------------
| 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 |
--------------------------


A continuación se realiza un XOR con una subclave de 48 bits. Dado que la clave inicial era de 56 bits (representada como 64 bits) es necesario generar, a partir de esta, subclaves de 48 bits. Más adelante se describe detalladamente el proceso de generación de subclaves.

A continuación los 48 bits se dividen en bloques de 6 bits, cada uno de de los cuales es utilizado como entrada de lo que se conoce como una caja S. Observe el esquema anterior.

Los 6 bits que forman cada bloque b1, b2, b3, b4, b5 y b6, son utilizados para leer de cada caja S. b1 y b6 indican la fila mientras que b2, b3, b4, y b5 indican la columna. Es decir, si utilizamos como entrada 000011, b1b6 -> 01 indican la primera fila y b2b3b4b5 -> 00001 indican la primera columna.

A continuación se muestran las ocho cajas S existentes:



S-1                      
---------------------------------------------------
| 14 04 13 01 02 15 11 08 03 10 06 12 05 09 00 07 |
| 00 15 07 04 14 02 13 01 10 06 12 11 09 05 03 08 |
| 04 01 14 08 13 06 02 11 15 12 09 07 03 10 05 00 |
| 15 12 08 02 04 09 01 07 05 11 03 14 10 00 06 13 |
---------------------------------------------------

S-2
---------------------------------------------------
| 15 01 08 14 06 11 03 04 09 07 02 13 12 00 05 10 |
| 03 13 04 07 15 02 08 14 12 00 01 10 06 09 11 05 |
| 00 14 07 11 10 04 13 01 04 08 12 06 09 03 02 15 |
| 13 08 10 01 03 15 04 02 11 06 07 12 00 05 14 09 |
---------------------------------------------------

S-3
---------------------------------------------------
| 10 00 09 14 06 03 15 05 01 13 12 07 11 04 02 08 |
| 13 07 00 09 03 04 06 10 02 08 05 14 12 11 15 01 |
| 13 06 04 09 08 15 03 00 11 01 02 12 05 10 14 07 |
| 01 10 13 00 06 09 08 07 04 15 14 03 11 05 02 12 |
---------------------------------------------------

S-4
---------------------------------------------------
| 07 13 14 03 00 06 09 10 01 02 08 05 11 12 04 15 |
| 13 08 11 05 06 15 00 03 04 07 02 12 01 10 14 09 |
| 10 06 09 00 12 11 07 13 15 01 03 14 05 02 08 04 |
| 03 15 00 06 10 01 13 08 09 04 05 11 12 07 02 14 |
---------------------------------------------------

S-5
---------------------------------------------------
| 02 12 04 01 07 10 11 06 08 05 03 15 13 00 14 09 |
| 14 11 02 12 04 07 13 01 05 00 15 10 03 09 08 06 |
| 04 02 01 11 10 13 07 08 15 09 12 05 06 03 00 14 |
| 11 08 12 07 01 14 02 13 06 15 00 09 10 04 05 03 |
---------------------------------------------------

S-6
---------------------------------------------------
| 12 01 10 15 09 02 06 08 00 13 03 04 14 07 05 11 |
| 10 15 04 02 07 12 09 05 06 01 13 14 00 11 03 08 |
| 09 14 15 05 02 08 12 03 07 00 04 10 01 13 11 06 |
| 04 03 02 12 09 05 15 10 11 14 01 07 06 00 08 13 |
---------------------------------------------------

S-7
---------------------------------------------------
| 04 11 02 14 15 00 08 13 03 12 09 07 05 10 06 01 |
| 13 00 11 07 04 09 01 10 14 03 05 12 02 15 08 06 |
| 01 04 11 13 12 03 07 14 10 15 06 08 00 05 09 02 |
| 06 11 13 08 01 04 10 07 09 05 00 15 14 02 03 12 |
---------------------------------------------------

S-8
---------------------------------------------------
| 13 02 08 04 06 15 11 01 10 09 03 14 05 00 12 07 |
| 01 15 13 08 10 03 07 04 12 05 06 11 00 14 09 02 |
| 07 11 04 01 09 12 14 02 00 06 10 13 15 03 05 08 |
| 02 01 14 07 04 10 08 13 15 12 09 00 03 05 06 11 |
---------------------------------------------------




Generación de subclaves K:
Este esquema se realiza para cada una de las iteraciones:


K (56 bits)
                    |
                  -----
                  | D |
                  -----
                    |
          ---------------------
          |                   |
------------------    ------------------
| Desplazamiento |    | Desplazamiento |
------------------    ------------------
          |                   |
          ---------------------
                    |
                  -----
                  | E |
                  -----
                    |
               ki (48 bits)



El primer paso consiste en una permutación mediante la tabla D:

------------------------
| Tabla  permutación D |
------------------------
| 57 49 41 33 25 17 09 |
| 01 58 50 42 34 26 18 |
| 10 02 59 51 43 35 27 |
| 19 11 03 60 52 44 36 |
| 63 55 47 39 31 23 15 |
| 07 62 54 46 38 30 22 |
| 14 06 61 53 45 37 29 |
| 21 13 05 28 20 12 04 |
------------------------


Los 56 bits se dividen en dos partes de 28 bits. Cada una de estas partes rota hacia la izquierda un número X de bits en cada iteración, conforme a la tabla siguiente:


----------------------------------------------------------------------
| Iteración       |  01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 |
| Desplazamiento  |   1  1  2  2  2  2  2  2  2  2  2  2  2  2  2  1 |
----------------------------------------------------------------------


Finalmente, mediante la tabla de compresión E los 56 bits (28+28) del resultado se comprimen formando una subclave de 48 bits (la utilizada en la función f).

--------------------------
|  Tabla de compresión E |
--------------------------
| 14  17  11  24  01  05 |
| 03  28  15  06  21  10 |
| 23  19  12  04  26  08 |
| 16  07  27  20  13  02 |
| 41  52  31  37  47  55 |
| 30  40  51  45  33  48 |
| 44  49  39  56  34  53 |
| 46  42  50  36  29  32 |
--------------------------




Descifrado en DES
Una de las partes positivas de DES es que podemos descifrar los mensajes utilizando el mismo algoritmo que utilizamos para cifrar. La única diferencia consiste en el orden en que se aplican la subclaves, dado que en el descifrado se utilizan en orden inverso. Es decir, primero se utiliza la subclave k16, después la k15 ... k1.


Debilidades del algoritmo DES
Desde la aparición del algoritmo DES han surgido algunas críticas sobr el criptosistema. La principal es la longitud de la clave, de solo 56 bits, que hacen posible los ataques de fuerza bruta.

Por otra parte, la arbitrariedad de las cajas S, podría ser causa de la existencia de una clave maestra que permitiese descifrar cualquier mensaje.

Una forma de solucionar el problema de la longitud de la clave es el uso del cifrado triple, conocido como Triple DES. La clave utilizada por Triple DES es de 128 bits (112 de clave y 16 de paridad) , es decir, dos claves de 64 bits (56 de clave y 8 de paridad) de los utilizados en DES. El motivo de utilizar este de tipo de clave es la compatibilidad con DES. Si la clave utilizada es el conjunto de dos claves DES iguales el resultado será el mismo para DES y para Triple DES.

Triple DES
Para cifrar mediante el algoritmo Triple DES seguiremos los siguientes pasos:

- Dividir la clave de 128 bits en dos partes de 64 bits: k1 y k2.
- Cifrar el texto en claro con k1. El resultado es conocido como ANTIDES.
- Cifrar ANTIDES con k2.
- Cifrar el resultado con k1.
- Si k1=k2 el resultado coincide con un cifrado mediante DES.


Otra forma de utilizar Triple DES es con una clave de 192 bits (168 bits de clave y 24 bits de paridad). En este caso se cifrará primero con k1, a continuación con k2 y finalmente con k3.
Para ser compatible con DES es necesario que k1=k2=k3.


Implementación en C

/* ---- H source file: des.h ---- */

/**
* \file des.h
*/
#ifndef _DES_H
#define _DES_H

#ifdef __cplusplus
extern "C" {
#endif

/**
* \brief          DES context structure
*/
typedef struct
{
unsigned long esk[32];     /*!< DES encryption subkeys */
unsigned long dsk[32];     /*!< DES decryption subkeys */
}
des_context;

/**
* \brief          Triple-DES context structure
*/
typedef struct
{
unsigned long esk[96];     /*!< Triple-DES encryption subkeys */
unsigned long dsk[96];     /*!< Triple-DES decryption subkeys */
}
des3_context;

/**
* \brief          DES key schedule (56-bit)
*
* \param ctx      DES context to be initialized
* \param key      8-byte secret key
*/
void des_set_key( des_context *ctx, unsigned char key[8] );

/**
* \brief          DES block encryption (ECB mode)
*
* \param ctx      DES context
* \param input    plaintext  block
* \param output   ciphertext block
*/
void des_encrypt( des_context *ctx,
unsigned char input[8],
unsigned char output[8] );

/**
* \brief          DES block decryption (ECB mode)
*
* \param ctx      DES context
* \param input    ciphertext block
* \param output   plaintext  block
*/
void des_decrypt( des_context *ctx,
unsigned char input[8],
unsigned char output[8] );

/**
* \brief          DES-CBC buffer encryption
*
* \param ctx      DES context
* \param iv       initialization vector (modified after use)
* \param input    buffer holding the plaintext
* \param output   buffer holding the ciphertext
* \param len      length of the data to be encrypted
*/
void des_cbc_encrypt( des_context *ctx,
unsigned char iv[8],
unsigned char *input,
unsigned char *output,
int len );

/**
* \brief          DES-CBC buffer decryption
*
* \param ctx      DES context
* \param iv       initialization vector (modified after use)
* \param input    buffer holding the ciphertext
* \param output   buffer holding the plaintext
* \param len      length of the data to be decrypted
*/
void des_cbc_decrypt( des_context *ctx,
unsigned char iv[8],
unsigned char *input,
unsigned char *output,
int len );

/**
* \brief          Triple-DES key schedule (112-bit)
*
* \param ctx      3DES context to be initialized
* \param key      16-byte secret key
*/
void des3_set_2keys( des3_context *ctx, unsigned char key[16] );

/**
* \brief          Triple-DES key schedule (168-bit)
*
* \param ctx      3DES context to be initialized
* \param key      24-byte secret key
*/
void des3_set_3keys( des3_context *ctx, unsigned char key[24] );

/**
* \brief          Triple-DES block encryption (ECB mode)
*
* \param ctx      3DES context
* \param input    plaintext  block
* \param output   ciphertext block
*/
void des3_encrypt( des3_context *ctx,
unsigned char input[8],
unsigned char output[8] );

/**
* \brief          Triple-DES block decryption (ECB mode)
*
* \param ctx      3DES context
* \param input    ciphertext block
* \param output   plaintext  block
*/
void des3_decrypt( des3_context *ctx,
unsigned char input[8],
unsigned char output[8] );

/**
* \brief          3DES-CBC buffer encryption
*
* \param ctx      3DES context
* \param iv       initialization vector (modified after use)
* \param input    buffer holding the plaintext
* \param output   buffer holding the ciphertext
* \param len      length of the data to be encrypted
*/
void des3_cbc_encrypt( des3_context *ctx,
unsigned char iv[8],
unsigned char *input,
unsigned char *output,
int len );

/**
* \brief          3DES-CBC buffer decryption
*
* \param ctx      3DES context
* \param iv       initialization vector (modified after use)
* \param input    buffer holding the ciphertext
* \param output   buffer holding the plaintext
* \param len      length of the data to be decrypted
*/
void des3_cbc_decrypt( des3_context *ctx,
unsigned char iv[8],
unsigned char *input,
unsigned char *output,
int len );

/*
* \brief          Checkup routine
*
* \return         0 if successful, or 1 if the test failed
*/
int des_self_test( void );

#ifdef __cplusplus
}
#endif

#endif /* des.h */








/* ---- C source file: des.c ---- */

/*
*  FIPS-46-3 compliant Triple-DES implementation
*
*  Copyright (C) 2003-2006  Christophe Devine
*
*  This library is free software; you can redistribute it and/or
*  modify it under the terms of the GNU Lesser General Public
*  License, version 2.1 as published by the Free Software Foundation.
*
*  This library is distributed in the hope that it will be useful,
*  but WITHOUT ANY WARRANTY; without even the implied warranty of
*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
*  Lesser General Public License for more details.
*
*  You should have received a copy of the GNU Lesser General Public
*  License along with this library; if not, write to the Free Software
*  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
*  MA  02110-1301  USA
*/
/*
*  DES, on which TDES is based, was originally designed by IBM in
*  1974 and adopted as a standard by NIST (formerly NBS).
*
*  http://csrc.nist.gov/publications/fips/fips46-3/fips46-3.pdf
*/


#ifndef _CRT_SECURE_NO_DEPRECATE
#define _CRT_SECURE_NO_DEPRECATE 1
#endif

#include 

#include "des.h"

/*
* 32-bit integer manipulation macros (big endian)
*/
#ifndef GET_UINT32_BE
#define GET_UINT32_BE(n,b,i)                            \
{                                                       \
(n) = ( (unsigned long) (b)[(i)    ] << 24 )        \
| ( (unsigned long) (b)[(i) + 1] << 16 )        \
| ( (unsigned long) (b)[(i) + 2] <<  8 )        \
| ( (unsigned long) (b)[(i) + 3]       );       \
}
#endif
#ifndef PUT_UINT32_BE
#define PUT_UINT32_BE(n,b,i)                            \
{                                                       \
(b)[(i)    ] = (unsigned char) ( (n) >> 24 );       \
(b)[(i) + 1] = (unsigned char) ( (n) >> 16 );       \
(b)[(i) + 2] = (unsigned char) ( (n) >>  8 );       \
(b)[(i) + 3] = (unsigned char) ( (n)       );       \
}
#endif

/*
* Expanded DES S-boxes
*/
static const unsigned long SB1[64] =
{
0x01010400, 0x00000000, 0x00010000, 0x01010404,
0x01010004, 0x00010404, 0x00000004, 0x00010000,
0x00000400, 0x01010400, 0x01010404, 0x00000400,
0x01000404, 0x01010004, 0x01000000, 0x00000004,
0x00000404, 0x01000400, 0x01000400, 0x00010400,
0x00010400, 0x01010000, 0x01010000, 0x01000404,
0x00010004, 0x01000004, 0x01000004, 0x00010004,
0x00000000, 0x00000404, 0x00010404, 0x01000000,
0x00010000, 0x01010404, 0x00000004, 0x01010000,
0x01010400, 0x01000000, 0x01000000, 0x00000400,
0x01010004, 0x00010000, 0x00010400, 0x01000004,
0x00000400, 0x00000004, 0x01000404, 0x00010404,
0x01010404, 0x00010004, 0x01010000, 0x01000404,
0x01000004, 0x00000404, 0x00010404, 0x01010400,
0x00000404, 0x01000400, 0x01000400, 0x00000000,
0x00010004, 0x00010400, 0x00000000, 0x01010004
};

static const unsigned long SB2[64] =
{
0x80108020, 0x80008000, 0x00008000, 0x00108020,
0x00100000, 0x00000020, 0x80100020, 0x80008020,
0x80000020, 0x80108020, 0x80108000, 0x80000000,
0x80008000, 0x00100000, 0x00000020, 0x80100020,
0x00108000, 0x00100020, 0x80008020, 0x00000000,
0x80000000, 0x00008000, 0x00108020, 0x80100000,
0x00100020, 0x80000020, 0x00000000, 0x00108000,
0x00008020, 0x80108000, 0x80100000, 0x00008020,
0x00000000, 0x00108020, 0x80100020, 0x00100000,
0x80008020, 0x80100000, 0x80108000, 0x00008000,
0x80100000, 0x80008000, 0x00000020, 0x80108020,
0x00108020, 0x00000020, 0x00008000, 0x80000000,
0x00008020, 0x80108000, 0x00100000, 0x80000020,
0x00100020, 0x80008020, 0x80000020, 0x00100020,
0x00108000, 0x00000000, 0x80008000, 0x00008020,
0x80000000, 0x80100020, 0x80108020, 0x00108000
};

static const unsigned long SB3[64] =
{
0x00000208, 0x08020200, 0x00000000, 0x08020008,
0x08000200, 0x00000000, 0x00020208, 0x08000200,
0x00020008, 0x08000008, 0x08000008, 0x00020000,
0x08020208, 0x00020008, 0x08020000, 0x00000208,
0x08000000, 0x00000008, 0x08020200, 0x00000200,
0x00020200, 0x08020000, 0x08020008, 0x00020208,
0x08000208, 0x00020200, 0x00020000, 0x08000208,
0x00000008, 0x08020208, 0x00000200, 0x08000000,
0x08020200, 0x08000000, 0x00020008, 0x00000208,
0x00020000, 0x08020200, 0x08000200, 0x00000000,
0x00000200, 0x00020008, 0x08020208, 0x08000200,
0x08000008, 0x00000200, 0x00000000, 0x08020008,
0x08000208, 0x00020000, 0x08000000, 0x08020208,
0x00000008, 0x00020208, 0x00020200, 0x08000008,
0x08020000, 0x08000208, 0x00000208, 0x08020000,
0x00020208, 0x00000008, 0x08020008, 0x00020200
};

static const unsigned long SB4[64] =
{
0x00802001, 0x00002081, 0x00002081, 0x00000080,
0x00802080, 0x00800081, 0x00800001, 0x00002001,
0x00000000, 0x00802000, 0x00802000, 0x00802081,
0x00000081, 0x00000000, 0x00800080, 0x00800001,
0x00000001, 0x00002000, 0x00800000, 0x00802001,
0x00000080, 0x00800000, 0x00002001, 0x00002080,
0x00800081, 0x00000001, 0x00002080, 0x00800080,
0x00002000, 0x00802080, 0x00802081, 0x00000081,
0x00800080, 0x00800001, 0x00802000, 0x00802081,
0x00000081, 0x00000000, 0x00000000, 0x00802000,
0x00002080, 0x00800080, 0x00800081, 0x00000001,
0x00802001, 0x00002081, 0x00002081, 0x00000080,
0x00802081, 0x00000081, 0x00000001, 0x00002000,
0x00800001, 0x00002001, 0x00802080, 0x00800081,
0x00002001, 0x00002080, 0x00800000, 0x00802001,
0x00000080, 0x00800000, 0x00002000, 0x00802080
};

static const unsigned long SB5[64] =
{
0x00000100, 0x02080100, 0x02080000, 0x42000100,
0x00080000, 0x00000100, 0x40000000, 0x02080000,
0x40080100, 0x00080000, 0x02000100, 0x40080100,
0x42000100, 0x42080000, 0x00080100, 0x40000000,
0x02000000, 0x40080000, 0x40080000, 0x00000000,
0x40000100, 0x42080100, 0x42080100, 0x02000100,
0x42080000, 0x40000100, 0x00000000, 0x42000000,
0x02080100, 0x02000000, 0x42000000, 0x00080100,
0x00080000, 0x42000100, 0x00000100, 0x02000000,
0x40000000, 0x02080000, 0x42000100, 0x40080100,
0x02000100, 0x40000000, 0x42080000, 0x02080100,
0x40080100, 0x00000100, 0x02000000, 0x42080000,
0x42080100, 0x00080100, 0x42000000, 0x42080100,
0x02080000, 0x00000000, 0x40080000, 0x42000000,
0x00080100, 0x02000100, 0x40000100, 0x00080000,
0x00000000, 0x40080000, 0x02080100, 0x40000100
};

static const unsigned long SB6[64] =
{
0x20000010, 0x20400000, 0x00004000, 0x20404010,
0x20400000, 0x00000010, 0x20404010, 0x00400000,
0x20004000, 0x00404010, 0x00400000, 0x20000010,
0x00400010, 0x20004000, 0x20000000, 0x00004010,
0x00000000, 0x00400010, 0x20004010, 0x00004000,
0x00404000, 0x20004010, 0x00000010, 0x20400010,
0x20400010, 0x00000000, 0x00404010, 0x20404000,
0x00004010, 0x00404000, 0x20404000, 0x20000000,
0x20004000, 0x00000010, 0x20400010, 0x00404000,
0x20404010, 0x00400000, 0x00004010, 0x20000010,
0x00400000, 0x20004000, 0x20000000, 0x00004010,
0x20000010, 0x20404010, 0x00404000, 0x20400000,
0x00404010, 0x20404000, 0x00000000, 0x20400010,
0x00000010, 0x00004000, 0x20400000, 0x00404010,
0x00004000, 0x00400010, 0x20004010, 0x00000000,
0x20404000, 0x20000000, 0x00400010, 0x20004010
};

static const unsigned long SB7[64] =
{
0x00200000, 0x04200002, 0x04000802, 0x00000000,
0x00000800, 0x04000802, 0x00200802, 0x04200800,
0x04200802, 0x00200000, 0x00000000, 0x04000002,
0x00000002, 0x04000000, 0x04200002, 0x00000802,
0x04000800, 0x00200802, 0x00200002, 0x04000800,
0x04000002, 0x04200000, 0x04200800, 0x00200002,
0x04200000, 0x00000800, 0x00000802, 0x04200802,
0x00200800, 0x00000002, 0x04000000, 0x00200800,
0x04000000, 0x00200800, 0x00200000, 0x04000802,
0x04000802, 0x04200002, 0x04200002, 0x00000002,
0x00200002, 0x04000000, 0x04000800, 0x00200000,
0x04200800, 0x00000802, 0x00200802, 0x04200800,
0x00000802, 0x04000002, 0x04200802, 0x04200000,
0x00200800, 0x00000000, 0x00000002, 0x04200802,
0x00000000, 0x00200802, 0x04200000, 0x00000800,
0x04000002, 0x04000800, 0x00000800, 0x00200002
};

static const unsigned long SB8[64] =
{
0x10001040, 0x00001000, 0x00040000, 0x10041040,
0x10000000, 0x10001040, 0x00000040, 0x10000000,
0x00040040, 0x10040000, 0x10041040, 0x00041000,
0x10041000, 0x00041040, 0x00001000, 0x00000040,
0x10040000, 0x10000040, 0x10001000, 0x00001040,
0x00041000, 0x00040040, 0x10040040, 0x10041000,
0x00001040, 0x00000000, 0x00000000, 0x10040040,
0x10000040, 0x10001000, 0x00041040, 0x00040000,
0x00041040, 0x00040000, 0x10041000, 0x00001000,
0x00000040, 0x10040040, 0x00001000, 0x00041040,
0x10001000, 0x00000040, 0x10000040, 0x10040000,
0x10040040, 0x10000000, 0x00040000, 0x10001040,
0x00000000, 0x10041040, 0x00040040, 0x10000040,
0x10040000, 0x10001000, 0x10001040, 0x00000000,
0x10041040, 0x00041000, 0x00041000, 0x00001040,
0x00001040, 0x00040040, 0x10000000, 0x10041000
};

/*
* PC1: left and right halves bit-swap
*/
static const unsigned long LHs[16] =
{
0x00000000, 0x00000001, 0x00000100, 0x00000101,
0x00010000, 0x00010001, 0x00010100, 0x00010101,
0x01000000, 0x01000001, 0x01000100, 0x01000101,
0x01010000, 0x01010001, 0x01010100, 0x01010101
};

static const unsigned long RHs[16] =
{
0x00000000, 0x01000000, 0x00010000, 0x01010000,
0x00000100, 0x01000100, 0x00010100, 0x01010100,
0x00000001, 0x01000001, 0x00010001, 0x01010001,
0x00000101, 0x01000101, 0x00010101, 0x01010101,
};

/*
* Initial Permutation macro
*/
#define DES_IP(X,Y)                                             \
{                                                               \
T = ((X >>  4) ^ Y) & 0x0F0F0F0F; Y ^= T; X ^= (T <<  4);   \
T = ((X >> 16) ^ Y) & 0x0000FFFF; Y ^= T; X ^= (T << 16);   \
T = ((Y >>  2) ^ X) & 0x33333333; X ^= T; Y ^= (T <<  2);   \
T = ((Y >>  8) ^ X) & 0x00FF00FF; X ^= T; Y ^= (T <<  8);   \
Y = ((Y << 1) | (Y >> 31)) & 0xFFFFFFFF;                    \
T = (X ^ Y) & 0xAAAAAAAA; Y ^= T; X ^= T;                   \
X = ((X << 1) | (X >> 31)) & 0xFFFFFFFF;                    \
}

/*
* Final Permutation macro
*/
#define DES_FP(X,Y)                                             \
{                                                               \
X = ((X << 31) | (X >> 1)) & 0xFFFFFFFF;                    \
T = (X ^ Y) & 0xAAAAAAAA; X ^= T; Y ^= T;                   \
Y = ((Y << 31) | (Y >> 1)) & 0xFFFFFFFF;                    \
T = ((Y >>  8) ^ X) & 0x00FF00FF; X ^= T; Y ^= (T <<  8);   \
T = ((Y >>  2) ^ X) & 0x33333333; X ^= T; Y ^= (T <<  2);   \
T = ((X >> 16) ^ Y) & 0x0000FFFF; Y ^= T; X ^= (T << 16);   \
T = ((X >>  4) ^ Y) & 0x0F0F0F0F; Y ^= T; X ^= (T <<  4);   \
}

/*
* DES round macro
*/
#define DES_ROUND(X,Y)                          \
{                                               \
T = *SK++ ^ X;                              \
Y ^= SB8[ (T      ) & 0x3F ] ^              \
SB6[ (T >>  8) & 0x3F ] ^              \
SB4[ (T >> 16) & 0x3F ] ^              \
SB2[ (T >> 24) & 0x3F ];               \
\
T = *SK++ ^ ((X << 28) | (X >> 4));         \
Y ^= SB7[ (T      ) & 0x3F ] ^              \
SB5[ (T >>  8) & 0x3F ] ^              \
SB3[ (T >> 16) & 0x3F ] ^              \
SB1[ (T >> 24) & 0x3F ];               \
}

static void des_main_ks( unsigned long SK[32], unsigned char key[8] )
{
int i;
unsigned long X, Y, T;

GET_UINT32_BE( X, key, 0 );
GET_UINT32_BE( Y, key, 4 );

/*
* Permuted Choice 1
*/
T =  ((Y >>  4) ^ X) & 0x0F0F0F0F;  X ^= T; Y ^= (T <<  4);
T =  ((Y      ) ^ X) & 0x10101010;  X ^= T; Y ^= (T      );

X =   (LHs[ (X      ) & 0xF] << 3) | (LHs[ (X >>  8) & 0xF ] << 2)
| (LHs[ (X >> 16) & 0xF] << 1) | (LHs[ (X >> 24) & 0xF ]     )
| (LHs[ (X >>  5) & 0xF] << 7) | (LHs[ (X >> 13) & 0xF ] << 6)
| (LHs[ (X >> 21) & 0xF] << 5) | (LHs[ (X >> 29) & 0xF ] << 4);

Y =   (RHs[ (Y >>  1) & 0xF] << 3) | (RHs[ (Y >>  9) & 0xF ] << 2)
| (RHs[ (Y >> 17) & 0xF] << 1) | (RHs[ (Y >> 25) & 0xF ]     )
| (RHs[ (Y >>  4) & 0xF] << 7) | (RHs[ (Y >> 12) & 0xF ] << 6)
| (RHs[ (Y >> 20) & 0xF] << 5) | (RHs[ (Y >> 28) & 0xF ] << 4);

X &= 0x0FFFFFFF;
Y &= 0x0FFFFFFF;

/*
* calculate subkeys
*/
for( i = 0; i < 16; i++ )
{
if( i < 2 || i == 8 || i == 15 )
{
X = ((X <<  1) | (X >> 27)) & 0x0FFFFFFF;
Y = ((Y <<  1) | (Y >> 27)) & 0x0FFFFFFF;
}
else
{
X = ((X <<  2) | (X >> 26)) & 0x0FFFFFFF;
Y = ((Y <<  2) | (Y >> 26)) & 0x0FFFFFFF;
}

*SK++ =   ((X <<  4) & 0x24000000) | ((X << 28) & 0x10000000)
| ((X << 14) & 0x08000000) | ((X << 18) & 0x02080000)
| ((X <<  6) & 0x01000000) | ((X <<  9) & 0x00200000)
| ((X >>  1) & 0x00100000) | ((X << 10) & 0x00040000)
| ((X <<  2) & 0x00020000) | ((X >> 10) & 0x00010000)
| ((Y >> 13) & 0x00002000) | ((Y >>  4) & 0x00001000)
| ((Y <<  6) & 0x00000800) | ((Y >>  1) & 0x00000400)
| ((Y >> 14) & 0x00000200) | ((Y      ) & 0x00000100)
| ((Y >>  5) & 0x00000020) | ((Y >> 10) & 0x00000010)
| ((Y >>  3) & 0x00000008) | ((Y >> 18) & 0x00000004)
| ((Y >> 26) & 0x00000002) | ((Y >> 24) & 0x00000001);

*SK++ =   ((X << 15) & 0x20000000) | ((X << 17) & 0x10000000)
| ((X << 10) & 0x08000000) | ((X << 22) & 0x04000000)
| ((X >>  2) & 0x02000000) | ((X <<  1) & 0x01000000)
| ((X << 16) & 0x00200000) | ((X << 11) & 0x00100000)
| ((X <<  3) & 0x00080000) | ((X >>  6) & 0x00040000)
| ((X << 15) & 0x00020000) | ((X >>  4) & 0x00010000)
| ((Y >>  2) & 0x00002000) | ((Y <<  8) & 0x00001000)
| ((Y >> 14) & 0x00000808) | ((Y >>  9) & 0x00000400)
| ((Y      ) & 0x00000200) | ((Y <<  7) & 0x00000100)
| ((Y >>  7) & 0x00000020) | ((Y >>  3) & 0x00000011)
| ((Y <<  2) & 0x00000004) | ((Y >> 21) & 0x00000002);
}
}

/*
* DES key schedule (56-bit)
*/
void des_set_key( des_context *ctx, unsigned char key[8] )
{
int i;

des_main_ks( ctx->esk, key );

for( i = 0; i < 32; i += 2 )
{
ctx->dsk[i    ] = ctx->esk[30 - i];
ctx->dsk[i + 1] = ctx->esk[31 - i];
}
}

static void des_crypt( unsigned long SK[32],
unsigned char input[8],
unsigned char output[8] )
{
unsigned long X, Y, T;

GET_UINT32_BE( X, input, 0 );
GET_UINT32_BE( Y, input, 4 );

DES_IP( X, Y );

DES_ROUND( Y, X );  DES_ROUND( X, Y );
DES_ROUND( Y, X );  DES_ROUND( X, Y );
DES_ROUND( Y, X );  DES_ROUND( X, Y );
DES_ROUND( Y, X );  DES_ROUND( X, Y );
DES_ROUND( Y, X );  DES_ROUND( X, Y );
DES_ROUND( Y, X );  DES_ROUND( X, Y );
DES_ROUND( Y, X );  DES_ROUND( X, Y );
DES_ROUND( Y, X );  DES_ROUND( X, Y );

DES_FP( Y, X );

PUT_UINT32_BE( Y, output, 0 );
PUT_UINT32_BE( X, output, 4 );
}

/*
* DES block encryption (ECB mode)
*/
void des_encrypt( des_context *ctx,
unsigned char input[8],
unsigned char output[8] )
{
des_crypt( ctx->esk, input, output );
}

/*
* DES block decryption (ECB mode)
*/
void des_decrypt( des_context *ctx,
unsigned char input[8],
unsigned char output[8] )
{
des_crypt( ctx->dsk, input, output );
}

/*
* DES-CBC buffer encryption
*/
void des_cbc_encrypt( des_context *ctx,
unsigned char iv[8],
unsigned char *input,
unsigned char *output,
int len )
{
int i;

while( len > 0 )
{
for( i = 0; i < 8; i++ )
output[i] = input[i] ^ iv[i];

des_crypt( ctx->esk, output, output );
memcpy( iv, output, 8 );

input  += 8;
output += 8;
len    -= 8;
}
}

/*
* DES-CBC buffer decryption
*/
void des_cbc_decrypt( des_context *ctx,
unsigned char iv[8],
unsigned char *input,
unsigned char *output,
int len )
{
int i;
unsigned char temp[8];

while( len > 0 )
{
memcpy( temp, input, 8 );
des_crypt( ctx->dsk, input, output );

for( i = 0; i < 8; i++ )
output[i] = output[i] ^ iv[i];

memcpy( iv, temp, 8 );

input  += 8;
output += 8;
len    -= 8;
}
}

/*
* Triple-DES key schedule (112-bit)
*/
void des3_set_2keys( des3_context *ctx, unsigned char key[16] )
{
int i;

des_main_ks( ctx->esk     , key     );
des_main_ks( ctx->dsk + 32, key + 8 );

for( i = 0; i < 32; i += 2 )
{
ctx->dsk[i     ] = ctx->esk[30 - i];
ctx->dsk[i +  1] = ctx->esk[31 - i];

ctx->esk[i + 32] = ctx->dsk[62 - i];
ctx->esk[i + 33] = ctx->dsk[63 - i];

ctx->esk[i + 64] = ctx->esk[     i];
ctx->esk[i + 65] = ctx->esk[ 1 + i];

ctx->dsk[i + 64] = ctx->dsk[     i];
ctx->dsk[i + 65] = ctx->dsk[ 1 + i];
}
}

/*
* Triple-DES key schedule (168-bit)
*/
void des3_set_3keys( des3_context *ctx, unsigned char key[24] )
{
int i;

des_main_ks( ctx->esk     , key      );
des_main_ks( ctx->dsk + 32, key +  8 );
des_main_ks( ctx->esk + 64, key + 16 );

for( i = 0; i < 32; i += 2 )
{
ctx->dsk[i     ] = ctx->esk[94 - i];
ctx->dsk[i +  1] = ctx->esk[95 - i];

ctx->esk[i + 32] = ctx->dsk[62 - i];
ctx->esk[i + 33] = ctx->dsk[63 - i];

ctx->dsk[i + 64] = ctx->esk[30 - i];
ctx->dsk[i + 65] = ctx->esk[31 - i];
}
}

static void des3_crypt( unsigned long SK[96],
unsigned char input[8],
unsigned char output[8] )
{
unsigned long X, Y, T;

GET_UINT32_BE( X, input, 0 );
GET_UINT32_BE( Y, input, 4 );

DES_IP( X, Y );

DES_ROUND( Y, X );  DES_ROUND( X, Y );
DES_ROUND( Y, X );  DES_ROUND( X, Y );
DES_ROUND( Y, X );  DES_ROUND( X, Y );
DES_ROUND( Y, X );  DES_ROUND( X, Y );
DES_ROUND( Y, X );  DES_ROUND( X, Y );
DES_ROUND( Y, X );  DES_ROUND( X, Y );
DES_ROUND( Y, X );  DES_ROUND( X, Y );
DES_ROUND( Y, X );  DES_ROUND( X, Y );

DES_ROUND( X, Y );  DES_ROUND( Y, X );
DES_ROUND( X, Y );  DES_ROUND( Y, X );
DES_ROUND( X, Y );  DES_ROUND( Y, X );
DES_ROUND( X, Y );  DES_ROUND( Y, X );
DES_ROUND( X, Y );  DES_ROUND( Y, X );
DES_ROUND( X, Y );  DES_ROUND( Y, X );
DES_ROUND( X, Y );  DES_ROUND( Y, X );
DES_ROUND( X, Y );  DES_ROUND( Y, X );

DES_ROUND( Y, X );  DES_ROUND( X, Y );
DES_ROUND( Y, X );  DES_ROUND( X, Y );
DES_ROUND( Y, X );  DES_ROUND( X, Y );
DES_ROUND( Y, X );  DES_ROUND( X, Y );
DES_ROUND( Y, X );  DES_ROUND( X, Y );
DES_ROUND( Y, X );  DES_ROUND( X, Y );
DES_ROUND( Y, X );  DES_ROUND( X, Y );
DES_ROUND( Y, X );  DES_ROUND( X, Y );

DES_FP( Y, X );

PUT_UINT32_BE( Y, output, 0 );
PUT_UINT32_BE( X, output, 4 );
}

/*
* Triple-DES block encryption (ECB mode)
*/
void des3_encrypt( des3_context *ctx,
unsigned char input[8],
unsigned char output[8] )
{
des3_crypt( ctx->esk, input, output );
}

/*
* Triple-DES block decryption (ECB mode)
*/
void des3_decrypt( des3_context *ctx,
unsigned char input[8],
unsigned char output[8] )
{
des3_crypt( ctx->dsk, input, output );
}

/*
* 3DES-CBC buffer encryption
*/
void des3_cbc_encrypt( des3_context *ctx,
unsigned char iv[8],
unsigned char *input,
unsigned char *output,
int len )
{
int i;

while( len > 0 )
{
for( i = 0; i < 8; i++ )
output[i] = input[i] ^ iv[i];

des3_crypt( ctx->esk, output, output );
memcpy( iv, output, 8 );

input  += 8;
output += 8;
len    -= 8;
}
}

/*
* 3DES-CBC buffer decryption
*/
void des3_cbc_decrypt( des3_context *ctx,
unsigned char iv[8],
unsigned char *input,
unsigned char *output,
int len )
{
int i;
unsigned char temp[8];

while( len > 0 )
{
memcpy( temp, input, 8 );
des3_crypt( ctx->dsk, input, output );

for( i = 0; i < 8; i++ )
output[i] = output[i] ^ iv[i];

memcpy( iv, temp, 8 );

input  += 8;
output += 8;
len    -= 8;
}
}

static const char _des_src[] = "_des_src";

#ifdef SELF_TEST

#include 

/*
* DES/3DES test vectors (source: NIST, tripledes-vectors.zip)
*/
static const unsigned char DES3_keys[24] =
{
0x01, 0x23, 0x45, 0x67, 0x89, 0xAB, 0xCD, 0xEF,
0x23, 0x45, 0x67, 0x89, 0xAB, 0xCD, 0xEF, 0x01,
0x45, 0x67, 0x89, 0xAB, 0xCD, 0xEF, 0x01, 0x23
};

static const unsigned char DES3_init[8] =
{
0x4E, 0x6F, 0x77, 0x20, 0x69, 0x73, 0x20, 0x74
};

static const unsigned char DES3_enc_test[3][8] =
{
{ 0x6A, 0x2A, 0x19, 0xF4, 0x1E, 0xCA, 0x85, 0x4B },
{ 0x03, 0xE6, 0x9F, 0x5B, 0xFA, 0x58, 0xEB, 0x42 },
{ 0xDD, 0x17, 0xE8, 0xB8, 0xB4, 0x37, 0xD2, 0x32 }
};

static const unsigned char DES3_dec_test[3][8] =
{
{ 0xCD, 0xD6, 0x4F, 0x2F, 0x94, 0x27, 0xC1, 0x5D },
{ 0x69, 0x96, 0xC8, 0xFA, 0x47, 0xA2, 0xAB, 0xEB },
{ 0x83, 0x25, 0x39, 0x76, 0x44, 0x09, 0x1A, 0x0A }
};

/*
* Checkup routine
*/
int des_self_test( void )
{
int i, j, u, v;
des_context ctx;
des3_context ctx3;
unsigned char buf[8];

for( i = 0; i < 6; i++ )
{
u = i >> 1;
v = i & 1;

printf( "  DES%c-EBC-%3d (%s): ",
( u == 0 ) ? ' ' : '3', 64 + u * 64,
( v == 0 ) ? "enc" : "dec" );

memcpy( buf, DES3_init, 8 );

if( u == 0 )
des_set_key( &ctx,  (unsigned char *) DES3_keys );

if( u == 1 )
des3_set_2keys( &ctx3, (unsigned char *) DES3_keys );

if( u == 2 )
des3_set_3keys( &ctx3, (unsigned char *) DES3_keys );

for( j = 0; j < 10000; j++ )
{
if( u == 0 )
{
if( v == 0 ) des_encrypt( &ctx, buf, buf );
if( v == 1 ) des_decrypt( &ctx, buf, buf );
}
else
{
if( v == 0 ) des3_encrypt( &ctx3, buf, buf );
if( v == 1 ) des3_decrypt( &ctx3, buf, buf );
}
}

if( ( v == 0 && memcmp( buf, DES3_enc_test[u], 8 ) != 0 ) ||
( v == 1 && memcmp( buf, DES3_dec_test[u], 8 ) != 0 ) )
{
printf( "failed\n" );
return( 1 );
}

printf( "passed\n" );
}

printf( "\n" );
return( 0 );
}
#else
int des_self_test( void )
{
return( 0 );
}
#endif

Referencias: - Data Encryption Standard - XySSL

4 comentarios:

Anónimo dijo...

Excelent. You just get the full point across.

Easy and clear

Thanks so much!!

Anónimo dijo...

Muy clara tu explicacion, se agradece la informacion
Saludos desde Peru

Anónimo dijo...

Where is the implementation???(MAIN)

Anónimo dijo...

muchísimas gracias, así se explican las cosas!