Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



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




Читайте также:
  1. CASE-технология создания информационных систем
  2. GNU(рекурсивный акроним от GNU’s Not UNIX — «GNU — не Unix!») — это проект создания свободной UNIX-подобная операционной системы, открытый в 1983 году Ричардом Столлмэном.
  3. Алгоритмы
  4. Алгоритмы внутренней сортировки. Элементарные методы сортировки
  5. Алгоритмы заливки замкнутых областей.
  6. Алгоритмы маршрутизации в сетях.
  7. Алгоритмы прохождения графа.
  8. Алгоритмы разгона и торможения. Сравнительная оценка алгоритмов. Примеры.
  9. Алгоритмы сжатия без потерь - кодирование длин серий (RLE), алгоритм Лемпеля-Зива-Велча (LZW), форматы GIF и PNG.
  10. Алгоритмы сжатия файлов без потерь

Первая задача, с которой мы столкнемся при шифровании данных криптоалгоритмом – это данные с длиной, неравной длине 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.

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

Метод Шифрование блока зависит от Искажение одного бита при передаче Кодируется ли некратное блоку число байт без дополнения? На выход криптосистемы поступает
ECB текущего блока портит весь текущий блок нет выход криптоалгоритма
CBC всех предыдущих блоков портит весь текущий и все последующие блоки нет выход криптоалгоритма
CFB всех предыдущих блоков портит один бит текущего блока и все последующие блоки да XOR маска с исходным текстом
OFB позиции блока в файле портит только один бит текущего блока да XOR маска с исходным текстом

 

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;

}


Дата добавления: 2015-04-21; просмотров: 18; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2020 год. (0.011 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты