des-decryption

des-decryption

#!/usr/bin/env python3

CIPHERTEXT_BITS = "1100101011101101101000100110010101011111101101110011100001110011"

KEY_64_BITS = "0100110001001111010101100100010101000011010100110100111001000100"

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,
]

FP = [
    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,
]

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,
]

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,
]

PC1 = [
    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,
]

PC2 = [
    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,
]

SHIFTS = [1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1]

SBOX = [
    # S1
    [
        [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],
    ],
    # S2
    [
        [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],
    ],
    # S3
    [
        [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],
    ],
    # S4
    [
        [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],
    ],
    # S5
    [
        [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],
    ],
    # S6
    [
        [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],
    ],
    # S7
    [
        [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],
    ],
    # S8
    [
        [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],
    ],
]


def bits_to_int(b: str) -> int:
    return int(b, 2)


def int_to_bits(x: int, width: int) -> str:
    return format(x, f"0{width}b")


def permute(bits: str, table: list[int]) -> str:
    return "".join(bits[i - 1] for i in table)


def xor_bits(a: str, b: str) -> str:
    return "".join("1" if x != y else "0" for x, y in zip(a, b))


def left_rotate(bits: str, n: int) -> str:
    n %= len(bits)
    return bits[n:] + bits[:n]


def chunk(s: str, size: int) -> list[str]:
    return [s[i : i + size] for i in range(0, len(s), size)]


def bits_to_hex(bits: str) -> str:
    return format(int(bits, 2), f"0{len(bits)//4}X")


def hex28(bits28: str) -> str:
    return format(int(bits28, 2), "07X")  # 28 bits -> 7 hex


def hex32(bits32: str) -> str:
    return format(int(bits32, 2), "08X")


def hex48(bits48: str) -> str:
    return format(int(bits48, 2), "012X")


def try_ascii(bits64: str) -> str:
    b = int(bits64, 2).to_bytes(8, byteorder="big")
    # show printable ASCII; otherwise escape
    out = ""
    for c in b:
        out += chr(c) if 32 <= c <= 126 else "."
    return out


def sbox_substitution(bits48: str) -> str:
    blocks = chunk(bits48, 6)
    out = ""
    for i, b6 in enumerate(blocks):
        row = int(b6[0] + b6[5], 2)
        col = int(b6[1:5], 2)
        val = SBOX[i][row][col]
        out += format(val, "04b")
    return out 


def f_function(R32: str, K48: str) -> tuple[str, dict]:
    ER48 = permute(R32, E)
    x = xor_bits(ER48, K48)
    s = sbox_substitution(x)
    p = permute(s, P)
    dbg = {"E(R)": ER48, "E(R)^K": x, "SBOX": s, "P": p}
    return p, dbg


def key_schedule(key64: str) -> tuple[list[str], dict]:
    k56 = permute(key64, PC1)
    C = k56[:28]
    D = k56[28:]
    dbg = {
        "PC1": k56,
        "C0": C,
        "D0": D,
        "rounds": [],
    }

    round_keys = []
    for r in range(16):
        sh = SHIFTS[r]
        C = left_rotate(C, sh)
        D = left_rotate(D, sh)
        CD = C + D
        K = permute(CD, PC2)
        round_keys.append(K)
        dbg["rounds"].append({"round": r + 1, "shift": sh, "Cn": C, "Dn": D, "Kn": K})
    return round_keys, dbg


def des_decrypt_block(cipher64: str, round_keys: list[str]) -> tuple[str, dict]:
    """Decrypt one 64-bit block. round_keys must be K1..K16; decryption uses K16..K1."""
    ip = permute(cipher64, IP)
    L = ip[:32]
    R = ip[32:]
    trace = {"IP": ip, "L0": L, "R0": R, "rounds": []}

    for i in range(16):
        K = round_keys[15 - i]
        f_out, _dbg = f_function(R, K)
        newL = R
        newR = xor_bits(L, f_out)
        trace["rounds"].append(
            {"round": i + 1, "K_used": 16 - i, "f": f_out, "Ln": newL, "Rn": newR}
        )
        L, R = newL, newR
        
    preoutput = R + L
    plain = permute(preoutput, FP)
    trace["preoutput"] = preoutput
    trace["FP"] = plain
    return plain, trace


def print_header(title: str):
    print("\n" + "=" * len(title))
    print(title)
    print("=" * len(title))


def main():
    print_header("Inputs")
    print("Ciphertext (bin):", CIPHERTEXT_BITS)
    print("Ciphertext (hex):", bits_to_hex(CIPHERTEXT_BITS))
    print("Key 64-bit (bin):", KEY_64_BITS)
    print("Key 64-bit (hex):", bits_to_hex(KEY_64_BITS))


    round_keys, kdbg = key_schedule(KEY_64_BITS)

    print_header("Key Schedule")
    print("PC-1(key) 56b (hex):", bits_to_hex(kdbg["PC1"]))
    print("C0 28b (hex):", hex28(kdbg["C0"]))
    print("D0 28b (hex):", hex28(kdbg["D0"]))
    print("\nRound | Shift |   Cn(28b hex) |   Dn(28b hex) |        Kn(48b hex)")
    print("-" * 70)
    for rd in kdbg["rounds"]:
        print(
            f"{rd['round']:>5} | {rd['shift']:>5} | "
            f"{hex28(rd['Cn']):>12} | {hex28(rd['Dn']):>12} | "
            f"{hex48(rd['Kn'])}"
        )

    plain_bits, t = des_decrypt_block(CIPHERTEXT_BITS, round_keys)

    print_header("Decryption Trace")
    print("After IP (hex):", bits_to_hex(t["IP"]))
    print("L0 (hex):", hex32(t["L0"]))
    print("R0 (hex):", hex32(t["R0"]))
    print("\nRound | KeyUsed | f(R,K) 32b hex |        Ln(32b) |        Rn(32b)")
    print("-" * 78)
    for rd in t["rounds"]:
        print(
            f"{rd['round']:>5} | {rd['K_used']:>7} | {hex32(rd['f'])} | "
            f"{hex32(rd['Ln'])} | {hex32(rd['Rn'])}"
        )

    print_header("Plaintext")
    print("Plaintext (bin):", plain_bits)
    print("Plaintext (hex):", bits_to_hex(plain_bits))
    print("Plaintext (ASCII):", try_ascii(plain_bits))

if __name__ == "__main__":
    main()