Файл: Руководство для профессиональных аналитиков москва 2009 rv удк 001. 51 Ббк72 с 40.pdf

Шифрование информации - взаимнооднозначное математическое (криптографическое) преобразование, зависящее от ключа
(секретный параметр преобразования), которое ставит в соответствие блоку открытой информации, представленной в некотором цифровом представлении, блок шифрованной информации, также представленной в цифровом представлении. Термин шифрование объединяет в себе два процесса: зашифрование и расшифрование информации.
Шифратор - аппарат или программа, реализующая шифр. В современной литературе вводится понятие
«средства криптографической защиты информации», которое включает в себя шифратор, но в целом является более широким.
Ключ - некоторый неизвестный параметр шифра, позволяющий выбрать*для шифрования и расшифрования конкретное преобразование из всего множества преобразований, составляющих шифр.
Простая ассоциация - ключ от замка - во многом проясняет смысл термина. Есть много качественно одинаковых ключей, но лишь некоторые (или один) откроют замок.
Шифрование - процесс получения шифрованного текста, основанный на знании ключа.
Дешифрование - восстановление открытого текста или ключа по шифрованному тексту.
Злоумышленник- субъект (или физическое лицо), не знающий ключа или открытого текста и стремящийся его получить. Злоумышленник в криптографии является конкретизацией злоумышленника для КС - в данном случае это некто, пытающийся выполнить атаку и прочитать зашифрованные данные.
Понятие «злоумышленник» в криптографии тесно связано с понятием «твердого незнания» ключа. В соответствии с методологией, принятой в современной криптографии, надежность шифра определяется степенью безопасности используемых в ней ключей, поскольку все долговременные элементы криптографической системы
(множество правил шифрования, его механизм) рано или поздно станут известными злоумышленнику. Этот прин-
374 цип был сформулирован еще в конце XIX в. и получил название «правила Кирхгофа» (Kerckhoffs' desiderata).
В современной криптографии считается также, что злоумышленник имеет возможность также произвольным образом изменять сообщения. Поэтому вводится еще один термин.
Подлинность
- принадлежность сообщения конкретному автору и неизменность содержания сообщения.
Пусть имеется некоторое множество X. Назовем его исходным множеством или множеством открытых текстов. Это могут быть, например, тексты, содержащие финансовые, торговые, политические сведения и передаваемые на некотором языке с помощью двоичных векторов или целых чисел. Чаще всего X полагается множеством векторов длины п, каждая его координата может принадлежать множеству М, которое называется алфавитом.
Зададим также множество У - другое множество, которое назовем множеством зашифрованных текстов.
Его также удобно представлять множеством векторов длины т, причем каждая координата вектора принадлежит множеству S. Это множество может совпадать с М или быть отличным от него. В первом случае при шифровании буквы текста отображаются в другие буквы, во втором случае для представления шифрованного текста используются символы другого алфавита, например, «пляшущие человечки».
Зададим также множество К - множество параметров преобразования или множество ключей.
Данный параметр задает, какое именно преобразование будет использовано.
Далее введем некоторое отображение Е множества X на множество У, зависящее от параметра к из множества К:
Е(к, х) = у,
где к принадлежит К; х принадлежит X; у принадлежит
У; причем для любого хиз X существует отображение D,
также зависящее от параметра к:
375

D(E(k, x)) = x, и х определяется однозначно.
Данное условие говорит о том, что после расшифрования D должен получиться тот нее самый исходный текст, а не какой-либо другой.
Отображение Е назовем шифрующим отображением, a D - расшифровывающим отображением. Вместо
«отображения» в литературе по криптографии используется также термин «преобразование». В литературе по криптографии еще используются следующие обозначения:
Ек{) - функция зашифрования на ключе к,
DkQ - функция расшифрования на ключе к.
Из этого определения можно сделать следующие выводы:
1. Мощность множества (количество элементов мно жества) X всегда не больше мощности множества У, по скольку в противном случае невозможно добиться одно значного отображения Y в X и получить однозначного расшифрования.
2. При любом фиксированном к отображение Е вза имно однозначно.
Однако в сформулированном определении мы ничем не выделили шифры среди прочих преобразований информации. Поэтому сформулируем дополнительные свойства:
1. Множество if должно иметь мощность, достаточ ную, чтобы невозможно было осуществить перебор всех различных преобразований Е.
2. По у=Е{к,х) было бы очень трудоемко определить как х, так и к.
Даже дополнив основное определение данными свойствами, мы не может утверждать, что шифр будет
«хорошим».
Данные требования являются необходимыми, но недостаточными - мы не можем быть абсолютно уверенными в том, что по у определить к или х действительно «очень трудоемко».
Пример 1
Пусть х , у
х
и k
t
принадлежат {0,1}.
Операция # задается таб. 21:
Таблица 21
#

действия подстановки
р.
Если существуют статистические закономерности исходного текста, то они сохранятся в шифртексте, но уже для образов соответствующих символов.
К статистическим закономерностям текста относятся частоты встречаемости отдельных букв, сочетаний букв и отдельных слов. Например, искусственное слово
«СЕНОВАЛИТР» означает расположение букв русского языка по убыванию частоты их встречаемости в
«среднем» тексте. Не будем смеяться над гениальным математиком Эйлером - он будет прав, если нам не удастся набрать нужной статистики на шифрованном тексте. Почему этого не произойдет? Потому, что символов шифртекста будет немного. Для установления сколько-нибудь достоверных статистических оценок нужно не меньше символов, чем мощность алфавита.
Увеличим алфавит - например, каждая «буква» файла будет последовательностью из 64 бит. Тогда на реальных объемах данных мы почти никогда не получим достоверной статистики. В этом состоит идея блочного шифрования.
Оценивая качество шифрующего отображения В,
мы должны задаться конкретными условиями. В этих условиях желательно добиться выполнения условия 2 определения шифра, а именно, чтобы по у - шифртек- сту или по паре у и х - зашифрованному и открытому тексту - найти параметр преобразования к было бы достаточно трудоемко.
Можно сформулировать несколько типовых классов задач, которые решает злоумышленник для нахождения открытых текстов или ключей:
• нахождение ключа только по шифртексту (а значит в силу обратимости отображения Е и открытого текста х- по уравнению х=Щк, у);
• нахождение открытого текста по шифртексту без нахождения ключа шифрования;
• нахождение ключа к по паре х и у, связанной соот ношением у=Е(к, х), или нескольким таким парам;
• нахождение некоторых х для известных совокуп ностей пар (х, у), таких что: у=Е(к, х), т.е. для текстов, зашифрованных при помощи одного ключа.
378
Первая задача решается, когда злоумышленник наблюдает за информацией, циркулирующей во внешнем сегменте КС, и желает определить ключ, использованный для шифрования перехваченной им информации. Вторая - когда ключ не интересует злоумышленника, а интересует только переданный открытый текст, третья -когда известен какой-либо переданный открытый текст, соответствующий перехваченному шифрованному тексту, а четвертая - когда известно, что несколько сообщений зашифровано на одном и том же ключе.
Поясним сформулированные задачи примерами.
Пример 3
Наиболее непонятной с точки зрения здравого смысла является задача 3. Казалось бы, откуда может взяться хдля у=Е(к, х)?
Предположим, однако, что текст х общеизвестен - например, среди зашифрованных на одном ключе файлов есть программа, которая есть у всех, например, упоминаемый нами Win.Word.exe. Следовательно, найдя в этом случае ключ, мы восстановим все файлы. При передаче данных по каналу связи может возникнуть ситуация, когда большая часть текста также известна - передается платежная ведомость вполне определенной структуры либо запрос типа «На Ваш исходящий - наш входящий ...". Таким образом, в большинстве систем хранения и передачи информации необходимо обеспечить высокую трудоемкость решения задачи 3.
Пример 4
Нахождение открытого текста для двух телеграмм, зашифрованных на одном ключе методом наложения ключа при помощи операции #. В этом и последующих примерах используется ASCII-кодировка, в которой для кодирования буквы используется один байт, а номер символа приведен в шестнадцатеричном обозначении, т.е. для «цифры» 9 используется обозначение латинской буквой «а», а для 15 - соответственно «/».
379

Рассмотрим схему шифрования
у = к#х
Случайный ключ длиной 21 байт:
К= 5 с 17 7f e 4е 37 d2 94 10 9 2е 22 57 ff c8 b Ь2 70 54
Телеграмма 1.
Т1=Н а в а ш и с х о д я щ и й о т 1 2 0 4
Tl=8d аО 82 аО е8 а8 el e5 ae a4 ef е9 а8 а9 ае е2 31 32 30 34
Телеграмма 2.
Т2= в С е в е р н ы й ф и л и а л Б а н к
Т2= 82 91 а5 а2 а5 еО ad eb a9 e4 a8 ab а8 аО ab 81 аО ad aa
Y1=T1#K =
88 ас 95 df еб еб d6 37 За Ь4 еб с7 8а fe 51 2а За 80 40 60
Y2= T2#K =
87 9d Ь2 dd ab ае 9а 39 3d f4 al 85 8а f7 54 49 ab If da f4
Рассмотрим Z = Y1+Y2 = T1+K+T2+K = T1+T2
Z= Y1#Y2 =
»
f 31 27 2 4d 48 4c e 7 40 47 42 0 9 5 63 91 9f 9a 94 0
Предположим теперь, что телеграмма начинается со слов:
"Наваш ..."
8d аО 82 аО е8
Сложим это сообщение с текстом Z:
f31 27 2 4d
8d аО 82 аО е8 82 91а5а2а5
В С е в е
По-видимому, это слово «Северный", тогда, действуя описанным образом в Т1, получим «исхо» по-видимому
«исходящий", в Т2 читаем: «филиа» - «филиал". Таким образом, мы, скорее всего, прочитаем обе телеграммы.
Введем теперь интуитивно ясное понятие стойкости шифра, описывающее сложность преобразования Е относительно задачи нахождения параметра преобразования.
Итак,
стойкость
шифрующего преобразования - трудоемкость задачи
нахождения параметра преобразования ключа к либо
текста X при тех или иных условиях (например, из тех, что были сформулированы выше).
Понятие трудоемкости связано с понятием алгоритма, т.е. полагается, что для нахождения ключа к строится некоторый алгоритм, и стойкость оценивается его трудоемкостью. С другой стороны, ниже мы увидим, что иногда алгоритм нахождения ключа или исходного текста будет порождать несколько ключей или несколько осмысленных текстов, среди которых также придется выбирать (а иногда выбор просто невозможен).
Рассмотрим идеальный случай, при котором шифр является абсолютно стойким, т.е. текст х найти невозможно. Клод Шеннон сформулировал условия для такого шифра. Эти условия, в общем, достаточно логичны - при перехвате некоторого зашифрованного текста злоумышленник не должен получить никакой информации о переданном открытом тексте.
Введем следующие обозначения:
р(х/у) - вероятность того, что зашифрован текст х
при перехвате текста у;
р(у/х) - вероятность того, что при условии зашифрования х получен был именно у - или суммарная вероятность использования всех ключей, которые переводят х
вг/;
р(у) - вероятность получения криптограммы у;
р(х) - вероятность взятия для зашифрования текста
х из множества возможных.
Для того чтобы злоумышленник не получил никакой информации о ключе или об открытом тексте необходимо и достаточно, чтобы:
р(х) = р(х/у),
т.е. вероятность выбора текста для шифрования из множества возможных текстов не изменилась бы при получении криптограммы, соответствующей данному тексту. По формуле Байеса:
р(х)р(у/х) Р(У)
Из равенства р(х) = р(х/у)
следует р(у) = р(у/х), т.е. суммарная вероятность всех ключей, переводящих х в у,
380 381
Р(х/у) =

должна быть равна вероятности получения криптограммы у и не должна зависеть от х.
Из этого равенства следуют также два важных следствия:
• число всевозможных ключей не должно быть мень ше числа сообщений,
• для каждого у должен найтись ключ к, который переводит любой х в данный у (так называемое условие криптографической транзитивности), в противном слу чае, получив конкретный шифртекст у, можно будет ис ключить из рассмотрения некоторые ключи или откры тые тексты.
Эти условия являются необходимыми, т.е. невыполнение хотя бы одного из них делает шифр не абсолютно стойким.
Пусть л:, у
Р
fc принадлежат {0,1}.
у=х#к - шифрование,
х=у#к - расшифрование.
Пусть рассматриваются сообщения длины I, все меньшие сообщения дополняются до длины I хаотической информацией. Ключ if-двоичный вектор длины L, и он выбирается случайно равновероятно из множества возможных векторов длины L. Такая система шифрования будет абсолютно стойкой по Шеннону.
Можно при этом попытаться возразить, а что если перебрать все ключи длиной I. Ведь мы же получим нужное сообщение. Безусловно, но оно будет далеко не единственным осмысленным сообщением среди полученных перебором ключей.
Пример 5
Вот Ключ Центра:
5 с 17 7f е 4е 37 d2 94 10 9 2е 22 57 ff c8 b Ь2 70 54 If
Вот сообщение Центра:
Штирлиц - вы Герой!!
98 е2 а8 еО ab а8 еб 20 2d 20 82 eb 20 83 а5 еО ае а9 21 21
Вот криптограмма, находящаяся у Мюллера.
Y=T#K=
9d ее bf 9f а5 еб dl f2 Ь9 30 8b c5 2 d4 5a 28 а5 lb 51 75
Вот дешифровалыцики попробовали ключ 1:
5 с 17 7f e 4е 37 d2 94 10 9 2е 22 75 f4 83 7 bb fc 54 If и получили текст:
98 е2 а8 еО ab а8 еб 20 2d 20 82 eb 20 al ае ab a2 a0 ad 21
Штирлиц - вы болван!
А вот дешифровалыцики попробовали ключ 2:
с се 12 31 7 d 7d d2 la 9e 2f 6b ae f8 fe c8 46 be bd 9a If и получили текст:
91 20 ad ae a2 eb ас 20 аЗ ае а4 ае ас 2с а4 еО еЗ а7 ее ef
Сновымгодом, друзья
Пробуя новые ключи, они будут видеть все новые и новые фразы, пословицы, стихотворные строфы, гениальные откровения - словом, всевозможные тексты заданной длины.
До сих пор мы рассматривали системы шифрования, основанные на ключе, который знают и отправитель, и получатель сообщения.
Чтобы отправитель и получатель узнали свой ключ, его нужно им доставить, причем так, чтобы сохранить его в тайне от всех других. Для практических аналитиков весьма важно знать, что используемый алгоритм шифрования должен быть приближающимся к абсолютно стойкому, к тому нее необходимо вырабатывать новый ключ для шифрования каждого нового сообщения.
Очень привлекательным со всех точек зрения было бы вырабатывать ключ для каждого сообщения. Однако понятно, что детерминированные алгоритмы для этого не годятся - злоумышленник может прогнозировать ключи. Но если мы будем вырабатывать ключи каждый раз случайно, то как оповестить об этом своего корреспондента? Решение проблемы - в односторонних
(однонаправленных) функциях. Функцию y
=
f(x) назовем односторонней, если вычисление у по х имеет малую трудоемкость, а вычисление х по у - высокую.
Односторонние функции чаще всего связаны с возведением в степень
(обратная функция
- логарифмирование). Надо отметить, что полагаемая из общих соображений «односторонность» функции часто впоследствии не подтверждается. Это связано либо с появлением новых математических методов, либо с появление мощной вы-
382 383