ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 18.01.2025
Просмотров: 710
Скачиваний: 2
При достаточно долгой работе скремблера неизбежно возникает его зацикливание. По выполнении определенного числа тактов в ячейках скремблера создастся комбинация бит, которая в нем уже однажды оказывалась, и с этого момента кодирующая последовательность начнет циклически повторяться с фиксированным периодом. Данная проблема неустранима по своей природе, так как в N разрядах скремблера не может пребывать более 2N комбинаций бит, и, следовательно, максимум, через, 2N-1 циклов повтор комбинации обязательно произойдет. Комбинация "все нули" сразу же исключается из цепочки графа состояний скремблера – она приводит скремблер к такому же положению "все нули". Это указывает еще и на то, что ключ "все нули" неприменим для скремблера. Каждый генерируемый при сдвиге бит зависит только от нескольких бит хранимой в данный момент скремблером комбинации. Поэтому после повторения некоторой ситуации, однажды уже встречавшейся в скремблере, все следующие за ней будут в точности повторять цепочку, уже прошедшую ранее в скремблере.
Возможны различные типы графов состояния скремблера. На рисунке 2 приведены примерные варианты для 3-разрядного скремблера. В случае "А" кроме всегда присутствующего цикла "000">>"000" мы видим еще два цикла – с 3-мя состояниями и 4-мя. В случае "Б" мы видим цепочку, которая сходится к циклу из 3-х состояний и уже никогда оттуда не выходит. И наконец, в случае "В" все возможные состояния кроме нулевого, объединены в один замкнутый цикл. Очевидно, что именно в этом случае, когда все 2N-1 состояний системы образуют цикл, период повторения выходных комбинаций максимален, а корреляция между длиной цикла и начальным состоянием скремблера (ключом), которая привела бы к появлению более слабых ключей, отсутствует.
И вот здесь математика преподнесла прикладной науке, каковой является криптография, очередной подарок. Следствием одной из теорем доказывается (в терминах применительно к скремблированию), что для скремблера любой разрядности N всегда существует такой выбор охватываемых обратной связью разрядов, что генерируемая ими последовательность бит будет иметь период, равный 2N-1 битам. Так, например, в 8-битном скремблере, при охвате 0-го, 1-го, 6-го и 7-го разрядов действительно за время генерации 255 бит последовательно проходят все числа от 1 до 255, не повторяясь ни разу.
Схемы с выбранными по данному закону обратными связями называются генераторами последовательностей наибольшей длины (ПНД), и именно они используются в скремблирующей аппаратуре. Из множества генераторов ПНД заданной разрядности во времена, когда они реализовывались на электрической или минимальной электронной базе выбирались те, у которых число разрядов, участвующих в создании очередного бита, было минимальным. Обычно генератора ПНД удавалось достичь за 3 или 4 связи. Сама же разрядность скремблеров превышала 30 бит, что давало возможность передавать до 240 бит = 100 Мбайт информации без опасения начала повторения кодирующей последовательности.
Рис.2.
ПНД неразрывно связаны с математической теорией неприводимых полиномов. Оказывается, достаточно чтобы полином степени N не был представим по модулю 2 в виде произведения никаких других полиномов, для того, чтобы скремблер, построенный на его основе, создавал ПНД. Например, единственным неприводимым полиномом степени 3 является x3+x+1, в двоичном виде он записывается как 10112 (единицы соответствуют присутствующим разрядам). Скремблеры на основе неприводимых полиномов образуются отбрасыванием самого старшего разряда (он всегда присутствует, а следовательно, несет информацию только о степени полинома), так на основе указанного полинома, мы можем создать скремблер 0112 с периодом зацикливания 7(=23-1). Естественно, что на практике применяются полиномы значительно более высоких порядков. А таблицы неприводимых полиномов любых порядков можно всегда найти в специализированных математических справочниках.
Существенным недостатком скремблирующих алгоритмов является их нестойкость к фальсификации. Подробнее данная проблема рассмотрена на следующей лекции, применительно к созданию целых криптосистем.
Блочные шифры
2.2.2.1. Общие сведения о блочных шифрах ( 19 кб ) На сегодняшний день разработано достаточно много стойких блочных шифров. Практически все алгоритмы используют для преобразований определенный набор биективных (обратимых) математических преобразований
2.2.2.2. Сеть Фейштеля Сетью Фейштеля называется метод обратимых преобразований текста, при котором значение, вычисленное от одной из частей текста, накладывается на другие части. Часто структура сети выполняется таким образом, что для шифрования и дешифрования используется один и тот же алгоритм – различие состоит только в порядке использования материала ключа.
2.2.2.3. Блочный шифр TEA Блочный алгоритм TEA приведен как пример одного из самых простых в реализации стойких криптоалгоритмов.
2.2.2.4. AES : cтандарт блочных шифров США c 2000 года В 1998 году был объявлен открытый конкурс на криптостандарт США на несколько первых десятилетий XXI века. Победителем конкурса был признан бельгийский блочный шифр Rijndael. Скорее всего он станет стандартом де-факто блочного шифрования во всем мире.
Общие сведения о блочных шифрах
Характерной особенностью блочных криптоалгоритмов является тот факт, что в ходе своей работы они производят преобразование блока входной информации фиксированной длины и получают результирующий блок того же объема, но недоступный для прочтения сторонним лицам, не владеющим ключом. Таким образом, схему работы блочного шифра можно описать функциями Z=EnCrypt(X,Key) и X=DeCrypt(Z,Key)
Ключ Key является параметром блочного криптоалгоритма и представляет собой некоторый блок двоичной информации фиксированного размера. Исходный (X) и зашифрованный (Z) блоки данных также имеют фиксированную разрядность, равную между собой, но необязательно равную длине ключа.
Блочные шифры являются основой, на которой реализованы практически все криптосистемы. Методика создания цепочек из зашифрованных блочными алгоритмами байт позволяет шифровать ими пакеты информации неограниченной длины. Такое свойство блочных шифров, как быстрота работы, используется асимметричными криптоалгоритмами, медлительными по своей природе. Отсутствие статистической корреляции между битами выходного потока блочного шифра используется для вычисления контрольных сумм пакетов данных и в хешировании паролей.
Следующие разработки всемирно признаны стойкими алгоритмами и публикаций о универсальных методах их взлома в средствах массовой информации на момент создания материала не встречалось.
|
Название алгоритма |
Автор |
Размер блока |
Длина ключа |
|
IDEA |
Xuejia Lia and James Massey |
64 бита |
128 бит |
|
CAST128 |
64 бита |
128 бит |
|
|
BlowFish |
Bruce Schneier |
64 бита |
128 – 448 бит |
|
ГОСТ |
НИИ *** |
64 бита |
256 бит |
|
TwoFish |
Bruce Schneier |
128 бит |
128 – 256 бит |
|
MARS |
Корпорация IBM |
128 бит |
128 – 1048 бит |
Криптоалгоритм именуется идеально стойким, если прочесть зашифрованный блок данных можно только перебрав все возможные ключи, до тех пор, пока сообщение не окажется осмысленным. Так как по теории вероятности искомый ключ будет найден с вероятностью 1/2 после перебора половины всех ключей, то на взлом идеально стойкого криптоалгоритма с ключом длины N потребуется в среднем 2N-1 проверок. Таким образом, в общем случае стойкость блочного шифра зависит только от длины ключа и возрастает экспоненциально с ее ростом. Даже предположив, что перебор ключей производится на специально созданной многопроцессорной системе, в которой благодаря диагональному параллелизму на проверку 1 ключа уходит только 1 такт, то на взлом 128 битного ключа современной технике потребуется не менее 1021 лет. Естественно, все сказанное относится только к идеально стойким шифрам, которыми, например, с большой долей уверенности являются приведенные в таблице выше алгоритмы.
Кроме этого условия к идеально стойким криптоалгоритмам применяется еще одно очень важное требование, которому они должны обязательно соответствовать. При известных исходном и зашифрованном значениях блока ключ, которым произведено это преобразование, можно узнать также только полным перебором. Ситуации, в которых постороннему наблюдателю известна часть исходного текста встречаются повсеместно. Это могут быть стандартные надписи в электронных бланках, фиксированные заголовки форматов файлов, довольно часто встречающиеся в тексте длинные слова или последовательности байт. В свете этой проблемы описанное выше требование не является ничем чрезмерным и также строго выполняется стойкими криптоалгоритмами, как и первое.
Таким образом, на функцию стойкого блочного шифра Z=EnCrypt(X,Key) накладываются следующие условия:
Функция EnCrypt должна быть обратимой.
Не должно существовать иных методов прочтения сообщения X по известному блоку Z, кроме как полным перебором ключей Key.
Не должно существовать иных методов определения каким ключом Key было произведено преобразование известного сообщения X в сообщение Z, кроме как полным перебором ключей.
Давайте рассмотрим методы, с помощью которых разработчики блочных криптоалгоритмов добиваются одновременного выполнения этих трех условий с очень большой долей достоверности.
Все действия, производимые над данными блочным криптоалгоритмом, основаны на том факте, что преобразуемый блок может быть представлен в виде целого неотрицательного числа из диапазона, соответствующего его разрядности. Так, например, 32-битный блок данных можно интерпретировать как число из диапазона 0..4'294'967'295. Кроме того, блок, разрядность которого обычно является "степенью двойки", можно трактовать как несколько независимых неотрицательных чисел из меньшего диапазона (рассмотренный выше 32-битный блок можно также представить в виде 2 независимых чисел из диапазона 0..65535 или в виде 4 независимых чисел из диапазона 0..255).
Над этими числами блочным криптоалгоритмом и производятся по определенной схеме следующие действия (слева даны условные обозначения этих операций на графических схемах алгоритмов) :
|
Биективные математические функции |
||
|
Сложение |
X'=X+V |
|
|
Исключающее ИЛИ |
X'=X XOR V |
|
|
Умножение по модулю 2N+1 |
X'=(X*V) mod (2N+1) |
|
|
Умножение по модулю 2N |
X'=(X*V) mod (2N) |
|
|
Битовые сдвиги |
||
|
Арифметический сдвиг влево |
X'=X SHL V |
|
|
Арифметический сдвиг вправо |
X'=X SHR V |
|
|
Циклический сдвиг влево |
X'=X ROL V |
|
|
Циклический сдвиг вправо |
X'=X ROR V |
|
|
Табличные подстановки |
||
|
S-box (англ. substitute) |
X'=Table[X,V] |
|