рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Проектирование S-блоков

Проектирование S-блоков - раздел Компьютеры, Часть III Криптографические алгоритмы Сила Большинства Сетей Фейстела - И Особенно Их Устойчивость К Дифференциальн...

Сила большинства сетей Фейстела - и особенно их устойчивость к дифференциальному и линейному кри п-тоанализу - непосредственно связана с их S-блоками. Это явилось причиной потока исследований, что же обр а-зует хороший S-блок.

S-блок - это просто подстановка: отображение m-битовых входов на n-битовые выходы. Ранее я упоминал об одной большой таблице отображения 64-битовых входов на 64-битовые выходы, такая таблица представляла бы собой S-блок размером 64*64 бита. S-блок с от-битовым входом и n-битовым выходом называется по­битовым S-блоком.S-блоки обычно являются единственным нелинейным действием в алгоритме, именно они


обеспечивают безопасность блочного шифра. В общем случае чем S-блоки больше, тем лучше.

В DES восемь различных 6*4-битовых S-блоков. В Khufu и Khafre единственный 8*32-битовый S-блок, в LOKI 12*8-битовый S-блок, а в Blowfish и CAST 8*32-битовые S-блоки. В IDEA S-блоком по сути является умножение по модулю, это 16*16-битовый S-блок. Чем больше S-блок, тем труднее обнаружить статистические отклонения, нужные для вскрытия с использованием либо дифференциального, либо линейного криптоанализа [653, 729, 1626]. Кроме того, хотя случайные S-блоки обычно не оптимальны с точки зрения устойчивости к дифференциальному и линейному криптоанализу, сильные S-блоки легче найти среди S-блоков большего ра з-мера. Большинство случайных S-блоков нелинейны, невырождены и обладают сильной устойчивостью к лине й-ному криптоанализу - и с уменьшением числа входных битов эта доля снижается медленно [1185, 1186, 1187].

Размер т важнее размера п. Увеличение размера п снижает эффективность дифференциального криптоана­лиза, но значительно повышает эффективность дифференциального криптоанализа. Действительно, если п>2т-т, то наверняка существует линейная зависимость для входных и выходных битов S-блока. И если п>2т, то линейная зависимость существует только для выходных битов [164].

Заметной частью работы по проектированию S-блоков является изучение логических функций[94, 1098, 1262, 1408]. Для обеспечения безопасности булевы функции, используемые в S-блоках, должны отвечать опр е-деленным условиям. Они не должны быть ни линейными, ни аффинными, ни даже быть близкими к линейным или аффинным [9, 1177, 1178, 1188]. Количество нулей и единиц должно быть сбалансированным, и не должно быть никаких корреляций между различными комбинациями битов. При изменении на противоположный л ю-бого входного бита выходные биты должны вести себя независимо. Эти критерии проектирования также связ а-ны с изучением функций изгиба:функций, которые, как может быть показано, являются оптимально нелине й-ными. Хотя они определены просто и естественно, их изучение очень нелегко [1344, 1216, 947, 905, 1176, 1271, 295, 296, 297, 149, 349, 471, 298].

Очень важным свойством представляется лавинный эффект: сколько выходных битов S-блока изменяется при изменении некоторого подмножества выходных битов. Нетрудно задать для булевых функций условия, в ы-полнение которых обеспечивает определенный лавинный эффект, но проектирование таких функций является более сложной задачей. Строгий лавинный критерий(strict avalanche criteria, SAC) обеспечивает, что с изм е-нением одного входного бита изменяется ровно половина выходных битов [1586]. См. также [982, 571, 1262, 399]. В одной из работ эти критерии рассматриваются в терминах утечки информации [1640].

Несколько лет назад криптографы предложили выбирать S-блоки так, чтобы таблица распределения разл и-чий для каждого S-блока была однородной. Это обеспечило бы устойчивость к дифференциальному криптоан а-лизу за счет сглаживания дифференциалов на любом отдельном этапе [6, 443, 444, 1177]. Примером такого проектирования является LOKI. Однако такой подход иногда способствует дифференциальному криптоанализу [172]. Действительно, лучшим подходом является минимизирование максимального дифференциала. Кванджо Ким (Kwangjo Kim) выдвинул пять критериев проектирования S-блоков [834], похожих на критерии проектир о-вания S-блоков DES.

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

1. Случайно выбрать. Ясно, что небольшие случайные S-блоки небезопасны, но большие случайные S-блоки могут оказаться достаточно хороши. Случайные S-блоки с восемью и более входами доста­точно сильны [1186, 1187]. Еще лучше 12-битовые S-блоки. Устойчивость S-блоков возрастает, если они одновременно являются и случайными, и зависящими от ключа. В IDEA используются большие зависящие от ключа S-блоки.

2. Выбрать и проверить. В некоторых шифрах свойства S-блоков, генерированных случайным образом, проверяются. Примеры такого подхода содержатся в [9, 729].

3. Разработать вручную. При этом математический аппарат используется крайне незначительно: S-блоки создаются с использованием интуитивных приемов. Барт Пренел (Bart Preneel) заявил, что "... теор е-тически интересные критерии недостаточны [для выбора булевых функций S-блоков] ...", и что "... н е-обходимы специальные критерии проектирования" [1262].

4. Разработать математически. S-блоки создаются в соответствии с математическими законами, поэтому они обладают гарантированной надежностью по отношению к дифференциальному и линейному криптоанализу, а также хорошими диффузными свойствами. Прекрасный пример такого подхода можно найти в [1179].

Существует ряд призывов объединить "математический" и "ручной" подходы [1334], но реально, по вид и-мому, конкурируют случайно выбранные S-блоки и S-блоки с определенными свойствами. Конечно преимущ е-ством последнего подхода является оптимизация против известных методов вскрытия - дифференциального и линейного криптоанализа - но обеспечиваемая этим подходом степень защиты от неизвестных методов вскр ы-


тия также неизвестна. Разработчикам DES было известно о дифференциальном криптоанализе, и его S-блоки были оптимизированы соответствующим образом. Скорее всего, о линейном криптоанализе они не знали, и S-блоки DES очень слабы по отношению к такому способу вскрытия [1018]. Случайно выбранные S-блоки в DES были бы слабее против дифференциального криптоанализа, но сильнее против линейного криптоанализа.

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

– Конец работы –

Эта тема принадлежит разделу:

Часть III Криптографические алгоритмы

На сайте allrefs.net читайте: Часть III Криптографические алгоритмы...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Проектирование S-блоков

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Энтропия и неопределенность
Теория информации определяет количество информациив сообщении как минимальное количество бит, необходимое для кодирования всех возможных значений сообщения, считая все сообщения ра

Норма языка
Для данного языка норма языкаравна г =H(M)/N где N - это длина сообщения. При больших N норма обычного английского яз

Зашифрованного алгоритмами с различной длиной ключа
Длина ключа (в битах) Расстояние уникальности (в символах)   5.9 8.2

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

Путаница и диффузия
Двумя основными методами маскировки избыточности открытого текста сообщения, согласно Шеннону, служат путаница и диффузия [1432]. Путаницамаскирует связь между открытым те

Сложность проблем
Теория сложности также классифицирует и сложность самих проблем, а не только сложность конкретных алгоритмов решения проблемы. (Отличным введением в эту тему являются [600, 211, 1226], см. также [1

Арифметика вычетов
Вы все учили математику вычетов в школе. Иногда ее называли "арифметикой часов". Если Милдред сказ а-ла, что она будет дома к 10:00, и опоздала на 13 часов, то когда она придет домой, и н

Простые числа
Простым называется целое число, большее единицы, единственными множителями которого является 1 и оно само: оно не делится ни на одно другое число. Два - это простое число. Простыми являются и 73, 2

Наибольший общий делитель
Два числа называются взаимно простыми,если у них нет общих множителей кроме 1. Иными словами, е с-ли наибольший общий делительа и п равен 1. Это записываетс

Обратные значения по модулю
Помните, что такое обратные значения? Обратное значение для 4 - 1/4, потому что 4*1/4 =1. В мире вычетов проблема усложняется: 4*х = 1 (mod 7) Это уравнение эквивалентно об

Квадратичные вычеты
Если/; - простое число, и а больше 0, но меньше р, то а представляет собой квадратичный вычет по модулю р, если х2 = a (mod/;), для некоторых

Символ Лежандра
Символ Лежандра, Ца,р), определен, если а - это любое целое число, а р - простое число, большее, чем 2. Он равен 0, 1 или-1. Ца,р) = 0, если а делится на р.

Символ Якоби
Символ Якоби, ](а,п), представляет собой обобщение символа Лежандра на составные модули, он определ я-ется для любого целого а и любого нечетного целого п. Функция удобна при п

Генераторы
Если р - простое число, и g меньше, чем р, то g называется генераторомпо модулю р, если для каждого числа Ъ от 1 тр - 1 существует

Квадратные корни по модулю п
Если п - произведение двух простых чисел, то возможность вычислить квадратные корни по модулю п вы­числительно эквивалентна возможности разложить число п на множители [1283, 35

Solovay-Strassen
Роберт Соловэй (Robert Solovay) и Фолькер Штрассен (Volker Strassen) разработали алгоритм вероятностной проверки простоты числа [1490]. Для проверки простоты числа р этот алгоритм использует

Lehmann
Другой, более простой тест был независимо разработан Леманном (Lehmann) [903]. Вот последовательность действий при проверке простоты числа р: (1) Выберите случайно число а, м

Rabin-Miller
Повсеместно используемым является простой алгоритм, разработанный Майклом Рабином (Michael Rabin), частично основанным на идеях Гэри Миллера [1093, 1284]. По сути, это упрощенная версия алгоритма,

Практические соображения
В реальных приложениях генерация простых чисел происходит быстро. (1) Сгенерируйте случайное и-битовое число/;. (2) Установите старший и младший биты равными 1. (Старший бит гаран

Сильные простые числа
Если п - произведение двух простых чисел, р и q, то может понадобиться использовать в качестве р и q сильные простые числа.Такие простые числа об

Вычисление дискретных логарифмов в конечной группе
Криптографы интересуются дискретными логарифмами следующих трех групп: — Мультипликативная группа полей простых чисел: G¥(p) — Мультипликативная группа конечных полей с

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

Принятие стандарта
Американский национальный институт стандартов (American National Standards Institute, ANSI) одобрил DES в качестве стандарта для частного сектора в 1981 году (ANSI X3.92.) [50], назвав его Алгоритм

Проверка и сертификация оборудования DES
Частью стандарта DES является проверка NIST реализаций DES. Эта проверка подтверждает, что реализ а-ция соответствует стандарту. До 1994 года NIST проверял только аппаратные и программно-аппаратные

Заключительная перестановка
Заключительная перестановка является обратной по отношению к начальной перестановки и описана в 4-й. Обратите внимание, что левая и правая половины не меняются местами после последнего этапа DES, в

Дешифрирование DES
После всех подстановок, перестановок, операций XOR и циклических сдвигов можно подумать, что алг о-ритм дешифрирования, резко отличаясь от алгоритма шифрования, точно также запутан. Напротив, разли

Режимы DES
FIPS PUB 81 определяет четыре режима работы: ЕСВ, СВС, OFB и CFB (см. главу 9) [1143]. Банковские стандарты ANSI определяют для шифрования ЕСВ и СВС, а для проверки подлинности - СВС и n-битовый CF

Аппаратные и программные реализации DES
Об эффективных аппаратных и программных реализациях алгоритма много писалось [997, 81, 533, 534, 437, 738, 1573, 176, 271, 1572]. Утверждается, что самой быстрой является микросхема DES, разработан

Ключи-дополнения
Выполним побитное дополнение ключа, заменяя все 0 на 1 и все 1 - на 0. Теперь, если блок открытого текста зашифрован оригинальным ключом, то дополнение ключа при шифровании превратит дополнение бло

Алгебраическая структура
Все возможные 64-битовые блоки открытого текста можно отобразить на 64-битовые блоки шифротекста 264! Различными способами. Алгоритм DES, используя 56-битовый ключ, предост

Количество этапов
Почему 16 этапов? Почему не 32? После пяти этапов каждый бит шифротекста является функцией всех б и-тов открытого текста и всех битов ключа [1078, 1080], а после восьми этапов шифротекст по сути пр

Проектирование S-блоков
Помимо уменьшения длины ключа NSA также обвиняют в изменении содержания S-блоков. Настаивая на подтверждении схемы S-блоков, NSA заявило, что детали алгоритма являются "чувствительными" и

Дополнительные результаты
Были предприняты и другие попытки криптоанализировать DES. Один из криптографов искал закономерн о-сти, используя спектральные тесты [559]. Другие анализировали последовательность линейных множител

Дифференциальный криптоанализ
В1990 году Эли Бихам и Ади Шамир ввели понятие дифференциального криптоанализа[167, 168, 171, 172]. Это был новый, ранее неизвестный метод криптоанализа. Используя

Криптоанализ со связанными ключами
В 9-й показано количество битов, на которые циклически смещается ключ DES на каждом этапе: на 2 бита на каждом этапе, кроме этапов 1, 2, 9 и 16, когда ключ сдвигается на 1 бит. Почему?

Линейный криптоанализ
Линейный криптоанализпредставляет собой другой тип криптоаналитического вскрытия, изобретенный Мицуру Мацуи (Mitsura Matsui) [1016, 1015, 1017]. Это вскрытие использует линейные пр

Дальнейшие направления
Был предпринят ряд попыток расширить концепцию дифференциального криптоанализа на дифференциалы более высоких порядков [702, 161, 927, 858, 860]. Ларе Кнудсен (Lars Knudsen) использует нечто, назыв

Многократный DES
В ряде реализаций DES используется трехкратный DES (см. 2-й) [55]. Так как DES e является группой, по­лученный шифротекст гораздо сложнее вскрыть, используя исчерпывающий поиск: 2 112 по

Обобщенный DES
Обобщенный DES (Generalized DES, GDES) был спроектирован для ускорения DES и повышения устойч и-вости алгоритма [1381, 1382]. Общий размер блока увеличился, а количество вычислений осталось неизме

MADRYGA
В.Е. Мадрига (W. E. Madryga) предложил этот блочный алгоритм в 1984 году [999]. Он может быть эффе к-тивно реализован как программа: в нем нет надоедливых перестановок, и все операции выполняются н

Описание Madryga
Madryga состоит из двух вложенных циклов. Внешний цикл повторяется восемь раз (но это количество м о-жет быть увеличено для повышения) и содержит применение внутреннего цикла к открытому тексту. Вн

Криптоанализ и Madryga
Исследователи из Технического университета в Квинсланде (Queensland University of Technology) [675] и с-следовали Madryga вместе с некоторыми другими блочными шифрами. Они обнаружили, что в этом ал

Описание FEAL
На 10-й представлена блок-схема одного этапа FEAL. В качестве входа процесса шифрования используется 64-битовый блок открытого текста. Сначала блок данных подвергается операции XOR с 64 битами ключ

Криптоанализ FEAL
Успешный криптоанализ FEAL-4, FEAL с четырьмя этапами, был выполнен с помощью вскрытия с выбра н-ными открытыми текстами [201], а позже слабость этого алгоритма была показана в [1132]. Последнее вс

Патенты
FEAL запатентован в Соединенных Штатах [1438], соответствующие патенты приняты к рассмотрению в Англии, Франции и Германии. Желающий лицензировать использование алгоритма должен связаться с Дера п-

REDOC III
REDOC представляет собой упрощенную версию REDOC II, также разработанную Майклом Вудом [1615]. Он работает с 80-битовым блоком. Длина ключа может меняться и достигать 2560 байтов (20480 битов). Алг

Описание LOKI91
Механизм LOKI91 похож на DES (см. Рис. 13-8). Блок данных делится на левую и правую половины и пр о-ходит через 16 этапов, что очень походе на DES. На каждом этапе правая половина сначала подвергае

Криптоанализ LOKI91
Кнудсен предпринял попытку криптоанализа LOKI91 [854, 858], но нашел, что этот алгоритм устойчив к дифференциальному криптоанализу. Однако ему удалось обнаружить, что вскрытие со связанными ключами

Патенты и лицензии
LOKI не запатентован. Кто угодно может реализовать алгоритм и использовать его. Исходный код, прив е-денный в этой книге, написан в Университете Нового Южного Уэльса. При желании использовать эту р

KHUFU и KHAFRE
В 1990 году Ральф Меркл (Ralph Merkle) предложил два алгоритма. В основе их проектирования лежали следующие принципы [1071]: 1. 56-битовый размер ключа DES слишком мал. Так как стоимость у

Патенты
И Khufu, и Khafre запатентованы [1072]. Исходный код этих алгоритмов содержится в патенте. При желании получить лицензию на любой или оба алгоритма следует обратиться к директору по лицензированию

Скорость IDEA
Современные программные реализации IDEA примерно в два раза быстрее, чем DES. На компьютере с i386/33 МГц IDEA шифрует данные со скоростью 880 Кбит/с, а на компьютере с i486/33 МГц - со скоростью 2

Криптоанализ IDEA
Длина ключа IDEA равна 128 битам - более чем в два раза длиннее ключа DES. При условии, что наиболее эффективным является вскрытие грубой силой, для вскрытия ключа потребуется 2 128 (10

Патенты и лицензии
IDEA запатентован в Европе и Соединенных Штатах [1012, 1013]. Патент принадлежит Ascom-Tech AG. Для некоммерческого использования лицензирование не нужно. При заинтересованности в лицензии для ко м

Описание ГОСТ
ГОСТ является 64-битовым алгоритмом с 256-битовым ключом. ГОСТ также использует дополнительный ключ, который рассматривается ниже. В процессе работы алгоритма на 32 этапах последовательно выполняет

Криптоанализ ГОСТ
Вот главные различия между DES и COST. — DES использует сложную процедуру для генерации подключей из ключей. В ГОСТ эта процедура очень проста. — В DES 56-битовый ключ, а в ГОСТ -

BLOWFISH
Blowfish - это алгоритм, разработанный лично мной для реализации на больших микропроцессорах [1388, 1389]. Алгоритм незапатентован, и его код на языке С приведен в конце этой книги для широкого пол

Безопасность Blowfish
Серж Воденэ (Serge Vaudenay) исследовал Blowfish с известными S-блоками и г этапами, дифференциал ь-ный криптоанализ может раскрыть Р-массив с помощью 2 8Ж выбранных открытых текстов [15

Описание SAFER K-64
Блок открытого текста делится на восемь байтовых подблоков: Въ В2, . . . , Въ В%. Затем подблоки обрабаты­ваются в ходе г этапов. Наконец подблоки

SAFER K-128
Этот альтернативный способ использования ключа был разработан Министерством внутренних дел Синг а-пура, а затем был встроен Массеем в SAFER [1010]. В этом способе используются два ключа, Ка

Безопасность SAFER K-64
Массей показал, что SAFER K-64 после 6 этапов абсолютно защищен от дифференциального криптоанализа после 8 этапов и достаточно безопасен. Уже после 3 этапов против этого алгоритма становится неэффе

Описание S-Way
Этот алгоритм описать несложно. Для шифрования блока открытого текста х: For i = 0 to n - 1 х = х XOR Ki х = theta (х) х = pi - 1 (х) х = gamma (x) х = pi - 2

Сети Фейстела
Большинство блочных алгоритмов являются сетями Фейстела(Felstel networks). Эта идея датируется нача­лом 70-х годов [552, 553]. Возьмите блок длиной п и разделите его на две

Простые соотношения
DES обладает следующим свойством: если Е^Р) = С, то ЕК{РГ) = С, где Р', С" и К' - побитовые дополнения Р,СиК. Это свойство вдвое уменьш

Групповая структура
При изучении алгоритма возникает вопрос, не образует ли он группу. Элементами группы являются блоки шифротекста для каждого возможного ключа, а групповой операцией является композиция. Изучение гру

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

Проектирование блочного шифра
Проектировать блочный шифр нетрудно. Если вы рассматривает 64-битовый блочный шифр как перестано в-ку 64-битовых чисел, ясно, что почти все эти перестановки безопасны. Трудность состоит в проектиро

Luby-Rackoff
Майкл Любы (Michael Luby) и Чарльз Ракофф (Charles Rackoff) показали, что Каш не является безопасным [992]. Рассмотрим два одноблочных сообщения: АВ и АС. Если криптоаналитику известн

Шифр краткого содержания сообщения
Шифр краткого содержания coo6nieHM(Message Digest Cipher, M DC), изобретенный Питером Гутманном (Peter Cutmann) [676], представляет собой способ превратить однонаправленные хэш-функции в

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

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги