Calculate and XOR Distribution Tables (XDT) for S-Boxes and best 2-round iterative characteristic (1/234).
All output of program is written to output.txt
, found in the current working directory.
Should be compiled with C99 support.
#ifndef DES_H | |
#define DES_H | |
/* width of s-box input width (bits) */ | |
#define DES_SIN (6) | |
/* width of s-box output width (bits) */ | |
#define DES_SOUT (4) | |
/* rows in each s-box */ | |
#define DES_SROW (4) | |
/* columns in each s-box */ | |
#define DES_SCOL (16) | |
/* number of s-boxes */ | |
#define DES_SNUM (8) | |
/* s-boxes */ | |
int DES_S1[DES_SROW][DES_SCOL] = | |
{{ 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 }}; | |
int DES_S2[DES_SROW][DES_SCOL] = | |
{{ 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 }}; | |
int DES_S3[DES_SROW][DES_SCOL] = | |
{{ 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 }}; | |
int DES_S4[DES_SROW][DES_SCOL] = | |
{{ 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 }}; | |
int DES_S5[DES_SROW][DES_SCOL] = | |
{{ 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 }}; | |
int DES_S6[DES_SROW][DES_SCOL] = | |
{{ 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 }}; | |
int DES_S7[DES_SROW][DES_SCOL] = | |
{{ 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 }}; | |
int DES_S8[DES_SROW][DES_SCOL] = | |
{{ 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 }}; | |
#endif /* DES_H */ |
#include <stdlib.h> | |
#include <stdio.h> | |
#include <stdint.h> | |
#include <string.h> | |
#include "des.h" | |
/* integer exponent (naive) */ | |
int iexp(int base, unsigned int exp); | |
/* apply given value to s-box */ | |
int sbox(int n, int x); | |
/* utility function for printing XDT to file */ | |
void print_tab(int x_size, int y_size, int tab[][y_size], FILE *fp); | |
/* path of output file */ | |
char *output_path = "output.txt"; | |
int main(void) | |
{ | |
int n, i, j, is, js, x, y; | |
FILE *fp; | |
int x_size = iexp(2, DES_SIN), | |
y_size = iexp(2, DES_SOUT), | |
t_size = DES_SNUM; | |
/* declare number of XDT tables */ | |
int xdt[t_size][x_size][y_size]; | |
/* reset table to zero */ | |
memset(xdt, 0, sizeof(xdt)); | |
/* open output file */ | |
fp = fopen(output_path, "w"); | |
if (fp == NULL) { | |
fprintf(stderr, "error opening file '%s'\n", output_path); | |
exit(1); | |
} | |
/* for each s-box */ | |
for (n = 1; n <= t_size; ++n) { | |
/* calculate XDT */ | |
for (i = 0; i < x_size; ++i) { | |
/* calculate S(i) */ | |
is = sbox(n, i); | |
for (j = 0; j < x_size; ++j) { | |
/* calculate S(j) */ | |
js = sbox(n, j); | |
/* calculate differences */ | |
x = i ^ j; | |
y = is ^ js; | |
/* increment table */ | |
xdt[n - 1][x][y]++; | |
} | |
} | |
} | |
/* print tables */ | |
for (n = 0; n < t_size; ++n) { | |
fprintf(fp, "S-Box #%d\n", n + 1); | |
print_tab(x_size, y_size, xdt[n], fp); | |
fprintf(fp, "\n"); | |
} | |
/* calculate best iterative characteristic */ | |
fprintf(fp, "Best 2-round iterative characteristic:\n\n"); | |
fprintf(fp, "Def. Om = (Op, Or, Ot),\n" | |
"\twhere Op, Ot are m-nit numbers and Or = (r_1, r_2),\n" | |
"\twhere r_i = (rIi, rOi),\n" | |
"\twhere rIi and rOi are m/2 bit numbers\n" | |
"\twhere m is the block size.\n\n"); | |
fprintf(fp, "Given Op and Ot, we calculate rIi by\n" | |
"\trI1 = the right half of Op\n" | |
"\trI2 = the left half of Op XOR rO1\n" | |
"\trI2 = the right half of Ot\n" | |
"\trI1 = the left half of Ot XOR rO2.\n\n"); | |
fprintf(fp, "It is well known that p_2 = 1/234 is the best characteristic\n" | |
"\twhere Op = 0x1960000000000000\n" | |
"\tand Ot = 0x0000000019600000\n\n"); | |
fprintf(fp, "With Op and Ot, we set rIi and rOi to:\n" | |
"\trI1 = 0x00000000\n" | |
"\trI2 = 0x19600000\n" | |
"\trO1 = 0x00000000\n" | |
"\trO2 = 0x00000000\n\n"); | |
uint32_t | |
rI1[] = { 0, 0, 0, 0, 0, 0, 0, 0 }, | |
rI2[] = { 1, 9, 6, 0, 0, 0, 0, 0 }, | |
rO1[] = { 0, 0, 0, 0, 0, 0, 0, 0 }, | |
rO2[] = { 0, 0, 0, 0, 0, 0, 0, 0 }; | |
fprintf(fp, "After extension, rI1 and rI2 are the inputs and rO1 and rO2 are the outputs to F-function.\n\n"); | |
uint64_t eI1 = 0, eI2 = 0; | |
uint32_t erI1[8], erI2[8]; | |
for(i = 0; i < 8; ++i) { | |
erI1[i] = (rI1[(i + 7) % 8] % 2) * 32 + rI1[i] * 2 + rI1[(i + 1) % 8] / 8; | |
erI2[i] = (rI2[(i + 7) % 8] % 2) * 32 + rI2[i] * 2 + rI2[(i + 1) % 8] / 8; | |
} | |
for(i = 0; i < 8; ++i) { | |
eI1 = 64 * eI1 + erI1[i]; | |
eI2 = 64 * eI2 + erI2[i]; | |
} | |
double p1 = 1.0f, p2 = 1.0f; | |
fprintf(fp, "Using XDTs, the probability of each tuple, p_1, becomes:\n\n"); | |
fprintf(fp, "\tInput:\n" | |
"\trI1 = 0x%02x%02x%02x%02x%02x%02x%02x%02x\n" | |
"\trI02 = 0x%02x%02x%02x%02x%02x%02x%02x%02x\n\n", | |
erI1[0], erI1[1], erI1[2], erI1[3], erI1[4], erI1[5], erI1[6], erI1[7], | |
erI2[0], erI2[1], erI2[2], erI2[3], erI2[4], erI2[5], erI2[6], erI2[7]); | |
fprintf(fp, "\tOutput:\n"); | |
for(i = 0; i < 8; ++i) { | |
fprintf(fp, "\tS-Box #%d: rI1[%d] = 0x%02x, rO1[%d] = 0x%02x -> XDT[%d][%d] = %d/64\n", | |
i+1, i+1, erI1[i], i+1, rO1[i], erI1[i], rO1[i], xdt[i][erI1[i]][rO1[i]]); | |
} | |
fprintf(fp, "\n\tResult:\n\tp_1 = "); | |
for(i = 0; i < 7; ++i) { | |
fprintf(fp, "%d/64 * ", xdt[i][erI1[i]][rO1[i]]); | |
} | |
fprintf(fp, "%d/64 = ", xdt[7][erI1[7]][rO1[7]]); | |
for(i = 0; i < 8; ++i) { | |
p1 *= (double) xdt[i][erI1[i]][rO1[i]] / (double) 64; | |
} | |
fprintf(fp, "%.6lf\n\n", p1); | |
fprintf(fp, "Again, using XDTs, the probability p_2 becomes:\n\n"); | |
fprintf(fp, "\tInput:\n" | |
"\trI1 = 0x%02x%02x%02x%02x%02x%02x%02x%02x\n" | |
"\trI02 = 0x%02x%02x%02x%02x%02x%02x%02x%02x\n\n", | |
erI1[0], erI1[1], erI1[2], erI1[3], erI1[4], erI1[5], erI1[6], erI1[7], | |
erI2[0], erI2[1], erI2[2], erI2[3], erI2[4], erI2[5], erI2[6], erI2[7]); | |
fprintf(fp, "\tOutput:\n"); | |
for(i = 0; i < 8; ++i) { | |
fprintf(fp, "\tS-Box #%d: rI2[%d] = 0x%02x, rO2[%d] = 0x%02x -> XDT[%d][%d] = %d/64\n", | |
i+1, i+1, erI2[i], i+1, rO2[i], erI2[i], rO2[i], xdt[i][erI2[i]][rO2[i]]); | |
} | |
fprintf(fp, "\n\tResult:\n\tp_2 = "); | |
for(i = 0; i < 7; ++i) { | |
fprintf(fp, "%d/64 * ", xdt[i][erI2[i]][rO2[i]]); | |
} | |
fprintf(fp, "%d/64 = ", xdt[7][erI2[7]][rO2[7]]); | |
for(i = 0; i < 8; ++i) { | |
p2 *= (double) xdt[i][erI2[i]][rO2[i]] / (double) 64; | |
} | |
fprintf(fp, "%.6lf\n\n", p2); | |
fprintf(fp, "The holding probability becomes:\n" | |
"\t p_1 * p_2 = %.6lf * %.6lf\n" | |
"\t = %.6lf\n" | |
"\t ~= 1/234\n\n", | |
p1, p2, p1 * p2); | |
fprintf(fp, "Thus, we have successfully verified the best iterative characteristic of DES to be 1/234.\n"); | |
/* close file handle */ | |
fclose(fp); | |
return 0; | |
} | |
int iexp(int base, unsigned int exp) | |
{ | |
int i, result = 1; | |
for (i = 0; (unsigned) i < exp; i++) | |
result *= base; | |
return result; | |
} | |
int sbox(int n, int x) | |
{ | |
int row, col; | |
/* calculate row and column in sbox */ | |
/* SBOX[b0b5][b1b2b3b4], where b are the binary input */ | |
row = ((x & 1) | ((x & (1 << 5)) >> 4)); | |
col = ((x >> 1) & 0xf); | |
/* select correct sbox */ | |
switch (n) { | |
case 1: return DES_S1[row][col]; | |
case 2: return DES_S2[row][col]; | |
case 3: return DES_S3[row][col]; | |
case 4: return DES_S4[row][col]; | |
case 5: return DES_S5[row][col]; | |
case 6: return DES_S6[row][col]; | |
case 7: return DES_S7[row][col]; | |
case 8: return DES_S8[row][col]; | |
default: | |
fprintf(stderr, "invalid sbox #%d", n); | |
exit(1); | |
} | |
} | |
void print_tab(int x_size, int y_size, int tab[][y_size], FILE *fp) | |
{ | |
int i, j; | |
fprintf(fp, " "); | |
for (i = 0; i < y_size; i++) { | |
fprintf(fp, "x%02x ", i); | |
} | |
fprintf(fp, "\n"); | |
for (i = 0; i < x_size; ++i) { | |
for (j = 0; j < y_size; j++) { | |
if (j == 0) fprintf(fp, "x%02x ", i); | |
fprintf(fp, "%3d ", tab[i][j]); | |
} | |
fprintf(fp, "\n"); | |
} | |
} |