Лекции по "Информационной безопасности"

Процедура дешифровки выглядит следующим образом: число, соответствующее iой буквы открытого текста получается прибавлением по модулю m (26) числа, соотвутствующего i-ой по модулю "р" букве ключа. 
 
 
 
 
 
 
 
 
 
 
 
 

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

Если  удается определить длину периода  ключа, то можно определить буквы  с помощью частотного анализа. Период ключа может быть обнаружен поиском  повторяющихся блоков в шифрованном  текста. Часть из них носит случайный  характер, но основная масса получается из соответствия между повторяемыми словами или подсловами в открытом тексте и повторами в последовательности ключа. Когда это имеет место, расстояние между повторами будет кратным периоду ключа 

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

Для запуска  шифра используется короткий затравочный  ключ (обычно 1 буква), этот ключ предложен  Кордано.

: с – константа, n и m – взаимно простые.

Второй  способ шифрования с автоматическим выбором ключа испльзует в  качестве ключа шифрованный текст  .

Шифр  бегущего ключа Вижинера использует в качестве ключа неповторяющийся  текст. Первоначально эти шифры считались невзламываемыми, но в конце XIX в. было найдено общее решение для многоалфавитных подстановок без ограничений на тип или длину ключа. Наиболее значительный вариант шифра Вижинера был предложен в 1918 году американским инженером.

Сообщение тогда передавалось с использованием двоичного кода и было предложено прибавлять по модулю 2 случайные последовательности точек и пробелов так, чтобы вся  частотная информация, корреляция между  символами, периодичность и т.п. терялись.

Главный недостаток этой процедуры состоит в том, что она требует обмена огромным количеством ключей заблаговременно (один символ ключа на каждый символ сообщения).

Сначала предполагалось использовать или короткий ключ или линейную комбинацию коротких ключей, но оба подхода оказались уязвимыми.

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

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

Следующим подходом к шифрованию является разработка полиграфовых систем – это блочные  шифры, рассматривающие одновременно группы символов открытого текста.

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

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

Также можно записать весь алфавит в  вершинах 4 кубов, и осуществлять сдвиги внутри этих кубов. 

Шифр  Хилла.

Хилл  выяснил, что все современные криптосистемы могут быть сформулированы в единой модели линейных преобразований пространства сообщений.

Пусть К есть матрица размера n´n. a и d – n-мерные вектора из множества Z_m (целые). Шифр Хилла – это отображение (T - транспонир).

Однозначное тогда и только тогда, когда НОД  между детерминантом матрицы  К и числом m =1. Все операции выполняются по модулю m.

Для шифрования открытый текст подразделяется на блоки  по n символов, каждая буква заменяется соответствующим кей излементом из множества Z_m, затем образуем транспонированные вектор-столбцы и применяем данное линейное преобразование к каждому блоку .

В этом контексте используются матрицы  инволюций К, являющиеся своими обратными, т.е. К²mod26=I è det(K)=±1

Пытаясь определить матрицы инволюций, когда  размерность n=2, а m=26 и если взять, что определитель =±1. При определителе 1 матриц 2´2 есть 8, -1 – 736.

При этом всё равно криптограмма может  быть дешифрована даже если неизвестно ни одного слова min длины из открытого текста.

Определяются  и пробуются все матрицы инволюций, но для больших значений n этим методом проб и ошибок достичь результата уже невозможно.

Заменяя постоянную матрицу K матрицей с переменными элементами, получаем разновидность предложенной Хиллом схемы. 

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

1) анализ  только шифрованного текста

2) анализ  известного открытого текста, т.е.  противник имеет несколько пар  открытый текст-шифрованный текст,  с которыми он может работать.

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

Поэтому только система одноразового блокнота безоговорочно надежна, что означает, что независимо от применяемых вычислительных мощностей вскрыть систему не удастся. 

Математические  проблемы могут быть разделены на 2 основные категории: разрешимые и неразрешимые проблемы. Неразрешимая проблема – проблема останова "машины Тьюринга" – некоторая гипотетическая машина.

Эта проблема эквивалентна следующей проблеме: цирюльник  бреет всех, кто не бреется сам, бреет ли он себя? Если бреет, то не бреет, а если не бреет, то бреет.

Разрешимые  проблемы могут быть подразделены на следующие ситуации:

1. Труднодоказуемые проблемы, имеющие лишь экспоненциальное время счета (решения) O(2ⁿ)
2. P-проблема, которая имеет полиномиальное время решения O(n^k)<O(2ⁿ)
3. NP-проблема, для которой известны только экспоненциальные алгоритмы, но не доказано, что алгоритма с полиномиальным временем не существует.

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

Рассмотрим  случай, когда мы имеем только 3 бита, с помощью которых можно представить  всего 8 объектов. Устройство называется ящиком подстановки или S-ящиком.

Устройство подстановки состоит из 2х переключателей. Первый преобразует последовательность 3х битов в соответствующее ей значение по основанию 8. Подавая таким образом энергию на любую из 8 выходящих линий, эти 8 линий могут быть соединены со вторым переключателем любим из 8! способов.

Роль  второго переключателя состоит  в том, что он должен преобразовать  вход, представляемый одной цифрой по основанию 8 снова в 3х битный выходной сигнал.

Предположим, что мы увеличим число входных  битов с 3х до 5, т.5. можно представлять сразу все буквы русского либо латинского алфивита, тогда существует уже 32! возможностей конфигураций в соединении этих 2х переключателей.

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

Ясно, что  одно устройство со многими входами  и выхоами само является Р-ящиком (ящиком перестановок) и Р-ящик имеет 8 входов и 8 выходов. S-ящик 0 это нелинейное устройство, а Р-ящик – линейное.

Чтобы улучшить эту схему, мы должны внести так называемые системы шифропроизведений, комбинируя P и S-ящики.

Впервые системы  шифропроизведений были предложены Шеноном. Они состоят из слоев  P и S-ящиков.

Предположим, что Р-ящики имеют 15 входов/выходов. За ними следует 5 S-ящиков и операции в системе шифров-произведений выполняются при условии, что вход состоит из 14 нулей и одной единицы. Первый ящик Р передает единственную единицу некоторому S-ящику, который являясь нелинейным устройством, может из одной единицы сделать до 3х единиц на своем выходе, затем эти единицы подаются на следующий Р-ящик, который перетасовывает их и подает на следующие S-ящики, и процесс повторяется. В конце выход содержит сбалансированное число нулей и единиц. Такой принцип реализован в системе IBM-"Люцифер", где Р ящики иеют по 64 или 128 входов, а S-ящики – по 4. Цель разработчика состоит в том, чтобы сделать для противника как можно более сложной задачу проследить обратный путь и таким образом восстановить ключи перестановок на S и Р ящиках.

Система "Люцифер" является блочным шифром высокой пробы, однако в настоящее  время она не считается достаточно надежной. В 1977 году национальное бюро стандартов выпустило стандарт шифрования данных DES. DES – блочный шифр, разработанный фирмой IBM на основе S-P ящиков. Шифрование осуществляется блоками по 64 бита и проводится за 16 отдельных этапов, хотя с точки зрения сложности DES выглядит надежным, но размер ключа 48 бит подвергается критике. Дело в том, что 56-битный ключ взламывается путем анализа известного открытого текста с использованием больших, но реальных вычислительных ресурсов (2⁵⁶ ключей). 

Основные  идеи цифровой подписи

Односторонней функцией с ловушкой называется функция  F_k, которая производит отображение Х в У в зависимости от параметра К и обладает 3 свойствами: F_K:XàY

1. При любом К существует полиномиальный алгоритм вычисления значений F_K(X)
2. При неизвестном К не существует полиномиального алгоритма инвертирования фукции F_K
3. При известном К существует полиномиальный алгоритм инвертирования F_K

В совреенной криптографии используется понятие  числового поля и конечного поля. Рассмотрим основные свойства операций сложения и умножения на множестве  действительных чисел.

Поле  – числовое множество, на котором выполнимы определенные действия + и ´.

Аксиомы поля:

1. Для любых 3х элементов a,b,cÎF a+(b+c)=(a+b)+c
2. В множестве F есть такой элемент 0, что для каждого aÎF a+0=0+a=a
3. Для каждого элемента аÎF существует противоположный элемент х, такой, что а+х=х+а=0
4. Для каждых 2х элементов a,bÎF a+b=b+a
5. Для каждых 3х элементов a,b,cÎF a×(b×c)=(a×b)×c
6. Во множестве F есть элемент 1¹0, такой, что для любого aÎF 1×a=a×1=a
7. Для каждого aÎF¹0 существует обратный элмент х, такой, что а×х=х×а=1
8. Для каждых 2х элементов a,bÎF a×b=b×a
9. Для любых 3х элементов a,b,cÎF a(b+c)=ab+ac