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

перемешивания строк и столбцов в блочных криптоалгоритмах с ар­ хитектурой «К в а д р а т» . Использование двухпараметической опера­ ции с операндами одинаковой длины произвольного вида (использу­ ются все 21значений операндов) улучшает качество рассеивания и перемешивания информации.

Логика работы стохастического сумматора определяется содер­ жимым ключевой таблицы стохастического преобразования объемом, например, 256 байт. Для аналитика, не знающего содержимого этой таблицы, результат работы Л-блока выглядит случайным. Всего су­ ществует 255! вариантов заполнения 8-разрядной таблицы стохасти­ ческого преобразования. При нулевом значении параметра преобра­ зования и вырожденной адресной таблице (в каждой ячейке записан ее собственный адрес) мы получаем классический блок замены. Та­ ким образом, можно утверждать, что 5’-блок это вырожденный вари­ ант /?-блока, который, по сути, реализует целый ансамбль из 256 криптографических преобразований замены (рис. 47). Заменяя значе­ ния параметра преобразования мы получаем новую таблицу заме­ ны для б’-блока. Следует отметить также большое сходство структу­ ры нелинейного Д-блока со структурой устройства, выполняющего табличное умножение в конечном поле GF(2").

Puc. 47. Представление трехразрядного R-блока в виде ансамбля различных S-блоков

Криптографические генераторы ПСП должны удовлетворять следующим требованиям:

♦непредсказуемость формируемых последовательностей;

♦хорошие статистические свойства;

♦большой период формируемых последовательностей. Наиболее производительные генераторы ПСП, так называемые

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

псп

Y, = YM + T,.9

Рис. 48. Схема аддитивного генератора

Кроме того, по своим периодическим свойствам они не выдер­ живают конкуренции даже с такими же линейными устройствами, функционирующими в конечных полях. Последние, при соответст­ вующем выборе характера обратных связей, формируют последова­ тельности максимальной длины. Простая замена обычного суммато­ ра на стохастический дает неожиданный результат, мы получаем не­ линейное устройство (рис. 49), по сути, регистр сдвига со стохасти­ ческой обратной связью (RFSR), со следующими свойствами:

псп

Y, = ^(Y,^» Y/.9)

Рис. 49. Регистр сдвига со стохастической обратной связью (RFSR)

♦эффективная программная и аппаратная реализация;

♦отличные статистические свойства формируемых ПСП;

Стохастический кодек с исправлением ошибок (рис. 51) сочета­ ет реализацию поточного режима блочного шифрования, обеспечи­ вающего преобразование произвольного дискретного канала связи к q-му симметричному каналу, для которого длина ^-го символа сов­ падает с длиной блока блочного шифра, с использованием q-ro (л, А)-кода на основе двоичного кода с расстоянием d, обеспечиваю­ щего исправление не менее d- 2 искаженных q-x символов. Стохасти­ ческое нелинейное преобразование используется в схеме для выпол­ нения операции гаммирования, т.е. наложения ПСП на входную ин­ формационную последовательность.

Преобразованный ДК

Рис. 51. Структура стохастического кодека: Д К - дискретный канал

Рис. 52. Принцип построения блочного шифратора (стохастического преобразования) произвольной длины на основе R-блоков

4. Выводы

♦Новую архитектуру построения блочных шифров «Квадрат», впервые предложенную в прототипе RIJNDAEL алгоритме SQUARE, следует признать перспективной и более эффек­ тивной, чем классическая сеть Фейстеля. В RIJNDAEL в од­

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

1. Следует выделить две тенденции в развитии криптоалгорит­ мов с секретным ключом. Активное использование, во-первых, опе­ раций в конечных полях (как при построении функции обратной свя­ зи, так и при построении функции выхода); во-вторых, блоков замен (^-блоков) с динамически изменяющейся в процессе работы табли­ цей преобразования.

♦Для изменения статистики шифруемой последовательности

сприближением результата ее преобразования к равномер­ ному распределению в постановке Шеннона о шифровании

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

2.Устройство, реализующее эту операцию (Л-блок), (рис. 52) имеет (2—1)! исходных состояний (начальных заполнений) при длине преобразования / и является в некотором смысле обобщением для ■У-блОКОВ.

3.Эту операцию можно использовать для наложения гаммы

впоточных криптоалгоритмах или для усложнения преобразований перемешивания строк и столбцов в блочном криптоалгоритме с ар­ хитектурой «Квадрат». Следует отметить большое сходство структу­ ры нелинейного Л-блока со структурой устройства, выполняющего табличное умножение в конечном поле GF{21).

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

5. Использование Л-блоков в цепях обратной связи регистров сдвига является средством достижения сочетания следующих свойств генераторов псевдослучайных последовательностей: неогра­ ниченного периода генерации, высокой скорости генерации, эффек­ тивной программной и/или аппаратной реализации, непредсказуемо­ сти последовательности при случайном заполнении не менее двух Л-блоков в цепях обратной связи.

2.1.9. Вопросы и задачи для самоконтроля

1.Приведите классификацию криптоатак, построенную на дан­ ных, известных криптоаналитику.

2.Перечислите возможные угрозы со стороны злоумышленника.

3.Перечислите возможные угрозы со стороны законного отпра­ вителя сообщения.

4.Перечислите возможные угрозы со стороны законного полу­ чателя сообщения.

5.Опишите классическую задачу криптографии.

6.Опишите задачу подтверждения авторства сообщения.

7.Опишите задачу вручения сообщения под расписку.

8.Перечислите основные теоретические задачи практической криптографии.

9.Укажите отличие абсолютно стойких систем от достаточно стойких систем.

10.Опишите алгоритм DES. Если произойдет искажение одного бита символа шифрованного текста при передаче в 8-битовом режи­ ме CFB, на сколько блоков распостранится это искажение в получен­ ном сообщении?

11.Имеет ли смысл дважды зашифровывать сообщение с помо­ щью алгоитма DES?

12.Опишите алгоритм криптографического преобразования данных ГОСТ 28147-89.

13.В чем преимущества ГОСТ 28147-89 перед DES?

14. Какие три режима шифрования предусмотрены в ГОСТ 28147-89?

15.Для чего используется имитовставка?

16.Сформулируйте правило Кирхгофа.

17.Укажите преимущества блочных шифров перед поточными.

18.Укажите преимущества поточных шифров перед блочными.

19.Требования, предъявляемые к генераторам ПСП в крипто­

графии.

2.2. СЛОЖНОСТЬ КРИПТОГАФИЧЕСКИХ АЛГОРИТМОВ. ОДНОСТОРОННИЕ ФУНКЦИИ

2.2.1.Детерминированные машины Тьюринга и класс Р

Рассмотрим модель детерминированной одноленточной маши­ ны Тьюринга (ДМТ), которая схематически изображена на рис. 53.

Рис. 53. Схематическое изображение ДМТ

Машина Тьюринга состоит из:

♦управляющего устройства с конечным числом состояний;

♦читающей/пишущей головки, которая может считывать и за­ писывать символы;

♦неограниченной в обе стороны ленты, разделенной на беско­ нечное число одинаковых ячеек, занумерованных целыми

числами: ..., -2, -1,0, 1,2, 3,...

Программа для ДМТ определяется следующими компонентами:

♦конечным множеством Г символов, которые записываются на ленте;

♦подмножеством Е С Г входных символов и выделенным пус­ тым символом b С 1\£;

♦конечным множеством состояний Q, в котором выделены на­ чальное состояние qO и два заключительных состояния qy,qn,

♦функцией перехода8: (Q\{qy,qn}) * Г—>Q * Г * { - 1,1}. Работа программы определяется следующим образом. Входом

детерминированной программы является слово х е Е*. Слово запи­ сывается на ленте в ячейках с номерами 1, 2, ...,|х| по одному симво­ лу в ячейке. Все другие ячейки в начальный момент времени содер­ жат пустой символ и называются пустыми. Программа начинает ра­ боту, находясь в состоянии qO , при этом читающая/ пишущая голов­ ка находится над ячейкой с номером 1.

Далее процесс вычислений осуществляется последовательно, шаг за шагом. Если текущее состояние q есть qy или qn, то процесс вычисления заканчивается, при этом результатом будет «да», если q = qy, и «нет», если q = qn. В противном случае текущее состояние принадлежит множеству Q\{qy,qn}, при этом головка читает на ленте некоторый символ s е Г и определено значение 8 (q,s). Предполо­ жим, что 8 (q,s) = (q’j ’fi). В этом случае головка стирает s, пишет на этом месте s' и сдвигается на одну ячейку влево, если А = -1, или на одну ячейку вправо, если А = +1. Одновременно управляющее уст­ ройство переходит из состояния q в q’ На этом заканчивается один «шаг» процесса вычисления, и программа готова к выполнению сле­ дующего шага.

Пример простой ДМТ-программы представлен на следующей схеме (рис. 54).

Функция перехода 8 определена таблицей, где величина, запи­ санная в у-й строке и s-м столбце, есть значение 8 (qj). Рис. 54 ил­ люстрирует вычисление по программе М при входе дс = 10100; здесь указаны состояние, расположение головки и содержимое непустых ячеек ленты до и после каждого шага.

Заметим, что это вычисление после восьми шагов оканчивается в состоянии qy, поэтому на входе 10100 ответом будет «да». В общем случае будем говорить, что программа М, имеющая входной алфавит Е, принимает в том и только в том случае, когда, будучи при­

мененной ко входу х, она останавливается в состоянии qy. Язык LM> распознаваемый программой Л/, задается следующим образом:

LM = {JC е Е * : М принимает х }.

Нетрудно видеть, что представленная программа распознает

язык

*два последних символа 1

слова х являются нулями J

Г - Ю . 1 , * ) . £ - ( 0 , 1 )

Q — (<7о.<7»> Я * * Я у * Я г * Я н \

Рис. 54. Пример ДМТ-программы М = (T,Q,5)

Отметим, что это определение распознавания языка не требует, чтобы программа М останавливалась при всех входах из Е*; М обя­ зана останавливаться лишь при входах из LM. Если х принадлежит