Основные методы и алгоритмы генерации случайных ключей для блочного шифрования
ФЕДЕРАЛЬНОЕ
АГЕНСТВО СВЯЗИ
Государственное
образовательное учреждение высшего профессионального образования
МОСКОВСИЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ СВЯЗИ И
ИНФОРМАТИКИ
Кафедра общей теории связи
РЕФЕРАТ
по дисциплине «Основы криптографии»
на
тему: «Основные методы и алгоритмы генерации случайных ключей для блочного
шифрования»
Выполнил:
Шахов М.Е.
Проверил: Волчков В. П.
Москва
2014
Содержание
Введение
.
Постановка задачи
.1
Режим прямого шифрования, или шифрования с использованием электронной книги
кодов ECB (Electronic Code Book)
.2
Режим шифрования со сцеплением с блоками зашифрованного сообщения CBC(Cipher
Block Chaining)
.3
Режим шифрования с посимвольной обратной связью CFB(Cipher Feedback)
.4
Режим шифрования с внутренней обратной связью OFB(Output Feedback)
.
Метод решения
.1
Генерация ключей в министерстве обороны США
.2
ANSI X9.17
.3
Линейный сдвиговый регистр с обратной связью (LFSR)
.4
Генератор реальных случайных последовательностей
.5
Структурные схемы генераторов случайных последовательностей, режима OFB и
рекомендации X.9.17
Вывод
Список
литературы
Введение
шифрование электронный код генерация
«Безопасность алгоритма сосредоточена в ключе.
Если вы используете криптографически слабый процесс для генерации ключей, то
ваша система в целом слаба. Еве не нужно анализировать ваш алгоритм шифрования,
она может анализировать ваш алгоритм генерации ключей».
Брюс Шнайер «Прикладная криптография».
Существует множество алгоритмов блочного
шифрования, такие как DES,
AES, Blowfish,
ГОСТ 28147-89 и др. Многолетний криптоанализ доказал надёжность и стойкость
этих алгоритмов. Безопасность криптосистемы является функцией двух факторов:
надёжности алгоритма и ключа. IP-революция
набирает обороты и блоковые шифры становятся всё более актуальны. В своей
работе я хочу рассмотреть методы генерации таких ключей и проблемы с которыми
сталкивается криптограф.
1. Постановка задачи
.1 Режим прямого шифрования, или шифрования с
использованием электронной книги кодов ECB
(Electronic
Code Book)
Обеспечивает непосредственное применение
алгоритма шифрования к каждому блоку защищаемой информации; таким образом,
каждый блок шифруется независимо от других. В этом режиме каждому блоку
открытого сообщения ставится в однозначное соответствие блок зашифрованного сообщения.
Плюсы:
. Простота реализации
Минусы:
. Неустойчив к атакам по известному
фрагменту (криптоаналитику известен исходный блок сообщения и соответствующий
ему блок шифротекста, тогда он может найти этот блок при его повторении);
. Неустойчив к атакам на типовые начала и
окончания (заголовки сообщений электронной почты, банковских форм);
. Неустойчив к повторам сообщения (Так
например у криптоаналитика оказывается записанное простым перехватом сообщение
от одного банка другому, с запросом перевода денежных средств на расчётный счёт
криптоаналитика, возможно инициированное самим криптоаналитиком, законным
образом, он получает возможность продублировать это сообщение, тем самым удвоив
сумму перевода);
. Неустойчив к активному перехвату
(криптоаналитик включается «в разрыв» канала передачи, если ему известна
структура сообщения, он может вносить в него изменения, например заменив чужой
расчётный счёт, на свой).
1.2 Режим шифрования со сцеплением с блоками
зашифрованного сообщения CBC(Cipher Block Chaining)
Этот режим, использует принцип обратной связи,
использует зависимость зашифрованного блока 
не
только от исходного сообщения 
, но так же и от
других блоков.
Для шифрования используют так называемый вектор
инициализации 
, представляющий
собой блок случайных чисел такого же размера, как и шифруемые блоки.
Этот вектор должен быть идентичен для шифрования
и дешифрования, причём хранение его в секрете не обязательно, необходимо только
использовать новый вектор при передачи нового сообщения.
Шифрование:
Плюсы:
. Относительная простота;
. Устойчив к повтору сообщения;
. Устойчив к активному перехвату;
. Вносит в передаваемое сообщение
некоторый элемент случайности.
Минусы:
. Эффект обратной связи приводит к
размножению ошибок (поражает сразу два блока, в первом сам бит ошибки, во
втором весь блок);
. Нарушение синхронизации приводит к
катастрофическим последствиям, если в режиме ECB
достаточно восстановить синхронизацию по блокам (восстановление правильных
границ блоков), то сбой синхронизации в CBC
требует реинициализации и рестарта всей системы;
.3 Режим шифрования с посимвольной обратной
связью CFB(Cipher
Feedback)
Данный режим ориентирован на использование в
случае, когда необходимо передавать нестандартные блоки сообщений, например,
при использование посимвольного (побайтового) диалога, т.н. режима чата.
Шифрование одного символа 
размером
бит
при размере блока шифрования 
бит 
осуществляется
в следующем порядке:
1. 
-
шифруемый блок (заполняется случайными числами вектора инициализации );
2. 
заполненный блок шифруется;
3. 
,
,
выделяются
старших
бит блока 
;
4. 
исходный символ складывается по
модулю два с комбинацией 
;
. Сообщение 
передается
в канал связи как зашифрованное сообщение, соответствующее исходному ;
6. 
блок сдвигается
логически влево на разрядов, а в
младшие разрядов
записывается .
Плюсы:
. Возможность использовать для шифровании
блоков любой длинны; Устойчивость к повтору сообщения;
. Устойчивость к активному перехвату.
Минусы:
. При потери синхронизации
работоспособность восстанавливается после передачи бит
информации.
.4 Режим шифрования с внутренней обратной связью
OFB(Output
Feedback)
Режим аналогичен режиму CFB,
за исключением того, что в операции 6. вместо
1. -
шифруемый блок (заполняется случайными числами вектора инициализации );
2.
заполненный блок шифруется;
3. ,
,
выделяются
старших
бит блока ;
4.
исходный символ складывается по
модулю два с комбинацией ;
. Сообщение передается
в канал связи как зашифрованное сообщение, соответствующее исходному ;
6. 
блок сдвигается
логически влево на разрядов, а в
младшие разрядов
записывается .
Предположим, что алгоритм, а точнее функция
шифрования совершенна, то
есть оптимальный путь взлома - вскрытие грубой силой с помощью перебора всех
возможных ключей. Тогда если используется 8битный ключ, существует 
,
или 
,
возможных ключей, с 50% -ой вероятностью найти ключ после половины попыток. Для
64битной системы, компьютеру обрабатывающему миллион ключей в секунду
понадобится около 585000 лет, что бы найти правильный ключ среди 
возможных
ключей. Для ключа в 128бит понадобится 
лет,
для сравнения возраст вселенной составляет 
лет.
Хорошими ключами являются строки случайных бит, их использование при достаточно
хорошем алгоритме, позволяет эффективно противостоять большинству криптоатак.
Но при длительном использовании одного ключа, криптоаналитик может составить
достаточный шифровальный блокнот, для дешифрации сообщений. С учётом научного
прогресса появляется возможность обрабатывать много больше ключей в секунду на
процессор, тем самым ключ который был стойким год назад на 10 лет, через год
продержится, 6 лет. А значит необходимо получить генератор случайных чисел,
либо линейный сдвиговый регистр с обратной связью(LFSR),
так же можно использовать стандарт ANSI X9.17
или рекомендацию министерства обороны США.
2. Метод решения
.1 Генерация ключей в министерстве обороны США
Министерство обороны США предлагает использовать
блочный алгоритм в режиме OFB.
1. -
шифруемый блок (заполняется случайными числами вектора инициализации );
2.
заполненный блок шифруется;
3. ,
,
выделяются
старших
бит блока ;
4.
исходный символ складывается по
модулю два с комбинацией ;
. Сообщение передается
в канал связи как зашифрованное сообщение, соответствующее исходному ;
6.
блок сдвигается
логически влево на разрядов, а в
младшие разрядов
записывается .
Анализ режима OFB показывает, что OFB стоит использовать
только, когда размер обратной связи совпадает с размером блока. Т.е.
размерность равно, размерности
.
Режим OFB выполняет XOR над потоком ключей и текстом. Этот поток ключей со
временем повторяется. Важно, чтобы он не повторялся для того же ключа, в
противном случае нарушается безопасность. Когда размер обратной связи равен
размеру блока, блочный шифр переставляет -битовые значения (где -
это размер блока), и средняя длина цикла составляет 
.
При длине блока 64 бита это очень большое число. Когда размер обратной связи меньше
длины блока, средняя длина цикла падает до приблизительно 
.
Для 64-битного шифра это только 232 - что явно недостаточно.
2.2 ANSI
X9.17
Данный стандарт подходит для генерации сеансовых
ключей или псевдослучайных чисел в системе.
Пусть 
-
это 
,
зашифрованный DES ключом 
, специальным
ключом, предусмотренным для генерации секретных ключей. 
-
это секретная 64-битовая стартовая последовательность. 
-
это метка времени. Для генерации случайного ключа 
вычислим:
Для генерации 
вычислим:
Для превращения в
ключ DES, просто удалите каждый восьмой бит. Если вам нужен 64-битовый ключ,
используйте ключ без изменения. Если вам нужен 128-битовый ключ, создайте пару
ключей и объедините их.
.3 Линейный сдвиговый регистр с обратной связью
(LFSR)
Наиболее распространённый среди криптографов
алгоритм генерации псп - LFSR.
Используется в основном для потоковых шифров, но может использоваться для
генерации ключа и вектора инициализации блочных шифров. Для этого необходимо
сгенерировать последовательность в БД, затем разбить её на блоки нужной длинны,
далее по меткам синхронизации блоков шифрованных сообщений менять блок вектора
инициализации ( если требуется, например для режима CBC),
а по меткам синхронизации внутреннего цикла алгоритма (брать по наименьшему
циклу), менять ключ. Обратная связь регистра представляет собой просто XOR
некоторых битов регистра, перечень этих битов называется отводной
последовательностью, такой регистр ещё называют конфигурацией Фиббоначи.
n-битовый LFSR
может находиться в одном из 
внутренних
состояний. Это означает, что теоретически он может генерировать
последовательность из битов. Но только
при определённых отводных последовательностях LFSR
циклически пройдёт через все состояний, такие LFSR
называют LFSR с
максимальным периодом, а последовательность, М-последовательностью.
Для того чтобы конкретный LFSR
имел максимальный период, многочлен, образованный из отводной
последовательности и константы 1, должен быть примитивен по модулю 2. Степень
многочлена является длиной сдвигового регистра.
Примитивный многочлен степени n
- это неприводимый многочлен, который является делителем 
,
но не является делителем 
для всех 
,
являющихся делителями 
.
В общем случае не существует простого способа
генерировать примитивные многочлены данной степени, обычно это делают, либо
методом подбора, либо специализированного программного обеспечения. Но по уже
известному многочлену, можно сгенерировать, например если примитивен 
,
то 
так
же примитивен. LFSR
- хороший генератор псп, но последовательные биты линейны. Для LSFR
длины 
внутреннее
состояние представляет выходных битов
генератора, а схема обратной связи может быть определена по 
выходным
битам генератора.
P.S.
Конгруэнтный метод генерации псп не рассматривается, так как такие генераторы
являются предсказуемыми и не могут применяться в криптографии.
2.4 Генератор реальных случайных
последовательностей
На мой взгляд - это оптимальный способ генерации
блочных ключей.
Первым встаёт вопрос о проверки такого
генератора, действительно ли он выдаёт нам случайные числа? В этом вопросе нам
может помочь тест Маурера. Цель теста - выяснить, может ли данная
последовательность быть значительно сжата без потерь информации. В случае если
это возможно сделать, то она не является истинно случайной. Так как же
сгенерировать случайную последовательность? Если вы стеснены в средствах, можно
подбрасывать монетку, записывать орёл как 0, решка как 1, но есть и более
действенные методы:
. Таблицы RAND.
В 1955 году Rand
Corporation издала книгу,
содержавшую миллион случайных цифр и описали метод генерации так:
Случайные цифры этой книги были получены при
помощи рандомизации основной таблицы, сгенерированной электронной рулеткой.
Вкратце, источник импульсов, выдающий их со случайной частотой в среднем около
100000 импульсов в секунду, открывался раз в секунду импульсом постоянной
частоты. Цепи нормализации импульса пропускали импульсы через 5-разрядный
бинарный счетчик. По сути машина являлась колесом рулетки с 32-позициями,
которое в среднем делало около 3000 оборотов за выборку и выдавало одно число в
секунду. Использовался двоично-десятичный преобразователь, который
преобразовывал 20 из 32 чисел (оставшиеся двенадцать отбрасываются) и оставлял
только последнюю цифру двузначных чисел. Эти последние цифры попадали в
компостер IBM, образуя в конце концов таблицу пробитых карточек случайных цифр.
. Использование случайного шума. Самое
хорошее в таких генераторах то, что за нас случайность генерирует сама природа.
Можно подключить счётчик Гейгера к пк, подсчитать количество импульсов за
фиксированное время и взять младший бит. Так, например, самым популярным можно
назвать генератор, основанный на шуме от эффекта теплового пробоя в
стабилитроне. В нём шум создаваемый стабилитроном в режиме электронного пробоя,
усиливается и подаётся на компаратор, на выходе которого устанавливается
потенциал логической единицы при положительном, а логического нуля при
отрицательном напряжениях. При выводе, сигнал с выхода компаратора стробируется
с требуемой частотой дискретизации, соответствующей тактовой частоте случайной
последовательности.
.5 Структурные схемы генераторов случайных
последовательностей, режима OFB
и рекомендации X.9.17
Рис.1. Режим OFB.
Рис.2. Рекомендация X.9.17.
Цикл:
Рис.3.LFSR (сдвиговый регистр с линейной
обратной связью).
Рис.4.Генератор шума стабилитрона.
Вывод
Наиболее стойкими считаются генераторы реальных
случайных чисел. Но его использование влечёт за собой трудности с передачей
огромных объёмов информации по засекреченным каналам. В некоторых случаях это
невозможно. Тогда следует использовать режим OFB
или CFB который
будет генерировать ключи внутри алгоритма на основе ключа, так же следует
генерировать, с определённой периодичностью, примерно равной длине внутренней
последовательности, сам ключ. Для этого можно использовать линейно сдвиговый
регистр.
Список литературы
1. Шнайер
Б. Прикладная криптография (Applied
Cryptography).
. Шаврин
С.С. Защита информации в многоканальных телекоммуникационных системах: Учебное
пособие. - М.: МТУСИ, 2002.
. Санников
В. Г. Введение в теорию и методы криптографической защиты информации: Учебное
пособие. - М.: МТУСИ, 2009.