Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






Теория и практика стойкости шифра



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

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

Обычно эту мысль выражают так: противник с неограниченными ресурсами может вскрыть любой неабсолютно стойкий шифр.

Как же должен действовать в этой ситуации законный пользователь, выбирая для себя шифр? У пользователя остается единственный путь – получение практических оценок стойкости.

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

Два простейших методах вскрытия шифра:

- случайное угадывание ключа (он срабатывает с маленькой вероятностью, зато имеет маленькую сложность);

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

17. Без атаки на ключ

N Буква Относит. частота
пробел 0,175
о 0,090
е, ё 0,072
а 0,062
и 0,062
н 0,053
т 0,053
с 0,045
р 0,040
в 0,038
л 0,035
к 0,028
м 0,026
д 0,025
п 0,023
у 0,021
я 0,018
0,016
ы 0,016
б 0,014
ъ, ь 0,014
г 0,013
ч 0,012
й 0,010
x 0,009
ж 0,007
ш 0,006
ю 0,006
ц 0,004
щ 0,003
э 0,003
ф 0,002

 

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



Покажем зто на примере шифра замены, для которого уже давно разработаны методы вскрытия.

Шифр заменыматематически описывается с помощью некоторой подстановки g.

Такой шифр преобразует открытый текст в шифрованный по следующему правилу: каждая буква х заменяется на букву g(х).Вскрытие шифра основано на двух следующих закономерностях:
1) в осмысленных текстах любого естественного языка различные буквы встречаются с разной частотой, а действие подстановки g«переносит» эту закономерность на шифрованный текст;
2) любой естественный язык обладает так называемой избыточностью,что позволяет с большой вероятностью «угадывать» смысл сообщения, даже если часть букв в сообщении неизвестна.

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

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

18. Комбинаторные алгоритмы и ЭВМ

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

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

Многие полезные результаты носят характер «ухищрений» для ускорения алгоритмов и поэтому быстро входят в массовую практику программистов.

Особенно это относится к области комбинаторных алгоритмов,выросшей из типичных задач быстрого поиска и сортировки данных.



Отметим, что к области комбинаторных алгоритмов относятся также алгоритмы для хорошо известных игр-головоломок типа «кубика Рубика».

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

Модулярная арифметика

Модулярная арифметика часто изучается в школе как "арифметикачасов".

На часах со стрелками циферблат разделён на 12 частей, которые мы обозначим числами 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11. В следующей таблице можно видеть, как время на аналоговом циферблате соответствует времени после полудня на экране цифровых часов.

 

Когда мы говорим, например, что сейчас 14:00, мы можем также сказать, что сейчас два часа дня. Тот же принцип применяется и в случае измерения углов. Угол в 370 градусов равен углу в 10 градусов, потому что от первого значения мы должны вычесть полный оборот в 360 градусов.

Заметим, что 370 = (1 х 360) + 10, то есть остатком от деления 370 на 360. Какой угол эквивалентен углу в 750 градусов? Вычитая соответствующее количество полных оборотов, получим, что угол в 750 градусов равен углу в 30 градусов. Мы видим, что 750 = (2х360 + 30, то есть 30 является остатком от деления 750 на 360. В математике это обозначается так:

Ordm; 30 (mod 360)

Мы говорим: «750 сравнимо с 30 по модулю 360».

В случае с часами мы бы написали 14 º 2(mod 12).

Также можно представить себе часы с отрицательными числами. В этом случае, который будет час, когда стрелка показывает на (-7)? Или другими словами, с каким числом сравнимо число (-7) по модулю 12?

Давайте посчитаем, учитывая, что на наших часах с циферблатом, разделённым на 12 частей, значение 0 соответствует 12.

-7 = -7 + 12 = 5

Математика для расчётов на наших часа со стрелками, циферблат которых разделён на 12 частей, называется арифметикой по модулю 12.

Если отсчитать 14 часов от 3 часов после полудня, то получится 5 часов утра следующего дня:

Ordm; 5 (mod 12)

или

(3 +14) mod 12 = 5.

Это арифметика по модулю 12.

Обычная запись вмодулярной арифметике

a º b (mod n)

читается так: "a сравнимо с b по модулю n".

В общем случае мы говорим,что a º b (mod n),если остаток от деленияа на mравенb, при условии, что а, mиb– целые числа. Число b сравнимо с остатком от деления a на m.

Cледующие утверждения эквивалентны:

a º b (mod n)

b º a (mod n)

a - b º 0 (mod n)

а – bкратноm

Вопрос «Которому часу на часах со стрелками соответствует время 19 часов?» эквивалентен в математических терминах следующему вопросу: «С каким числом сравнимо число 19 по модулю 12?»

Для ответа на этот вопрос надо решить уравнение:

Ordm; Х (mod 12)

Разделив 19 на 12, получим частное 1 и остаток 7, поэтому

Ordm; 7 (mod 12)

Определим связь между модульной арифметикой и шифром ЦЕЗАРЯ.

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

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

 

Видно, что зашифрованное значение буквы по номером х ( в стандартном алфавите) буквой, стоящей на позиции (Х + 3) (также в стандартном алфавите).

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

С(х) = (х + 3) (mod 26),

Где: х – изначальное значение

С(х) – зашифрованное значение.

Теперь. Достаточно подставить вместо буквы её числовое значение и применить трансформацию.

Возьмём в качестве примера слово PLAY и зашифруем его.

Буква Р стоит на позиции 15, С(15) = 15 + 3 º 18 (mod 26 ), а число 18 соответствует букве S.

Буква L стоит на позиции 11, С(11) = 11 + 3 º 14 (mod 26 ), а число 14 соответствует букве O.

Буква A стоит на позиции 0, С(0) = 0 + 3 º 3 (mod 26 ), а число 3 соответствует букве D.

Буква Y стоит на позиции 24, С(24) = 24 + 3 = 27 (mod 26 ), а число 1 соответствует букве B.

Таким образом, слово РLAY , зашифрованное с ключом 3 превращается в слово SODB.

В общем случае, если х означает позицию буквы, которую мы хотим зашифровать (О для А, 1 для В, и т.д.) позиция зашифрованной буквы , обозначаемая С(х), выражается формулой:

С(х) = (х + k) (mod n),

Где: n – длина алфавита (26 в английском алфавите)

k– ключ, используемый в данном шифре.

Расшифровка такого сообщения включает в себя расчёты, обратные тем, что использовались для шифрования. В нашем примере расшифровка означает применение формулы, обратной той, что использовалась выше:

С-1 (х) =(х - k) (mod n),

В случае сообщения SODB, зашифрованного щифром Цезаря с ключом 3 с применением английского алфавита, то есть k = 3 и n = 26, мы получим:

С-1 (х) =(х - k) (mod 26),

Применим эту формулу следующим образом:

Для S: х = 18, С-1 (х) = 18 - 3 º 15 (mod 26), что соответствует букве P.

Для O: х = 14, С-1 (х) = 14 - 3 º 11 (mod 26), что соответствует букве L.

Для D: х = 3, С-1 (х) = 3 - 3 º 0 (mod 26), что соответствует букве A.

Для B: х = 1, С-1 (х) = 1 - 3 º -2 +26 º 24 (mod 26), что соответствует букве Y.

Сообщение SODB, зашифрованное шифром Цезаря с ключом 3, соответствует оригинальному тексту PLAY.

Это соотношение справедливо дляцелых значений a,b и n ¹ 0,

если, и только если

a = b + k * n

для некоторого целого k.

Отсюда, в частности, следует

n | (a – b).

Это читается как "n делит (a – b )".

Если a º b (mod n),

то b называют вычетом числа a по модулю n.

Операцию нахождения вычета числа a по модулю n

A (mod n)

называют приведением числа a по модулю n или приведением по модулю.

В нашем примере

(3 +14) mod 12 =17 mod 12 = 5

или

Ordm; 5 (mod 12),

число 5 является вычетом числа 17 по модулю 12.

Набор целых чисел от 0 до (n –1) называютполным набором вычетов по модулю n.

Это означает, что для любого целого a (a > 0) его вычет r по модулю n есть некоторое целое число в интервале от 0 до (n –1), определяемое из соотношения

r = a – k * n,

гдеk – целое число.

Например, для n =12 полный набор вычетов:

{0, 1, 2, …, 11}.


Эта страница нарушает авторские права

allrefrs.ru - 2019 год. Все права принадлежат их авторам!