28553

Примеры современных шифров проблема последнего блока DES

Доклад

Информатика, кибернетика и программирование

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

Русский

2013-08-20

26.44 KB

7 чел.

21 Примеры современных шифров проблема последнего блока DES

Проблемы DES

Так как длина ключа равна 56 битам, существует 256 возможных ключей. На сегодня такая длина ключа недостаточна, поскольку допускает успешное применение лобовых атак. Альтернативой DES можно считать тройной DES, IDEA, а также алгоритм Rijndael, принятый в качестве нового стандарта на алгоритмы симметричного шифрования.

Также без ответа пока остается вопрос, возможен ли криптоанализ с использованием существующих характеристик алгоритма DES. Основой алгоритма являются восемь таблиц подстановки, или S-boxes, которые применяются в каждой итерации. Существует опасность, что эти S-boxes конструировались таким образом, что криптоанализ возможен для взломщика, который знает слабые места S-boxes. В течение многих лет обсуждалось как стандартное, так и неожиданное поведение S-boxes, но все-таки никому не удалось обнаружить их фатально слабые места.

Алгоритм тройной DES

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

Недостатки двойного DES

Простейший способ увеличить длину ключа состоит в повторном применении DES с двумя разными ключами. Используя незашифрованное сообщение P и два ключа K1 и K2, зашифрованное сообщение С можно получить следующим образом:

C = Ek2 [Ek1 [P]]

Для дешифрования требуется, чтобы два ключа применялись в обратном порядке:

P = Dk1 [Dk2 [C]]

В этом случае длина ключа равна 56 * 2 = 112 бит.

Атака "встреча посередине"

Для приведенного выше алгоритма двойного DES существует так называемая атака "встреча посередине". Она основана на следующем свойстве алгоритма. Мы имеем

С = Ek2 [Ek1 [P]]

Тогда

X = Ek1 [P] = Dk2 [C].

Атака состоит в следующем. Требуется, чтобы атакующий знал хотя бы одну пару незашифрованный текст и соответствующий ему зашифрованный текст: (Р, С). В этом случае, во-первых, шифруется Р для всех возможных 256 значений K1. Этот результат запоминается в таблице, и затем таблица упорядочивается по значению Х. Следующий шаг состоит в дешифровании С, с применением всех возможных 256 значений K2. Для каждого выполненного дешифрования ищется равное ему значение в первой таблице. Если соответствующее значение найдено, то считается, что эти ключи могут быть правильными, и они проверяются для следующей известной пары незашифрованный текст, зашифрованный текст.

Если известна только одна пара значений незашифрованный текст, зашифрованный текст, то может быть получено достаточно большое число неверных значений ключей. Но если противник имеет возможность перехватить хотя бы две пары значений (незашифрованный текст - зашифрованный текст), то сложность взлома двойного DES фактически становится равной сложности взлома обычного DES, т.е. 256.

Тройной DES с двумя ключами

Очевидное противодействие атаке "встреча посередине" состоит в использовании третьей стадии шифрования с тремя различными ключами. Это поднимает стоимость атаки с известным незашифрованным текстом до 2168, которая на сегодняшний день считается выше практических возможностей. Но при этом длина ключа равна 56 * 3 = 168 бит, что иногда бывает громоздко.

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

C = EK1 [DK2 [EK1 [P]]]


Рис. 6. Шифрование тройным DES


Рис. 7. Дешифрование тройным DES

Не имеет большого значения, что используется на второй стадии: шифрование или дешифрование. В случае использования дешифрования существует только то преимущество, что можно тройной DES свести к обычному одиночному DES, используя K1 = K2:

C = EK1 [DK1 [EK1 [P]]] = EK1 [P]

Тройной DES является достаточно популярной альтернативой DES и используется при управлении ключами в стандартах ANSI X9.17 и ISO 8732 и в PEM (Privacy Enhanced Mail).

Известных криптографических атак на тройной DES не существует. Цена подбора ключа в тройном DES равна 2112.

Дифференциальный криптоанализ рассматривает отличия, которые происходят в каждой половине при шифровании. (Для алгоритма DES "отличия" определяются с помощью операции XOR, для других алгоритмов возможен иной способ). Выбирается пара незашифрованных текстов с фиксированным отличием. Затем анализируются отличия, получившиеся после шифрования одним раундом алгоритма, и определяются вероятности различных ключей. Если для многих пар входных значений, имеющих одно и то же отличие Х, при использовании одного и того же подключа одинаковыми (Y) оказываются и отличия соответствующих выходных значений, то можно говорить, что Х влечет Y с определенной вероятностью. Если эта вероятность близка к единице, то можно считать, что подключ раунда найден с данной вероятностью. Так как раунды алгоритма независимы, вероятности определения подключа каждого раунда следует перемножать. Как мы помним, считается, что результат шифрования данной пары известен. Результаты дифференциального криптоанализа используются как при разрабоке конкретных S-box, так и при определении оптимального числа раундов.

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

P[1], … , P[n] - незашифрованный блок сообщения.
C[1], … , C[n] - зашифрованный блок сообщения.
K[1], … , K[m] - ключ.
A [i, j, …, k] = A[i]
A[j] A[k]

Целью линейного криптоанализа является поиск линейного уравнения вида
P [α
1, α2, …, αa] C [β1, β2, …, βb] = K [γ1, …, γc]

Выполняющееся с вероятностью р ≠ 0.5. αi, βi и γi - фиксированные позиции в блоках сообщения и ключе. Чем больше р отклоняется от 0.5, тем более подходящим считается уравнение.

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

Уравнения составляются следующим образом. Вычисляются значения левой части для большого числа пар соответствующих фрагментов незашифрованного и зашифрованного блоков. Если результат оказывается равен нулю более чем в половине случаев, то полагают, что K [γ1, …, γс] = 0. Если в большинстве случаев получается 1, полагают, что K [γ1, …, γс] = 1. Таким образом получают систему уравнений, решением которой является ключ.

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


 

А также другие работы, которые могут Вас заинтересовать

82255. Рождение знания в процессе взаимодействия коммуницирующих индивидов. Распространение и борьба научных идей. Индоктринация 32.16 KB
  Важную роль в развитии социальногуманитарных науках играет коммуникация ученых диалог между ними. Механизмом их преодоления является постоянный диалог ученых представителей разных школ в социальногуманитарных науках. Диалог является важнейшим видом коммуникации и представляет собой попеременный обмен высказываниями репликами между двумя или более ученымигуманитариями. Диалог может представлять собой определенную дискуссию беседу диспут и т.
82256. Рациональное, объективное, истинное в социально-гуманитарных науках 28.02 KB
  Социальное познание является частным видом научного познания подчиняющимся его критериям и законам. Социальное познание неразрывно связано с предметными справедливо несправедливо добро зло субъективными установки взгляды нормы цели ценностями на основе которых осуществляется познание объекта. Таким образом социальное познание объективно так как изучение объекта общества на определенном этапе развития происходит на основе объективных критериев и законов характерных для научного познания в целом. Социальное познание рационально...
82257. Классическая и неклассическая концепция истины. Экзистенциальная истина, истина и правда 39.28 KB
  Стержень классической концепции истины принцип соответствия знания действительности. Исследования показали возможность применения классической концепции истины к любым мыслимым мирам но в этом случае она должна быть уточнена следующим образом. Для классической концепции истины характерны следующие принципы: действительность не зависит от мира знания; между нашими мыслями и действительностью можно установить однозначное соответствие; существует критерий установления соответствия мыслей действительности; сама теория соответствия...
82258. Проблемы истины в свете практичкского применения. Плюрализм и социологическое требование отсутствия монополии на истину 38.38 KB
  Так что же такое истина Имеются разные понимания истины. Вот некоторые из них: Истина это соответствие знаний действительности; Истина это опытная подтверждаемость; Истина это свойство самосогласованности знаний; Истина это полезность знания его эффективность; Истина это соглашение. Первое положение согласно которому истина есть соответствие мыслей действительности является главным в классической концепции истины.
82259. Объяснение и понимание как следствие коммуникативности науки. Природа и типы объяснений. Объяснение как функция теории и её результат 37.73 KB
  Понимание нельзя смешивать с тем что называют озарением инсайтом интуицией хотя все это есть в процессе понимания. Наряду с описанием объяснением истолкованием интерпретацией понимание относится к основным процедурам функционирования научного знания. Поэтому понимание не следует отождествлять с познанием понять значит выразить в логике понятий или смешивать с процедурой объяснения хотя они и связаны между собой.
82260. Понимание в гуманитарных науках, необходимость обращения к герминевтике как « органону наук о духе»(В.Дильтей, Г.Гадамер) 39.83 KB
  Дильтей 1833-1911 который предпринял попытку расширить герменевтику до ее понимания как общенаучной философской дисциплины. Понимание внутреннего мира осуществляется при помощи интроспекции а для понимания культуры прошлого необходима герменевтика. Два вида понимания рассуждал Дильтей отражают собой два имеющихся комплекса наук: наук о духе и наук о природе. Концепцию логических форм интерпретации Дильтей предваряет исследованием проявлений жизни и форм понимания.
82261. Объяснение и понимание в социологии, исторической, экономической и юридической науках, психологии, филологии, культурологи 33.73 KB
  Степина в качестве ведущих элементов структуры теории рассматриваются теоретические схемы представленные относительно независимо в языке содержательного описания либо в форме математических зависимостей на языке формул. Так основание физической теории составляют математический формализм первый слой фундаментальная теоретическая схема второй слой они всегда взаимообусловлены. Развитая теория строится на основе синтеза частных теоретических схем которые предстают как выводимые или конструируемые из фундаментальной теоретической схемы...
82262. Герменевтика – наука о понимании и интерпритации текста. Текст как особая реальность и «еденица» анализа социально – гуманитарного знания 37.79 KB
  Изначальная многозначность любого текста а она характерна даже для научных текстов что обыгрывается в современном постмодернизме становится в философии предметом особого направления которое обозначается как герменевтика. Внешне общая парадигма герменевтических устремлений реализуется в антисциентистском направлении но не в плане простого отказа от использования научной методологии при исследовании текста а в плане утверждения идеи о необходимости обязательного дополнения такого исследования субъективистскими компонентами. Сами тексты...
82263. Язык социально-гуманитарных наук. Языковая картина мира и «языковые игры» 34.44 KB
  проблемы природы языка принципов и законов его функционирования начинают изучаться лингвистами логиками психологами и философами. Таким образом для языкознания важными вопросами становятся вопросы семантики а также проблемы взаимосвязи языка и мышления языка и предметного мира. Так швейцарский лингвист Фердинанд де Соссюр 18571913 указывает на то что предметом изучения лингвистики становится имманентная реальность языка. Также проблемы языка в первую очередь выдвигаются в логике.