Файл: ответы.doc

Матрица путей m2.

Матрица путей m3.

2. Общая схема симметричной криптосистемы. Алгоритм построения цепочек.

Симметричные криптосистемы. Функции криптосистем

Все недостатки непосредственного применения криптоалгоритмов устраняются в криптосистемах. Криптосистема – это завершенная комплексная модель, способная производить двусторонние криптопреобразования над данными произвольного объема и подтверждать время отправки сообщения, обладающая механизмом преобразования паролей и ключей и системой транспортного кодирования. Таким образом, криптосистема выполняет три основные функции:

усиление защищенности данных,

облегчение работы с криптоалгоритмом со стороны человека

обеспечение совместимости потока данных с другим программным обеспечением.

Конкретная программная реализация криптосистемы называется криптопакетом.

Общая схема симметричной криптосистемы

Алгоритмы создания цепочек

Первая задача, с которой мы столкнемся при шифровании данных криптоалгоритмом – это данные с длиной, неравной длине 1 блока криптоалгоритма. Эта ситуация будет иметь место практически всегда.

Первый вопрос:

– Что можно сделать, если мы хотим зашифровать 24 байта текста, если используется криптоалгоритм с длиной блока 8 байт? – Последовательно зашифровать три раза по 8 байт и сложить их в выходной файл так, как они лежали в исходном. – А если данных много и некоторые блоки по 8 байт повторяются, это значит, что в выходном файле эти же блоки будут зашифрованы одинаково - это очень плохо.

Второй вопрос :

– А что если данных не 24, а 21 байт.

Не шифровать последние 5 байт или чем-то заполнять еще 3 байта, – а потом при дешифровании их выкидывать. – Первый вариант вообще никуда не годится, а второй применяется, но чем заполнять?

Для решения этих проблем и были введены в криптосистемы алгоритмы создания цепочек (англ. chaining modes). Самый простой метод мы уже в принципе описали. Это метод ECB (Electronic Code Book). Шифруемый файл временно разделяется на блоки, равные блокам алгоритма, каждый из них шифруется независимо, а затем из зашифрованных пакетов данных компонуется в той же последовательности файл, который отныне надежно защищен криптоалгоритмом. Название алгоритм получил из-за того, что в силу своей простоты он широко применялся в простых портативных устройствах для шифрования – электронных шифрокнижках. Схема данного метода приведена на рис.1.

Рис.1.

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

Указанным выше недостатком этой схемы является то, что при повторе в исходном тексте одинаковых символов в течение более, чем 2*N байт (где N – размер блока криптоалгоритма), в выходном файле будут присутствовать одинаковые зашифрованные блоки. Поэтому, для более "мощной" защиты больших пакетов информации с помощью блочных шифров применяются несколько обратимых схем "создания цепочек". Все они почти равнозначны по криптостойкости, каждая имеет некоторые преимущества и недостатки, зависящие от вида исходного текста. Все схемы создания цепочек основаны на идее зависимости результирующего зашифровываемого блока от предыдущих, либо от позиции его в исходном файле. Это достигается с помощью блока "памяти" – пакета информации длины, равной длине блока алгоритма. Блок памяти (к нему применяют термин IV – англ. Initial Vector) вычисляется по определенному принципу из всех прошедших шифрование блоков, а затем накладывается с помощью какой-либо обратимой функции (обычно XOR) на обрабатываемый текст на одной из стадий шифрования. В процессе раскодирования на приемной стороне операция создания IV повторяется на основе принятого и расшифрованного текста, вследствие чего алгоритмы создания цепочек полностью обратимы.

Два наиболее распространенных алгоритма создания цепочек – CBC и CFB. Их структура приведена на рис.2 и рис.3. Метод CBC получил название от английской аббревиатуры Cipher Block Chaining – объединение в цепочку блоков шифра, а метод CFB – от Cipher FeedBack – обратная связь по шифроблоку.

Рис.2.

Рис.3.

Еще один метод OFB (англ. Output FeedBack – обратная связь по выходу) имеет несколько иную структуру (она изображена на рис.4.) : в нем значение накладываемое на шифруемый блок не зависит от предыдущих блоков, а только от позиции шифруемого блока (в этом смысле он полностью соответствует скремблерам), и из-за этого он не распространяет помехи на последующие блоки. Очевидно, что все алгоритмы создания цепочек однозначно восстановимы. Практические алгоритмы создания и декодирования цепочек будут разработаны на практическом занятии.

Рис.4.

Сравним характеристики методов создания цепочек в виде таблицы.

3. Написать процедуру, которая выполняет вставку компоненты по заданному ключу.

include <stdio.h>

#include <stdlib.h>

#define MyType int

//Будем считать, что ключ в нашем случае - это эзначение типа int.

//Хранение значений -в виде двоичного однонаправленного дерева. Левое поддерево - данные, со значением ключа меньше, чем вершина, прваое - большим, чем вершина.

typedef struct element //элемент-вершина дерева.

{

int key;

struct element * left_el;

struct element * right_el;

MyType val;

} MyElement;

typedef struct

{

MyElement * tree_root; //корень;

int size;

} MyMap; //сама структура хранилища.

MyMap initNewMap()

{

MyMap mm;

mm.tree_root=NULL;

mm.size=0;

return mm;

}

int add_element(MyMap * mm, int k, MyType el) //добавить пару ключ-значение

{

MyElement * new_el = malloc(sizeof(MyElement));

if(new_el)

{

new_el->key=k;

new_el->val=el;

new_el->left_el=NULL;

new_el->right_el=NULL;

if(mm->tree_root==NULL)

{

mm->tree_root=new_el;

mm->size++;

return 0;

}

if(!paste_element(new_el, mm->tree_root))

{

mm->size++;

//printf("SIZE: %d \n", mm->size);

return 0;

}

else

{

printf("ERROR!\n");

}

}

else

{

return -1;

}

}

int paste_element(MyElement * me, MyElement * root) //рекурсивная функция вставки. 0 - в случае успеха, -1 - ошибка

{

if(root==NULL)

{

return -1;

}

if(me->key==root->key)

{

root->val=me->val;

return 0;

//printf("ALREADY EXIST!\n"); //Значиение с совпадающим ключем заменяет текущее

}

if(me->key<root->key)

{

if(root->left_el==NULL)

{

//printf("ADD LEFT!\n");

root->left_el=me;

return 0;

}

else

root=root->left_el;

}

if(me->key>root->key)

{

if(root->right_el==NULL)

{

//printf("ADD Right!\n");

root->right_el=me;

return 0;

}

else

root=root->right_el;

}

paste_element(me, root);

}

MyType get_value(MyMap *mm, int key)

{

return find_element(key, mm->tree_root);

}

MyType find_element(int key, MyElement * root)

{

if(root==NULL)

{

return -1;

}

if(key==root->key)

return root->val;

else

{

if(key<root->key)

{

if(root->left_el==NULL)

{

return -1;

}

else

root=root->left_el;

}

if(key>root->key)

{

if(root->right_el==NULL)

{

return -1;

}

else

root=root->right_el;

}

find_element(key, root);

}

}

int main(void)

{

MyMap m_map = initNewMap();

add_element(&m_map, 12, 13);

add_element(&m_map, 15, 14);

add_element(&m_map, 14, 16);

add_element(&m_map, 15, 12);

add_element(&m_map, 19, 123);

add_element(&m_map, 39, 121);

printf ("VALUE 15: %d\n",get_value(&m_map, 15));

printf ("VALUE 19: %d\n",get_value(&m_map, 19));

printf ("VALUE 12: %d\n",get_value(&m_map, 12));

printf ("VALUE 12: %d\n",get_value(&m_map, 552));

return 0;

}

Билет 4.

1. Нормальный алгоритм Маркова.

Норма́льный алгори́тм Ма́ркова (НАМ) — один из стандартных способов формального определения понятия алгоритма. Понятие нормального алгоритма введено А. А. Марковымв конце1940-хгодов. Традиционно, когда говорят об алгоритмах Маркова, используют слово «алгорифм».

Нормальный алгоритм описывает метод переписывания строк, похожий по способу задания на формальные грамматики.НАМ является Тьюринг-полнымязыком, что делает его по выразительной силе эквивалентныммашине Тьюрингаи следовательно современным языкам программирования. ( про машину Тьюринга лучше не упоминать, чтобы не было дополнительных вопросов, но в курсе дела надо быть).

На основе НАМ был создан функциональныйязык программированияРефал.

Нормальные алгоритмы являются вербальными, то есть предназначенными для применения к словам в различных алфавитах. Определение всякого нормального алгоритма состоит из двух частей: определения алфавита алгоритма (к словам из символов которого алгоритм будет применяться) и определения его схемы. Схемой нормального алгоритма называется конечный упорядоченный набор т. н. формул подстановки, каждая из которых может быть простой или заключительной. Простыми формулами подстановки называются слова вида , где L и D — два произвольных слова в алфавите алгоритма (называемые, соответственно, левой и правой частями формулы подстановки). Аналогично, заключительными формулами подстановки называются слова вида , где L и D — два произвольных слова в алфавите алгоритма. При этом предполагается, что вспомогательные буквы  и  не принадлежат алфавиту алгоритма (в противном случае на исполняемую ими роль разделителя левой и правой частей следует избрать другие две буквы).