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

На тему:

«Алгоритм криптографического преобразования в режиме простой замены»

Москва 2009

Содержание

Техническое задание

Описание алгоритма режима простой замены

Схема реализации режима простой замены

Алгоритм

Листинг

Пример выполнения

Литература

Техническое задание

1. Реализовать алгоритм криптографического преобразования в режиме простой замены на языке программирования

2. Провести тест программы.

Описание алгоритма режима простой замены

Для реализации алгоритма шифрования данных в режиме простой замены используется только часть блоков общей криптосистемы (рис. 3.11). Обозначения на схеме:

N₁, N₂-32-разрядные накопители;

СM₁- 32-разрядный сумматор по модулю 2³² (?);

СМ²-32-разрядный сумматор по модулю 2 (?);

R-32-разрядный регистр циклического сдвига;

КЗУ - ключевое запоминающее устройство на 256 бит, состоящее из восьми 32-разрядных накопителей Х₀, X₁, Х₂, ..., Х₇;

Шифрование открытых данных в режиме простой замены

Рис. 3.11. Схема реализации режима простой замены

Открытые данные, подлежащие зашифрованию, разбивают на 64-разрядные блоки Т₀. Процедура зашифрования 64-разрядного блока Т₀ в режиме простой замены включает 32 цикла (j = 1... 32). В ключевое запоминающее устройство вводят 256 бит ключа К в виде восьми 32-разрядных подключей (чисел) Ki:

К= K₇K₆K₅K₄K₃K₂K₁K₀.

Последовательность битов блока

Т₀= (а₁(0), а₂(0), ..., а₃₁(0), а₃₂(0), b₁(0), b₂(0), ..., b₃₁(0), b₃₂(0))

разбивают на две последовательности по 32 бита: b(0) а(0), где b(0)-левые или старшие биты, а(0)- правые или младшие биты.

Эти последовательности вводят в накопители N₁ и N₂ перед началом первого цикла зашифрования. В результате начальное заполнение накопителя n₁

а(0) = (а₃₂(0), а₃₁(0), ..., а₂(0), a₁(0)),

32, 31, ... 2, 1 ?номер разряда N₁

начальное заполнение накопителя N₂

b(0) = (b₃₂(0),b₃₁(0),...,b₂(0),b₁(0)).

32, 31, ... 2, 1 ? номер разряда N₂

Первый цикл (j = 1) процедуры зашифрования 64-разрядного блока открытых данных можно описать уравнениями:

Здесь а (1)-заполнение N₁ после 1-го цикла зашифрования; b(1)-заполнение N₂ после 1-го цикла зашифрования; f-функция шифрования.

Аргументом функции f является сумма по модулю 2³² числа а(0) (начального заполнения накопителя N₁) и числа К₀-подключа, считываемого из накопителя Х₀ КЗУ. Каждое из этих чисел равно 32 битам.

Функция f включает две операции над полученной 32-разрядной суммой (a(0)?K₀).

Первая операция называется подстановкой (заменой) и выполняется блоком подстановки S. Блок подстановки S состоит из восьми узлов замены (S-блоков замены) S₁, S₂, ...,S₈ с памятью 64 бит каждый. Поступающий из CM₁ на блок подстановки S₃₂-разрядный вектор разбивают на восемь последовательно идущих 4-разрядных векторов, каждый из которых преобразуется в четырехразрядный вектор соответствующим узлом замены. Каждый узел замены можно представить в виде таблицы-перестановки шестнадцати четырехразрядных двоичных чисел в диапазоне 0000...1111. Входной вектор указывает адрес строки в таблице, а число в этой строке является выходным вектором. Затем четырехразрядные выходные векторы последовательно объединяют в 32-разрядный вектор. Узлы замены (таблицы-перестановки), представляют собой ключевые элементы, которые являются общими для сети ЭВМ и редко изменяются. Эти узлы замены должны сохраняться в секрете.

Вторая операция - циклический сдвиг влево (на 11 разрядов) 32-разрядного вектора, полученного с выхода блока подстановки S. Циклический сдвиг выполняется регистром сдвига R.

Далее результат работы функции шифрования f суммируют поразрядно па модулю 2 в сумматоре СМ₂ с 32-разрядным начальным заполнением b(0) накопителя N₂. Затем полученный на выходе СМ₂ результат (значение а(1)) записывают в накопитель N₁, а старое значение N₁ (значение а(0)) переписывают в накопитель N₂ (значение b(1) = а(0)). Первый цикл завершен.

Последующие циклы осуществляются аналогично, при этом во втором цикле из КЗУ считывают заполнение X₁-подключ K₁, в третьем цикле - подключ К₂ и т.д., в восьмом цикле - подключ К₇. В циклах с 9-го по 16-й, а также в циклах с 17-го по 24-й подключи из КЗУ считываются в том же порядке: К₀, К₁, К₂,.... К₆, К₇. В последних восьми циклах с 25-го по 32-й порядок считывания подключей из КЗУ обратный: К₇, К₆, ..., К₂, К₁, К₀. Таким образом, при зашифровании в 32 циклах осуществляется следующий порядок выборки из КЗУ подключей:

K₀, K₁, K₂, К₃, К₄, K₅, K₆, К₇, К₀, К₁, К₂, К₃, К₄, K₅, K₆, K₇,

K₀, K₁, К₂, К₃, К₄, K₅, К₆, К₇, K₇, K₆, K₅, К₄, К₃, К₂, K₁, K₀.

В 32-м цикле результат из сумматора СМ₂ вводится в накопитель N₂, а в накопителе N₁ сохраняется прежнее заполнение. Полученные после 32-го цикла зашифрования заполнения накопителей N₁ и N₂ являются блоком зашифрованных данных Т_ш, соответствующим блоку открытых данных Т₀.

Уравнения зашифрования в режиме простой замены имеют вид:

где a(j) = (a₃₂ (i), a₃₁(j),...., а₁( j ))-заполнение N₁ после j-гo цикла зашифрования; b(j) = (b₃₂(j), b₃₁(j), …,b₁(j))-заполнение N₂ после j- гo цикла зашифрования, j = 1... 32.

Блок зашифрованных данных Тш (64 разряда) выводится из накопителей N_l N₂ в следующем порядке: из разрядов 1...32 накопителя N₁, затем из разрядов 1... 32 накопителя N₂, т.е. начиная c младших-разрядов:

Тш= (а₁ (32), а₂(32), ..., а₃₂(32), b₁(32), b₂(32), .... b₃₂(32)).

Остальные блоки открытых данных зашифровываются в режиме простой замены аналогично.

Расшифрование в режиме простой замены

Криптосхема, реализующая алгоритм расшифрования в режиме простой замены, имеет тот же вид, что и при зашифровании (см. рис. 3.11).

В КЗУ вводят 256 бит ключа, на котором осуществлялось зашифрование. Зашифрованные данные, подлежащие расшифрованию, разбиты на блоки Тш по 64 бита в каждом. Ввод любого блока

Тш = (a₁ (32), а₂(32),.... а₃₂(32), b₁(32), b₂(32),.... b₃₂(32))

в накопители N₁ и N₂ производят так, чтобы начальное значение накопителя N₁ имело вид

(а₃₂(32),а₃₁(32), ...,а₂(32),а₁(32)),

32, 31, ..., 2, 1 ? номер разряда N₁

а начальное заполнение накопителя N₂ - вид

(b₃₂(32)b₃₁(32), ..., b₂(32)b₁(32)).

32 31, ..., 2, 1 ? номер разряда N₂

Расшифрование осуществляется по тому же алгоритму, что и зашифрование, с тем изменением, что заполнения накопителей Х₀, X_l ,..., Х₇ считываются из КЗУ в циклах расшифрования в следующем порядке:

K₀, K₁, К₂, К₃, К₄, K₅, K₆, К₇, К₇, K₆, K₅, K₄, К₃, К₂, K₁, K₀,

K₇, K₆, K₅, К₄, K₃, К₂, K₁, K₀, K₇, K₆, K₅, K₄, K₃, K₂, K₁, K₀.

Уравнения расшифрования имеют вид:

Полученные после 32 циклов работы заполнения накопителей N₁ и N₂ образуют блок открытых данных

Т₀ = (a₁(0), а₂(0), .... а₃₂(0), b₁(0), b₂(0), ..., b₃₂(0)),

соответствующий блоку зашифрованных данных Тш. При этом состояние накопителя N₁

(а₃₂(0),а₃₁(0),..,а₂(0),а₁(0)),

32, 31, ..., 2, 1 ? номер разряда N₁

состояние накопителя N₂

(b₃₂(0)b₃₁(0), ..., b₂(0)b₁(0)).

32, 31, ..., 2, 1 ? номер разряда N₂

Аналогично расшифровываются остальные блоки зашифрованных данных.

Если алгоритм зашифрования в режиме простой замены 64-битового блока Т₀ обозначить через А, то

А (Т₀) = А (а(0), b(0)) = (а (32), b (32)) =Т_Ш.

Алгоритм

На входе основного шага определяется 64-битный блок данных N = (N₁, N₂), где N₁ - младшая 32-битовая часть, а N₂ - старшая 32-битовая часть. Обе части рассматриваются как отдельные 32-битовые числа. На вход основного шага также поступает один из восьми элементов ключа (какой именно, будет рассказано далее). 32-битовый элемент ключа обозначается за X. Далее производятся следующие действия:

1. S = N₁ + X (mod 2³²).

2. Число S разбивается на 8 частей: S₀,S₁,S₂,S₃, S₄,S₅,S₆,S₇ по 4 бита каждая, где S₀ - младшая, а S₇ - старшая части числа S.

3. Для всех i от 0 до 7: S_i = T(i, S_i), где T(a, b) означает ячейку таблицы замен с номером строки a и номером столбца b (счет с нуля).

4. Новое число S, полученное на предыдущем шаге циклически сдвигается в сторону старших разрядов на 11 бит.

5. S = S xor N₂, где xor - операция исключающего или.

6. N₂ = N₁.

7. N₁ = S.

Как результат основного шага криптопреобразования возвращается блок данных N = (N₁, N₂), где N₂ равно исходному N₁, а N₁ - результат преобразований основного шага.

Берем блок данных N и вызываем последовательно процедуру основного шага криптопреобразования со следующими ключами:

· Для цикла зашифрования (32-З): X₀,X₁,X₂,X₃,X₄, X₅,X₆,X₇,X₀,X₁,X₂,X₃, X₄,X₅,X₆,X₇,X₀,X₁,X₂, X₃,X₄,X₅,X₆,X₇,X₇,X₆, X₅,X₄,X₃,X₂,X₁,X₀.

· Для цикла расшифрования (32-Р): X₀,X₁,X₂,X₃, X₄,X₅,X₆,X₇X₇,X₆,X₅, X₄,X₃,X₂,X₁,X₀X₇,X₆, X₅,X₄,X₃,X₂,X₁,X₀X₇, X₆,X₅,X₄,X₃,X₂,X₁,X₀.

Листинг

#include <stdio.h>

typedef unsigned long u4;

typedef unsigned char byte;

typedef struct {

u4 k[8];

/* Constant s-boxes -- set up in gost_init(). */

char k87[256],k65[256],k43[256],k21[256];

} gost_ctx;

/* Note: encrypt and decrypt expect full blocks--padding blocks is

caller's responsibility. All bulk encryption is done in

ECB mode by these calls. Other modes may be added easily

enough. */

void gost_enc(gost_ctx *, u4 *, int);

void gost_dec(gost_ctx *, u4 *, int);

void gost_key(gost_ctx *, u4 *);

void gost_init(gost_ctx *);

void gost_destroy(gost_ctx *);

#ifdef __alpha /* Any other 64-bit machines? */

typedef unsigned int word32;

#else

typedef unsigned long word32;

#endif

kboxinit(gost_ctx *c)

{int i;

byte k8[16] = {14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6,

12, 5, 9, 0, 7 };

byte k7[16] = {15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2,

13, 12, 0, 5, 10 };

byte k6[16] = {10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12,

7, 11, 4, 2, 8 };

byte k5[16] = { 7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8,

5, 11, 12, 4, 15 };

byte k4[16] = { 2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3,

15, 13, 0, 14, 9 };

byte k3[16] = {12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3,

4, 14, 7, 5, 11 };

byte k2[16] = { 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9,

7, 5, 10, 6, 1 };

byte k1[16] = {13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3,

14, 5, 0, 12, 7 };

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

c->k87[i] = k8[i >> 4] << 4 | k7[i & 15];

c->k65[i] = k6[i >> 4] << 4 | k5[i & 15];

c->k43[i] = k4[i >> 4] << 4 | k3[i & 15];

c->k21[i] = k2[i >> 4] << 4 | k1[i & 15];}}

static word32

f(gost_ctx *c,word32 x)

{x = c->k87[x>>24 & 255] << 24 | c->k65[x>>16 & 255] << 16 |

c->k43[x>> 8 & 255] << 8 | c->k21[x & 255];

/* Rotate left 11 bits */

return x<<11 | x>>(32-11);}

void gostcrypt(gost_ctx *c, word32 *d){

register word32 n1, n2; /* As named in the GOST */

n1 = d[0];

n2 = d[1];

/* Instead of swapping halves, swap names each round */

n2 ^= f(c,n1+c->k[0]); n1 ^= f(c,n2+c->k[1]);

n2 ^= f(c,n1+c->k[2]); n1 ^= f(c,n2+c->k[3]);

n2 ^= f(c,n1+c->k[4]); n1 ^= f(c,n2+c->k[5]);

n2 ^= f(c,n1+c->k[6]); n1 ^= f(c,n2+c->k[7]);

n2 ^= f(c,n1+c->k[0]); n1 ^= f(c,n2+c->k[1]);

n2 ^= f(c,n1+c->k[2]); n1 ^= f(c,n2+c->k[3]);

n2 ^= f(c,n1+c->k[4]); n1 ^= f(c,n2+c->k[5]);

n2 ^= f(c,n1+c->k[6]); n1 ^= f(c,n2+c->k[7]);

n2 ^= f(c,n1+c->k[0]); n1 ^= f(c,n2+c->k[1]);

n2 ^= f(c,n1+c->k[2]); n1 ^= f(c,n2+c->k[3]);

n2 ^= f(c,n1+c->k[4]); n1 ^= f(c,n2+c->k[5]);

n2 ^= f(c,n1+c->k[6]); n1 ^= f(c,n2+c->k[7]);

n2 ^= f(c,n1+c->k[7]); n1 ^= f(c,n2+c->k[6]);

n2 ^= f(c,n1+c->k[5]); n1 ^= f(c,n2+c->k[4]);

n2 ^= f(c,n1+c->k[3]); n1 ^= f(c,n2+c->k[2]);

n2 ^= f(c,n1+c->k[1]); n1 ^= f(c,n2+c->k[0]);

d[0] = n2; d[1] = n1;}

void

gostdecrypt(gost_ctx *c, u4 *d){

register word32 n1, n2; /* As named in the GOST */

n1 = d[0]; n2 = d[1];

n2 ^= f(c,n1+c->k[0]); n1 ^= f(c,n2+c->k[1]);

n2 ^= f(c,n1+c->k[2]); n1 ^= f(c,n2+c->k[3]);

n2 ^= f(c,n1+c->k[4]); n1 ^= f(c,n2+c->k[5]);

n2 ^= f(c,n1+c->k[6]); n1 ^= f(c,n2+c->k[7]);

n2 ^= f(c,n1+c->k[7]); n1 ^= f(c,n2+c->k[6]);

n2 ^= f(c,n1+c->k[5]); n1 ^= f(c,n2+c->k[4]);

n2 ^= f(c,n1+c->k[3]); n1 ^= f(c,n2+c->k[2]);

n2 ^= f(c,n1+c->k[1]); n1 ^= f(c,n2+c->k[0]);

n2 ^= f(c,n1+c->k[7]); n1 ^= f(c,n2+c->k[6]);

n2 ^= f(c,n1+c->k[5]); n1 ^= f(c,n2+c->k[4]);

n2 ^= f(c,n1+c->k[3]); n1 ^= f(c,n2+c->k[2]);

n2 ^= f(c,n1+c->k[1]); n1 ^= f(c,n2+c->k[0]);

n2 ^= f(c,n1+c->k[7]); n1 ^= f(c,n2+c->k[6]);

n2 ^= f(c,n1+c->k[5]); n1 ^= f(c,n2+c->k[4]);

n2 ^= f(c,n1+c->k[3]); n1 ^= f(c,n2+c->k[2]);

n2 ^= f(c,n1+c->k[1]); n1 ^= f(c,n2+c->k[0]);

d[0] = n2; d[1] = n1;}

void gost_enc(gost_ctx *c, u4 *d, int blocks){

int i;

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

gostcrypt(c,d);

d+=2;}}

void gost_dec(gost_ctx *c, u4 *d, int blocks){

int i;

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

gostdecrypt(c,d);

d+=2;}}

void gost_key(gost_ctx *c, u4 *k){

int i;

for(i=0;i<8;i++) c->k[i]=k[i];}

void gost_init(gost_ctx *c){

kboxinit(c);}

void gost_destroy(gost_ctx *c){

int i;

for(i=0;i<8;i++) c->k[i]=0;}

int main(){

gost_ctx gc;

u4 k[8],data[10];

int i;

/* Initialize GOST context. */

gost_init(&gc);

/* Prepare key--a simple key should be OK, with this many

rounds! */

for(i=0;i<8;i++) k[i] = i;

gost_key(&gc,k);

/* Try some test vectors. */

data[0] = 0; data[1] = 0;

gostcrypt(&gc,data);

printf("Enc of zero vector: %08lx %08lx\n",data[0],data[1]);

gostcrypt(&gc,data);

printf("Enc of above: %08lx %08lx\n",data[0],data[1]);

data[0] = 0xffffffff; data[1] = 0xffffffff;

gostcrypt(&gc,data);

printf("Enc of ones vector: %08lx %08lx\n",data[0],data[1]);

gostcrypt(&gc,data);

printf("Enc of above: %08lx %08lx\n",data[0],data[1]);

/* Init data */

for(i=0;i<10;i++) data[i]=i;

/* Encrypt data as 5 blocks. */

gost_enc(&gc,data,5);

/* Display encrypted data. */

for(i=0;i<10;i+=2) printf("Block %02d = %08lx %08lx\n",

i/2,data[i],data[i+1]);

/* Decrypt in different sized chunks. */

gost_dec(&gc,data,1);

gost_dec(&gc,data+2,4);

printf("\n");

/* Display decrypted data. */

for(i=0;i<10;i+=2) printf("Block %02d = %08lx %08lx\n",

i/2,data[i],data[i+1]);

gost_destroy(&gc);

return 0;}

Пример выполнения

Литература

1. В.В. Подбельский, С.С. Фомин «Язык программирования Си»