Основы криптографии
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
дительной записки более часа времени. Ну, а предположим, что отправитель неизвестен? И это не беда, хотя потребует больше времени. Несложно перебрать несколько возможных имен, а в случае неудачи придется подставлять в разные места часто употребляемые слова текста и ключа - ТОВАРИЩ, ВЛАСТЬ, ВОССТАНИЕ. Отгадав одно из двух - текст или ключ, сразу получим второе.Мда неприятная вырисовывается картина однакотАж. Сразу становится как-то не по себе тАж получается что вскрывают чаще и проще чем можно подуматьтАжНо унывать не стоит- забегая вперед, скажу что есть нескрываемая системы криптографии- т.н. одноразовый блокнот, и в конце концов вскрыть 512 битовый клоч не так то уж легко и быстротАж Но об этом позжетАж.
А теперь настало время самой "труднопроходимой" части. Догадались? Правильно- на iену выходить её величество-математика, точнее
Теория информации
Современная теория информации впервые была опубликована в 1948 году Клодом Э. Шенноном (Claude Elmwood Shannon).
Энтропия и неопределенность
Теория информации определяет количество информации в сообщении как минимальное количество бит, необходимое для кодирования всех возможных значений сообщения, iитая все сообщения равновероятными. Например, для поля дня недели в базе данных достаточно использовать три бита информации, так как вся информация может быть закодирована 3 битами:
1.- Воскресенье
2.- Понедельник
010-Вторник
-Среда
-Четверг
101 -Пятница
-Суббота
- Не используется
Если эта информация была бы представлена соответствующими строками ASCII символов, она заняла бы больше места в памяти, но не содержала бы больше информации. Аналогично, поле базы данных "пол" содеpжит только один бит информации, хотя эта информация может храниться как одно из двух 7-байтовых ASCII строк: "МУЖЧИНА" или "ЖЕНЩИНА".
Формально, количество информации в сообщении M измеряется энтропией сообщения, обозначаемое как H(M). Энтропия сообщения, определяющего пол, составляет! бит, а энтропия сообщения, определяющего день недели, немного меньше, чем 3 бита. В общем случае энтропия сообщения, измеряемая в битах, равна log 2 n, где n - это количество возможных значений. При этом предполагается, что все значения равновероятны.
Энтропия сообщения также является мерой его неопределенности. Это количество битов открытого текста, которое нужно раскрыть в шифротексте сообщения, чтобы узнать весь открытый текст. Например, если блок шифротекста "QHP*5M " означает либо "МУЖЧИНА", либо "ЖЕНЩИНА", то неопределенность сообщения равна 1. Криптоаналитику нужно узнать только один правильно выбранный бит, чтобы раскрыть сообщение.
Норма языка
Для данного языка норма языка равна
r = H(M)/N
где N - это длина сообщения. При больших N норма обычного английского языка принимает различные зонaчения от 1.0 бит/буква до 1.5 бит/буква. Шеннон утверждает, что энтропия зависит от длины текста. Конкретно он показал, что норма для 8-буквенных блоков равна 2.3 бит/буква, но ее значение падает и находится между 1.3 и 1.5 для 16-буквенных блоков. Томас Кавер (Thomas Cover) использовал игровую методику оценки и обнаружил, что энтропия равна 1.3 бит/символ. Я буду использовать значение 1.3 Абсолютная норма языка равна максимальному количеству битов, которое может быть передано каждым символом при условии, что все последовательности символов равновероятны. Если в языке L символов, то абсолютная норма равна:
R = log2 L
Это максимум энтропии отдельных символов.
Для английского языка с 26 буквами абсолютная норма равна log 2 26, или около 4.7 бит/буква. Вас не должно удивлять, что действительная норма английского языка намного меньше, чем абсолютная - естественные языки обладают высокой избыточностью. Избыточность языка, обозначаемая D, определяется как:
D=R-r
iитая, что норма английского языка равна 1.3, избыточность составит 3.4 бит/буква. Это означает, что кaждая английская буква содержит 3.4 бита избыточной информации.
У сообщения ASCII, состоящего только из английских букв, количество информации на каждый байт составляет 1.3 бита. Значит, в каждом байте содержится 6.7 бита избыточной информации, что дает общую избыточность 0.84 бита информации на бит ASCII-текста и энтропию 0.16 бита информации на бит ASCII-текста. To же сообщение, набранное кодом BAUDOT, с 5 битами на символ, имеет избыточность 0.74 бита на бит и энтрoпию 0.26 бита на бит. Пробелы, пунктуация, числа и форматирование изменяют эти результаты.
Расстояние уникальности
Для сообщения длиной n число различных ключей, которые расшифруют шифротекст сообщения в какой-то осмысленный открытый текст на языке оригинального открытого текста (например, английском
Шеннон определил расстояние уникальности, U, называемое также точкой уникальности, как такое приближенное количество шифротекста, для которого сумма реальной информации (энтропия) в соответствующем открытом тексте плюс энтропия ключа шифрования равняется числу используемых битов шифротекста. Затем он показал, что имеет смысл iитать, что шифротексты, которые длиннее расстояния уникальности, можно расшифровать только одним осмысленным способом. Шифротексты, которые заметно короче расстояния уникальности, скорее всего, можно расшифровать несколькими способами, каждый из которых может быть правилен, и таким образом обеспечить безопасность, поставив противника перед выбором правил