des.cpp

// ============================================================================
// des.cpp — DES Algorithm Implementation
// ============================================================================
//
// This file implements the DES algorithm as described in Forouzan's
// "Cryptography and Network Security", with performance optimizations.
//
// The overall flow matches the textbook exactly:
//
//   Plaintext (64 bits)
//       |
//   Initial Permutation (IP)        ← fast_ip()
//       |
//   Split into L0 (32 bits) and R0 (32 bits)
//       |
//   16 Feistel rounds:              ← run_rounds()
//       L[i] = R[i-1]
//       R[i] = L[i-1] XOR f(R[i-1], K[i])
//       where f() is the Feistel function:
//           Expand R (32→48)        ← expand()
//           XOR with round key K    ← simple ^ operator
//           S-box substitution      ← sp_box_ lookup (merged with P-box)
//           Straight permutation    ← (merged into sp_box_ lookup)
//       |
//   Swap and Final Permutation (FP) ← fast_fp()
//       |
//   Ciphertext (64 bits)
//
// Decryption is the same algorithm with round keys applied in reverse order.
//
// ============================================================================

#include "des.h"

#include <iomanip>
#include <iostream>
#include <stdexcept>

namespace des {

// ── Hex conversion utilities ────────────────────────────────────────────────
// Convert between hex strings ("AABB09...") and integers (0xAABB09...).

uint64_t hex_to_u64(std::string_view hex) {
    uint64_t result = 0;
    for (char c : hex) {
        result <<= 4;  // make room for the next nibble (4 bits)
        if (c >= '0' && c <= '9')      result |= c - '0';
        else if (c >= 'A' && c <= 'F') result |= c - 'A' + 10;
        else if (c >= 'a' && c <= 'f') result |= c - 'a' + 10;
        else throw std::invalid_argument(
            std::string("hex_to_u64: invalid hex character '") + c + "'");
    }
    return result;
}

std::string u64_to_hex(uint64_t val, int nibbles) {
    static constexpr char digits[] = "0123456789ABCDEF";
    std::string hex(nibbles, '0');
    for (int i = nibbles - 1; i >= 0; --i) {
        hex[i] = digits[val & 0xF];  // extract lowest nibble
        val >>= 4;
    }
    return hex;
}

std::string u32_to_hex(uint32_t val) { return u64_to_hex(val, 8); }
std::string u48_to_hex(uint64_t val) { return u64_to_hex(val, 12); }

// ============================================================================
// Lookup table initialization
// ============================================================================
//
// These tables are built once (on first Cipher construction) and shared
// across all instances. They precompute results that the textbook computes
// bit-by-bit, trading memory for speed.

std::array<std::array<uint32_t, 64>, 8> Cipher::sp_box_;
std::array<std::array<uint64_t, 256>, 8> Cipher::ip_table_;
std::array<std::array<uint64_t, 256>, 8> Cipher::fp_table_;
bool Cipher::tables_initialized_ = false;

// Build a byte-indexed lookup table for a 64-bit → 64-bit permutation.
//
// Textbook approach:  for each of the 64 output bits, look up which input
//                     bit goes there (one at a time).
//
// Optimized approach: split the 64-bit input into 8 bytes. For each byte
//                     position (0–7) and each possible byte value (0–255),
//                     precompute what that byte contributes to the output.
//                     At runtime: output = table[0][byte0] | table[1][byte1]
//                                        | ... | table[7][byte7]
//                     This replaces 64 bit operations with 8 table lookups.
static void build_byte_perm_table(
        std::array<std::array<uint64_t, 256>, 8>& table,
        const int* perm) {
    for (int byte_pos = 0; byte_pos < 8; ++byte_pos) {
        for (int val = 0; val < 256; ++val) {
            uint64_t result = 0;
            for (int bit = 0; bit < 8; ++bit) {
                if (val & (1 << (7 - bit))) {
                    // This bit is at DES position (byte_pos*8 + bit + 1)
                    // (1-indexed, as in the textbook tables)
                    int in_pos = byte_pos * 8 + bit + 1;
                    // Find which output position this input bit maps to
                    for (int out = 0; out < 64; ++out) {
                        if (perm[out] == in_pos) {
                            result |= 1ULL << (63 - out);
                            break;
                        }
                    }
                }
            }
            table[byte_pos][val] = result;
        }
    }
}

void Cipher::init_tables() {
    if (tables_initialized_) return;

    // ── SP-boxes ────────────────────────────────────────────────────────
    // In the textbook, the Feistel function does two separate steps:
    //   Step 4: S-box substitution (6 bits → 4 bits, per box)
    //   Step 5: Straight permutation (P-box, rearranges all 32 bits)
    //
    // Since the P-box always follows the S-boxes, we can precompute the
    // combined result: for each S-box (0–7) and each possible 6-bit input
    // (0–63), store the 32-bit output after BOTH steps.
    //
    // At runtime, the Feistel function just does:
    //   result |= sp_box_[i][six_bits]   (for each of the 8 S-boxes)
    // instead of: S-box lookup, then 32 bit-by-bit P-box moves.
    for (int box = 0; box < 8; ++box) {
        for (int input = 0; input < 64; ++input) {
            // S-box row/column extraction (same as textbook):
            //   row = outer bits (bit 5 and bit 0 of the 6-bit group)
            //   col = inner 4 bits (bits 4-3-2-1)
            int row = ((input >> 4) & 0x02) | (input & 0x01);
            int col = (input >> 1) & 0x0F;
            uint32_t sbox_val = kSBox[box][row][col];
            // Place the 4-bit result in the correct nibble position
            // (S-box 0 outputs to bits 1-4, S-box 1 to bits 5-8, etc.)
            uint32_t positioned = sbox_val << (4 * (7 - box));
            // Apply the straight permutation to get the final 32-bit result
            sp_box_[box][input] = static_cast<uint32_t>(
                permute64(positioned, 32, kStraightPermutation.data(), 32));
        }
    }

    // ── Byte-indexed IP and FP tables ───────────────────────────────────
    build_byte_perm_table(ip_table_, kInitialPermutation.data());
    build_byte_perm_table(fp_table_, kFinalPermutation.data());

    tables_initialized_ = true;
}

// ============================================================================
// Cipher construction
// ============================================================================

Cipher::Cipher(std::string_view key_hex) {
    if (key_hex.size() != 16) {
        throw std::invalid_argument("Key must be exactly 16 hex characters (64 bits)");
    }
    init_tables();
    generate_round_keys(hex_to_u64(key_hex));
}

// ============================================================================
// Permutation — the textbook (bit-by-bit) approach
// ============================================================================
//
// This is the straightforward implementation of a DES permutation table:
//   output bit i = input bit table[i]
//
// The table uses 1-based indexing (as in the textbook).
// Example: if table[0] = 58, then output bit 0 (MSB) = input bit 58.
//
// This function is used during initialization and key generation.
// For the hot path (IP, FP, P-box), we use precomputed lookup tables instead.

uint64_t Cipher::permute64(uint64_t input, int in_bits,
                           const int* table, int out_bits) {
    uint64_t output = 0;
    for (int i = 0; i < out_bits; ++i) {
        // Convert 1-based table entry to 0-based bit position from LSB
        int src_bit = in_bits - table[i];
        if (input & (1ULL << src_bit)) {
            output |= 1ULL << (out_bits - 1 - i);
        }
    }
    return output;
}

// ============================================================================
// Fast Initial Permutation (IP) and Final Permutation (FP)
// ============================================================================
//
// These do the exact same thing as:
//   permute64(input, 64, kInitialPermutation.data(), 64)
//   permute64(input, 64, kFinalPermutation.data(), 64)
//
// But instead of 64 conditional bit moves, they use 8 precomputed table
// lookups (one per input byte) and OR the results together.
//
// (Forouzan: Table 6.1 for IP, Table 6.4 for FP)

uint64_t Cipher::fast_ip(uint64_t input) {
    return ip_table_[0][(input >> 56) & 0xFF] |
           ip_table_[1][(input >> 48) & 0xFF] |
           ip_table_[2][(input >> 40) & 0xFF] |
           ip_table_[3][(input >> 32) & 0xFF] |
           ip_table_[4][(input >> 24) & 0xFF] |
           ip_table_[5][(input >> 16) & 0xFF] |
           ip_table_[6][(input >>  8) & 0xFF] |
           ip_table_[7][ input        & 0xFF];
}

uint64_t Cipher::fast_fp(uint64_t input) {
    return fp_table_[0][(input >> 56) & 0xFF] |
           fp_table_[1][(input >> 48) & 0xFF] |
           fp_table_[2][(input >> 40) & 0xFF] |
           fp_table_[3][(input >> 32) & 0xFF] |
           fp_table_[4][(input >> 24) & 0xFF] |
           fp_table_[5][(input >> 16) & 0xFF] |
           fp_table_[6][(input >>  8) & 0xFF] |
           fp_table_[7][ input        & 0xFF];
}

// ============================================================================
// Expansion Permutation (E-box): 32 bits → 48 bits
// ============================================================================
//
// (Forouzan: "Expansion Permutation" — Table 6.2)
//
// The textbook describes this as a table lookup, but the E-box has a very
// regular structure. Each of the 8 four-bit nibbles gets expanded to 6 bits
// by borrowing one bit from each neighbor (with wraparound):
//
//   Nibble i (bits b3 b2 b1 b0) becomes:  [left_neighbor_b0] b3 b2 b1 b0 [right_neighbor_b3]
//
// This lets us compute it with bit shifts instead of a table loop.

uint64_t Cipher::expand(uint32_t r) {
    uint64_t e = 0;
    for (int i = 0; i < 8; ++i) {
        int shift = 28 - i * 4;  // bit position of nibble i (MSB-first)

        // The 4 middle bits come directly from nibble i
        uint32_t middle = (r >> shift) & 0xF;

        // Borrow one bit from the left neighbor (wraps: nibble 0 borrows from nibble 7)
        uint32_t left_bit = (r >> ((shift + 4) & 31)) & 1;

        // Borrow one bit from the right neighbor (wraps: nibble 7 borrows from nibble 0)
        uint32_t right_bit = (r >> ((shift - 1) & 31)) & 1;

        // Assemble the 6-bit group: [left_bit] [middle 4 bits] [right_bit]
        uint64_t six = (left_bit << 5) | (middle << 1) | right_bit;

        // Place this 6-bit group at the correct position in the 48-bit output
        e |= six << ((7 - i) * 6);
    }
    return e;
}

// ============================================================================
// Key Generation — produce 16 round subkeys from the 64-bit master key
// ============================================================================
//
// (Forouzan: "Key Generation" — Figure 6.22)
//
// Steps (per the textbook):
//   1. Apply Parity Bit Drop (PC-1): 64 bits → 56 bits
//      This removes the 8 parity bits (every 8th bit of the key).
//   2. Split the 56-bit result into two 28-bit halves (C and D).
//   3. For each round i = 1..16:
//      a. Circular-left-shift both C and D by 1 or 2 positions
//         (the shift amount comes from kShiftSchedule).
//      b. Recombine C and D into 56 bits.
//      c. Apply Key Compression (PC-2): 56 bits → 48 bits to get round key K[i].

void Cipher::generate_round_keys(uint64_t key64) {
    // Step 1: Parity drop (PC-1) — 64 bits → 56 bits
    uint64_t key56 = permute64(key64, 64, kParityDrop.data(), 56);

    // Step 2: Split into two 28-bit halves (C and D in the textbook)
    uint32_t left  = static_cast<uint32_t>(key56 >> 28) & 0x0FFFFFFF;  // C (upper 28 bits)
    uint32_t right = static_cast<uint32_t>(key56) & 0x0FFFFFFF;        // D (lower 28 bits)

    // Step 3: Generate each round key
    for (int round = 1; round <= 16; ++round) {
        // Step 3a: Circular left shift within 28 bits
        // The shift amount is 1 for rounds 1, 2, 9, 16 and 2 for all others.
        int shift = kShiftSchedule[round];
        left  = ((left << shift) | (left >> (28 - shift))) & 0x0FFFFFFF;
        right = ((right << shift) | (right >> (28 - shift))) & 0x0FFFFFFF;

        // Step 3b: Recombine into 56 bits
        uint64_t combined = (static_cast<uint64_t>(left) << 28) | right;

        // Step 3c: Key compression (PC-2) — 56 bits → 48-bit round key
        round_keys_[round - 1] = permute64(combined, 56,
                                            kKeyCompression.data(), 48);
    }
}

// ============================================================================
// Feistel Function f(R, K) — the core of each DES round
// ============================================================================
//
// (Forouzan: "DES Function" — Figure 6.7)
//
// Textbook steps:
//   1. Expansion (E-box):        32-bit R → 48 bits
//   2. Key mixing:               XOR with 48-bit round key K
//   3. Split into eight 6-bit groups
//   4. S-box substitution:       each 6 bits → 4 bits (8 S-boxes)
//   5. Straight permutation (P-box): rearrange the 32 output bits
//
// In this implementation, steps 4 and 5 are merged into the precomputed
// SP-box lookup (sp_box_). For each S-box and each possible 6-bit input,
// the lookup table already stores the 32-bit result after BOTH the S-box
// substitution AND the straight permutation.

uint32_t Cipher::feistel(uint32_t block32, uint64_t round_key48) {
    // Step 1: Expansion permutation (32 → 48 bits)
    // Step 2: XOR with round key
    uint64_t xored = expand(block32) ^ round_key48;

    // Steps 3–5: S-box substitution + straight permutation (merged)
    // Extract each 6-bit group and look up the combined result.
    uint32_t result = 0;
    for (int i = 0; i < 8; ++i) {
        // Extract 6 bits for S-box i from the 48-bit XOR result.
        // S-box 0 uses the leftmost (most significant) 6 bits, etc.
        int six_bits = (xored >> ((7 - i) * 6)) & 0x3F;

        // SP-box lookup: combines S-box output + P-box in one step.
        // In the textbook, this would be:
        //   row = outer_bits(six_bits)
        //   col = inner_bits(six_bits)
        //   sbox_output[i] = kSBox[i][row][col]          ← 4 bits
        //   then apply straight permutation to all 32 bits
        result |= sp_box_[i][six_bits];
    }
    return result;
}

// ============================================================================
// DES Round Loop — encryption and decryption
// ============================================================================
//
// (Forouzan: "Cipher" — Figure 6.4)
//
// DES performs 16 rounds of the Feistel network:
//   1. Apply Initial Permutation (IP) to the 64-bit input
//   2. Split into 32-bit left (L) and right (R) halves
//   3. For each round i = 1..16:
//        new_R = L XOR f(R, K[i])
//        new_L = R
//      (This is the Feistel structure — R passes through unchanged to
//       become the next L, while L gets mixed with f(R, K).)
//   4. Swap the final L and R, then apply Final Permutation (FP)
//
// Decryption uses the exact same structure — the only difference is that
// round keys are applied in reverse order (K16 first, K1 last).
// This works because the Feistel structure is its own inverse.

uint64_t Cipher::run_rounds(uint64_t input, bool reverse_keys) const {
    // Step 1: Initial Permutation (Forouzan: Table 6.1)
    uint64_t permuted = fast_ip(input);

    // Step 2: Split into L0 and R0
    uint32_t left  = static_cast<uint32_t>(permuted >> 32);  // upper 32 bits
    uint32_t right = static_cast<uint32_t>(permuted);         // lower 32 bits

    // Step 3: 16 Feistel rounds
    for (int i = 0; i < 16; ++i) {
        // For encryption: use keys K1, K2, ..., K16 (in order)
        // For decryption: use keys K16, K15, ..., K1 (reversed)
        int key_idx = reverse_keys ? (15 - i) : i;

        uint32_t f_out = feistel(right, round_keys_[key_idx]);
        uint32_t new_right = left ^ f_out;  // R[i] = L[i-1] XOR f(R[i-1], K[i])
        left = right;                        // L[i] = R[i-1]
        right = new_right;
    }

    // Step 4: After round 16, swap L and R (note: the loop already swapped
    // them on each iteration, so we combine as R16 || L16), then apply FP.
    uint64_t combined = (static_cast<uint64_t>(right) << 32) | left;
    return fast_fp(combined);  // Final Permutation (Forouzan: Table 6.4)
}

uint64_t Cipher::encrypt_block(uint64_t block) const {
    return run_rounds(block, false);  // keys in order: K1..K16
}

uint64_t Cipher::decrypt_block(uint64_t block) const {
    return run_rounds(block, true);   // keys reversed: K16..K1
}

// ============================================================================
// String-based encrypt/decrypt (with optional verbose round output)
// ============================================================================

std::string Cipher::encrypt(std::string_view plaintext_hex, bool verbose) {
    if (plaintext_hex.size() != 16) {
        throw std::invalid_argument("Input must be exactly 16 hex characters (64 bits)");
    }
    uint64_t input = hex_to_u64(plaintext_hex);

    if (!verbose) {
        return u64_to_hex(encrypt_block(input));
    }

    // Verbose path: repeat the round loop with per-round printing
    uint64_t permuted = fast_ip(input);
    uint32_t left  = static_cast<uint32_t>(permuted >> 32);
    uint32_t right = static_cast<uint32_t>(permuted);

    print_round_header();
    for (int i = 0; i < 16; ++i) {
        uint32_t f_out = feistel(right, round_keys_[i]);
        uint32_t new_right = left ^ f_out;
        left = right;
        right = new_right;
        print_round(i + 1, left, right, round_keys_[i]);
    }

    uint64_t combined = (static_cast<uint64_t>(right) << 32) | left;
    return u64_to_hex(fast_fp(combined));
}

std::string Cipher::decrypt(std::string_view ciphertext_hex, bool verbose) {
    if (ciphertext_hex.size() != 16) {
        throw std::invalid_argument("Input must be exactly 16 hex characters (64 bits)");
    }
    uint64_t input = hex_to_u64(ciphertext_hex);

    if (!verbose) {
        return u64_to_hex(decrypt_block(input));
    }

    uint64_t permuted = fast_ip(input);
    uint32_t left  = static_cast<uint32_t>(permuted >> 32);
    uint32_t right = static_cast<uint32_t>(permuted);

    print_round_header();
    for (int i = 0; i < 16; ++i) {
        int key_idx = 15 - i;  // reverse key order for decryption
        uint32_t f_out = feistel(right, round_keys_[key_idx]);
        uint32_t new_right = left ^ f_out;
        left = right;
        right = new_right;
        print_round(i + 1, left, right, round_keys_[key_idx]);
    }

    uint64_t combined = (static_cast<uint64_t>(right) << 32) | left;
    return u64_to_hex(fast_fp(combined));
}

// ── Verbose output helpers ──────────────────────────────────────────────────

void Cipher::print_round_header() {
    std::cout << color::bold_blue
              << std::setw(6) << "Round"
              << std::setw(12) << "Left"
              << std::setw(12) << "Right"
              << std::setw(14) << "Round Key"
              << color::reset << '\n';
}

void Cipher::print_round(int round, uint32_t left, uint32_t right, uint64_t key) {
    std::cout << color::bold_blue << std::setw(4) << round << color::reset
              << std::setw(12) << u32_to_hex(left)
              << std::setw(12) << u32_to_hex(right)
              << std::setw(14) << u48_to_hex(key) << '\n';
}

} // namespace des