This week I learned about Data Encryption Standard (DES) and its simplified, educational version Simple DES (S–DES) in the Networking Security class. In this two–part post, I will go over my implementation of S–DES in Zig.

S–DES is a Feistal structure encryption–decryption standard with the following spec:

In part-1, I will write about the key generation process of S–DES. We need to generate two 8–bit keys for the two rounds of encryption.

First, lets import the zig standard module:

const std = @import("std");
const math = std.math;

The process starts with accepting a 10–bit key. Let’s assume this input is 1010000010.

pub fn generateKey() !struct{u8, u8} {
    const key: u10 = 0b1010000010;

Step–1: P10 Permutation

The 10–bit key is permutated in the following way:

This is implemented using bit shifts. The bit in n’th position is sampled with (key >> n) & 0b1 and then shifted to corresponding bit on the p10 mapping:

const p10_key: u10 = ((key >> 0) & 0b1) << 4 | // bit0 -> bit4 
                     ((key >> 1) & 0b1) << 2 | // bit1 -> bit2 
                     ((key >> 2) & 0b1) << 1 | // bit2 -> bit1 
                     ((key >> 3) & 0b1) << 6 | // bit3 -> bit6 
                     ((key >> 4) & 0b1) << 0 | // bit4 -> bit0 
                     ((key >> 5) & 0b1) << 8 | // bit5 -> bit8 
                     ((key >> 6) & 0b1) << 5 | // bit6 -> bit5 
                     ((key >> 7) & 0b1) << 9 | // bit7 -> bit9 
                     ((key >> 8) & 0b1) << 7 | // bit8 -> bit7 
                     ((key >> 9) & 0b1) << 3 ; // bit9 -> bit3 

The output of the P10 is also a 10–bit binary, and for our key its 1000001100.

Step–2: Split and Shift

The P10 permutated key is split into two 5–bit segments. Each segment is left shifted one bit. To be precise, it is a rotate–left operation, not a shift operation–the MSB is rotated back to the LSB.

Left–shifting the P10 result 5–bits gives the left half segment. We use the Zig built–in function @truncate to discard the first 5 bits and get u5 from u10. The right half is simply obtained by discarding the first 5 bits of p10_key. The rotl function rotates the bits around by one bit.

const left1: u5 = @truncate(p10_key >> 5);  
const left1_LS1: u5 = math.rotl(u5, left1, 1); 
const right1: u5 = @truncate(p10_key);
const right1_LS1: u5 = math.rotl(u5, right1, 1);

Step–3: First P8 Permutation

The left and right segments are combined to make a 10–bit sequence. This is followed by a P8 permutation, which produces a 8–bit sequence. The 8–bit sequence is our first key (Key–1). The P8 permutation scheme:

The combined key is found by right–shifting the left segment bits and then doing OR with the right segment bits:

const combined_key1: u8 = @as(u8, left1_LS1) << 5 | right1_LS1;
const p8_key1: u8 = ((combined_key1 >> 0) & 0b1) << 1 | // bit0 -> bit1 
                    ((combined_key1 >> 1) & 0b1) << 0 | // bit1 -> bit0 
                    ((combined_key1 >> 2) & 0b1) << 3 | // bit2 -> bit3 
                    ((combined_key1 >> 3) & 0b1) << 5 | // bit3 -> bit5 
                    ((combined_key1 >> 4) & 0b1) << 7 | // bit4 -> bit7 
                    ((combined_key1 >> 5) & 0b1) << 2 | // bit5 -> bit2 
                    ((combined_key1 >> 6) & 0b1) << 4 | // bit6 -> bit4 
                    ((combined_key1 >> 7) & 0b1) << 6 ; // bit7 -> bit6 

To find the second key, we need to repeat the shift and permutate process once more.

Step–4: 2–bit Left–Shift

In this step, we have to left–shift the two results from LS-1 (step–2). However, in this case the shift is 2–bit instead of 1:

const left2_LS2 = math.rotl(u5, left1_LS1, 2);
const right2_LS2 = math.rotl(u5, right1_LS1, 2);

Step–5: Second P8 Permutation

We combine the two segments from the previous step, apply P8 permutation, and return the result along with Key–1 as a tuple:

const combined_key2: u8 = @as(u8, left2_LS2) << 5 | right2_LS2;
const p8_key2: u8 = ((combined_key2 >> 0) & 0b1) << 1 | // bit0 -> bit1 
                    ((combined_key2 >> 1) & 0b1) << 0 | // bit1 -> bit0 
                    ((combined_key2 >> 2) & 0b1) << 3 | // bit2 -> bit3 
                    ((combined_key2 >> 3) & 0b1) << 5 | // bit3 -> bit5 
                    ((combined_key2 >> 4) & 0b1) << 7 | // bit4 -> bit7 
                    ((combined_key2 >> 5) & 0b1) << 2 | // bit5 -> bit2 
                    ((combined_key2 >> 6) & 0b1) << 4 | // bit6 -> bit4 
                    ((combined_key2 >> 7) & 0b1) << 6 ; // bit7 -> bit6 

return .{p8_key1, p8_key2};

Now, we have the two 8–bit keys needed for the two rounds of encryption of SDES. This marks the end of the key generation process. I will describe the encryption process in my next post.

Wrapping up

pub fn generateKey(key: u10) !struct{u8, u8} {
    const p10_key: u10 = ((key >> 0) & 0b1) << 4 | // bit0 -> bit4 
                         ((key >> 1) & 0b1) << 2 | // bit1 -> bit2 
                         ((key >> 2) & 0b1) << 1 | // bit2 -> bit1 
    ...
    ...
    return .{p8_key1, p8_key2};

const std = @import("std");

pub fn build(b: *std.Build) void {
    const target = b.standardTargetOptions(.{});
    const optimize = b.standardOptimizeOption(.{});

    const key_mod = b.addModule("key", .{ // <-- Create the module
        .root_source_file = b.path("src/key_generation.zig"),
    });
    const exe = b.addExecutable(.{
        .name = "sdes",
        .root_module = b.createModule(.{
            .root_source_file = b.path("src/main.zig"),
            .target = target,
            .optimize = optimize,
            .imports = &.{
                .{.name = "key", .module=key_mod}, // <-- add to the build
            },
        }),
    });

    b.installArtifact(exe);

    const run_step = b.step("run", "Run the app");
    const run_cmd = b.addRunArtifact(exe);
    run_step.dependOn(&run_cmd.step);
    run_cmd.step.dependOn(b.getInstallStep());

    if (b.args) |args| {
        run_cmd.addArgs(args);
    }

}