Алгоритмы шифрования с открытым ключом

Алгоритмы шифрования с открытым ключом, также называемые асимметричными алгоритмами шифрования, устроены так, что ключ, используемый для шифрования сообщений, отличается от ключа, применяемого для их расшифрования. Более того, ключ расшифрования не может быть за обозримое время вычислен , ходя из ключа шифрования. Свое название алгоритмы с открытым ключом получили благодаря тому, что ключ шифрования не требуемся держать в тайне. Любой может им воспользоваться, чтобы зашифровать свое сообщение, но только обладатель соответствующего секретного ключа расшифрования будет в состоянии прочесть это шифрованное сообщение. Ключ шифрования обычно называют открытым ключом, а ключ расшифрования — тайным ключом. Иногда тайный ключ называют также секретным, однако чтобы избежать путаницы с симметричными алгоритмами, это название не будет использоваться при дальнейшем изложении.

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

Е k (Р) - С

D к (С) = Р

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

Е к (Р) = С

D k (C) = Р

Аутентификация, целостность и неоспоримость

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

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

Целостность. Получатель сообщения в состоянии проверить, были ли внесены какие-нибудь изменения в полученное сообщение в ходе его передачи. Злоумышленнику не позволено заменить настоящее сообщение на фальшивое.

Неоспоримость. Отправитель сообщения должен быть лишен возможности впоследствии отрицать, что именно он является автором этого сообщения.

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

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

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

Data Encryption Standard (DES). Симметричный алгоритм шифрования, являющийся в США государственным стандартом.

RSA. Алгоритм шифрования с открытым ключом, названный по первым буквам фамилий его создателей (Rivest, Shamir, Adleman).

ГОСТ 28147-89. Симметричный алгоритм шифрования, одобренный сначала в СССР, а затем и в России для использования в качестве государственного стандарта.

Криптоаналитические атаки

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

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

Попытка криптоанализа называется атакой. Успешная криптоаналитическая атака зовется взломом, или вскрытием.

В современной криптологии принято считать, что надежность шифра определяется только секретностью используемого ключа. Правило, впервые сформулированное голландцем А. Керкхоффом (1835—1903), гласит о том, что весь механизм шифрования, за исключением значения ключа, предположительно известен противнику. Это предположение является довольно естественным. Например, хотя ФАПСИ вряд ли знакомит АНБ со своими криптографическими алгоритмами, какое-то представление о них там вес равно имеется. Следовательно, правило Керкхоффа является относительно хорошим допущением при рассмотрении надежности алгоритмов шифрования. Если шифр невозможно взломать, зная абсолютно все детали алгоритма шифрования, значит это тем более нельзя сделать, не обладая подобными знаниями во всей их полноте.

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

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

Дано:

С 1 = E k1 (P 1 ), С 2 = E k2 (P 2 ),..., С i = E ki (P i ).

Найти:

P 1 , P 2 , ..., Р i или К 1 , К 2 , ..., K i .

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

Дано:

P 1 , C 1 = E k1 (P 1 ), P 2 , C 2 = E k2 (P 2 ),..., P i , C i = E ki (P i ).

Найти:

K 1 , K 2 , . . , K i .

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

Дано:

P 1 , C 1 = E k 1 (P 1 ), P 2 , C 2 = E k 2 (P 2 ),..., P i ,

где С i = Е к i ( P i ), где P 1 , P 2 ,. . . , Pi выбраны криптоаналитиком.

Найти: К 1 , К 2 , . . . , K i .

4. Адаптивная атака с выбранным открытым текстом. Эта атака является разновидностью атаки с выбранным открытым текстом. Криптоаналитик не только выбирает открытые тексты посылаемых шифрованных сообщений, но и может менять свой выбор в зависимости от результатов их шифрования.

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

1. Атака с выбранным шифртекстом. Криптоаналитику предоставлена возможность выбора шифртекстов, подлежащих расшифрованию получателем. Он также имеет доступ к соответствующим открытым текстам.

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

Дано:

С 1 , P 1 = D k1 ( C 1 ) , С 2 , P 2 = D k2 ( C 2 ) , ..., С i , P i = D ki ( C i ).

Найти :

K 1 , K 2, . . . , K i . Этой криптоаналитической атаке, как правило, подвергаются алгоритмы шифрования с открытым ключом. Хотя иногда она эффективна и против симметричных криптосистем. Атаку с выбранным открытым текстом и с выбранным шифртектом называют атакой с выбранным текстом.

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

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

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

С этой точки зрения зашифрованная программа на языке С особенно уязвима, поскольку содержит множество зарезервированных слов типа # define, # include, if, then и do.

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

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

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

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

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

Полное вскрытие. Криптоаналитик нашел ключ К такой, что D K (C)=P.

Глобальная дедукция. Не зная К, криптоаналитик отыскал адьтернативный D k алгоритм А такой, что А(С) = Р.

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

Частичная дедукция. Криптоаналитик получил неполную информацию о ключе или открытом тексте. Это могут быть несколько битов ключа, или. дополнительные данные о структуре открытого текста, или что-то еще в том же духе.

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

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

Хотите верьте, хотите нет, но на самом деле все-таки существует алгоритм шифрования, который невозможно вскрыть. Зовется он одноразовым блокнотом. В классическом виде одноразовый блокнот представляет собой очень длинную последовательность случайных букв, записанную на листах бумаги, которые скреплены между собой в блокнот. Отправитель использует каждую букву из блокнота, чтобы зашифровать ровно одну букву открытого текста сообщения. Шифрование состоит в сложении буквы открытого текста и буквы из одноразового блокнота по модулю N, где N — количество букв в алфавите. После зашифрования отправитель уничтожает использованный одноразовый блокнот. Чтобы отправить новое сообщение, ему придется изготовить или найти новый одноразовый блокнот.

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

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

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

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

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

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

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

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

Шифры и ключи

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

Когда надежность криптографического алгоритма обеспечивается за счет сохранения в тайне сути самого алгоритма, такой алгоритм шифрования называется ограниченным. Ограниченные алгоритмы представляют значительный интерес с точки зрения истории криптографии, однако совершенно непригодны при современных требованиях, предъявляемых к шифрованию. Ведь в этом случае каждая группа пользователей, желающих обмениваться секретными сообщениями, должна обзавестись своим оригинальным алгоритмом шифрования. Применение готового оборудования и стандартных программ исключено, поскольку тогда любой сможет приобрести это оборудование и эти программы и ознакомиться с заложенным в них алгоритмом шифрования. Придется разрабатывать собственный криптографический алгоритм, причем делать это надо будет каждый раз, когда кто-то из пользователей группы захочет ее покинуть или когда детали алгоритма случайно станут известны посторонним.

В современной криптографии эти проблемы решаются с помощью использования ключа, который обозначается буквой К (от английского слова key). Ключ должен выбираться среди значений, принадлежащих множеству, которое называется ключевым пространством. И функция шифрования Е, и функция расшифрования D зависят от ключа. Сей факт выражается присутствием К в качестве подстрочного индекса у функций Е и D:

Е к (Р) = С

D к (С) = Р

По-прежнему справедливо следующее тождество:

D k (E k (P)) = P

Некоторые алгоритмы шифрования используют различные ключи для шифрования и расшифрования. Это означает, что ключ шифрования К 1 отличается от ключа расшифрования К 2 . В этом случае справедливы следующие соотношения:

Е к 1 ( P ) = С

D k2 (С) = Р

D k2 (E k1 (Р) ) = Р

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

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

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

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

Шифры замены

Шифром замены

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

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

разновидности шифров замены:

Простая замена,

или

одноалфавитный шифр.

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

Омофонная замена.

Аналогична простой замене с единственным отличием: каждой букве открытого текста ставятся в соответствие несколько символов шифртекста. Например, буква "А" заменяется на цифру 5, 13, 25

или 57

а буква "Б" — на 7, 19, 31 или 43 и так далее.

Блочная замена.

Шифрование открытого текста производится блоками. Например, блоку "АБА" может соответствовать "РТК", а блоку "АББ" — "СЛЛ".

Многоалфавитная замена. Состоит из нескольких шифров простои замены. Например, могут использоваться пять шифров простой замены, а какой из них конкретно применяется для шифрования данной буквы открытого текста, — зависит от ее положения в тексте.

Примером шифра простой замены может служить программа ROT13, которую обычно можно найти в операционной системе UNIX. С ее помощью буква "А" открытого текста на английском языке заменяется на букву "N", "В" — на "О" и так далее. Таким образом, ROT13 циклически сдвигает каждую букву английского алфавита на 13 позиций вправо. Чтобы получить исходный открытый текст надо применить функцию шифрования ROT 13 дважды:

Р = ROT13(ROT13(P))

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

Разновидностью шифра замены можно считать код, который вместо букв осуществляет замену слов, фраз и даже целых предложений. Например, кодовый текст "ЛЕДЕНЕЦ" может соответствовать фразе открытого текста "ПОВЕРНУТЬ ВПРАВО НА 90°". Однако коды применимы только при определенных условиях: если, например, в коде отсутствует соответствующее значение для слова "МУРАВЬЕД", то вы не можете использовать это слово в открытом тексте своего сообщения, предназначенном для кодирования.

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

В

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

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

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

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

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

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

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

роторов —

специальных вращающихся колес, каждое из которых реализовывало простую замену. Например, ротор мог заменять "А" на "Ф". "Б" на "У", "С" на "Л" и т. д. При этом выходные контакты одного ротора подсоединялись к входным контактам следующего за ним.

Тогда, например, если на клавиатуре 4-роторной машины нажималась клавиша "А", то первый ротор мог превратить ее в "Ф", которая, пройдя через второй ротор, могла стать буквой "Т", которую третий ротор мог заменить на букву "К", которая могла быть преобразована четвертым ротором в букву "F" шифртекста. После этого роторы поворачивались, и в следующий раз заме на была иной. Чтобы сбить с толку криптоаналитиков, роторы вращались с разной скоростью.

Наиболее известной роторной машиной стала немецкая "Энигма", которую Германия использовала для засекречивания своей переписки во время Второй мировой войны.

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

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

Å

, представляет собой стандартную операцию над битами:

0

Å 0 = 0

0

Å 1 = 1

1

Å 0 = 1

1

Å 1 =

0

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

К сожалению, данный алгоритм обладает очень слабой стойкостью. Тем не менее АНБ одобрило его использование в цифровых сотовых телефонах американских производителей для засекречивания речевых переговоров. Он также часто встречается в различных коммерческих программных продуктах.

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

1. Сначала следует определить длину ключа.Шифртекст последовательно складывается по модулю 2 со своей копией, сдвинутой на различное число байт, и в полученном векторе подсчитывается число совпадающих компонентов. Когда величина сдвига кратна длине ключа, это число превысит 6% от общей длины исследуемого шифртекста. Если не кратна, то совпадений будет меньше 0,4%. Проанализировав полученные данные, можно сделать обоснованный вывод о длине ключа.

2. Затем надо сложить шифртекст по модулю 2 со своей копией, сдвинутой на величину длины ключа. Эта операция аннулирует ключ и оставит в наличии открытый текст сообщения, сложенный по модулю 2 со своей копией, сдвинутой на величину длины ключа.

Симметричные алгоритмы шифрования

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

Шифрование и расшифрование в симметричных криптографических алгоритмах задаются уже знакомыми формулами:

Е к (Р) = С

D к (С) = Р

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

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

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

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

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

Часто под сложностью криптоаналитической атаки понимается максимальная среди этих величин. А для некоторых атак приходится искать компромисс между сложностью по данным, вычислительной сложностью и сложностью по памяти. Например, для реализации более быстрой атаки может потребоваться дополнительная память.

Сложность криптоаналитической атаки, как правило, выражается в виде экспоненциальной функции. К примеру, если атака имеет сложность 2 128 , то это значит, что для взлома шифра требуется выполнить 2 128 операций.

При оценке сложности атаки часто приходится оперировать очень большими числами. Чтобы было понятно, насколько они велики, в табл. 5.1 для них приведены некоторые физические аналогии.

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

Физическая аналогия	Число
Время, оставшееся до наступления следующего ледникового периода	16-10 3 (2 14 ) лет
Время, оставшееся до превращения Солнца в новую звезду	10 9 (2 30 ) лет
Возраст Земли	10 9 (2 30 ) лет
Возраст Вселенной	10 10 (2 32 ) лет
Количество атомов, из которых состоит Земля	10 51 (2 170 )
Количество атомов, из которых состоит Солнце	10 57 (2 190 )
Количество атомов, из которых состоит наша Галактика	10 67 (2 223 )
Количество атомов, из которых состоит Вселенная	10 77 (2 265 )
Объем Вселенной	10 84 (2 280 )см 3

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

Терминология

Шифрование и расшифрование

Предположим, что отправитель хочет послать сообщение получателю. Более того, отправитель желает засекретить это сообщение, чтобы никто, кроме получателя, не смог его прочитать.

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

Наука, которая учит, как следует поступать, чтобы сохранить содержание сообщений в тайне, называется криптографией. Людей, занимающихся криптографией, зовут криптографами. Криптоаналитики являются специалистами в области криптоанализа — науки о вскрытии шифров, которая отвечает на вопрос о том, как прочесть открытый текст, скрывающийся пол шифрованным. Раздел науки, объединяющий криптографию и криптоанализ, именуется криптологией.

Обозначим открытый текст буквой Р (от английского слова plaintext). Это может быть текстовый файл, битовое изображение, оцифрованный звук — что угодно. Единственное ограничение связано с тем, что, поскольку, прел метом изложения является компьютерная криптография, под Р понимание;; исключительно двоичные данные.

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

На вход функции шифрования Е подается Р, чтобы на выходе получить С.

В обозначениях, принятых в математике, это записывается как:

Е(Р) = C

При обратном преобразовании шифртекста в открытый текст на вход функции расшифрования D поступает С, а на выходе получается Р:

D(C) = М

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

D(E(P)) = Р

Зачем нужна криптография

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

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

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

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

Нуждается ли рядовой обыватель в подобной защите? Конечно, нуждается.
Под ее прикрытием он может вести учет своих финансовых затрат, не опасаясь, что с ними ознакомятся налоговые службы. Он может разрабатывать новое изделие для последующей выгодной продажи на рынке, надежно пряча детали своей разработки от конкурентов. Он может завести любовницу и не бояться, что волей случая жена окажется посвященной в подробности его тайной любовной переписки. Ведь любой не застрахован от ситуации, котла он занимается какой-то деятельностью, которую он сам не считает незаконной, но которая впоследствии может быть объявлена кем-то вне закона. Каковы бы ни были причины, человек имеет право на частную жизнь, в том числе — на сохранение в тайне любых сведений, которые он сочтет нужным не предавать огласке. И никому, в том числе и государству, не должно быть до них никакого дела.

На практике все обстоит совершенно иначе. Своим Указом № 334 от 3 апреля 1995 г. президент России строго-настрого запретил "деятельность юридических и физических лиц, связанную с разработкой, производством, реализацией и эксплуатацией шифровальных средств, |...| предоставлением услуг в области шифрования информации", без государственных лицензий. А российские спецслужбы обязал "осуществлять выявление юридических и физических лиц, нарушающих требования настоящего Указа". Что с такими лицами будут делать — вырывать им ноздри или просто ставить клеймо на лоб, чтобы другим неповадно было, — в президентском Указе не сказано. Но и без этого у государственных чиновников в России появились все необходимые полномочия, чтобы при необходимости можно было воспрепятствовать внедрению надежных систем криптографической защиты информации. Надо сказать, что аналогично действует и американское правительство, которое путем введения государственного стандарта шифрования с передачей ключей на хранение пытается узаконить для себя право шпионить за своими гражданами.

Таким образом, становится совершенно очевидно, что надежность шифровальных средств — традиционно лишнее качество для "Большого брата", независимо от его национальной принадлежности.

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

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

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

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

А отвоевываются не чужие территории или право распоряжаться судьбами побежденных, а информация. И противостоят друг другу не "хорошие" и "плохие" парни, даже не озверевшие наемники. а государство и его граждане.

В информационной войне государство пользуется двумя основными видами оружия. Во-первых, в любую сертифицированную государством систему защиты информации встраивается так называемый потайной ход. который иногда еще именуют лазейкой. Еще в 1991 г. в сенат США был внесен законопроект, который требовал, чтобы любое американское криптографическое оборудование содержало потайной ход, известный АН Б. Поэтому совершенно не удивительно, что один из крупнейших разработчиков криптографического оборудования в США — компания AT&T — нисколько не скрывает того факта, что у американского правительства есть "ключики" "потайных ходов", ведущих во все ее системы вне зависимости от тою. насколько сложные пароли придумают неискушенные пользователи.

Второй способ обмана граждан является более изощренным и состоит в применении системы с депонированием ключей. В этом случае прочесть сообщение можно только при наличии всех частей ключа, использованного для засекречивания этого сообщения. Тайна переписки гарантируется до тех пор, пока государству не понадобится с ней ознакомиться. Тогда стоит заручиться согласием, скажем, тех доверенных лиц или организаций, которым были отданы на хранение части ключа, — и тайное станет явным. В США данный подход был подвергнут справедливой критике со стороны большинства специалистов, а корпоративные пользователи с негодованием отвергли саму идею довериться правительству в таком деликатном вопросе, как коммерческая тайна. И это в законопослушной Америке, где ставшие явными попытки спецслужб вторгнуться в частную жизнь своих граждан встречают немедленный и достойный отпор!

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

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

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

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

Конечно, разложение большого числа на множители — задача трудная. Однако сразу возникает резонный вопрос, насколько трудная. К несчастью для криптографов, сложность ее решения уменьшается. И что еще хуже, эта сложность падает значительно более быстрыми темпами, чем ожидалось ранее. Например, в середине 70-х годов считалось, что для разложения на множители числа из 125 цифр потребуются десятки квадрильонов лет. А всего два десятилетия спустя с помощью компьютеров, подключенных к сети Internet удалось разложить на множители число из 129 цифр. Этот прорыв стал возможен благодаря тому, что за прошедшие 20 лет были не только предложены новые, более быстрые, методы разложения на множители больших чисел, но и возросла производительность используемых компьютеров.

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

А почему, спрашивается, не взять 10000-битный ключ 9 Ведь тогда отпадут все вопросы, связанные со стойкостью асимметричного алгоритма шифрования с открытым ключом, основанном на разложении большого числа па множители. Но дело в том, что обеспечение достаточной стойкости шифра не является единственной заботой криптографа. Имеются дополнительные соображения, влияющие на выбор длины ключа, и среди них — вопросы. связанные с практической реализуемостью алгоритма шифрования при выбранной длине ключа.

Чтобы оценить длину открытого ключа, будем измерять доступную криптоаналитику вычислительную мощь в так называемых мопс-годах, т. е. количеством операций, которые компьютер, способный работать со скоростью 1 миллион операций в секунду, выполняет за год. Допустим, что хакер имеет доступ к компьютерным ресурсам общей вычислительной мощью 10000 мопс-лет, крупная корпорация — 107 мопс-лет, правительство — 109 мопс-лет. Это вполне реальные цифры, если учесть, что при реализации упомянутого выше проекта разложения числа из 129 цифр его участники задействовали всего 0,03% вычислительной мощи Internet, и чтобы добиться этого, им не потребовалось принимать какие-либо экстраординарные меры или выходить за рамки закона.

Предположим еще, что вычислительная мощь возрастает в 10 раз каждые 5 лет, а метод, который используется для разложения больших чисел на множители, позволяет это делать с трудоемкостью, указанной в табл. 6.3.

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

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

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

Подсчитать сложность атаки методом тотального перебора достаточно просто. Если ключ имеет длину 64 бита, то суперкомпьютер, который может опробовать 1 млн ключей за 1 с, потратит более 5 тыс. лет на проверку всех возможных ключей. При увеличении длины ключа до 12cS бит, этому же суперкомпьютеру понадобится 10 25 лет, чтобы перебрать все ключи. Вселенная существует всего-навсего 10'° лет, поэтому можно сказать, что 10- — это достаточно большой запас надежности для тех, кто пользуется 128-5ишымп ключами.

Однако прежде чем броситься спешно изобретать криптосистему с длиной ключа в 4 Кбайт, следует вспомнить о сделанном выше предположении, а именно: используемый алгоритм шифрования идеален в том смысле, что вскрыть его можно только методом тотального перебора. Убедиться в этом на практике бывает не так просто, как может показаться на первый взгляд.
Криптография требует утонченности и терпения. Новые сверхсложные криптосистемы при более внимательном рассмотрении зачастую оказываются очень нестойкими. А внесение даже крошечных изменений в стойкий криптографический алгоритм может существенно понизить его стойкость. Поэтому надо пользоваться только проверенными шифрами, которые известны уже в течение многих лет, и не бояться проявлять болезненную подозрительность по отношению к новейшим алгоритмам шифрования, вне зависимости от заявлений их авторов об абсолютной надежности этих алгоритмов.

Важно также не забывать о правиле Керкхоффа: стойкость алгоритма шифрования должна определяться ключом, а не деталями самого алгоритма. Чтобы быть уверенным в стойкости используемого шифра, недостаточно проанализировать его при условии, что противник досконально знаком с алгоритмом шифрования. Нужно еще и рассмотреть атаку на этот алгоритм, при которой враг может получить любое количество шифрованного и соответствующего открытого текста. Более того, для повышения надежности следует предположить, что криптоаналитик имеет возможность организовать атаку с выбранным открытым текстом произвольной длины.

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

Генерация ключей

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

Сокращенные ключевые пространства

Длина ключа в DES-алгоритме составляет 56 бит. В принципе, в качестве ключа может быть использован любой 56-битный вектор. На практике это правило часто не соблюдается. Например, широко распространенная программа шифрования файлов Norton Discreet, входящая в пакет Norton Utilities (версии 8.0 или более младшей версии), который предназначен для работы в операционной системе DOS, предлагает пользователю программную реализацию DES-алгоритма. Однако при вводе ключа разрешается подавать на вход программы только те символы, старший бит представления которых в коде ASCII равен нулю. Более того, пятый бит в каждом байте введенного ключа является отрицанием шестого бита, и в нем игнорируется младший бит. Это означает, что мощность ключевого пространства сокращается до каких-то жалких 2

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

В табл. 6.6 приведено количество возможных ключей в зависимости от раз-личных ограничений на символы, которые могут входить в ключевую последовательность. Табл. 6.7 содержит сложность атаки методом тотального перебора при условии, что перебор ведется со скоростью 1 млн ключей в секунду.

Таблица 6.6. Количество возможных ключей в зависимости от ограничений на символы ключевой последовательности

Символы ключа	4 байта	5 байт	6 байт	7 байт	8 байт
Строчные буквы (26)	4,7*10 5	1,3*10 7	3,2*10 8	8,1*10 9	2,2*10 11
Строчные буквы и цифры (36)	1,8*10 6	6,1*10 7	2.3*10 9	7,9*10 10	2.9*10 12
Буквы и цифры (62)	1,6*10 7	9,3*10 8	5,8*10 10	3,6*10 11	2,3*10 14
Печатаемые символы (95)	8,2*10 7	7,8*10 9	7,5*10 11	7,1*10 13	6,7*10 15
Все ASCII-символы	4,4*10 9	1,2*10 10	2,9*10 14	7,3*10 16	1,9*10 19

<

Таблица 6.7. Сложность атаки методом тотального перебора при условии, что перебор ведется со скоростью 1 миллион ключей в секунду

Символы ключа	4 байта	5 байт	6 байт	7 байт	8 байт
Строчные буквы (26)	0,6 сек.	13 сек.	6 мин.	2,3ч.	2,5 дн.
Строчные буквы и цифры (36)	1,8 сек.	2 мин.	37 мин.	23ч.	34 дн.
Буквы и цифры (62)	16 сек.	16 мин.	17ч.	42 дн.	7,0 лет
Печатаемые символы (95)	1,5 мин.	2,2ч.	8,6 дн.	2,3 лет	211 лет
Все ASCII-символы	1,3ч.	14 дн.	9,0 лет	2400 лет	590000 лет

Из табл. 6.6 следует, что возможность опробовать 1 млн ключей в секунду позволяет в разумные сроки вскрывать 8-байтовые ключи из строчных букв и цифр, 7-байтовые буквенно-цифровые ключи, 6-байтовые ключи, составленные из печатаемых ASCII-символов, и 5-байтовые ключи, в которые могут входить любые ASCII-символы. А если учесть, что вычислительная мощь компьютеров увеличивается вдвое каждые полтора года, то для успешного отражения атаки методом тотального перебора в течение ближайшего десятилетия необходимо заблаговременно позаботиться о том. чтобы используемый ключ был достаточно длинным.

Плохие ключи

Когда отправитель сам выбирает ключ, с помощью которого он шифрует свои сообщения, его выбор обычно оставляет желать лучшего. Например, Петр Сергеевич Иванов скорее предпочтет использовать в качестве ключа Ivanov, чем &7)g\*. И вовсе не потому, что он принципиально не желает соблюдать элементарные правила безопасности. Просто свою фамилию Иванов помнит гораздо лучше, чем абракадабру из шести произвольно взятых символов. Однако тогда сохранить свою переписку в тайне ему не поможет и самый стон кий алгоритм шифрования в мире, особенно если используемые Ивановым ключи всегда совпадают с именами его ближайших родственников и записывает он эти ключи на клочках бумаги, которые наклеивает на компьютер. В ходе хорошо организованной атаки методом тотального перебора квалифицированный криптоанатитик не будет опробовать все ключи последовательно, один за другим.

Он сначала проверит те из них, которые хоть что-то значат для Иванова. Такая разновидность атаки методом тотального перебора наливается

товарной атакой,

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

Имя, фамилия, отчество, инициалы, год рождения и другая личная информация, имеющая отношение к данному человеку. Например, при словарной атаке против Петра Сергеевича Иванова в первую очередь следует проверить PSI, PSIPSI, PIVANOV, Pivanov, psivanov, peteri, pete I, IvanovP, peterivanov, Peter-Ivanov и т. д.

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

Слова, которые получены путем внесения различных изменений в словарную базу данных, составленную на предыдущем этапе. Сюда относятся обратный порядок написания слова, замена в нем латинских буки о, l, z, s на цифры

0 , 1, 2 и 5 соответственно, использование слова во множественном числе и т. д. Это даст дополнительно еще около миллиона словарных единиц для опробования в качестве возможного ключа к шифру.

Слова, полученные с помощью замены строчных букв на заглавные. Такой замене в принципе может подвергаться любое число букв. Например. вместе со словом Ivanov будут проверяться слова iVanov, ivAnov, ivaNov, ivanOv, ivanoV, IVanov, IvAnov, IvaNov, IvanOv, IvanoV и т. д. Однако. вычислительная мощь современных компьютеров позволяет проверять только одно-, двух- и трехбуквенные замены строчных букв на заглавные.

Слова на различных иностранных языках. Хотя компьютерные пользователи в основном работают с англоязычными операционными системами (DOS, UNIX, Windows и другими), существуют локализованные версии распространенных операционных систем, в которых допускается использование другого языка.

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

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

Случайные ключи

Хороший ключ представляет собой случайный битовый вектор. К примеру. если его длина составляет 56 бит, то это значит, что в процессе его генерации с одинаковой вероятностью может получиться любой из 2

56

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

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

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

нестойкие

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

Поэтому при генерации ключей нужно автоматически проверять их на стойкость и генерировать новые вместо тех, которые эту проверку не прошли. К примеру, в DES-алгоритме имеются всего 24 нестойких ключа из общего количества 2

56

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

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

Пользоваться случайными ключами не всегда удобно. Иногда ключ требуется сохранить в памяти, а запомнить 36f9 67аЗ f9cb d931 человеку не так-то

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

Составьте ключ из нескольких слов, разделенных знаками препинания. Например, очень просто и надолго запоминаются ключи типа Yankee'Go home.

Используйте в качестве ключа сочетание букв, которые представляют собой акроним более длинного слова. К примеру, броское название немецкого вина Liebenfraumilch позволяет путем отбрасывания гласных букв и добавления восклицательного знака сгенерировать ключ Lbnfrmlch!.

Пароль

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

паролем.

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

Пароль следует выбирать достаточно длинным, чтобы полученный в результате его преобразования ключ был случайным. Из теории информации известно, что в предложении на английском языке каждая буква содержит примерно 1,3 бита информации. Тогда, чтобы получить 64-бтный ключ, пароль должен состоять примерно из 49 букв, что соответствует английской фразе из 10 слов.

Необходимо, чтобы при желании пароль было легко вспомнить, и в то же время требуется, чтобы он был достаточно уникален. Цитата из Козьмы Пруткова, которая у всех на слуху, вряд ли подойдет, поскольку его сочинения имеются в форме, доступной для воспроизведения на компьютере, и следовательно, могут быть использованы в словарной атаке. Лучше воспользоваться творчеством малоизвестного поэта или драматурга, процитировав его с ошибками. Большего эффекта можно добиться, если в цитате, использованной для генерации ключа, будут присутствовать иностранные слова. Идеально подходят для этой цели незатейливые ругательства — их вам не придется записывать, чтобы запомнить. Достаточно шарахнуть себя по пальцу молотком, и пароль автоматически придет вам в голову. Надо только сдержаться и не произнести его вслух, чтобы не подслушали посторонние.

Несмотря на все сказанное, залогом наилучшей зашиты служит не шаманство при выборе пароля, а случайность полученного ключа. Хороший ключ — это случайный ключ, а значит, заранее будьте готовы к тому, что запомнить его наизусть будет очень трудно.

Стандарт ANSI X9.17

Американский национальный институт стандартов (ANSI) разработал метол генерации 64-битных ключей при помощи DES-алгоритма. Его основное назначение состоит в получении большого количества ключей для многократных сеансов связи. Вместо DES-алгоритма можно использовать любой другой стойкий алгоритм шифрования.

Пусть функция Е

K

(Р) осуществляет шифрование Р по DES-алгоритму на заранее заготовленном ключе К, который используется только для генерации секретных ключей. Пусть далее V

0

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

i

представляет собой отметку времени, когда был сгенерирован i-й ключ. Тогда очередной случайный ключ R

i

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

R

i

= Е

К

(Е

К

(Т

i

)

Å

V

i

)

Чтобы получить очередное значение V

i

, надо вычислить

V

i

= Е

К

(Е

К

(Т

i

)

Å

R

i

)

Генерация случайных и псевдослучайных последовательностей

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

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

Хранение ключей

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

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

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

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

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

"Китайская лотерея"

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

За найденный ключ полагается значительный приз. Благодаря этому радиоприемники и телевизоры со встроенными микросхемами хорошо раскупаются, а вскрытые ключи своевременно доводятся до сведения китайского правительства. Если учесть, что у каждого из десяти китайцев есть радиоприемник или телевизор, то получится, что на вскрытие 64-битного ключа китайскому правительству потребуется самое большее 43 часа. В табл. 6.2 приведена сложность вскрытия 64-битного ключа с помощью "китайской лотереи" при ее проведении в Китае, а также в США, Ираке и Израиле.

Контроль за использованием ключей

Прогресс в области вычислительной техники идет семимильными шагами. Ныне даже персональные компьютеры повсеместно работают под управлением многозадачных операционных систем. В результате пользователь часто оказывается не в состоянии определить, когда операционная система прерывает выполнение его программы шифрования, записывает ее саму, а также все ее данные на диск и переключается на работу с другим приложением. После того как операционная система наконец возобновляет процесс шифрования, все выглядит вполне пристойно: пользователь даже не успевает осознать, что шифровальная программа вместе с используемым ею ключом побывала на диске. В итоге ключ так и останется на диске в незашифрованном виде, пока поверх него не будут записаны другие данные. Когда это случится — через полсекунды, через месяц или вообще никогда, не может сказать никто. Однако враг не дремлет, и вполне может произойти так, что ключ все еще будет храниться на диске в открытую, когда вражеский агент проверит этот диск в поисках полезной информации.

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

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

Криптографически надежные псевдослучайные последовательности

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

Нелинейные ключевые пространства

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

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

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

Например, блочный алгоритм шифрования с длиной блока 64 бита и длиной ключа 128 бит может использовать "составной" ключ из 192 бит. Тогда вероятность случайно использовать стойкий ключ будет достаточно мала — всего 2 -64 .

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

Обновление ключей

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

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

Однонаправленные функции

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

Аналогом однонаправленной функции в быту является разбитая вдребезги стеклянная бутылка. Расколотить ее на мелкие осколки очень легко, однако попробуйте снова собрать целую бутылку из осколков!

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

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

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

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

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

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

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

Передача ключей

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

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

Упоминавшийся выше американский стандарт ANSI X9.17 определяет две разновидности ключей. Ключи шифрования данных используются для зашифрования сообщений, отправляемых по каналам связи. Ключи шифрования ключей применяются для зашифрования других ключей, которые предназначены для передачи получателям этих шифрованных сообщении. Ключи шифрования ключей передаются по каналам связи, исключающим подслушивание. Например, с помощью курьеров. Однако, поскольку делать это приходится значительно реже, чем посылать ключи шифрования данных, такой способ передачи ключей абонентам сети связи вполне пригоден для использования на практике.

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

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

С ростом количества абонентов сети связи применять подход, рекомендуемый стандартом ANSI X9.17, становится все трудней и трудней. Если n человек захотят обмениваться шифрованными сообщениями, общее число переданных ими ключей составит п(п-1)/2. При n =1000 потребуется почти 500 тыс. пересылок ключей между абонентами, что может вылиться в серьезную проблему. В этом случае лучше производить рассылку ключей из единого центра (назовем его центром распределения ключей, сокращенно — ЦРК).

По-настоящему случайные последовательности

Последовательность называется no-настоящему случайной, если ее нельзя воспроизвести. Это означает, что если запустить генератор по-настоящему случайных последовательностей дважды при одном и том же входе, то на его выходе получатся разные случайные последовательности. Основная трудность состоит в том, чтобы суметь отличить случайную последовательность от неслучайной. Если несколько раз зашифровать строку символов с помощью криптографического алгоритма, соответствующего ГОСТ 28147-89, то получится последовательность, очень напоминающая по-настоящему случайную. Чтобы доказать ее неслучайность, другого способа, кроме аренды АНБ соответствующих вычислительных мощностей и программы вскрытия. не существует. Однако вряд ли ваше предложение об аренде будет воспринято там всерьез.

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

Любой ключ должен использоваться в течение ограниченного периода времени. Тому есть несколько причин:

Чем дольше ключ находится в действии, тем больше вероятность того. что он будет скомпрометирован.

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

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

Криптоаналитическую атаку на шифр вести тем легче, чем больше перехваченного шифртекста для него накоплено.

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

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

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

Что касается открытых ключей, то продолжительность их использования сильно варьируется в зависимости от области применения. Если открытый ключ применяется для целей аутентификации или для цифровой подписи, он продолжает оставаться актуальным годами, иногда даже десятилетиями. Но даже в этом случае не следует пренебрегать сменой ключа каждые 2—3 года, чтобы в распоряжении криптоаналитика накапливалось меньше шифртекста, необходимого для организации атаки. А старый ключ все равно надо продолжать хранить в секрете — он может понадобиться, чтобы, например, подтвердить подлинность подписи, поставленной в течение периода, пока этот ключ был действующим.

Проверка подлинности ключей

Как Иванову убедиться в том, что полученные им ключи были действительно переданы Петровым, а не противником, который притворился Петровым? Если Петров отдает ключи Иванову с глазу на глаз, то сделать это довольно легко. Однако если Петров присылает ключи с курьером, то Иванову придется положиться на честность курьера. А если полученные Ивановым ключи зашифрованы с помощью ключа шифрования ключей, ему остается лишь надеяться, что этот ключ имеется только у Петрова. Наконец, если рассылку ключей производит ЦРК, Иванов должен убедиться в надежности процедур рассылки, которые приняты в ЦРК.

Если противник полностью контролирует все каналы связи, которыми пользуется Иванов, он может заставить поверить Иванова во что угодно. Противник может прислать ему фальшивый ключ шифрования ключей якобы от Петрова и затем передавать Иванову поддельные ключи шифрования данных, зашифрованные на этом ключе. Противник будет в состоянии обзавестись собственным ЦРК и слать Иванову ключи от имени подлинного ЦРК. И ничего не подозревающий Иванов станет шифровать свои сообщения с помощью ключей, известных противнику.

Подобные рассуждения иногда приводятся, чтобы доказать ненужность криптографических методов, применяемых при передаче ключей Ведь получается, что у Иванова и Петрова нет иного пути удостовериться в подлинности используемых ими ключей на все 100%, кроме личной встречи.

Эти рассуждения наивны. На практике установить тотальный контроль нал чьими бы то ни было линиями связи невозможно. Действительно. Иванов не в силах убедиться наверняка, что переданный ему ключ не был подменен всемогущим противником. Однако, чтобы его контроль был действительно тотальным, такому противнику придется прибегнуть к средствам, которые в реальном мире ему вряд ли будут доступны.

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

Нередко бывает, что Иванов желает убедиться: переданный ему ключ не только является подлинным, но и не был искажен при передаче. Ведь в результате Иванов может оказаться не в состоянии прочесть многие мегабайты шифр-текста. Если соответствующий открытый текст был ASCII-файлом, то можно проверить ключ, попытавшись расшифровать с его помощью шифртекст, и получив абракадабру вместо осмысленного текста, сделать вывод о том, что ключ был передан с искажениями. Если открытый текст является достаточно случайным, можно прибегнуть к другим методам проверки ключа.

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

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

Псевдослучайные последовательности

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

Псевдослучайная битовая последовательность должна, по возможности, не отличаться от по-настоящему случайной. Необходимо, чтобы в ней число единиц примерно совпадало с числом нулей, а половина всех "полосок" (подряд идущих идентичных компонентов последовательности) имела длину I. одна четвертая — длину 2, одна восьмая — длину 4 и т. д. Кроме только что перечисленных, существует еще ряд общепринятых тестов, которые позволяют проверить, действительно ли данная последовательность является псевдослучайной.

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

Работа с ключами

Предположим, некто Иванов и Петров пользуются надежной системой связи. Они делятся друг с другом своими соображениями на разные темы, играют в покер по переписке, заключают взаимовыгодные контракты, заверяя их своими цифровыми подписями, а затем производят расчеты между собой посредством электронных платежей. Алгоритм шифрования, используемый ими для этих целей, обладает сверхвысокой стойкостью. Но к сожалению, они покупают криптографические ключи в фирме "Ключкис и К о ", девиз которой гласит: "Полностью доверьтесь нам. Надежность — девичья фамилия бывшей тещи нашего генерального директора".

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

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

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

Потратить 10 млн долл. на разработку и изготовление специализированного криптоаналитического суперкомпьютера? Ну уж нет! Лучше за 1000 долл. подкупить шифровальщика, который будет регулярно передавать ключи к шифру. А если бюджет позволяет, то за миллион долларов можно накупим, этих ключей на много-много лет вперед. Американский военнослужащий Джон Уокер, к примеру, годами снабжал советскую разведку ключами к шифрам ВМС США, что позволило КГБ прочесть огромное количество американских шифровок. Ну а за несколько миллионов долларов доставим, где-то ключи, чтобы потом с их помощью читать шифрованные сообщения, нет нужды и вовсе.
За такие огромные деньги лучше сразу приобрести oi-крытые тексты этих сообщений. Например, всего 2 млн долларов понадобилось советской разведке, чтобы купить высокопоставленного сотрудника американской контрразведки Олдрича Эймса вместе с женой.

Ну а если из бюджета не удается выкроить нужную сумму на подкуй, то можно воспользоваться другими методами. Человек слаб: его можно напоить, усыпить или просто оглушить тяжелым предметом, чтобы выкраси, криптографические ключи. Его можно также соблазнить. Морские пехотинцы, охранявшие американское посольство в Москве, по просьбе своих русских любовниц пропускали в шифровальный отсек посольства сотрудников КГБ — на "экскурсию".

Это значит, что криптографические ключи нуждаются в такой же защите. как и сами данные, которые шифруются с их помощью. К сожалению, во многих коммерческих средствах шифрования часто считается достаточным провозгласить об использовании DES-алгоритма или другого достаточно стойкого шифра, а о генерации и хранении ключей к ним не говорить ни слова. Например, программа DiskLock (версия 2.1) для персонального компьютера Macintosh позволяет шифровать файлы по DES-алгоритму. Однако ключ, использованный этой программой для зашифрования, она сохраняет на носителе информации вместе с файлом. Зная, где лежит ключ, его можно оттуда извлечь и затем без особых хлопот прочесть с помощью этого ключа содержимое зашифрованного файла. В данном случае совершенно неважно. что сам алгоритм шифрования достаточно надежен. Имеет значение только то, что его реализация абсолютно никуда не годится.

Скомпрометированные ключи

Любой стойкий шифр обеспечивает надежную защиту только до тех пор, пока ключ к нему хранится в тайне. Если Иванов потеряет этот ключ, если у него этот ключ украдут, если этот ключ зачитает диктор в вечернем выпуске телевизионных новостей или этот ключ будет скомпрометирован каким-либо другим образом, обеспечиваемая им защита будет сведена на нет.

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

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

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

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

Среди параметров, которые необходимо принимать во внимание при рассмотрении атаки методом тотального перебора, прежде всего, надо упомянуть об общем количестве проверяемых ключей и о времени, затрачиваемом противником на проверку одного ключа. Количество ключей для конкретною алгоритма обычно фиксировано. Например, DES-алгоритм использует 56-битный ключ. Это означает, что его ключевое пространство содержит 2 56 ключей.

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

При решении вопроса о достаточной длине ключа в качестве алгоритма шифрования чаще всего рассматривается DES-алгоритм. В 1977 г. американские криптологи У. Диффи (W.Diffie) и М. Хеллман (M.Hellman) заявили, что при существующем уровне развития компьютерной технологии можно построить специализированный суперкомпьютер для вскрытия ключей DES-алгоритма методом тотального перебора. Имея в своем составе 1 млн микросхем, каждая из которых способна проверять 1 млн ключей в секунду, этот суперкомпьютер перебрал бы все 2 56 ключей за 20 час.

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

В 1993 г. американский криптолог М. Винер (M.Wiener) спроектировал суперкомпьютер для атаки на DES-атгоритм методом тотального перебора. Рассуждения Винера верны не только для DES-алгоритма, но и практически для любого другого алгоритма шифрования. Суперкомпьютер, разработанный Винером, состоит из специализированных микросхем, плат и стоек. По мнению Винера, для того чтобы гарантировать вскрытие 56-битного ключа за 7 час, на изготовление такого суперкомпьютера потребуется не более 1 млн долларов. По закону Мура, вычислительная мощь компьютеров улавливается каждые полтора года. Поэтому к 2001 г. стоимость суперкомпьютера, придуманного Винером, уменьшится в 10 раз и составит всего-навсего 100 тыс. долларов. Это означает, что уже сейчас крупные компании и "крутые" криминальные структуры могут вскрывать 56-битные ключи. Для военных криптоаналитиков в большинстве индустриально развитых стран доступны 64-битные ключи.

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

Стоимость и вычислительная

Таблица 6.1. Стоимость и вычислительная сложность атаки методом тотального перебора

Кто атакует	Бюджет	Сложность атаки	Стойкий ключ
40 бит	56 бит
Хакер	1000 долл.	1 неделя	Никогда	45 бит
Малый бизнес	10 тыс. долл.	12 мин.	556 дней	64 бита
Крупная компания	10 млн долл.	0.005 с	6 мин	70 бит
Федеральное агентство	300 млн долл.	0.0002 с	12с	75 бит

К приведенным в табл. 6.1 цифрам следует относиться с осторожностью. Теоретический расчет затрат на проведение атак методом тотального перебора на криптографические ключи разной длины всегда существенно отличается от того, с чем криптоаналитики сталкиваются на практике при покупке или разработке суперкомпьютеров для ведения такого рода атак. Объясняется это тем, что одни сделанные допущения оказываются весьма далеки от реальности, в то время как другие факторы просто не принимаются во внимание. В данном случае Диффи, Винер и другие посчитали, что при создании специализированного суперкомпьютера для атаки методом тотального перебора будут использоваться заказные микросхемы ценой не более 10 долл. По оценкам АНБ, такие микросхемы стоят, как правило, в 100 раз дороже. У АНБ вызвало сомнение и допущение о том, что вне зависимости от алгоритма шифрования, лишь длина ключа определяет сложность криптоаналитической атаки. Кроме того, при составлении таблицы не были учтены затраты на научно-исследовательские и опытно-конструкторские работы, которые для первого экземпляра суперкомпьютера обычно составляют не менее 10 млн долл. Не были также приняты во внимание расходы на приобретение компьютерной памяти.

Из сказанного можно сделать весьма важный вывод. Если кто-то очень захочет узнать использованный вами ключ, ему нужно всего лишь потратить достаточное количество денег. Поэтому определяющей является стоимость зашифрованной вами информации. Если цена ей в базарный день — около 2 долл., вряд ли кто-то решится потратить 1 млн, чтобы ее заполучить. Но если прибыль от прочтения вашей шифровки составляет 100 млн долл..
— берегитесь! Единственным утешением может послужить тот факт, что с течением времени любая информация очень быстро устаревает и теряет свою ценность.

Программная атака

Без специализированного компьютерного оборудования, ведущего параллельный поиск ключей, атака методом тотального перебора имеет значительно меньше шансов на успех. Однако если вы не припасли лишний миллион долларов, который можно потратить на изготовление такого оборудования, есть другой, более дешевый, способ попытаться вскрыть интересующий вас ключ.
В мире имеется огромное количество компьютеров (по оценкам экспертов, в 1996 г. их число достигло 200 млн), которые, чтобы не простаивать, могли бы опробовать ключи. Эксперимент, проведенный в начале 1997 г., показал, что таким способом за две недели можно вскрыть 48-битный ключ. И хотя этот ключ был найден методом тотального перебора после проверки чуть более половины всех возможных ключей, полученный результат впечатляет, поскольку в ходе атаки одновременно использовались не более 5 тысяч компьютеров из существующих 200 миллионов, а в общей сложности в атаке оказались задействованными лишь 7 тысяч компьютеров.
Основное препятствие на пути к использованию миллионов вычислительных устройств, разбросанных по всему миру, заключается в невозможности сделать так, чтобы их владельцы приняли участие в атаке. Можно, конечно, вежливо попросить каждого из них об услуге, но во-первых, на это уйдет уйма времени, а во-вторых, ответом в большинстве случаев будет, скорее всего, твердое "нет". Можно попытаться тайком проникнуть на чужие компьютеры через сеть, но на это понадобится еще больше времени, да вдобавок вас могут арестовать.
Более разумным представляется создание компьютерного вируса, который вместо того, чтобы стирать файлы с жесткого диска и выдавать на дисплей % глупые сообщения, незаметно для владельца компьютера будет перебирать возможные ключи. Проведенные исследования показывают, что в распоряжении вируса будет от 70 до 90% процессорного времени зараженного им компьютера.

После вскрытия ключа вирус может породить новый вирус, содержащий информацию о найденном ключе, и отправить его странствовать по компьютерной сети до тех пор, пока он не доберется до своего хозяина.
При более тонком подходе вирус, обнаруживший ключ, выдаст на экран компьютера информацию вида:
В ВАШЕМ КОМПЬЮТЕРЕ ОБНАРУЖЕНА СЕРЬЕЗНАЯ ОШИБКА!
ПОЖАЛУЙСТА, ПОЗВОНИТЕ ПО ТЕЛЕФОНУ (095)123-45-67
И ЗАЧИТАЙТЕ ОПЕРАТОРУ СЛЕДУЮЩЕЕ 48-БИТОВОЕ ЧИСЛО:
хххххххх ххххххх ххххххх ххххххх ххххххх ххххххх
ПЕРВОМУ, КТО СООБЩИТ ОБ ЭТОЙ ОШИБКЕ, ГАРАНТИРОВАНО
ВОЗНАГРАЖДЕНИЕ В РАЗМЕРЕ 100 (СТА) ДОЛЛАРОВ.
Если вирусу удастся заразить 10 млн компьютеров, каждый из которых станет проверять хотя бы 1 тыс. ключей в секунду, то 56-битный ключ будет найден менее чем через 3 месяца. Дополнительно придется раскошелиться на подкуп производителей антивирусных программ, однако к компьютерной криптографии, о которой сейчас идет речь, эта проблема никакого отношения не имеет.

Сложность вскрытия

Таблица 6.2. Сложность вскрытия 64-битного ключа с помощью "китайской лотереи"

Страна	Численность населения	Количество телевизоров и радиоприемников	Сложность вскрытия 64-битового ключа с помощью "китайской лотереи"
Китай		1 190 431 000	257 000 000	43 часа
США	260 714 000	739 000 000	6,9 часов
Ирак	19 890 000	4 730 000	44 дня
Израиль	5 051 000	3 640 000	58 дней

Биотехнология

Предположим такую ситуацию: с использованием генной инженерии удалось вывести особую породу травоядных динозавров. Их нарекли "криптозаврами", поскольку они состоят из клеток, которые могут проверять криптографические ключи. Шифрованный и соответствующий открытый теки передаются в клетки криптозавра с помощью магнитооптических средин. Найденный ключ выводится специальными клетками, способными перемещаться в пределах тела криптозавра. Поскольку динозавр в среднем состоит из 2 14 клеток, то при условии, что каждая из них успевает проверить 1 миллион ключей в секунду, на поиск 64-битного ключа уйдет не более 1 с.

Для этой же цели можно использовать клетки морских водорослей. Например, на площади в 500 км2 и на глубине в 1 м их можно разместить в количестве 1023. Если каждая из них будет обрабатывать 1 млн ключей в секунду. то 128-битный ключ будет вскрыт менее чем за сотню лет. Шифрованный и открытый тексты передаются водорослям с помощью спутника, а сигналом о нахождении искомого ключа служит изменение окраски водорослей вокруг клетки, отыскавшей этот ключ. За советами по разведению морских водорослей криптоаналитики могут обратиться на биологический факультет ближайшего университета.

Трудоемкость разложения

Таблица 6.3. Трудоемкость разложения больших чисел на множители

Количество бит в двоичном представлении числа	Количество мопс-лет для разложения на множители
768	3-10 5
1024	3-10 7
1280	3-10 9
1536	3-10 11
2048	3-10 14

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

Таблица 6.4. Рекомендуемая длина открытого ключа (в битах)

Год	Хакер	Крупная корпорация	Правительство
2000	1024	1280	1536
2005	1280	1536	2048
2010	1280	1536	2048
2015	1536	2048	2048

С приведенными в табл. 6.4 данными согласны далеко не все авторитетные криптографы. Некоторые из них наотрез отказываются делать какие-либо долгосрочные прогнозы, считая это бесполезным делом. Другие, например, специалисты из АНБ, чересчур оптимистичны, рекомендуя для систем цифровой подписи длину открытого ключа всего 512—1024 бита, что в свете данных из табл. 6.4 является совершенно недостаточным для обеспечения надлежащей долговременной защиты.

Какой длины должен быть ключ

Криптоаналитическая атака против алгоритма шифрования обычно своим острием бывает направлена в самое уязвимое место этого алгоритма.
Например, для организации шифрованной связи часто используются криптографические алгоритмы как с секретным, так и с открытым ключом. Такая криптосистема называется гибридной. Стойкость каждого из алгоритмов, входящих в состав гибридной криптосистемы, должна быть достаточной, чтобы успешно противостоять вскрытию. Например, глупо применять симметричный алгоритм с ключом длиной 128 бит совместно с асимметричным алгоритмом, в котором длина ключа составляет всего 386 бит. И наоборот, не имеет смысла задействовать симметричный алгоритм с ключом длиной 56 бит вместе с асимметричным алгоритмом с ключом /шиной 1024 бита.
В табл. 6.5 перечисляются пары длин ключей для симметричного и асимметричного криптографического алгоритма, при которых стойкость обоих алгоритмов против криптоаналитической атаки методом тотального перебора приблизительно одинакова. Из данных, приведенных в табл. 6.5, например, следует, что если используется симметричный алгоритм со 112-битным ключом, то вместе с ним должен применяться асимметричный алгоритм с 1792-битным ключом. Однако на практике ключ для асимметричного алгоритма шифрования обычно выбирают несколько более стойким, чем для симметричного, поскольку с помощью первого защищаются значительно большие объемы информации и на более продолжительный срок.

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

Длина ключа для симметричного алгоритма	Длина ключа для асимметричного алгоритма
56	384
64	512
80	768
112	1792
128	2304

Термодинамические ограничения

Из второго закона термодинамики следует, что для записи одного бита информации путем соответствующего изменения состояния среды требуется не менее kT эрг энергии, где k— постоянная Больцмана и Т— температура системы. Учитывая, что температура Вселенной составляет 3,2° по Кельвину, для изменения одного бита информации компьютеру понадобится не менее 4,4 10 -16 эрг энергии. Уменьшение температуры среды ниже уровня температуры Вселенной потребует дополнительных затрат энергии и поэтому не имеет особого смысла.

За год вся энергия, излучаемая Солнцем, составляет 1,21 10- 41 эрг. Ее хватит, чтобы произвести 2,7 1056 записей одного бита информации, что эквивалентно прогону 187-битного счетчика через все возможные состояния. Если наше довольно "прохладное" Солнце заменить сверхновой звездой, то счет-£ чик можно сделать 219-битным.

Сказанное означает, что атака методом тотального перебора против криптосистемы с 256-битным ключом энергетически неосуществима до тех пор, пока компьютеры являются объектами материального мира и их функционирование подчиняется его законам, в частности — второму закону термодинамики.

Уничтожение ключей

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

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

Запасные ключи

Рассмотрим такой возможный случай. Давид Ключкис, президент фирмы "Ключкис и К°", постоянно шифрует всю информацию, связанную с делами своей фирмы. Однако, к несчастью, он переходил улицу в неположенном месте, и его сбил 10-тонный грузовик. При этом больше всего пострадала та часть его организма, которая отвечала за хранение ключей к используемому им алгоритму шифрования. И если у Абрама Ключмана, первого заместителя Ключкиса, нет копии этих ключей, их фирма окажется в незавидном положении. Целью шифрования является защита информации от посторонних. Поэтому при условии, что Ключкис использовал стойкий криптографический алгоритм, зашифрованные им данные, касающиеся дел фирмы, будут потеряны навсегда.

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

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