Кафедра: АСОИиУ

Лабораторная работа

«Алгоритм формирования ключей в процессе функционирования 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 половины C₀ и D₀. Каждая половина содержит 28 бит.

 

C₀:

0000111111111111111100000000

D₀:

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: 0001111111111111111000000000 D1: 1011101011001011000011100110
1	C2: 0011111111111111110000000000 D2: 0111010110010110000111001101
2	C3: 1111111111111111000000000011 D3: 1101011001011000011100110111
2	C4: 1111111111111100000000001111 D4: 0101100101100001110011011101
2	C5: 1111111111110000000000111111 D5: 0110010110000111001101110101
2	C6: 1111111111000000000011111111 D6: 1001011000011100110111010110
2	C7: 1111111100000000001111111111 D7: 0101100001110011011101011001
2	C8: 1111110000000000111111111111 D8: 0110000111001101110101100101
1	C9: 1111100000000001111111111111 D9: 1100001110011011101011001011
2	C10: 1110000000000111111111111111 D10: 0000111001101110101100101100
2	C11: 1000000000011111111111111110 D11: 0011100110111010110010110000
2	C12: 0000000001111111111111111000 D12: 1110011011101011001011000011
2	C13: 0000000111111111111111100000 D13: 1001101110101100101100001110
2	C14: 0000011111111111111110000000 D14: 0110111010110010110000111001
2	C15: 0001111111111111111000000000 D15: 1011101011001011000011100110
1	C16: 0011111111111111110000000000 D16: 0111010110010110000111001101

 

4 шаг. Перестановка битов ключа с использованием таблицы PC1

До финальной перестановки битов ключей, необходимо слияние каждой пары данных. После того, как для каждого битового блока C_nD_n, где 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₁: 111001111101001101110010001100110001010011011101

K₂: 111001101101001101110011111011100011011001010110

K₃: 101011111101001111011011001111011110001011101010

K₄: 001111100101001111011011011101001101110001000011

K₅: 001111100101100111011001100011101010010001111110

K₆: 000111110110100111011101101010011111111011000000

K₇: 000111100110110110011101011111001100011000110011

K₈: 010111100010110110101101100111110100110001001110

K₉: 010110111010110110101101010001010001111010110110

K₁₀: 110110001010110010101111110110010010100011111001

K₁₁: 111100001010111010100110001000111101101000011101

K₁₂: 111100011011111000100110000101110011010010110110

K₁₃: 111000011011011001110110111010010000100011100101

K₁₄: 111001001101011001110110010001101110101010011111

K₁₅: 111001111101001101110010001100110001010011011101

K₁₆: 111001101101001101110011111011100011011001010110

Исходный код

#include

#include

#include

#include

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 (« Vvedite key »);

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 (« Key neveren »);

}

for (i=0; i

A[i]=str[i];}

for (i=0; i

B[i]=(int) A[i];

printf («%d », B[i]);

}

for (i=0; 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 (« »);

}

printf (« »);

k=0;

for (i=0; 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 (« »);

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 (« »);

for (i=0; i<28; i++) {

printf («%d», Z[i]);}

printf (« »);

for (i=0; i<28; i++) {

printf («%d», R[i]);}

printf (« »);

printf (« »);

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 (« »);*/

}

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 (« »);

}

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 (« »);

}

}

 

Пример работы программы