Основы криптографии
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
ьного открытого текста.
Для большинства симметричных криптосистем расстояние уникальности определяется как энтропия криптoсистемы деленная на избыточность языка.
U = H(K)/D
Расстояние уникальности является не точным, а вероятностным значением. Оно позволяет оценить минимальное количество шифротекста, при вскрытии которого грубой силой имеется, вероятно, только один разумный способ дешифрирования. Обычно чем больше расстояние уникальности, тем лучше криптосистема. Для DES с 56-битовым ключом и англоязычного сообщения, записанного символами ASCII, расстояние уникальности приблизительно равно 8.2 символа ASCII или 66 бит. В приведены расстояния уникальности для различных длин ключа.
Расстояние уникальности измеряет не количество криптотекста, нужного для криптоанализа, а количество криптотекста, необходимое для единственности результата криптоанализа. Криптосистема может быть вычиcлительно неуязвима, даже если теоретически ее возможно взломать, используя малое количество шифротекста. Расстояние уникальности пропорционально избыточности. Если избыточность стремится к нулю, даже тривиальный шифр может не поддаться вскрытию с использованием только шифротекста.
Табл. 1. Расстояния уникальности текста ASCII, зашифрованного алгоритмами с различной длиной ключа
Длина ключа (в битах)Расстояние уникальности (в символах)
5^9
8.2
9.4
11.8
18.8
37.6
Шеннон определил криптосистему с бесконечным расстоянием уникальности, как обладающую идеальной тайной. Обратите внимание, что идеальная криптосистема не обязательно является совершенной, хотя совеpшенная криптосистема обязательно будет и идеальной. Если криптосистема обладает идеальной тайной, то даже при успешном криптоанализе останется некоторая неопределенность, является ли восстановленный открытый текст реальным открытым текстом.
Путаница и диффузия
Двумя основными методами маскировки избыточности открытого текста сообщения, согласно Шеннону, служат путаница и диффузия.
Путаница маскирует связь между открытым текстом и шифротекстом. Она затрудняет попытки найти в шифротексте избыточность и статистические закономерности. Простейшим путем создать путаницу является подстановка. В простом подстановочном шифре, например, шифре Цезаря, все одинаковые буквы открытого текста заменяются другими одинаковыми буквами шифротекста. Современные подстановочные шифры являются более сложными: длинный блок открытого текста заменяется блоком шифротекста, и способ замены меняется с каждым битом открытого текста или ключа. Такого типа подстановки обычно недостаточно - сложный алгоритм немецкой Энигмы был взломан в ходе второй мировой войны.
Диффузия рассеивает избыточность открытого текста, распространяя ее по всему шифротексту. Криптоанaлитику потребуется немало времени для поиска избыточности. Простейшим способом создать диффузию является транспозиция (также называемая перестановкой). Простой перестановочный шифр только переставляет буквы открытого текста. Современные шифры также выполняют такую перестановку, но они также используют другие формы диффузии, которые позволяют разбросать части сообщения по всему сообщению.
Потоковые шифры используют только путаницу, хотя ряд схем с обратной связью добавляют диффузию. Блочные алгоритмы применяют и путаницу, и диффузию. Как правило, диффузию саму по себе несложно взломать (хотя шифры с двойной перестановкой оказываются поустойчивее, чем другие некомпьютерные системы, но об этом мы кажется уже говорили).
Арифметика вычетов
Вы все учили математику вычетов в школе.Если Маша сказaла, что она будет дома к 10:00, и опоздала на 13 часов, то когда она придет домой, и на сколько лет отец лишит ее водительских прав? Это арифметика по модулю 12. Двадцать три по модулю 12 равно 11.
(10 + 13) mod 12 = 23 mod 12 = 11 mod 12
Другим способом записать это является утверждение об эквивалентности 23 и 11 по модулю 12:
+13 = ll(modl2)
В основном, а = b (mod n), если а = b + kn для некоторого целого k. Если а неотрицательно и b находится между 0 и и, можно рассматривать b как остаток при делении а на п. Иногда, b называется вычетом а по модулю п. Иногда а называется конгруэнтным b по модулю n (знак тройного равенства, =, обозначает конгруэнтность). Одно и то же можно сказать разными способами.
Множество чисел от 0 до n-\ образует то, что называется полным множеством вычетов по модулю п. Это означает, что для любого целого а, его остаток по модулю n является некоторым числом от 0 до n-1.
Операция a mod n обозначает остаток от а, являющийся некоторым целым числом от 0 до n-1. Эта операция называется приведением по модулю. Например, 5 mod 3 = 2.
Это определение mod может отличаться от принятого в некоторых языках программирования. Например, оператор получения остатка в языке PASCAL иногда возвращает отрицательное число. Он возвращает число между -(и-1) и n-\. В языке С оператор % возвращает остаток от деления первого выражения на второе, оно может быть отрицательным числом, если любой из операндов отрицателен. Для всех алгоритмов, проверяйте, что вы добавляете n к результату операции получения остатка, если она возвращает отрицательное число.
Арифметика остатков очень похожа на обычную арифметику: она коммутативна, ассоциативна и дистрибyтивна. Кроме того, приведение каждого промежуточного результата по модулю n дает тот же результат, как и выполнение всего вычисления с последующим п?/p>