Анин Б.Ю. Защита компьютерной информации

Подождите немного. Документ загружается.

Найти:

, Р

, ..., Р

или К

, К

, ...,K

2. Атака со знанием открытого текста. Криптоаналитик имеет доступ

не только к шифрованным текстам нескольких сообщений, но и знает

их открытые тексты. От него требуется найти ключи, которые

использовались для шифрования этих сообщений.

Дано:

Найти:

, ...,K

3. Атака с выбранным открытым текстом. Криптоаналитик не только

знает шифрованные и открытые тексты нескольких сообщений, но и

может определять содержание этих сообщений. Данная разновидность

крипто-аналитической атаки является более мощной по сравнению с

атакой со знанием открытого текста, поскольку здесь криптоаналитик

может по своему усмотрению выбирать открытый текст, подлежащий

зашифрованию, и, тем самым, получать больше информации об

используемых ключах. Его задача по-прежнему состоит в нахождении

ключей.

Дано:

, C

= E

, K

, ..., K

.), P

, C

= E

), …, P

где С

= Е

), где P

, P

, ... , P

выбраны криптоаналитиком.

Найти: K

, K

, ..., K

4. Адаптивная атака с выбранным открытым текстом. Эта атака

является разновидностью атаки с выбранным открытым текстом.

Криптоаналитик не только выбирает открытые тексты посылаемых

шифрованных сообщений, но и может менять свой выбор в

зависимости от результатов их шифрования.

Имеются по крайней мере еще 3 разновидности криптоаналитических

атак.

1. Атака с выбранным шифртекстом. Криптоаналитику предоставлена

возможность выбора шифртекстов, подлежащих расшиф рованию

получателем. Он также имеет доступ к соответствующим открытым

текстам. Требуется найти ключи.

101

Дано:

, P

= D

), С

, P

= D

), ..., C

, P

= D

Найти :

, K

, ..., K

. Этой криптоаналитической атаке, как правило,

подвергаются алгоритмы шифрования с открытым ключом. Хотя

иногда она эффективна и против симметричных криптосистем . Атаку с

выбранным открытым текстом и с выбранным шифртектом называют

атакой с выбранным текстом.

2. Атака с выбранным ключом. В ходе этой атаки криптоаналитик

обладает некоторыми знаниями относительно правил, по,которым

отправитель и получатель сообщений выбирают ключи шифрования.

3. Атака с применением грубой силы. Криптоаналитик занимается

подкупом, шантажом или пытками, чтобы получить сведения,

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

выделяют в отдельную категорию и называют атакой с покупкой

ключа. Эти атаки являются очень эф фективными и зачастую

предоставляют наиболее легкий путь для получения доступа к

открытым текстам шифрованных сообщений.

Атаки со знанием открытого текста и с выбранным открытым текстом не

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

когда криптоаналитику удавалось подкупить шифровальщика, чтобы он

зашифровал сообщение, открытый текст которого известен криптоаналитику.

Иногда даже не требуется никого подкупать, поскольку открытые тексты

многих сообщений начинаются и заканчиваются стандартными фразами.

С этой точки зрения зашифрованная программа на языке С особенно

уязвима, поскольку содержит множество зарезервированных слов типа

#define, # include, if, then и do.

He следует забывать и о правиле Керкхоффа. Попытка добиться высокой

надежности криптографического алгоритма за счет сохранения в тайне

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

выполнить дизассемблирование любой сверхсложной программы шифрования

и методом обратного проектирования воспроизвести алгоритм, положенный в

основу ее функционирования. Такое случается довольно часто. Лучшие

алгоритмы шифрования являются общественным достоянием уже в течение

многих лет, и над их взломом продолжают безуспешно трудиться самые

способные криптоаналитики в мире.

102

Надежность алгоритма шифрования

Различные криптографические алгоритмы обладают разной надежностью,

чаще называемой стойкостью алгоритма шифрования или стойкостью

шифра. Стойкость зависит от того, насколько легко криптоаналитик может

взломать шифр. Если при этом стоимость затрат превышает ценность

полученной в результате информации, то владельцу этого шифра, возможно, и

беспокоиться не о чем. Если время, потраченное на взлом шифра, больше, чем

период, в течение которого ваши данные должны храниться в секрете, то они

вероятно вне опасности. Если противник не накопил достаточного количества

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

определить этот ключ, время его менять, может быть, еще и не пришло.

Слова “мож ет быть”, “вероятно” и “возможно” употреблены здесь не зря.

Ведь всегда существует шанс, что в криптоанализе произойдут революционные

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

прорыва поможет соблюдение простого правила: ценность секретных данных

должна быть всегда ниже, чем стоимость преодоления защитных средств,

используемых для сохранения этих данных в тайне.

Под вскрытием (взломом) шифра обычно понимается решение одной из

перечисленных ниже задач:

 Полное вскрытие. Криптоаналитик нашел ключ К такой, что D

(C)=P.

 Глобальная дедукция. Не зная К, криптоаналитик отыскал

альтернативный D

алгоритм А такой, что А(С) = Р.

 Локальная дедукция. Криптоаналитику удалось определить открытый

текст, соответствующий конкретному перехваченному шифртексту.

 Частичная дедукция. Криптоаналитик получил неполную информацию

о ключе или открытом тексте. Это могут быть несколько битов ключа,

или дополнительные данные о структуре открытого текста, или что-то

еще в том же духе.

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

зависимости от того каким объемом перехваченного шифртекста располагает

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

исходный открытый текст. Существует всего один безусловно стойкий шифр (о

нем речь пойдет ниже). Все остальные шифры можно вскрыть с помощью атаки

со знанием только шифртекста: достаточно перебрать все возмож ные ключи и

проверить, имеет ли смысл открытый текст, полученный с их помощью.

Сложность криптоаналитической атаки

Сложность криптоаналитической атаки на алгоритм шифрования может

быть охарактеризована с помощью трех величин:

103

 Сложность по данным. Количество входных данных, необходимое для

успешной криптоаналитической атаки на алгоритм шифрования.

 Вычислительная сложность. Время, требуемое для успешной

криптоаналитической атаки на алгоритм шифрования.

 Сложность по памяти. Объем памяти, которая нужна для успешной

криптоаналитической атаки на алгоритм шифрования.

Часто под сложностью криптоаналитической атаки понимается

максимальная среди этих величин. А для некоторых атак приходится искать

компромисс между сложностью по данным, вычислительной сложностью и

сложностью по памяти. Например, для реализации более быстрой атаки может

потребоваться дополнительная память.

Сложность криптоаналитической атаки, как правило, выраж ается в виде

экспоненциальной функции. К примеру, если атака им еет сложность 2

128

, то это

значит, что для взлома шифра требуется выполнить 2

128

операций.

При оценке сложности атаки часто приходится оперировать очень

большими числами. Чтобы было понятно, насколько они велики, в табл. 5.1 для

них приведены некоторые физические аналогии.

Таблица 5.1. Физические аналогии для очень больших чисел

Физическая аналогия Число

Время, оставшееся до наступления следующего ледникового

Периода

Время, оставшееся до превращения Солнца в новую звезду

Возраст Земли

Возраст Вселенной

Количество атомов, из которых состоит Земля

Количество атомов, из которых состоит Солнце

Количество атомов, из которых состоит наша Галактика

Количество атомов, из которых состоит Вселенная

Объем Вселенной

1610

) лет

)лет

170

)

190

)

223

)

265

)

280

)см

В то время как сложность атаки на данный алгоритм шифрования

является постоянной величиной (по крайней мере, до тех пор, пока

криптоаналитик не придумает более эффективный метод взлома),

вычислительная мощь современных компьютеров растет буквально не по дням,

а по часам. Такой феноменальный рост наблюдается в течение последних

пятидесяти лет, и есть все основания полагать, что в ближайшее врем я данная

тенденция сохранится. Большинство криптоаналитических атак идеально

подходят для реализации на параллельных компьютерах: полномасштабная

атака на шифр разбивается на миллионы крошечных атак, которые ведутся

независимо друг от друга и, следовательно, не требуют организации

взаимодействия между процессорами. Поэтому в корне неверно заявлять о

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

104

что его невозможно взломать при современном уровне развития технологии.

Хорошая криптосистема всегда проектируется с достаточным запасом на

будущее. При этом необходимо принимать во внимание прогнозируемый рост

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

вычислительно стойким в течение многих лет.

Шифры замены и перестановки

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

Получившие широкое распространение криптографические алгоритмы

выполняли либо замену одних букв на другие, либо переставляли буквы друг с

другом. Самые стойкие шифры делали одновременно и то, и другое, причем

многократно.

Шифры замены

Шифром замены называется алгоритм шифрования, который производит

замену каждой буквы открытого текста на какой-то символ шиф рованного

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

В классической криптографии различают 4 разновидности шифров

замены:

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

текста заменяется на один и тот же символ шифртекста.

 Омофонноя замена. Аналогична простой замене с единственным

отличием: каждой букве открытого текста ставятся в соответствие

несколько символов шифртекста. Например, буква “А” заменяется на

цифру 5, 13, 25 или 57, а буква “Б” — на 7, 19, 31 или 43 и так далее.

 Блочная замена. Шифрование открытого текста производится блоками.

Например, блоку “АБА” может соответствовать “РТК”, а блоку “АББ”

— “СЛЛ”.

 Многоалфавитная замена. Состоит из нескольких шифров простой

замены. Например, могут использоваться пять шифров простой

замены, а какой из них конкретно применяется для шифрования данной

буквы открытого текста, — зависит от ее положения в тексте.

Примером шифра простой замены может служить программ а ROT13,

которую обычно можно найти в операционной системе UNIX. С ее помощью

буква “А” открытого текста на английском языке заменяется на букву “N”, “В”

— на “О” и так далее. Таким образом, ROT13 циклически сдвигает каж дую

букву английского алфавита на 13 позиций вправо. Чтобы получить исходный

открытый текст надо применить функцию шифрования ROT 13 дважды:

105

Р = ROT13 (ROT13 (P))

Все упомянутые шифры замены легко взламываются с использованием

современных компьютеров, поскольку замена недостаточно хорошо маскирует

стандартные частоты встречаемости букв в бткрытом тексте.

Разновидностью шифра замены можно считать код, который вместо букв

осуществляет замену слов, фраз и даже целых предложений. Например,

кодовый текст “ЛЕДЕНЕЦ” может соответствовать фразе открытого текста

“ПОВЕРНУТЬ ВПРАВО НА 90°”. Однако коды применимы только при

определенных условиях: если, например, в коде отсутствует соответствующее

значение для слова “МУРАВЬЕД”, то вы не можете использовать это слово в

открытом тексте своего сообщения, предназначенном для кодирования.

Шифры перестановки

В шифре перестановки буквы открытого текста не замещаются на

другие, а м еняется сам порядок их следования. Например, в шифре простой

колонной перестановки исходный открытый текст записывается построчно

(число букв в строке фиксировано), а шифртекст получается считыванием букв

по колонкам. Расшифрование производится аналогично: шифртекст

записывается поколонно, а открытый текст можно затем прочесть по

горизонтали.

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

второго шифра перестановки. Существуют еще более сложные шифры

перестановки, однако почти все они легко взламываю тся с помощью

компьютера.

Хотя во многих современных криптографических алгоритмах и

используется перестановка, ее применение ограничено узкими рам ками,

поскольку в этом случае требуется память большого объема, а также

накладываются ограничения на длину шифруемых сообщений. Замена

получила значительно большее распространение.

Роторные машины

В 20-е годы были изобретены разнообразные механические устройства,

призванные автоматизировать процесс шифрования и расшифрования.

Большинство из них состояло из клавиатуры для ввода открытого текста и

набора роторов — специальных вращаю щихся колес, каждое из которых

реализовывало простую замену. Например, ротор мог заменять “А” на “Ф”, “Б”

на “У”, “С” на “Л” и т. д. При этом, выходные контакты одного ротора

подсоединялись к входным контактам следующего за ним.

Тогда, например, если на клавиатуре 4-роторной машины нажималась

клавиша “А”, то первый ротор мог превратить ее в “Ф”, которая, пройдя через

106

второй ротор, могла стать буквой “Т”, которую третий ротор мог заменить на

букву “К”, которая могла быть преобразована четвертым ротором в букву “Е”

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

была иной. Чтобы сбить с толку криптоаналитиков, роторы вращались с разной

скоростью.

Наиболее известной роторной машиной стала немецкая “Энигма”,

которую Германия использовала для засекречивания своей переписки во время

Второй мировой войны.

Операция сложения по модулю 2

Операция сложения по модулю 2, которая в языке программирования С

обозначается знаком ˄ , а в математике — знаком ⊕, представляет собой

стандартную операцию над битами:

0 ⊕ 0 = 0

0 ⊕ 1 = 1

1 ⊕ 0 = 1

1 ⊕ 1 = 0

С помощью сложения по модулю 2 можно выполнять м ногоалфавитную

замену, прибавляя к битам ключа соответствующие биты открытого текста.

Этот алгоритм шифрования является симметричным. Поскольку двойное

прибавление одной и той же величины по модулю 2 восстанавливает исходное

значение, шифрование и расшифрование выполняются одной и той же

программой.

К сожалению, данный алгоритм обладает очень слабой стойкостью. Тем

не менее АНБ одобрило его использование в цифровых сотовых телефонах

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

также часто встречается в различных коммерческих программ ных продуктах.

Следует помнить, что с помощью данного алгоритма вы можете надежно

спрятать от человека, не сведущего в криптоанализе, содержание своей

переписки, однако опытному криптоаналитику понадобится всего несколько

минут, чтобы его взломать. Делается это очень просто, если предположить,

например, что открытый текст сообщения написан на английском языке.

1. Сначала следует определить длину ключа. Шифртекст последовательно

складывается по модулю 2 со своей копией, сдвинутой на различное

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

совпадающих компонентов. Когда величина сдвига кратна длине

ключа, это число превысит 6% от общей длины исследуемого

шифртекста. Если не кратна, то совпадений будет меньше 0,4%.

Проанализировав полученные данные, можно сделать обоснованный

вывод о длине ключа.

2. Затем надо сложить шифртекст по модулю 2 со своей копией,

107

сдвинутой на величину длины ключа. Эта операция аннулирует ключ и

оставит в наличии открытый текст сообщения, сложенный по модулю 2

со своей копией, сдвинутой на величину длины ключа.

Одноразовые блокноты

Хотите верьте, хотите нет, но на самом деле все-таки существует

алгоритм шифрования, который невозмож но вскрыть. Зовется он одноразовым

блокнотом. В классическом виде одноразовый блокнот представляет собой

очень длинную последовательность случайных букв, записанную на листах

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

каждую букву из блокнота, чтобы зашифровать ровно одну букву открытого

текста сообщения. Шифрование состоит в сложении буквы открытого текста и

буквы из одноразового блокнота по модулю N, где N — количество букв в

алфавите. После зашифрования отправитель уничтожает использованный

одноразовый блокнот. Чтобы отправить новое сообщение, ему придется

изготовить или найти новый одноразовый блокнот.

Получатель, владеющий копией одноразового блокнота, которым

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

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

одноразового блокнота. Эту копию он затем уничтожает.

Если предположить, что у криптоаналитика нет доступа к одноразовому

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

шифрованному сообщению с одинаковой вероятностью соответствует

произвольный открытый текст той же длины, что и сообщение.

Однако у алгоритма шифрования с помощью одноразового блокнота есть

весьма существенный недостаток. Последовательность букв, которая

содержится в одноразовом блокноте, должна быть по-настоящему случайной, а

не просто псевдослучайной, поскольку любая криптоаналитическая атака на

него будет, в первую очередь, направлена против метода генерации

содержимого этого блокнота.

Другая важная особенность применения одноразового блокнота состоит в

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

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

один и тот же одноразовый блокнот. Делается это следующим образом. Нужно

последовательно сдвигать одно сообщение относительно другого и

подсчитывать количество совпадений. Как только это количество резко

увеличится, значит, случайная последовательность, использованная для

зашифрования двух различных отрезков сообщений, была одной и той же.

Дальнейший криптоанализ осуществляется достаточно просто.

Одноразовые блокноты могут состоять не из байтов, а из битов. Тогда

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

получения открытого текста достаточно опять сложить по модулю 2 шифртекст

и содержимое одноразового блокнота. Надежность будет по-прежнему такой

108

же, как при посимвольном модульном сложении.

Еще один недостаток блокнотного способа шифрования заключается в

том, что случайная последовательность должна быть той же длины, что и само

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

блокнот еще сгодится, но как быть с каналом связи, пропускная способность

которого измеряется десятками мегабит в секунду?

Конечно, при необходимости можно для хранения случайных

последовательностей воспользоваться компакт-дисками с многократной

перезаписью или цифровой магнитной лентой. Однако это будет достаточно

дорогостоящее решение проблем ы. Кроме того, необходимо будет обеспечить

синхронную работу приемной и передаю щей аппаратуры, а также отсутствие

искажений при передаче. Ведь даже если несколько бит сообщения пропущены

при его передаче, получатель так и не сможет прочесть открытый текст.

Несмотря на все перечисленные выше недостатки, в настоящее время

одноразовые блокноты активно используются для шифрования сверхсекретных

сообщений. Не имея в своем распоряжении соответствующего блокнота, эти

сообщения невозможно прочитать вне зависимости от того, насколько быстро

работают суперкомпьютеры, которые используются в ходе

криптоаналитической атаки. Даже инопланетные пришельцы со своими

сверхсветовыми звездолетами и чудо-компьютерами не смогут их прочесть,

если, конечно, не вернутся в прошлое на машине времени и не добудут

одноразовые блокноты, использованные для шифрования этих сообщений.

Компьютерные алгоритмы шифрования

Существует великое множество алгоритмов шифрования, придуманных

специально в расчете на реализацию в виде компьютерных программ. Среди

наиболее известных можно упомянуть:

 Data Encryption Standard (DES). Симметричный алгоритм шифрования,

являющийся в США государственным стандартом.

 RSA. Алгоритм шифрования с открытым ключом, названный по

первым буквам фамилий его создателей (Rivest, Shamir, Adleman).

 ГОСТ 28147-89. Симметричный алгоритм шифрования, одобренный

сначала в СССР, а затем и в России для использования в качестве

государственного стандарта.

109

Глава 6

Криптографические ключи

Длина секретного ключа

Надежность симметричной криптосистемы зависит от стойкости

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

Допустим, что сам алгоритм идеален — вскрыть его можно только путем

опробования всех возможных ключей. Этот вид криптоаналитической атаки

называется методом тотального перебора. Чтобы применить данный метод,

криптоаналитику понадобится немного шифртекста и соответствующий

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

в свое распоряжение по одному блоку шифрованного и соответствующего

открытого текста. Сделать это не так уж и трудно.

Криптоаналитик может заранее узнать содержание сообщения, а затем

перехватить его при передаче в зашифрованном виде. По некоторым признакам

он также может догадаться, что посланное сообщение представляет собой не

что иное, как текстовый файл, подготовленный с помощью распространенного

редактора, компьютерное изображение в стандартном формате, каталог

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

каждом из этих случаев в открытом тексте перехваченного шифрсообще-ния

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

знанием открытого текста.

Подсчитать сложность атаки методом тотального перебора достаточно

просто. Если ключ имеет длину 64 бита, то суперкомпьютер, который может

опробовать 1 млн ключей за 1 с, потратит более 5 тыс. лет на проверку всех

возможных ключей. При увеличении длины ключа до 128 бит, этому же

суперкомпьютеру понадобится 10

лет, чтобы перебрать все ключи. Вселенная

существует всего-навсего 10

лет, поэтому можно сказать, что 10

— это

достаточно большой запас надежности для тех, кто пользуется 128-битными

ключами.

Однако прежде чем броситься спешно изобретать криптосистему с

длиной ключа в 4 Кбайт, следует вспомнить о сделанном выше предположении,

а именно: используемый алгоритм шифрования идеален в том смысле, что

110