Cornell Photograph

A Simplified DES-Type Algorithm

Description

This is an implementation of the DES-like Feistel system presented in Section 4.2 of Introduction to Cryptography (Second Edition), by Wade Trappe and Lawrence C. Washington. Combined with my driver functions, it can be used to solve Computer Problems 1 & 2 from that chapter. The block size for this cipher is 12 bits, and the key size is 9 bits.

This cipher is useful for demonstrating differential cryptanalysis, and with the changes mentioned in the code comments, can be modified to allow two weak keys.

simpledes.h

#ifndef __SIMPLEDES_H__
#define __SIMPLEDES_H__

#include <stdint.h>

uint16_t do_round(const uint16_t in, const uint8_t k);
uint8_t do_f(const uint8_t r, const uint8_t k);
uint8_t expand(const uint8_t r);
uint8_t make_key(const uint16_t k, const int round);
uint16_t encrypt(const uint16_t pt, const uint16_t key);
uint16_t decrypt(const uint16_t ct, const uint16_t key);
uint16_t swap_lr(const uint16_t in);
void cbc_encrypt(const uint16_t pt[], uint16_t ct[], const uint16_t key,
        const uint16_t iv, const int nblocks);
void cbc_decrypt(const uint16_t ct[], uint16_t pt[], const uint16_t key,
        const uint16_t iv, const int nblocks);

#endif  /* __SIMPLEDES_H__ */

/* simpledes.h
 *
 * Copyright (C) 2009  Curran D. Muhlberger
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

simpledes.c

#include "simpledes.h"

#define FIRSTROUND 1
#define LASTROUND 4

static const uint8_t s1[2][8] = { {5, 2, 1, 6, 3, 4, 7, 0},
                                  {1, 4, 6, 2, 0, 7, 5, 3} };
static const uint8_t s2[2][8] = { {4, 0, 6, 5, 7, 1, 3, 2},
                                  {5, 3, 0, 7, 6, 2, 1, 4} };

uint16_t do_round(const uint16_t in, const uint8_t k)
{
    uint16_t out = 0;
    uint8_t rin = 0;
    uint8_t lin = 0;

    rin = in & 0x3F;
    lin = (in & 0xFC0) >> 6;

    out = (rin << 6) | (lin ^ do_f(rin, k));

    return out;
}

uint8_t expand(const uint8_t r)
{
    uint8_t out = 0;

    out = r & 0x3;
    out |= (r & 0xC) << 1;
    out |= (r & 0x30) << 2;
    out |= (r & 0x4) << 3;
    out |= (r & 0x8) >> 1;

    return out;
}

uint8_t do_f(const uint8_t r, const uint8_t k)
{
    uint8_t a = 0;
    uint8_t a1 = 0;
    uint8_t a2 = 0;
    uint8_t b1 = 0;
    uint8_t b2 = 0;
    uint8_t out = 0;

    a = expand(r) ^ k;
    a1 = (a & 0xF0) >> 4;
    a2 = a & 0xF;

    b1 = s1[(a1 & 0x8) >> 3][a1 & 0x7];
    b2 = s2[(a2 & 0x8) >> 3][a2 & 0x7];

    out = (b1 << 3) | b2;
    return out;
}

uint8_t make_key(const uint16_t k, const int round)
{
    uint8_t out = 0;

    if (round == 1)
    {
        out = (k >> 1) & 0xFF;
    }
    else
    {
        out = (k << (round - 2)) & 0xFF;
        out |= (k >> (11 - round));
    }

    return out;
}

uint16_t encrypt(const uint16_t pt, const uint16_t key)
{
    uint8_t ki;
    uint16_t ct;
    int i;

    ct = pt;

    for (i = FIRSTROUND; i <= LASTROUND; ++i)
    {
        ki = make_key(key, i);
        ct = do_round(ct, ki);
    }

    /* Uncomment to make 0x0 and 0x1ff weak keys */
    /* ct = swap_lr(ct); */

    return ct;
}

uint16_t decrypt(const uint16_t ct, const uint16_t key)
{
    uint8_t ki;
    uint16_t pt;
    int i;

    pt = swap_lr(ct);

    /* Uncomment to make 0x0 and 0x1ff weak keys */
    /* pt = swap_lr(pt); */

    for (i = LASTROUND; i >= FIRSTROUND; --i)
    {
        ki = make_key(key, i);
        pt = do_round(pt, ki);
    }

    pt = swap_lr(pt);
    return pt;
}

uint16_t swap_lr(const uint16_t in)
{
    uint16_t out = 0;

    out = (in & 0x3F) << 6;
    out |= (in & 0xFC0) >> 6;

    return out;
}

void cbc_encrypt(const uint16_t pt[], uint16_t ct[], const uint16_t key,
        const uint16_t iv, const int nblocks)
{
    int i;

    ct[0] = encrypt(pt[0] ^ iv, key);

    for (i = 1; i < nblocks; ++i)
    {
        ct[i] = encrypt(pt[i] ^ ct[i - 1], key);
    }
}

void cbc_decrypt(const uint16_t ct[], uint16_t pt[], const uint16_t key,
        const uint16_t iv, const int nblocks)
{
    int i;

    pt[0] = decrypt(ct[0], key) ^ iv;

    for (i = 1; i < nblocks; ++i)
    {
        pt[i] = decrypt(ct[i], key) ^ ct[i - 1];
    }
}

/* simpledes.c
 *
 * Copyright (C) 2009  Curran D. Muhlberger
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */