Кафедра: АСОИиУ
Лабораторная работа
«Алгоритм формирования ключей в процессе функционирования
DES
»
по дисциплине
«Методы и средства защиты информации»
Москва 2009 г.
Оглавление
Техническое задание. 3
Алгоритм формирования ключей в процессе функционирования DES. 3
Работа алгоритма. 4
1 шаг. Перестановки битов ключа с использованием таблицы перестановок. 5
2 шаг. Разбиение ключа. 6
3 шаг. Создание 16-ти подключей путем сдвига. 7
4 шаг. Перестановка битов ключа с использованием таблицы PC1. 8
Исходный код. 9
Пример работы программы.. 15
Техническое задание
1. Реализовать алгоритм формирования ключей в процессе функционирования DES на языке программирования C++.
2. Провести тест программы.
Алгоритм формирования ключей в процессе функционирования
DES
Формирование ключей – алгоритм, позволяющий получить по относительно короткому ключу шифрования последовательность раундовых ключей.
Входные данные: Ключ состоит из 8 символов или 8 байт. Соответственно ключ имеет размер 64 байта. Но размер ключа используется только для записи (для организации данных). Фактически, каждый 8 бит отбрасывается и эффективный размер ключа – 56 бит.
Работа алгоритма
1 шаг. Перестановки битов ключа с использованием таблицы перестановок.
Для примера введем:
olga1234
Заданный ключ в двоичном представлении:
0110111101101100011001110110000100110001001100100011001100110100
В начале над ключом шифра выполняется операция B, которая сводится к выбору определенных бит и их перестановке, как это показано в таблицей. Причем, первые четыре строки определяют, как выбираются биты последовательности C(0) (первым битом C(0) будет бит 57 бит ключа шифра, затем бит 49 и т.д., а последними битами биты 44 и 36 ключа шифра), а следующие четыре строки – как выбираются биты последовательности D(0) (т.е. последовательность D(0) будем состоять из битов 63,55,…, 12, 4 ключа шифра).
| 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 |
В результате перестановки ключ будет выглядеть так:
00001111111111111111000000000101110101100101100001110011
2 шаг. Разбиение ключа
На этом шаге осуществляется разбиение ключа на 2 половины C0
и D0
. Каждая половина содержит 28 бит.
C0
:
0000111111111111111100000000
D0
:
0101110101100101100001110011
3 шаг. Создание 16-ти подключей путем сдвига
После определения C(0) и D(0) рекурсивно определяются C(i) и D(i), i=1,2,…, 16. Для этого применяются операции сдвига влево на один или два бита в зависимости от номера шага итерации, как это показано в таблице «Функция сдвига Si». Операции сдвига выполняются для последовательностей C(i) и D(i) независимо. Например, последовательность C(3) получается, посредством сдвига влево на две позиции последовательности C(2), а последовательность D(3) – посредством сдвига влево на две позиции последовательности D(2). Следует иметь в виду, что выполняется циклический сдвиг влево. Например, единичный сдвиг влево последовательности C(i) приведет к тому, что первый бит C(i) станет последним и последовательность бит будет следующая: 2,3,…, 28,1.
Таблица «Функция сдвига Si»
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 2 |
| 5 | 2 |
| 6 | 2 |
| 7 | 2 |
| 8 | 2 |
| 9 | 1 |
| 10 | 2 |
| 11 | 2 |
| 12 | 2 |
| 13 | 2 |
| 14 | 2 |
| 15 | 2 |
| 16 | 1 |
В результате сдвига получаем следующие пары
| Количество сдвигов | Созданные пары |
| 1 | C1
D1
|
| 1 | C2
D2
|
| 2 | C3
D3
|
| 2 | C4
D4
|
| 2 | C5
D5
|
| 2 | C6
D6
|
| 2 | C7
D7
|
| 2 | C8
D8
|
| 1 | C9
D9
|
| 2 | C10
D10
|
| 2 | C11
D11
|
| 2 | C12
D12
|
| 2 | C13
D13
|
| 2 | C14
D14
|
| 2 | C15
D15
|
| 1 | C16
D16
|
4 шаг. Перестановка битов ключа с использованием таблицы PC1
До финальной перестановки битов ключей, необходимо слияние каждой пары данных. После того, как для каждого битового блока Cn
Dn
, где 1<=n
<=16 осуществиться соответствующая перестановка по таблице (см ниже), формируя ключи. Только 48 бит каждой объединенной пары сохраняется в перестановленном ключе.
| 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 |
Все подключи:
K
1
: 111001111101001101110010001100110001010011011101
K
2
: 111001101101001101110011111011100011011001010110
K
3
: 101011111101001111011011001111011110001011101010
K
4
: 001111100101001111011011011101001101110001000011
K
5
: 001111100101100111011001100011101010010001111110
K
6
: 000111110110100111011101101010011111111011000000
K
7
: 000111100110110110011101011111001100011000110011
K
8
: 010111100010110110101101100111110100110001001110
K
9
: 010110111010110110101101010001010001111010110110
K
10
: 110110001010110010101111110110010010100011111001
K
11
: 111100001010111010100110001000111101101000011101
K
12
: 111100011011111000100110000101110011010010110110
K
13
: 111000011011011001110110111010010000100011100101
K
14
: 111001001101011001110110010001101110101010011111
K
15
: 111001111101001101110010001100110001010011011101
K
16
: 111001101101001101110011111011100011011001010110
Исходный код
#include <stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
int main (int argc, char *argv[]) {
int
i, b, y, r, j, v, p, m, l, f, u, k, a, s, q, D[100] [100], Y[100] [100], U[100] [100], X[1000] [1000], E[100] [100], G[100] [100], W[100] [100], P[100] [1 $
double z;
int key[16]={1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1};
char A[1000];
char B[200];
char N[200];
char T[200];
char C[1000];
char Z[43];
char R[43];
char L[43];
char *str2;
char *str;
char *str1;
char *str3;
char *str4;
char *str5;
char d[100];
printf («nVvedite keyn»);
str=(char *) (malloc(1000));
for (i=0; i<1000; i++) {
scanf («%c»,&str[i]);
if (str[i]==(char) 10) {
m=i;
break;
}
if (str[i]==(char) 32) {
str[i]=157;}
}
if (m!=8) {
printf («nKey neverenn»);
}
for (i=0; i<m; i++) {
A[i]=str[i];}
for (i=0; i<m; i++) {
B[i]=(int) A[i];
printf («%dn», B[i]);
}
for (i=0; i<m; i++) {
f=B[i];
for (j=0; j<8; j++) {
if (f<1) {
X[j] [i]=0;
goto Metka;}
s=f/2;
/*printf («%d», s);*/
z=fmod (f, 2);
if (z!=0)
X[j] [i]=1;
else
X[j] [i]=0;
f=s;
Metka:printf («%d», X[j] [i]);}
printf («n»);
}
printf («n»);
k=0;
for (i=0; i<m; i++) {
k=i*8;
for (j=0; j<8; j++) {
N [j+k]=X [8-j-1] [i];
}
}
for (i=0; i<64; i++) {
printf («%d», N[i]);}
printf («n»);
C[0]=N[57]; C[1]=N[49]; C[2]=N[41]; C[3]=N[33]; C[4]=N[25]; C[5]=N[17]; C[6]=N[9]; C[7]=N[1];
C[8]=N[58]; C[9]=N[50]; C[10]=N[42]; C[11]=N[34]; C[12]=N[26]; C[13]=N[18]; C[14]=N[10];
C[15]=N[2]; C[16]=N[59]; C[17]=N[51]; C[18]=N[43]; C[19]=N[35]; C[20]=N[27]; C[21]=N[19];
C[22]=N[11]; C[23]=N[3]; C[24]=N[60]; C[25]=N[52]; C[26]=N[44]; C[27]=N[36]; C[28]=N[63];
C[29]=N[55]; C[30]=N[47]; C[31]=N[39]; C[32]=N[31]; C[33]=N[23]; C[34]=N[15]; C[35]=N[7];
C[36]=N[62]; C[37]=N[54]; C[38]=N[46]; C[39]=N[38]; C[40]=N[30]; C[41]=N[22]; C[42]=N[14];
C[43]=N[6]; C[44]=N[61]; C[45]=N[53]; C[46]=N[45]; C[47]=N[37]; C[48]=N[29]; C[49]=N[21];
C[50]=N[13]; C[51]=N[5]; C[52]=N[28]; C[53]=N[20]; C[54]=N[12]; C[55]=N[4];
for (i=0; i<56; i++) {
printf («%d», C[i]);
}
for (i=0; i<56; i++) {
if (i<28) {
Z[i]=C[i];}
if (i>27) {
R [i-28]=C[i];}
}
printf («n»);
for (i=0; i<28; i++) {
printf («%d», Z[i]);}
printf («n»);
for (i=0; i<28; i++) {
printf («%d», R[i]);}
printf («n»);
printf («n»);
for (j=0; j<16; j++) {
v=key[j];
for (i=0; i<28; i++) {
if (v==2) {
Y[26] [j]=Z[0];
Y[27] [j]=Z[1];
U[26] [j]=R[0];
U[27] [j]=R[1];
}
if (v==1) {
Y[27] [j]=Z[1];
U[27] [j]=R[1];
}
if (i<(28-v)) {
Y[i] [j]=Z [i+v];
U[i] [j]=R [i+v];}
Z[i]=Y[i] [j];
R[i]=U[i] [j];
/*printf («%d», U[i] [j]);*/
}
/*printf («n»);*/
}
for (j=0; j<16; j++) {
for (i=0; i<56; i++) {
if (i<28) {
W[i] [j]=Y[i] [j];}
if (i>27) {
W[i] [j]=U [i-28] [j];}
printf («%d», W[i] [j]);
}
printf («n»);
}
for (j=0; j<16; j++) {
P[0] [j]=W[14] [j]; P[1] [j]=W[17] [j]; P[2] [j]=W[11] [j]; P[3] [j]=W[24] [j]; P[4] [j]=W[1] [j]; P[5] [j]=W[5] [j];
P[6] [j]=W[3] [j]; P[7] [j]=W[28] [j]; P[8] [j]=W[15] [j]; P[9] [j]=W[6] [j]; P[10] [j]=W[21] [j]; P[11] [j]=W[10] [j];
P[12] [j]=W[23] [j]; P[13] [j]=W[19] [j]; P[14] [j]=W[12] [j]; P[15] [j]=W[4] [j]; P[16] [j]=W[26] [j]; P[17] [j]=W[8] [j];
P[18] [j]=W[16] [j]; P[19] [j]=W[7] [j]; P[20] [j]=W[27] [j]; P[21] [j]=W[20] [j]; P[22] [j]=W[13] [j]; P[23] [j]=W[2] [j];
P[24] [j]=W[41] [j]; P[25] [j]=W[52] [j]; P[26] [j]=W[31] [j]; P[27] [j]=W[37] [j]; P[28] [j]=W[47] [j]; P[29] [j]=W[55] [j];
P[30] [j]=W[30] [j]; P[31] [j]=W[40] [j]; P[32] [j]=W[51] [j]; P[33] [j]=W[45] [j]; P[34] [j]=W[33] [j]; P[35] [j]=W[48] [j];
P[36] [j]=W[44] [j]; P[37] [j]=W[49] [j]; P[38] [j]=W[39] [j]; P[39] [j]=W[56] [j]; P[40] [j]=W[34] [j]; P[41] [j]=W[53] [j];
P[42] [j]=W[46] [j]; P[43] [j]=W[42] [j]; P[44] [j]=W[50] [j]; P[45] [j]=W[36] [j]; P[46] [j]=W[29] [j]; P[47] [j]=W[32] [j];
}
for (j=0; j<16; j++) {
for (i=0; i<48; i++) {
printf («%d», P[i] [j]);
}
printf («n»);
}
}
Пример работы программы